From 3d1d2afa535b251ddc3ded4d90bdec08f7e39fa6 Mon Sep 17 00:00:00 2001 From: Sergey Simonchik Date: Fri, 30 Oct 2015 21:34:50 +0300 Subject: [PATCH 1/1] ability to specify max capacity --- .../util/containers/CharArrayQueue.java | 105 ----------- .../util/containers/CircularCharBuffer.java | 164 ++++++++++++++++++ ...eTest.java => CircularCharBufferTest.java} | 68 ++++++-- 3 files changed, 216 insertions(+), 121 deletions(-) delete mode 100644 platform/util/src/com/intellij/util/containers/CharArrayQueue.java create mode 100644 platform/util/src/com/intellij/util/containers/CircularCharBuffer.java rename platform/util/testSrc/com/intellij/util/containers/{CharArrayQueueTest.java => CircularCharBufferTest.java} (53%) diff --git a/platform/util/src/com/intellij/util/containers/CharArrayQueue.java b/platform/util/src/com/intellij/util/containers/CharArrayQueue.java deleted file mode 100644 index 0023b9f2fd02..000000000000 --- a/platform/util/src/com/intellij/util/containers/CharArrayQueue.java +++ /dev/null @@ -1,105 +0,0 @@ -/* - * Copyright 2000-2013 JetBrains s.r.o. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package com.intellij.util.containers; - -import org.jetbrains.annotations.NotNull; - -/** - * A single threaded, resizable, circular char queue backed by an array. - * - * @author Sergey Simonchik - */ -public class CharArrayQueue { - - private char[] myArray; - private int mySize; - private int myTail; - private int myHead; - - public CharArrayQueue(int initialCapacity) { - myArray = new char[initialCapacity]; - mySize = 0; - myTail = 0; - myHead = 0; - } - - public void add(char c) { - resizeIfNeeded(mySize + 1); - doAdd(c); - } - - public void addAll(char[] buffer) { - resizeIfNeeded(mySize + buffer.length); - for (char c : buffer) { - doAdd(c); - } - } - - public void add(@NotNull String str) { - resizeIfNeeded(mySize + str.length()); - for (int i = 0; i < str.length(); i++) { - doAdd(str.charAt(i)); - } - } - - private void doAdd(char c) { - myArray[myTail] = c; - myTail++; - if (myTail >= myArray.length) { - myTail = 0; - } - mySize++; - } - - public int poll() { - if (mySize == 0) { - return -1; - } - char res = myArray[myHead]; - myHead++; - if (myHead >= myArray.length) { - myHead = 0; - } - mySize--; - return res; - } - - public boolean isEmpty() { - return mySize == 0; - } - - public int size() { - return mySize; - } - - private void resizeIfNeeded(int newSize) { - int len = myArray.length; - if (newSize > len) { - char[] newArray = new char[Math.max(len << 1, newSize)]; - if (myHead < myTail) { - System.arraycopy(myArray, myHead, newArray, 0, myTail - myHead); - } - else { - System.arraycopy(myArray, myHead, newArray, 0, len - myHead); - System.arraycopy(myArray, 0, newArray, len - myHead, myTail); - } - myArray = newArray; - myHead = 0; - myTail = mySize; - } - } - -} diff --git a/platform/util/src/com/intellij/util/containers/CircularCharBuffer.java b/platform/util/src/com/intellij/util/containers/CircularCharBuffer.java new file mode 100644 index 000000000000..912c397f9fb8 --- /dev/null +++ b/platform/util/src/com/intellij/util/containers/CircularCharBuffer.java @@ -0,0 +1,164 @@ +/* + * Copyright 2000-2015 JetBrains s.r.o. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.intellij.util.containers; + +import com.intellij.util.ArrayUtil; +import org.jetbrains.annotations.NotNull; + +/** + * A single threaded, resizable, circular char queue backed by an array. + */ +public class CircularCharBuffer { + + private char[] myArray; + private final int myMaxCapacity; + private int mySize; + private int myTail; + private int myHead; + + public CircularCharBuffer(int initialCapacity) { + this(initialCapacity, -1); + } + + public CircularCharBuffer(int initialCapacity, int maxCapacity) { + assert maxCapacity < 0 || initialCapacity <= maxCapacity; + myArray = new char[initialCapacity]; + myMaxCapacity = maxCapacity; + mySize = 0; + myTail = 0; + myHead = 0; + } + + public void add(char c) { + resizeIfNeeded(mySize + 1); + doAdd(c); + } + + public void add(char[] buffer) { + resizeIfNeeded(mySize + buffer.length); + for (char c : buffer) { + doAdd(c); + } + } + + public void add(@NotNull String str) { + resizeIfNeeded(mySize + str.length()); + for (int i = 0; i < str.length(); i++) { + doAdd(str.charAt(i)); + } + } + + private void doAdd(char c) { + myArray[myTail] = c; + myTail++; + int length = myArray.length; + if (myTail >= length) { + myTail = 0; + } + mySize++; + if (mySize > length) { + doPoll(); + } + } + + public int poll() { + return doPoll(); + } + + public int doPoll() { + if (mySize == 0) { + return -1; + } + char res = myArray[myHead]; + myHead++; + if (myHead >= myArray.length) { + myHead = 0; + } + mySize--; + return res; + } + + @NotNull + public String getText() { + normalize(); + return new String(myArray, 0, mySize); + } + + public boolean isEmpty() { + return mySize == 0; + } + + public int size() { + return mySize; + } + + private boolean resizeIfNeeded(int newSize) { + int length = myArray.length; + if (newSize <= length) { + return true; + } + if (myMaxCapacity > -1 && length == myMaxCapacity) { + return false; + } + normalize(); + int newLength = Math.max(length << 1, newSize); + if (myMaxCapacity > -1) { + newLength = Math.min(myMaxCapacity, newLength); + } + char[] newArray = new char[newLength]; + System.arraycopy(myArray, myHead, newArray, 0, mySize); + myArray = newArray; + myTail = mySize % newArray.length; + return true; + } + + /** + * Updates internal data to make sure {@code myHead} points to zero index of {@code myArray}. + * As a result of this operation there will be no visible changes to clients. + */ + private void normalize() { + if (myHead == 0) { + return; + } + int length = myArray.length; + if (myHead < myTail) { + moveSubArrayLeft(myArray, myHead, mySize, myHead); + } + else { + int headSize = myTail; + int tailSize = length - myHead; + reverseSubArray(myArray, 0, headSize); + reverseSubArray(myArray, length - tailSize, tailSize); + reverseSubArray(myArray, 0, length); + moveSubArrayLeft(myArray, length - headSize, headSize, length - headSize - tailSize); + } + myHead = 0; + myTail = mySize % length; + } + + private static void moveSubArrayLeft(char[] array, int startInd, int length, int moveLeftCount) { + //noinspection ManualArrayCopy + for (int i = startInd; i < startInd + length; i++) { + array[i - moveLeftCount] = array[i]; + } + } + + private static void reverseSubArray(char[] array, int startInd, int length) { + for (int i = 0; i < length / 2; i++) { + ArrayUtil.swap(array, startInd + i, startInd + length - 1 - i); + } + } +} diff --git a/platform/util/testSrc/com/intellij/util/containers/CharArrayQueueTest.java b/platform/util/testSrc/com/intellij/util/containers/CircularCharBufferTest.java similarity index 53% rename from platform/util/testSrc/com/intellij/util/containers/CharArrayQueueTest.java rename to platform/util/testSrc/com/intellij/util/containers/CircularCharBufferTest.java index aab60be2b550..b19255622378 100644 --- a/platform/util/testSrc/com/intellij/util/containers/CharArrayQueueTest.java +++ b/platform/util/testSrc/com/intellij/util/containers/CircularCharBufferTest.java @@ -1,5 +1,5 @@ /* - * Copyright 2000-2013 JetBrains s.r.o. + * Copyright 2000-2015 JetBrains s.r.o. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -15,17 +15,14 @@ */ package com.intellij.util.containers; -import junit.framework.Assert; +import org.junit.Assert; import org.junit.Test; -/** - * @author Sergey Simonchik - */ -public class CharArrayQueueTest { +public class CircularCharBufferTest { - @org.junit.Test + @Test public void testSingleAdd() throws Exception { - CharArrayQueue queue = new CharArrayQueue(0); + CircularCharBuffer queue = new CircularCharBuffer(0); char value = '1'; queue.add(value); Assert.assertEquals(1, queue.size()); @@ -33,11 +30,11 @@ public class CharArrayQueueTest { Assert.assertEquals(-1, queue.poll()); } - @org.junit.Test + @Test public void testResize1() throws Exception { - CharArrayQueue queue = new CharArrayQueue(4); + CircularCharBuffer queue = new CircularCharBuffer(4); char[] buf = new char[] {'1', '2', '3', '4', '5'}; - queue.addAll(buf); + queue.add(buf); Assert.assertEquals(queue.size(), buf.length); for (char c : buf) { Assert.assertEquals(c, queue.poll()); @@ -45,11 +42,11 @@ public class CharArrayQueueTest { Assert.assertEquals(-1, queue.poll()); } - @org.junit.Test + @Test public void testResize2() throws Exception { - CharArrayQueue queue = new CharArrayQueue(4); + CircularCharBuffer queue = new CircularCharBuffer(4, 16); char[] buf = new char[] {'1', '2', '3', '4', '5', '6', '7', '8'}; - queue.addAll(buf); + queue.add(buf); Assert.assertEquals(queue.size(), buf.length); Assert.assertEquals(buf[0], queue.poll()); Assert.assertEquals(buf[1], queue.poll()); @@ -57,7 +54,7 @@ public class CharArrayQueueTest { queue.add(v); queue.add(v); - queue.addAll(buf); // array resize with myHead > myTail + queue.add(buf); // array resize with myHead > myTail Assert.assertEquals(queue.size(), buf.length * 2); for (int i = 2; i < buf.length; i++) { Assert.assertEquals(buf[i], queue.poll()); @@ -72,7 +69,7 @@ public class CharArrayQueueTest { @Test public void testAddString() throws Exception { - CharArrayQueue queue = new CharArrayQueue(2); + CircularCharBuffer queue = new CircularCharBuffer(2, 16); queue.add(""); Assert.assertEquals(0, queue.size()); queue.add("abc"); @@ -81,4 +78,43 @@ public class CharArrayQueueTest { Assert.assertEquals('c', queue.poll()); Assert.assertEquals(-1, queue.poll()); } + + @Test + public void testOverflow() throws Exception { + CircularCharBuffer queue = new CircularCharBuffer(1, 4); + queue.add("1"); + Assert.assertEquals("1", queue.getText()); + queue.add("2"); + Assert.assertEquals("12", queue.getText()); + queue.add("3"); + Assert.assertEquals("123", queue.getText()); + queue.add("4"); + Assert.assertEquals("1234", queue.getText()); + queue.add("5"); + Assert.assertEquals("2345", queue.getText()); + queue.add("6"); + Assert.assertEquals("3456", queue.getText()); + queue.add("7"); + Assert.assertEquals("4567", queue.getText()); + queue.add("8"); + Assert.assertEquals("5678", queue.getText()); + queue.add("9"); + Assert.assertEquals("6789", queue.getText()); + } + + @Test + public void testOverflowComplex() throws Exception { + CircularCharBuffer queue = new CircularCharBuffer(1, 10); + String alphabet = "abcdefghijklmnopqrstuvwxyz"; + queue.add(alphabet); + Assert.assertEquals(alphabet.substring(alphabet.length() - 10), queue.getText()); + queue.add(alphabet); + Assert.assertEquals(alphabet.substring(alphabet.length() - 10), queue.getText()); + queue.add(alphabet.substring(0, 4)); + Assert.assertEquals("uvwxyzabcd", queue.getText()); + queue.poll(); + Assert.assertEquals("vwxyzabcd", queue.getText()); + queue.add("12"); + Assert.assertEquals("wxyzabcd12", queue.getText()); + } } -- 2.32.0