← Back to branch summary

~eda-qa/dhlib/main

« back to all changes in this revision

Viewing changes to app-words/words/PermutationTree.mhx

  • Committer: edA-qa mort-ora-y
  • Date: 2010-02-16 05:36:32 UTC
  • Revision ID: eda-qa@disemia.com-20100216053632-60lt7fndfi3fgblw
first

Show diffs side-by-side

added added

removed removed

Lines of Context:
app-words/words/PermutationTree.mhx
 
1
/* <license>
 
2
 * This file is part of the dis-Emi-A HaXe Library. Copyright © edA-qa mort-ora-y
 
3
 * For full copyright and license information please refer to doc/license.txt.
 
4
 * </license> 
 
5
 */
 
6
package words;
 
7
 
 
8
/**
 
9
 * Allows navigation of a word via permutation tree: exposes the permutations 
 
10
 * of a string as a tree
 
11
 */
 
12
class PermutationTree
 
13
{
 
14
        var items : List<String>;
 
15
        
 
16
        private function new( items : List<String> )
 
17
        {
 
18
                this.items = items;
 
19
        }
 
20
        
 
21
        /**
 
22
         *  Provide a string for a permutation which will permutate all orders of the
 
23
         * characters in the string.  
 
24
         *
 
25
         * @param string [in] the characters which to permute. 
 
26
         *              NOTE: Characters are all treated as unique, thus providing a character
 
27
         *              twice will result in two passes on that branch.  This is very hard
 
28
         *      to avoid without suffering horrible performance loss.
 
29
         */
 
30
        static public function withString( string : String )
 
31
        {
 
32
                var items = new List<String>();
 
33
                for( i in 0...string.length )
 
34
                        items.add( string.charAt(i) );
 
35
                return new PermutationTree( items );
 
36
        }
 
37
        
 
38
        /**
 
39
         * Obtain the root node of the tree.  Multiple calls to this function may
 
40
         * return different objects.  The object returned should be considered
 
41
         * invalid if the owning tree changes.
 
42
         */
 
43
        public function root() : PermutationIterator
 
44
        {
 
45
                return new TreePermutationIterator( new TreePermutationIteratorInt( null, items, 0 ) );
 
46
        }
 
47
}
 
48
 
 
49
/**
 
50
 * Build the iterator out of the virtual node items.  That was how it was built
 
51
 * first, and since there is no present need to optimize this it will just stay
 
52
 * that way.
 
53
 */
 
54
private class TreePermutationIterator implements PermutationIterator
 
55
{
 
56
        var current : TreePermutationIteratorInt;
 
57
        
 
58
        public function new( start : TreePermutationIteratorInt )
 
59
        {
 
60
                current = start;
 
61
        }
 
62
        
 
63
        public function childFirstStep() : Bool
 
64
        {
 
65
                if( current.hasFirstChild() )
 
66
                {
 
67
                        current = current.firstChild();
 
68
                        return true;
 
69
                }
 
70
                if( current.hasNextSibling() )
 
71
                {
 
72
                        current = current.nextSibling();
 
73
                        return true;
 
74
                }
 
75
                        
 
76
                while( current.hasParent() )
 
77
                {
 
78
                        current = current.parent();
 
79
                        if( current.hasNextSibling() )
 
80
                        {
 
81
                                current = current.nextSibling();
 
82
                                return true;
 
83
                        }
 
84
                }
 
85
                
 
86
                return false;
 
87
        }
 
88
        
 
89
        public function stringToHere() : String { return current.stringToHere(); }
 
90
        
 
91
        /**
 
92
         * @return [out] firstChild, or null if none
 
93
         */
 
94
        public function toFirstChild() : Bool { current = current.firstChild(); return current != null; }
 
95
        public function hasFirstChild() : Bool { return current.hasFirstChild(); }
 
96
        
 
97
        /**
 
98
         * @return [out] next sbiling, or null if none
 
99
         */
 
100
        public function toNextSibling() : Bool { current = current.nextSibling(); return current != null; }
 
101
        public function hasNextSibling() : Bool { return current.hasNextSibling(); }
 
102
        
 
103
        /**
 
104
         * @return [out] parent, or null if none
 
105
         */
 
106
        public function toParent() : Bool { current = current.parent(); return current != null; }
 
107
        public function hasParent() : Bool { return current.hasParent(); }
 
108
        
 
109
}
 
110
 
 
111
private class TreePermutationIteratorInt
 
112
{
 
113
        var parentN : TreePermutationIteratorInt;
 
114
        var set : List<String>; //rotation such that "at" is always at front
 
115
        var at : Int;   //how far into this set we are
 
116
        
 
117
        public function new( parent : TreePermutationIteratorInt, set : List<String>, at : Int )
 
118
        {
 
119
                this.parentN = parent;
 
120
                this.set = set;
 
121
                this.at = at;
 
122
        }
 
123
        
 
124
        public function stringToHere() : String
 
125
        {
 
126
                var ret = (parentN == null) ? "" : parentN.stringToHere();
 
127
                ret += set.first();
 
128
                return ret;
 
129
        }
 
130
        
 
131
        public function firstChild() : TreePermutationIteratorInt
 
132
        {
 
133
                if( !hasFirstChild() )
 
134
                        return null;
 
135
                        
 
136
                var cset = ListUtil.clone( set );
 
137
                cset.pop();     //drop out item
 
138
                return new TreePermutationIteratorInt( this, cset, 0 );
 
139
        }
 
140
        
 
141
        public function hasFirstChild() : Bool
 
142
        {
 
143
                return set.length > 1;
 
144
        }
 
145
        
 
146
        public function nextSibling() : TreePermutationIteratorInt
 
147
        {
 
148
                if( !hasNextSibling() )
 
149
                        return null;
 
150
                        
 
151
                //NOTE: This clone could be avoided if we use Array's instead of List's
 
152
                var sset = ListUtil.clone( set );
 
153
                //rotate
 
154
                var r = sset.pop();
 
155
                sset.add( r );
 
156
                
 
157
                return new TreePermutationIteratorInt( parentN, sset, at+1 );
 
158
        }
 
159
        
 
160
        public function hasNextSibling() : Bool
 
161
        {
 
162
                return (at+1) < set.length;
 
163
        }
 
164
        
 
165
        public function parent() : TreePermutationIteratorInt
 
166
        {
 
167
                return parentN;
 
168
        }
 
169
        
 
170
        public function hasParent() : Bool
 
171
        {
 
172
                return parentN != null;
 
173
        }
 
174
 
 
175
}