content: ///////////////////////////////////////////////////////////////////////////////
  // Copyright (c) 2009, Rob Eden All Rights Reserved.
  //
  // This library is free software; you can redistribute it and/or
  // modify it under the terms of the GNU Lesser General Public
  // License as published by the Free Software Foundation; either
  // version 2.1 of the License, or (at your option) any later version.
  //
  // This library is distributed in the hope that it will be useful,
  // but WITHOUT ANY WARRANTY; without even the implied warranty of
  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  // GNU General Public License for more details.
  //
  // You should have received a copy of the GNU Lesser General Public
  // License along with this program; if not, write to the Free Software
  // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  ///////////////////////////////////////////////////////////////////////////////
  
  package gnu.trove.map.hash;
  
  import gnu.trove.function.TObjectFunction;
  import gnu.trove.impl.HashFunctions;
  import gnu.trove.impl.hash.TCustomObjectHash;
  import gnu.trove.iterator.hash.TObjectHashIterator;
  import gnu.trove.map.TMap;
  import gnu.trove.procedure.TObjectObjectProcedure;
  import gnu.trove.procedure.TObjectProcedure;
  import gnu.trove.strategy.HashingStrategy;
  
  import java.io.Externalizable;
  import java.io.IOException;
  import java.io.ObjectInput;
  import java.io.ObjectOutput;
  import java.util.*;
  
  
  
  /**
   * An implementation of the Map interface which uses an open addressed
   * hash table to store its contents.
   *
   * @author Rob Eden
   */
  public class TCustomHashMap<K, V> extends TCustomObjectHash<K>
  	implements TMap<K, V>, Externalizable {
  
      static final long serialVersionUID = 1L;
  
      /** the values of the  map */
      protected transient V[] _values;
  
  	/** FOR EXTERNALIZATION ONLY!!! */
  	public TCustomHashMap() {
  		super();
  	}
  
  
      /**
       * Creates a new <code>TCustomHashMap</code> instance with the default
       * capacity and load factor.
       */
      public TCustomHashMap( HashingStrategy<? super K> strategy ) {
          super( strategy );
      }
  
  
      /**
       * Creates a new <code>TCustomHashMap</code> instance with a prime
       * capacity equal to or greater than <tt>initialCapacity</tt> and
       * with the default load factor.
       *
       * @param initialCapacity an <code>int</code> value
       */
      public TCustomHashMap( HashingStrategy<? super K> strategy, int initialCapacity ) {
          super( strategy, initialCapacity );
      }
  
  
      /**
       * Creates a new <code>TCustomHashMap</code> instance with a prime
       * capacity equal to or greater than <tt>initialCapacity</tt> and
       * with the specified load factor.
       *
       * @param initialCapacity an <code>int</code> value
       * @param loadFactor      a <code>float</code> value
       */
      public TCustomHashMap( HashingStrategy<? super K> strategy, int initialCapacity,
  	    float loadFactor ) {
  
          super( strategy, initialCapacity, loadFactor );
      }
  
  
      /**
       * Creates a new <code>TCustomHashMap</code> instance which contains the
       * key/value pairs in <tt>map</tt>.
       *
       * @param map a <code>Map</code> value
       */
      public TCustomHashMap( HashingStrategy<? super K> strategy,
  	    Map<? extends K, ? extends V> map ) {
  
          this( strategy, map.size() );
          putAll( map );
      }
  
  
      /**
       * Creates a new <code>TCustomHashMap</code> instance which contains the
       * key/value pairs in <tt>map</tt>.
       *
       * @param map a <code>Map</code> value
       */
      public TCustomHashMap( HashingStrategy<? super K> strategy,
  	    TCustomHashMap<? extends K, ? extends V> map ) {
  
          this( strategy, map.size() );
          putAll( map );
      }
  
  
      /**
       * initialize the value array of the map.
       *
       * @param initialCapacity an <code>int</code> value
       * @return an <code>int</code> value
       */
      public int setUp( int initialCapacity ) {
          int capacity;
  
          capacity = super.setUp( initialCapacity );
          //noinspection unchecked
          _values = (V[]) new Object[capacity];
          return capacity;
      }
  
  
      /**
       * Inserts a key/value pair into the map.
       *
       * @param key   an <code>Object</code> value
       * @param value an <code>Object</code> value
       * @return the previous value associated with <tt>key</tt>,
       *         or {@code null} if none was found.
       */
      public V put( K key, V value ) {
          int index = insertKey( key );
          return doPut( value, index );
      }
  
  
      /**
       * Inserts a key/value pair into the map if the specified key is not already
       * associated with a value.
       *
       * @param key   an <code>Object</code> value
       * @param value an <code>Object</code> value
       * @return the previous value associated with <tt>key</tt>,
       *         or {@code null} if none was found.
       */
      public V putIfAbsent( K key, V value ) {
          int index = insertKey( key );
          if ( index < 0 ) {
              return _values[-index - 1];
          }
          return doPut(value, index );
      }
  
  
      private V doPut( V value, int index ) {
          V previous = null;
          boolean isNewMapping = true;
          if ( index < 0 ) {
              index = -index - 1;
              previous = _values[index];
              isNewMapping = false;
          }
  
          _values[index] = value;
  
          if ( isNewMapping ) {
              postInsertHook( consumeFreeSlot );
          }
  
          return previous;
      }
  
  
      /**
       * Compares this map with another map for equality of their stored
       * entries.
       *
       * @param other an <code>Object</code> value
       * @return a <code>boolean</code> value
       */
      @SuppressWarnings({"unchecked", "SimplifiableIfStatement"})
      public boolean equals( Object other ) {
          if ( !( other instanceof Map ) ) {
              return false;
          }
          Map<K, V> that = (Map<K, V>) other;
          if ( that.size() != this.size() ) {
              return false;
          }
          return forEachEntry( new EqProcedure<K, V>( that ) );
      }
  
  
      public int hashCode() {
          HashProcedure p = new HashProcedure();
          forEachEntry( p );
          return p.getHashCode();
      }
  
  
      public String toString() {
          final StringBuilder buf = new StringBuilder( "{" );
          forEachEntry( new TObjectObjectProcedure<K, V>() {
              private boolean first = true;
  
  
              public boolean execute( K key, V value ) {
                  if ( first ) {
                      first = false;
                  } else {
                      buf.append( ", " );
                  }
  
                  buf.append( key );
                  buf.append( "=" );
                  buf.append( value );
                  return true;
              }
          } );
          buf.append( "}" );
          return buf.toString();
      }
  
  
      private final class HashProcedure implements TObjectObjectProcedure<K, V> {
          private int h = 0;
  
          public int getHashCode() {
              return h;
          }
  
          public final boolean execute( K key, V value ) {
              h += HashFunctions.hash( key ) ^ ( value == null ? 0 : value.hashCode() );
              return true;
          }
      }
  
      private static final class EqProcedure<K, V> implements TObjectObjectProcedure<K, V> {
          private final Map<K, V> _otherMap;
  
  
          EqProcedure( Map<K, V> otherMap ) {
              _otherMap = otherMap;
          }
  
  
          public final boolean execute( K key, V value ) {
              // Check to make sure the key is there. This avoids problems that come up with
              // null values. Since it is only caused in that cause, only do this when the
              // value is null (to avoid extra work).
              if ( value == null && !_otherMap.containsKey( key ) ) {
                  return false;
              }
  
              V oValue = _otherMap.get( key );
              return oValue == value || ( oValue != null && oValue.equals( value ) );
          }
      }
  
  
      /**
       * Executes <tt>procedure</tt> for each key in the map.
       *
       * @param procedure a <code>TObjectProcedure</code> value
       * @return false if the loop over the keys terminated because
       *         the procedure returned false for some key.
       */
      public boolean forEachKey( TObjectProcedure<? super K> procedure ) {
          return forEach( procedure );
      }
  
  
      /**
       * Executes <tt>procedure</tt> for each value in the map.
       *
       * @param procedure a <code>TObjectProcedure</code> value
       * @return false if the loop over the values terminated because
       *         the procedure returned false for some value.
       */
      public boolean forEachValue( TObjectProcedure<? super V> procedure ) {
          V[] values = _values;
          Object[] set = _set;
          for ( int i = values.length; i-- > 0; ) {
              if ( set[i] != FREE
                   && set[i] != REMOVED
                   && !procedure.execute( values[i] ) ) {
                  return false;
              }
          }
          return true;
      }
  
  
      /**
       * Executes <tt>procedure</tt> for each key/value entry in the
       * map.
       *
       * @param procedure a <code>TObjectObjectProcedure</code> value
       * @return false if the loop over the entries terminated because
       *         the procedure returned false for some entry.
       */
      @SuppressWarnings({"unchecked"})
      public boolean forEachEntry( TObjectObjectProcedure<? super K, ? super V> procedure ) {
          Object[] keys = _set;
          V[] values = _values;
          for ( int i = keys.length; i-- > 0; ) {
              if ( keys[i] != FREE
                   && keys[i] != REMOVED
                   && !procedure.execute( (K) keys[i], values[i] ) ) {
                  return false;
              }
          }
          return true;
      }
  
  
      /**
       * Retains only those entries in the map for which the procedure
       * returns a true value.
       *
       * @param procedure determines which entries to keep
       * @return true if the map was modified.
       */
      @SuppressWarnings({"unchecked"})
      public boolean retainEntries( TObjectObjectProcedure<? super K, ? super V> procedure ) {
          boolean modified = false;
          Object[] keys = _set;
          V[] values = _values;
  
          // Temporarily disable compaction. This is a fix for bug #1738760
          tempDisableAutoCompaction();
          try {
              for ( int i = keys.length; i-- > 0; ) {
                  if ( keys[i] != FREE
                       && keys[i] != REMOVED
                       && !procedure.execute( (K) keys[i], values[i] ) ) {
                      removeAt( i );
                      modified = true;
                  }
              }
          }
          finally {
              reenableAutoCompaction( true );
          }
  
          return modified;
      }
  
  
      /**
       * Transform the values in this map using <tt>function</tt>.
       *
       * @param function a <code>TObjectFunction</code> value
       */
      public void transformValues( TObjectFunction<V, V> function ) {
          V[] values = _values;
          Object[] set = _set;
          for ( int i = values.length; i-- > 0; ) {
              if ( set[i] != FREE && set[i] != REMOVED ) {
                  values[i] = function.execute( values[i] );
              }
          }
      }
  
  
      /**
       * rehashes the map to the new capacity.
       *
       * @param newCapacity an <code>int</code> value
       */
      @SuppressWarnings({"unchecked"})
      protected void rehash( int newCapacity ) {
          int oldCapacity = _set.length;
          int oldSize = size();
          Object oldKeys[] = _set;
          V oldVals[] = _values;
  
          _set = new Object[ newCapacity ];
          Arrays.fill( _set, FREE );
          _values = ( V[] ) new Object[ newCapacity ];
  
  		// Process entries from the old array, skipping free and removed slots. Put the
  		// values into the appropriate place in the new array.
          for ( int i = oldCapacity; i-- > 0; ) {
              Object o = oldKeys[ i ];
              if ( o == FREE || o == REMOVED ) continue;
  
  			int index = insertKey( ( K ) o );
  			if ( index < 0 ) {
  				throwObjectContractViolation( _set[ ( -index - 1 ) ], o, size(), oldSize, oldKeys);
  			}
  			_values[ index ] = oldVals[ i ];
          }
      }
  
  
      /**
       * retrieves the value for <tt>key</tt>
       *
       * @param key an <code>Object</code> value
       * @return the value of <tt>key</tt> or null if no such mapping exists.
       */
      @SuppressWarnings({"unchecked"})
      public V get( Object key ) {
          int index = index( key );
          if ( index < 0 || ! strategy.equals( ( K ) _set[index], ( K ) key  ) ) {
              return null;
          }
          return _values[index];
      }
  
  
      /** Empties the map. */
      public void clear() {
          if ( size() == 0 ) {
              return; // optimization
          }
  
          super.clear();
  
          Arrays.fill( _set, 0, _set.length, FREE );
          Arrays.fill( _values, 0, _values.length, null );
      }
  
  
      /**
       * Deletes a key/value pair from the map.
       *
       * @param key an <code>Object</code> value
       * @return an <code>Object</code> value
       */
      @SuppressWarnings({"unchecked"})
      public V remove( Object key ) {
          V prev = null;
          int index = index( key );
          if ( index >= 0 ) {
              prev = _values[index];
              removeAt( index );    // clear key,state; adjust size
          }
          return prev;
      }
  
  
      /**
       * removes the mapping at <tt>index</tt> from the map.
       *
       * @param index an <code>int</code> value
       */
      public void removeAt( int index ) {
          _values[index] = null;
          super.removeAt( index );  // clear key, state; adjust size
      }
  
  
      /**
       * Returns a view on the values of the map.
       *
       * @return a <code>Collection</code> value
       */
      public Collection<V> values() {
          return new ValueView();
      }
  
  
      /**
       * returns a Set view on the keys of the map.
       *
       * @return a <code>Set</code> value
       */
      public Set<K> keySet() {
          return new KeyView();
      }
  
  
      /**
       * Returns a Set view on the entries of the map.
       *
       * @return a <code>Set</code> value
       */
      public Set<Map.Entry<K, V>> entrySet() {
          return new EntryView();
      }
  
  
      /**
       * checks for the presence of <tt>val</tt> in the values of the map.
       *
       * @param val an <code>Object</code> value
       * @return a <code>boolean</code> value
       */
      public boolean containsValue( Object val ) {
          Object[] set = _set;
          V[] vals = _values;
  
          // special case null values so that we don't have to
          // perform null checks before every call to equals()
          if ( null == val ) {
              for ( int i = vals.length; i-- > 0; ) {
                  if ( ( set[i] != FREE && set[i] != REMOVED ) &&
                       val == vals[i] ) {
                      return true;
                  }
              }
          } else {
              for ( int i = vals.length; i-- > 0; ) {
                  if ( ( set[i] != FREE && set[i] != REMOVED ) &&
                       ( val == vals[i] || strategy.equals( ( K ) val, ( K ) vals[i] ) ) ) {
                      return true;
                  }
              }
          } // end of else
          return false;
      }
  
  
      /**
       * checks for the present of <tt>key</tt> in the keys of the map.
       *
       * @param key an <code>Object</code> value
       * @return a <code>boolean</code> value
       */
      public boolean containsKey( Object key ) {
          return contains( key );
      }
  
  
      /**
       * copies the key/value mappings in <tt>map</tt> into this map.
       *
       * @param map a <code>Map</code> value
       */
      public void putAll( Map<? extends K, ? extends V> map ) {
          ensureCapacity( map.size() );
          // could optimize this for cases when map instanceof TCustomHashMap
          for ( Map.Entry<? extends K, ? extends V> e : map.entrySet() ) {
              put( e.getKey(), e.getValue() );
          }
      }
  
  
      /** a view onto the values of the map. */
      protected class ValueView extends MapBackedView<V> {
  
          @SuppressWarnings({"unchecked"})
          public Iterator<V> iterator() {
              return new TObjectHashIterator( TCustomHashMap.this ) {
                  protected V objectAtIndex( int index ) {
                      return _values[index];
                  }
              };
          }
  
  
          public boolean containsElement( V value ) {
              return containsValue( value );
          }
  
  
          public boolean removeElement( V value ) {
              Object[] values = _values;
              Object[] set = _set;
  
              for ( int i = values.length; i-- > 0; ) {
                  if ( ( set[i] != FREE && set[i] != REMOVED ) &&
                       value == values[i] ||
                       ( null != values[i] && strategy.equals( ( K ) values[i], ( K ) value ) ) ) {
  
                      removeAt( i );
                      return true;
                  }
              }
  
              return false;
          }
      }
  
      /** a view onto the entries of the map. */
      protected class EntryView extends MapBackedView<Map.Entry<K, V>> {
  
          private final class EntryIterator extends TObjectHashIterator {
  
              EntryIterator( TCustomHashMap<K, V> map ) {
                  super( map );
              }
  
  
              @SuppressWarnings({"unchecked"})
              public Entry objectAtIndex( final int index ) {
                  return new Entry( (K) _set[index], _values[index], index );
              }
          }
  
  
          @SuppressWarnings({"unchecked"})
          public Iterator<Map.Entry<K, V>> iterator() {
              return new EntryIterator( TCustomHashMap.this );
          }
  
  
          public boolean removeElement( Map.Entry<K, V> entry ) {
              // have to effectively reimplement Map.remove here
              // because we need to return true/false depending on
              // whether the removal took place.  Since the Entry's
              // value can be null, this means that we can't rely
              // on the value of the object returned by Map.remove()
              // to determine whether a deletion actually happened.
              //
              // Note also that the deletion is only legal if
              // both the key and the value match.
              Object val;
              int index;
  
              K key = keyForEntry( entry );
              index = index( key );
              if ( index >= 0 ) {
                  val = valueForEntry( entry );
                  if ( val == _values[index] ||
                       ( null != val && strategy.equals( ( K ) val, ( K ) _values[index] ) ) ) {
                      removeAt( index );    // clear key,state; adjust size
                      return true;
                  }
              }
              return false;
          }
  
  
          public boolean containsElement( Map.Entry<K, V> entry ) {
              Object val = get( keyForEntry( entry ) );
              Object entryValue = entry.getValue();
              return entryValue == val ||
                     ( null != val && strategy.equals( ( K ) val, ( K ) entryValue ) );
          }
  
  
          protected V valueForEntry( Map.Entry<K, V> entry ) {
              return entry.getValue();
          }
  
  
          protected K keyForEntry( Map.Entry<K, V> entry ) {
              return entry.getKey();
          }
      }
  
      private abstract class MapBackedView<E> extends AbstractSet<E>
              implements Set<E>, Iterable<E> {
  
          public abstract Iterator<E> iterator();
  
  
          public abstract boolean removeElement( E key );
  
  
          public abstract boolean containsElement( E key );
  
  
          @SuppressWarnings({"unchecked"})
          public boolean contains( Object key ) {
              return containsElement( (E) key );
          }
  
  
          @SuppressWarnings({"unchecked"})
          public boolean remove( Object o ) {
              return removeElement( (E) o );
          }
  
  
  //        public boolean containsAll( Collection<?> collection ) {
  //            for ( Object element : collection ) {
  //                if ( !contains( element ) ) {
  //                    return false;
  //                }
  //            }
  //            return true;
  //        }
  
  
          public void clear() {
              TCustomHashMap.this.clear();
          }
  
  
          public boolean add( E obj ) {
              throw new UnsupportedOperationException();
          }
  
  
          public int size() {
              return TCustomHashMap.this.size();
          }
  
  
          public Object[] toArray() {
              Object[] result = new Object[size()];
              Iterator<E> e = iterator();
              for ( int i = 0; e.hasNext(); i++ ) {
                  result[i] = e.next();
              }
              return result;
          }
  
  
          @SuppressWarnings({"unchecked"})
          public <T> T[] toArray( T[] a ) {
              int size = size();
              if ( a.length < size ) {
                  a = (T[]) java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size );
              }
  
              Iterator<E> it = iterator();
              Object[] result = a;
              for ( int i = 0; i < size; i++ ) {
                  result[i] = it.next();
              }
  
              if ( a.length > size ) {
                  a[size] = null;
              }
  
              return a;
          }
  
  
          public boolean isEmpty() {
              return TCustomHashMap.this.isEmpty();
          }
  
  
          public boolean addAll( Collection<? extends E> collection ) {
              throw new UnsupportedOperationException();
          }
  
  
          @SuppressWarnings({"SuspiciousMethodCalls"})
          public boolean retainAll( Collection<?> collection ) {
              boolean changed = false;
              Iterator<E> i = iterator();
              while ( i.hasNext() ) {
                  if ( !collection.contains( i.next() ) ) {
                      i.remove();
                      changed = true;
                  }
              }
              return changed;
          }
  
  		public String toString() {
  			Iterator<E> i = iterator();
  			if ( !i.hasNext() ) return "{}";
  
  			StringBuilder sb = new StringBuilder();
  			sb.append( '{' );
  			for (; ; ) {
  				E e = i.next();
  				sb.append( e == this ? "(this Collection)" : e );
  				if ( !i.hasNext() ) return sb.append( '}' ).toString();
  				sb.append( ", " );
  			}
  		}
      }
  
      /** a view onto the keys of the map. */
      protected class KeyView extends MapBackedView<K> {
  
          @SuppressWarnings({"unchecked"})
          public Iterator<K> iterator() {
              return new TObjectHashIterator( TCustomHashMap.this );
          }
  
  
          public boolean removeElement( K key ) {
              return null != TCustomHashMap.this.remove( key );
          }
  
  
          public boolean containsElement( K key ) {
              return TCustomHashMap.this.contains( key );
          }
      }
  
      final class Entry implements Map.Entry<K, V> {
  
          private K key;
          private V val;
          private final int index;
  
  
          Entry( final K key, V value, final int index ) {
              this.key = key;
              this.val = value;
              this.index = index;
          }
  
  
          public K getKey() {
              return key;
          }
  
  
          public V getValue() {
              return val;
          }
  
  
          public V setValue( V o ) {
              if ( _values[index] != val ) {
                  throw new ConcurrentModificationException();
              }
              // need to return previous value
              V retval = val;
              // update this entry's value, in case setValue is called again
              _values[index] = o;
              val = o;
              return retval;
          }
  
  
          public boolean equals( Object o ) {
              if ( o instanceof Map.Entry ) {
                  Map.Entry<K, V> e1 = this;
                  Map.Entry e2 = (Map.Entry) o;
                  return ( e1.getKey() == null ? e2.getKey() == null :
  	                strategy.equals( e1.getKey(), ( K ) e2.getKey() ) ) &&
  	                ( e1.getValue() == null ? e2.getValue() == null :
  					e1.getValue().equals( e2.getValue() ) );
              }
              return false;
          }
  
  
          public int hashCode() {
              return ( getKey() == null ? 0 : getKey().hashCode() ) ^ ( getValue() == null ? 0 : getValue().hashCode() );
          }
  
  
          @Override
          public String toString() {
              return key + "=" + val;
          }
      }
  
  
      public void writeExternal( ObjectOutput out ) throws IOException {
          // VERSION
          out.writeByte( 1 );
  
          // NOTE: Super was not written in version 0
          super.writeExternal( out );
  
          // NUMBER OF ENTRIES
          out.writeInt( _size );
  
          // ENTRIES
          for ( int i = _set.length; i-- > 0; ) {
              if ( _set[i] != REMOVED && _set[i] != FREE ) {
                  out.writeObject( _set[i] );
                  out.writeObject( _values[i] );
              }
          }
      }
  
  
      public void readExternal( ObjectInput in )
              throws IOException, ClassNotFoundException {
  
          // VERSION
          byte version = in.readByte();
  
          // NOTE: super was not written in version 0
          if ( version != 0 ) {
              super.readExternal( in );
          }
  
          // NUMBER OF ENTRIES
          int size = in.readInt();
          setUp( size );
  
          // ENTRIES
          while ( size-- > 0 ) {
              //noinspection unchecked
              K key = (K) in.readObject();
              //noinspection unchecked
              V val = (V) in.readObject();
              put( key, val );
          }
      }
  } // TCustomHashMap
  