lucene-java-3.4.0/lucene/contrib/facet/src/java/org/apache/lucene/util/collections/IntArray.java

   1 package org.apache.lucene.util.collections;
   2
   3 import java.util.Arrays;
   4
   5 /**
   6  * Licensed to the Apache Software Foundation (ASF) under one or more
   7  * contributor license agreements.  See the NOTICE file distributed with
   8  * this work for additional information regarding copyright ownership.
   9  * The ASF licenses this file to You under the Apache License, Version 2.0
  10  * (the "License"); you may not use this file except in compliance with
  11  * the License.  You may obtain a copy of the License at
  12  *
  13  *     http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  * Unless required by applicable law or agreed to in writing, software
  16  * distributed under the License is distributed on an "AS IS" BASIS,
  17  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  18  * See the License for the specific language governing permissions and
  19  * limitations under the License.
  20  */
  21
  22 /**
  23  * A Class wrapper for a grow-able int[] which can be sorted and intersect with
  24  * other IntArrays.
  25  *
  26  * @lucene.experimental
  27  */
  28 public class IntArray {
  29
  30   /**
  31    * The int[] which holds the data
  32    */
  33   private int[] data;
  34
  35   /**
  36    * Holds the number of items in the array.
  37    */
  38   private int size;
  39
  40   /**
  41    * A flag which indicates whether a sort should occur of the array is
  42    * already sorted.
  43    */
  44   private boolean shouldSort;
  45
  46   /**
  47    * Construct a default IntArray, size 0 and surly a sort should not occur.
  48    */
  49   public IntArray() {
  50     init(true);
  51   }
  52
  53   private void init(boolean realloc) {
  54     size = 0;
  55     if (realloc) {
  56       data = new int[0];
  57     }
  58     shouldSort = false;
  59   }
  60
  61   /**
  62    * Intersects the data with a given {@link IntHashSet}.
  63    *
  64    * @param set
  65    *            A given ArrayHashSetInt which holds the data to be intersected
  66    *            against
  67    */
  68   public void intersect(IntHashSet set) {
  69     int newSize = 0;
  70     for (int i = 0; i < size; ++i) {
  71       if (set.contains(data[i])) {
  72         data[newSize] = data[i];
  73         ++newSize;
  74       }
  75     }
  76     this.size = newSize;
  77   }
  78
  79   /**
  80    * Intersects the data with a given IntArray
  81    *
  82    * @param other
  83    *            A given IntArray which holds the data to be intersected agains
  84    */
  85   public void intersect(IntArray other) {
  86     sort();
  87     other.sort();
  88
  89     int myIndex = 0;
  90     int otherIndex = 0;
  91     int newSize = 0;
  92     if (this.size > other.size) {
  93       while (otherIndex < other.size && myIndex < size) {
  94         while (otherIndex < other.size
  95             && other.data[otherIndex] < data[myIndex]) {
  96           ++otherIndex;
  97         }
  98         if (otherIndex == other.size) {
  99           break;
 100         }
 101         while (myIndex < size && other.data[otherIndex] > data[myIndex]) {
 102           ++myIndex;
 103         }
 104         if (other.data[otherIndex] == data[myIndex]) {
 105           data[newSize++] = data[myIndex];
 106           ++otherIndex;
 107           ++myIndex;
 108         }
 109       }
 110     } else {
 111       while (otherIndex < other.size && myIndex < size) {
 112         while (myIndex < size && other.data[otherIndex] > data[myIndex]) {
 113           ++myIndex;
 114         }
 115         if (myIndex == size) {
 116           break;
 117         }
 118         while (otherIndex < other.size
 119             && other.data[otherIndex] < data[myIndex]) {
 120           ++otherIndex;
 121         }
 122         if (other.data[otherIndex] == data[myIndex]) {
 123           data[newSize++] = data[myIndex];
 124           ++otherIndex;
 125           ++myIndex;
 126         }
 127       }
 128     }
 129     this.size = newSize;
 130   }
 131
 132   /**
 133    * Return the size of the Array. Not the allocated size, but the number of
 134    * values actually set.
 135    *
 136    * @return the (filled) size of the array
 137    */
 138   public int size() {
 139     return size;
 140   }
 141
 142   /**
 143    * Adds a value to the array.
 144    *
 145    * @param value
 146    *            value to be added
 147    */
 148   public void addToArray(int value) {
 149     if (size == data.length) {
 150       int[] newArray = new int[2 * size + 1];
 151       System.arraycopy(data, 0, newArray, 0, size);
 152       data = newArray;
 153     }
 154     data[size] = value;
 155     ++size;
 156     shouldSort = true;
 157   }
 158
 159   /**
 160    * Equals method. Checking the sizes, than the values from the last index to
 161    * the first (Statistically for random should be the same but for our
 162    * specific use would find differences faster).
 163    */
 164   @Override
 165   public boolean equals(Object o) {
 166     if (!(o instanceof IntArray)) {
 167       return false;
 168     }
 169
 170     IntArray array = (IntArray) o;
 171     if (array.size != size) {
 172       return false;
 173     }
 174
 175     sort();
 176     array.sort();
 177
 178     boolean equal = true;
 179
 180     for (int i = size; i > 0 && equal;) {
 181       --i;
 182       equal = (array.data[i] == this.data[i]);
 183     }
 184
 185     return equal;
 186   }
 187
 188   /**
 189    * Sorts the data. If it is needed.
 190    */
 191   public void sort() {
 192     if (shouldSort) {
 193       shouldSort = false;
 194       Arrays.sort(data, 0, size);
 195     }
 196   }
 197
 198   /**
 199    * Calculates a hash-code for HashTables
 200    */
 201   @Override
 202   public int hashCode() {
 203     int hash = 0;
 204     for (int i = 0; i < size; ++i) {
 205       hash = data[i] ^ (hash * 31);
 206     }
 207     return hash;
 208   }
 209
 210   /**
 211    * Get an element from a specific index.
 212    *
 213    * @param i
 214    *            index of which element should be retrieved.
 215    */
 216   public int get(int i) {
 217     if (i >= size) {
 218       throw new ArrayIndexOutOfBoundsException(i);
 219     }
 220     return this.data[i];
 221   }
 222
 223   public void set(int idx, int value) {
 224     if (idx >= size) {
 225       throw new ArrayIndexOutOfBoundsException(idx);
 226     }
 227     this.data[idx] = value;
 228   }
 229
 230   /**
 231    * toString or not toString. That is the question!
 232    */
 233   @Override
 234   public String toString() {
 235     String s = "(" + size + ") ";
 236     for (int i = 0; i < size; ++i) {
 237       s += "" + data[i] + ", ";
 238     }
 239     return s;
 240   }
 241
 242   /**
 243    * Clear the IntArray (set all elements to zero).
 244    * @param resize - if resize is true, then clear actually allocates
 245    * a new array of size 0, essentially 'clearing' the array and freeing
 246    * memory.
 247    */
 248   public void clear(boolean resize) {
 249     init(resize);
 250   }
 251
 252 }