DLLEntry

package prog08;

import java.util.AbstractMap;
import java.util.Map;
import java.util.Map.Entry;

import prog04.DLLEntry;

import java.util.AbstractSet;
import java.util.Set;
import java.util.Iterator;

public class DLLMap<K extends Comparable<K>, V> extends AbstractMap<K, V> {

  protected class Entry implements Map.Entry<K, V> {

    K key;
    Object value;
    Entry previous, next;

    Entry(K key, Object value) {
      this.key = key;
      this.value = value;
    }

    public K getKey() {
      return key;
    }

    public V getValue() {
      return (V) value;
    }

    public V setValue(V newValue) {
      V oldValue = (V) value;
      value = newValue;
      return oldValue;
    }

    protected boolean isSkipEntry() {
      return value != null && value instanceof DLLMap.Entry;
    }

    protected Entry getEntry() {
      return (Entry) value;
    }
  }

  protected Entry first, last;

  /**
   * Starting from entry, find an Entry with key nearest to key.
   *
   * @param startAt The entry to start from.
   * @param key     The Key to be found.
   * @return Entry with key or, if not there, neighboring key in list.
   */
  protected Entry find(Entry startAt, K key) {
    if (startAt == null)
      return null;
    Entry nearest = startAt;

    // EXERCISE
    // Move nearest to the nearest key to key (same or a neighbor).
    // forwardsssssssssss
    if (nearest.getKey().compareTo(key) < 0) {
      while (nearest.getKey().compareTo(key) < 0 && nearest.next != null)
        nearest = nearest.next;
    }
    // backwardssssssssssssssssss
    else if (nearest.getKey().compareTo(key) > 0) {
      while (nearest.getKey().compareTo(key) > 0 && nearest.previous != null)
        nearest = nearest.previous;
    }
    return nearest;
    // return nearest;
    // return nearest;
  }

  public boolean containsKey(Object keyAsObject) {
    K key = (K) keyAsObject;
    Entry entry = find(first, key);
    return entry != null && entry.key.equals(key);
  }

  // like containskey() but returns the value of entry if it's there
  // otherwise turn null
  public V get(Object keyAsObject) {
    // EXERCISE
    // Look at containsKey and fix this.
    ///
    K key = (K) keyAsObject;
    Entry entry = find(last, key);

    if (entry != null && entry.getKey() == key) {
      return entry.getValue();

    }
    return null;
  }

  /**
   * Add newEntry before or after neighbor depending on the order of their Keys.
   *
   * @param neighbor The Entry to insert before or after. null if the list is
   *                 empty.
   * @param newEntry The new Entry to be inserted.
   * @return newEntry
   */

  /*
   * 1. Implement the missing part of the add method in DLLMap. Read the Javadoc.
   * It is the same idea as add in prog02.SortedDLLPD. Follow the directions. I
   * have handled updating first and last for you. Do not read or write these
   * variables in your part of the exercise. Output should look like step01.txt.
   */

  protected Entry add(Entry neighbor, Entry newEntry) {
    Entry previous = null;
    Entry next = null;

    if (neighbor != null) {
      if (neighbor.getKey().compareTo(newEntry.getKey()) >= 0) {
        next = neighbor;
        previous = neighbor.previous;
      }
      // setting previous and next
      else if (neighbor.getKey().compareTo(newEntry.getKey()) < 0) {
        previous = neighbor;
        next = neighbor.next;
      }
      // setting newEntry's previous and next
      newEntry.previous = previous;
      newEntry.next = next;
      // setting previous.next and next.previous, careful of nulls
      if (previous != null)
        previous.next = newEntry;
      if (next != null)
        next.previous = newEntry;
    }

    if (first == next)
      first = newEntry;
    if (last == previous)
      last = newEntry;

    return newEntry;
  }

//like addOrChangeEntry()
  public V put(K key, V value) {
    Entry entry = find(first, key);
    // EXERCISE
    // Look at containsKey and then fix this.
    ///
    // entry's key equals key, we update it's value
    if (entry != null && entry.getKey().equals(key)) {
      V firstOne = entry.getValue();
      entry.setValue(value);
      return firstOne;

    }
    ///
    // if it's normal we return null
    else {
      add(entry, new Entry(key, value));
      return null;
    }
  }

