import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Stack;

/**
 * A tree based set which contains DNA strings. This set stores DNA strings with
 * a common prefix under the same sequence of edges in the tree. No node in the
 * tree stores the DNA string associated with that node; instead, its position
 * in the tree defines the DNA string with which it is associated. All the
 * descendants of a node have a common prefix of the DNA string associated with
 * that node, and the root is associated with the empty string. The DNA strings
 * are associated only with leaves.
 * 
 * @author Michael D. Naper, Jr. <MichaelNaper.com>
 * @version 2013.01.07
 */
public class DnaTreeSet implements Iterable<DnaString> {

  // Root node of this DNA tree
  private Node root;

  // Number of mappings in this tree
  private int size;

  /**
   * Constructs a new, empty {@code DnaTreeSet}.
   */
  public DnaTreeSet() {
    root = FlyweightNode.getInstance();
    size = 0;
  }

  /**
   * Constructs a new {@code DnaTreeSet} containing the {@link DnaString}s in
   * the specified collection.
   * 
   * @param collection
   *          The collection whose DNA strings are to be added to this set.
   */
  public DnaTreeSet(Collection<? extends DnaString> collection) {
    this();
    addAll(collection);
  }

  /**
   * Adds the specified {@link DnaString} to this set if it is not already
   * present. If this set already contains the DNA string, the call leaves the
   * set unchanged.
   * 
   * @param dnaString
   *          The DNA string to be added to this set.
   * @return {@code true} if this set did not already contain the specified DNA
   *         string.
   */
  public boolean add(DnaString dnaString) {
    if (dnaString == null) {
      throw new NullPointerException("dnaString is null.");
    }

    try {
      root = root.add(dnaString, 0);
      size++;
      return true;
    } catch (DuplicateElementException e) {
      return false;
    }
  }

  /**
   * Adds all of the {@link DnaString}s in the specified collection to this set
   * if they are not already present.
   * 
   * @param collection
   *          The collection containing DNA strings to be added to this set.
   * @return {@code true} if this set changed as a result of the call.
   */
  public boolean addAll(Collection<? extends DnaString> collection) {
    if (collection == null) {
      throw new NullPointerException("collection is null.");
    }

    // Prevent adding during concurrent modification of collection
    DnaString[] dnaStrings = collection.toArray(new DnaString[0]);

    boolean modified = false;
    for (DnaString dnaString : dnaStrings) {
      modified |= add(dnaString);
    }
    return modified;
  }

  /**
   * Returns {@code true} if this set contains the specified {@link DnaString}.
   * 
   * @param dnaString
   *          The DNA string to be checked for containment in this set.
   * @return {@code true} if this set contains the specified DNA string.
   */
  public boolean contains(DnaString dnaString) {
    if (dnaString == null) {
      throw new NullPointerException("dnaString is null.");
    }

    return root.contains(dnaString, 0);
  }

  /**
   * Returns {@code true} if this set contains all of the {@link DnaString}s of
   * the specified collection.
   * 
   * @param collection
   *          The collection to be checked for containment in this set.
   * @return {@code true} if this set contains all of the DNA strings of the
   *         specified collection.
   */
  public boolean containsAll(Collection<? extends DnaString> collection) {
    if (collection == null) {
      throw new NullPointerException("collection is null.");
    }

    // Prevent containment check during concurrent modification of collection
    DnaString[] dnaStrings = collection.toArray(new DnaString[0]);

    for (DnaString dnaString : dnaStrings) {
      if (!contains(dnaString)) {
        return false;
      }
    }
    return true;
  }

  /**
   * Returns {@code true} if this set contains a {@link DnaString} with the
   * specified prefix DNA string.
   * 
   * @param prefix
   *          The prefix DNA string.
   * @return {@code true} if this set contains a DNA string with the specified
   *         prefix DNA string.
   */
  public boolean containsPrefix(DnaString prefix) {
    if (prefix == null) {
      throw new NullPointerException("prefix is null.");
    }

    return root.containsPrefix(prefix, 0);
  }

