+++ /dev/null
-/*
- * 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;
- }
- }
-
-}
--- /dev/null
+/*
+ * 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);
+ }
+ }
+}
/*
- * 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());
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());
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());
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());
@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");
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());
+ }
}
projects / idea / community.git / commitdiff