lucene-java-3.4.0/lucene/src/java/org/apache/lucene/analysis/CharArrayMap.java

   1 package org.apache.lucene.analysis;
   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.util.Arrays;
  21 import java.util.AbstractMap;
  22 import java.util.AbstractSet;
  23 import java.util.Iterator;
  24 import java.util.Map;
  25 import java.util.Set;
  26
  27 import org.apache.lucene.util.CharacterUtils;
  28 import org.apache.lucene.util.Version;
  29
  30 /**
  31  * A simple class that stores key Strings as char[]'s in a
  32  * hash table. Note that this is not a general purpose
  33  * class.  For example, it cannot remove items from the
  34  * map, nor does it resize its hash table to be smaller,
  35  * etc.  It is designed to be quick to retrieve items
  36  * by char[] keys without the necessity of converting
  37  * to a String first.
  38  * <p>You must specify the required {@link Version}
  39  * compatibility when creating {@link CharArrayMap}:
  40  * <ul>
  41  *   <li> As of 3.1, supplementary characters are
  42  *       properly lowercased.</li>
  43  * </ul>
  44  * Before 3.1 supplementary characters could not be
  45  * lowercased correctly due to the lack of Unicode 4
  46  * support in JDK 1.4. To use instances of
  47  * {@link CharArrayMap} with the behavior before Lucene
  48  * 3.1 pass a {@link Version} &lt; 3.1 to the constructors.
  49  */
  50 public class CharArrayMap<V> extends AbstractMap<Object,V> {
  51   // private only because missing generics
  52   private static final CharArrayMap<?> EMPTY_MAP = new EmptyCharArrayMap<Object>();
  53
  54   private final static int INIT_SIZE = 8;
  55   private final CharacterUtils charUtils;
  56   private boolean ignoreCase;
  57   private int count;
  58   final Version matchVersion; // package private because used in CharArraySet
  59   char[][] keys; // package private because used in CharArraySet's non Set-conform CharArraySetIterator
  60   V[] values; // package private because used in CharArraySet's non Set-conform CharArraySetIterator
  61
  62   /**
  63    * Create map with enough capacity to hold startSize terms
  64    *
  65    * @param matchVersion
  66    *          compatibility match version see <a href="#version">Version
  67    *          note</a> above for details.
  68    * @param startSize
  69    *          the initial capacity
  70    * @param ignoreCase
  71    *          <code>false</code> if and only if the set should be case sensitive
  72    *          otherwise <code>true</code>.
  73    */
  74   @SuppressWarnings("unchecked")
  75   public CharArrayMap(Version matchVersion, int startSize, boolean ignoreCase) {
  76     this.ignoreCase = ignoreCase;
  77     int size = INIT_SIZE;
  78     while(startSize + (startSize>>2) > size)
  79       size <<= 1;
  80     keys = new char[size][];
  81     values = (V[]) new Object[size];
  82     this.charUtils = CharacterUtils.getInstance(matchVersion);
  83     this.matchVersion = matchVersion;
  84   }
  85
  86   /**
  87    * Creates a map from the mappings in another map.
  88    *
  89    * @param matchVersion
  90    *          compatibility match version see <a href="#version">Version
  91    *          note</a> above for details.
  92    * @param c
  93    *          a map whose mappings to be copied
  94    * @param ignoreCase
  95    *          <code>false</code> if and only if the set should be case sensitive
  96    *          otherwise <code>true</code>.
  97    */
  98   public CharArrayMap(Version matchVersion, Map<?,? extends V> c, boolean ignoreCase) {
  99     this(matchVersion, c.size(), ignoreCase);
 100     putAll(c);
 101   }
 102
 103   /** Create set from the supplied map (used internally for readonly maps...) */
 104   private CharArrayMap(CharArrayMap<V> toCopy){
 105     this.keys = toCopy.keys;
 106     this.values = toCopy.values;
 107     this.ignoreCase = toCopy.ignoreCase;
 108     this.count = toCopy.count;
 109     this.charUtils = toCopy.charUtils;
 110     this.matchVersion = toCopy.matchVersion;
 111   }
 112
 113   /** Clears all entries in this map. This method is supported for reusing, but not {@link Map#remove}. */
 114   @Override
 115   public void clear() {
 116     count = 0;
 117     Arrays.fill(keys, null);
 118     Arrays.fill(values, null);
 119   }
 120
 121   /** true if the <code>len</code> chars of <code>text</code> starting at <code>off</code>
 122    * are in the {@link #keySet} */
 123   public boolean containsKey(char[] text, int off, int len) {
 124     return keys[getSlot(text, off, len)] != null;
 125   }
 126
 127   /** true if the <code>CharSequence</code> is in the {@link #keySet} */
 128   public boolean containsKey(CharSequence cs) {
 129     return keys[getSlot(cs)] != null;
 130   }
 131
 132   @Override
 133   public boolean containsKey(Object o) {
 134     if (o instanceof char[]) {
 135       final char[] text = (char[])o;
 136       return containsKey(text, 0, text.length);
 137     }
 138     return containsKey(o.toString());
 139   }
 140
 141   /** returns the value of the mapping of <code>len</code> chars of <code>text</code>
 142    * starting at <code>off</code> */
 143   public V get(char[] text, int off, int len) {
 144     return values[getSlot(text, off, len)];
 145   }
 146
 147   /** returns the value of the mapping of the chars inside this {@code CharSequence} */
 148   public V get(CharSequence cs) {
 149     return values[getSlot(cs)];
 150   }
 151
 152   @Override
 153   public V get(Object o) {
 154     if (o instanceof char[]) {
 155       final char[] text = (char[])o;
 156       return get(text, 0, text.length);
 157     }
 158     return get(o.toString());
 159   }
 160
 161   private int getSlot(char[] text, int off, int len) {
 162     int code = getHashCode(text, off, len);
 163     int pos = code & (keys.length-1);
 164     char[] text2 = keys[pos];
 165     if (text2 != null && !equals(text, off, len, text2)) {
 166       final int inc = ((code>>8)+code)|1;
 167       do {
 168         code += inc;
 169         pos = code & (keys.length-1);
 170         text2 = keys[pos];
 171       } while (text2 != null && !equals(text, off, len, text2));
 172     }
 173     return pos;
 174   }
 175
 176   /** Returns true if the String is in the set */
 177   private int getSlot(CharSequence text) {
 178     int code = getHashCode(text);
 179     int pos = code & (keys.length-1);
 180     char[] text2 = keys[pos];
 181     if (text2 != null && !equals(text, text2)) {
 182       final int inc = ((code>>8)+code)|1;
 183       do {
 184         code += inc;
 185         pos = code & (keys.length-1);
 186         text2 = keys[pos];
 187       } while (text2 != null && !equals(text, text2));
 188     }
 189     return pos;
 190   }
 191
 192   /** Add the given mapping. */
 193   public V put(CharSequence text, V value) {
 194     return put(text.toString(), value); // could be more efficient
 195   }
 196
 197   @Override
 198   public V put(Object o, V value) {
 199     if (o instanceof char[]) {
 200       return put((char[])o, value);
 201     }
 202     return put(o.toString(), value);
 203   }
 204
 205   /** Add the given mapping. */
 206   public V put(String text, V value) {
 207     return put(text.toCharArray(), value);
 208   }
 209
 210   /** Add the given mapping.
 211    * If ignoreCase is true for this Set, the text array will be directly modified.
 212    * The user should never modify this text array after calling this method.
 213    */
 214   public V put(char[] text, V value) {
 215     if (ignoreCase)
 216       for(int i=0;i<text.length;){
 217         i += Character.toChars(
 218               Character.toLowerCase(
 219                   charUtils.codePointAt(text, i)), text, i);
 220       }
 221     int slot = getSlot(text, 0, text.length);
 222     if (keys[slot] != null) {
 223       final V oldValue = values[slot];
 224       values[slot] = value;
 225       return oldValue;
 226     }
 227     keys[slot] = text;
 228     values[slot] = value;
 229     count++;
 230
 231     if (count + (count>>2) > keys.length) {
 232       rehash();
 233     }
 234
 235     return null;
 236   }
 237
 238   @SuppressWarnings("unchecked")
 239   private void rehash() {
 240     assert keys.length == values.length;
 241     final int newSize = 2*keys.length;
 242     final char[][] oldkeys = keys;
 243     final V[] oldvalues = values;
 244     keys = new char[newSize][];
 245     values = (V[]) new Object[newSize];
 246
 247     for(int i=0; i<oldkeys.length; i++) {
 248       char[] text = oldkeys[i];
 249       if (text != null) {
 250         // todo: could be faster... no need to compare strings on collision
 251         final int slot = getSlot(text,0,text.length);
 252         keys[slot] = text;
 253         values[slot] = oldvalues[i];
 254       }
 255     }
 256   }
 257
 258   private boolean equals(char[] text1, int off, int len, char[] text2) {
 259     if (len != text2.length)
 260       return false;
 261     final int limit = off+len;
 262     if (ignoreCase) {
 263       for(int i=0;i<len;) {
 264         final int codePointAt = charUtils.codePointAt(text1, off+i, limit);
 265         if (Character.toLowerCase(codePointAt) != charUtils.codePointAt(text2, i))
 266           return false;
 267         i += Character.charCount(codePointAt);
 268       }
 269     } else {
 270       for(int i=0;i<len;i++) {
 271         if (text1[off+i] != text2[i])
 272           return false;
 273       }
 274     }
 275     return true;
 276   }
 277
 278   private boolean equals(CharSequence text1, char[] text2) {
 279     int len = text1.length();
 280     if (len != text2.length)
 281       return false;
 282     if (ignoreCase) {
 283       for(int i=0;i<len;) {
 284         final int codePointAt = charUtils.codePointAt(text1, i);
 285         if (Character.toLowerCase(codePointAt) != charUtils.codePointAt(text2, i))
 286           return false;
 287         i += Character.charCount(codePointAt);
 288       }
 289     } else {
 290       for(int i=0;i<len;i++) {
 291         if (text1.charAt(i) != text2[i])
 292           return false;
 293       }
 294     }
 295     return true;
 296   }
 297
 298   private int getHashCode(char[] text, int offset, int len) {
 299     if (text == null)
 300       throw new NullPointerException();
 301     int code = 0;
 302     final int stop = offset + len;
 303     if (ignoreCase) {
 304       for (int i=offset; i<stop;) {
 305         final int codePointAt = charUtils.codePointAt(text, i, stop);
 306         code = code*31 + Character.toLowerCase(codePointAt);
 307         i += Character.charCount(codePointAt);
 308       }
 309     } else {
 310       for (int i=offset; i<stop; i++) {
 311         code = code*31 + text[i];
 312       }
 313     }
 314     return code;
 315   }
 316
 317   private int getHashCode(CharSequence text) {
 318     if (text == null)
 319       throw new NullPointerException();
 320     int code = 0;
 321     int len = text.length();
 322     if (ignoreCase) {
 323       for (int i=0; i<len;) {
 324         int codePointAt = charUtils.codePointAt(text, i);
 325         code = code*31 + Character.toLowerCase(codePointAt);
 326         i += Character.charCount(codePointAt);
 327       }
 328     } else {
 329       for (int i=0; i<len; i++) {
 330         code = code*31 + text.charAt(i);
 331       }
 332     }
 333     return code;
 334   }
 335
 336   @Override
 337   public V remove(Object key) {
 338     throw new UnsupportedOperationException();
 339   }
 340
 341   @Override
 342   public int size() {
 343     return count;
 344   }
 345
 346   @Override
 347   public String toString() {
 348     final StringBuilder sb = new StringBuilder("{");
 349     for (Map.Entry<Object,V> entry : entrySet()) {
 350       if (sb.length()>1) sb.append(", ");
 351       sb.append(entry);
 352     }
 353     return sb.append('}').toString();
 354   }
 355
 356   private EntrySet entrySet = null;
 357   private CharArraySet keySet = null;
 358
 359   EntrySet createEntrySet() {
 360     return new EntrySet(true);
 361   }
 362
 363   @Override
 364   public final EntrySet entrySet() {
 365     if (entrySet == null) {
 366       entrySet = createEntrySet();
 367     }
 368     return entrySet;
 369   }
 370
 371   // helper for CharArraySet to not produce endless recursion
 372   final Set<Object> originalKeySet() {
 373     return super.keySet();
 374   }
 375
 376   /** Returns an {@link CharArraySet} view on the map's keys.
 377    * The set will use the same {@code matchVersion} as this map. */
 378   @Override @SuppressWarnings("unchecked")
 379   public final CharArraySet keySet() {
 380     if (keySet == null) {
 381       // prevent adding of entries
 382       keySet = new CharArraySet((CharArrayMap) this) {
 383         @Override
 384         public boolean add(Object o) {
 385           throw new UnsupportedOperationException();
 386         }
 387         @Override
 388         public boolean add(CharSequence text) {
 389           throw new UnsupportedOperationException();
 390         }
 391         @Override
 392         public boolean add(String text) {
 393           throw new UnsupportedOperationException();
 394         }
 395         @Override
 396         public boolean add(char[] text) {
 397           throw new UnsupportedOperationException();
 398         }
 399       };
 400     }
 401     return keySet;
 402   }
 403
 404   /** public iterator class so efficient methods are exposed to users */
 405   public class EntryIterator implements Iterator<Map.Entry<Object,V>> {
 406     private int pos=-1;
 407     private int lastPos;
 408     private final boolean allowModify;
 409
 410     private EntryIterator(boolean allowModify) {
 411       this.allowModify = allowModify;
 412       goNext();
 413     }
 414
 415     private void goNext() {
 416       lastPos = pos;
 417       pos++;
 418       while (pos < keys.length && keys[pos] == null) pos++;
 419     }
 420
 421     public boolean hasNext() {
 422       return pos < keys.length;
 423     }
 424
 425     /** gets the next key... do not modify the returned char[] */
 426     public char[] nextKey() {
 427       goNext();
 428       return keys[lastPos];
 429     }
 430
 431     /** gets the next key as a newly created String object */
 432     public String nextKeyString() {
 433       return new String(nextKey());
 434     }
 435
 436     /** returns the value associated with the last key returned */
 437     public V currentValue() {
 438       return values[lastPos];
 439     }
 440
 441     /** sets the value associated with the last key returned */
 442     public V setValue(V value) {
 443       if (!allowModify)
 444         throw new UnsupportedOperationException();
 445       V old = values[lastPos];
 446       values[lastPos] = value;
 447       return old;
 448     }
 449
 450     /** use nextCharArray() + currentValue() for better efficiency. */
 451     public Map.Entry<Object,V> next() {
 452       goNext();
 453       return new MapEntry(lastPos, allowModify);
 454     }
 455
 456     public void remove() {
 457       throw new UnsupportedOperationException();
 458     }
 459   }
 460
 461   private final class MapEntry implements Map.Entry<Object,V> {
 462     private final int pos;
 463     private final boolean allowModify;
 464
 465     private MapEntry(int pos, boolean allowModify) {
 466       this.pos = pos;
 467       this.allowModify = allowModify;
 468     }
 469
 470     public Object getKey() {
 471       // we must clone here, as putAll to another CharArrayMap
 472       // with other case sensitivity flag would corrupt the keys
 473       return keys[pos].clone();
 474     }
 475
 476     public V getValue() {
 477       return values[pos];
 478     }
 479
 480     public V setValue(V value) {
 481       if (!allowModify)
 482         throw new UnsupportedOperationException();
 483       final V old = values[pos];
 484       values[pos] = value;
 485       return old;
 486     }
 487
 488     @Override
 489     public String toString() {
 490       return new StringBuilder().append(keys[pos]).append('=')
 491         .append((values[pos] == CharArrayMap.this) ? "(this Map)" : values[pos])
 492         .toString();
 493     }
 494   }
 495
 496   /** public EntrySet class so efficient methods are exposed to users */
 497   public final class EntrySet extends AbstractSet<Map.Entry<Object,V>> {
 498     private final boolean allowModify;
 499
 500     private EntrySet(boolean allowModify) {
 501       this.allowModify = allowModify;
 502     }
 503
 504     @Override
 505     public EntryIterator iterator() {
 506       return new EntryIterator(allowModify);
 507     }
 508
 509     @Override
 510     public boolean contains(Object o) {
 511       if (!(o instanceof Map.Entry))
 512         return false;
 513       final Map.Entry e = (Map.Entry)o;
 514       final Object key = e.getKey();
 515       final Object val = e.getValue();
 516       final Object v = get(key);
 517       return v == null ? val == null : v.equals(val);
 518     }
 519
 520     @Override
 521     public boolean remove(Object o) {
 522       throw new UnsupportedOperationException();
 523     }
 524
 525     @Override
 526     public int size() {
 527       return count;
 528     }
 529
 530     @Override
 531     public void clear() {
 532       if (!allowModify)
 533         throw new UnsupportedOperationException();
 534       CharArrayMap.this.clear();
 535     }
 536   }
 537
 538   /**
 539    * Returns an unmodifiable {@link CharArrayMap}. This allows to provide
 540    * unmodifiable views of internal map for "read-only" use.
 541    *
 542    * @param map
 543    *          a map for which the unmodifiable map is returned.
 544    * @return an new unmodifiable {@link CharArrayMap}.
 545    * @throws NullPointerException
 546    *           if the given map is <code>null</code>.
 547    */
 548   public static <V> CharArrayMap<V> unmodifiableMap(CharArrayMap<V> map) {
 549     if (map == null)
 550       throw new NullPointerException("Given map is null");
 551     if (map == emptyMap() || map.isEmpty())
 552       return emptyMap();
 553     if (map instanceof UnmodifiableCharArrayMap)
 554       return map;
 555     return new UnmodifiableCharArrayMap<V>(map);
 556   }
 557
 558   /**
 559    * Returns a copy of the given map as a {@link CharArrayMap}. If the given map
 560    * is a {@link CharArrayMap} the ignoreCase property will be preserved.
 561    * <p>
 562    * <b>Note:</b> If you intend to create a copy of another {@link CharArrayMap} where
 563    * the {@link Version} of the source map differs from its copy
 564    * {@link #CharArrayMap(Version, Map, boolean)} should be used instead.
 565    * The {@link #copy(Version, Map)} will preserve the {@link Version} of the
 566    * source map it is an instance of {@link CharArrayMap}.
 567    * </p>
 568    *
 569    * @param matchVersion
 570    *          compatibility match version see <a href="#version">Version
 571    *          note</a> above for details. This argument will be ignored if the
 572    *          given map is a {@link CharArrayMap}.
 573    * @param map
 574    *          a map to copy
 575    * @return a copy of the given map as a {@link CharArrayMap}. If the given map
 576    *         is a {@link CharArrayMap} the ignoreCase property as well as the
 577    *         matchVersion will be of the given map will be preserved.
 578    */
 579   @SuppressWarnings("unchecked")
 580   public static <V> CharArrayMap<V> copy(final Version matchVersion, final Map<?,? extends V> map) {
 581     if(map == EMPTY_MAP)
 582       return emptyMap();
 583     if(map instanceof CharArrayMap) {
 584       CharArrayMap<V> m = (CharArrayMap<V>) map;
 585       // use fast path instead of iterating all values
 586       // this is even on very small sets ~10 times faster than iterating
 587       final char[][] keys = new char[m.keys.length][];
 588       System.arraycopy(m.keys, 0, keys, 0, keys.length);
 589       final V[] values = (V[]) new Object[m.values.length];
 590       System.arraycopy(m.values, 0, values, 0, values.length);
 591       m = new CharArrayMap<V>(m);
 592       m.keys = keys;
 593       m.values = values;
 594       return m;
 595     }
 596     return new CharArrayMap<V>(matchVersion, map, false);
 597   }
 598
 599   /** Returns an empty, unmodifiable map. */
 600   @SuppressWarnings("unchecked")
 601   public static <V> CharArrayMap<V> emptyMap() {
 602     return (CharArrayMap<V>) EMPTY_MAP;
 603   }
 604
 605   // package private CharArraySet instanceof check in CharArraySet
 606   static class UnmodifiableCharArrayMap<V> extends CharArrayMap<V> {
 607
 608     UnmodifiableCharArrayMap(CharArrayMap<V> map) {
 609       super(map);
 610     }
 611
 612     @Override
 613     public void clear() {
 614       throw new UnsupportedOperationException();
 615     }
 616
 617     @Override
 618     public V put(Object o, V val){
 619       throw new UnsupportedOperationException();
 620     }
 621
 622     @Override
 623     public V put(char[] text, V val) {
 624       throw new UnsupportedOperationException();
 625     }
 626
 627     @Override
 628     public V put(CharSequence text, V val) {
 629       throw new UnsupportedOperationException();
 630     }
 631
 632     @Override
 633     public V put(String text, V val) {
 634       throw new UnsupportedOperationException();
 635     }
 636
 637     @Override
 638     public V remove(Object key) {
 639       throw new UnsupportedOperationException();
 640     }
 641
 642     @Override
 643     EntrySet createEntrySet() {
 644       return new EntrySet(false);
 645     }
 646   }
 647
 648   /**
 649    * Empty {@link UnmodifiableCharArrayMap} optimized for speed.
 650    * Contains checks will always return <code>false</code> or throw
 651    * NPE if necessary.
 652    */
 653   private static final class EmptyCharArrayMap<V> extends UnmodifiableCharArrayMap<V> {
 654     EmptyCharArrayMap() {
 655       super(new CharArrayMap<V>(Version.LUCENE_CURRENT, 0, false));
 656     }
 657
 658     @Override
 659     public boolean containsKey(char[] text, int off, int len) {
 660       if(text == null)
 661         throw new NullPointerException();
 662       return false;
 663     }
 664
 665     @Override
 666     public boolean containsKey(CharSequence cs) {
 667       if(cs == null)
 668         throw new NullPointerException();
 669       return false;
 670     }
 671
 672     @Override
 673     public boolean containsKey(Object o) {
 674       if(o == null)
 675         throw new NullPointerException();
 676       return false;
 677     }
 678
 679     @Override
 680     public V get(char[] text, int off, int len) {
 681       if(text == null)
 682         throw new NullPointerException();
 683       return null;
 684     }
 685
 686     @Override
 687     public V get(CharSequence cs) {
 688       if(cs == null)
 689         throw new NullPointerException();
 690       return null;
 691     }
 692
 693     @Override
 694     public V get(Object o) {
 695       if(o == null)
 696         throw new NullPointerException();
 697       return null;
 698     }
 699   }
 700 }