  /**
   * Returns a collection of {@link DnaString}s contained in this set matching
   * the specified {@link DnaStringDescriptor}.
   * 
   * @param dnaStringDescriptor
   *          The DNA string descriptor against which to match.
   * @return A collection of DNA strings contained in this set matching the
   *         specified DNA string descriptor.
   */
  public Collection<DnaString> search(DnaStringDescriptor dnaStringDescriptor) {
    if (dnaStringDescriptor == null) {
      throw new NullPointerException("dnaStringDescriptor is null.");
    }

    Collection<DnaString> found = new LinkedList<>();
    root.search(dnaStringDescriptor, 0, found);
    return found;
  }

  /**
   * Returns a collection of the {@link DnaString}s contained in this set.
   * 
   * @return A collection of the DNA strings contained in this set.
   */
  public Collection<DnaString> values() {
    Collection<DnaString> collected = new LinkedList<>();
    root.collect(collected);
    return collected;
  }

  /**
   * Removes the specified {@link DnaString} from this set if it is present.
   * 
   * @param dnaString
   *          The DNA string to be removed from this set, if present.
   * @return {@code true} if this set contained the specified DNA string.
   */
  public boolean remove(DnaString dnaString) {
    if (dnaString == null) {
      throw new NullPointerException("dnaString is null.");
    }

    try {
      root = root.remove(dnaString, 0);
      size--;
      return true;
    } catch (AbsentElementException e) {
      return false;
    }
  }

  /**
   * Removes from this set all of its {@link DnaString}s that are contained in
   * the specified collection.
   * 
   * @param collection
   *          The collection containing DNA strings to be removed from this set.
   * @return {@code true} if this set changed as a result of the call.
   */
  public boolean removeAll(Collection<? extends DnaString> collection) {
    if (collection == null) {
      throw new NullPointerException("collection is null.");
    }

    // Prevent removing during concurrent modification of collection
    DnaString[] dnaStrings = collection.toArray(new DnaString[0]);

    boolean modified = false;
    for (DnaString dnaString : dnaStrings) {
      modified |= remove(dnaString);
    }
    return modified;
  }

  /**
   * Retains only the {@link DnaString}s in this set that are contained in the
   * specified collection. In other words, removes from this set all of its DNA
   * strings that are not contained in the specified collection.
   * 
   * @param collection
   *          The collection containing DNA strings to be retained in this set.
   * @return {@code true} if this set changed as a result of the call.
   */
  public boolean retainAll(Collection<? extends DnaString> collection) {
    if (collection == null) {
      throw new NullPointerException("collection is null.");
    }

    // Prevent removing during concurrent modification of collection
    List<DnaString> dnaStrings = Arrays.asList(collection
        .toArray(new DnaString[0]));

    boolean modified = false;
    for (DnaString dnaString : values()) {
      if (!dnaStrings.contains(dnaString)) {
        modified |= remove(dnaString);
      }
    }
    return modified;
  }

  /**
   * Removes all of the {@link DnaString}s from this set. The set will be empty
   * after this call returns.
   */
  public void clear() {
    root = FlyweightNode.getInstance();
    size = 0;
  }

  /**
   * Returns the number of {@link DnaString}s in this set.
   * 
   * @return The number of DNA strings in this set.
   */
  public int size() {
    return size;
  }

  /**
   * Returns {@code true} if this set contains no {@link DnaString}s.
   * 
   * @return {@code true} if this set contains no DNA strings.
   */
  public boolean isEmpty() {
    return size == 0;
  }

  @Override
  public Iterator<DnaString> iterator() {
    return new DnaTreeSetIterator();
  }

  /**
   * Returns an array containing all of the {@link DnaString}s in this set.
   * 
   * @return An array containing all the DNA strings in this set.
   */
  public DnaString[] toArray() {
    Collection<DnaString> dnaStrings = new ArrayList<>(size);
    root.collect(dnaStrings);
    return dnaStrings.toArray(new DnaString[size]);
  }

  @Override
  public String toString() {
    NodeVisitor<String> visitor = new NodeVisitor<String>() {

      private StringBuilder stringBuilder = new StringBuilder();

      @Override
      public void visit(Node node, int depth) {
        String padding = new String(new char[depth << 1]).replace('\0', ' ');
        stringBuilder.append(padding + node.toString() + "\n");
      }

      @Override
      public String result() {
        return stringBuilder.toString();
      }
    };

    root.traverse(visitor, 0);
    return visitor.result();
  }

