gt:         int index = index(key);
context: ///////////////////////////////////////////////////////////////////////////////
  // Copyright (c) 2001, Eric D. Friedman 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;
  
  import java.io.IOException;
  import java.io.ObjectInputStream;
  import java.io.ObjectOutputStream;
  import java.io.Serializable;
  
  /**
   * An open addressed Map implementation for double keys and Object values.
   *
   * Created: Sun Nov  4 08:52:45 2001
   *
   * @author Eric D. Friedman
   * @version $Id: TDoubleObjectHashMap.java,v 1.1 2011/07/29 09:11:48 bleaman Exp $
   */
  public class TDoubleObjectHashMap extends TDoubleHash implements Serializable {
  
      /** the values of the map */
      protected transient Object[] _values;
  
      /**
       * Creates a new <code>TDoubleObjectHashMap</code> instance with the default
       * capacity and load factor.
       */
      public TDoubleObjectHashMap() {
          super();
      }
  
      /**
       * Creates a new <code>TDoubleObjectHashMap</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 TDoubleObjectHashMap(int initialCapacity) {
          super(initialCapacity);
      }
  
      /**
       * Creates a new <code>TDoubleObjectHashMap</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 TDoubleObjectHashMap(int initialCapacity, float loadFactor) {
          super(initialCapacity, loadFactor);
      }
  
      /**
       * Creates a new <code>TDoubleObjectHashMap</code> instance with the default
       * capacity and load factor.
       * @param strategy used to compute hash codes and to compare keys.
       */
      public TDoubleObjectHashMap(TDoubleHashingStrategy strategy) {
          super(strategy);
      }
  
      /**
       * Creates a new <code>TDoubleObjectHashMap</code> instance whose capacity
       * is the next highest prime above <tt>initialCapacity + 1</tt>
       * unless that value is already prime.
       *
       * @param initialCapacity an <code>int</code> value
       * @param strategy used to compute hash codes and to compare keys.
       */
      public TDoubleObjectHashMap(int initialCapacity, TDoubleHashingStrategy strategy) {
          super(initialCapacity, strategy);
      }
  
      /**
       * Creates a new <code>TDoubleObjectHashMap</code> instance with a prime
       * value at or near the specified capacity and load factor.
       *
       * @param initialCapacity used to find a prime capacity for the table.
       * @param loadFactor used to calculate the threshold over which
       * rehashing takes place.
       * @param strategy used to compute hash codes and to compare keys.
       */
      public TDoubleObjectHashMap(int initialCapacity, float loadFactor, TDoubleHashingStrategy strategy) {
          super(initialCapacity, loadFactor, strategy);
      }
  
      /**
       * @return a deep clone of this collection
       */
      public Object clone() {
        TDoubleObjectHashMap m = (TDoubleObjectHashMap)super.clone();
        m._values = (Object[])this._values.clone();
        return m;
      }
  
      /**
       * @return a TDoubleObjectIterator with access to this map's keys and values
       */
      public TDoubleObjectIterator iterator() {
          return new TDoubleObjectIterator(this);
      }
  
      /**
       * initializes the hashtable to a prime capacity which is at least
       * <tt>initialCapacity + 1</tt>.  
       *
       * @param initialCapacity an <code>int</code> value
       * @return the actual capacity chosen
       */
      protected int setUp(int initialCapacity) {
          int capacity;
  
          capacity = super.setUp(initialCapacity);
          _values = new Object[capacity];
          return capacity;
      }
  
      /**
       * Inserts a key/value pair into the map.
       *
       * @param key an <code>double</code> value
       * @param value an <code>Object</code> value
       * @return the previous value associated with <tt>key</tt>,
       * or null if none was found.
       */
      public Object put(double key, Object value) {
          byte previousState;
          Object previous = null;
          int index = insertionIndex(key);
          boolean isNewMapping = true;
          if (index < 0) {
              index = -index -1;
              previous = _values[index];
              isNewMapping = false;
          }
          previousState = _states[index];
          _set[index] = key;
          _states[index] = FULL;
          _values[index] = value;
          if (isNewMapping) {
              postInsertHook(previousState == FREE);
          }
  
          return previous;
      }
  
      /**
       * rehashes the map to the new capacity.
       *
       * @param newCapacity an <code>int</code> value
       */
      protected void rehash(int newCapacity) {
          int oldCapacity = _set.length;
          double oldKeys[] = _set;
          Object oldVals[] = _values;
          byte oldStates[] = _states;
  
          _set = new double[newCapacity];
          _values = new Object[newCapacity];
          _states = new byte[newCapacity];
  
          for (int i = oldCapacity; i-- > 0;) {
              if(oldStates[i] == FULL) {
                  double o = oldKeys[i];
                  int index = insertionIndex(o);
                  _set[index] = o;
                  _values[index] = oldVals[i];
                  _states[index] = FULL;
              }
          }
      }
  
      /**
       * retrieves the value for <tt>key</tt>
       *
       * @param key an <code>double</code> value
       * @return the value of <tt>key</tt> or null if no such mapping exists.
       */
      public Object get(double key) {
          int index = index(key);
          return index < 0 ? null : _values[index];
      }
  
      /**
       * Empties the map.
       *
       */
      public void clear() {
          super.clear();
          double[] keys = _set;
          Object[] vals = _values;
          byte[] states = _states;
  
          for (int i = keys.length; i-- > 0;) {
              keys[i] = (double)0;
              vals[i] = null;
              states[i] = FREE;
          }
      }
  
      /**
       * Deletes a key/value pair from the map.
       *
       * @param key an <code>double</code> value
       * @return an <code>Object</code> value
       */
      public Object remove(double key) {
          Object prev = null;
  