Home | History | Annotate | Download | only in stream 
      1 /*
      2  * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved.
      3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
      4  *
      5  * This code is free software; you can redistribute it and/or modify it
      6  * under the terms of the GNU General Public License version 2 only, as
      7  * published by the Free Software Foundation.  Oracle designates this
      8  * particular file as subject to the "Classpath" exception as provided
      9  * by Oracle in the LICENSE file that accompanied this code.
     10  *
     11  * This code is distributed in the hope that it will be useful, but WITHOUT
     12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
     13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
     14  * version 2 for more details (a copy is included in the LICENSE file that
     15  * accompanied this code).
     16  *
     17  * You should have received a copy of the GNU General Public License version
     18  * 2 along with this work; if not, write to the Free Software Foundation,
     19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
     20  *
     21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
     22  * or visit www.oracle.com if you need additional information or have any
     23  * questions.
     24  */
     25 package java.util.stream;
     26 
     27 /**
     28  * Base class for a data structure for gathering elements into a buffer and then
     29  * iterating them. Maintains an array of increasingly sized arrays, so there is
     30  * no copying cost associated with growing the data structure.
     31  * @since 1.8
     32  */
     33 abstract class AbstractSpinedBuffer {
     34     /**
     35      * Minimum power-of-two for the first chunk.
     36      */
     37     public static final int MIN_CHUNK_POWER = 4;
     38 
     39     /**
     40      * Minimum size for the first chunk.
     41      */
     42     public static final int MIN_CHUNK_SIZE = 1 << MIN_CHUNK_POWER;
     43 
     44     /**
     45      * Max power-of-two for chunks.
     46      */
     47     public static final int MAX_CHUNK_POWER = 30;
     48 
     49     /**
     50      * Minimum array size for array-of-chunks.
     51      */
     52     public static final int MIN_SPINE_SIZE = 8;
     53 
     54 
     55     /**
     56      * log2 of the size of the first chunk.
     57      */
     58     protected final int initialChunkPower;
     59 
     60     /**
     61      * Index of the *next* element to write; may point into, or just outside of,
     62      * the current chunk.
     63      */
     64     protected int elementIndex;
     65 
     66     /**
     67      * Index of the *current* chunk in the spine array, if the spine array is
     68      * non-null.
     69      */
     70     protected int spineIndex;
     71 
     72     /**
     73      * Count of elements in all prior chunks.
     74      */
     75     protected long[] priorElementCount;
     76 
     77     /**
     78      * Construct with an initial capacity of 16.
     79      */
     80     protected AbstractSpinedBuffer() {
     81         this.initialChunkPower = MIN_CHUNK_POWER;
     82     }
     83 
     84     /**
     85      * Construct with a specified initial capacity.
     86      *
     87      * @param initialCapacity The minimum expected number of elements
     88      */
     89     protected AbstractSpinedBuffer(int initialCapacity) {
     90         if (initialCapacity < 0)
     91             throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
     92 
     93         this.initialChunkPower = Math.max(MIN_CHUNK_POWER,
     94                                           Integer.SIZE - Integer.numberOfLeadingZeros(initialCapacity - 1));
     95     }
     96 
     97     /**
     98      * Is the buffer currently empty?
     99      */
    100     public boolean isEmpty() {
    101         return (spineIndex == 0) && (elementIndex == 0);
    102     }
    103 
    104     /**
    105      * How many elements are currently in the buffer?
    106      */
    107     public long count() {
    108         return (spineIndex == 0)
    109                ? elementIndex
    110                : priorElementCount[spineIndex] + elementIndex;
    111     }
    112 
    113     /**
    114      * How big should the nth chunk be?
    115      */
    116     protected int chunkSize(int n) {
    117         int power = (n == 0 || n == 1)
    118                     ? initialChunkPower
    119                     : Math.min(initialChunkPower + n - 1, AbstractSpinedBuffer.MAX_CHUNK_POWER);
    120         return 1 << power;
    121     }
    122 
    123     /**
    124      * Remove all data from the buffer
    125      */
    126     public abstract void clear();
    127 }
    128