  /**
   * Returns a string representation of this {@code DnaTreeSet} with each
   * sequence's length included along with the sequence. This representation
   * includes both the tree's node structure and the sequences it contains,
   * traversed in a pre-order fashion.
   * 
   * @return A string representation of this {@code DnaTreeSet} with each
   *         sequence's length included along with the sequence.
   */
  public String toStringWithLengths() {
    NodeVisitor<String> visitor = new NodeVisitor<String>() {

      private StringBuilder stringBuilder = new StringBuilder();

      @Override
      public void visit(Node node, int depth) {
        String padding = new String(new char[depth << 1]).replace('\0', ' ');
        stringBuilder.append(padding + node.toString());
        if (node.isLeafNode()) {
          DnaString dnaString = ((LeafNode) node).dnaString;
          stringBuilder.append(" [" + dnaString.getDnaString().length() + "]");
        }
        stringBuilder.append("\n");
      }

      @Override
      public String result() {
        return stringBuilder.toString();
      }
    };

    root.traverse(visitor, 0);
    return visitor.result();
  }

  /**
   * Returns a string representation of this {@code DnaTreeSet} with each
   * sequence's character breakdown statistics included along with the sequence.
   * This representation includes both the tree's node structure and the
   * sequences it contains, traversed in a pre-order fashion.
   * 
   * @return A string representation of this {@code DnaTreeSet} with each
   *         sequence's letter breakdown statistics included along with the
   *         sequence.
   */
  public String toStringWithStatistics() {
    NodeVisitor<String> visitor = new NodeVisitor<String>() {

      private StringBuilder stringBuilder = new StringBuilder();

      @Override
      public void visit(Node node, int depth) {
        String padding = new String(new char[depth << 1]).replace('\0', ' ');
        stringBuilder.append(padding + node.toString());
        if (node.isLeafNode()) {
          DnaString dnaString = ((LeafNode) node).dnaString;
          stringBuilder.append(" [" + characterPercentages(dnaString) + "]");
        }
        stringBuilder.append("\n");
      }

      private String characterPercentages(DnaString dnaString) {
        int aCount = 0, cCount = 0, gCount = 0, tCount = 0;
        for (char c : dnaString.getDnaString().toCharArray()) {
          switch (c) {
            case 'A':
              aCount++;
              break;
            case 'C':
              cCount++;
              break;
            case 'G':
              gCount++;
              break;
            case 'T':
              tCount++;
              break;
          }
        }
        double percA = 0, percC = 0, percG = 0, percT = 0;
        int numChars = dnaString.getDnaString().length();
        if (numChars > 0) {
          percA = (double) aCount / numChars * 100;
          percC = (double) cCount / numChars * 100;
          percG = (double) gCount / numChars * 100;
          percT = (double) tCount / numChars * 100;
        }
        DecimalFormat df = new DecimalFormat("0.00");
        StringBuilder sb = new StringBuilder();
        sb.append("A: ").append(df.format(percA)).append("%, ");
        sb.append("C: ").append(df.format(percC)).append("%, ");
        sb.append("G: ").append(df.format(percG)).append("%, ");
        sb.append("T: ").append(df.format(percT)).append("%");
        return sb.toString();
      }

      @Override
      public String result() {
        return stringBuilder.toString();
      }
    };

    root.traverse(visitor, 0);
    return visitor.result();
  }

  @Override
  public int hashCode() {
    int hashCode = 0;
    for (DnaString dnaString : values()) {
      hashCode += dnaString.hashCode();
    }
    return hashCode;
  }

  public boolean equals(Object o) {
    if (o == this) {
      return true;
    }
    if (!(o instanceof DnaTreeSet)) {
      return false;
    }
    DnaTreeSet other = (DnaTreeSet) o;
    if (other.size() != size()) {
      return false;
    }
    for (DnaString dnaString : other.values()) {
      if (!contains(dnaString)) {
        return false;
      }
    }
    return true;
  }

