Clover coverage report - Drools - 2.0-rc2
Coverage timestamp: Wed May 11 2005 07:12:26 BST
file stats: LOC: 1,651   Methods: 91
NCLOC: 949   Classes: 10
 
 Source file Conditionals Statements Methods TOTAL
AbstractHashedMap.java 26.3% 39.4% 40.7% 36.3%
coverage coverage
 1    package org.drools.util;
 2    /*
 3    * Copyright 2003-2004 The Apache Software Foundation
 4    *
 5    * Licensed under the Apache License, Version 2.0 (the "License");
 6    * you may not use this file except in compliance with the License.
 7    * You may obtain a copy of the License at
 8    *
 9    * http://www.apache.org/licenses/LICENSE-2.0
 10    *
 11    * Unless required by applicable law or agreed to in writing, software
 12    * distributed under the License is distributed on an "AS IS" BASIS,
 13    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 14    * See the License for the specific language governing permissions and
 15    * limitations under the License.
 16    */
 17   
 18    import java.io.IOException;
 19    import java.io.ObjectInputStream;
 20    import java.io.ObjectOutputStream;
 21    import java.util.AbstractCollection;
 22    import java.util.AbstractMap;
 23    import java.util.AbstractSet;
 24    import java.util.Collection;
 25    import java.util.Collections;
 26    import java.util.ConcurrentModificationException;
 27    import java.util.Iterator;
 28    import java.util.Map;
 29    import java.util.NoSuchElementException;
 30    import java.util.Set;
 31   
 32    /**
 33    * An abstract implementation of a hash-based map which provides numerous points
 34    * for subclasses to override.
 35    * <p>
 36    * This class implements all the features necessary for a subclass hash-based
 37    * map. Key-value entries are stored in instances of the <code>HashEntry</code>
 38    * class, which can be overridden and replaced. The iterators can similarly be
 39    * replaced, without the need to replace the KeySet, EntrySet and Values view
 40    * classes.
 41    * <p>
 42    * Overridable methods are provided to change the default hashing behaviour, and
 43    * to change how entries are added to and removed from the map. Hopefully, all
 44    * you need for unusual subclasses is here.
 45    * <p>
 46    * NOTE: From Commons Collections 3.1 this class extends AbstractMap. This is to
 47    * provide backwards compatibility for ReferenceMap between v3.0 and v3.1. This
 48    * extends clause will be removed in v4.0.
 49    *
 50    * @since Commons Collections 3.0
 51    * @version $Revision: 1.4 $ $Date: 2004/12/06 01:30:38 $
 52    *
 53    * @author java util HashMap
 54    * @author Stephen Colebourne
 55    */
 56    public class AbstractHashedMap extends AbstractMap
 57    {
 58   
 59    protected static final String NO_NEXT_ENTRY = "No next() entry in the iteration";
 60    protected static final String NO_PREVIOUS_ENTRY = "No previous() entry in the iteration";
 61    protected static final String REMOVE_INVALID = "remove() can only be called once after next()";
 62    protected static final String GETKEY_INVALID = "getKey() can only be called after next() and before remove()";
 63    protected static final String GETVALUE_INVALID = "getValue() can only be called after next() and before remove()";
 64    protected static final String SETVALUE_INVALID = "setValue() can only be called after next() and before remove()";
 65   
 66    /** The default capacity to use */
 67    protected static final int DEFAULT_CAPACITY = 16;
 68    /** The default threshold to use */
 69    protected static final int DEFAULT_THRESHOLD = 12;
 70    /** The default load factor to use */
 71    protected static final float DEFAULT_LOAD_FACTOR = 0.75f;
 72    /** The maximum capacity allowed */
 73    protected static final int MAXIMUM_CAPACITY = 1 << 30;
 74    /** An object for masking null */
 75    protected static final Object NULL = new Object( );
 76   
 77    /** Load factor, normally 0.75 */
 78    protected transient float loadFactor;
 79    /** The size of the map */
 80    protected transient int size;
 81    /** Map entries */
 82    protected transient HashEntry[] data;
 83    /** Size at which to rehash */
 84    protected transient int threshold;
 85    /** Modification count for iterators */
 86    protected transient int modCount;
 87    /** Entry set */
 88    protected transient EntrySet entrySet;
 89    /** Key set */
 90    protected transient KeySet keySet;
 91    /** Values */
 92    protected transient Values values;
 93   
 94    /**
 95    * Constructor only used in deserialization, do not use otherwise.
 96    */
 97  15 protected AbstractHashedMap()
 98    {
 99  15 super( );
 100    }
 101   
 102    /**
 103    * Constructor which performs no validation on the passed in parameters.
 104    *
 105    * @param initialCapacity
 106    * the initial capacity, must be a power of two
 107    * @param loadFactor
 108    * the load factor, must be &gt; 0.0f and generally &lt; 1.0f
 109    * @param threshold
 110    * the threshold, must be sensible
 111    */
 112  71 protected AbstractHashedMap(int initialCapacity,
 113    float loadFactor,
 114    int threshold)
 115    {
 116  71 super( );
 117  71 this.loadFactor = loadFactor;
 118  71 this.data = new HashEntry[initialCapacity];
 119  71 this.threshold = threshold;
 120  71 init( );
 121    }
 122   
 123    /**
 124    * Constructs a new, empty map with the specified initial capacity and
 125    * default load factor.
 126    *
 127    * @param initialCapacity
 128    * the initial capacity
 129    * @throws IllegalArgumentException
 130    * if the initial capacity is less than one
 131    */
 132  0 protected AbstractHashedMap(int initialCapacity)
 133    {
 134  0 this( initialCapacity,
 135    DEFAULT_LOAD_FACTOR );
 136    }
 137   
 138    /**
 139    * Constructs a new, empty map with the specified initial capacity and load
 140    * factor.
 141    *
 142    * @param initialCapacity
 143    * the initial capacity
 144    * @param loadFactor
 145    * the load factor
 146    * @throws IllegalArgumentException
 147    * if the initial capacity is less than one
 148    * @throws IllegalArgumentException
 149    * if the load factor is less than or equal to zero
 150    */
 151  0 protected AbstractHashedMap(int initialCapacity,
 152    float loadFactor)
 153    {
 154  0 super( );
 155  0 if ( initialCapacity < 1 )
 156    {
 157  0 throw new IllegalArgumentException( "Initial capacity must be greater than 0" );
 158    }
 159  0 if ( loadFactor <= 0.0f || Float.isNaN( loadFactor ) )
 160    {
 161  0 throw new IllegalArgumentException( "Load factor must be greater than 0" );
 162    }
 163  0 this.loadFactor = loadFactor;
 164  0 this.threshold = calculateThreshold( initialCapacity,
 165    loadFactor );
 166  0 initialCapacity = calculateNewCapacity( initialCapacity );
 167  0 this.data = new HashEntry[initialCapacity];
 168  0 init( );
 169    }
 170   
 171    /**
 172    * Constructor copying elements from another map.
 173    *
 174    * @param map
 175    * the map to copy
 176    * @throws NullPointerException
 177    * if the map is null
 178    */
 179  0 protected AbstractHashedMap(Map map)
 180    {
 181  0 this( Math.max( 2 * map.size( ),
 182    DEFAULT_CAPACITY ),
 183    DEFAULT_LOAD_FACTOR );
 184  0 putAll( map );
 185    }
 186   
 187    /**
 188    * Initialise subclasses during construction, cloning or deserialization.
 189    */
 190  86 protected void init()
 191    {
 192    }
 193   
 194    // -----------------------------------------------------------------------
 195    /**
 196    * Gets the value mapped to the key specified.
 197    *
 198    * @param key
 199    * the key
 200    * @return the mapped value, null if no match
 201    */
 202  1234 public Object get(Object key)
 203    {
 204  1234 key = convertKey( key );
 205  1234 int hashCode = hash( key );
 206  1234 HashEntry entry = data[hashIndex( hashCode,
 207    data.length )]; // no local for hash
 208    // index
 209  1234 while ( entry != null )
 210    {
 211  800 if ( entry.hashCode == hashCode && isEqualKey( key,
 212    entry.key ) )
 213    {
 214  362 return entry.getValue( );
 215    }
 216  438 entry = entry.next;
 217    }
 218  872 return null;
 219    }
 220   
 221    /**
 222    * Gets the size of the map.
 223    *
 224    * @return the size
 225    */
 226  3 public int size()
 227    {
 228  3 return size;
 229    }
 230   
 231    /**
 232    * Checks whether the map is currently empty.
 233    *
 234    * @return true if the map is currently size zero
 235    */
 236  0 public boolean isEmpty()
 237    {
 238  0 return (size == 0);
 239    }
 240   
 241    // -----------------------------------------------------------------------
 242    /**
 243    * Checks whether the map contains the specified key.
 244    *
 245    * @param key
 246    * the key to search for
 247    * @return true if the map contains the key
 248    */
 249  0 public boolean containsKey(Object key)
 250    {
 251  0 key = convertKey( key );
 252  0 int hashCode = hash( key );
 253  0 HashEntry entry = data[hashIndex( hashCode,
 254    data.length )]; // no local for hash
 255    // index
 256  0 while ( entry != null )
 257    {
 258  0 if ( entry.hashCode == hashCode && isEqualKey( key,
 259    entry.key ) )
 260    {
 261  0 return true;
 262    }
 263  0 entry = entry.next;
 264    }
 265  0 return false;
 266    }
 267   
 268    /**
 269    * Checks whether the map contains the specified value.
 270    *
 271    * @param value
 272    * the value to search for
 273    * @return true if the map contains the value
 274    */
 275  0 public boolean containsValue(Object value)
 276    {
 277  0 if ( value == null )
 278    {
 279  0 for ( int i = 0, isize = data.length; i < isize; i++ )
 280    {
 281  0 HashEntry entry = data[i];
 282  0 while ( entry != null )
 283    {
 284  0 if ( entry.getValue( ) == null )
 285    {
 286  0 return true;
 287    }
 288  0 entry = entry.next;
 289    }
 290    }
 291    }
 292    else
 293    {
 294  0 for ( int i = 0, isize = data.length; i < isize; i++ )
 295    {
 296  0 HashEntry entry = data[i];
 297  0 while ( entry != null )
 298    {
 299  0 if ( isEqualValue( value,
 300    entry.getValue( ) ) )
 301    {
 302  0 return true;
 303    }
 304  0 entry = entry.next;
 305    }
 306    }
 307    }
 308  0 return false;
 309    }
 310   
 311    // -----------------------------------------------------------------------
 312    /**
 313    * Puts a key-value mapping into this map.
 314    *
 315    * @param key
 316    * the key to add
 317    * @param value
 318    * the value to add
 319    * @return the value previously mapped to this key, null if none
 320    */
 321  1337 public Object put(Object key,
 322    Object value)
 323    {
 324  1337 key = convertKey( key );
 325  1337 int hashCode = hash( key );
 326  1337 int index = hashIndex( hashCode,
 327    data.length );
 328  1337 HashEntry entry = data[index];
 329  1337 while ( entry != null )
 330    {
 331  587 if ( entry.hashCode == hashCode && isEqualKey( key,
 332    entry.key ) )
 333    {
 334  0 Object oldValue = entry.getValue( );
 335  0 updateEntry( entry,
 336    value );
 337  0 return oldValue;
 338    }
 339  587 entry = entry.next;
 340    }
 341   
 342  1337 addMapping( index,
 343    hashCode,
 344    key,
 345    value );
 346  1337 return null;
 347    }
 348   
 349    /**
 350    * Puts all the values from the specified map into this map.
 351    * <p>
 352    * This implementation iterates around the specified map and uses
 353    * {@link #put(Object, Object)}.
 354    *
 355    * @param map
 356    * the map to add
 357    * @throws NullPointerException
 358    * if the map is null
 359    */
 360  0 public void putAll(Map map)
 361    {
 362  0 int mapSize = map.size( );
 363  0 if ( mapSize == 0 )
 364    {
 365  0 return;
 366    }
 367  0 int newSize = (int) ((size + mapSize) / loadFactor + 1);
 368  0 ensureCapacity( calculateNewCapacity( newSize ) );
 369  0 for ( Iterator it = map.entrySet( ).iterator( ); it.hasNext( ); )
 370    {
 371  0 Map.Entry entry = (Map.Entry) it.next( );
 372  0 put( entry.getKey( ),
 373    entry.getValue( ) );
 374    }
 375    }
 376   
 377    /**
 378    * Removes the specified mapping from this map.
 379    *
 380    * @param key
 381    * the mapping to remove
 382    * @return the value mapped to the removed key, null if key not in map
 383    */
 384  370 public Object remove(Object key)
 385    {
 386  370 key = convertKey( key );
 387  370 int hashCode = hash( key );
 388  370 int index = hashIndex( hashCode,
 389    data.length );
 390  370 HashEntry entry = data[index];
 391  370 HashEntry previous = null;
 392  381 while ( entry != null )
 393    {
 394  381 if ( entry.hashCode == hashCode && isEqualKey( key,
 395    entry.key ) )
 396    {
 397  370 Object oldValue = entry.getValue( );
 398  370 removeMapping( entry,
 399    index,
 400    previous );
 401  370 return oldValue;
 402    }
 403  11 previous = entry;
 404  11 entry = entry.next;
 405    }
 406  0 return null;
 407    }
 408   
 409    /**
 410    * Clears the map, resetting the size to zero and nullifying references to
 411    * avoid garbage collection issues.
 412    */
 413  0 public void clear()
 414    {
 415  0 modCount++;
 416  0 HashEntry[] data = this.data;
 417  0 for ( int i = data.length - 1; i >= 0; i-- )
 418    {
 419  0 data[i] = null;
 420    }
 421  0 size = 0;
 422    }
 423   
 424    // -----------------------------------------------------------------------
 425    /**
 426    * Converts input keys to another object for storage in the map. This
 427    * implementation masks nulls. Subclasses can override this to perform
 428    * alternate key conversions.
 429    * <p>
 430    * The reverse conversion can be changed, if required, by overriding the
 431    * getKey() method in the hash entry.
 432    *
 433    * @param key
 434    * the key convert
 435    * @return the converted key
 436    */
 437  2941 protected Object convertKey(Object key)
 438    {
 439  2941 return (key == null ? NULL : key);
 440    }
 441   
 442    /**
 443    * Gets the hash code for the key specified. This implementation uses the
 444    * additional hashing routine from JDK1.4. Subclasses can override this to
 445    * return alternate hash codes.
 446    *
 447    * @param key
 448    * the key to get a hash code for
 449    * @return the hash code
 450    */
 451  0 protected int hash(Object key)
 452    {
 453    // same as JDK 1.4
 454  0 int h = key.hashCode( );
 455  0 h += ~(h << 9);
 456  0 h ^= (h >>> 14);
 457  0 h += (h << 4);
 458  0 h ^= (h >>> 10);
 459  0 return h;
 460    }
 461   
 462    /**
 463    * Compares two keys, in internal converted form, to see if they are equal.
 464    * This implementation uses the equals method and assumes neither key is
 465    * null. Subclasses can override this to match differently.
 466    *
 467    * @param key1
 468    * the first key to compare passed in from outside
 469    * @param key2
 470    * the second key extracted from the entry via
 471    * <code>entry.key</code>
 472    * @return true if equal
 473    */
 474  0 protected boolean isEqualKey(Object key1,
 475    Object key2)
 476    {
 477  0 return (key1 == key2 || key1.equals( key2 ));
 478    }
 479   
 480    /**
 481    * Compares two values, in external form, to see if they are equal. This
 482    * implementation uses the equals method and assumes neither value is null.
 483    * Subclasses can override this to match differently.
 484    *
 485    * @param value1
 486    * the first value to compare passed in from outside
 487    * @param value2
 488    * the second value extracted from the entry via
 489    * <code>getValue()</code>
 490    * @return true if equal
 491    */
 492  0 protected boolean isEqualValue(Object value1,
 493    Object value2)
 494    {
 495  0 return (value1 == value2 || value1.equals( value2 ));
 496    }
 497   
 498    /**
 499    * Gets the index into the data storage for the hashCode specified. This
 500    * implementation uses the least significant bits of the hashCode.
 501    * Subclasses can override this to return alternate bucketing.
 502    *
 503    * @param hashCode
 504    * the hash code to use
 505    * @param dataSize
 506    * the size of the data to pick a bucket from
 507    * @return the bucket index
 508    */
 509  4403 protected int hashIndex(int hashCode,
 510    int dataSize)
 511    {
 512  4403 return hashCode & (dataSize - 1);
 513    }
 514   
 515    // -----------------------------------------------------------------------
 516    /**
 517    * Gets the entry mapped to the key specified.
 518    * <p>
 519    * This method exists for subclasses that may need to perform a multi-step
 520    * process accessing the entry. The public methods in this class don't use
 521    * this method to gain a small performance boost.
 522    *
 523    * @param key
 524    * the key
 525    * @return the entry, null if no match
 526    */
 527  0 protected HashEntry getEntry(Object key)
 528    {
 529  0 key = convertKey( key );
 530  0 int hashCode = hash( key );
 531  0 HashEntry entry = data[hashIndex( hashCode,
 532    data.length )]; // no local for hash
 533    // index
 534  0 while ( entry != null )
 535    {
 536  0 if ( entry.hashCode == hashCode && isEqualKey( key,
 537    entry.key ) )
 538    {
 539  0 return entry;
 540    }
 541  0 entry = entry.next;
 542    }
 543  0 return null;
 544    }
 545   
 546    // -----------------------------------------------------------------------
 547    /**
 548    * Updates an existing key-value mapping to change the value.
 549    * <p>
 550    * This implementation calls <code>setValue()</code> on the entry.
 551    * Subclasses could override to handle changes to the map.
 552    *
 553    * @param entry
 554    * the entry to update
 555    * @param newValue
 556    * the new value to store
 557    */
 558  0 protected void updateEntry(HashEntry entry,
 559    Object newValue)
 560    {
 561  0 entry.setValue( newValue );
 562    }
 563   
 564    /**
 565    * Reuses an existing key-value mapping, storing completely new data.
 566    * <p>
 567    * This implementation sets all the data fields on the entry. Subclasses
 568    * could populate additional entry fields.
 569    *
 570    * @param entry
 571    * the entry to update, not null
 572    * @param hashIndex
 573    * the index in the data array
 574    * @param hashCode
 575    * the hash code of the key to add
 576    * @param key
 577    * the key to add
 578    * @param value
 579    * the value to add
 580    */
 581  0 protected void reuseEntry(HashEntry entry,
 582    int hashIndex,
 583    int hashCode,
 584    Object key,
 585    Object value)
 586    {
 587  0 entry.next = data[hashIndex];
 588  0 entry.hashCode = hashCode;
 589  0 entry.key = key;
 590  0 entry.value = value;
 591    }
 592   
 593    // -----------------------------------------------------------------------
 594    /**
 595    * Adds a new key-value mapping into this map.
 596    * <p>
 597    * This implementation calls <code>createEntry()</code>,
 598    * <code>addEntry()</code> and <code>checkCapacity()</code>. It also
 599    * handles changes to <code>modCount</code> and <code>size</code>.
 600    * Subclasses could override to fully control adds to the map.
 601    *
 602    * @param hashIndex
 603    * the index into the data array to store at
 604    * @param hashCode
 605    * the hash code of the key to add
 606    * @param key
 607    * the key to add
 608    * @param value
 609    * the value to add
 610    */
 611  1337 protected void addMapping(int hashIndex,
 612    int hashCode,
 613    Object key,
 614    Object value)
 615    {
 616  1337 modCount++;
 617  1337 HashEntry entry = createEntry( data[hashIndex],
 618    hashCode,
 619    key,
 620    value );
 621  1337 addEntry( entry,
 622    hashIndex );
 623  1337 size++;
 624  1337 checkCapacity( );
 625    }
 626   
 627    /**
 628    * Creates an entry to store the key-value data.
 629    * <p>
 630    * This implementation creates a new HashEntry instance. Subclasses can
 631    * override this to return a different storage class, or implement caching.
 632    *
 633    * @param next
 634    * the next entry in sequence
 635    * @param hashCode
 636    * the hash code to use
 637    * @param key
 638    * the key to store
 639    * @param value
 640    * the value to store
 641    * @return the newly created entry
 642    */
 643  0 protected HashEntry createEntry(HashEntry next,
 644    int hashCode,
 645    Object key,
 646    Object value)
 647    {
 648  0 return new HashEntry( next,
 649    hashCode,
 650    key,
 651    value );
 652    }
 653   
 654    /**
 655    * Adds an entry into this map.
 656    * <p>
 657    * This implementation adds the entry to the data storage table. Subclasses
 658    * could override to handle changes to the map.
 659    *
 660    * @param entry
 661    * the entry to add
 662    * @param hashIndex
 663    * the index into the data array to store at
 664    */
 665  1337 protected void addEntry(HashEntry entry,
 666    int hashIndex)
 667    {
 668  1337 data[hashIndex] = entry;
 669    }
 670   
 671    // -----------------------------------------------------------------------
 672    /**
 673    * Removes a mapping from the map.
 674    * <p>
 675    * This implementation calls <code>removeEntry()</code> and
 676    * <code>destroyEntry()</code>. It also handles changes to
 677    * <code>modCount</code> and <code>size</code>. Subclasses could
 678    * override to fully control removals from the map.
 679    *
 680    * @param entry
 681    * the entry to remove
 682    * @param hashIndex
 683    * the index into the data structure
 684    * @param previous
 685    * the previous entry in the chain
 686    */
 687  370 protected void removeMapping(HashEntry entry,
 688    int hashIndex,
 689    HashEntry previous)
 690    {
 691  370 modCount++;
 692  370 removeEntry( entry,
 693    hashIndex,
 694    previous );
 695  370 size--;
 696  370 destroyEntry( entry );
 697    }
 698   
 699    /**
 700    * Removes an entry from the chain stored in a particular index.
 701    * <p>
 702    * This implementation removes the entry from the data storage table. The
 703    * size is not updated. Subclasses could override to handle changes to the
 704    * map.
 705    *
 706    * @param entry
 707    * the entry to remove
 708    * @param hashIndex
 709    * the index into the data structure
 710    * @param previous
 711    * the previous entry in the chain
 712    */
 713  370 protected void removeEntry(HashEntry entry,
 714    int hashIndex,
 715    HashEntry previous)
 716    {
 717  370 if ( previous == null )
 718    {
 719  359 data[hashIndex] = entry.next;
 720    }
 721    else
 722    {
 723  11 previous.next = entry.next;
 724    }
 725    }
 726   
 727    /**
 728    * Kills an entry ready for the garbage collector.
 729    * <p>
 730    * This implementation prepares the HashEntry for garbage collection.
 731    * Subclasses can override this to implement caching (override clear as
 732    * well).
 733    *
 734    * @param entry
 735    * the entry to destroy
 736    */
 737  370 protected void destroyEntry(HashEntry entry)
 738    {
 739  370 entry.next = null;
 740  370 entry.key = null;
 741  370 entry.value = null;
 742    }
 743   
 744    // -----------------------------------------------------------------------
 745    /**
 746    * Checks the capacity of the map and enlarges it if necessary.
 747    * <p>
 748    * This implementation uses the threshold to check if the map needs
 749    * enlarging
 750    */
 751  1337 protected void checkCapacity()
 752    {
 753  1337 if ( size >= threshold )
 754    {
 755  30 int newCapacity = data.length * 2;
 756  30 if ( newCapacity <= MAXIMUM_CAPACITY )
 757    {
 758  30 ensureCapacity( newCapacity );
 759    }
 760    }
 761    }
 762   
 763    /**
 764    * Changes the size of the data structure to the capacity proposed.
 765    *
 766    * @param newCapacity
 767    * the new capacity of the array (a power of two, less or equal
 768    * to max)
 769    */
 770  30 protected void ensureCapacity(int newCapacity)
 771    {
 772  30 int oldCapacity = data.length;
 773  30 if ( newCapacity <= oldCapacity )
 774    {
 775  0 return;
 776    }
 777  30 if ( size == 0 )
 778    {
 779  0 threshold = calculateThreshold( newCapacity,
 780    loadFactor );
 781  0 data = new HashEntry[newCapacity];
 782    }
 783    else
 784    {
 785  30 HashEntry oldEntries[] = data;
 786  30 HashEntry newEntries[] = new HashEntry[newCapacity];
 787   
 788  30 modCount++;
 789  30 for ( int i = oldCapacity - 1; i >= 0; i-- )
 790    {
 791  2896 HashEntry entry = oldEntries[i];
 792  2896 if ( entry != null )
 793    {
 794  1048 oldEntries[i] = null; // gc
 795  1048 do
 796    {
 797  1462 HashEntry next = entry.next;
 798  1462 int index = hashIndex( entry.hashCode,
 799    newCapacity );
 800  1462 entry.next = newEntries[index];
 801  1462 newEntries[index] = entry;
 802  1462 entry = next;
 803    }
 804  1462 while ( entry != null );
 805    }
 806    }
 807  30 threshold = calculateThreshold( newCapacity,
 808    loadFactor );
 809  30 data = newEntries;
 810    }
 811    }
 812   
 813    /**
 814    * Calculates the new capacity of the map. This implementation normalizes
 815    * the capacity to a power of two.
 816    *
 817    * @param proposedCapacity
 818    * the proposed capacity
 819    * @return the normalized new capacity
 820    */
 821  0 protected int calculateNewCapacity(int proposedCapacity)
 822    {
 823  0 int newCapacity = 1;
 824  0 if ( proposedCapacity > MAXIMUM_CAPACITY )
 825    {
 826  0 newCapacity = MAXIMUM_CAPACITY;
 827    }
 828    else
 829    {
 830  0 while ( newCapacity < proposedCapacity )
 831    {
 832  0 newCapacity <<= 1; // multiply by two
 833    }
 834  0 if ( newCapacity > MAXIMUM_CAPACITY )
 835    {
 836  0 newCapacity = MAXIMUM_CAPACITY;
 837    }
 838    }
 839  0 return newCapacity;
 840    }
 841   
 842    /**
 843    * Calculates the new threshold of the map, where it will be resized. This
 844    * implementation uses the load factor.
 845    *
 846    * @param newCapacity
 847    * the new capacity
 848    * @param factor
 849    * the load factor
 850    * @return the new resize threshold
 851    */
 852  45 protected int calculateThreshold(int newCapacity,
 853    float factor)
 854    {
 855  45 return (int) (newCapacity * factor);
 856    }
 857   
 858    // -----------------------------------------------------------------------
 859    /**
 860    * Gets the <code>next</code> field from a <code>HashEntry</code>. Used
 861    * in subclasses that have no visibility of the field.
 862    *
 863    * @param entry
 864    * the entry to query, must not be null
 865    * @return the <code>next</code> field of the entry
 866    * @throws NullPointerException
 867    * if the entry is null
 868    * @since Commons Collections 3.1
 869    */
 870  0 protected HashEntry entryNext(HashEntry entry)
 871    {
 872  0 return entry.next;
 873    }
 874   
 875    /**
 876    * Gets the <code>hashCode</code> field from a <code>HashEntry</code>.
 877    * Used in subclasses that have no visibility of the field.
 878    *
 879    * @param entry
 880    * the entry to query, must not be null
 881    * @return the <code>hashCode</code> field of the entry
 882    * @throws NullPointerException
 883    * if the entry is null
 884    * @since Commons Collections 3.1
 885    */
 886  0 protected int entryHashCode(HashEntry entry)
 887    {
 888  0 return entry.hashCode;
 889    }
 890   
 891    /**
 892    * Gets the <code>key</code> field from a <code>HashEntry</code>. Used
 893    * in subclasses that have no visibility of the field.
 894    *
 895    * @param entry
 896    * the entry to query, must not be null
 897    * @return the <code>key</code> field of the entry
 898    * @throws NullPointerException
 899    * if the entry is null
 900    * @since Commons Collections 3.1
 901    */
 902  0 protected Object entryKey(HashEntry entry)
 903    {
 904  0 return entry.key;
 905    }
 906   
 907    /**
 908    * Gets the <code>value</code> field from a <code>HashEntry</code>.
 909    * Used in subclasses that have no visibility of the field.
 910    *
 911    * @param entry
 912    * the entry to query, must not be null
 913    * @return the <code>value</code> field of the entry
 914    * @throws NullPointerException
 915    * if the entry is null
 916    * @since Commons Collections 3.1
 917    */
 918  0 protected Object entryValue(HashEntry entry)
 919    {
 920  0 return entry.value;
 921    }
 922   
 923    // -----------------------------------------------------------------------
 924    /**
 925    * Gets an iterator over the map. Changes made to the iterator affect this
 926    * map.
 927    * <p>
 928    * A MapIterator returns the keys in the map. It also provides convenient
 929    * methods to get the key and value, and set the value. It avoids the need
 930    * to create an entrySet/keySet/values object. It also avoids creating the
 931    * Map.Entry object.
 932    *
 933    * @return the map iterator
 934    */
 935  15 private MapIterator mapIterator()
 936    {
 937  15 if ( size == 0 )
 938    {
 939  5 return EmptyMapIterator.INSTANCE;
 940    }
 941  10 return new HashMapIterator( this );
 942    }
 943   
 944    /**
 945    * MapIterator implementation.
 946    */
 947    protected static class HashMapIterator extends HashIterator
 948    implements
 949    MapIterator
 950    {
 951   
 952  10 protected HashMapIterator(AbstractHashedMap parent)
 953    {
 954  10 super( parent );
 955    }
 956   
 957  144 public Object next()
 958    {
 959  144 return super.nextEntry( ).getKey( );
 960    }
 961   
 962  0 public Object getKey()
 963    {
 964  0 HashEntry current = currentEntry( );
 965  0 if ( current == null )
 966    {
 967  0 throw new IllegalStateException( AbstractHashedMap.GETKEY_INVALID );
 968    }
 969  0 return current.getKey( );
 970    }
 971   
 972  144 public Object getValue()
 973    {
 974  144 HashEntry current = currentEntry( );
 975  144 if ( current == null )
 976    {
 977  0 throw new IllegalStateException( AbstractHashedMap.GETVALUE_INVALID );
 978    }
 979  144 return current.getValue( );
 980    }
 981   
 982  0 public Object setValue(Object value)
 983    {
 984  0 HashEntry current = currentEntry( );
 985  0 if ( current == null )
 986    {
 987  0 throw new IllegalStateException( AbstractHashedMap.SETVALUE_INVALID );
 988    }
 989  0 return current.setValue( value );
 990    }
 991    }
 992   
 993    // -----------------------------------------------------------------------
 994    /**
 995    * Gets the entrySet view of the map. Changes made to the view affect this
 996    * map. To simply iterate through the entries, use {@link #mapIterator()}.
 997    *
 998    * @return the entrySet view
 999    */
 1000  0 public Set entrySet()
 1001    {
 1002  0 if ( entrySet == null )
 1003    {
 1004  0 entrySet = new EntrySet( this );
 1005    }
 1006  0 return entrySet;
 1007    }
 1008   
 1009    /**
 1010    * Creates an entry set iterator. Subclasses can override this to return
 1011    * iterators with different properties.
 1012    *
 1013    * @return the entrySet iterator
 1014    */
 1015  0 protected Iterator createEntrySetIterator()
 1016    {
 1017  0 if ( size( ) == 0 )
 1018    {
 1019  0 return Collections.EMPTY_MAP.keySet( ).iterator( );
 1020    }
 1021  0 return new EntrySetIterator( this );
 1022    }
 1023   
 1024    /**
 1025    * EntrySet implementation.
 1026    */
 1027    protected static class EntrySet extends AbstractSet
 1028    {
 1029    /** The parent map */
 1030    protected final AbstractHashedMap parent;
 1031   
 1032  0 protected EntrySet(AbstractHashedMap parent)
 1033    {
 1034  0 super( );
 1035  0 this.parent = parent;
 1036    }
 1037   
 1038  0 public int size()
 1039    {
 1040  0 return parent.size( );
 1041    }
 1042   
 1043  0 public void clear()
 1044    {
 1045  0 parent.clear( );
 1046    }
 1047   
 1048  0 public boolean contains(Object entry)
 1049    {
 1050  0 if ( entry instanceof Map.Entry )
 1051    {
 1052  0 Map.Entry e = (Map.Entry) entry;
 1053  0 Entry match = parent.getEntry( e.getKey( ) );
 1054  0 return (match != null && match.equals( e ));
 1055    }
 1056  0 return false;
 1057    }
 1058   
 1059  0 public boolean remove(Object obj)
 1060    {
 1061  0 if ( obj instanceof Map.Entry == false )
 1062    {
 1063  0 return false;
 1064    }
 1065  0 if ( contains( obj ) == false )
 1066    {
 1067  0 return false;
 1068    }
 1069  0 Map.Entry entry = (Map.Entry) obj;
 1070  0 Object key = entry.getKey( );
 1071  0 parent.remove( key );
 1072  0 return true;
 1073    }
 1074   
 1075  0 public Iterator iterator()
 1076    {
 1077  0 return parent.createEntrySetIterator( );
 1078    }
 1079    }
 1080   
 1081    /**
 1082    * EntrySet iterator.
 1083    */
 1084    protected static class EntrySetIterator extends HashIterator
 1085    {
 1086   
 1087  0 protected EntrySetIterator(AbstractHashedMap parent)
 1088    {
 1089  0 super( parent );
 1090    }
 1091   
 1092  0 public Object next()
 1093    {
 1094  0 return super.nextEntry( );
 1095    }
 1096    }
 1097   
 1098    // -----------------------------------------------------------------------
 1099    /**
 1100    * Gets the keySet view of the map. Changes made to the view affect this
 1101    * map. To simply iterate through the keys, use {@link #mapIterator()}.
 1102    *
 1103    * @return the keySet view
 1104    */
 1105  0 public Set keySet()
 1106    {
 1107  0 if ( keySet == null )
 1108    {
 1109  0 keySet = new KeySet( this );
 1110    }
 1111  0 return keySet;
 1112    }
 1113   
 1114    /**
 1115    * Creates a key set iterator. Subclasses can override this to return
 1116    * iterators with different properties.
 1117    *
 1118    * @return the keySet iterator
 1119    */
 1120  0 protected Iterator createKeySetIterator()
 1121    {
 1122  0 if ( size( ) == 0 )
 1123    {
 1124  0 return Collections.EMPTY_MAP.keySet().iterator();
 1125    }
 1126  0 return new KeySetIterator( this );
 1127    }
 1128   
 1129    /**
 1130    * KeySet implementation.
 1131    */
 1132    protected static class KeySet extends AbstractSet
 1133    {
 1134    /** The parent map */
 1135    protected final AbstractHashedMap parent;
 1136   
 1137  0 protected KeySet(AbstractHashedMap parent)
 1138    {
 1139  0 super( );
 1140  0 this.parent = parent;
 1141    }
 1142   
 1143  0 public int size()
 1144    {
 1145  0 return parent.size( );
 1146    }
 1147   
 1148  0 public void clear()
 1149    {
 1150  0 parent.clear( );
 1151    }
 1152   
 1153  0 public boolean contains(Object key)
 1154    {
 1155  0 return parent.containsKey( key );
 1156    }
 1157   
 1158  0 public boolean remove(Object key)
 1159    {
 1160  0 boolean result = parent.containsKey( key );
 1161  0 parent.remove( key );
 1162  0 return result;
 1163    }
 1164   
 1165  0 public Iterator iterator()
 1166    {
 1167  0 return parent.createKeySetIterator( );
 1168    }
 1169    }
 1170   
 1171    /**
 1172    * KeySet iterator.
 1173    */
 1174    protected static class KeySetIterator extends EntrySetIterator
 1175    {
 1176   
 1177  0 protected KeySetIterator(AbstractHashedMap parent)
 1178    {
 1179  0 super( parent );
 1180    }
 1181   
 1182  0 public Object next()
 1183    {
 1184  0 return super.nextEntry( ).getKey( );
 1185    }
 1186    }
 1187   
 1188    // -----------------------------------------------------------------------
 1189    /**
 1190    * Gets the values view of the map. Changes made to the view affect this
 1191    * map. To simply iterate through the values, use {@link #mapIterator()}.
 1192    *
 1193    * @return the values view
 1194    */
 1195  1 public Collection values()
 1196    {
 1197  1 if ( values == null )
 1198    {
 1199  1 values = new Values( this );
 1200    }
 1201  1 return values;
 1202    }
 1203   
 1204    /**
 1205    * Creates a values iterator. Subclasses can override this to return
 1206    * iterators with different properties.
 1207    *
 1208    * @return the values iterator
 1209    */
 1210  1 protected Iterator createValuesIterator()
 1211    {
 1212  1 if ( size( ) == 0 )
 1213    {
 1214  0 return Collections.EMPTY_MAP.keySet().iterator();
 1215    }
 1216  1 return new ValuesIterator( this );
 1217    }
 1218   
 1219    /**
 1220    * Values implementation.
 1221    */
 1222    protected static class Values extends AbstractCollection
 1223    {
 1224    /** The parent map */
 1225    protected final AbstractHashedMap parent;
 1226   
 1227  1 protected Values(AbstractHashedMap parent)
 1228    {
 1229  1 super( );
 1230  1 this.parent = parent;
 1231    }
 1232   
 1233  2 public int size()
 1234    {
 1235  2 return parent.size( );
 1236    }
 1237   
 1238  0 public void clear()
 1239    {
 1240  0 parent.clear( );
 1241    }
 1242   
 1243  0 public boolean contains(Object value)
 1244    {
 1245  0 return parent.containsValue( value );
 1246    }
 1247   
 1248  1 public Iterator iterator()
 1249    {
 1250  1 return parent.createValuesIterator( );
 1251    }
 1252    }
 1253   
 1254    /**
 1255    * Values iterator.
 1256    */
 1257    protected static class ValuesIterator extends HashIterator
 1258    {
 1259   
 1260  1 protected ValuesIterator(AbstractHashedMap parent)
 1261    {
 1262  1 super( parent );
 1263    }
 1264   
 1265  2 public Object next()
 1266    {
 1267  2 return super.nextEntry( ).getValue( );
 1268    }
 1269    }
 1270   
 1271    // -----------------------------------------------------------------------
 1272    /**
 1273    * HashEntry used to store the data.
 1274    * <p>
 1275    * If you subclass <code>AbstractHashedMap</code> but not
 1276    * <code>HashEntry</code> then you will not be able to access the
 1277    * protected fields. The <code>entryXxx()</code> methods on
 1278    * <code>AbstractHashedMap</code> exist to provide the necessary access.
 1279    */
 1280    protected static class HashEntry
 1281    implements
 1282    Map.Entry
 1283    {
 1284    /** The next entry in the hash chain */
 1285    protected HashEntry next;
 1286    /** The hash code of the key */
 1287    protected int hashCode;
 1288    /** The key */
 1289    protected Object key;
 1290    /** The value */
 1291    protected Object value;
 1292   
 1293  1337 protected HashEntry(HashEntry next,
 1294    int hashCode,
 1295    Object key,
 1296    Object value)
 1297    {
 1298  1337 super( );
 1299  1337 this.next = next;
 1300  1337 this.hashCode = hashCode;
 1301  1337 this.key = key;
 1302  1337 this.value = value;
 1303    }
 1304   
 1305  144 public Object getKey()
 1306    {
 1307  144 return (key == NULL ? null : key);
 1308    }
 1309   
 1310  878 public Object getValue()
 1311    {
 1312  878 return value;
 1313    }
 1314   
 1315  0 public Object setValue(Object value)
 1316    {
 1317  0 Object old = this.value;
 1318  0 this.value = value;
 1319  0 return old;
 1320    }
 1321   
 1322  0 public boolean equals(Object obj)
 1323    {
 1324  0 if ( obj == this )
 1325    {
 1326  0 return true;
 1327    }
 1328  0 if ( obj instanceof Map.Entry == false )
 1329    {
 1330  0 return false;
 1331    }
 1332  0 Map.Entry other = (Map.Entry) obj;
 1333  0 return (getKey( ) == null ? other.getKey( ) == null : getKey( ).equals( other.getKey( ) )) && (getValue( ) == null ? other.getValue( ) == null : getValue( ).equals( other.getValue( ) ));
 1334    }
 1335   
 1336  0 public int hashCode()
 1337    {
 1338  0 return (getKey( ) == null ? 0 : getKey( ).hashCode( )) ^ (getValue( ) == null ? 0 : getValue( ).hashCode( ));
 1339    }
 1340   
 1341  0 public String toString()
 1342    {
 1343  0 return new StringBuffer( ).append( getKey( ) ).append( '=' ).append( getValue( ) ).toString( );
 1344    }
 1345    }
 1346   
 1347    /**
 1348    * Base Iterator
 1349    */
 1350    protected static abstract class HashIterator
 1351    implements
 1352    Iterator
 1353    {
 1354   
 1355    /** The parent map */
 1356    protected final AbstractHashedMap parent;
 1357    /** The current index into the array of buckets */
 1358    protected int hashIndex;
 1359    /** The last returned entry */
 1360    protected HashEntry last;
 1361    /** The next entry */
 1362    protected HashEntry next;
 1363    /** The modification count expected */
 1364    protected int expectedModCount;
 1365   
 1366  11 protected HashIterator(AbstractHashedMap parent)
 1367    {
 1368  11 super( );
 1369  11 this.parent = parent;
 1370  11 HashEntry[] data = parent.data;
 1371  11 int i = data.length;
 1372  11 HashEntry next = null;
 1373  11 while ( i > 0 && next == null )
 1374    {
 1375  142 next = data[--i];
 1376    }
 1377  11 this.next = next;
 1378  11 this.hashIndex = i;
 1379  11 this.expectedModCount = parent.modCount;
 1380    }
 1381   
 1382  154 public boolean hasNext()
 1383    {
 1384  154 return (next != null);
 1385    }
 1386   
 1387  146 protected HashEntry nextEntry()
 1388    {
 1389  146 if ( parent.modCount != expectedModCount )
 1390    {
 1391  0 throw new ConcurrentModificationException( );
 1392    }
 1393  146 HashEntry newCurrent = next;
 1394  146 if ( newCurrent == null )
 1395    {
 1396  0 throw new NoSuchElementException( AbstractHashedMap.NO_NEXT_ENTRY );
 1397    }
 1398  146 HashEntry[] data = parent.data;
 1399  146 int i = hashIndex;
 1400  146 HashEntry n = newCurrent.next;
 1401  146 while ( n == null && i > 0 )
 1402    {
 1403  834 n = data[--i];
 1404    }
 1405  146 next = n;
 1406  146 hashIndex = i;
 1407  146 last = newCurrent;
 1408  146 return newCurrent;
 1409    }
 1410   
 1411  144 protected HashEntry currentEntry()
 1412    {
 1413  144 return last;
 1414    }
 1415   
 1416  0 public void remove()
 1417    {
 1418  0 if ( last == null )
 1419    {
 1420  0 throw new IllegalStateException( AbstractHashedMap.REMOVE_INVALID );
 1421    }
 1422  0 if ( parent.modCount != expectedModCount )
 1423    {
 1424  0 throw new ConcurrentModificationException( );
 1425    }
 1426  0 parent.remove( last.getKey( ) );
 1427  0 last = null;
 1428  0 expectedModCount = parent.modCount;
 1429    }
 1430   
 1431  0 public String toString()
 1432    {
 1433  0 if ( last != null )
 1434    {
 1435  0 return "Iterator[" + last.getKey( ) + "=" + last.getValue( ) + "]";
 1436    }
 1437    else
 1438    {
 1439  0 return "Iterator[]";
 1440    }
 1441    }
 1442    }
 1443   
 1444    // -----------------------------------------------------------------------
 1445    /**
 1446    * Writes the map data to the stream. This method must be overridden if a
 1447    * subclass must be setup before <code>put()</code> is used.
 1448    * <p>
 1449    * Serialization is not one of the JDK's nicest topics. Normal serialization
 1450    * will initialise the superclass before the subclass. Sometimes however,
 1451    * this isn't what you want, as in this case the <code>put()</code> method
 1452    * on read can be affected by subclass state.
 1453    * <p>
 1454    * The solution adopted here is to serialize the state data of this class in
 1455    * this protected method. This method must be called by the
 1456    * <code>writeObject()</code> of the first serializable subclass.
 1457    * <p>
 1458    * Subclasses may override if they have a specific field that must be
 1459    * present on read before this implementation will work. Generally, the read
 1460    * determines what must be serialized here, if anything.
 1461    *
 1462    * @param out
 1463    * the output stream
 1464    */
 1465  15 protected void doWriteObject(ObjectOutputStream out) throws IOException
 1466    {
 1467  15 out.writeFloat( loadFactor );
 1468  15 out.writeInt( data.length );
 1469  15 out.writeInt( size );
 1470  15 for ( MapIterator it = mapIterator( ); it.hasNext( ); )
 1471    {
 1472  144 out.writeObject( it.next( ) );
 1473  144 out.writeObject( it.getValue( ) );
 1474    }
 1475    }
 1476   
 1477    /**
 1478    * Reads the map data from the stream. This method must be overridden if a
 1479    * subclass must be setup before <code>put()</code> is used.
 1480    * <p>
 1481    * Serialization is not one of the JDK's nicest topics. Normal serialization
 1482    * will initialise the superclass before the subclass. Sometimes however,
 1483    * this isn't what you want, as in this case the <code>put()</code> method
 1484    * on read can be affected by subclass state.
 1485    * <p>
 1486    * The solution adopted here is to deserialize the state data of this class
 1487    * in this protected method. This method must be called by the
 1488    * <code>readObject()</code> of the first serializable subclass.
 1489    * <p>
 1490    * Subclasses may override if the subclass has a specific field that must be
 1491    * present before <code>put()</code> or <code>calculateThreshold()</code>
 1492    * will work correctly.
 1493    *
 1494    * @param in
 1495    * the input stream
 1496    */
 1497  15 protected void doReadObject(ObjectInputStream in) throws IOException,
 1498    ClassNotFoundException
 1499    {
 1500  15 loadFactor = in.readFloat( );
 1501  15 int capacity = in.readInt( );
 1502  15 int size = in.readInt( );
 1503  15 init( );
 1504  15 data = new HashEntry[capacity];
 1505  15 for ( int i = 0; i < size; i++ )
 1506    {
 1507  144 Object key = in.readObject( );
 1508  144 Object value = in.readObject( );
 1509  144 put( key,
 1510    value );
 1511    }
 1512  15 threshold = calculateThreshold( data.length,
 1513    loadFactor );
 1514    }
 1515   
 1516    // -----------------------------------------------------------------------
 1517    /**
 1518    * Clones the map without cloning the keys or values.
 1519    * <p>
 1520    * To implement <code>clone()</code>, a subclass must implement the
 1521    * <code>Cloneable</code> interface and make this method public.
 1522    *
 1523    * @return a shallow clone
 1524    */
 1525  0 protected Object clone()
 1526    {
 1527  0 try
 1528    {
 1529  0 AbstractHashedMap cloned = (AbstractHashedMap) super.clone( );
 1530  0 cloned.data = new HashEntry[data.length];
 1531  0 cloned.entrySet = null;
 1532  0 cloned.keySet = null;
 1533  0 cloned.values = null;
 1534  0 cloned.modCount = 0;
 1535  0 cloned.size = 0;
 1536  0 cloned.init( );
 1537  0 cloned.putAll( this );
 1538  0 return cloned;
 1539   
 1540    }
 1541    catch ( CloneNotSupportedException ex )
 1542    {
 1543  0 return null; // should never happen
 1544    }
 1545    }
 1546   
 1547    /**
 1548    * Compares this map with another.
 1549    *
 1550    * @param obj
 1551    * the object to compare to
 1552    * @return true if equal
 1553    */
 1554  0 public boolean equals(Object obj)
 1555    {
 1556  0 if ( obj == this )
 1557    {
 1558  0 return true;
 1559    }
 1560  0 if ( obj instanceof Map == false )
 1561    {
 1562  0 return false;
 1563    }
 1564  0 Map map = (Map) obj;
 1565  0 if ( map.size( ) != size( ) )
 1566    {
 1567  0 return false;
 1568    }
 1569  0 MapIterator it = mapIterator( );
 1570  0 try
 1571    {
 1572  0 while ( it.hasNext( ) )
 1573    {
 1574  0 Object key = it.next( );
 1575  0 Object value = it.getValue( );
 1576  0 if ( value == null )
 1577    {
 1578  0 if ( map.get( key ) != null || map.containsKey( key ) == false )
 1579    {
 1580  0 return false;
 1581    }
 1582    }
 1583    else
 1584    {
 1585  0 if ( value.equals( map.get( key ) ) == false )
 1586    {
 1587  0 return false;
 1588    }
 1589    }
 1590    }
 1591    }
 1592    catch ( ClassCastException ignored )
 1593    {
 1594  0 return false;
 1595    }
 1596    catch ( NullPointerException ignored )
 1597    {
 1598  0 return false;
 1599    }
 1600  0 return true;
 1601    }
 1602   
 1603    /**
 1604    * Gets the standard Map hashCode.
 1605    *
 1606    * @return the hash code defined in the Map interface
 1607    */
 1608  0 public int hashCode()
 1609    {
 1610  0 int total = 0;
 1611  0 Iterator it = createEntrySetIterator( );
 1612  0 while ( it.hasNext( ) )
 1613    {
 1614  0 total += it.next( ).hashCode( );
 1615    }
 1616  0 return total;
 1617    }
 1618   
 1619    /**
 1620    * Gets the map as a String.
 1621    *
 1622    * @return a string version of the map
 1623    */
 1624  0 public String toString()
 1625    {
 1626  0 if ( size( ) == 0 )
 1627    {
 1628  0 return "{}";
 1629    }
 1630  0 StringBuffer buf = new StringBuffer( 32 * size( ) );
 1631  0 buf.append( '{' );
 1632   
 1633  0 MapIterator it = mapIterator( );
 1634  0 boolean hasNext = it.hasNext( );
 1635  0 while ( hasNext )
 1636    {
 1637  0 Object key = it.next( );
 1638  0 Object value = it.getValue( );
 1639  0 buf.append( key == this ? "(this Map)" : key ).append( '=' ).append( value == this ? "(this Map)" : value );
 1640   
 1641  0 hasNext = it.hasNext( );
 1642  0 if ( hasNext )
 1643    {
 1644  0 buf.append( ',' ).append( ' ' );
 1645    }
 1646    }
 1647   
 1648  0 buf.append( '}' );
 1649  0 return buf.toString( );
 1650    }
 1651    }