phishman3579/java-algorithms-implementation

Bug in Queue

HaoyangFan opened this issue · 0 comments

In Queue.java,

        // Grow the array by 50% and rearrange to make sequential
        private void grow(int size) {
            int growSize = (size + (size<<1));
            T[] temp = (T[]) new Object[growSize];
            // Since the array can wrap around, make sure you grab the first chunk 
            int adjLast = lastIndex % array.length;
            if (adjLast < firstIndex) {
                System.arraycopy(array, 0, temp, array.length-adjLast, adjLast+1);
            }
            // Copy the remaining
            System.arraycopy(array, firstIndex, temp, 0, array.length-firstIndex);
            array = null;
            array = temp;
            lastIndex = (lastIndex - firstIndex);
            firstIndex = 0;
        }

I think int growSize = (size + (size<<1)) will actually triple the size instead of growing size by 50%.
I believe this is a typo and it should be int growSize = (size + (size>>1)) and I have make a pull request to fix that #100