  /**
   * Represents an abstract node in this tree.
   */
  private static abstract class Node {

    /**
     * Adds the specified {@link DnaString} to the subtree rooted by this node.
     * 
     * @param dnaString
     *          The DNA string to be added.
     * @param depth
     *          The depth of this node in the tree.
     * @return The new root of the subtree.
     * @throws DuplicateElementException
     *           Thrown if the subtree rooted by this node already contains the
     *           specified DNA string.
     */
    abstract Node add(DnaString dnaString, int depth)
        throws DuplicateElementException;

    /**
     * Returns {@code true} if the subtree rooted by this node contains the
     * specified {@link DnaString}.
     * 
     * @param dnaString
     *          The DNA string to be checked for containment.
     * @param depth
     *          The depth of this node in the tree.
     * @return {@code true} if the subtree rooted by this node contains the
     *         specified DNA string.
     */
    abstract boolean contains(DnaString dnaString, int depth);

    /**
     * Returns {@code true} if the subtree rooted by this node contains a
     * {@link DnaString} with the specified prefix DNA string.
     * 
     * @param prefix
     *          The prefix DNA string.
     * @param depth
     *          The depth of this node in the tree.
     * @return {@code true} if the subtree rooted by this node contains a DNA
     *         string with the specified prefix DNA string.
     */
    abstract boolean containsPrefix(DnaString prefix, int depth);

    /**
     * Adds all {@link DnaString}s contained in the subtree rooted by this node
     * matching the specified {@link DnaStringDescriptor} to the specified
     * collection.
     * 
     * @param dnaStringDescriptor
     *          The DNA string descriptor against which to match.
     * @param depth
     *          The depth of this node in the tree.
     * @param found
     *          The collection to which to add DNA strings matching the
     *          specified DNA string descriptor.
     */
    abstract void search(DnaStringDescriptor dnaStringDescriptor, int depth,
        Collection<DnaString> found);

    /**
     * Adds all {@link DnaString}s contained in the subtree rooted by this node
     * to the specified collection.
     * 
     * @param collected
     *          The collection to which to add DNA strings.
     */
    abstract void collect(Collection<DnaString> collected);

    /**
     * Removes the specified {@link DnaString} from the subtree rooted by this
     * node if it is present.
     * 
     * @param dnaString
     *          The DNA string to be removed, if present.
     * @param depth
     *          The depth of this node in the tree.
     * @return The new root of the subtree.
     * @throws AbsentElementException
     *           Thrown if the subtree rooted by this node did not contain the
     *           specified DNA string.
     */
    abstract Node remove(DnaString dnaString, int depth)
        throws AbsentElementException;

    /**
     * Traverses the subtree rooted by this node in a pre-order fashion,
     * executing the specified {@link NodeVisitor}'s
     * {@link NodeVisitor#visit(Node, int)} method at each node.
     * 
     * @param visitor
     *          The node visitor.
     * @param depth
     *          The depth of this node in the tree.
     */
    void traverse(NodeVisitor<?> visitor, int depth) {
      assert depth >= 0 : "depth must be a non-negative integer.";

      visitor.visit(this, depth);
    }

    /**
     * Returns {@code true} if this node is an {@link InternalNode}.
     * 
     * @return {@code true} if this node is an internal node.
     */
    boolean isInternalNode() {
      return false;
    }

    /**
     * Returns {@code true} if this node is a {@link LeafNode}.
     * 
     * @return {@code true} if this node is a leaf node.
     */
    boolean isLeafNode() {
      return false;
    }

    @Override
    public abstract String toString();
  }

  /**
   * Represents an internal node in this tree.
   */
  private static class InternalNode extends Node {

    // Child nodes
    Node aNode, cNode, gNode, tNode, $Node;

    /**
     * Constructs a new {@code InternalNode} with all child nodes as
     * {@link FlyweightNode}s.
     */
    InternalNode() {
      aNode = cNode = gNode = tNode = $Node = FlyweightNode.getInstance();
    }

