Merge branch 'master' of plugins/structuralsearch
[idea/community.git] / platform / util / src / com / intellij / util / containers / CharArrayQueue.java
1 /*
2  * Copyright 2000-2013 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 org.jetbrains.annotations.NotNull;
19
20 /**
21  * A single threaded, resizable, circular char queue backed by an array.
22  *
23  * @author Sergey Simonchik
24  */
25 public class CharArrayQueue {
26
27   private char[] myArray;
28   private int mySize;
29   private int myTail;
30   private int myHead;
31
32   public CharArrayQueue(int initialCapacity) {
33     myArray = new char[initialCapacity];
34     mySize = 0;
35     myTail = 0;
36     myHead = 0;
37   }
38
39   public void add(char c) {
40     resizeIfNeeded(mySize + 1);
41     doAdd(c);
42   }
43
44   public void addAll(char[] buffer) {
45     resizeIfNeeded(mySize + buffer.length);
46     for (char c : buffer) {
47       doAdd(c);
48     }
49   }
50
51   public void add(@NotNull String str) {
52     resizeIfNeeded(mySize + str.length());
53     for (int i = 0; i < str.length(); i++) {
54       doAdd(str.charAt(i));
55     }
56   }
57
58   private void doAdd(char c) {
59     myArray[myTail] = c;
60     myTail++;
61     if (myTail >= myArray.length) {
62       myTail = 0;
63     }
64     mySize++;
65   }
66
67   public int poll() {
68     if (mySize == 0) {
69       return -1;
70     }
71     char res = myArray[myHead];
72     myHead++;
73     if (myHead >= myArray.length) {
74       myHead = 0;
75     }
76     mySize--;
77     return res;
78   }
79
80   public boolean isEmpty() {
81     return mySize == 0;
82   }
83
84   public int size() {
85     return mySize;
86   }
87
88   private void resizeIfNeeded(int newSize) {
89     int len = myArray.length;
90     if (newSize > len) {
91       char[] newArray = new char[Math.max(len << 1, newSize)];
92       if (myHead < myTail) {
93         System.arraycopy(myArray, myHead, newArray, 0, myTail - myHead);
94       }
95       else {
96         System.arraycopy(myArray, myHead, newArray, 0, len - myHead);
97         System.arraycopy(myArray, 0, newArray, len - myHead, myTail);
98       }
99       myArray = newArray;
100       myHead = 0;
101       myTail = mySize;
102     }
103   }
104
105 }