You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by sh...@apache.org on 2011/06/29 13:53:19 UTC
svn commit: r1141060 [10/21] - in /lucene/dev/branches/branch_3x:
dev-tools/eclipse/ dev-tools/maven/lucene/contrib/facet/ lucene/contrib/
lucene/contrib/facet/ lucene/contrib/facet/src/
lucene/contrib/facet/src/examples/ lucene/contrib/facet/src/examp...
Added: lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/cl2o/CompactLabelToOrdinal.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/cl2o/CompactLabelToOrdinal.java?rev=1141060&view=auto
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/cl2o/CompactLabelToOrdinal.java (added)
+++ lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/cl2o/CompactLabelToOrdinal.java Wed Jun 29 11:53:10 2011
@@ -0,0 +1,572 @@
+package org.apache.lucene.facet.taxonomy.writercache.cl2o;
+
+import java.io.BufferedInputStream;
+import java.io.BufferedOutputStream;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.util.Iterator;
+
+import org.apache.lucene.facet.taxonomy.CategoryPath;
+
+/**
+ * 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.
+ */
+
+/**
+ * This is a very efficient LabelToOrdinal implementation that uses a
+ * CharBlockArray to store all labels and a configurable number of HashArrays to
+ * reference the labels.
+ * <p>
+ * Since the HashArrays don't handle collisions, a {@link CollisionMap} is used
+ * to store the colliding labels.
+ * <p>
+ * This data structure grows by adding a new HashArray whenever the number of
+ * collisions in the {@link CollisionMap} exceeds {@code loadFactor} *
+ * {@link #getMaxOrdinal()}. Growing also includes reinserting all colliding
+ * labels into the HashArrays to possibly reduce the number of collisions.
+ *
+ * For setting the {@code loadFactor} see
+ * {@link #CompactLabelToOrdinal(int, float, int)}.
+ *
+ * <p>
+ * This data structure has a much lower memory footprint (~30%) compared to a
+ * Java HashMap<String, Integer>. It also only uses a small fraction of objects
+ * a HashMap would use, thus limiting the GC overhead. Ingestion speed was also
+ * ~50% faster compared to a HashMap for 3M unique labels.
+ *
+ * @lucene.experimental
+ */
+public class CompactLabelToOrdinal extends LabelToOrdinal {
+
+ public static final float DefaultLoadFactor = 0.15f;
+
+ static final char TerminatorChar = 0xffff;
+ private static final int Collision = -5;
+
+ private HashArray[] hashArrays;
+ private CollisionMap collisionMap;
+ private CharBlockArray labelRepository;
+
+ private int capacity;
+ private int threshold;
+ private float loadFactor;
+
+ public int sizeOfMap() {
+ return this.collisionMap.size();
+ }
+
+ private CompactLabelToOrdinal() {
+ }
+
+ public CompactLabelToOrdinal(int initialCapacity, float loadFactor,
+ int numHashArrays) {
+
+ this.hashArrays = new HashArray[numHashArrays];
+
+ this.capacity = determineCapacity((int) Math.pow(2, numHashArrays),
+ initialCapacity);
+ init();
+ this.collisionMap = new CollisionMap(this.labelRepository);
+
+ this.counter = 0;
+ this.loadFactor = loadFactor;
+
+ this.threshold = (int) (this.loadFactor * this.capacity);
+ }
+
+ static int determineCapacity(int minCapacity, int initialCapacity) {
+ int capacity = minCapacity;
+ while (capacity < initialCapacity) {
+ capacity <<= 1;
+ }
+ return capacity;
+ }
+
+ private void init() {
+ labelRepository = new CharBlockArray();
+ try {
+ new CategoryPath().serializeAppendTo(labelRepository);
+ } catch (IOException e) { } //can't happen
+
+ int c = this.capacity;
+ for (int i = 0; i < this.hashArrays.length; i++) {
+ this.hashArrays[i] = new HashArray(c);
+ c /= 2;
+ }
+ }
+
+ @Override
+ public void addLabel(CategoryPath label, int ordinal) {
+ if (this.collisionMap.size() > this.threshold) {
+ grow();
+ }
+
+ int hash = CompactLabelToOrdinal.stringHashCode(label);
+ for (int i = 0; i < this.hashArrays.length; i++) {
+ if (addLabel(this.hashArrays[i], label, hash, ordinal)) {
+ return;
+ }
+ }
+
+ int prevVal = this.collisionMap.addLabel(label, hash, ordinal);
+ if (prevVal != ordinal) {
+ throw new IllegalArgumentException("Label already exists: " +
+ label.toString('/') + " prev ordinal " + prevVal);
+ }
+ }
+
+ @Override
+ public void addLabel(CategoryPath label, int prefixLen, int ordinal) {
+ if (this.collisionMap.size() > this.threshold) {
+ grow();
+ }
+
+ int hash = CompactLabelToOrdinal.stringHashCode(label, prefixLen);
+ for (int i = 0; i < this.hashArrays.length; i++) {
+ if (addLabel(this.hashArrays[i], label, prefixLen, hash, ordinal)) {
+ return;
+ }
+ }
+
+ int prevVal = this.collisionMap.addLabel(label, prefixLen, hash, ordinal);
+ if (prevVal != ordinal) {
+ throw new IllegalArgumentException("Label already exists: " +
+ label.toString('/', prefixLen) + " prev ordinal " + prevVal);
+ }
+ }
+
+ @Override
+ public int getOrdinal(CategoryPath label) {
+ if (label == null) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ int hash = CompactLabelToOrdinal.stringHashCode(label);
+ for (int i = 0; i < this.hashArrays.length; i++) {
+ int ord = getOrdinal(this.hashArrays[i], label, hash);
+ if (ord != Collision) {
+ return ord;
+ }
+ }
+
+ return this.collisionMap.get(label, hash);
+ }
+
+ @Override
+ public int getOrdinal(CategoryPath label, int prefixLen) {
+ if (label == null) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ int hash = CompactLabelToOrdinal.stringHashCode(label, prefixLen);
+ for (int i = 0; i < this.hashArrays.length; i++) {
+ int ord = getOrdinal(this.hashArrays[i], label, prefixLen, hash);
+ if (ord != Collision) {
+ return ord;
+ }
+ }
+
+ return this.collisionMap.get(label, prefixLen, hash);
+ }
+
+ private void grow() {
+ HashArray temp = this.hashArrays[this.hashArrays.length - 1];
+
+ for (int i = this.hashArrays.length - 1; i > 0; i--) {
+ this.hashArrays[i] = this.hashArrays[i - 1];
+ }
+
+ this.capacity *= 2;
+ this.hashArrays[0] = new HashArray(this.capacity);
+
+ for (int i = 1; i < this.hashArrays.length; i++) {
+ int[] sourceOffsetArray = this.hashArrays[i].offsets;
+ int[] sourceCidsArray = this.hashArrays[i].cids;
+
+ for (int k = 0; k < sourceOffsetArray.length; k++) {
+
+ for (int j = 0; j < i && sourceOffsetArray[k] != 0; j++) {
+ int[] targetOffsetArray = this.hashArrays[j].offsets;
+ int[] targetCidsArray = this.hashArrays[j].cids;
+
+ int newIndex = indexFor(stringHashCode(
+ this.labelRepository, sourceOffsetArray[k]),
+ targetOffsetArray.length);
+ if (targetOffsetArray[newIndex] == 0) {
+ targetOffsetArray[newIndex] = sourceOffsetArray[k];
+ targetCidsArray[newIndex] = sourceCidsArray[k];
+ sourceOffsetArray[k] = 0;
+ }
+ }
+ }
+ }
+
+ for (int i = 0; i < temp.offsets.length; i++) {
+ int offset = temp.offsets[i];
+ if (offset > 0) {
+ int hash = stringHashCode(this.labelRepository, offset);
+ addLabelOffset(hash, temp.cids[i], offset);
+ }
+ }
+
+ CollisionMap oldCollisionMap = this.collisionMap;
+ this.collisionMap = new CollisionMap(oldCollisionMap.capacity(),
+ this.labelRepository);
+ this.threshold = (int) (this.capacity * this.loadFactor);
+
+ Iterator<CollisionMap.Entry> it = oldCollisionMap.entryIterator();
+ while (it.hasNext()) {
+ CollisionMap.Entry e = it.next();
+ addLabelOffset(stringHashCode(this.labelRepository, e.offset),
+ e.cid, e.offset);
+ }
+ }
+
+ private boolean addLabel(HashArray a, CategoryPath label, int hash,
+ int ordinal) {
+ int index = CompactLabelToOrdinal.indexFor(hash, a.offsets.length);
+ int offset = a.offsets[index];
+
+ if (offset == 0) {
+ a.offsets[index] = this.labelRepository.length();
+ try {
+ label.serializeAppendTo(this.labelRepository);
+ } catch (IOException e) {
+ // can't happen - LabelRepository.append() never throws an
+ // exception
+ }
+ a.cids[index] = ordinal;
+ return true;
+ }
+
+ return false;
+ }
+
+ private boolean addLabel(HashArray a, CategoryPath label, int prefixLen,
+ int hash, int ordinal) {
+ int index = CompactLabelToOrdinal.indexFor(hash, a.offsets.length);
+ int offset = a.offsets[index];
+
+ if (offset == 0) {
+ a.offsets[index] = this.labelRepository.length();
+ try {
+ label.serializeAppendTo(prefixLen, this.labelRepository);
+ } catch (IOException e) {
+ // can't happen - LabelRepository.append() never throws an
+ // exception
+ }
+ a.cids[index] = ordinal;
+ return true;
+ }
+
+ return false;
+ }
+
+ private void addLabelOffset(int hash, int cid, int knownOffset) {
+ for (int i = 0; i < this.hashArrays.length; i++) {
+ if (addLabelOffsetToHashArray(this.hashArrays[i], hash, cid,
+ knownOffset)) {
+ return;
+ }
+ }
+
+ this.collisionMap.addLabelOffset(hash, knownOffset, cid);
+
+ if (this.collisionMap.size() > this.threshold) {
+ grow();
+ }
+ }
+
+ private boolean addLabelOffsetToHashArray(HashArray a, int hash, int ordinal,
+ int knownOffset) {
+
+ int index = CompactLabelToOrdinal.indexFor(hash, a.offsets.length);
+ int offset = a.offsets[index];
+
+ if (offset == 0) {
+ a.offsets[index] = knownOffset;
+ a.cids[index] = ordinal;
+ return true;
+ }
+
+ return false;
+ }
+
+ private int getOrdinal(HashArray a, CategoryPath label, int hash) {
+ if (label == null) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ int index = CompactLabelToOrdinal.indexFor(hash, a.offsets.length);
+ int offset = a.offsets[index];
+ if (offset == 0) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ if (label.equalsToSerialized(labelRepository, offset)) {
+ return a.cids[index];
+ }
+
+ return Collision;
+ }
+
+ private int getOrdinal(HashArray a, CategoryPath label, int prefixLen, int hash) {
+ if (label == null) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ int index = CompactLabelToOrdinal.indexFor(hash, a.offsets.length);
+ int offset = a.offsets[index];
+ if (offset == 0) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ if (label.equalsToSerialized(prefixLen, labelRepository, offset)) {
+ return a.cids[index];
+ }
+
+ return Collision;
+ }
+
+ /**
+ * Returns index for hash code h.
+ */
+ static int indexFor(int h, int length) {
+ return h & (length - 1);
+ }
+
+ // static int stringHashCode(String label) {
+ // int len = label.length();
+ // int hash = 0;
+ // int i;
+ // for (i = 0; i < len; ++i)
+ // hash = 33 * hash + label.charAt(i);
+ //
+ // hash = hash ^ ((hash >>> 20) ^ (hash >>> 12));
+ // hash = hash ^ (hash >>> 7) ^ (hash >>> 4);
+ //
+ // return hash;
+ //
+ // }
+
+ static int stringHashCode(CategoryPath label) {
+ int hash = label.hashCode();
+
+ hash = hash ^ ((hash >>> 20) ^ (hash >>> 12));
+ hash = hash ^ (hash >>> 7) ^ (hash >>> 4);
+
+ return hash;
+
+ }
+
+ static int stringHashCode(CategoryPath label, int prefixLen) {
+ int hash = label.hashCode(prefixLen);
+
+ hash = hash ^ ((hash >>> 20) ^ (hash >>> 12));
+ hash = hash ^ (hash >>> 7) ^ (hash >>> 4);
+
+ return hash;
+
+ }
+
+ static int stringHashCode(CharBlockArray labelRepository, int offset) {
+ int hash = CategoryPath.hashCodeOfSerialized(labelRepository, offset);
+
+ hash = hash ^ ((hash >>> 20) ^ (hash >>> 12));
+ hash = hash ^ (hash >>> 7) ^ (hash >>> 4);
+
+ return hash;
+ }
+
+ // public static boolean equals(CharSequence label, CharBlockArray array,
+ // int offset) {
+ // // CONTINUE HERE
+ // int len = label.length();
+ // int bi = array.blockIndex(offset);
+ // CharBlockArray.Block b = array.blocks.get(bi);
+ // int index = array.indexInBlock(offset);
+ //
+ // for (int i = 0; i < len; i++) {
+ // if (label.charAt(i) != b.chars[index]) {
+ // return false;
+ // }
+ // index++;
+ // if (index == b.length) {
+ // b = array.blocks.get(++bi);
+ // index = 0;
+ // }
+ // }
+ //
+ // return b.chars[index] == TerminatorChar;
+ // }
+
+ /**
+ * Returns an estimate of the amount of memory used by this table. Called only in
+ * this package. Memory is consumed mainly by three structures: the hash arrays,
+ * label repository and collision map.
+ */
+ int getMemoryUsage() {
+ int memoryUsage = 0;
+ if (this.hashArrays != null) {
+ // HashArray capacity is instance-specific.
+ for (HashArray ha : this.hashArrays) {
+ // Each has 2 capacity-length arrays of ints.
+ memoryUsage += ( ha.capacity * 2 * 4 ) + 4;
+ }
+ }
+ if (this.labelRepository != null) {
+ // All blocks are the same size.
+ int blockSize = this.labelRepository.blockSize;
+ // Each block has room for blockSize UTF-16 chars.
+ int actualBlockSize = ( blockSize * 2 ) + 4;
+ memoryUsage += this.labelRepository.blocks.size() * actualBlockSize;
+ memoryUsage += 8; // Two int values for array as a whole.
+ }
+ if (this.collisionMap != null) {
+ memoryUsage += this.collisionMap.getMemoryUsage();
+ }
+ return memoryUsage;
+ }
+
+ /**
+ * Opens the file and reloads the CompactLabelToOrdinal. The file it expects
+ * is generated from the {@link #flush()} command.
+ */
+ static CompactLabelToOrdinal open(File file, float loadFactor,
+ int numHashArrays) throws IOException {
+ /**
+ * Part of the file is the labelRepository, which needs to be rehashed
+ * and label offsets re-added to the object. I am unsure as to why we
+ * can't just store these off in the file as well, but in keeping with
+ * the spirit of the original code, I did it this way. (ssuppe)
+ */
+ CompactLabelToOrdinal l2o = new CompactLabelToOrdinal();
+ l2o.loadFactor = loadFactor;
+ l2o.hashArrays = new HashArray[numHashArrays];
+
+ DataInputStream dis = null;
+ try {
+ dis = new DataInputStream(new BufferedInputStream(
+ new FileInputStream(file)));
+
+ // TaxiReader needs to load the "counter" or occupancy (L2O) to know
+ // the next unique facet. we used to load the delimiter too, but
+ // never used it.
+ l2o.counter = dis.readInt();
+
+ l2o.capacity = determineCapacity((int) Math.pow(2,
+ l2o.hashArrays.length), l2o.counter);
+ l2o.init();
+
+ // now read the chars
+ l2o.labelRepository = CharBlockArray.open(dis);
+
+ l2o.collisionMap = new CollisionMap(l2o.labelRepository);
+
+ // Calculate hash on the fly based on how CategoryPath hashes
+ // itself. Maybe in the future we can call some static based methods
+ // in CategoryPath so that this doesn't break again? I don't like
+ // having code in two different places...
+ int cid = 0;
+ // Skip the initial offset, it's the CategoryPath(0,0), which isn't
+ // a hashed value.
+ int offset = 1;
+ int lastStartOffset = offset;
+ // This loop really relies on a well-formed input (assumes pretty blindly
+ // that array offsets will work). Since the initial file is machine
+ // generated, I think this should be OK.
+ while (offset < l2o.labelRepository.length()) {
+ // First component is numcomponents, so we initialize the hash
+ // to this
+ int ncomponents = l2o.labelRepository.charAt(offset++);
+ int hash = ncomponents;
+ // If ncomponents is 0, then we are done?
+ if (ncomponents != 0) {
+
+ // usedchars is always the last member of the 'ends' array
+ // in serialization. Rather than rebuild the entire array,
+ // assign usedchars to the last value we read in. This will
+ // be slightly more memory efficient.
+ int usedchars = 0;
+ for (int i = 0; i < ncomponents; i++) {
+ usedchars = l2o.labelRepository.charAt(offset++);
+ hash = hash * 31 + usedchars;
+ }
+ // Hash the usedchars for this label
+ for (int i = 0; i < usedchars; i++) {
+ hash = hash * 31 + l2o.labelRepository.charAt(offset++);
+ }
+ }
+ // Now that we've hashed the components of the label, do the
+ // final part of the hash algorithm.
+ hash = hash ^ ((hash >>> 20) ^ (hash >>> 12));
+ hash = hash ^ (hash >>> 7) ^ (hash >>> 4);
+ // Add the label, and let's keep going
+ l2o.addLabelOffset(hash, cid, lastStartOffset);
+ cid++;
+ lastStartOffset = offset;
+ }
+
+ } catch (ClassNotFoundException cnfe) {
+ throw new IOException("Invalid file format. Cannot deserialize.");
+ } finally {
+ if (dis != null) {
+ dis.close();
+ }
+ }
+
+ l2o.threshold = (int) (l2o.loadFactor * l2o.capacity);
+ return l2o;
+
+ }
+
+ void flush(File file) throws IOException {
+ FileOutputStream fos = new FileOutputStream(file);
+
+ try {
+ BufferedOutputStream os = new BufferedOutputStream(fos);
+
+ DataOutputStream dos = new DataOutputStream(os);
+ dos.writeInt(this.counter);
+
+ // write the labelRepository
+ this.labelRepository.flush(dos);
+
+ // Closes the data output stream
+ dos.close();
+
+ } finally {
+ fos.close();
+ }
+ }
+
+ private static final class HashArray {
+ int[] offsets;
+ int[] cids;
+
+ int capacity;
+
+ HashArray(int c) {
+ this.capacity = c;
+ this.offsets = new int[this.capacity];
+ this.cids = new int[this.capacity];
+ }
+ }
+}
Added: lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/cl2o/LabelToOrdinal.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/cl2o/LabelToOrdinal.java?rev=1141060&view=auto
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/cl2o/LabelToOrdinal.java (added)
+++ lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/cl2o/LabelToOrdinal.java Wed Jun 29 11:53:10 2011
@@ -0,0 +1,73 @@
+package org.apache.lucene.facet.taxonomy.writercache.cl2o;
+
+import org.apache.lucene.facet.taxonomy.CategoryPath;
+
+/**
+ * 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.
+ */
+
+/**
+ * Abstract class for storing Label->Ordinal mappings in a taxonomy.
+ *
+ * @lucene.experimental
+ */
+public abstract class LabelToOrdinal {
+
+ protected int counter;
+ public static final int InvalidOrdinal = -2;
+
+ /**
+ * return the maximal Ordinal assigned so far
+ */
+ public int getMaxOrdinal() {
+ return this.counter;
+ }
+
+ /**
+ * Returns the next unassigned ordinal. The default behavior of this method
+ * is to simply increment a counter.
+ */
+ public int getNextOrdinal() {
+ return this.counter++;
+ }
+
+ /**
+ * Adds a new label if its not yet in the table.
+ * Throws an {@link IllegalArgumentException} if the same label with
+ * a different ordinal was previoulsy added to this table.
+ */
+ public abstract void addLabel(CategoryPath label, int ordinal);
+
+ /**
+ * Adds a new label if its not yet in the table.
+ * Throws an {@link IllegalArgumentException} if the same label with
+ * a different ordinal was previoulsy added to this table.
+ */
+ public abstract void addLabel(CategoryPath label, int prefixLen, int ordinal);
+
+ /**
+ * @return the ordinal assigned to the given label,
+ * or {@link #InvalidOrdinal} if the label cannot be found in this table.
+ */
+ public abstract int getOrdinal(CategoryPath label);
+
+ /**
+ * @return the ordinal assigned to the given label,
+ * or {@link #InvalidOrdinal} if the label cannot be found in this table.
+ */
+ public abstract int getOrdinal(CategoryPath label, int prefixLen);
+
+}
Added: lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/cl2o/package.html
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/cl2o/package.html?rev=1141060&view=auto
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/cl2o/package.html (added)
+++ lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/cl2o/package.html Wed Jun 29 11:53:10 2011
@@ -0,0 +1,11 @@
+<html>
+<head>
+<title>Category->Ordinal caching implementation using an optimized data-structures</title>
+</head>
+<body>
+ <h1>Category->Ordinal caching implementation using an optimized data-structures</h1>
+
+ The internal map data structure consumes less memory (~30%) and is faster (~50%) compared to a
+ Java HashMap<String, Integer>.
+</body>
+</html>
\ No newline at end of file
Added: lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/LruTaxonomyWriterCache.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/LruTaxonomyWriterCache.java?rev=1141060&view=auto
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/LruTaxonomyWriterCache.java (added)
+++ lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/LruTaxonomyWriterCache.java Wed Jun 29 11:53:10 2011
@@ -0,0 +1,123 @@
+package org.apache.lucene.facet.taxonomy.writercache.lru;
+
+import org.apache.lucene.facet.taxonomy.CategoryPath;
+import org.apache.lucene.facet.taxonomy.writercache.TaxonomyWriterCache;
+
+/**
+ * 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.
+ */
+
+/**
+ * LRU {@link TaxonomyWriterCache} - good choice for huge taxonomies.
+ *
+ * @lucene.experimental
+ */
+public class LruTaxonomyWriterCache implements TaxonomyWriterCache {
+
+ public enum LRUType { LRU_HASHED, LRU_STRING }
+
+ private NameIntCacheLRU cache;
+
+ public LruTaxonomyWriterCache(int cacheSize) {
+ // TODO (Facet): choose between NameHashIntCacheLRU and NameIntCacheLRU.
+ // For guaranteed correctness - not relying on no-collisions in the hash
+ // function, NameIntCacheLRU should be used:
+ // On the other hand, NameHashIntCacheLRU takes less RAM but if there
+ // are collisions (which we never found) two different paths would be
+ // mapped to the same ordinal...
+ this(cacheSize, LRUType.LRU_HASHED);
+ }
+
+ public LruTaxonomyWriterCache(int cacheSize, LRUType lruType) {
+ // TODO (Facet): choose between NameHashIntCacheLRU and NameIntCacheLRU.
+ // For guaranteed correctness - not relying on no-collisions in the hash
+ // function, NameIntCacheLRU should be used:
+ // On the other hand, NameHashIntCacheLRU takes less RAM but if there
+ // are collisions (which we never found) two different paths would be
+ // mapped to the same ordinal...
+ if (lruType == LRUType.LRU_HASHED) {
+ this.cache = new NameHashIntCacheLRU(cacheSize);
+ } else {
+ this.cache = new NameIntCacheLRU(cacheSize);
+ }
+ }
+
+ public boolean hasRoom(int n) {
+ return n<=(cache.getMaxSize()-cache.getSize());
+ }
+
+ public void close() {
+ cache.clear();
+ cache=null;
+ }
+
+ public int get(CategoryPath categoryPath) {
+ Integer res = cache.get(categoryPath);
+ if (res == null) {
+ return -1;
+ }
+
+ return res.intValue();
+ }
+
+ public int get(CategoryPath categoryPath, int length) {
+ if (length<0 || length>categoryPath.length()) {
+ length = categoryPath.length();
+ }
+ // TODO (Facet): unfortunately, we make a copy here! we can avoid part of
+ // the copy by creating a wrapper object (but this still creates a new
+ // object). A better implementation of the cache would not use Java's
+ // hash table, but rather some other hash table we can control, and
+ // pass the length parameter into it...
+ Integer res = cache.get(new CategoryPath(categoryPath, length));
+ if (res==null) {
+ return -1;
+ }
+ return res.intValue();
+ }
+
+ public boolean put(CategoryPath categoryPath, int ordinal) {
+ boolean ret = cache.put(categoryPath, new Integer(ordinal));
+ // If the cache is full, we need to clear one or more old entries
+ // from the cache. However, if we delete from the cache a recent
+ // addition that isn't yet in our reader, for this entry to be
+ // visible to us we need to make sure that the changes have been
+ // committed and we reopen the reader. Because this is a slow
+ // operation, we don't delete entries one-by-one but rather in bulk
+ // (put() removes the 2/3rd oldest entries).
+ if (ret) {
+ cache.makeRoomLRU();
+ }
+ return ret;
+ }
+
+ public boolean put(CategoryPath categoryPath, int prefixLen, int ordinal) {
+ boolean ret = cache.put(categoryPath, prefixLen, new Integer(ordinal));
+ // If the cache is full, we need to clear one or more old entries
+ // from the cache. However, if we delete from the cache a recent
+ // addition that isn't yet in our reader, for this entry to be
+ // visible to us we need to make sure that the changes have been
+ // committed and we reopen the reader. Because this is a slow
+ // operation, we don't delete entries one-by-one but rather in bulk
+ // (put() removes the 2/3rd oldest entries).
+ if (ret) {
+ cache.makeRoomLRU();
+ }
+ return ret;
+ }
+
+}
+
Added: lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/NameHashIntCacheLRU.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/NameHashIntCacheLRU.java?rev=1141060&view=auto
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/NameHashIntCacheLRU.java (added)
+++ lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/NameHashIntCacheLRU.java Wed Jun 29 11:53:10 2011
@@ -0,0 +1,46 @@
+package org.apache.lucene.facet.taxonomy.writercache.lru;
+
+import org.apache.lucene.facet.taxonomy.CategoryPath;
+
+/**
+ * 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.
+ */
+
+/**
+ * An an LRU cache of mapping from name to int.
+ * Used to cache Ordinals of category paths.
+ * It uses as key, hash of the path instead of the path.
+ * This way the cahce takes less RAM, but correctness depends on
+ * assuming no collisions.
+ *
+ * @lucene.experimental
+ */
+public class NameHashIntCacheLRU extends NameIntCacheLRU {
+
+ NameHashIntCacheLRU(int maxCacheSize) {
+ super(maxCacheSize);
+ }
+
+ @Override
+ Object key(CategoryPath name) {
+ return new Long(name.longHashCode());
+ }
+
+ @Override
+ Object key(CategoryPath name, int prefixLen) {
+ return new Long(name.longHashCode(prefixLen));
+ }
+}
Added: lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/NameIntCacheLRU.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/NameIntCacheLRU.java?rev=1141060&view=auto
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/NameIntCacheLRU.java (added)
+++ lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/NameIntCacheLRU.java Wed Jun 29 11:53:10 2011
@@ -0,0 +1,144 @@
+package org.apache.lucene.facet.taxonomy.writercache.lru;
+
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import org.apache.lucene.facet.taxonomy.CategoryPath;
+
+/**
+ * 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.
+ */
+
+/**
+ * An an LRU cache of mapping from name to int.
+ * Used to cache Ordinals of category paths.
+ *
+ * @lucene.experimental
+ */
+// Note: Nothing in this class is synchronized. The caller is assumed to be
+// synchronized so that no two methods of this class are called concurrently.
+class NameIntCacheLRU {
+
+ private HashMap<Object, Integer> cache;
+ long nMisses = 0; // for debug
+ long nHits = 0; // for debug
+ private int maxCacheSize;
+
+ NameIntCacheLRU(int maxCacheSize) {
+ this.maxCacheSize = maxCacheSize;
+ createCache(maxCacheSize);
+ }
+
+ public int getMaxSize() {
+ return maxCacheSize;
+ }
+
+ public int getSize() {
+ return cache.size();
+ }
+
+ private void createCache (int maxSize) {
+ if (maxSize<Integer.MAX_VALUE) {
+ cache = new LinkedHashMap<Object, Integer>(1000,(float)0.7,true); //for LRU
+ } else {
+ cache = new HashMap<Object, Integer>(1000,(float)0.7); //no need for LRU
+ }
+ }
+
+ Integer get (CategoryPath name) {
+ Integer res = cache.get(key(name));
+ if (res==null) {
+ nMisses ++;
+ } else {
+ nHits ++;
+ }
+ return res;
+ }
+
+ /**
+ * Subclasses can override this to provide caching by e.g. hash of the string.
+ * @param name
+ * @return
+ */
+ Object key(CategoryPath name) {
+ // Note that a copy constructor (cloning) here is necessary, because a
+ // CategoryPath object is mutable, so we cannot save a reference to an
+ // existing CategoryPath. Subclasses which override this method can
+ // avoid this cloning by, e.g., hashing the name.
+ return new CategoryPath(name);
+ }
+
+ Object key(CategoryPath name, int prefixLen) {
+ // Note that a copy constructor (cloning) here is necessary, because a
+ // CategoryPath object is mutable, so we cannot save a reference to an
+ // existing CategoryPath. Subclasses which override this method can
+ // avoid this cloning by, e.g., hashing the name.
+ return new CategoryPath(name, prefixLen);
+ }
+
+ /**
+ * Add a new value to cache.
+ * Return true if cache became full and some room need to be made.
+ */
+ boolean put (CategoryPath name, Integer val) {
+ cache.put(key(name), val);
+ return isCacheFull();
+ }
+
+ boolean put (CategoryPath name, int prefixLen, Integer val) {
+ cache.put(key(name, prefixLen), val);
+ return isCacheFull();
+ }
+
+ private boolean isCacheFull() {
+ return (cache.size()>maxCacheSize);
+ }
+
+ void clear() {
+ cache.clear();
+ }
+
+ String stats() {
+ return "#miss="+nMisses+" #hit="+nHits;
+ }
+
+ /**
+ * If cache is full remove least recently used entries from cache.
+ * Return true if anything was removed, false otherwise.
+ *
+ * See comment in {@link LuceneTaxonomyWriter#addToCache(String, Integer)}
+ * for an explanation why we clean 2/3rds of the cache, and not just one
+ * entry.
+ */
+ boolean makeRoomLRU() {
+ if (!isCacheFull()) {
+ return false;
+ }
+ int n = cache.size() - (2*maxCacheSize)/3;
+ if (n<=0) {
+ return false;
+ }
+ Iterator<Object> it = cache.keySet().iterator();
+ int i = 0;
+ while (i<n && it.hasNext()) {
+ it.next();
+ it.remove();
+ i++;
+ }
+ return true;
+ }
+
+}
Added: lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/package.html
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/package.html?rev=1141060&view=auto
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/package.html (added)
+++ lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/lru/package.html Wed Jun 29 11:53:10 2011
@@ -0,0 +1,9 @@
+<html>
+<head>
+<title>An LRU cache implementation for the CategoryPath to Ordinal map</title>
+</head>
+<body>
+ <h1>An LRU cache implementation for the CategoryPath to Ordinal map</h1>
+
+</body>
+</html>
\ No newline at end of file
Added: lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/package.html
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/package.html?rev=1141060&view=auto
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/package.html (added)
+++ lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/package.html Wed Jun 29 11:53:10 2011
@@ -0,0 +1,9 @@
+<html>
+<head>
+<title>Improves indexing time by caching a map of CategoryPath to their Ordinal</title>
+</head>
+<body>
+ <h1>Improves indexing time by caching a map of CategoryPath to their Ordinal</h1>
+
+</body>
+</html>
\ No newline at end of file
Added: lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/MultiCategoryListIterator.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/MultiCategoryListIterator.java?rev=1141060&view=auto
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/MultiCategoryListIterator.java (added)
+++ lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/MultiCategoryListIterator.java Wed Jun 29 11:53:10 2011
@@ -0,0 +1,83 @@
+package org.apache.lucene.facet.util;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.lucene.facet.search.CategoryListIterator;
+
+/**
+ * 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.
+ */
+
+/**
+ * Iterates over multiple {@link CategoryListIterator}s, consuming the provided
+ * iterators in order.
+ *
+ * @lucene.experimental
+ */
+public class MultiCategoryListIterator implements CategoryListIterator {
+
+ private final CategoryListIterator[] iterators;
+ private final List<CategoryListIterator> validIterators;
+ private final List<CategoryListIterator> perDocValidIterators;
+
+ /** Receives the iterators to iterate on */
+ public MultiCategoryListIterator(CategoryListIterator... iterators) {
+ this.iterators = iterators;
+ this.validIterators = new ArrayList<CategoryListIterator>();
+ this.perDocValidIterators = new ArrayList<CategoryListIterator>();
+ }
+
+ /** Fails if all given iterators fail to init */
+ public boolean init() throws IOException {
+ for (CategoryListIterator cli : iterators) {
+ if (cli.init()) {
+ validIterators.add(cli);
+ }
+ }
+ return !validIterators.isEmpty();
+ }
+
+ /**
+ * Return a value larger than {@link Integer#MAX_VALUE} only if all
+ * iterators are exhausted
+ */
+ public long nextCategory() throws IOException {
+ while (!perDocValidIterators.isEmpty()) {
+ long value = perDocValidIterators.get(0).nextCategory();
+ if (value <= Integer.MAX_VALUE) {
+ return value;
+ }
+ perDocValidIterators.remove(0);
+ }
+ return 0x100000000L;
+ }
+
+ /**
+ * Fails only if skipTo on all the provided iterators returned {@code false}
+ */
+ public boolean skipTo(int docId) throws IOException {
+ perDocValidIterators.clear();
+ for (CategoryListIterator cli : validIterators) {
+ if (cli.skipTo(docId)) {
+ perDocValidIterators.add(cli);
+ }
+ }
+ return !perDocValidIterators.isEmpty();
+ }
+
+}
Added: lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/PartitionsUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/PartitionsUtils.java?rev=1141060&view=auto
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/PartitionsUtils.java (added)
+++ lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/PartitionsUtils.java Wed Jun 29 11:53:10 2011
@@ -0,0 +1,104 @@
+package org.apache.lucene.facet.util;
+
+import org.apache.lucene.facet.index.params.CategoryListParams;
+import org.apache.lucene.facet.index.params.FacetIndexingParams;
+import org.apache.lucene.facet.search.params.FacetSearchParams;
+import org.apache.lucene.facet.taxonomy.TaxonomyReader;
+
+/**
+ * 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.
+ */
+
+/**
+ * Utilities for partitions - sizes and such
+ *
+ * @lucene.experimental
+ */
+public final class PartitionsUtils {
+
+ /**
+ * Get the offset for a given partition. That is, what is the minimum number an
+ * ordinal could be for a particular partition.
+ */
+ public final static int partitionOffset ( FacetIndexingParams iParams,
+ int partitionNumber,
+ final TaxonomyReader taxonomyReader) {
+ return partitionNumber * partitionSize(iParams, taxonomyReader);
+ }
+
+ /**
+ * @see #partitionOffset(FacetIndexingParams, int, TaxonomyReader)
+ */
+ public final static int partitionOffset ( FacetSearchParams sParams,
+ int partitionNumber,
+ final TaxonomyReader taxonomyReader) {
+ return partitionOffset(sParams.getFacetIndexingParams(), partitionNumber, taxonomyReader);
+ }
+
+ /**
+ * Get the partition size in this parameter, or return the size of the taxonomy, which
+ * is smaller. (Guarantees usage of as little memory as possible at search time).
+ */
+ public final static int partitionSize(FacetIndexingParams indexingParams, final TaxonomyReader taxonomyReader) {
+ return Math.min(indexingParams.getPartitionSize(), taxonomyReader.getSize());
+ }
+
+ /**
+ * @see #partitionSize(FacetIndexingParams, TaxonomyReader)
+ */
+ public final static int partitionSize(FacetSearchParams sParams, final TaxonomyReader taxonomyReader) {
+ return partitionSize(sParams.getFacetIndexingParams(), taxonomyReader);
+ }
+
+ /**
+ * Partition number of an ordinal.
+ * <p>
+ * This allows to locate the partition containing a certain (facet) ordinal.
+ * @see FacetIndexingParams#getPartitionSize()
+ */
+ public final static int partitionNumber(FacetIndexingParams iParams, int ordinal) {
+ return ordinal / iParams.getPartitionSize();
+ }
+
+ /**
+ * @see #partitionNumber(FacetIndexingParams, int)
+ */
+ public final static int partitionNumber(FacetSearchParams sParams, int ordinal) {
+ return partitionNumber(sParams.getFacetIndexingParams(), ordinal);
+ }
+
+ /**
+ * Partition name by category ordinal
+ */
+ public final static String partitionNameByOrdinal( FacetIndexingParams iParams,
+ CategoryListParams clParams,
+ int ordinal) {
+ int partition = partitionNumber(iParams, ordinal);
+ return partitionName(clParams, partition);
+ }
+
+ /**
+ * Partition name by its number
+ */
+ public final static String partitionName(CategoryListParams clParams, int partition) {
+ String term = clParams.getTerm().text();
+ if (partition == 0) {
+ return term; // for backwards compatibility we do not add a partition number in this case
+ }
+ return term + partition;
+ }
+
+}
Added: lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/RandomSample.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/RandomSample.java?rev=1141060&view=auto
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/RandomSample.java (added)
+++ lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/RandomSample.java Wed Jun 29 11:53:10 2011
@@ -0,0 +1,639 @@
+package org.apache.lucene.facet.util;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+import org.apache.lucene.analysis.KeywordAnalyzer;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.index.CorruptIndexException;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.store.LockObtainFailedException;
+import org.apache.lucene.store.RAMDirectory;
+import org.apache.lucene.util.PriorityQueue;
+import org.apache.lucene.util.Version;
+
+import org.apache.lucene.facet.search.ScoredDocIDs;
+import org.apache.lucene.facet.search.ScoredDocIDsIterator;
+
+/**
+ * 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.
+ */
+
+/**
+ * Take random samples of large collections.
+ *
+ * @lucene.experimental
+ */
+public class RandomSample {
+
+ private static final Logger logger = Logger.getLogger(RandomSample.class.getName());
+
+ /**
+ * Returns <code>sampleSize</code> values from the first <code>collectionSize</code>
+ * locations of <code>collection</code>, chosen using
+ * the <code>TRAVERSAL</code> algorithm. The sample values are not sorted.
+ * @param collection The values from which a sample is wanted.
+ * @param collectionSize The number of values (from the first) from which to draw the sample.
+ * @param sampleSize The number of values to return.
+ * @return An array of values chosen from the collection.
+ * @see Algorithm#TRAVERSAL
+ */
+ public static int[] repeatableSample(ScoredDocIDs collection,
+ int collectionSize, int sampleSize)
+ throws IOException {
+ return RandomSample.repeatableSample(collection, collectionSize,
+ sampleSize, Algorithm.HASHING, Sorted.NO);
+ }
+
+ /**
+ * Returns <code>sampleSize</code> values from the first <code>collectionSize</code>
+ * locations of <code>collection</code>, chosen using <code>algorithm</code>.
+ * @param collection The values from which a sample is wanted.
+ * @param collectionSize The number of values (from the first) from which to draw the sample.
+ * @param sampleSize The number of values to return.
+ * @param algorithm Which algorithm to use.
+ * @param sorted Sorted.YES to sort the sample values in ascending order before returning;
+ * Sorted.NO to return them in essentially random order.
+ * @return An array of values chosen from the collection.
+ */
+ public static int[] repeatableSample(ScoredDocIDs collection,
+ int collectionSize, int sampleSize,
+ Algorithm algorithm, Sorted sorted)
+ throws IOException {
+ if (collection == null) {
+ throw new IOException("docIdSet is null");
+ }
+ if (sampleSize < 1) {
+ throw new IOException("sampleSize < 1 (" + sampleSize + ")");
+ }
+ if (collectionSize < sampleSize) {
+ throw new IOException("collectionSize (" + collectionSize + ") less than sampleSize (" + sampleSize + ")");
+ }
+ int[] sample = new int[sampleSize];
+ long[] times = new long[4];
+ if (algorithm == Algorithm.TRAVERSAL) {
+ RandomSample.sample1(collection, collectionSize, sample, times);
+ } else if (algorithm == Algorithm.HASHING) {
+ RandomSample.sample2(collection, collectionSize, sample, times);
+ } else {
+ throw new IllegalArgumentException("Invalid algorithm selection");
+ }
+ if (sorted == Sorted.YES) {
+ Arrays.sort(sample);
+ }
+ if (RandomSample.returnTimings) {
+ times[3] = System.currentTimeMillis();
+ if (logger.isLoggable(Level.FINEST)) {
+ logger.finest("Times: " + (times[1] - times[0]) + "ms, "
+ + (times[2] - times[1]) + "ms, " + (times[3] - times[2])+"ms");
+ }
+ }
+ return sample;
+ }
+
+ /**
+ * Returns <code>sample</code>.length values chosen from the first <code>collectionSize</code>
+ * locations of <code>collection</code>, using the TRAVERSAL algorithm. The sample is
+ * pseudorandom: no subset of the original collection
+ * is in principle more likely to occur than any other, but for a given collection
+ * and sample size, the same sample will always be returned. This algorithm walks the
+ * original collection in a methodical way that is guaranteed not to visit any location
+ * more than once, which makes sampling without replacement faster because removals don't
+ * have to be tracked, and the number of operations is proportional to the sample size,
+ * not the collection size.
+ * Times for performance measurement
+ * are returned in <code>times</code>, which must be an array of at least three longs, containing
+ * nanosecond event times. The first
+ * is set when the algorithm starts; the second, when the step size has been calculated;
+ * and the third when the sample has been taken.
+ * @param collection The set to be sampled.
+ * @param collectionSize The number of values to use (starting from first).
+ * @param sample The array in which to return the sample.
+ * @param times The times of three events, for measuring performance.
+ */
+ private static void sample1(ScoredDocIDs collection, int collectionSize, int[] sample, long[] times)
+ throws IOException {
+ ScoredDocIDsIterator it = collection.iterator();
+ if (RandomSample.returnTimings) {
+ times[0] = System.currentTimeMillis();
+ }
+ int sampleSize = sample.length;
+ int prime = RandomSample.findGoodStepSize(collectionSize, sampleSize);
+ int mod = prime % collectionSize;
+ if (RandomSample.returnTimings) {
+ times[1] = System.currentTimeMillis();
+ }
+ int sampleCount = 0;
+ int index = 0;
+ for (; sampleCount < sampleSize;) {
+ if (index + mod < collectionSize) {
+ for (int i = 0; i < mod; i++, index++) {
+ it.next();
+ }
+ } else {
+ index = index + mod - collectionSize;
+ it = collection.iterator();
+ for (int i = 0; i < index; i++) {
+ it.next();
+ }
+ }
+ sample[sampleCount++] = it.getDocID();
+ }
+ if (RandomSample.returnTimings) {
+ times[2] = System.currentTimeMillis();
+ }
+ } // end RandomSample.sample1()
+
+ /**
+ * Returns a value which will allow the caller to walk
+ * a collection of <code>collectionSize</code> values, without repeating or missing
+ * any, and spanning the collection from beginning to end at least once with
+ * <code>sampleSize</code> visited locations. Choosing a value
+ * that is relatively prime to the collection size ensures that stepping by that size (modulo
+ * the collection size) will hit all locations without repeating, eliminating the need to
+ * track previously visited locations for a "without replacement" sample. Starting with the
+ * square root of the collection size ensures that either the first or second prime tried will
+ * work (they can't both divide the collection size). It also has the property that N steps of
+ * size N will span a collection of N**2 elements once. If the sample is bigger than N, it will
+ * wrap multiple times (without repeating). If the sample is smaller, a step size is chosen
+ * that will result in at least one spanning of the collection.
+ *
+ * @param collectionSize The number of values in the collection to be sampled.
+ * @param sampleSize The number of values wanted in the sample.
+ * @return A good increment value for walking the collection.
+ */
+ private static int findGoodStepSize(int collectionSize, int sampleSize) {
+ int i = (int) Math.sqrt(collectionSize);
+ if (sampleSize < i) {
+ i = collectionSize / sampleSize;
+ }
+ do {
+ i = RandomSample.findNextPrimeAfter(i);
+ } while (collectionSize % i == 0);
+ return i;
+ } // end RandomSample.findGoodStepSize()
+
+ /**
+ * Returns the first prime number that is larger than <code>n</code>.
+ * @param n A number less than the prime to be returned.
+ * @return The smallest prime larger than <code>n</code>.
+ */
+ private static int findNextPrimeAfter(int n) {
+ n += (n % 2 == 0) ? 1 : 2; // next odd
+ foundFactor: for (;; n += 2) {
+ int sri = (int) (Math.sqrt(n));
+ for (int primeIndex = 0; primeIndex < RandomSample.N_PRIMES; primeIndex++) {
+ int p = RandomSample.primes[primeIndex];
+ if (p > sri) {
+ return n;
+ }
+ if (n % p == 0) {
+ continue foundFactor;
+ }
+ }
+ for (int p = RandomSample.primes[RandomSample.N_PRIMES - 1] + 2;; p += 2) {
+ if (p > sri) {
+ return n;
+ }
+ if (n % p == 0) {
+ continue foundFactor;
+ }
+ }
+ }
+ } // end RandomSample.findNextPrimeAfter()
+
+ /**
+ * Divides the values in <code>collection</code> into <code>numSubranges</code>
+ * subranges from <code>minValue</code> to <code>maxValue</code> and returns the
+ * number of values in each subrange. (For testing the flatness of distribution of
+ * a sample.)
+ * @param collection The collection of values to be counted.
+ * @param range The number of possible values.
+ * @param numSubranges How many intervals to divide the value range into.
+ */
+ private static int[] countsBySubrange(int[] collection, int range, int numSubranges) {
+ int[] counts = new int[numSubranges];
+ Arrays.fill(counts, 0);
+ int numInSubrange = range / numSubranges;
+ for (int j = 0; j < collection.length; j++) {
+ counts[collection[j] / numInSubrange]++;
+ }
+ return counts;
+ } // end RandomSample.countsBySubrange()
+
+ /**
+ * Factors <code>value</code> into primes.
+ */
+ public static int[] factor(long value) {
+ ArrayList<Integer> list = new ArrayList<Integer>();
+ while (value > 1 && value % 2 == 0) {
+ list.add(2);
+ value /= 2;
+ }
+ long sqrt = Math.round(Math.sqrt(value));
+ for (int pIndex = 0, lim = RandomSample.primes.length; pIndex < lim; pIndex++) {
+ int p = RandomSample.primes[pIndex];
+ if (p >= sqrt) {
+ break;
+ }
+ while (value % p == 0) {
+ list.add(p);
+ value /= p;
+ sqrt = Math.round(Math.sqrt(value));
+ }
+ }
+ if (list.size() == 0 || value > Integer.MAX_VALUE) {
+ throw new RuntimeException("Prime or too large to factor: "+value);
+ }
+ if ((int)value > 1) {
+ list.add((int)value);
+ }
+ int[] factors = new int[list.size()];
+ for (int j = 0; j < factors.length; j++) {
+ factors[j] = list.get(j).intValue();
+ }
+ return factors;
+ } // end RandomSample.factor()
+
+ /**
+ * The first N_PRIMES primes, after 2.
+ */
+ private static final int N_PRIMES = 4000;
+ private static int[] primes = new int[RandomSample.N_PRIMES];
+ static {
+ RandomSample.primes[0] = 3;
+ for (int count = 1; count < RandomSample.N_PRIMES; count++) {
+ primes[count] = RandomSample.findNextPrimeAfter(primes[count - 1]);
+ }
+ }
+
+ /**
+ * Returns <code>sample</code>.length values chosen from the first <code>collectionSize</code>
+ * locations of <code>collection</code>, using the HASHING algorithm. Performance measurements
+ * are returned in <code>times</code>, which must be an array of at least three longs. The first
+ * will be set when the algorithm starts; the second, when a hash key has been calculated and
+ * inserted into the priority queue for every element in the collection; and the third when the
+ * original elements associated with the keys remaining in the PQ have been stored in the sample
+ * array for return.
+ * <P>
+ * This algorithm slows as the sample size becomes a significant fraction of the collection
+ * size, because the PQ is as large as the sample set, and will not do early rejection of values
+ * below the minimum until it fills up, and a larger PQ contains more small values to be purged,
+ * resulting in less early rejection and more logN insertions.
+ *
+ * @param collection The set to be sampled.
+ * @param collectionSize The number of values to use (starting from first).
+ * @param sample The array in which to return the sample.
+ * @param times The times of three events, for measuring performance.
+ */
+ private static void sample2(ScoredDocIDs collection, int collectionSize, int[] sample, long[] times)
+ throws IOException {
+ if (RandomSample.returnTimings) {
+ times[0] = System.currentTimeMillis();
+ }
+ int sampleSize = sample.length;
+ IntPriorityQueue pq = new IntPriorityQueue(sampleSize);
+ /*
+ * Convert every value in the collection to a hashed "weight" value, and insert
+ * into a bounded PQ (retains only sampleSize highest weights).
+ */
+ ScoredDocIDsIterator it = collection.iterator();
+ while (it.next()) {
+ pq.insertWithReuse((int)(it.getDocID() * PHI_32) & 0x7FFFFFFF);
+ }
+ if (RandomSample.returnTimings) {
+ times[1] = System.currentTimeMillis();
+ }
+ /*
+ * Extract heap, convert weights back to original values, and return as integers.
+ */
+ Object[] heap = pq.getHeap();
+ for (int si = 0; si < sampleSize; si++) {
+ sample[si] = (int)(((IntPriorityQueue.MI)(heap[si+1])).value * PHI_32I) & 0x7FFFFFFF;
+ }
+ if (RandomSample.returnTimings) {
+ times[2] = System.currentTimeMillis();
+ }
+ } // end RandomSample.sample2()
+
+ /**
+ * A bounded priority queue for Integers, to retain a specified number of
+ * the highest-weighted values for return as a random sample.
+ */
+ private static class IntPriorityQueue extends PriorityQueue<Object> {
+
+ /**
+ * Creates a bounded PQ of size <code>size</code>.
+ * @param size The number of elements to retain.
+ */
+ public IntPriorityQueue(int size) {
+ super();
+ this.initialize(size);
+ }
+
+ /**
+ * Inserts an integer with overflow and object reuse.
+ */
+ public void insertWithReuse(int intval) {
+ if (this.mi == null) {
+ this.mi = new MI();
+ }
+ this.mi.value = intval;
+ this.mi = (MI)this.insertWithOverflow(this.mi);
+ } // end IntPriorityQueue.insertWithReuse()
+
+ /**
+ * Returns the underlying data structure for faster access. Extracting elements
+ * one at a time would require N logN time, and since we want the elements sorted
+ * in ascending order by value (not weight), the array is useful as-is.
+ * @return The underlying heap array.
+ */
+ public Object[] getHeap() {
+ return getHeapArray();
+ }
+
+ /**
+ * Returns true if <code>o1<code>'s weight is less than that of <code>o2</code>, for
+ * ordering in the PQ.
+ * @return True if <code>o1</code> weighs less than <code>o2</code>.
+ */
+ @Override
+ public boolean lessThan(Object o1, Object o2) {
+ return ((MI)o1).value < ((MI)o2).value;
+ }
+
+ /**
+ * A mutable integer that lets queue objects be reused once they start overflowing.
+ */
+ private static class MI {
+ MI() { }
+ public int value;
+ } // end class RandomSample.IntPriorityQueue.MI
+
+ /**
+ * The mutable integer instance for reuse after first overflow.
+ */
+ private MI mi;
+
+ } // end class RandomSample.IntPriorityQueue
+
+ /**
+ * For specifying which sampling algorithm to use.
+ */
+ public static class Algorithm {
+
+ /**
+ * Specifies a methodical traversal algorithm, which is guaranteed to span the collection
+ * at least once, and never to return duplicates. Faster than the hashing algorithm and
+ * uses much less space, but the randomness of the sample may be affected by systematic
+ * variations in the collection. Requires only an array for the sample, and visits only
+ * the number of elements in the sample set, not the full set.
+ */
+ // TODO (Facet): This one produces a bimodal distribution (very flat around
+ // each peak!) for collection size 10M and sample sizes 10k and 10544.
+ // Figure out why.
+ public static final Algorithm TRAVERSAL = new Algorithm("Traversal");
+
+ /**
+ * Specifies a Fibonacci-style hash algorithm (see Knuth, S&S), which generates a less
+ * systematically distributed subset of the sampled collection than the traversal method,
+ * but requires a bounded priority queue the size of the sample, and creates an object
+ * containing a sampled value and its hash, for every element in the full set.
+ */
+ public static final Algorithm HASHING = new Algorithm("Hashing");
+
+ /**
+ * Constructs an instance of an algorithm.
+ * @param name An ID for printing.
+ */
+ private Algorithm(String name) {
+ this.name = name;
+ }
+
+ /**
+ * Prints this algorithm's name.
+ */
+ @Override
+ public String toString() {
+ return this.name;
+ }
+
+ /**
+ * The name of this algorithm, for printing.
+ */
+ private String name;
+
+ } // end class RandomSample.Algorithm
+
+ /**
+ * For specifying whether to sort the sample.
+ */
+ public static class Sorted {
+
+ /**
+ * Specifies sorting the resulting sample before returning.
+ */
+ public static final Sorted YES = new Sorted("sorted");
+
+ /**
+ * Specifies not sorting the resulting sample.
+ */
+ public static final Sorted NO = new Sorted("unsorted");
+
+ /**
+ * Constructs an instance of a "sorted" selector.
+ * @param name An ID for printing.
+ */
+ private Sorted(String name) {
+ this.name = name;
+ }
+
+ /**
+ * Prints this selector's name.
+ */
+ @Override
+ public String toString() {
+ return this.name;
+ }
+
+ /**
+ * The name of this selector, for printing.
+ */
+ private String name;
+
+ } // end class RandomSample.Sorted
+
+ /**
+ * Magic number 1: prime closest to phi, in 32 bits.
+ */
+ private static final long PHI_32 = 2654435769L;
+
+ /**
+ * Magic number 2: multiplicative inverse of PHI_32, modulo 2**32.
+ */
+ private static final long PHI_32I = 340573321L;
+
+ /**
+ * Switch to cause methods to return timings.
+ */
+ private static boolean returnTimings = false;
+
+ /**
+ * Self-test.
+ */
+ public static void main(String[] args) throws Exception {
+ RandomSample.returnTimings = true;
+ /*
+ * Create an array of sequential integers, from which samples will be taken.
+ */
+ final int COLLECTION_SIZE = 10 * 1000 * 1000;
+ ScoredDocIDs collection = createAllScoredDocs(COLLECTION_SIZE);
+
+ /*
+ * Factor PHI.
+ *
+ int[] factors = RandomSample.factor(PHI_32);
+ System.out.print("Factors of PHI_32: ");
+ for (int k : factors) {
+ System.out.print(k+", ");
+ }
+ System.out.println("");
+
+ * Verify inverse relationship of PHI & phi.
+ *
+ boolean inverseValid = true;
+ for (int j = 0; j < Integer.MAX_VALUE; j++) {
+ int k = (int)(j * PHI_32) & 0x7FFFFFFF;
+ int m = (int)(k * PHI_32I) & 0X7FFFFFFF;
+ if (j != m) {
+ System.out.println("Inverse not valid for "+j);
+ inverseValid = false;
+ }
+ }
+ System.out.println("Inverse valid? "+inverseValid);
+ */
+ /*
+ * Take samples of various sizes from the full set, verify no duplicates,
+ * check flatness.
+ */
+ int[] sampleSizes = {
+ 10, 57, 100, 333, 1000, 2154, 10000
+ };
+ Algorithm[] algorithms = { Algorithm.HASHING, Algorithm.TRAVERSAL };
+ for (int sampleSize : sampleSizes) {
+ for (Algorithm algorithm : algorithms) {
+ System.out.println("Sample size " + sampleSize
+ + ", algorithm " + algorithm + "...");
+ /*
+ * Take the sample.
+ */
+ int[] sample = RandomSample.repeatableSample(
+ collection, COLLECTION_SIZE, sampleSize, algorithm, Sorted.YES);
+ /*
+ * Check for duplicates.
+ */
+ boolean noDups = true;
+ for (int j = 0; j < sampleSize - 1; j++) {
+ if (sample[j] == sample[j + 1]) {
+ System.out.println("Duplicate value "
+ + sample[j] + " at " + j + ", "
+ + (j + 1));
+ noDups = false;
+ break;
+ }
+ }
+ if (noDups) {
+ System.out.println("No duplicates.");
+ }
+ if (algorithm == Algorithm.HASHING) {
+ System.out.print("Hashed sample, up to 100 of "+sampleSize+": ");
+ int lim = Math.min(100, sampleSize);
+ for (int k = 0; k < lim; k++) {
+ System.out.print(sample[k]+", ");
+ }
+ System.out.println("");
+ }
+ /*
+ * Check flatness of distribution in sample.
+ */
+ final int N_INTERVALS = 100;
+ int[] counts = RandomSample.countsBySubrange(sample, COLLECTION_SIZE, N_INTERVALS);
+ int minCount = Integer.MAX_VALUE;
+ int maxCount = Integer.MIN_VALUE;
+ int avgCount = 0;
+ for (int j = 0; j < N_INTERVALS; j++) {
+ int count = counts[j];
+ if (count < minCount) {
+ minCount = count;
+ }
+ if (count > maxCount) {
+ maxCount = count;
+ }
+ avgCount += count;
+ }
+ avgCount /= N_INTERVALS;
+ System.out.println("Min, max, avg: "+minCount+", "+maxCount+", "+avgCount);
+
+ if (((double)minCount - avgCount)/avgCount < -0.05 && (minCount - avgCount) < -5) {
+ System.out.println("Not flat enough.");
+ } else if (((double)maxCount - avgCount)/avgCount > 0.05 && (maxCount - avgCount) > 5) {
+ System.out.println("Not flat enough.");
+ } else {
+ System.out.println("Flat enough.");
+ }
+ if (sampleSize == 10544 && algorithm == Algorithm.TRAVERSAL) {
+ System.out.print("Counts of interest: ");
+ for (int j = 0; j < N_INTERVALS; j++) {
+ System.out.print(counts[j]+", ");
+ }
+ System.out.println("");
+ }
+ }
+ }
+ System.out.println("Last prime is "
+ + RandomSample.primes[RandomSample.N_PRIMES - 1]);
+ }
+
+ private static ScoredDocIDs createAllScoredDocs(final int COLLECTION_SIZE)
+ throws CorruptIndexException, LockObtainFailedException, IOException {
+ ScoredDocIDs collection;
+
+ IndexReader reader = null;
+ Directory ramDir = new RAMDirectory();
+ try {
+ IndexWriter writer = new IndexWriter(ramDir, new IndexWriterConfig(Version.LUCENE_30, new KeywordAnalyzer()));
+ for (int i = 0; i < COLLECTION_SIZE; i++) {
+ writer.addDocument(new Document());
+ }
+ writer.commit();
+ writer.close();
+ reader = IndexReader.open(ramDir);
+ collection = ScoredDocIdsUtils.createAllDocsScoredDocIDs(reader);
+ } finally {
+ if (reader != null) {
+ reader.close();
+ }
+ ramDir.close();
+ }
+ return collection;
+ }
+} // end class RandomSample
Added: lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/ResultSortUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/ResultSortUtils.java?rev=1141060&view=auto
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/ResultSortUtils.java (added)
+++ lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/ResultSortUtils.java Wed Jun 29 11:53:10 2011
@@ -0,0 +1,194 @@
+package org.apache.lucene.facet.util;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+
+import org.apache.lucene.util.PriorityQueue;
+
+import org.apache.lucene.facet.search.Heap;
+import org.apache.lucene.facet.search.params.FacetRequest;
+import org.apache.lucene.facet.search.params.FacetRequest.SortOrder;
+import org.apache.lucene.facet.search.results.FacetResultNode;
+
+/**
+ * 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.
+ */
+
+/**
+ * Utilities for generating facet results sorted as required
+ *
+ * @lucene.experimental
+ */
+public class ResultSortUtils {
+
+ /**
+ * Create a suitable heap according to facet request being served.
+ * @return heap for maintaining results for specified request.
+ * @throws IllegalArgumentException is provided facet request is not supported
+ */
+ public static Heap<FacetResultNode> createSuitableHeap(FacetRequest facetRequest) {
+ int nresults = facetRequest.getNumResults();
+ boolean accending = (facetRequest.getSortOrder() == SortOrder.ASCENDING);
+
+ if (nresults == Integer.MAX_VALUE) {
+ return new AllValueHeap(accending);
+ }
+
+ if (accending) {
+ switch (facetRequest.getSortBy()) {
+ case VALUE:
+ return new MaxValueHeap(nresults);
+ case ORDINAL:
+ return new MaxOrdinalHeap(nresults);
+ }
+ } else {
+ switch (facetRequest.getSortBy()) {
+ case VALUE:
+ return new MinValueHeap(nresults);
+ case ORDINAL:
+ return new MinOrdinalHeap(nresults);
+ }
+ }
+ throw new IllegalArgumentException("none supported facet request: "+facetRequest);
+ }
+
+ private static class MinValueHeap extends PriorityQueue<FacetResultNode> implements Heap<FacetResultNode> {
+ public MinValueHeap(int size) {
+ initialize(size);
+ }
+
+ @Override
+ protected boolean lessThan(FacetResultNode arg0, FacetResultNode arg1) {
+ double value0 = arg0.getValue();
+ double value1 = arg1.getValue();
+
+ int valueCompare = Double.compare(value0, value1);
+ if (valueCompare == 0) {
+ return arg0.getOrdinal() < arg1.getOrdinal();
+ }
+
+ return valueCompare < 0;
+ }
+
+ }
+
+ private static class MaxValueHeap extends PriorityQueue<FacetResultNode> implements Heap<FacetResultNode> {
+ public MaxValueHeap(int size) {
+ initialize(size);
+ }
+
+ @Override
+ protected boolean lessThan(FacetResultNode arg0, FacetResultNode arg1) {
+ double value0 = arg0.getValue();
+ double value1 = arg1.getValue();
+
+ int valueCompare = Double.compare(value0, value1);
+ if (valueCompare == 0) {
+ return arg0.getOrdinal() > arg1.getOrdinal();
+ }
+
+ return valueCompare > 0;
+ }
+ }
+
+ private static class MinOrdinalHeap extends
+ PriorityQueue<FacetResultNode> implements Heap<FacetResultNode> {
+ public MinOrdinalHeap(int size) {
+ initialize(size);
+ }
+
+ @Override
+ protected boolean lessThan(FacetResultNode arg0, FacetResultNode arg1) {
+ return arg0.getOrdinal() < arg1.getOrdinal();
+ }
+
+ }
+
+ private static class MaxOrdinalHeap extends
+ PriorityQueue<FacetResultNode> implements Heap<FacetResultNode> {
+ public MaxOrdinalHeap(int size) {
+ initialize(size);
+ }
+
+ @Override
+ protected boolean lessThan(FacetResultNode arg0, FacetResultNode arg1) {
+ return arg0.getOrdinal() > arg1.getOrdinal();
+ }
+
+ }
+
+ /**
+ * Create a Heap-Look-Alike, which implements {@link Heap}, but uses a
+ * regular <code>ArrayList</code> for holding <b>ALL</b> the objects given,
+ * only sorting upon the first call to {@link #pop()}.
+ */
+ private static class AllValueHeap implements Heap<FacetResultNode> {
+ private ArrayList<FacetResultNode> resultNodes = new ArrayList<FacetResultNode>();
+ final boolean accending;
+ private boolean isReady = false;
+ public AllValueHeap(boolean accending) {
+ this.accending = accending;
+ }
+
+ public FacetResultNode insertWithOverflow(FacetResultNode node) {
+ resultNodes.add(node);
+ return null;
+ }
+
+ public FacetResultNode pop() {
+ if (!isReady) {
+ Collections.sort(resultNodes, new Comparator<FacetResultNode>() {
+ public int compare(FacetResultNode o1, FacetResultNode o2) {
+ int value = Double.compare(o1.getValue(), o2
+ .getValue());
+ if (value == 0) {
+ value = o1.getOrdinal() - o2.getOrdinal();
+ }
+ if (accending) {
+ value = -value;
+ }
+ return value;
+ }
+ });
+ isReady = true;
+ }
+
+ return resultNodes.remove(0);
+ }
+
+ public int size() {
+ return resultNodes.size();
+ }
+
+ public FacetResultNode top() {
+ if (resultNodes.size() > 0) {
+ return resultNodes.get(0);
+ }
+
+ return null;
+ }
+
+ public FacetResultNode add(FacetResultNode frn) {
+ resultNodes.add(frn);
+ return null;
+ }
+
+ public void clear() {
+ resultNodes.clear();
+ }
+ }
+}
Added: lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/ScoredDocIdsUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/ScoredDocIdsUtils.java?rev=1141060&view=auto
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/ScoredDocIdsUtils.java (added)
+++ lucene/dev/branches/branch_3x/lucene/contrib/facet/src/java/org/apache/lucene/facet/util/ScoredDocIdsUtils.java Wed Jun 29 11:53:10 2011
@@ -0,0 +1,394 @@
+package org.apache.lucene.facet.util;
+
+import java.io.IOException;
+import java.util.Arrays;
+
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.search.DocIdSet;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.OpenBitSet;
+import org.apache.lucene.util.OpenBitSetDISI;
+
+import org.apache.lucene.facet.search.ScoredDocIDs;
+import org.apache.lucene.facet.search.ScoredDocIDsIterator;
+
+/**
+ * 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.
+ */
+
+/**
+ * Utility methods for Scored Doc IDs.
+ *
+ * @lucene.experimental
+ */
+public class ScoredDocIdsUtils {
+
+ /**
+ * Create a complement of the input set. The returned {@link ScoredDocIDs}
+ * does not contain any scores, which makes sense given that the complementing
+ * documents were not scored.
+ *
+ * Note: the complement set does NOT contain doc ids which are noted as deleted by the given reader
+ *
+ * @param docids to be complemented.
+ * @param reader holding the number of documents & information about deletions.
+ */
+ public final static ScoredDocIDs getComplementSet(final ScoredDocIDs docids, final IndexReader reader)
+ throws IOException {
+ final int maxDoc = reader.maxDoc();
+
+ DocIdSet docIdSet = docids.getDocIDs();
+ final OpenBitSet complement;
+ if (docIdSet instanceof OpenBitSet) {
+ // That is the most common case, if ScoredDocIdsCollector was used.
+ complement = (OpenBitSet) ((OpenBitSet) docIdSet).clone();
+ } else {
+ complement = new OpenBitSetDISI(docIdSet.iterator(), maxDoc);
+ }
+
+ complement.flip(0, maxDoc);
+
+ // Remove all Deletions from the complement set
+ clearDeleted(reader, complement);
+
+ return createScoredDocIds(complement, maxDoc);
+ }
+
+ /**
+ * Clear all deleted documents from a given open-bit-set according to a given reader
+ */
+ private static void clearDeleted(final IndexReader reader,
+ final OpenBitSet set) throws IOException {
+
+ // If there are no deleted docs
+ if (!reader.hasDeletions()) {
+ return; // return immediately
+ }
+
+ DocIdSetIterator it = set.iterator();
+ int doc = DocIdSetIterator.NO_MORE_DOCS;
+ while ((doc = it.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
+ if (reader.isDeleted(doc)) {
+ set.fastClear(doc);
+ }
+ }
+ }
+
+ /**
+ * Create a subset of an existing ScoredDocIDs object.
+ *
+ * @param allDocIds orginal set
+ * @param sampleSet Doc Ids of the subset.
+ */
+ public static final ScoredDocIDs createScoredDocIDsSubset(final ScoredDocIDs allDocIds,
+ final int[] sampleSet) throws IOException {
+
+ // sort so that we can scan docs in order
+ final int[] docids = sampleSet;
+ Arrays.sort(docids);
+ final float[] scores = new float[docids.length];
+ // fetch scores and compute size
+ ScoredDocIDsIterator it = allDocIds.iterator();
+ int n = 0;
+ while (it.next() && n < docids.length) {
+ int doc = it.getDocID();
+ if (doc == docids[n]) {
+ scores[n] = it.getScore();
+ ++n;
+ }
+ }
+ final int size = n;
+
+ return new ScoredDocIDs() {
+
+ public DocIdSet getDocIDs() {
+ return new DocIdSet() {
+
+ @Override
+ public boolean isCacheable() { return true; }
+
+ @Override
+ public DocIdSetIterator iterator() throws IOException {
+ return new DocIdSetIterator() {
+
+ private int next = -1;
+
+ @Override
+ public int advance(int target) throws IOException {
+ while (next < size && docids[next++] < target) {
+ }
+ return next == size ? NO_MORE_DOCS : docids[next];
+ }
+
+ @Override
+ public int docID() {
+ return docids[next];
+ }
+
+ @Override
+ public int nextDoc() throws IOException {
+ if (++next >= size) {
+ return NO_MORE_DOCS;
+ }
+ return docids[next];
+ }
+
+ };
+ }
+ };
+ }
+
+ public ScoredDocIDsIterator iterator() throws IOException {
+ return new ScoredDocIDsIterator() {
+
+ int next = -1;
+
+ public boolean next() { return ++next < size; }
+
+ public float getScore() { return scores[next]; }
+
+ public int getDocID() { return docids[next]; }
+ };
+ }
+
+ public int size() { return size; }
+
+ };
+ }
+
+ /**
+ * Creates a {@link ScoredDocIDs} which returns document IDs all non-deleted doc ids
+ * according to the given reader.
+ * The returned set contains the range of [0 .. reader.maxDoc ) doc ids
+ */
+ public static final ScoredDocIDs createAllDocsScoredDocIDs (final IndexReader reader) {
+ if (reader.hasDeletions()) {
+ return new AllLiveDocsScoredDocIDs(reader);
+ }
+ return new AllDocsScoredDocIDs(reader);
+ }
+
+ /**
+ * Create a ScoredDocIDs out of a given docIdSet and the total number of documents in an index
+ */
+ public static final ScoredDocIDs createScoredDocIds(final DocIdSet docIdSet, final int maxDoc) {
+ return new ScoredDocIDs() {
+ private int size = -1;
+ public DocIdSet getDocIDs() { return docIdSet; }
+
+ public ScoredDocIDsIterator iterator() throws IOException {
+ final DocIdSetIterator docIterator = docIdSet.iterator();
+ return new ScoredDocIDsIterator() {
+ public boolean next() {
+ try {
+ return docIterator.nextDoc() != DocIdSetIterator.NO_MORE_DOCS;
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ }
+
+ public float getScore() { return DEFAULT_SCORE; }
+
+ public int getDocID() { return docIterator.docID(); }
+ };
+ }
+
+ public int size() {
+ // lazy size computation
+ if (size < 0) {
+ OpenBitSetDISI openBitSetDISI;
+ try {
+ openBitSetDISI = new OpenBitSetDISI(docIdSet.iterator(), maxDoc);
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ size = (int) openBitSetDISI.cardinality();
+ }
+ return size;
+ }
+ };
+ }
+
+ /**
+ * All docs ScoredDocsIDs - this one is simply an 'all 1' bitset. Used when
+ * there are no deletions in the index and we wish to go through each and
+ * every document
+ */
+ private static class AllDocsScoredDocIDs implements ScoredDocIDs {
+ final int maxDoc;
+
+ public AllDocsScoredDocIDs(IndexReader reader) {
+ this.maxDoc = reader.maxDoc();
+ }
+
+ public int size() {
+ return maxDoc;
+ }
+
+ public DocIdSet getDocIDs() {
+ return new DocIdSet() {
+
+ @Override
+ public boolean isCacheable() {
+ return true;
+ }
+
+ @Override
+ public DocIdSetIterator iterator() throws IOException {
+ return new DocIdSetIterator() {
+ private int next = -1;
+
+ @Override
+ public int advance(int target) throws IOException {
+ if (target <= next) {
+ target = next + 1;
+ }
+ return next = target >= maxDoc ? NO_MORE_DOCS
+ : target;
+ }
+
+ @Override
+ public int docID() {
+ return next;
+ }
+
+ @Override
+ public int nextDoc() throws IOException {
+ return ++next < maxDoc ? next : NO_MORE_DOCS;
+ }
+
+ };
+ }
+ };
+ }
+
+ public ScoredDocIDsIterator iterator() {
+ try {
+ final DocIdSetIterator iter = getDocIDs().iterator();
+ return new ScoredDocIDsIterator() {
+ public boolean next() {
+ try {
+ return iter.nextDoc() != DocIdSetIterator.NO_MORE_DOCS;
+ } catch (IOException e) {
+ // cannot happen
+ return false;
+ }
+ }
+
+ public float getScore() {
+ return DEFAULT_SCORE;
+ }
+
+ public int getDocID() {
+ return iter.docID();
+ }
+ };
+ } catch (IOException e) {
+ // cannot happen
+ throw new RuntimeException(e);
+ }
+ }
+ }
+
+ /**
+ * An All-docs bitset which has '0' for deleted documents and '1' for the
+ * rest. Useful for iterating over all 'live' documents in a given index.
+ * <p>
+ * NOTE: this class would work for indexes with no deletions at all,
+ * although it is recommended to use {@link AllDocsScoredDocIDs} to ease
+ * the performance cost of validating isDeleted() on each and every docId
+ */
+ private static final class AllLiveDocsScoredDocIDs implements ScoredDocIDs {
+ final int maxDoc;
+ final IndexReader reader;
+
+ AllLiveDocsScoredDocIDs(IndexReader reader) {
+ this.maxDoc = reader.maxDoc();
+ this.reader = reader;
+ }
+
+ public int size() {
+ return reader.numDocs();
+ }
+
+ public DocIdSet getDocIDs() {
+ return new DocIdSet() {
+
+ @Override
+ public boolean isCacheable() {
+ return true;
+ }
+
+ @Override
+ public DocIdSetIterator iterator() throws IOException {
+ return new DocIdSetIterator() {
+ private int next = -1;
+
+ @Override
+ public int advance(int target) throws IOException {
+ if (target > next) {
+ next = target - 1;
+ }
+ return nextDoc();
+ }
+
+ @Override
+ public int docID() {
+ return next;
+ }
+
+ @Override
+ public int nextDoc() throws IOException {
+ do {
+ ++next;
+ } while (next < maxDoc && reader.isDeleted(next));
+
+ return next < maxDoc ? next : NO_MORE_DOCS;
+ }
+
+ };
+ }
+ };
+ }
+
+ public ScoredDocIDsIterator iterator() {
+ try {
+ final DocIdSetIterator iter = getDocIDs().iterator();
+ return new ScoredDocIDsIterator() {
+ public boolean next() {
+ try {
+ return iter.nextDoc() != DocIdSetIterator.NO_MORE_DOCS;
+ } catch (IOException e) {
+ // cannot happen
+ return false;
+ }
+ }
+
+ public float getScore() {
+ return DEFAULT_SCORE;
+ }
+
+ public int getDocID() {
+ return iter.docID();
+ }
+ };
+ } catch (IOException e) {
+ // cannot happen
+ throw new RuntimeException(e);
+ }
+ }
+ }
+}
\ No newline at end of file