Branch data Line data Source code
1 : : // $Id: EquivClass.cc 6219 2008-10-01 05:39:07Z vern $
2 : : //
3 : : // See the file "COPYING" in the main distribution directory for copyright.
4 : :
5 : : #include "config.h"
6 : :
7 : : #include "EquivClass.h"
8 : :
9 : 1026 : EquivClass::EquivClass(int arg_size)
10 : : {
11 : 1026 : size = arg_size;
12 : 1026 : fwd = new int[size];
13 : 1026 : bck = new int[size];
14 : 1026 : equiv_class = new int[size];
15 : 1026 : rep = new int[size];
16 : 1026 : ccl_flags = 0;
17 : 1026 : num_ecs = 0;
18 : :
19 : 1026 : ec_nil = no_class = no_rep = size + 1;
20 : :
21 : 1026 : bck[0] = ec_nil;
22 : 1026 : fwd[size - 1] = ec_nil;
23 : :
24 [ + + ][ # # ]: 126749 : for ( int i = 0; i < size; ++i )
25 : : {
26 [ + + ][ # # ]: 125723 : if ( i > 0 )
27 : : {
28 : 124697 : fwd[i - 1] = i;
29 : 124697 : bck[i] = i - 1;
30 : : }
31 : :
32 : 125723 : equiv_class[i] = no_class;
33 : 125723 : rep[i] = no_rep;
34 : : }
35 : 1026 : }
36 : :
37 : 4 : EquivClass::~EquivClass()
38 : : {
39 [ + - ][ # # ]: 4 : delete [] fwd;
40 [ + - ][ # # ]: 4 : delete [] bck;
41 [ + - ][ # # ]: 4 : delete [] equiv_class;
42 [ + - ][ # # ]: 4 : delete [] rep;
43 [ + - ][ # # ]: 4 : delete [] ccl_flags;
44 : 4 : }
45 : :
46 : 1069 : void EquivClass::ConvertCCL(CCL* ccl)
47 : : {
48 : : // For each character in the class, add the character's
49 : : // equivalence class to the new "character" class we are
50 : : // creating. Thus when we are all done, the character class
51 : : // will really consist of collections of equivalence classes
52 : : // instead of collections of characters.
53 : :
54 : 1069 : int_list* c_syms = ccl->Syms();
55 : 1069 : int_list* new_syms = new int_list;
56 : :
57 [ + + ]: 7740 : for ( int i = 0; i < c_syms->length(); ++i )
58 : : {
59 : 6671 : int sym = (*c_syms)[i];
60 [ + + ]: 6671 : if ( IsRep(sym) )
61 : 2617 : new_syms->append(SymEquivClass(sym));
62 : : }
63 : :
64 : 1069 : ccl->ReplaceSyms(new_syms);
65 : 1069 : }
66 : :
67 : 1026 : int EquivClass::BuildECs()
68 : : {
69 : : // Create equivalence class numbers. If bck[x] is nil,
70 : : // then x is the representative of its equivalence class.
71 : :
72 [ + + ]: 126749 : for ( int i = 0; i < size; ++i )
73 [ + + ]: 125723 : if ( bck[i] == ec_nil )
74 : : {
75 : 10179 : equiv_class[i] = num_ecs++;
76 : 10179 : rep[i] = i;
77 [ + + ]: 125723 : for ( int j = fwd[i]; j != ec_nil; j = fwd[j] )
78 : : {
79 : 115544 : equiv_class[j] = equiv_class[i];
80 : 115544 : rep[j] = i;
81 : : }
82 : : }
83 : :
84 : 1026 : return num_ecs;
85 : : }
86 : :
87 : 4650 : void EquivClass::CCL_Use(CCL* ccl)
88 : : {
89 : : // Note that it doesn't matter whether or not the character class is
90 : : // negated. The same results will be obtained in either case.
91 : :
92 [ + + ]: 4650 : if ( ! ccl_flags )
93 : : {
94 : 797 : ccl_flags = new int[size];
95 [ + + ]: 108035 : for ( int i = 0; i < size; ++i )
96 : 107238 : ccl_flags[i] = 0;
97 : : }
98 : :
99 : 4650 : int_list* csyms = ccl->Syms();
100 [ + + ]: 13398 : for ( int i = 0; i < csyms->length(); /* no increment */ )
101 : : {
102 : 8748 : int sym = (*csyms)[i];
103 : :
104 : 8748 : int old_ec = bck[sym];
105 : 8748 : int new_ec = sym;
106 : :
107 : 8748 : int j = i + 1;
108 : :
109 [ + - ][ + + ]: 216727 : for ( int k = fwd[sym]; k && k < size; k = fwd[k] )
110 : : { // look for the symbol in the character class
111 [ + + ]: 214374 : for ( ; j < csyms->length(); ++j )
112 : : {
113 [ + + ]: 109083 : if ( (*csyms)[j] > k )
114 : : // Since the character class is sorted,
115 : : // we can stop.
116 : 95281 : break;
117 : :
118 [ + + ][ + - ]: 13802 : if ( (*csyms)[j] == k && ! ccl_flags[j] )
[ + + ]
119 : : {
120 : : // We found an old companion of sym
121 : : // in the ccl. Link it into the new
122 : : // equivalence class and flag it as
123 : : // having been processed.
124 : 7407 : bck[k] = new_ec;
125 : 7407 : fwd[new_ec] = k;
126 : 7407 : new_ec = k;
127 : :
128 : : // Set flag so we don't reprocess.
129 : 7407 : ccl_flags[j] = 1;
130 : :
131 : : // Get next equivalence class member.
132 : 7407 : break;
133 : : }
134 : : }
135 : :
136 [ + + ][ + + ]: 207979 : if ( j < csyms->length() && (*csyms)[j] == k )
[ + + ]
137 : : // We broke out of the above loop by finding
138 : : // an old companion - go to the next symbol.
139 : 7407 : continue;
140 : :
141 : : // Symbol isn't in character class. Put it in the old
142 : : // equivalence class.
143 : 200572 : bck[k] = old_ec;
144 [ + + ]: 200572 : if ( old_ec != ec_nil )
145 : 200550 : fwd[old_ec] = k;
146 : :
147 : 200572 : old_ec = k;
148 : : }
149 : :
150 [ + + ][ + + ]: 8748 : if ( bck[sym] != ec_nil || old_ec != bck[sym] )
151 : : {
152 : 2144 : bck[sym] = ec_nil;
153 : 2144 : fwd[old_ec] = ec_nil;
154 : : }
155 : :
156 : 8748 : fwd[new_ec] = ec_nil;
157 : :
158 : : // Find next ccl member to process.
159 [ + + ][ + + ]: 16155 : for ( ++i; i < csyms->length() && ccl_flags[i]; ++i )
[ + + ]
160 : : // Reset "doesn't need processing" flag.
161 : 7407 : ccl_flags[i] = 0;
162 : : }
163 : 4650 : }
164 : :
165 : :
166 : 24812 : void EquivClass::UniqueChar(int sym)
167 : : {
168 : : // If until now the character has been a proper subset of
169 : : // an equivalence class, break it away to create a new ec.
170 : :
171 [ + + ]: 24812 : if ( fwd[sym] != ec_nil )
172 : 6712 : bck[fwd[sym]] = bck[sym];
173 : :
174 [ + + ]: 24812 : if ( bck[sym] != ec_nil )
175 : 6555 : fwd[bck[sym]] = fwd[sym];
176 : :
177 : 24812 : fwd[sym] = ec_nil;
178 : 24812 : bck[sym] = ec_nil;
179 : 24812 : }
180 : :
181 : 0 : void EquivClass::Dump(FILE* f)
182 : : {
183 : 0 : fprintf(f, "%d symbols in EC yielded %d ecs\n", size, num_ecs);
184 [ # # ]: 0 : for ( int i = 0; i < size; ++i )
185 [ # # ]: 0 : if ( SymEquivClass(i) != 0 ) // skip usually huge default ec
186 : 0 : fprintf(f, "map %d ('%c') -> %d\n", i, i, SymEquivClass(i));
187 : 0 : }
188 : :
189 : 0 : int EquivClass::Size() const
190 : : {
191 [ # # ]: 0 : return padded_sizeof(*this) + pad_size(sizeof(int) * size * (ccl_flags ? 5 : 4));
192 : : }
|
