bundles/org.simantics.scenegraph/src/gnu/trove/TIntObjectHashMap.java

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
   3 //
   4 // This library is free software; you can redistribute it and/or
   5 // modify it under the terms of the GNU Lesser General Public
   6 // License as published by the Free Software Foundation; either
   7 // version 2.1 of the License, or (at your option) any later version.
   8 //
   9 // This library is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Lesser General Public
  15 // License along with this program; if not, write to the Free Software
  16 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  17 ///////////////////////////////////////////////////////////////////////////////
  18
  19 package gnu.trove;
  20
  21 import java.io.IOException;
  22 import java.io.ObjectInput;
  23 import java.io.ObjectOutput;
  24 import java.io.Externalizable;
  25 import java.util.Arrays;
  26
  27
  28 //////////////////////////////////////////////////
  29 // THIS IS A GENERATED CLASS. DO NOT HAND EDIT! //
  30 //////////////////////////////////////////////////
  31
  32
  33 /**
  34  * An open addressed Map implementation for int keys and Object values.
  35  *
  36  * Created: Sun Nov  4 08:52:45 2001
  37  *
  38  * @author Eric D. Friedman
  39  */
  40 @SuppressWarnings({"unchecked", "rawtypes", "unused"})
  41 public class TIntObjectHashMap<V> extends TIntHash implements Externalizable {
  42         static final long serialVersionUID = 1L;
  43
  44         private final TIntObjectProcedure<V> PUT_ALL_PROC = new TIntObjectProcedure<V>() {
  45         public boolean execute(int key, V value) {
  46             put(key, value);
  47             return true;
  48         }
  49     };
  50
  51
  52     /** the values of the map */
  53     protected transient V[] _values;
  54
  55     /**
  56      * Creates a new <code>TIntObjectHashMap</code> instance with the default
  57      * capacity and load factor.
  58      */
  59     public TIntObjectHashMap() {
  60         super();
  61     }
  62
  63     /**
  64      * Creates a new <code>TIntObjectHashMap</code> instance with a prime
  65      * capacity equal to or greater than <tt>initialCapacity</tt> and
  66      * with the default load factor.
  67      *
  68      * @param initialCapacity an <code>int</code> value
  69      */
  70     public TIntObjectHashMap(int initialCapacity) {
  71         super(initialCapacity);
  72     }
  73
  74     /**
  75      * Creates a new <code>TIntObjectHashMap</code> instance with a prime
  76      * capacity equal to or greater than <tt>initialCapacity</tt> and
  77      * with the specified load factor.
  78      *
  79      * @param initialCapacity an <code>int</code> value
  80      * @param loadFactor a <code>float</code> value
  81      */
  82     public TIntObjectHashMap(int initialCapacity, float loadFactor) {
  83         super(initialCapacity, loadFactor);
  84     }
  85
  86     /**
  87      * Creates a new <code>TIntObjectHashMap</code> instance with the default
  88      * capacity and load factor.
  89      * @param strategy used to compute hash codes and to compare keys.
  90      */
  91     public TIntObjectHashMap(TIntHashingStrategy strategy) {
  92         super(strategy);
  93     }
  94
  95     /**
  96      * Creates a new <code>TIntObjectHashMap</code> instance whose capacity
  97      * is the next highest prime above <tt>initialCapacity + 1</tt>
  98      * unless that value is already prime.
  99      *
 100      * @param initialCapacity an <code>int</code> value
 101      * @param strategy used to compute hash codes and to compare keys.
 102      */
 103     public TIntObjectHashMap(int initialCapacity, TIntHashingStrategy strategy) {
 104         super(initialCapacity, strategy);
 105     }
 106
 107     /**
 108      * Creates a new <code>TIntObjectHashMap</code> instance with a prime
 109      * value at or near the specified capacity and load factor.
 110      *
 111      * @param initialCapacity used to find a prime capacity for the table.
 112      * @param loadFactor used to calculate the threshold over which
 113      * rehashing takes place.
 114      * @param strategy used to compute hash codes and to compare keys.
 115      */
 116     public TIntObjectHashMap(int initialCapacity, float loadFactor, TIntHashingStrategy strategy) {
 117         super(initialCapacity, loadFactor, strategy);
 118     }
 119
 120     /**
 121      * @return a deep clone of this collection
 122      */
 123     public TIntObjectHashMap<V> clone() {
 124       TIntObjectHashMap<V> m = (TIntObjectHashMap<V>)super.clone();
 125       m._values = (V[]) this._values.clone();
 126       return m;
 127     }
 128
 129     /**
 130      * @return a TIntObjectIterator with access to this map's keys and values
 131      */
 132     public TIntObjectIterator<V> iterator() {
 133         return new TIntObjectIterator<V>(this);
 134     }
 135
 136     /**
 137      * initializes the hashtable to a prime capacity which is at least
 138      * <tt>initialCapacity + 1</tt>.
 139      *
 140      * @param initialCapacity an <code>int</code> value
 141      * @return the actual capacity chosen
 142      */
 143     protected int setUp(int initialCapacity) {
 144         int capacity;
 145
 146         capacity = super.setUp(initialCapacity);
 147         _values = (V[]) new Object[capacity];
 148         return capacity;
 149     }
 150
 151     /**
 152      * Inserts a key/value pair into the map.
 153      *
 154      * @param key an <code>int</code> value
 155      * @param value an <code>Object</code> value
 156      * @return the previous value associated with <tt>key</tt>,
 157      * or {@code null} if none was found.
 158      */
 159     public V put(int key, V value) {
 160         int index = insertionIndex(key);
 161         return doPut(key, value, index);
 162     }
 163
 164     /**
 165      * Inserts a key/value pair into the map if the specified key is not already
 166      * associated with a value.
 167      *
 168      * @param key an <code>int</code> value
 169      * @param value an <code>Object</code> value
 170      * @return the previous value associated with <tt>key</tt>,
 171      * or {@code null} if none was found.
 172      */
 173     public V putIfAbsent(int key, V value) {
 174         int index = insertionIndex(key);
 175         if (index < 0)
 176             return _values[-index - 1];
 177         return doPut(key, value, index);
 178     }
 179
 180     private V doPut(int key, V value, int index) {
 181         byte previousState;
 182         V previous = null;
 183         boolean isNewMapping = true;
 184         if (index < 0) {
 185             index = -index -1;
 186             previous = _values[index];
 187             isNewMapping = false;
 188         }
 189         previousState = _states[index];
 190         _set[index] = key;
 191         _states[index] = FULL;
 192         _values[index] = value;
 193         if (isNewMapping) {
 194             postInsertHook(previousState == FREE);
 195         }
 196
 197         return previous;
 198     }
 199
 200
 201     /**
 202      * Put all the entries from the given map into this map.
 203      *
 204      * @param map   The map from which entries will be obtained to put into this map.
 205      */
 206     public void putAll(TIntObjectHashMap<V> map){
 207         map.forEachEntry(PUT_ALL_PROC);
 208     }
 209
 210
 211     /**
 212      * rehashes the map to the new capacity.
 213      *
 214      * @param newCapacity an <code>int</code> value
 215      */
 216     protected void rehash(int newCapacity) {
 217         int oldCapacity = _set.length;
 218         int oldKeys[] = _set;
 219         V oldVals[] = _values;
 220         byte oldStates[] = _states;
 221
 222         _set = new int[newCapacity];
 223         _values = (V[]) new Object[newCapacity];
 224         _states = new byte[newCapacity];
 225
 226         for (int i = oldCapacity; i-- > 0;) {
 227             if(oldStates[i] == FULL) {
 228                 int o = oldKeys[i];
 229                 int index = insertionIndex(o);
 230                 _set[index] = o;
 231                 _values[index] = oldVals[i];
 232                 _states[index] = FULL;
 233             }
 234         }
 235     }
 236
 237     /**
 238      * retrieves the value for <tt>key</tt>
 239      *
 240      * @param key an <code>int</code> value
 241      * @return the value of <tt>key</tt> or (int)0 if no such mapping exists.
 242      */
 243     public V get(int key) {
 244         int index = index(key);
 245         return index < 0 ? null : _values[index];
 246     }
 247
 248     /**
 249      * Empties the map.
 250      *
 251      */
 252     public void clear() {
 253         super.clear();
 254         int[] keys = _set;
 255         Object[] vals = _values;
 256         byte[] states = _states;
 257
 258         Arrays.fill(_set, 0, _set.length, (int) 0);
 259         Arrays.fill(_values, 0, _values.length, null);
 260         Arrays.fill(_states, 0, _states.length, FREE);
 261     }
 262
 263     /**
 264      * Deletes a key/value pair from the map.
 265      *
 266      * @param key an <code>int</code> value
 267      * @return an <code>Object</code> value or (int)0 if no such mapping exists.
 268      */
 269     public V remove(int key) {
 270         V prev = null;
 271         int index = index(key);
 272         if (index >= 0) {
 273             prev = _values[index];
 274             removeAt(index);    // clear key,state; adjust size
 275         }
 276         return prev;
 277     }
 278
 279     /**
 280      * Compares this map with another map for equality of their stored
 281      * entries.
 282      *
 283      * @param other an <code>Object</code> value
 284      * @return a <code>boolean</code> value
 285      */
 286     public boolean equals(Object other) {
 287         if (! (other instanceof TIntObjectHashMap)) {
 288             return false;
 289         }
 290         TIntObjectHashMap that = (TIntObjectHashMap)other;
 291         if (that.size() != this.size()) {
 292             return false;
 293         }
 294         return forEachEntry(new EqProcedure(that));
 295     }
 296
 297     public int hashCode() {
 298         HashProcedure p = new HashProcedure();
 299         forEachEntry(p);
 300         return p.getHashCode();
 301     }
 302
 303     private final class HashProcedure implements TIntObjectProcedure {
 304         private int h = 0;
 305
 306         public int getHashCode() {
 307             return h;
 308         }
 309
 310         public final boolean execute(int key, Object value) {
 311             h += (_hashingStrategy.computeHashCode(key) ^ HashFunctions.hash(value));
 312             return true;
 313         }
 314     }
 315
 316     private static final class EqProcedure implements TIntObjectProcedure {
 317         private final TIntObjectHashMap _otherMap;
 318
 319         EqProcedure(TIntObjectHashMap otherMap) {
 320             _otherMap = otherMap;
 321         }
 322
 323         public final boolean execute(int key, Object value) {
 324             int index = _otherMap.index(key);
 325             if (index >= 0 && eq(value, _otherMap.get(key))) {
 326                 return true;
 327             }
 328             return false;
 329         }
 330
 331         /**
 332          * Compare two objects for equality.
 333          */
 334         private final boolean eq(Object o1, Object o2) {
 335             return o1 == o2 || ((o1 != null) && o1.equals(o2));
 336         }
 337
 338     }
 339
 340     /**
 341      * removes the mapping at <tt>index</tt> from the map.
 342      *
 343      * @param index an <code>int</code> value
 344      */
 345     protected void removeAt(int index) {
 346         _values[index] = null;
 347         super.removeAt(index);  // clear key, state; adjust size
 348     }
 349
 350     /**
 351      * Returns the values of the map.
 352      *
 353      * @return a <code>Collection</code> value
 354      *
 355      * @see #getValues(Object[])
 356      */
 357     public Object[] getValues() {
 358         Object[] vals = new Object[size()];
 359         V[] v = _values;
 360         byte[] states = _states;
 361
 362         for (int i = v.length, j = 0; i-- > 0;) {
 363             if (states[i] == FULL) {
 364                 vals[j++] = v[i];
 365             }
 366         }
 367         return vals;
 368     }
 369
 370     /**
 371      * Return the values of the map; the runtime type of the returned array is that of
 372      * the specified array.
 373     *
 374     * @param a the array into which the elements of this collection are to be
 375     *        stored, if it is big enough; otherwise, a new array of the same
 376     *        runtime type is allocated for this purpose.
 377     * @return an array containing the elements of this collection
 378     *
 379     * @throws ArrayStoreException the runtime type of the specified array is
 380     *         not a supertype of the runtime type of every element in this
 381     *         collection.
 382     * @throws NullPointerException if the specified array is <tt>null</tt>.
 383     *
 384     * @see #getValues()
 385     */
 386     public <T> T[] getValues( T[] a ) {
 387                 if (a.length < _size) {
 388                         a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(),
 389                         _size);
 390         }
 391
 392         V[] v = _values;
 393         byte[] states = _states;
 394
 395         for (int i = v.length, j = 0; i-- > 0;) {
 396             if (states[i] == FULL) {
 397                 a[j++] = (T) v[i];
 398             }
 399         }
 400                 return a;
 401     }
 402
 403     /**
 404      * returns the keys of the map.
 405      *
 406      * @return a <code>Set</code> value
 407      */
 408     public int[] keys() {
 409         int[] keys = new int[size()];
 410         int[] k = _set;
 411         byte[] states = _states;
 412
 413         for (int i = k.length, j = 0; i-- > 0;) {
 414           if (states[i] == FULL) {
 415             keys[j++] = k[i];
 416           }
 417         }
 418         return keys;
 419     }
 420
 421     /**
 422      * returns the keys of the map.
 423      *
 424      * @param a the array into which the elements of the list are to
 425      *        be stored, if it is big enough; otherwise, a new array of the
 426      *         same type is allocated for this purpose.
 427      * @return a <code>Set</code> value
 428      */
 429     public int[] keys(int[] a) {
 430         int size = size();
 431         if (a.length < size) {
 432             a = (int[]) java.lang.reflect.Array.newInstance(
 433                 a.getClass().getComponentType(), size);
 434         }
 435
 436         int[] k = (int[]) _set;
 437         byte[] states = _states;
 438
 439         for (int i = k.length, j = 0; i-- > 0;) {
 440           if (states[i] == FULL) {
 441             a[j++] = k[i];
 442           }
 443         }
 444         return a;
 445     }
 446
 447     /**
 448      * checks for the presence of <tt>val</tt> in the values of the map.
 449      *
 450      * @param val an <code>Object</code> value
 451      * @return a <code>boolean</code> value
 452      */
 453     public boolean containsValue(V val) {
 454         byte[] states = _states;
 455         V[] vals = _values;
 456
 457         // special case null values so that we don't have to
 458         // perform null checks before every call to equals()
 459         if (null == val) {
 460             for (int i = vals.length; i-- > 0;) {
 461                 if (states[i] == FULL &&
 462                         val == vals[i]) {
 463                     return true;
 464                 }
 465             }
 466         } else {
 467             for (int i = vals.length; i-- > 0;) {
 468                 if (states[i] == FULL &&
 469                     (val == vals[i] || val.equals(vals[i]))) {
 470                     return true;
 471                 }
 472             }
 473         } // end of else
 474         return false;
 475     }
 476
 477
 478     /**
 479      * checks for the present of <tt>key</tt> in the keys of the map.
 480      *
 481      * @param key an <code>int</code> value
 482      * @return a <code>boolean</code> value
 483      */
 484     public boolean containsKey(int key) {
 485         return contains(key);
 486     }
 487
 488     /**
 489      * Executes <tt>procedure</tt> for each key in the map.
 490      *
 491      * @param procedure a <code>TIntProcedure</code> value
 492      * @return false if the loop over the keys terminated because
 493      * the procedure returned false for some key.
 494      */
 495     public boolean forEachKey(TIntProcedure procedure) {
 496         return forEach(procedure);
 497     }
 498
 499     /**
 500      * Executes <tt>procedure</tt> for each value in the map.
 501      *
 502      * @param procedure a <code>TObjectProcedure</code> value
 503      * @return false if the loop over the values terminated because
 504      * the procedure returned false for some value.
 505      */
 506     public boolean forEachValue(TObjectProcedure<V> procedure) {
 507         byte[] states = _states;
 508         V[] values = _values;
 509         for (int i = values.length; i-- > 0;) {
 510             if (states[i] == FULL && ! procedure.execute(values[i])) {
 511                 return false;
 512             }
 513         }
 514         return true;
 515     }
 516
 517     /**
 518      * Executes <tt>procedure</tt> for each key/value entry in the
 519      * map.
 520      *
 521      * @param procedure a <code>TOIntObjectProcedure</code> value
 522      * @return false if the loop over the entries terminated because
 523      * the procedure returned false for some entry.
 524      */
 525     public boolean forEachEntry(TIntObjectProcedure<V> procedure) {
 526         byte[] states = _states;
 527         int[] keys = _set;
 528         V[] values = _values;
 529         for (int i = keys.length; i-- > 0;) {
 530             if (states[i] == FULL && ! procedure.execute(keys[i],values[i])) {
 531                 return false;
 532             }
 533         }
 534         return true;
 535     }
 536
 537     /**
 538      * Retains only those entries in the map for which the procedure
 539      * returns a true value.
 540      *
 541      * @param procedure determines which entries to keep
 542      * @return true if the map was modified.
 543      */
 544     public boolean retainEntries(TIntObjectProcedure<V> procedure) {
 545         boolean modified = false;
 546         byte[] states = _states;
 547         int[] keys = _set;
 548         V[] values = _values;
 549
 550         // Temporarily disable compaction. This is a fix for bug #1738760
 551         tempDisableAutoCompaction();
 552         try {
 553             for (int i = keys.length; i-- > 0;) {
 554                 if (states[i] == FULL && ! procedure.execute(keys[i],values[i])) {
 555                     removeAt(i);
 556                     modified = true;
 557                 }
 558             }
 559         }
 560         finally {
 561             reenableAutoCompaction(true);
 562         }
 563
 564         return modified;
 565     }
 566
 567     /**
 568      * Transform the values in this map using <tt>function</tt>.
 569      *
 570      * @param function a <code>TObjectFunction</code> value
 571      */
 572     public void transformValues(TObjectFunction<V,V> function) {
 573         byte[] states = _states;
 574         V[] values = _values;
 575         for (int i = values.length; i-- > 0;) {
 576             if (states[i] == FULL) {
 577                 values[i] = function.execute(values[i]);
 578             }
 579         }
 580     }
 581
 582
 583
 584
 585     public void writeExternal( ObjectOutput out ) throws IOException {
 586         // VERSION
 587         out.writeByte( 0 );
 588
 589         // NUMBER OF ENTRIES
 590         out.writeInt( _size );
 591
 592         // ENTRIES
 593         SerializationProcedure writeProcedure = new SerializationProcedure( out );
 594         if (! forEachEntry(writeProcedure)) {
 595             throw writeProcedure.exception;
 596         }
 597     }
 598
 599     public void readExternal( ObjectInput in )
 600         throws IOException, ClassNotFoundException {
 601
 602         // VERSION
 603         in.readByte();
 604
 605         // NUMBER OF ENTRIES
 606         int size = in.readInt();
 607         setUp( size );
 608
 609         // ENTRIES
 610         while (size-- > 0) {
 611             int key = in.readInt();
 612             V val = (V) in.readObject();
 613             put(key, val);
 614         }
 615     }
 616
 617     public String toString() {
 618         final StringBuilder buf = new StringBuilder("{");
 619         forEachEntry(new TIntObjectProcedure<V>() {
 620             private boolean first = true;
 621             public boolean execute(int key, Object value) {
 622                 if ( first ) first = false;
 623                 else buf.append( "," );
 624
 625                 buf.append(key);
 626                 buf.append("=");
 627                 buf.append(value);
 628                 return true;
 629             }
 630         });
 631         buf.append("}");
 632         return buf.toString();
 633     }
 634 } // TIntObjectHashMap