class EmptyIteratorSingleton {
    static final Iterator<Object> INSTANCE = new Iterator<Object>() {

      @Override
      public boolean hasNext() {
        return false;
      }

      @Override
      public Object next() {
        return null;
      }

      @Override
      public void remove() {
        // do nothing
      }
    };
  }

  protected static <X> Iterator<X> emptyIterator() {
    @SuppressWarnings("unchecked")
    Iterator<X> retVal = (Iterator<X>) EmptyIteratorSingleton.INSTANCE;
    return retVal;
  }

  /** Erases the contents of the current HashChain. */
  @Override
  public synchronized void clear() {
    stateCount++;
    firstItem = lastItem = null;
    map.clear();
  }

  @Override
  public synchronized void swapWith(E out, E in) {
    insertBefore(in, out);
    remove(out);
  }

  /** Adds the given object to this HashChain. */
  @Override
  public synchronized boolean add(E item) {
    addLast(item);
    return true;
  }

  /**
   * Gets all elements in the chain. There is no guarantee on sorting.
   *
   * @return All elements in the chain in an unsorted collection
   */
  @Override
  public synchronized Collection<E> getElementsUnsorted() {
    return map.keySet();
  }

  /**
   * Returns an unbacked list containing the contents of the given Chain.
   *
   * @deprecated you can use <code>new ArrayList<E>(c)</code> instead
   */
  @Deprecated
  public static <E> List<E> toList(Chain<E> c) {
    return new ArrayList<E>(c);
  }

  @Override
  public synchronized boolean follows(E someObject, E someReferenceObject) {
    Iterator<E> it;
    try {
      it = iterator(someReferenceObject);
    } catch (NoSuchElementException e) {
      // someReferenceObject not in chain.
      return false;
    }
    while (it.hasNext()) {
      if (it.next() == someObject) {
        return true;
      }
    }
    return false;
  }

  @Override
  public synchronized boolean contains(Object o) {
    return map.containsKey(o);
  }

  @Override
  public synchronized boolean containsAll(Collection<?> c) {
    for (Object next : c) {
      if (!(map.containsKey(next))) {
        return false;
      }
    }
    return true;
  }

  @Override
  public synchronized void insertAfter(E toInsert, E point) {
    if (toInsert == null) {
      throw new RuntimeException("Cannot insert a null object into a Chain!");
    }
    if (point == null) {
      throw new RuntimeException("Insertion point cannot be null!");
    }

    if (map.containsKey(toInsert)) {
      throw new RuntimeException("Chain already contains object.");
    }

    Link<E> temp = map.get(point);
    if (temp == null) {
      throw new RuntimeException("Insertion point not found in chain!");
    }

    stateCount++;

    Link<E> newLink = temp.insertAfter(toInsert);
    map.put(toInsert, newLink);
  }

  @Override
  public synchronized void insertAfter(Collection<? extends E> toInsert, E point) {
    if (toInsert == null) {
      throw new RuntimeException("Cannot insert a null Collection into a Chain!");
    }
    if (point == null) {
      throw new RuntimeException("Insertion point cannot be null!");
    }

    E previousPoint = point;
    for (E o : toInsert) {
      insertAfter(o, previousPoint);
      previousPoint = o;
    }
  }

  @Override
  public synchronized void insertAfter(List<E> toInsert, E point) {
    insertAfter((Collection<E>) toInsert, point);
  }

  @Override
  public synchronized void insertAfter(Chain<E> toInsert, E point) {
    insertAfter((Collection<E>) toInsert, point);
  }

  @Override
  public synchronized void insertBefore(E toInsert, E point) {<FILL_FUNCTION_BODY>

    if (toInsert == null) {
      throw new RuntimeException("Cannot insert a null object into a Chain!");
    }
    if (point == null) {
      throw new RuntimeException("Insertion point cannot be null!");
    }

    if (map.containsKey(toInsert)) {
      throw new RuntimeException("Chain already contains object.");
    }

    Link<E> temp = map.get(point);
    if (temp == null) {
      throw new RuntimeException("Insertion point not found in chain!");
    }
    stateCount++;

    Link<E> newLink = temp.insertBefore(toInsert);
    map.put(toInsert, newLink);
  
<methods>public boolean add(E) ,public boolean addAll(Collection<? extends E>) ,public void clear() ,public boolean contains(java.lang.Object) ,public boolean containsAll(Collection<?>) ,public boolean isEmpty() ,public abstract Iterator<E> iterator() ,public boolean remove(java.lang.Object) ,public boolean removeAll(Collection<?>) ,public boolean retainAll(Collection<?>) ,public abstract int size() ,public java.lang.Object[] toArray() ,public T[] toArray(T[]) ,public java.lang.String toString() <variables>