  /**
   * Remove Entry entry from list.
   *
   * @param entry The entry to remove.
   */
  protected void remove(Entry entry) {
    // EXERCISE
    // ONLY modify first IF entry==first. Ditto last.
    ///
    if (entry == first) {
      first = first.next;
    } else if (entry == last) {
      last = last.previous;
    } else {
      if (find(first, entry.getKey()) == entry) {
        entry.previous.next = entry.next;
        entry.next.previous = entry.previous;
      }
    }
    ///
  }

  public V remove(Object keyAsObject) {
    // EXERCISE
    // If it is not there:
    ///
    K key = (K) keyAsObject;
    Entry entry = find(first, key);
    if (entry == null || entry.key != key) {
      ///
      return null;
    }

    // Otherwise remove it and return the right thing.
    // EXERCISE
    ///
    else {
      if (entry == first && entry == last) {
        first = null;
        last = null;
      } else if (entry == first) {
        Entry placeholder = first.next;
        placeholder.previous = null;
        first = placeholder;
      } else if (entry == last && entry != first) {
        Entry placeholder = last.previous;
        placeholder.next = null;
        last = placeholder;
      } else {
        Entry previous = entry.previous;
        Entry next = entry.next;
        previous.next = next;
        next.previous = previous;
      }
      return entry.getValue();
    }
    ///
  }

  protected class Iter implements Iterator<Map.Entry<K, V>> {
    Entry next = first;

    public boolean hasNext() {
      return next != null;
    }

    public Map.Entry<K, V> next() {
      Map.Entry<K, V> ret = next;
      next = next.next;
      return ret;
    }

    public void remove() {
      throw new UnsupportedOperationException();
    }
  }

  protected class Setter extends AbstractSet<Map.Entry<K, V>> {
    public Iterator<Map.Entry<K, V>> iterator() {
      return new Iter();
    }

    public int size() {
      return DLLMap.this.size();
    }
  }

  public Set<Map.Entry<K, V>> entrySet() {
    return new Setter();
  }

  public static void main(String[] args) {
    Map<String, Integer> map = new DLLMap<String, Integer>();

    if (false) {
      map.put("Victor", 50);
      map.put("Irina", 45);
      map.put("Lisa", 47);

      for (Map.Entry<String, Integer> pair : map.entrySet())
        System.out.println(pair.getKey() + " " + pair.getValue());

      System.out.println(map.put("Irina", 55));

      for (Map.Entry<String, Integer> pair : map.entrySet())
        System.out.println(pair.getKey() + " " + pair.getValue());

      System.out.println(map.remove("Irina"));
      System.out.println(map.remove("Irina"));
      System.out.println(map.get("Irina"));

      for (Map.Entry<String, Integer> pair : map.entrySet())
        System.out.println(pair.getKey() + " " + pair.getValue());
    } else {
      String[] keys = { "Vic", "Ira", "Sue", "Zoe", "Bob", "Ann", "Moe" };
      for (int i = 0; i < keys.length; i++) {
        System.out.print("put(" + keys[i] + ", " + i + ") = ");
        System.out.println(map.put(keys[i], i));
        System.out.println(map);
        System.out.print("put(" + keys[i] + ", " + -i + ") = ");
        System.out.println(map.put(keys[i], -i));
        System.out.println(map);
        System.out.print("get(" + keys[i] + ") = ");
        System.out.println(map.get(keys[i]));
        System.out.print("remove(" + keys[i] + ") = ");
        System.out.println(map.remove(keys[i]));
        System.out.println(map);
        System.out.print("get(" + keys[i] + ") = ");
        System.out.println(map.get(keys[i]));
        System.out.print("remove(" + keys[i] + ") = ");
        System.out.println(map.remove(keys[i]));
        System.out.println(map);
        System.out.print("put(" + keys[i] + ", " + i + ") = ");
        System.out.println(map.put(keys[i], i));
        System.out.println(map);
      }
    }
  }
}