using Nemerle.Collections;
using Nemerle.IO;

class SuffixTrees {

  class node {
    public mutable childs : Hashtable [char, node]; 
    public suffNr : int; 
    public mutable link : node;

    public this (childs : Hashtable [char, node], suffNr : int, link : node) {
      this.childs = childs;
      this.suffNr = suffNr;
      this.link = link;
    }

    public HasChild (c : char) : bool {
      if (this.childs != null)
        this.childs.Contains (c)
      else
        false
    }

    public GetChild (c : char) : node {
      match (this.childs.Get (c)) {
        | Some (n) => n
        | None => throw System.Exception ()
      }
    }
  }


  static OnLineTrie (str : string) : node {
    def n = str.Length;

    if (n >= 1) {
      def root = node (Hashtable (), 0, null);
      root.link = root;
      mutable v = node (null, 1, root);
      root.childs.Add (str[0], v);
      
      for (mutable i = 1; i < n; i = i + 1) {
        mutable a = str[i];
        mutable w = v;
        mutable prev = (null : node);

        while (!w.HasChild (a)) {
          def newNode = node (null, w.suffNr + 1, null);

          when (w.childs == null) { w.childs = Hashtable(); };
          w.childs.Add (a, newNode);

          unless (prev == null) { prev.link = newNode; };
          prev = newNode;

          when ((v : object) == w) { v = newNode; };

          w = w.link;
        };
        prev.link = w.GetChild (a);
        when ((prev : object) == prev.link) { prev.link = w };
      };
      root
    }
    else
      node (Hashtable (), 0, null)
  }


  public static Main() : void {
    def str = "abbaabac";
    
    def sufftree = OnLineTrie (str);

    def print_trie (nd : node, empty : string) : void {
      def print_child (cha : char, n : node) : void {
        printf ("%s%c\n", empty, cha);
        print_trie (n, empty + "  ");
      };

      printf ("%sNode %d\n", empty, nd.suffNr);
      when (nd.childs != null) {
        def childs = nd.childs.Fold ([], fun (k, v, acc) { 
    (k,v) :: acc 
  });
  def sorted = List.Sort (childs, fun (x, y) { 
    | ((k1, _), (k2, _)) => if ((k1 : char) > k2) 1 else -1
  });
  
  List.Iter (sorted, print_child);
      }
    };

    print_trie (sufftree, "");
  }
}

/*
BEGIN-OUTPUT
Node 0
a
  Node 1
  a
    Node 2
    b
      Node 3
      a
        Node 4
        c
          Node 5
  b
    Node 2
    a
      Node 3
      c
        Node 4
    b
      Node 3
      a
        Node 4
        a
          Node 5
          b
            Node 6
            a
              Node 7
              c
                Node 8
  c
    Node 2
b
  Node 1
  a
    Node 2
    a
      Node 3
      b
        Node 4
        a
          Node 5
          c
            Node 6
    c
      Node 3
  b
    Node 2
    a
      Node 3
      a
        Node 4
        b
          Node 5
          a
            Node 6
            c
              Node 7
c
  Node 1
END-OUTPUT
*/