← Back to branch summary

~ubuntu-branches/ubuntu/natty/mimetic/natty

« back to all changes in this revision

Viewing changes to test/t.tree.h

  • Committer: Bazaar Package Importer
  • Author(s): gregor herrmann
  • Date: 2006-06-16 13:16:07 UTC
  • Revision ID: james.westby@ubuntu.com-20060616131607-245mqjypkjuahq6b
Tags: upstream-0.9.1
Import upstream version 0.9.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
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