class structure

Each node of the tree is an instance of the "Object" class below.

class Object{
public:
  string lemma;              // identifier
  int    count;              
  list<Object> branches;

  void    add_sequence(  vector<Object>::iterator );
  void    sort_branches();
  void    printout(int);
 }

In the following example tree:

A :3
     B :3
          C :2
          D :1

The object instances would be:

 Object A {
           lemma = "A"
           count = 3
           branches = [ B ]
           }

 Object B {
           lemma = "B"
           count = 3
           branches = [ C,D ]
           }

 Object C {
           lemma = "C"
           count = 2
           branches = [ ]
           }

 Object D {
           lemma = "D"
           count = 1
           branches = [ ]
           }

The member functions are all recursive: (in pseudo code)

Object: :printout(int depth){
  for( i =0; i<depth;i++) cout<<"   "
  cout<<lemma<<" :"<<count<<endl
  for (b=branches.begin; b!=branches.end){
      b->printout(depth+1)
   }
}

Object: :sort_branches(){
    branches.sort()
    for (b=branches.begin; b!=branches.end){
        b->sort_branches()
    }
}

The add_sequence() function operates on a vector of Objects. To add a sequence [A, B, C] to a tree, we call add_sequence(o), where o points to the first object in the vector.

Object: :add_sequence( vector<Object>: :iterator o){
   if (o->lemma == "") return
   for (b=branches.begin; b!=branches.end){
      if (o->lemma == b->lemma){
         b->count++
         b->add_sequence(++o)
         return
      }
   }      
   // new branch
   Object new_branch(*o)
   branches.push_back(new_branch)
   branches.back().add_sequence(++o)
}

An example main() function to build and print the tree would be:

main(){

  Object A, B, C
  A->lemma="A"
  B->lemma="B"
  C->lemma="C"
  vector<Object> v1 = [ A, B, C ]
  vector<Object> v2 = [ A, B, D ]

  Object tree
  vector: :iterator o=v1.begin
  tree.add_sequence(o)
  tree.add_sequence(o)

  o = v2.begin()
  tree.add_sequence(o)

  tree.sort_branches()
  tree.printout()
}

This would printout the tree:

A :3
     B :3
          C :2
          D :1

The class used in the ensuing analysis is expanded from the above definition. But the general framework is the same.