3e77e25aad7b1393e9c9f52f8535a7df6c1ed7bd
[idea/community.git] / platform / lang-impl / src / com / intellij / util / indexing / containers / SortedIdSet.java
1 /*
2  * Copyright 2000-2014 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.indexing.containers;
17
18 import com.intellij.util.indexing.ValueContainer;
19 import gnu.trove.TIntProcedure;
20
21 /**
22 * Created by Maxim.Mossienko on 5/27/2014.
23 */
24 public class SortedIdSet implements Cloneable, RandomAccessIntContainer {
25   private int[] mySet;
26   private int mySetLength;
27   private int mySize;
28
29   public SortedIdSet(final int initialCapacity) {
30     assert initialCapacity < Short.MAX_VALUE;
31     mySet = new int[initialCapacity]; // todo slightly increase size
32   }
33
34   public SortedIdSet(final int[] array, int size) {
35     mySet = array;
36     mySetLength = mySize = size;
37   }
38
39   public boolean isEmpty() {
40     return mySize == 0;
41   }
42
43   public int size() {
44     return mySize;
45   }
46
47   public boolean add(int value) {
48     assert value > 0;
49     int pos;
50
51     if (mySetLength == 0 || (mySetLength > 0 && Math.abs(mySet[mySetLength -1]) < value)) {
52       pos = -mySetLength-1; // most of the time during bulk indexing we add near the end
53     }
54     else {
55       pos = binarySearch(mySet, 0, mySetLength, value);
56     }
57     if (pos >= 0) {
58       if (mySet[pos] > 0) return false;
59       pos = -pos - 1; // found removed
60     }
61     if (mySetLength == mySet.length) {
62       int nextArraySize = mySet.length < 1024 ? mySet.length << 1 : mySet.length + mySet.length / 5;
63       int[] newSet = new int[nextArraySize];
64       System.arraycopy(mySet, 0, newSet, 0, mySet.length);
65       mySet = newSet;
66     }
67     pos = -pos - 1;
68
69     boolean lengthIsIncreased = pos == mySetLength;  // insert at end
70     if (!lengthIsIncreased && Math.abs(mySet[pos]) != value) { // todo we can shift until first removed
71       System.arraycopy(mySet, pos, mySet, pos + 1, mySetLength - pos);
72       lengthIsIncreased = true;
73     }
74     mySet[pos] = value;
75     ++mySize;
76     if (lengthIsIncreased) ++mySetLength;
77     return true;
78   }
79
80   public boolean remove(int value) {
81     assert value > 0;
82     int pos = binarySearch(mySet, 0, mySetLength, value);
83     if (pos < 0 || mySet[pos] < 0) return false;
84     mySet[pos] = -value;
85     //if (pos != mySetLength - 1) System.arraycopy(mySet, pos + 1, mySet, pos, mySetLength - pos - 1);
86     --mySize;
87     //--mySetLength;
88     return true;
89   }
90
91   @Override
92   public ValueContainer.IntIterator intIterator() {
93     return new Iterator();
94   }
95
96   @Override
97   public ValueContainer.IntPredicate intPredicate() {
98     return new ValueContainer.IntPredicate() {
99
100       @Override
101       public boolean contains(int id) {
102         return SortedIdSet.this.contains(id);
103       }
104     };
105   }
106
107   private class Iterator implements ValueContainer.IntIterator {
108     private int myCursor;
109
110     Iterator() {
111       myCursor = findNext(0);
112     }
113
114     @Override
115     public boolean hasNext() {
116       return myCursor != -1;
117     }
118
119     @Override
120     public int next() {
121       int result = get(myCursor);
122       myCursor = findNext(myCursor + 1);
123       return result;
124     }
125
126     @Override
127     public int size() {
128       return SortedIdSet.this.size();
129     }
130
131     @Override
132     public boolean hasAscendingOrder() {
133       return true;
134     }
135
136     @Override
137     public ValueContainer.IntIterator createCopyInInitialState() {
138       return new Iterator();
139     }
140   }
141
142   private static int binarySearch(int[] set, int off, int length, int key) {
143     int low = off;
144     int high = length - 1;
145
146     while (low <= high) {
147       int mid = (low + high) >>> 1;
148       int midVal = Math.abs(set[mid]);
149
150       if (midVal < key)
151         low = mid + 1;
152       else if (midVal > key)
153         high = mid - 1;
154       else
155         return mid; // key found
156     }
157     return -(low + 1);  // key not found.
158   }
159
160   public void forEach(TIntProcedure procedure) {
161     for(int i = 0; i < mySetLength; ++i) {
162       int value = mySet[i];
163       if (value > 0 && !procedure.execute(value)) break;
164     }
165   }
166
167   public boolean contains(int value) {
168     assert value > 0;
169     int pos = binarySearch(mySet, 0, mySetLength, value);
170     return pos >= 0 && mySet[pos] > 0;
171   }
172
173   @Override
174   public Object clone() {
175     try {
176       SortedIdSet set = (SortedIdSet)super.clone();
177       set.mySet = mySet.clone();
178       return set;
179     }
180     catch (CloneNotSupportedException e) {
181       throw new RuntimeException(e);
182     }
183   }
184
185   public void compact() {
186     if(2 * mySize < mySetLength && mySetLength > 5) {
187       int positivePosition = -1;
188       for(int i = 0; i < mySetLength; ++i) {
189         if (mySet[i] < 0) {
190           while(i < mySetLength && mySet[i] < 0) ++i;
191
192           if (i == mySetLength) {
193             break;
194           } else {
195             mySet[++positivePosition] = mySet[i];
196           }
197         } else {
198           ++positivePosition;
199           if (i != positivePosition) mySet[positivePosition] = mySet[i];
200         }
201       }
202       // todo slightly decrease size
203       mySetLength = (short)(positivePosition + 1);
204     }
205   }
206
207   public RandomAccessIntContainer ensureContainerCapacity(int count) {
208     int newSize = mySetLength + count;
209     if (newSize < mySet.length) return this;
210     if (newSize > ChangeBufferingList.MAX_FILES) {
211       return new IdBitSet(this, count);
212     }
213
214     newSize = ChangeBufferingList.calcNextArraySize(mySet.length, newSize);
215     assert newSize < Short.MAX_VALUE;
216
217     int[] newSet = new int[newSize]; // todo slightly increase size and compact
218     System.arraycopy(mySet, 0, newSet, 0, mySetLength);
219     mySet = newSet;
220
221     return this;
222   }
223
224   public int findNext(int i) {
225     while(i < mySetLength) {
226       if (mySet[i] > 0) return i;
227       ++i;
228     }
229     return -1;
230   }
231
232   public int get(int cursor) {
233     assert cursor < mySetLength;
234     int value = mySet[cursor];
235     assert value > 0;
236     return value;
237   }
238 }