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     if(value <= 0) return false;
 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 }