import structure5.*;

public class MapTree<K extends Comparable<K>,V> implements Map<K,V> {
  
  protected BinarySearchTree<ComparableAssociation<K,V>> _bst = new BinarySearchTree<>();
  
  /**
   * Removes all elements in the data structure.
   */
  public void clear() {
    _bst = new BinarySearchTree<>();
  }
  
  /**
   * Returns true iff an entry with the given key is
   * stored in the map.
   *
   * @param key  The key.
   */
  public boolean containsKey(K key) {
    return get(key) != null;
  }
  
  /**
   * Returns true iff an entry with the given value
   * is stored in the map.
   */
  public boolean containsValue(V value) {
    // this is a little more work because
    // there are no guarantees about where we
    // might find the value
    for (ComparableAssociation<K,V> pair : _bst) {
      if (pair.getValue().equals(value)) {
        return true;
      }
    }
    return false;
  }
  
  /**
   * Returns a set of associations for every entry.
   */
  public Set<Association<K,V>> entrySet() {
    // we haven't discussed sets yet, but in short they're
    // unordered collections that do not store duplicate
    // values
    SetList<Association<K,V>> s = new SetList<>();
    for (ComparableAssociation<K,V> pair : _bst) {
      s.add(pair);
    }
    return s;
  }
  
  /**
   * Returns the value associated with the given key, or
   * null if there is no corresponding entry in the map.
   */
  public V get(K key) {
    // we need a key to do the search
    ComparableAssociation<K,V> a = new ComparableAssociation<>(key, null);
    ComparableAssociation<K,V> entry = _bst.get(a);
    if (entry != null) {
      return entry.getValue();
    } else {
      return null;
    }
  }
  
  /**
   * Returns true iff the data structure stores no entries.
   */
  public boolean isEmpty() {
    return _bst.size() == 0;
  }
  
  /**
   * Returns all of the keys stored in the map.
   */
  public Set<K> keySet() {
    // this is much like the entrySet method,
    // except that we only care about keys
    SetList<K> s = new SetList<>();
    for (ComparableAssociation<K,V> pair : _bst) {
      s.add(pair.getKey());
    }
    return s;
  }
  
  /**
   * Inserts the given key and value into the tree.
   * If an entry with a duplicate key already exists,
   * that entry's value is updated with the new value.
   * If an entry already exists, the old value is returned,
   * otherwise, the new value is returned.
   *
   * @param key  The key.
   * @param value  The value.
   */
  public V put(K key, V value) {
    // we need an association to do the search
    ComparableAssociation<K,V> a = new ComparableAssociation<>(key, value);
    if (_bst.contains(a)) {
      // get the value so that we can update it
      Association<K,V> oldAssoc = _bst.get(a);
      // save the old value
      V oldValue = oldAssoc.getValue();
      // update the association with the new value
      oldAssoc.setValue(value);
      // return the old value
      return oldValue;
    } else {
      // insert as new mapping
      _bst.add(a);
      return value;
    }
  }
  
  /**
   * Inserts all of the entries from other into this map,
   * updating any values where duplicate keys already exist.
   *
   * @param other  A second Map of the same type.
   */
  public void putAll(Map<K, V> other) {
    // this adds all of the elements from
    // an existing map into this map
    for (ComparableAssociation<K,V> pair : _bst) {
      put(pair.getKey(), pair.getValue());
    }
  }
  
  /**
   * Removes an entry from the map, returning the removed
   * value when successful.  If no entry is found, returns
   * null.
   *
   * @param key  The key.
   */
  public V remove(K key) {
    // we need an association to do the search
    ComparableAssociation<K,V> a = new ComparableAssociation<>(key, null);
    ComparableAssociation<K,V> rem = _bst.remove(a);
    if (rem != null) {
      return rem.getValue();
    }
    return null;
  }
  
  /**
   * Returns all of the values in the map.
   */
  public Structure<V> values() {
    // this is much like the entrySet method,
    // except that we only care about values
    SetList<V> s = new SetList<>();
    for (ComparableAssociation<K,V> pair : _bst) {
      s.add(pair.getValue());
    }
    return s;
  }
  
  /**
   * Returns the number entries stored in the map.
   */
  public int size() {
    return _bst.size();
  }
}