
class HashMap {
  private KeyValuePair[] array;
  private double loadFactor;
  private int size;
  
  // used to delete entries without leaving them empty
  private static KeyValuePair DELETED = new KeyValuePair( null, null );
  
  public HashMap() {
    this( 16 );
  }
  
  public HashMap( int initialCapacity ) {
    this( initialCapacity, 0.75 );
  }
  
  public HashMap( int initialCapacity, double loadFactor ) {
    if ( initialCapacity < 1 )
      throwRuntimeError( "Error: OutOfBoundsException", "initialCapacity", "" + initialCapacity );
    
    // must be less than 1, or while-loop ind find... will not terminate if key not found!
    if ( loadFactor < 0 || 1 < loadFactor )
      throwRuntimeError( "Error: OutOfBoundsException", "loadFactor", "" + loadFactor );

    this.array = new KeyValuePair[ initialCapacity ];
    this.loadFactor = loadFactor;
    
    size = 0;
  }
  
  public HashMap( HashMap other ) {
    this( other.array.length, other.loadFactor );
    
    for ( int i=0; i<array.length; i++ )
      this.array[ i ] = other.array[ i ];

    this.size = other.size;
  }
  
  public void clear() {
    array = new KeyValuePair[ array.length ];
    
    size = 0;
  }

  // Java: Not in Java
  public int getCapacity() {
    return array.length;
  }
  
  public boolean containsKey( Object key ) {
    return get( key ) != null;
  }
  
  public boolean containsValue( Object value ) {
    for ( int i=0; i<array.length; i++ )
      if ( array[ i ] != null && array[ i ] != DELETED && array[ i ].hasValue( value ) )
        return true;

    return false;
  }
  
  public Object get( Object key ) {
    int index = findKey( key );
    
    if ( index == -1 )
      return null;
    else
      return array[ index ].getValue();
  }
  
  public boolean isEmpty() {
    return size == 0;
  }
  
  // Java: In Java the returned collection is two-way bound with the HashMap (deletions are propagated both ways).
  //       In PS there is no such binding.
  // Java: This method does not return an ArrayList in Java
  public ArrayList keySet() {
    ArrayList list = new ArrayList();

    for ( int i=0; i<array.length; i++ )
      if ( array[ i ] != null && array[ i ] != DELETED )
        list.add( array[ i ].getKey() );

    return list;
  }
  
  public Object put( Object key, Object value ) {
    int index = findKey( key );
    Object oldValue = null;

    if ( index == -1 ) {
      // new entry
      
      if ( ( (double) size + 1 ) / array.length > loadFactor )
        expand();
      
      index = findInsertPosition( array, key );
      size++;
      
    } else
      oldValue = array[ index ].getValue();
    
    array[ index ] = new KeyValuePair( key, value );
    
    return oldValue;
  }
  
  public void putAll( HashMap other ) {
    for ( int i=0; i<other.array.length; i++ ) {
      KeyValuePair pair = other.array[ i ];
      
      if ( pair != null && pair != DELETED )
        put( pair.getKey(), pair.getValue() );
    }
  }
  
  public Object remove( Object key ) {
    int index = findKey( key );
    
    if ( index == -1 )
      return null;
    
    else {
      Object value = array[ index ].getValue();
      
      array[ index ] = DELETED;
      size--;
      
      return value;
    }
  }
  
  public int size() {
    return size;
  }
  
  // Java: In Java the returned collection is two-way bound with the HashMap (deletions are propagated both ways).
  //       In PS there is no such binding.
  // Java: This method does not return an ArrayList in Java
  public ArrayList values() {
    ArrayList list = new ArrayList();

    for ( int i=0; i<array.length; i++ )
      if ( array[ i ] != null && array[ i ] != DELETED )
        list.add( array[ i ].getValue() );

    return list;
  }
  
  // returns index of a key
  private int findKey( Object key ) {
    int index = hash( array, key );
    
    while ( array[ index ] != null ) {
      if ( array[ index ] != DELETED && array[ index ].hasKey( key ) )
        return index;
      
      index = ( index + 1 ) % array.length;
    }
    
    // not found
    return -1;
  }
  
  // PRE: adding one more entry will not require a rehash
  private static int findInsertPosition( KeyValuePair[] array, Object key ) {
    int index = hash( array, key );
    
    while ( array[ index ] != null && array[ index ] != DELETED )
      index = ( index + 1 ) % array.length;
    
    return index;
  }

  private static int hash( KeyValuePair[] array, Object key ) {
    if ( key != null )
      return abs( key.hashCode() ) % array.length;
    else
      return 0;
  }
  
  // rehash
  private void expand() {
    KeyValuePair[] newArray = new KeyValuePair[ 2 * array.length ];
    
    for ( int i=0; i<array.length; i++ )
      if ( array[ i ] != null && array[ i ] != DELETED ) {
        int newIndex = findInsertPosition( newArray, array[ i ].getKey() );
        
        newArray[ newIndex ] = array[ i ];
      }
      
    array = newArray;
    // 'size' is the same
  }
  
  // not in Java
  public String toString() {
    String result = "[HashMap:";

    ArrayList elements = keySet();

    if ( size > 0 )
      for ( int i=0; i<elements.size(); i++ ) {
        result += " " + array[ findKey( elements.get( i ) ) ];

        if ( i < size - 1 )
          result += ",";
      }
    else
      result += " empty";
    
    result += "]";
    
    return result;
  }
}
