test/t.tree.h

   1 #ifndef _T_TREE_H_
   2 #define _T_TREE_H_
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <mimetic/tree.h>
   6 #include "cutee.h"
   7
   8
   9 namespace mimetic
  10 {
  11
  12 struct TEST_CLASS( tree )
  13 {
  14     typedef TreeNode<char> Node;
  15     void TEST_FUNCTION( buildTree )
  16     {
  17         const char* words[] = {
  18               "pro", "pra", "tre", 0
  19         };
  20
  21         // creates a tree of reversed wordlist (*words)
  22         for(int i = 0; words[i]; ++i)
  23         {
  24             Node::NodeList *pChilds = &m_tree.childList();
  25             Node::NodeList::iterator it = pChilds->begin();
  26             const char *w = words[i];
  27             int depth = 0;
  28             do
  29             {
  30                 it = find_if(pChilds->begin(), pChilds->end(),
  31                         FindNodePred<char>(*w));
  32                 if( it == pChilds->end() )
  33                 {
  34                     it = pChilds->insert(pChilds->end(),*w);
  35                     TEST_ASSERT(pChilds->size() > 0);
  36                 }
  37                 pChilds = &it->childList();
  38                 depth++;
  39             } while(*++w);
  40         }
  41     }
  42     void TEST_FUNCTION( search )
  43     {
  44         // boyer-moore algorithm modified to work with
  45         // multiple patterns(i.e. boundaries)
  46
  47         #if 0
  48         // tlen: text len
  49         // mlen: pattern len
  50         // text: input text
  51         // muster: patter
  52         int i, j, skip[256];
  53
  54         for(i=0; i<256; ++i)
  55             skip[i]=mlen;
  56         for(i=0; i<mlen; ++i)
  57             skip[muster[i]]=mlen-1-i;
  58
  59         for(i=j=mlen-1; j>=0; --i, --j)
  60             while(text[i] != muster[j])
  61             {
  62             i += max(mlen-j,skip[text[i]]);
  63             if(i >= tlen)
  64                 return -1;
  65             j = mlen-1;
  66             }
  67         return i;
  68         #endif
  69     }
  70 private:
  71     Node m_tree;
  72 };
  73
  74 }
  75
  76
  77 #endif