    @Override
    Node add(DnaString dnaString, int depth) throws DuplicateElementException {
      assert dnaString != null : "dnaString is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";

      String string = dnaString.getDnaString();
      if (depth >= string.length()) {
        $Node = $Node.add(dnaString, depth + 1);
      } else {
        switch (string.charAt(depth)) {
          case 'A':
            aNode = aNode.add(dnaString, depth + 1);
            break;
          case 'C':
            cNode = cNode.add(dnaString, depth + 1);
            break;
          case 'G':
            gNode = gNode.add(dnaString, depth + 1);
            break;
          case 'T':
            tNode = tNode.add(dnaString, depth + 1);
            break;
          default:
            throw new IllegalArgumentException(
                "Invalid DNA character encountered.");
        }
      }
      return this;
    }

    @Override
    boolean contains(DnaString dnaString, int depth) {
      assert dnaString != null : "dnaString is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";

      String string = dnaString.getDnaString();
      if (depth >= string.length()) {
        return $Node.contains(dnaString, depth + 1);
      } else {
        switch (string.charAt(depth)) {
          case 'A':
            return aNode.contains(dnaString, depth + 1);
          case 'C':
            return cNode.contains(dnaString, depth + 1);
          case 'G':
            return gNode.contains(dnaString, depth + 1);
          case 'T':
            return tNode.contains(dnaString, depth + 1);
          default:
            throw new IllegalArgumentException(
                "Invalid DNA character encountered.");
        }
      }
    }

    @Override
    boolean containsPrefix(DnaString prefix, int depth) {
      assert prefix != null : "prefix is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";

      String dnaString = prefix.getDnaString();
      if (depth >= dnaString.length()) {
        return true;
      } else {
        switch (dnaString.charAt(depth)) {
          case 'A':
            return aNode.containsPrefix(prefix, depth + 1);
          case 'C':
            return cNode.containsPrefix(prefix, depth + 1);
          case 'G':
            return gNode.containsPrefix(prefix, depth + 1);
          case 'T':
            return tNode.containsPrefix(prefix, depth + 1);
          default:
            throw new IllegalArgumentException(
                "Invalid DNA character encountered.");
        }
      }
    }

    @Override
    void search(DnaStringDescriptor dnaStringDescriptor, int depth,
        Collection<DnaString> found) {
      assert dnaStringDescriptor != null : "dnaStringDescriptor is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";
      assert found != null : "found is null.";

      String descriptor = dnaStringDescriptor.getDnaStringDescriptor();
      if (depth >= descriptor.length()) {
        collect(found);
      } else {
        switch (descriptor.charAt(depth)) {
          case 'A':
            aNode.search(dnaStringDescriptor, depth + 1, found);
            break;
          case 'C':
            cNode.search(dnaStringDescriptor, depth + 1, found);
            break;
          case 'G':
            gNode.search(dnaStringDescriptor, depth + 1, found);
            break;
          case 'T':
            tNode.search(dnaStringDescriptor, depth + 1, found);
            break;
          case DnaStringDescriptor.TERMINATION_CHAR:
            $Node.search(dnaStringDescriptor, depth + 1, found);
            break;
          default:
            throw new IllegalArgumentException(
                "Invalid DNA character encountered.");
        }
      }
    }

    @Override
    void collect(Collection<DnaString> collected) {
      assert collected != null : "collected is null.";

      aNode.collect(collected);
      cNode.collect(collected);
      gNode.collect(collected);
      tNode.collect(collected);
      $Node.collect(collected);
    }

    @Override
    Node remove(DnaString dnaString, int depth) throws AbsentElementException {
      assert dnaString != null : "dnaString is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";

      String string = dnaString.getDnaString();
      if (depth >= string.length()) {
        $Node = $Node.remove(dnaString, depth + 1);
      } else {
        switch (string.charAt(depth)) {
          case 'A':
            aNode = aNode.remove(dnaString, depth + 1);
            break;
          case 'C':
            cNode = cNode.remove(dnaString, depth + 1);
            break;
          case 'G':
            gNode = gNode.remove(dnaString, depth + 1);
            break;
          case 'T':
            tNode = tNode.remove(dnaString, depth + 1);
            break;
          default:
            throw new IllegalArgumentException(
                "Invalid DNA character encountered.");
        }
      }
      return retract();
    }

