ability to specify max capacity
[idea/community.git] / platform / util / src / com / intellij / util / containers / CircularCharBuffer.java
1 /*
2  * Copyright 2000-2015 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.intellij.util.containers;
17
18 import com.intellij.util.ArrayUtil;
19 import org.jetbrains.annotations.NotNull;
20
21 /**
22  * A single threaded, resizable, circular char queue backed by an array.
23  */
24 public class CircularCharBuffer {
25
26   private char[] myArray;
27   private final int myMaxCapacity;
28   private int mySize;
29   private int myTail;
30   private int myHead;
31
32   public CircularCharBuffer(int initialCapacity) {
33     this(initialCapacity, -1);
34   }
35
36   public CircularCharBuffer(int initialCapacity, int maxCapacity) {
37     assert maxCapacity < 0 || initialCapacity <= maxCapacity;
38     myArray = new char[initialCapacity];
39     myMaxCapacity = maxCapacity;
40     mySize = 0;
41     myTail = 0;
42     myHead = 0;
43   }
44
45   public void add(char c) {
46     resizeIfNeeded(mySize + 1);
47     doAdd(c);
48   }
49
50   public void add(char[] buffer) {
51     resizeIfNeeded(mySize + buffer.length);
52     for (char c : buffer) {
53       doAdd(c);
54     }
55   }
56
57   public void add(@NotNull String str) {
58     resizeIfNeeded(mySize + str.length());
59     for (int i = 0; i < str.length(); i++) {
60       doAdd(str.charAt(i));
61     }
62   }
63
64   private void doAdd(char c) {
65     myArray[myTail] = c;
66     myTail++;
67     int length = myArray.length;
68     if (myTail >= length) {
69       myTail = 0;
70     }
71     mySize++;
72     if (mySize > length) {
73       doPoll();
74     }
75   }
76
77   public int poll() {
78     return doPoll();
79   }
80
81   public int doPoll() {
82     if (mySize == 0) {
83       return -1;
84     }
85     char res = myArray[myHead];
86     myHead++;
87     if (myHead >= myArray.length) {
88       myHead = 0;
89     }
90     mySize--;
91     return res;
92   }
93
94   @NotNull
95   public String getText() {
96     normalize();
97     return new String(myArray, 0, mySize);
98   }
99
100   public boolean isEmpty() {
101     return mySize == 0;
102   }
103
104   public int size() {
105     return mySize;
106   }
107
108   private boolean resizeIfNeeded(int newSize) {
109     int length = myArray.length;
110     if (newSize <= length) {
111       return true;
112     }
113     if (myMaxCapacity > -1 && length == myMaxCapacity) {
114       return false;
115     }
116     normalize();
117     int newLength = Math.max(length << 1, newSize);
118     if (myMaxCapacity > -1) {
119       newLength = Math.min(myMaxCapacity, newLength);
120     }
121     char[] newArray = new char[newLength];
122     System.arraycopy(myArray, myHead, newArray, 0, mySize);
123     myArray = newArray;
124     myTail = mySize % newArray.length;
125     return true;
126   }
127
128   /**
129    * Updates internal data to make sure {@code myHead} points to zero index of {@code myArray}.
130    * As a result of this operation there will be no visible changes to clients.
131    */
132   private void normalize() {
133     if (myHead == 0) {
134       return;
135     }
136     int length = myArray.length;
137     if (myHead < myTail) {
138       moveSubArrayLeft(myArray, myHead, mySize, myHead);
139     }
140     else {
141       int headSize = myTail;
142       int tailSize = length - myHead;
143       reverseSubArray(myArray, 0, headSize);
144       reverseSubArray(myArray, length - tailSize, tailSize);
145       reverseSubArray(myArray, 0, length);
146       moveSubArrayLeft(myArray, length - headSize, headSize, length - headSize - tailSize);
147     }
148     myHead = 0;
149     myTail = mySize % length;
150   }
151
152   private static void moveSubArrayLeft(char[] array, int startInd, int length, int moveLeftCount) {
153     //noinspection ManualArrayCopy
154     for (int i = startInd; i < startInd + length; i++) {
155       array[i - moveLeftCount] = array[i];
156     }
157   }
158
159   private static void reverseSubArray(char[] array, int startInd, int length) {
160     for (int i = 0; i < length / 2; i++) {
161       ArrayUtil.swap(array, startInd + i, startInd + length - 1 - i);
162     }
163   }
164 }