Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Dateiinhalt

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * An object representing a single trie, i.e., a tree that is used to store a set of strings.
 */
public class Trie {
  // Root node of the trie
  private Node root;

  public Trie() {
    root = new Node();
  }

  /**
   * Add the given word to the trie.
   */
  public void add(String word) {
    //TODO: insert code here
  }

  /**
   * Search the trie for the given word.
   * 
   * @return true if the trie contains the word, otherwise false.
   */
  private boolean contains(String word) {
    //TODO: insert code here
    return true;
  }

  /**
   * Print a list of all words in the trie.
   */
  public void printWords() {
    printWordsRecursive(root, "");
  }

  private void printWordsRecursive(Node node, String word) {
    //TODO: insert code here
  }

  /**
   * Main method with a simple test case for the trie.
   * The output should not print any ERRORs, but all inserted words correctly.
   * The order, in which words are printed, is of no importance.
   */
  public static void main(String[] args) {
    Trie trie = new Trie();
    trie.add("foo");
    check(trie,"foo",true);
    check(trie,"fo",false);

    trie.add("bar");
    check(trie,"bar",true);
    check(trie,"foobar",false);

    trie.add("baz");
    check(trie,"baz",true);
    check(trie,"bar",true);

    trie.add("flo");
    check(trie,"flo",true);
    check(trie,"foo",true);

    trie.add("flob");
    check(trie,"flob",true);
    check(trie,"flo",true);
    check(trie,"",false);

    trie.printWords();
  }

  public static void check(Trie trie, String word, boolean correctResult) {
    if (trie.contains(word) != correctResult)
      System.out.println("ERROR: " + word + " is falsely reported as "
          + (correctResult ? "not contained." : "contained."));
  }

  /**
   * A Node object represents one node in the trie.
   */
  private class Node {
    private Map<Character, Node> outgoingEdges;

    public Node() {
      outgoingEdges = new HashMap<Character, Node>();
    }

    public void addOutgoingEdge(char c, Node child) {
      outgoingEdges.put(c, child);
    }

    public Set<Character> getOutgoingEdgeLabels() {
      return outgoingEdges.keySet();
    }

    public Node getChild(char c) {
      return outgoingEdges.get(c);
    }
  }
}