    /**
     * Retracts the subtree rooted by this node if possible, returning the new
     * root of the subtree, or {@code this} if the subtree can not be retracted.
     * 
     * @return The new root of the subtree, or {@code this} if the subtree can
     *         not be retracted.
     */
    Node retract() {
      if (aNode.isInternalNode() || cNode.isInternalNode()
          || gNode.isInternalNode() || tNode.isInternalNode()) {
        return this;
      } else {
        Node leafNode = null;
        if (aNode.isLeafNode()) {
          leafNode = aNode;
        }
        if (cNode.isLeafNode()) {
          if (leafNode != null) {
            return this;
          }
          leafNode = cNode;
        }
        if (gNode.isLeafNode()) {
          if (leafNode != null) {
            return this;
          }
          leafNode = gNode;
        }
        if (tNode.isLeafNode()) {
          if (leafNode != null) {
            return this;
          }
          leafNode = tNode;
        }
        if ($Node.isLeafNode()) {
          if (leafNode != null) {
            return this;
          }
          leafNode = $Node;
        }
        return leafNode;
      }
    }

    @Override
    void traverse(NodeVisitor<?> visitor, int depth) {
      super.traverse(visitor, depth);
      aNode.traverse(visitor, depth + 1);
      cNode.traverse(visitor, depth + 1);
      gNode.traverse(visitor, depth + 1);
      tNode.traverse(visitor, depth + 1);
      $Node.traverse(visitor, depth + 1);
    }

    @Override
    boolean isInternalNode() {
      return true;
    }

    @Override
    public String toString() {
      return "I";
    }
  }

  /**
   * Represents a leaf node in this tree.
   */
  private static class LeafNode extends Node {

    // DNA string stored in this node
    final DnaString dnaString;

    /**
     * Constructs a new {@code LeafNode} with the specified {@link DnaString} to
     * be stored in this node.
     * 
     * @param dnaString
     *          The DNA string to be stored in this node.
     */
    LeafNode(DnaString dnaString) {
      assert dnaString != null : "dnaString is null.";

      this.dnaString = dnaString;
    }

    @Override
    Node add(DnaString dnaString, int depth) throws DuplicateElementException {
      assert dnaString != null : "dnaString is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";

      if (dnaString.equals(this.dnaString)) {
        throw new DuplicateElementException("DNA string " + dnaString
            + " already contained in this set.");
      }

      Node newNode = new InternalNode();
      newNode.add(this.dnaString, depth);
      newNode.add(dnaString, depth);
      return newNode;
    }

    @Override
    boolean contains(DnaString dnaString, int depth) {
      assert dnaString != null : "dnaString is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";

      return dnaString.equals(this.dnaString);
    }

    @Override
    boolean containsPrefix(DnaString prefix, int depth) {
      assert prefix != null : "prefix is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";

      return dnaString.getDnaString().startsWith(prefix.getDnaString());
    }

    @Override
    void search(DnaStringDescriptor dnaStringDescriptor, int depth,
        Collection<DnaString> found) {
      assert dnaStringDescriptor != null : "dnaStringDescriptor is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";
      assert found != null : "found is null.";

      if (dnaStringDescriptor.matches(dnaString)) {
        found.add(dnaString);
      }
    }

    @Override
    void collect(Collection<DnaString> collected) {
      assert collected != null : "collected is null.";

      collected.add(dnaString);
    }

    @Override
    Node remove(DnaString dnaString, int depth) throws AbsentElementException {
      assert dnaString != null : "dnaString is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";

      if (!dnaString.equals(this.dnaString)) {
        throw new AbsentElementException("DNA string " + dnaString
            + " is not contained in this set.");
      }

      return FlyweightNode.getInstance();
    }

    @Override
    boolean isLeafNode() {
      return true;
    }

    @Override
    public String toString() {
      return dnaString.toString();
    }
  }

  /**
   * Represents a flyweight node in this tree.
   */
  private static class FlyweightNode extends Node {

    // Singleton instance for the lifetime of the program
    static final FlyweightNode INSTANCE = new FlyweightNode();

