--- /dev/null
+package org.apache.lucene.util.collections;
+
+import java.util.Arrays;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/**
+ * A Class wrapper for a grow-able int[] which can be sorted and intersect with
+ * other IntArrays.
+ *
+ * @lucene.experimental
+ */
+public class IntArray {
+
+ /**
+ * The int[] which holds the data
+ */
+ private int[] data;
+
+ /**
+ * Holds the number of items in the array.
+ */
+ private int size;
+
+ /**
+ * A flag which indicates whether a sort should occur of the array is
+ * already sorted.
+ */
+ private boolean shouldSort;
+
+ /**
+ * Construct a default IntArray, size 0 and surly a sort should not occur.
+ */
+ public IntArray() {
+ init(true);
+ }
+
+ private void init(boolean realloc) {
+ size = 0;
+ if (realloc) {
+ data = new int[0];
+ }
+ shouldSort = false;
+ }
+
+ /**
+ * Intersects the data with a given {@link IntHashSet}.
+ *
+ * @param set
+ * A given ArrayHashSetInt which holds the data to be intersected
+ * against
+ */
+ public void intersect(IntHashSet set) {
+ int newSize = 0;
+ for (int i = 0; i < size; ++i) {
+ if (set.contains(data[i])) {
+ data[newSize] = data[i];
+ ++newSize;
+ }
+ }
+ this.size = newSize;
+ }
+
+ /**
+ * Intersects the data with a given IntArray
+ *
+ * @param other
+ * A given IntArray which holds the data to be intersected agains
+ */
+ public void intersect(IntArray other) {
+ sort();
+ other.sort();
+
+ int myIndex = 0;
+ int otherIndex = 0;
+ int newSize = 0;
+ if (this.size > other.size) {
+ while (otherIndex < other.size && myIndex < size) {
+ while (otherIndex < other.size
+ && other.data[otherIndex] < data[myIndex]) {
+ ++otherIndex;
+ }
+ if (otherIndex == other.size) {
+ break;
+ }
+ while (myIndex < size && other.data[otherIndex] > data[myIndex]) {
+ ++myIndex;
+ }
+ if (other.data[otherIndex] == data[myIndex]) {
+ data[newSize++] = data[myIndex];
+ ++otherIndex;
+ ++myIndex;
+ }
+ }
+ } else {
+ while (otherIndex < other.size && myIndex < size) {
+ while (myIndex < size && other.data[otherIndex] > data[myIndex]) {
+ ++myIndex;
+ }
+ if (myIndex == size) {
+ break;
+ }
+ while (otherIndex < other.size
+ && other.data[otherIndex] < data[myIndex]) {
+ ++otherIndex;
+ }
+ if (other.data[otherIndex] == data[myIndex]) {
+ data[newSize++] = data[myIndex];
+ ++otherIndex;
+ ++myIndex;
+ }
+ }
+ }
+ this.size = newSize;
+ }
+
+ /**
+ * Return the size of the Array. Not the allocated size, but the number of
+ * values actually set.
+ *
+ * @return the (filled) size of the array
+ */
+ public int size() {
+ return size;
+ }
+
+ /**
+ * Adds a value to the array.
+ *
+ * @param value
+ * value to be added
+ */
+ public void addToArray(int value) {
+ if (size == data.length) {
+ int[] newArray = new int[2 * size + 1];
+ System.arraycopy(data, 0, newArray, 0, size);
+ data = newArray;
+ }
+ data[size] = value;
+ ++size;
+ shouldSort = true;
+ }
+
+ /**
+ * Equals method. Checking the sizes, than the values from the last index to
+ * the first (Statistically for random should be the same but for our
+ * specific use would find differences faster).
+ */
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof IntArray)) {
+ return false;
+ }
+
+ IntArray array = (IntArray) o;
+ if (array.size != size) {
+ return false;
+ }
+
+ sort();
+ array.sort();
+
+ boolean equal = true;
+
+ for (int i = size; i > 0 && equal;) {
+ --i;
+ equal = (array.data[i] == this.data[i]);
+ }
+
+ return equal;
+ }
+
+ /**
+ * Sorts the data. If it is needed.
+ */
+ public void sort() {
+ if (shouldSort) {
+ shouldSort = false;
+ Arrays.sort(data, 0, size);
+ }
+ }
+
+ /**
+ * Calculates a hash-code for HashTables
+ */
+ @Override
+ public int hashCode() {
+ int hash = 0;
+ for (int i = 0; i < size; ++i) {
+ hash = data[i] ^ (hash * 31);
+ }
+ return hash;
+ }
+
+ /**
+ * Get an element from a specific index.
+ *
+ * @param i
+ * index of which element should be retrieved.
+ */
+ public int get(int i) {
+ if (i >= size) {
+ throw new ArrayIndexOutOfBoundsException(i);
+ }
+ return this.data[i];
+ }
+
+ public void set(int idx, int value) {
+ if (idx >= size) {
+ throw new ArrayIndexOutOfBoundsException(idx);
+ }
+ this.data[idx] = value;
+ }
+
+ /**
+ * toString or not toString. That is the question!
+ */
+ @Override
+ public String toString() {
+ String s = "(" + size + ") ";
+ for (int i = 0; i < size; ++i) {
+ s += "" + data[i] + ", ";
+ }
+ return s;
+ }
+
+ /**
+ * Clear the IntArray (set all elements to zero).
+ * @param resize - if resize is true, then clear actually allocates
+ * a new array of size 0, essentially 'clearing' the array and freeing
+ * memory.
+ */
+ public void clear(boolean resize) {
+ init(resize);
+ }
+
+}
\ No newline at end of file
fnp / pylucene.git / blobdiff