ability to specify max capacity
authorSergey Simonchik <sergey.simonchik@jetbrains.com>
Fri, 30 Oct 2015 18:34:50 +0000 (21:34 +0300)
committerSergey Simonchik <sergey.simonchik@jetbrains.com>
Fri, 30 Oct 2015 18:35:30 +0000 (21:35 +0300)
platform/util/src/com/intellij/util/containers/CharArrayQueue.java [deleted file]
platform/util/src/com/intellij/util/containers/CircularCharBuffer.java [new file with mode: 0644]
platform/util/testSrc/com/intellij/util/containers/CircularCharBufferTest.java [moved from platform/util/testSrc/com/intellij/util/containers/CharArrayQueueTest.java with 53% similarity]

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 (file)
index 0023b9f..0000000
+++ /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 (file)
index 0000000..912c397
--- /dev/null
@@ -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);
+    }
+  }
+}
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 aab60be2b5505153587e12d0c05f1ae0b319b644..b192556223780af8cebe64ac5096cd8a81373c1a 100644 (file)
@@ -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.
  */
 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());
+  }
 }