    /**
     * Returns a singleton instance of {@code FlyweightNode}.
     * 
     * @return A singleton instance of {@code FlyweightNode}.
     */
    static FlyweightNode getInstance() {
      return INSTANCE;
    }

    @Override
    Node add(DnaString dnaString, int depth) {
      assert dnaString != null : "dnaString is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";

      return new LeafNode(dnaString);
    }

    @Override
    boolean contains(DnaString dnaString, int depth) {
      assert dnaString != null : "dnaString is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";

      return false;
    }

    @Override
    boolean containsPrefix(DnaString prefix, int depth) {
      assert prefix != null : "prefix is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";

      return false;
    }

    @Override
    void search(DnaStringDescriptor dnaStringDescriptor, int depth,
        Collection<DnaString> found) {
      assert dnaStringDescriptor != null : "dnaStringDescriptor is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";
      assert found != null : "found is null.";

      // nothing to find
    }

    @Override
    void collect(Collection<DnaString> collected) {
      // nothing to collect
    }

    @Override
    Node remove(DnaString dnaString, int depth) throws AbsentElementException {
      assert dnaString != null : "dnaString is null.";
      assert depth >= 0 : "depth must be a non-negative integer.";

      throw new AbsentElementException("DNA string " + dnaString
          + " is not contained in this set.");
    }

    @Override
    public String toString() {
      return "E";
    }
  }

  /**
   * Iterator over {@link DnaString}s in this {@code DnaTreeSet}.
   */
  private class DnaTreeSetIterator implements Iterator<DnaString> {

    // Explicit stack for traversal
    private final Stack<Node> traversal;

    /**
     * Constructs a new {@code DnaTreeSetIterator}.
     */
    DnaTreeSetIterator() {
      traversal = new Stack<>();
      traversal.push(root);
    }

    @Override
    public boolean hasNext() {
      while (!traversal.isEmpty()) {
        Node next = traversal.peek();
        if (next.isLeafNode()) {
          return true;
        }
        traversal.pop();
        if (next.isInternalNode()) {
          InternalNode internalNode = (InternalNode) next;
          traversal.push(internalNode.$Node);
          traversal.push(internalNode.tNode);
          traversal.push(internalNode.gNode);
          traversal.push(internalNode.cNode);
          traversal.push(internalNode.aNode);
        }
      }
      return false;
    }

    @Override
    public DnaString next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      LeafNode next = (LeafNode) traversal.pop();
      return next.dnaString;
    }

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

  /**
   * A {@link Node} visitor for operating on this tree's nodes.
   * 
   * @param <T>
   *          The type of the resulting value.
   */
  private static interface NodeVisitor<T> {

    /**
     * Visits the specified {@link Node}.
     * 
     * @param node
     *          The node to visit.
     * @param depth
     *          The depth of the node being visited.
     */
    void visit(Node node, int depth);

    /**
     * Returns the value currently resulting from this {@code NodeVisitor}'s
     * visiting.
     * 
     * @return The value currently resulting from this {@code NodeVisitor}'s
     *         visiting.
     */
    T result();
  }

  /**
   * Thrown to indicate that a mapping for a duplicate element has been
   * encountered.
   */
  private static class DuplicateElementException extends Exception {

    static final long serialVersionUID = 9054209401712052017L;

    /**
     * Constructs a new {@code DuplicateElementException}.
     */
    DuplicateElementException() {
      super();
    }

    /**
     * Constructs a new {@code DuplicateElementException} with the specified
     * detail message.
     * 
     * @param message
     *          The detail message.
     */
    DuplicateElementException(String message) {
      super(message);
    }
  }

  /**
   * Thrown to indicate that an element has not been encountered.
   */
  private static class AbsentElementException extends Exception {

    static final long serialVersionUID = 7346751132692363281L;

    /**
     * Constructs a new {@code AbsentElementException}.
     */
    AbsentElementException() {
      super();
    }

    /**
     * Constructs a new {@code AbsentElementException} with the specified detail
     * message.
     * 
     * @param message
     *          The detail message.
     */
    AbsentElementException(String message) {
      super(message);
    }
  }
}