lucene-java-3.5.0/lucene/contrib/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java

   1 package org.apache.lucene.index.memory;
   2
   3 /**
   4  * Licensed to the Apache Software Foundation (ASF) under one or more
   5  * contributor license agreements.  See the NOTICE file distributed with
   6  * this work for additional information regarding copyright ownership.
   7  * The ASF licenses this file to You under the Apache License, Version 2.0
   8  * (the "License"); you may not use this file except in compliance with
   9  * the License.  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 import java.io.IOException;
  21 import java.io.Serializable;
  22 import java.io.StringReader;
  23 import java.util.Arrays;
  24 import java.util.Collection;
  25 import java.util.Collections;
  26 import java.util.Comparator;
  27 import java.util.HashMap;
  28 import java.util.HashSet;
  29 import java.util.Iterator;
  30 import java.util.Map;
  31
  32 import org.apache.lucene.analysis.Analyzer;
  33 import org.apache.lucene.analysis.TokenStream;
  34 import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
  35 import org.apache.lucene.analysis.tokenattributes.OffsetAttribute;
  36 import org.apache.lucene.analysis.tokenattributes.PositionIncrementAttribute;
  37 import org.apache.lucene.document.Document;
  38 import org.apache.lucene.document.FieldSelector;
  39 import org.apache.lucene.index.IndexReader;
  40 import org.apache.lucene.index.Term;
  41 import org.apache.lucene.index.TermDocs;
  42 import org.apache.lucene.index.TermEnum;
  43 import org.apache.lucene.index.TermFreqVector;
  44 import org.apache.lucene.index.TermPositionVector;
  45 import org.apache.lucene.index.TermPositions;
  46 import org.apache.lucene.index.TermVectorMapper;
  47 import org.apache.lucene.index.FieldInvertState;
  48 import org.apache.lucene.search.Collector;
  49 import org.apache.lucene.search.IndexSearcher;
  50 import org.apache.lucene.search.Query;
  51 import org.apache.lucene.search.Searcher;
  52 import org.apache.lucene.search.Scorer;
  53 import org.apache.lucene.search.Similarity;
  54 import org.apache.lucene.store.RAMDirectory; // for javadocs
  55 import org.apache.lucene.util.ArrayUtil;
  56 import org.apache.lucene.util.Constants; // for javadocs
  57
  58 /**
  59  * High-performance single-document main memory Apache Lucene fulltext search index.
  60  *
  61  * <h4>Overview</h4>
  62  *
  63  * This class is a replacement/substitute for a large subset of
  64  * {@link RAMDirectory} functionality. It is designed to
  65  * enable maximum efficiency for on-the-fly matchmaking combining structured and
  66  * fuzzy fulltext search in realtime streaming applications such as Nux XQuery based XML
  67  * message queues, publish-subscribe systems for Blogs/newsfeeds, text chat, data acquisition and
  68  * distribution systems, application level routers, firewalls, classifiers, etc.
  69  * Rather than targeting fulltext search of infrequent queries over huge persistent
  70  * data archives (historic search), this class targets fulltext search of huge
  71  * numbers of queries over comparatively small transient realtime data (prospective
  72  * search).
  73  * For example as in
  74  * <pre>
  75  * float score = search(String text, Query query)
  76  * </pre>
  77  * <p>
  78  * Each instance can hold at most one Lucene "document", with a document containing
  79  * zero or more "fields", each field having a name and a fulltext value. The
  80  * fulltext value is tokenized (split and transformed) into zero or more index terms
  81  * (aka words) on <code>addField()</code>, according to the policy implemented by an
  82  * Analyzer. For example, Lucene analyzers can split on whitespace, normalize to lower case
  83  * for case insensitivity, ignore common terms with little discriminatory value such as "he", "in", "and" (stop
  84  * words), reduce the terms to their natural linguistic root form such as "fishing"
  85  * being reduced to "fish" (stemming), resolve synonyms/inflexions/thesauri
  86  * (upon indexing and/or querying), etc. For details, see
  87  * <a target="_blank" href="http://today.java.net/pub/a/today/2003/07/30/LuceneIntro.html">Lucene Analyzer Intro</a>.
  88  * <p>
  89  * Arbitrary Lucene queries can be run against this class - see <a target="_blank"
  90  * href="../../../../../../../queryparsersyntax.html">Lucene Query Syntax</a>
  91  * as well as <a target="_blank"
  92  * href="http://today.java.net/pub/a/today/2003/11/07/QueryParserRules.html">Query Parser Rules</a>.
  93  * Note that a Lucene query selects on the field names and associated (indexed)
  94  * tokenized terms, not on the original fulltext(s) - the latter are not stored
  95  * but rather thrown away immediately after tokenization.
  96  * <p>
  97  * For some interesting background information on search technology, see Bob Wyman's
  98  * <a target="_blank"
  99  * href="http://bobwyman.pubsub.com/main/2005/05/mary_hodder_poi.html">Prospective Search</a>,
 100  * Jim Gray's
 101  * <a target="_blank" href="http://www.acmqueue.org/modules.php?name=Content&pa=showpage&pid=293&page=4">
 102  * A Call to Arms - Custom subscriptions</a>, and Tim Bray's
 103  * <a target="_blank"
 104  * href="http://www.tbray.org/ongoing/When/200x/2003/07/30/OnSearchTOC">On Search, the Series</a>.
 105  *
 106  *
 107  * <h4>Example Usage</h4>
 108  *
 109  * <pre>
 110  * Analyzer analyzer = PatternAnalyzer.DEFAULT_ANALYZER;
 111  * //Analyzer analyzer = new SimpleAnalyzer();
 112  * MemoryIndex index = new MemoryIndex();
 113  * index.addField("content", "Readings about Salmons and other select Alaska fishing Manuals", analyzer);
 114  * index.addField("author", "Tales of James", analyzer);
 115  * QueryParser parser = new QueryParser("content", analyzer);
 116  * float score = index.search(parser.parse("+author:james +salmon~ +fish* manual~"));
 117  * if (score &gt; 0.0f) {
 118  *     System.out.println("it's a match");
 119  * } else {
 120  *     System.out.println("no match found");
 121  * }
 122  * System.out.println("indexData=" + index.toString());
 123  * </pre>
 124  *
 125  *
 126  * <h4>Example XQuery Usage</h4>
 127  *
 128  * <pre>
 129  * (: An XQuery that finds all books authored by James that have something to do with "salmon fishing manuals", sorted by relevance :)
 130  * declare namespace lucene = "java:nux.xom.pool.FullTextUtil";
 131  * declare variable $query := "+salmon~ +fish* manual~"; (: any arbitrary Lucene query can go here :)
 132  *
 133  * for $book in /books/book[author="James" and lucene:match(abstract, $query) > 0.0]
 134  * let $score := lucene:match($book/abstract, $query)
 135  * order by $score descending
 136  * return $book
 137  * </pre>
 138  *
 139  *
 140  * <h4>No thread safety guarantees</h4>
 141  *
 142  * An instance can be queried multiple times with the same or different queries,
 143  * but an instance is not thread-safe. If desired use idioms such as:
 144  * <pre>
 145  * MemoryIndex index = ...
 146  * synchronized (index) {
 147  *    // read and/or write index (i.e. add fields and/or query)
 148  * }
 149  * </pre>
 150  *
 151  *
 152  * <h4>Performance Notes</h4>
 153  *
 154  * Internally there's a new data structure geared towards efficient indexing
 155  * and searching, plus the necessary support code to seamlessly plug into the Lucene
 156  * framework.
 157  * <p>
 158  * This class performs very well for very small texts (e.g. 10 chars)
 159  * as well as for large texts (e.g. 10 MB) and everything in between.
 160  * Typically, it is about 10-100 times faster than <code>RAMDirectory</code>.
 161  * Note that <code>RAMDirectory</code> has particularly
 162  * large efficiency overheads for small to medium sized texts, both in time and space.
 163  * Indexing a field with N tokens takes O(N) in the best case, and O(N logN) in the worst
 164  * case. Memory consumption is probably larger than for <code>RAMDirectory</code>.
 165  * <p>
 166  * Example throughput of many simple term queries over a single MemoryIndex:
 167  * ~500000 queries/sec on a MacBook Pro, jdk 1.5.0_06, server VM.
 168  * As always, your mileage may vary.
 169  * <p>
 170  * If you're curious about
 171  * the whereabouts of bottlenecks, run java 1.5 with the non-perturbing '-server
 172  * -agentlib:hprof=cpu=samples,depth=10' flags, then study the trace log and
 173  * correlate its hotspot trailer with its call stack headers (see <a
 174  * target="_blank"
 175  * href="http://java.sun.com/developer/technicalArticles/Programming/HPROF.html">
 176  * hprof tracing </a>).
 177  *
 178  */
 179 public class MemoryIndex implements Serializable {
 180
 181   /** info for each field: Map<String fieldName, Info field> */
 182   private final HashMap<String,Info> fields = new HashMap<String,Info>();
 183
 184   /** fields sorted ascending by fieldName; lazily computed on demand */
 185   private transient Map.Entry<String,Info>[] sortedFields;
 186
 187   /** pos: positions[3*i], startOffset: positions[3*i +1], endOffset: positions[3*i +2] */
 188   private final int stride;
 189
 190   /** Could be made configurable; See {@link Document#setBoost(float)} */
 191   private static final float docBoost = 1.0f;
 192
 193   private static final long serialVersionUID = 2782195016849084649L;
 194
 195   private static final boolean DEBUG = false;
 196
 197   /**
 198    * Sorts term entries into ascending order; also works for
 199    * Arrays.binarySearch() and Arrays.sort()
 200    */
 201   private static final Comparator<Object> termComparator = new Comparator<Object>() {
 202     @SuppressWarnings("unchecked")
 203     public int compare(Object o1, Object o2) {
 204       if (o1 instanceof Map.Entry<?,?>) o1 = ((Map.Entry<?,?>) o1).getKey();
 205       if (o2 instanceof Map.Entry<?,?>) o2 = ((Map.Entry<?,?>) o2).getKey();
 206       if (o1 == o2) return 0;
 207       return ((String) o1).compareTo((String) o2);
 208     }
 209   };
 210
 211   /**
 212    * Constructs an empty instance.
 213    */
 214   public MemoryIndex() {
 215     this(false);
 216   }
 217
 218   /**
 219    * Constructs an empty instance that can optionally store the start and end
 220    * character offset of each token term in the text. This can be useful for
 221    * highlighting of hit locations with the Lucene highlighter package.
 222    * Private until the highlighter package matures, so that this can actually
 223    * be meaningfully integrated.
 224    *
 225    * @param storeOffsets
 226    *            whether or not to store the start and end character offset of
 227    *            each token term in the text
 228    */
 229   private MemoryIndex(boolean storeOffsets) {
 230     this.stride = storeOffsets ? 3 : 1;
 231   }
 232
 233   /**
 234    * Convenience method; Tokenizes the given field text and adds the resulting
 235    * terms to the index; Equivalent to adding an indexed non-keyword Lucene
 236    * {@link org.apache.lucene.document.Field} that is
 237    * {@link org.apache.lucene.document.Field.Index#ANALYZED tokenized},
 238    * {@link org.apache.lucene.document.Field.Store#NO not stored},
 239    * {@link org.apache.lucene.document.Field.TermVector#WITH_POSITIONS termVectorStored with positions} (or
 240    * {@link org.apache.lucene.document.Field.TermVector#WITH_POSITIONS termVectorStored with positions and offsets}),
 241    *
 242    * @param fieldName
 243    *            a name to be associated with the text
 244    * @param text
 245    *            the text to tokenize and index.
 246    * @param analyzer
 247    *            the analyzer to use for tokenization
 248    */
 249   public void addField(String fieldName, String text, Analyzer analyzer) {
 250     if (fieldName == null)
 251       throw new IllegalArgumentException("fieldName must not be null");
 252     if (text == null)
 253       throw new IllegalArgumentException("text must not be null");
 254     if (analyzer == null)
 255       throw new IllegalArgumentException("analyzer must not be null");
 256
 257     TokenStream stream;
 258     try {
 259       stream = analyzer.reusableTokenStream(fieldName, new StringReader(text));
 260     } catch (IOException ex) {
 261       throw new RuntimeException(ex);
 262     }
 263
 264     addField(fieldName, stream);
 265   }
 266
 267   /**
 268    * Convenience method; Creates and returns a token stream that generates a
 269    * token for each keyword in the given collection, "as is", without any
 270    * transforming text analysis. The resulting token stream can be fed into
 271    * {@link #addField(String, TokenStream)}, perhaps wrapped into another
 272    * {@link org.apache.lucene.analysis.TokenFilter}, as desired.
 273    *
 274    * @param keywords
 275    *            the keywords to generate tokens for
 276    * @return the corresponding token stream
 277    */
 278   public <T> TokenStream keywordTokenStream(final Collection<T> keywords) {
 279     // TODO: deprecate & move this method into AnalyzerUtil?
 280     if (keywords == null)
 281       throw new IllegalArgumentException("keywords must not be null");
 282
 283     return new TokenStream() {
 284       private Iterator<T> iter = keywords.iterator();
 285       private int start = 0;
 286       private final CharTermAttribute termAtt = addAttribute(CharTermAttribute.class);
 287       private final OffsetAttribute offsetAtt = addAttribute(OffsetAttribute.class);
 288
 289       @Override
 290       public boolean incrementToken() {
 291         if (!iter.hasNext()) return false;
 292
 293         T obj = iter.next();
 294         if (obj == null)
 295           throw new IllegalArgumentException("keyword must not be null");
 296
 297         String term = obj.toString();
 298         clearAttributes();
 299         termAtt.setEmpty().append(term);
 300         offsetAtt.setOffset(start, start+termAtt.length());
 301         start += term.length() + 1; // separate words by 1 (blank) character
 302         return true;
 303       }
 304     };
 305   }
 306
 307   /**
 308    * Equivalent to <code>addField(fieldName, stream, 1.0f)</code>.
 309    *
 310    * @param fieldName
 311    *            a name to be associated with the text
 312    * @param stream
 313    *            the token stream to retrieve tokens from
 314    */
 315   public void addField(String fieldName, TokenStream stream) {
 316     addField(fieldName, stream, 1.0f);
 317   }
 318
 319   /**
 320    * Iterates over the given token stream and adds the resulting terms to the index;
 321    * Equivalent to adding a tokenized, indexed, termVectorStored, unstored,
 322    * Lucene {@link org.apache.lucene.document.Field}.
 323    * Finally closes the token stream. Note that untokenized keywords can be added with this method via
 324    * {@link #keywordTokenStream(Collection)}, the Lucene contrib <code>KeywordTokenizer</code> or similar utilities.
 325    *
 326    * @param fieldName
 327    *            a name to be associated with the text
 328    * @param stream
 329    *            the token stream to retrieve tokens from.
 330    * @param boost
 331    *            the boost factor for hits for this field
 332    * @see org.apache.lucene.document.Field#setBoost(float)
 333    */
 334   public void addField(String fieldName, TokenStream stream, float boost) {
 335     try {
 336       if (fieldName == null)
 337         throw new IllegalArgumentException("fieldName must not be null");
 338       if (stream == null)
 339           throw new IllegalArgumentException("token stream must not be null");
 340       if (boost <= 0.0f)
 341           throw new IllegalArgumentException("boost factor must be greater than 0.0");
 342       if (fields.get(fieldName) != null)
 343         throw new IllegalArgumentException("field must not be added more than once");
 344
 345       HashMap<String,ArrayIntList> terms = new HashMap<String,ArrayIntList>();
 346       int numTokens = 0;
 347       int numOverlapTokens = 0;
 348       int pos = -1;
 349
 350       CharTermAttribute termAtt = stream.addAttribute(CharTermAttribute.class);
 351       PositionIncrementAttribute posIncrAttribute = stream.addAttribute(PositionIncrementAttribute.class);
 352       OffsetAttribute offsetAtt = stream.addAttribute(OffsetAttribute.class);
 353       stream.reset();
 354       while (stream.incrementToken()) {
 355         String term = termAtt.toString();
 356         if (term.length() == 0) continue; // nothing to do
 357 //        if (DEBUG) System.err.println("token='" + term + "'");
 358         numTokens++;
 359         final int posIncr = posIncrAttribute.getPositionIncrement();
 360         if (posIncr == 0)
 361           numOverlapTokens++;
 362         pos += posIncr;
 363
 364         ArrayIntList positions = terms.get(term);
 365         if (positions == null) { // term not seen before
 366           positions = new ArrayIntList(stride);
 367           terms.put(term, positions);
 368         }
 369         if (stride == 1) {
 370           positions.add(pos);
 371         } else {
 372           positions.add(pos, offsetAtt.startOffset(), offsetAtt.endOffset());
 373         }
 374       }
 375       stream.end();
 376
 377       // ensure infos.numTokens > 0 invariant; needed for correct operation of terms()
 378       if (numTokens > 0) {
 379         boost = boost * docBoost; // see DocumentWriter.addDocument(...)
 380         fields.put(fieldName, new Info(terms, numTokens, numOverlapTokens, boost));
 381         sortedFields = null;    // invalidate sorted view, if any
 382       }
 383     } catch (IOException e) { // can never happen
 384       throw new RuntimeException(e);
 385     } finally {
 386       try {
 387         if (stream != null) stream.close();
 388       } catch (IOException e2) {
 389         throw new RuntimeException(e2);
 390       }
 391     }
 392   }
 393
 394   /**
 395    * Creates and returns a searcher that can be used to execute arbitrary
 396    * Lucene queries and to collect the resulting query results as hits.
 397    *
 398    * @return a searcher
 399    */
 400   public IndexSearcher createSearcher() {
 401     MemoryIndexReader reader = new MemoryIndexReader();
 402     IndexSearcher searcher = new IndexSearcher(reader); // ensures no auto-close !!
 403     reader.setSearcher(searcher); // to later get hold of searcher.getSimilarity()
 404     return searcher;
 405   }
 406
 407   /**
 408    * Convenience method that efficiently returns the relevance score by
 409    * matching this index against the given Lucene query expression.
 410    *
 411    * @param query
 412    *            an arbitrary Lucene query to run against this index
 413    * @return the relevance score of the matchmaking; A number in the range
 414    *         [0.0 .. 1.0], with 0.0 indicating no match. The higher the number
 415    *         the better the match.
 416    *
 417    */
 418   public float search(Query query) {
 419     if (query == null)
 420       throw new IllegalArgumentException("query must not be null");
 421
 422     Searcher searcher = createSearcher();
 423     try {
 424       final float[] scores = new float[1]; // inits to 0.0f (no match)
 425       searcher.search(query, new Collector() {
 426         private Scorer scorer;
 427
 428         @Override
 429         public void collect(int doc) throws IOException {
 430           scores[0] = scorer.score();
 431         }
 432
 433         @Override
 434         public void setScorer(Scorer scorer) throws IOException {
 435           this.scorer = scorer;
 436         }
 437
 438         @Override
 439         public boolean acceptsDocsOutOfOrder() {
 440           return true;
 441         }
 442
 443         @Override
 444         public void setNextReader(IndexReader reader, int docBase) { }
 445       });
 446       float score = scores[0];
 447       return score;
 448     } catch (IOException e) { // can never happen (RAMDirectory)
 449       throw new RuntimeException(e);
 450     } finally {
 451       // searcher.close();
 452       /*
 453        * Note that it is harmless and important for good performance to
 454        * NOT close the index reader!!! This avoids all sorts of
 455        * unnecessary baggage and locking in the Lucene IndexReader
 456        * superclass, all of which is completely unnecessary for this main
 457        * memory index data structure without thread-safety claims.
 458        *
 459        * Wishing IndexReader would be an interface...
 460        *
 461        * Actually with the new tight createSearcher() API auto-closing is now
 462        * made impossible, hence searcher.close() would be harmless and also
 463        * would not degrade performance...
 464        */
 465     }
 466   }
 467
 468   /**
 469    * Returns a reasonable approximation of the main memory [bytes] consumed by
 470    * this instance. Useful for smart memory sensititive caches/pools. Assumes
 471    * fieldNames are interned, whereas tokenized terms are memory-overlaid.
 472    *
 473    * @return the main memory consumption
 474    */
 475   public int getMemorySize() {
 476     // for example usage in a smart cache see nux.xom.pool.Pool
 477     int PTR = VM.PTR;
 478     int INT = VM.INT;
 479     int size = 0;
 480     size += VM.sizeOfObject(2*PTR + INT); // memory index
 481     if (sortedFields != null) size += VM.sizeOfObjectArray(sortedFields.length);
 482
 483     size += VM.sizeOfHashMap(fields.size());
 484     for (Map.Entry<String, Info> entry : fields.entrySet()) { // for each Field Info
 485       Info info = entry.getValue();
 486       size += VM.sizeOfObject(2*INT + 3*PTR); // Info instance vars
 487       if (info.sortedTerms != null) size += VM.sizeOfObjectArray(info.sortedTerms.length);
 488
 489       int len = info.terms.size();
 490       size += VM.sizeOfHashMap(len);
 491       Iterator<Map.Entry<String,ArrayIntList>> iter2 = info.terms.entrySet().iterator();
 492       while (--len >= 0) { // for each term
 493         Map.Entry<String,ArrayIntList> e = iter2.next();
 494         size += VM.sizeOfObject(PTR + 3*INT); // assumes substring() memory overlay
 495 //        size += STR + 2 * ((String) e.getKey()).length();
 496         ArrayIntList positions = e.getValue();
 497         size += VM.sizeOfArrayIntList(positions.size());
 498       }
 499     }
 500     return size;
 501   }
 502
 503   private int numPositions(ArrayIntList positions) {
 504     return positions.size() / stride;
 505   }
 506
 507   /** sorts into ascending order (on demand), reusing memory along the way */
 508   private void sortFields() {
 509     if (sortedFields == null) sortedFields = sort(fields);
 510   }
 511
 512   /** returns a view of the given map's entries, sorted ascending by key */
 513   private static <K,V> Map.Entry<K,V>[] sort(HashMap<K,V> map) {
 514     int size = map.size();
 515     @SuppressWarnings("unchecked")
 516     Map.Entry<K,V>[] entries = new Map.Entry[size];
 517
 518     Iterator<Map.Entry<K,V>> iter = map.entrySet().iterator();
 519     for (int i=0; i < size; i++) {
 520       entries[i] = iter.next();
 521     }
 522
 523     if (size > 1) ArrayUtil.quickSort(entries, termComparator);
 524     return entries;
 525   }
 526
 527   /**
 528    * Returns a String representation of the index data for debugging purposes.
 529    *
 530    * @return the string representation
 531    */
 532   @Override
 533   public String toString() {
 534     StringBuilder result = new StringBuilder(256);
 535     sortFields();
 536     int sumChars = 0;
 537     int sumPositions = 0;
 538     int sumTerms = 0;
 539
 540     for (int i=0; i < sortedFields.length; i++) {
 541       Map.Entry<String,Info> entry = sortedFields[i];
 542       String fieldName = entry.getKey();
 543       Info info = entry.getValue();
 544       info.sortTerms();
 545       result.append(fieldName + ":\n");
 546
 547       int numChars = 0;
 548       int numPositions = 0;
 549       for (int j=0; j < info.sortedTerms.length; j++) {
 550         Map.Entry<String,ArrayIntList> e = info.sortedTerms[j];
 551         String term = e.getKey();
 552         ArrayIntList positions = e.getValue();
 553         result.append("\t'" + term + "':" + numPositions(positions) + ":");
 554         result.append(positions.toString(stride)); // ignore offsets
 555         result.append("\n");
 556         numPositions += numPositions(positions);
 557         numChars += term.length();
 558       }
 559
 560       result.append("\tterms=" + info.sortedTerms.length);
 561       result.append(", positions=" + numPositions);
 562       result.append(", Kchars=" + (numChars/1000.0f));
 563       result.append("\n");
 564       sumPositions += numPositions;
 565       sumChars += numChars;
 566       sumTerms += info.sortedTerms.length;
 567     }
 568
 569     result.append("\nfields=" + sortedFields.length);
 570     result.append(", terms=" + sumTerms);
 571     result.append(", positions=" + sumPositions);
 572     result.append(", Kchars=" + (sumChars/1000.0f));
 573     return result.toString();
 574   }
 575
 576
 577   ///////////////////////////////////////////////////////////////////////////////
 578   // Nested classes:
 579   ///////////////////////////////////////////////////////////////////////////////
 580   /**
 581    * Index data structure for a field; Contains the tokenized term texts and
 582    * their positions.
 583    */
 584   private static final class Info implements Serializable {
 585
 586     /**
 587      * Term strings and their positions for this field: Map <String
 588      * termText, ArrayIntList positions>
 589      */
 590     private final HashMap<String,ArrayIntList> terms;
 591
 592     /** Terms sorted ascending by term text; computed on demand */
 593     private transient Map.Entry<String,ArrayIntList>[] sortedTerms;
 594
 595     /** Number of added tokens for this field */
 596     private final int numTokens;
 597
 598     /** Number of overlapping tokens for this field */
 599     private final int numOverlapTokens;
 600
 601     /** Boost factor for hits for this field */
 602     private final float boost;
 603
 604     /** Term for this field's fieldName, lazily computed on demand */
 605     public transient Term template;
 606
 607     private static final long serialVersionUID = 2882195016849084649L;
 608
 609     public Info(HashMap<String,ArrayIntList> terms, int numTokens, int numOverlapTokens, float boost) {
 610       this.terms = terms;
 611       this.numTokens = numTokens;
 612       this.numOverlapTokens = numOverlapTokens;
 613       this.boost = boost;
 614     }
 615
 616     /**
 617      * Sorts hashed terms into ascending order, reusing memory along the
 618      * way. Note that sorting is lazily delayed until required (often it's
 619      * not required at all). If a sorted view is required then hashing +
 620      * sort + binary search is still faster and smaller than TreeMap usage
 621      * (which would be an alternative and somewhat more elegant approach,
 622      * apart from more sophisticated Tries / prefix trees).
 623      */
 624     public void sortTerms() {
 625       if (sortedTerms == null) sortedTerms = sort(terms);
 626     }
 627
 628     /** note that the frequency can be calculated as numPosition(getPositions(x)) */
 629     public ArrayIntList getPositions(String term) {
 630       return terms.get(term);
 631     }
 632
 633     /** note that the frequency can be calculated as numPosition(getPositions(x)) */
 634     public ArrayIntList getPositions(int pos) {
 635       return sortedTerms[pos].getValue();
 636     }
 637
 638     public float getBoost() {
 639       return boost;
 640     }
 641
 642   }
 643
 644
 645   ///////////////////////////////////////////////////////////////////////////////
 646   // Nested classes:
 647   ///////////////////////////////////////////////////////////////////////////////
 648   /**
 649    * Efficient resizable auto-expanding list holding <code>int</code> elements;
 650    * implemented with arrays.
 651    */
 652   private static final class ArrayIntList implements Serializable {
 653
 654     private int[] elements;
 655     private int size = 0;
 656
 657     private static final long serialVersionUID = 2282195016849084649L;
 658
 659     public ArrayIntList() {
 660       this(10);
 661     }
 662
 663     public ArrayIntList(int initialCapacity) {
 664       elements = new int[initialCapacity];
 665     }
 666
 667     public void add(int elem) {
 668       if (size == elements.length) ensureCapacity(size + 1);
 669       elements[size++] = elem;
 670     }
 671
 672     public void add(int pos, int start, int end) {
 673       if (size + 3 > elements.length) ensureCapacity(size + 3);
 674       elements[size] = pos;
 675       elements[size+1] = start;
 676       elements[size+2] = end;
 677       size += 3;
 678     }
 679
 680     public int get(int index) {
 681       if (index >= size) throwIndex(index);
 682       return elements[index];
 683     }
 684
 685     public int size() {
 686       return size;
 687     }
 688
 689     public int[] toArray(int stride) {
 690       int[] arr = new int[size() / stride];
 691       if (stride == 1) {
 692         System.arraycopy(elements, 0, arr, 0, size); // fast path
 693       } else {
 694         for (int i=0, j=0; j < size; i++, j += stride) arr[i] = elements[j];
 695       }
 696       return arr;
 697     }
 698
 699     private void ensureCapacity(int minCapacity) {
 700       int newCapacity = Math.max(minCapacity, (elements.length * 3) / 2 + 1);
 701       int[] newElements = new int[newCapacity];
 702       System.arraycopy(elements, 0, newElements, 0, size);
 703       elements = newElements;
 704     }
 705
 706     private void throwIndex(int index) {
 707       throw new IndexOutOfBoundsException("index: " + index
 708             + ", size: " + size);
 709     }
 710
 711     /** returns the first few positions (without offsets); debug only */
 712     public String toString(int stride) {
 713       int s = size() / stride;
 714       int len = Math.min(10, s); // avoid printing huge lists
 715       StringBuilder buf = new StringBuilder(4*len);
 716       buf.append("[");
 717       for (int i = 0; i < len; i++) {
 718         buf.append(get(i*stride));
 719         if (i < len-1) buf.append(", ");
 720       }
 721       if (len != s) buf.append(", ..."); // and some more...
 722       buf.append("]");
 723       return buf.toString();
 724     }
 725   }
 726
 727
 728   ///////////////////////////////////////////////////////////////////////////////
 729   // Nested classes:
 730   ///////////////////////////////////////////////////////////////////////////////
 731   private static final Term MATCH_ALL_TERM = new Term("");
 732
 733   /**
 734    * Search support for Lucene framework integration; implements all methods
 735    * required by the Lucene IndexReader contracts.
 736    */
 737   private final class MemoryIndexReader extends IndexReader {
 738
 739     private Searcher searcher; // needed to find searcher.getSimilarity()
 740
 741     private MemoryIndexReader() {
 742       super(); // avoid as much superclass baggage as possible
 743       readerFinishedListeners = Collections.synchronizedSet(new HashSet<ReaderFinishedListener>());
 744     }
 745
 746     private Info getInfo(String fieldName) {
 747       return fields.get(fieldName);
 748     }
 749
 750     private Info getInfo(int pos) {
 751       return sortedFields[pos].getValue();
 752     }
 753
 754     @Override
 755     public int docFreq(Term term) {
 756       Info info = getInfo(term.field());
 757       int freq = 0;
 758       if (info != null) freq = info.getPositions(term.text()) != null ? 1 : 0;
 759       if (DEBUG) System.err.println("MemoryIndexReader.docFreq: " + term + ", freq:" + freq);
 760       return freq;
 761     }
 762
 763     @Override
 764     public TermEnum terms() {
 765       if (DEBUG) System.err.println("MemoryIndexReader.terms()");
 766       return terms(MATCH_ALL_TERM);
 767     }
 768
 769     @Override
 770     public TermEnum terms(Term term) {
 771       if (DEBUG) System.err.println("MemoryIndexReader.terms: " + term);
 772
 773       int i; // index into info.sortedTerms
 774       int j; // index into sortedFields
 775
 776       sortFields();
 777       if (sortedFields.length == 1 && sortedFields[0].getKey() == term.field()) {
 778         j = 0; // fast path
 779       } else {
 780         j = Arrays.binarySearch(sortedFields, term.field(), termComparator);
 781       }
 782
 783       if (j < 0) { // not found; choose successor
 784         j = -j -1;
 785         i = 0;
 786         if (j < sortedFields.length) getInfo(j).sortTerms();
 787       } else { // found
 788         Info info = getInfo(j);
 789         info.sortTerms();
 790         i = Arrays.binarySearch(info.sortedTerms, term.text(), termComparator);
 791         if (i < 0) { // not found; choose successor
 792           i = -i -1;
 793           if (i >= info.sortedTerms.length) { // move to next successor
 794             j++;
 795             i = 0;
 796             if (j < sortedFields.length) getInfo(j).sortTerms();
 797           }
 798         }
 799       }
 800       final int ix = i;
 801       final int jx = j;
 802
 803       return new TermEnum() {
 804
 805         private int srtTermsIdx = ix; // index into info.sortedTerms
 806         private int srtFldsIdx = jx; // index into sortedFields
 807
 808         @Override
 809         public boolean next() {
 810           if (DEBUG) System.err.println("TermEnum.next");
 811           if (srtFldsIdx >= sortedFields.length) return false;
 812           Info info = getInfo(srtFldsIdx);
 813           if (++srtTermsIdx < info.sortedTerms.length) return true;
 814
 815           // move to successor
 816           srtFldsIdx++;
 817           srtTermsIdx = 0;
 818           if (srtFldsIdx >= sortedFields.length) return false;
 819           getInfo(srtFldsIdx).sortTerms();
 820           return true;
 821         }
 822
 823         @Override
 824         public Term term() {
 825           if (DEBUG) System.err.println("TermEnum.term: " + srtTermsIdx);
 826           if (srtFldsIdx >= sortedFields.length) return null;
 827           Info info = getInfo(srtFldsIdx);
 828           if (srtTermsIdx >= info.sortedTerms.length) return null;
 829 //          if (DEBUG) System.err.println("TermEnum.term: " + i + ", " + info.sortedTerms[i].getKey());
 830           return createTerm(info, srtFldsIdx, info.sortedTerms[srtTermsIdx].getKey());
 831         }
 832
 833         @Override
 834         public int docFreq() {
 835           if (DEBUG) System.err.println("TermEnum.docFreq");
 836           if (srtFldsIdx >= sortedFields.length) return 0;
 837           Info info = getInfo(srtFldsIdx);
 838           if (srtTermsIdx >= info.sortedTerms.length) return 0;
 839           return numPositions(info.getPositions(srtTermsIdx));
 840         }
 841
 842         @Override
 843         public void close() {
 844           if (DEBUG) System.err.println("TermEnum.close");
 845         }
 846
 847         /** Returns a new Term object, minimizing String.intern() overheads. */
 848         private Term createTerm(Info info, int pos, String text) {
 849           // Assertion: sortFields has already been called before
 850           Term template = info.template;
 851           if (template == null) { // not yet cached?
 852             String fieldName = sortedFields[pos].getKey();
 853             template = new Term(fieldName);
 854             info.template = template;
 855           }
 856
 857           return template.createTerm(text);
 858         }
 859
 860       };
 861     }
 862
 863     @Override
 864     public TermPositions termPositions() {
 865       if (DEBUG) System.err.println("MemoryIndexReader.termPositions");
 866
 867       return new TermPositions() {
 868
 869         private boolean hasNext;
 870         private int cursor = 0;
 871         private ArrayIntList current;
 872         private Term term;
 873
 874         public void seek(Term term) {
 875           this.term = term;
 876           if (DEBUG) System.err.println(".seek: " + term);
 877           if (term == null) {
 878             hasNext = true;  // term==null means match all docs
 879           } else {
 880             Info info = getInfo(term.field());
 881             current = info == null ? null : info.getPositions(term.text());
 882             hasNext = (current != null);
 883             cursor = 0;
 884           }
 885         }
 886
 887         public void seek(TermEnum termEnum) {
 888           if (DEBUG) System.err.println(".seekEnum");
 889           seek(termEnum.term());
 890         }
 891
 892         public int doc() {
 893           if (DEBUG) System.err.println(".doc");
 894           return 0;
 895         }
 896
 897         public int freq() {
 898           int freq = current != null ? numPositions(current) : (term == null ? 1 : 0);
 899           if (DEBUG) System.err.println(".freq: " + freq);
 900           return freq;
 901         }
 902
 903         public boolean next() {
 904           if (DEBUG) System.err.println(".next: " + current + ", oldHasNext=" + hasNext);
 905           boolean next = hasNext;
 906           hasNext = false;
 907           return next;
 908         }
 909
 910         public int read(int[] docs, int[] freqs) {
 911           if (DEBUG) System.err.println(".read: " + docs.length);
 912           if (!hasNext) return 0;
 913           hasNext = false;
 914           docs[0] = 0;
 915           freqs[0] = freq();
 916           return 1;
 917         }
 918
 919         public boolean skipTo(int target) {
 920           if (DEBUG) System.err.println(".skipTo: " + target);
 921           return next();
 922         }
 923
 924         public void close() {
 925           if (DEBUG) System.err.println(".close");
 926         }
 927
 928         public int nextPosition() { // implements TermPositions
 929           int pos = current.get(cursor);
 930           cursor += stride;
 931           if (DEBUG) System.err.println(".nextPosition: " + pos);
 932           return pos;
 933         }
 934
 935         /**
 936          * Not implemented.
 937          * @throws UnsupportedOperationException
 938          */
 939         public int getPayloadLength() {
 940           throw new UnsupportedOperationException();
 941         }
 942
 943         /**
 944          * Not implemented.
 945          * @throws UnsupportedOperationException
 946          */
 947         public byte[] getPayload(byte[] data, int offset) throws IOException {
 948           throw new UnsupportedOperationException();
 949         }
 950
 951         public boolean isPayloadAvailable() {
 952           // unsuported
 953           return false;
 954         }
 955
 956       };
 957     }
 958
 959     @Override
 960     public TermDocs termDocs() {
 961       if (DEBUG) System.err.println("MemoryIndexReader.termDocs");
 962       return termPositions();
 963     }
 964
 965     @Override
 966     public TermFreqVector[] getTermFreqVectors(int docNumber) {
 967       if (DEBUG) System.err.println("MemoryIndexReader.getTermFreqVectors");
 968       TermFreqVector[] vectors = new TermFreqVector[fields.size()];
 969 //      if (vectors.length == 0) return null;
 970       Iterator<String> iter = fields.keySet().iterator();
 971       for (int i=0; i < vectors.length; i++) {
 972         vectors[i] = getTermFreqVector(docNumber, iter.next());
 973       }
 974       return vectors;
 975     }
 976
 977       @Override
 978       public void getTermFreqVector(int docNumber, TermVectorMapper mapper) throws IOException
 979       {
 980           if (DEBUG) System.err.println("MemoryIndexReader.getTermFreqVectors");
 981
 982     //      if (vectors.length == 0) return null;
 983           for (final String fieldName : fields.keySet())
 984           {
 985             getTermFreqVector(docNumber, fieldName, mapper);
 986           }
 987       }
 988
 989       @Override
 990       public void getTermFreqVector(int docNumber, String field, TermVectorMapper mapper) throws IOException
 991       {
 992         if (DEBUG) System.err.println("MemoryIndexReader.getTermFreqVector");
 993         final Info info = getInfo(field);
 994           if (info == null){
 995               return;
 996           }
 997           info.sortTerms();
 998           mapper.setExpectations(field, info.sortedTerms.length, stride != 1, true);
 999           for (int i = info.sortedTerms.length; --i >=0;){
1000
1001               ArrayIntList positions = info.sortedTerms[i].getValue();
1002               int size = positions.size();
1003               org.apache.lucene.index.TermVectorOffsetInfo[] offsets =
1004                 new org.apache.lucene.index.TermVectorOffsetInfo[size / stride];
1005
1006               for (int k=0, j=1; j < size; k++, j += stride) {
1007                 int start = positions.get(j);
1008                 int end = positions.get(j+1);
1009                 offsets[k] = new org.apache.lucene.index.TermVectorOffsetInfo(start, end);
1010               }
1011               mapper.map(info.sortedTerms[i].getKey(),
1012                          numPositions(info.sortedTerms[i].getValue()),
1013                          offsets, (info.sortedTerms[i].getValue()).toArray(stride));
1014           }
1015       }
1016
1017       @Override
1018       public TermFreqVector getTermFreqVector(int docNumber, final String fieldName) {
1019       if (DEBUG) System.err.println("MemoryIndexReader.getTermFreqVector");
1020       final Info info = getInfo(fieldName);
1021       if (info == null) return null; // TODO: or return empty vector impl???
1022       info.sortTerms();
1023
1024       return new TermPositionVector() {
1025
1026         private final Map.Entry<String,ArrayIntList>[] sortedTerms = info.sortedTerms;
1027
1028         public String getField() {
1029           return fieldName;
1030         }
1031
1032         public int size() {
1033           return sortedTerms.length;
1034         }
1035
1036         public String[] getTerms() {
1037           String[] terms = new String[sortedTerms.length];
1038           for (int i=sortedTerms.length; --i >= 0; ) {
1039             terms[i] = sortedTerms[i].getKey();
1040           }
1041           return terms;
1042         }
1043
1044         public int[] getTermFrequencies() {
1045           int[] freqs = new int[sortedTerms.length];
1046           for (int i=sortedTerms.length; --i >= 0; ) {
1047             freqs[i] = numPositions(sortedTerms[i].getValue());
1048           }
1049           return freqs;
1050         }
1051
1052         public int indexOf(String term) {
1053           int i = Arrays.binarySearch(sortedTerms, term, termComparator);
1054           return i >= 0 ? i : -1;
1055         }
1056
1057         public int[] indexesOf(String[] terms, int start, int len) {
1058           int[] indexes = new int[len];
1059           for (int i=0; i < len; i++) {
1060             indexes[i] = indexOf(terms[start++]);
1061           }
1062           return indexes;
1063         }
1064
1065         // lucene >= 1.4.3
1066         public int[] getTermPositions(int index) {
1067           return sortedTerms[index].getValue().toArray(stride);
1068         }
1069
1070         // lucene >= 1.9 (remove this method for lucene-1.4.3)
1071         public org.apache.lucene.index.TermVectorOffsetInfo[] getOffsets(int index) {
1072           if (stride == 1) return null; // no offsets stored
1073
1074           ArrayIntList positions = sortedTerms[index].getValue();
1075           int size = positions.size();
1076           org.apache.lucene.index.TermVectorOffsetInfo[] offsets =
1077             new org.apache.lucene.index.TermVectorOffsetInfo[size / stride];
1078
1079           for (int i=0, j=1; j < size; i++, j += stride) {
1080             int start = positions.get(j);
1081             int end = positions.get(j+1);
1082             offsets[i] = new org.apache.lucene.index.TermVectorOffsetInfo(start, end);
1083           }
1084           return offsets;
1085         }
1086
1087       };
1088     }
1089
1090     private Similarity getSimilarity() {
1091       if (searcher != null) return searcher.getSimilarity();
1092       return Similarity.getDefault();
1093     }
1094
1095     private void setSearcher(Searcher searcher) {
1096       this.searcher = searcher;
1097     }
1098
1099     /** performance hack: cache norms to avoid repeated expensive calculations */
1100     private byte[] cachedNorms;
1101     private String cachedFieldName;
1102     private Similarity cachedSimilarity;
1103
1104     @Override
1105     public byte[] norms(String fieldName) {
1106       byte[] norms = cachedNorms;
1107       Similarity sim = getSimilarity();
1108       if (fieldName != cachedFieldName || sim != cachedSimilarity) { // not cached?
1109         Info info = getInfo(fieldName);
1110         int numTokens = info != null ? info.numTokens : 0;
1111         int numOverlapTokens = info != null ? info.numOverlapTokens : 0;
1112         float boost = info != null ? info.getBoost() : 1.0f;
1113         FieldInvertState invertState = new FieldInvertState(0, numTokens, numOverlapTokens, 0, boost);
1114         float n = sim.computeNorm(fieldName, invertState);
1115         byte norm = sim.encodeNormValue(n);
1116         norms = new byte[] {norm};
1117
1118         // cache it for future reuse
1119         cachedNorms = norms;
1120         cachedFieldName = fieldName;
1121         cachedSimilarity = sim;
1122         if (DEBUG) System.err.println("MemoryIndexReader.norms: " + fieldName + ":" + n + ":" + norm + ":" + numTokens);
1123       }
1124       return norms;
1125     }
1126
1127     @Override
1128     public void norms(String fieldName, byte[] bytes, int offset) {
1129       if (DEBUG) System.err.println("MemoryIndexReader.norms*: " + fieldName);
1130       byte[] norms = norms(fieldName);
1131       System.arraycopy(norms, 0, bytes, offset, norms.length);
1132     }
1133
1134     @Override
1135     protected void doSetNorm(int doc, String fieldName, byte value) {
1136       throw new UnsupportedOperationException();
1137     }
1138
1139     @Override
1140     public int numDocs() {
1141       if (DEBUG) System.err.println("MemoryIndexReader.numDocs");
1142       return fields.size() > 0 ? 1 : 0;
1143     }
1144
1145     @Override
1146     public int maxDoc() {
1147       if (DEBUG) System.err.println("MemoryIndexReader.maxDoc");
1148       return 1;
1149     }
1150
1151     @Override
1152     public Document document(int n) {
1153       if (DEBUG) System.err.println("MemoryIndexReader.document");
1154       return new Document(); // there are no stored fields
1155     }
1156
1157     //When we convert to JDK 1.5 make this Set<String>
1158     @Override
1159     public Document document(int n, FieldSelector fieldSelector) throws IOException {
1160       if (DEBUG) System.err.println("MemoryIndexReader.document");
1161       return new Document(); // there are no stored fields
1162     }
1163
1164     @Override
1165     public boolean isDeleted(int n) {
1166       if (DEBUG) System.err.println("MemoryIndexReader.isDeleted");
1167       return false;
1168     }
1169
1170     @Override
1171     public boolean hasDeletions() {
1172       if (DEBUG) System.err.println("MemoryIndexReader.hasDeletions");
1173       return false;
1174     }
1175
1176     @Override
1177     protected void doDelete(int docNum) {
1178       throw new UnsupportedOperationException();
1179     }
1180
1181     @Override
1182     protected void doUndeleteAll() {
1183       throw new UnsupportedOperationException();
1184     }
1185
1186     @Override
1187     protected void doCommit(Map<String,String> commitUserData) {
1188       if (DEBUG) System.err.println("MemoryIndexReader.doCommit");
1189     }
1190
1191     @Override
1192     protected void doClose() {
1193       if (DEBUG) System.err.println("MemoryIndexReader.doClose");
1194     }
1195
1196     // lucene >= 1.9 (remove this method for lucene-1.4.3)
1197     @Override
1198     public Collection<String> getFieldNames(FieldOption fieldOption) {
1199       if (DEBUG) System.err.println("MemoryIndexReader.getFieldNamesOption");
1200       if (fieldOption == FieldOption.UNINDEXED)
1201         return Collections.<String>emptySet();
1202       if (fieldOption == FieldOption.INDEXED_NO_TERMVECTOR)
1203         return Collections.<String>emptySet();
1204       if (fieldOption == FieldOption.TERMVECTOR_WITH_OFFSET && stride == 1)
1205         return Collections.<String>emptySet();
1206       if (fieldOption == FieldOption.TERMVECTOR_WITH_POSITION_OFFSET && stride == 1)
1207         return Collections.<String>emptySet();
1208
1209       return Collections.unmodifiableSet(fields.keySet());
1210     }
1211   }
1212
1213
1214   ///////////////////////////////////////////////////////////////////////////////
1215   // Nested classes:
1216   ///////////////////////////////////////////////////////////////////////////////
1217   private static final class VM {
1218
1219     public static final int PTR = Constants.JRE_IS_64BIT ? 8 : 4;
1220
1221     // bytes occupied by primitive data types
1222     public static final int BOOLEAN = 1;
1223     public static final int BYTE = 1;
1224     public static final int CHAR = 2;
1225     public static final int SHORT = 2;
1226     public static final int INT = 4;
1227     public static final int LONG = 8;
1228     public static final int FLOAT = 4;
1229     public static final int DOUBLE = 8;
1230
1231     private static final int LOG_PTR = (int) Math.round(log2(PTR));
1232
1233     /**
1234      * Object header of any heap allocated Java object.
1235      * ptr to class, info for monitor, gc, hash, etc.
1236      */
1237     private static final int OBJECT_HEADER = 2*PTR;
1238
1239     private VM() {} // not instantiable
1240
1241     //  assumes n > 0
1242     //  64 bit VM:
1243     //    0     --> 0*PTR
1244     //    1..8  --> 1*PTR
1245     //    9..16 --> 2*PTR
1246     private static int sizeOf(int n) {
1247         return (((n-1) >> LOG_PTR) + 1) << LOG_PTR;
1248     }
1249
1250     public static int sizeOfObject(int n) {
1251         return sizeOf(OBJECT_HEADER + n);
1252     }
1253
1254     public static int sizeOfObjectArray(int len) {
1255         return sizeOfObject(INT + PTR*len);
1256     }
1257
1258     public static int sizeOfCharArray(int len) {
1259         return sizeOfObject(INT + CHAR*len);
1260     }
1261
1262     public static int sizeOfIntArray(int len) {
1263         return sizeOfObject(INT + INT*len);
1264     }
1265
1266     public static int sizeOfString(int len) {
1267         return sizeOfObject(3*INT + PTR) + sizeOfCharArray(len);
1268     }
1269
1270     public static int sizeOfHashMap(int len) {
1271         return sizeOfObject(4*PTR + 4*INT) + sizeOfObjectArray(len)
1272             + len * sizeOfObject(3*PTR + INT); // entries
1273     }
1274
1275     // note: does not include referenced objects
1276     public static int sizeOfArrayList(int len) {
1277         return sizeOfObject(PTR + 2*INT) + sizeOfObjectArray(len);
1278     }
1279
1280     public static int sizeOfArrayIntList(int len) {
1281         return sizeOfObject(PTR + INT) + sizeOfIntArray(len);
1282     }
1283
1284     /** logarithm to the base 2. Example: log2(4) == 2, log2(8) == 3 */
1285     private static double log2(double value) {
1286       return Math.log(value) / Math.log(2);
1287     }
1288
1289   }
1290
1291 }