1 | /* | |
2 | * Copyright 1999-2004 The Apache Software Foundation. | |
3 | * | |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); | |
5 | * you may not use this file except in compliance with the License. | |
6 | * You may obtain a copy of the License at | |
7 | * | |
8 | * http://www.apache.org/licenses/LICENSE-2.0 | |
9 | * | |
10 | * Unless required by applicable law or agreed to in writing, software | |
11 | * distributed under the License is distributed on an "AS IS" BASIS, | |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
13 | * See the License for the specific language governing permissions and | |
14 | * limitations under the License. | |
15 | */ | |
16 | ||
17 | package com.lowagie.text.pdf.hyphenation; | |
18 | ||
19 | import java.io.Serializable; | |
20 | import java.util.Enumeration; | |
21 | import java.util.Stack; | |
22 | ||
23 | /** | |
24 | * <h2>Ternary Search Tree.</h2> | |
25 | * | |
26 | * <p>A ternary search tree is a hybrid between a binary tree and | |
27 | * a digital search tree (trie). Keys are limited to strings. | |
28 | * A data value of type char is stored in each leaf node. | |
29 | * It can be used as an index (or pointer) to the data. | |
30 | * Branches that only contain one key are compressed to one node | |
31 | * by storing a pointer to the trailer substring of the key. | |
32 | * This class is intended to serve as base class or helper class | |
33 | * to implement Dictionary collections or the like. Ternary trees | |
34 | * have some nice properties as the following: the tree can be | |
35 | * traversed in sorted order, partial matches (wildcard) can be | |
36 | * implemented, retrieval of all keys within a given distance | |
37 | * from the target, etc. The storage requirements are higher than | |
38 | * a binary tree but a lot less than a trie. Performance is | |
39 | * comparable with a hash table, sometimes it outperforms a hash | |
40 | * function (most of the time can determine a miss faster than a hash).</p> | |
41 | * | |
42 | * <p>The main purpose of this java port is to serve as a base for | |
43 | * implementing TeX's hyphenation algorithm (see The TeXBook, | |
44 | * appendix H). Each language requires from 5000 to 15000 hyphenation | |
45 | * patterns which will be keys in this tree. The strings patterns | |
46 | * are usually small (from 2 to 5 characters), but each char in the | |
47 | * tree is stored in a node. Thus memory usage is the main concern. | |
48 | * We will sacrifice 'elegance' to keep memory requirements to the | |
49 | * minimum. Using java's char type as pointer (yes, I know pointer | |
50 | * it is a forbidden word in java) we can keep the size of the node | |
51 | * to be just 8 bytes (3 pointers and the data char). This gives | |
52 | * room for about 65000 nodes. In my tests the English patterns | |
53 | * took 7694 nodes and the German patterns 10055 nodes, | |
54 | * so I think we are safe.</p> | |
55 | * | |
56 | * <p>All said, this is a map with strings as keys and char as value. | |
57 | * Pretty limited!. It can be extended to a general map by | |
58 | * using the string representation of an object and using the | |
59 | * char value as an index to an array that contains the object | |
60 | * values.</p> | |
61 | * | |
62 | * @author cav@uniscope.co.jp | |
63 | */ | |
64 | ||
65 | public class TernaryTree implements Cloneable, Serializable { | |
66 | ||
67 | /** | |
68 | * We use 4 arrays to represent a node. I guess I should have created | |
69 | * a proper node class, but somehow Knuth's pascal code made me forget | |
70 | * we now have a portable language with virtual memory management and | |
71 | * automatic garbage collection! And now is kind of late, furthermore, | |
72 | * if it ain't broken, don't fix it. | |
73 | */ | |
74 | ||
75 | private static final long serialVersionUID = 5313366505322983510L; | |
76 | ||
77 | /** | |
78 | * Pointer to low branch and to rest of the key when it is | |
79 | * stored directly in this node, we don't have unions in java! | |
80 | */ | |
81 | protected char[] lo; | |
82 | ||
83 | /** | |
84 | * Pointer to high branch. | |
85 | */ | |
86 | protected char[] hi; | |
87 | ||
88 | /** | |
89 | * Pointer to equal branch and to data when this node is a string terminator. | |
90 | */ | |
91 | protected char[] eq; | |
92 | ||
93 | /** | |
94 | * <P>The character stored in this node: splitchar. | |
95 | * Two special values are reserved:</P> | |
96 | * <ul><li>0x0000 as string terminator</li> | |
97 | * <li>0xFFFF to indicate that the branch starting at | |
98 | * this node is compressed</li></ul> | |
99 | * <p>This shouldn't be a problem if we give the usual semantics to | |
100 | * strings since 0xFFFF is guaranteed not to be an Unicode character.</p> | |
101 | */ | |
102 | protected char[] sc; | |
103 | ||
104 | /** | |
105 | * This vector holds the trailing of the keys when the branch is compressed. | |
106 | */ | |
107 | protected CharVector kv; | |
108 | ||
109 | protected char root; | |
110 | protected char freenode; | |
111 | protected int length; // number of items in tree | |
112 | ||
113 | protected static final int BLOCK_SIZE = 2048; // allocation size for arrays | |
114 | ||
115 | TernaryTree() { | |
116 |
1
1. |
init(); |
117 | } | |
118 | ||
119 | protected void init() { | |
120 | root = 0; | |
121 | freenode = 1; | |
122 | length = 0; | |
123 | lo = new char[BLOCK_SIZE]; | |
124 | hi = new char[BLOCK_SIZE]; | |
125 | eq = new char[BLOCK_SIZE]; | |
126 | sc = new char[BLOCK_SIZE]; | |
127 | kv = new CharVector(); | |
128 | } | |
129 | ||
130 | /** | |
131 | * Branches are initially compressed, needing | |
132 | * one node per key plus the size of the string | |
133 | * key. They are decompressed as needed when | |
134 | * another key with same prefix | |
135 | * is inserted. This saves a lot of space, | |
136 | * specially for long keys. | |
137 | */ | |
138 | public void insert(String key, char val) { | |
139 | // make sure we have enough room in the arrays | |
140 |
1
1. insert : Replaced integer addition with subtraction → NO_COVERAGE |
int len = key.length() |
141 | + 1; // maximum number of nodes that may be generated | |
142 |
3
1. insert : changed conditional boundary → NO_COVERAGE 2. insert : Replaced integer addition with subtraction → NO_COVERAGE 3. insert : negated conditional → NO_COVERAGE |
if (freenode + len > eq.length) { |
143 |
2
1. insert : Replaced integer addition with subtraction → NO_COVERAGE 2. insert : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::redimNodeArrays → NO_COVERAGE |
redimNodeArrays(eq.length + BLOCK_SIZE); |
144 | } | |
145 |
1
1. insert : Changed increment from -1 to 1 → NO_COVERAGE |
char[] strkey = new char[len--]; |
146 |
1
1. insert : removed call to java/lang/String::getChars → NO_COVERAGE |
key.getChars(0, len, strkey, 0); |
147 | strkey[len] = 0; | |
148 | root = insert(root, strkey, 0, val); | |
149 | } | |
150 | ||
151 | public void insert(char[] key, int start, char val) { | |
152 |
1
1. insert : Replaced integer addition with subtraction → NO_COVERAGE |
int len = strlen(key) + 1; |
153 |
3
1. insert : changed conditional boundary → NO_COVERAGE 2. insert : Replaced integer addition with subtraction → NO_COVERAGE 3. insert : negated conditional → NO_COVERAGE |
if (freenode + len > eq.length) { |
154 |
2
1. insert : Replaced integer addition with subtraction → NO_COVERAGE 2. insert : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::redimNodeArrays → NO_COVERAGE |
redimNodeArrays(eq.length + BLOCK_SIZE); |
155 | } | |
156 | root = insert(root, key, start, val); | |
157 | } | |
158 | ||
159 | /** | |
160 | * The actual insertion function, recursive version. | |
161 | */ | |
162 | private char insert(char p, char[] key, int start, char val) { | |
163 | int len = strlen(key, start); | |
164 |
1
1. insert : negated conditional → NO_COVERAGE |
if (p == 0) { |
165 | // this means there is no branch, this node will start a new branch. | |
166 | // Instead of doing that, we store the key somewhere else and create | |
167 | // only one node with a pointer to the key | |
168 |
1
1. insert : Replaced integer addition with subtraction → NO_COVERAGE |
p = freenode++; |
169 | eq[p] = val; // holds data | |
170 |
1
1. insert : Replaced integer addition with subtraction → NO_COVERAGE |
length++; |
171 | hi[p] = 0; | |
172 |
2
1. insert : changed conditional boundary → NO_COVERAGE 2. insert : negated conditional → NO_COVERAGE |
if (len > 0) { |
173 | sc[p] = 0xFFFF; // indicates branch is compressed | |
174 |
1
1. insert : Replaced integer addition with subtraction → NO_COVERAGE |
lo[p] = (char)kv.alloc(len |
175 | + 1); // use 'lo' to hold pointer to key | |
176 |
1
1. insert : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::strcpy → NO_COVERAGE |
strcpy(kv.getArray(), lo[p], key, start); |
177 | } else { | |
178 | sc[p] = 0; | |
179 | lo[p] = 0; | |
180 | } | |
181 |
1
1. insert : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return p; |
182 | } | |
183 | ||
184 |
1
1. insert : negated conditional → NO_COVERAGE |
if (sc[p] == 0xFFFF) { |
185 | // branch is compressed: need to decompress | |
186 | // this will generate garbage in the external key array | |
187 | // but we can do some garbage collection later | |
188 |
1
1. insert : Replaced integer addition with subtraction → NO_COVERAGE |
char pp = freenode++; |
189 | lo[pp] = lo[p]; // previous pointer to key | |
190 | eq[pp] = eq[p]; // previous pointer to data | |
191 | lo[p] = 0; | |
192 |
2
1. insert : changed conditional boundary → NO_COVERAGE 2. insert : negated conditional → NO_COVERAGE |
if (len > 0) { |
193 | sc[p] = kv.get(lo[pp]); | |
194 | eq[p] = pp; | |
195 |
1
1. insert : Replaced integer addition with subtraction → NO_COVERAGE |
lo[pp]++; |
196 |
1
1. insert : negated conditional → NO_COVERAGE |
if (kv.get(lo[pp]) == 0) { |
197 | // key completely decompressed leaving garbage in key array | |
198 | lo[pp] = 0; | |
199 | sc[pp] = 0; | |
200 | hi[pp] = 0; | |
201 | } else { | |
202 | // we only got first char of key, rest is still there | |
203 | sc[pp] = 0xFFFF; | |
204 | } | |
205 | } else { | |
206 | // In this case we can save a node by swapping the new node | |
207 | // with the compressed node | |
208 | sc[pp] = 0xFFFF; | |
209 | hi[p] = pp; | |
210 | sc[p] = 0; | |
211 | eq[p] = val; | |
212 |
1
1. insert : Replaced integer addition with subtraction → NO_COVERAGE |
length++; |
213 |
1
1. insert : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return p; |
214 | } | |
215 | } | |
216 | char s = key[start]; | |
217 |
2
1. insert : changed conditional boundary → NO_COVERAGE 2. insert : negated conditional → NO_COVERAGE |
if (s < sc[p]) { |
218 | lo[p] = insert(lo[p], key, start, val); | |
219 |
1
1. insert : negated conditional → NO_COVERAGE |
} else if (s == sc[p]) { |
220 |
1
1. insert : negated conditional → NO_COVERAGE |
if (s != 0) { |
221 |
1
1. insert : Replaced integer addition with subtraction → NO_COVERAGE |
eq[p] = insert(eq[p], key, start + 1, val); |
222 | } else { | |
223 | // key already in tree, overwrite data | |
224 | eq[p] = val; | |
225 | } | |
226 | } else { | |
227 | hi[p] = insert(hi[p], key, start, val); | |
228 | } | |
229 |
1
1. insert : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return p; |
230 | } | |
231 | ||
232 | /** | |
233 | * Compares 2 null terminated char arrays | |
234 | */ | |
235 | public static int strcmp(char[] a, int startA, char[] b, int startB) { | |
236 |
3
1. strcmp : Changed increment from 1 to -1 → NO_COVERAGE 2. strcmp : Changed increment from 1 to -1 → NO_COVERAGE 3. strcmp : negated conditional → NO_COVERAGE |
for (; a[startA] == b[startB]; startA++, startB++) { |
237 |
1
1. strcmp : negated conditional → NO_COVERAGE |
if (a[startA] == 0) { |
238 |
1
1. strcmp : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return 0; |
239 | } | |
240 | } | |
241 |
2
1. strcmp : Replaced integer subtraction with addition → NO_COVERAGE 2. strcmp : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return a[startA] - b[startB]; |
242 | } | |
243 | ||
244 | /** | |
245 | * Compares a string with null terminated char array | |
246 | */ | |
247 | public static int strcmp(String str, char[] a, int start) { | |
248 | int i, d, len = str.length(); | |
249 |
3
1. strcmp : changed conditional boundary → NO_COVERAGE 2. strcmp : Changed increment from 1 to -1 → NO_COVERAGE 3. strcmp : negated conditional → NO_COVERAGE |
for (i = 0; i < len; i++) { |
250 |
2
1. strcmp : Replaced integer addition with subtraction → NO_COVERAGE 2. strcmp : Replaced integer subtraction with addition → NO_COVERAGE |
d = str.charAt(i) - a[start + i]; |
251 |
1
1. strcmp : negated conditional → NO_COVERAGE |
if (d != 0) { |
252 |
1
1. strcmp : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return d; |
253 | } | |
254 |
2
1. strcmp : Replaced integer addition with subtraction → NO_COVERAGE 2. strcmp : negated conditional → NO_COVERAGE |
if (a[start + i] == 0) { |
255 |
1
1. strcmp : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return d; |
256 | } | |
257 | } | |
258 |
2
1. strcmp : Replaced integer addition with subtraction → NO_COVERAGE 2. strcmp : negated conditional → NO_COVERAGE |
if (a[start + i] != 0) { |
259 |
3
1. strcmp : removed negation → NO_COVERAGE 2. strcmp : Replaced integer addition with subtraction → NO_COVERAGE 3. strcmp : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return -a[start + i]; |
260 | } | |
261 |
1
1. strcmp : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return 0; |
262 | ||
263 | } | |
264 | ||
265 | public static void strcpy(char[] dst, int di, char[] src, int si) { | |
266 |
1
1. strcpy : negated conditional → NO_COVERAGE |
while (src[si] != 0) { |
267 |
2
1. strcpy : Changed increment from 1 to -1 → NO_COVERAGE 2. strcpy : Changed increment from 1 to -1 → NO_COVERAGE |
dst[di++] = src[si++]; |
268 | } | |
269 | dst[di] = 0; | |
270 | } | |
271 | ||
272 | public static int strlen(char[] a, int start) { | |
273 | int len = 0; | |
274 |
4
1. strlen : changed conditional boundary → NO_COVERAGE 2. strlen : Changed increment from 1 to -1 → NO_COVERAGE 3. strlen : negated conditional → NO_COVERAGE 4. strlen : negated conditional → NO_COVERAGE |
for (int i = start; i < a.length && a[i] != 0; i++) { |
275 |
1
1. strlen : Changed increment from 1 to -1 → NO_COVERAGE |
len++; |
276 | } | |
277 |
1
1. strlen : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return len; |
278 | } | |
279 | ||
280 | public static int strlen(char[] a) { | |
281 |
1
1. strlen : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return strlen(a, 0); |
282 | } | |
283 | ||
284 | public int find(String key) { | |
285 | int len = key.length(); | |
286 |
1
1. find : Replaced integer addition with subtraction → NO_COVERAGE |
char[] strkey = new char[len + 1]; |
287 |
1
1. find : removed call to java/lang/String::getChars → NO_COVERAGE |
key.getChars(0, len, strkey, 0); |
288 | strkey[len] = 0; | |
289 | ||
290 |
1
1. find : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return find(strkey, 0); |
291 | } | |
292 | ||
293 | public int find(char[] key, int start) { | |
294 | int d; | |
295 | char p = root; | |
296 | int i = start; | |
297 | char c; | |
298 | ||
299 |
1
1. find : negated conditional → NO_COVERAGE |
while (p != 0) { |
300 |
1
1. find : negated conditional → NO_COVERAGE |
if (sc[p] == 0xFFFF) { |
301 |
1
1. find : negated conditional → NO_COVERAGE |
if (strcmp(key, i, kv.getArray(), lo[p]) == 0) { |
302 |
1
1. find : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return eq[p]; |
303 | } else { | |
304 |
1
1. find : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return -1; |
305 | } | |
306 | } | |
307 | c = key[i]; | |
308 |
1
1. find : Replaced integer subtraction with addition → NO_COVERAGE |
d = c - sc[p]; |
309 |
1
1. find : negated conditional → NO_COVERAGE |
if (d == 0) { |
310 |
1
1. find : negated conditional → NO_COVERAGE |
if (c == 0) { |
311 |
1
1. find : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return eq[p]; |
312 | } | |
313 |
1
1. find : Changed increment from 1 to -1 → NO_COVERAGE |
i++; |
314 | p = eq[p]; | |
315 |
2
1. find : changed conditional boundary → NO_COVERAGE 2. find : negated conditional → NO_COVERAGE |
} else if (d < 0) { |
316 | p = lo[p]; | |
317 | } else { | |
318 | p = hi[p]; | |
319 | } | |
320 | } | |
321 |
1
1. find : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return -1; |
322 | } | |
323 | ||
324 | public boolean knows(String key) { | |
325 |
3
1. knows : changed conditional boundary → NO_COVERAGE 2. knows : negated conditional → NO_COVERAGE 3. knows : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return (find(key) >= 0); |
326 | } | |
327 | ||
328 | // redimension the arrays | |
329 | private void redimNodeArrays(int newsize) { | |
330 |
2
1. redimNodeArrays : changed conditional boundary → NO_COVERAGE 2. redimNodeArrays : negated conditional → NO_COVERAGE |
int len = newsize < lo.length ? newsize : lo.length; |
331 | char[] na = new char[newsize]; | |
332 |
1
1. redimNodeArrays : removed call to java/lang/System::arraycopy → NO_COVERAGE |
System.arraycopy(lo, 0, na, 0, len); |
333 | lo = na; | |
334 | na = new char[newsize]; | |
335 |
1
1. redimNodeArrays : removed call to java/lang/System::arraycopy → NO_COVERAGE |
System.arraycopy(hi, 0, na, 0, len); |
336 | hi = na; | |
337 | na = new char[newsize]; | |
338 |
1
1. redimNodeArrays : removed call to java/lang/System::arraycopy → NO_COVERAGE |
System.arraycopy(eq, 0, na, 0, len); |
339 | eq = na; | |
340 | na = new char[newsize]; | |
341 |
1
1. redimNodeArrays : removed call to java/lang/System::arraycopy → NO_COVERAGE |
System.arraycopy(sc, 0, na, 0, len); |
342 | sc = na; | |
343 | } | |
344 | ||
345 | public int size() { | |
346 | return length; | |
347 | } | |
348 | ||
349 | public Object clone() { | |
350 | TernaryTree t = new TernaryTree(); | |
351 | t.lo = this.lo.clone(); | |
352 | t.hi = this.hi.clone(); | |
353 | t.eq = this.eq.clone(); | |
354 | t.sc = this.sc.clone(); | |
355 | t.kv = (CharVector)this.kv.clone(); | |
356 | t.root = this.root; | |
357 | t.freenode = this.freenode; | |
358 | t.length = this.length; | |
359 | ||
360 |
1
1. clone : mutated return of Object value for com/lowagie/text/pdf/hyphenation/TernaryTree::clone to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return t; |
361 | } | |
362 | ||
363 | /** | |
364 | * Recursively insert the median first and then the median of the | |
365 | * lower and upper halves, and so on in order to get a balanced | |
366 | * tree. The array of keys is assumed to be sorted in ascending | |
367 | * order. | |
368 | */ | |
369 | protected void insertBalanced(String[] k, char[] v, int offset, int n) { | |
370 | int m; | |
371 |
2
1. insertBalanced : changed conditional boundary → NO_COVERAGE 2. insertBalanced : negated conditional → NO_COVERAGE |
if (n < 1) { |
372 | return; | |
373 | } | |
374 |
1
1. insertBalanced : Replaced Shift Right with Shift Left → NO_COVERAGE |
m = n >> 1; |
375 | ||
376 |
3
1. insertBalanced : Replaced integer addition with subtraction → NO_COVERAGE 2. insertBalanced : Replaced integer addition with subtraction → NO_COVERAGE 3. insertBalanced : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::insert → NO_COVERAGE |
insert(k[m + offset], v[m + offset]); |
377 |
1
1. insertBalanced : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::insertBalanced → NO_COVERAGE |
insertBalanced(k, v, offset, m); |
378 | ||
379 |
5
1. insertBalanced : Replaced integer addition with subtraction → NO_COVERAGE 2. insertBalanced : Replaced integer addition with subtraction → NO_COVERAGE 3. insertBalanced : Replaced integer subtraction with addition → NO_COVERAGE 4. insertBalanced : Replaced integer subtraction with addition → NO_COVERAGE 5. insertBalanced : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::insertBalanced → NO_COVERAGE |
insertBalanced(k, v, offset + m + 1, n - m - 1); |
380 | } | |
381 | ||
382 | ||
383 | /** | |
384 | * Balance the tree for best search performance | |
385 | */ | |
386 | public void balance() { | |
387 | // System.out.print("Before root splitchar = "); System.out.println(sc[root]); | |
388 | ||
389 | int i = 0, n = length; | |
390 | String[] k = new String[n]; | |
391 | char[] v = new char[n]; | |
392 | Iterator iter = new Iterator(); | |
393 |
1
1. balance : negated conditional → NO_COVERAGE |
while (iter.hasMoreElements()) { |
394 | v[i] = iter.getValue(); | |
395 |
1
1. balance : Changed increment from 1 to -1 → NO_COVERAGE |
k[i++] = (String)iter.nextElement(); |
396 | } | |
397 |
1
1. balance : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::init → NO_COVERAGE |
init(); |
398 |
1
1. balance : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::insertBalanced → NO_COVERAGE |
insertBalanced(k, v, 0, n); |
399 | ||
400 | // With uniform letter distribution sc[root] should be around 'm' | |
401 | // System.out.print("After root splitchar = "); System.out.println(sc[root]); | |
402 | } | |
403 | ||
404 | /** | |
405 | * Each node stores a character (splitchar) which is part of | |
406 | * some key(s). In a compressed branch (one that only contain | |
407 | * a single string key) the trailer of the key which is not | |
408 | * already in nodes is stored externally in the kv array. | |
409 | * As items are inserted, key substrings decrease. | |
410 | * Some substrings may completely disappear when the whole | |
411 | * branch is totally decompressed. | |
412 | * The tree is traversed to find the key substrings actually | |
413 | * used. In addition, duplicate substrings are removed using | |
414 | * a map (implemented with a TernaryTree!). | |
415 | * | |
416 | */ | |
417 | public void trimToSize() { | |
418 | // first balance the tree for best performance | |
419 |
1
1. trimToSize : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::balance → NO_COVERAGE |
balance(); |
420 | ||
421 | // redimension the node arrays | |
422 |
1
1. trimToSize : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::redimNodeArrays → NO_COVERAGE |
redimNodeArrays(freenode); |
423 | ||
424 | // ok, compact kv array | |
425 | CharVector kx = new CharVector(); | |
426 | kx.alloc(1); | |
427 | TernaryTree map = new TernaryTree(); | |
428 |
1
1. trimToSize : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::compact → NO_COVERAGE |
compact(kx, map, root); |
429 | kv = kx; | |
430 |
1
1. trimToSize : removed call to com/lowagie/text/pdf/hyphenation/CharVector::trimToSize → NO_COVERAGE |
kv.trimToSize(); |
431 | } | |
432 | ||
433 | private void compact(CharVector kx, TernaryTree map, char p) { | |
434 | int k; | |
435 |
1
1. compact : negated conditional → NO_COVERAGE |
if (p == 0) { |
436 | return; | |
437 | } | |
438 |
1
1. compact : negated conditional → NO_COVERAGE |
if (sc[p] == 0xFFFF) { |
439 | k = map.find(kv.getArray(), lo[p]); | |
440 |
2
1. compact : changed conditional boundary → NO_COVERAGE 2. compact : negated conditional → NO_COVERAGE |
if (k < 0) { |
441 |
1
1. compact : Replaced integer addition with subtraction → NO_COVERAGE |
k = kx.alloc(strlen(kv.getArray(), lo[p]) + 1); |
442 |
1
1. compact : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::strcpy → NO_COVERAGE |
strcpy(kx.getArray(), k, kv.getArray(), lo[p]); |
443 |
1
1. compact : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::insert → NO_COVERAGE |
map.insert(kx.getArray(), k, (char)k); |
444 | } | |
445 | lo[p] = (char)k; | |
446 | } else { | |
447 |
1
1. compact : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::compact → NO_COVERAGE |
compact(kx, map, lo[p]); |
448 |
1
1. compact : negated conditional → NO_COVERAGE |
if (sc[p] != 0) { |
449 |
1
1. compact : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::compact → NO_COVERAGE |
compact(kx, map, eq[p]); |
450 | } | |
451 |
1
1. compact : removed call to com/lowagie/text/pdf/hyphenation/TernaryTree::compact → NO_COVERAGE |
compact(kx, map, hi[p]); |
452 | } | |
453 | } | |
454 | ||
455 | ||
456 | public Enumeration keys() { | |
457 |
1
1. keys : mutated return of Object value for com/lowagie/text/pdf/hyphenation/TernaryTree::keys to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return new Iterator(); |
458 | } | |
459 | ||
460 | public class Iterator implements Enumeration { | |
461 | ||
462 | /** | |
463 | * current node index | |
464 | */ | |
465 | int cur; | |
466 | ||
467 | /** | |
468 | * current key | |
469 | */ | |
470 | String curkey; | |
471 | ||
472 | private class Item implements Cloneable { | |
473 | char parent; | |
474 | char child; | |
475 | ||
476 | public Item() { | |
477 | parent = 0; | |
478 | child = 0; | |
479 | } | |
480 | ||
481 | public Item(char p, char c) { | |
482 | parent = p; | |
483 | child = c; | |
484 | } | |
485 | ||
486 | public Object clone() { | |
487 |
1
1. clone : mutated return of Object value for com/lowagie/text/pdf/hyphenation/TernaryTree$Iterator$Item::clone to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return new Item(parent, child); |
488 | } | |
489 | ||
490 | } | |
491 | ||
492 | /** | |
493 | * Node stack | |
494 | */ | |
495 | Stack ns; | |
496 | ||
497 | /** | |
498 | * key stack implemented with a StringBuffer | |
499 | */ | |
500 | StringBuffer ks; | |
501 | ||
502 | public Iterator() { | |
503 | cur = -1; | |
504 | ns = new Stack(); | |
505 | ks = new StringBuffer(); | |
506 |
1
1. |
rewind(); |
507 | } | |
508 | ||
509 | public void rewind() { | |
510 |
1
1. rewind : removed call to java/util/Stack::removeAllElements → NO_COVERAGE |
ns.removeAllElements(); |
511 |
1
1. rewind : removed call to java/lang/StringBuffer::setLength → NO_COVERAGE |
ks.setLength(0); |
512 | cur = root; | |
513 | run(); | |
514 | } | |
515 | ||
516 | public Object nextElement() { | |
517 | String res = curkey; | |
518 | cur = up(); | |
519 | run(); | |
520 |
1
1. nextElement : mutated return of Object value for com/lowagie/text/pdf/hyphenation/TernaryTree$Iterator::nextElement to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return res; |
521 | } | |
522 | ||
523 | public char getValue() { | |
524 |
2
1. getValue : changed conditional boundary → NO_COVERAGE 2. getValue : negated conditional → NO_COVERAGE |
if (cur >= 0) { |
525 |
1
1. getValue : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return eq[cur]; |
526 | } | |
527 |
1
1. getValue : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return 0; |
528 | } | |
529 | ||
530 | public boolean hasMoreElements() { | |
531 |
2
1. hasMoreElements : negated conditional → NO_COVERAGE 2. hasMoreElements : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return (cur != -1); |
532 | } | |
533 | ||
534 | /** | |
535 | * traverse upwards | |
536 | */ | |
537 | private int up() { | |
538 | Item i = new Item(); | |
539 | int res = 0; | |
540 | ||
541 |
1
1. up : negated conditional → NO_COVERAGE |
if (ns.empty()) { |
542 |
1
1. up : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return -1; |
543 | } | |
544 | ||
545 |
2
1. up : negated conditional → NO_COVERAGE 2. up : negated conditional → NO_COVERAGE |
if (cur != 0 && sc[cur] == 0) { |
546 |
1
1. up : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return lo[cur]; |
547 | } | |
548 | ||
549 | boolean climb = true; | |
550 | ||
551 |
1
1. up : negated conditional → NO_COVERAGE |
while (climb) { |
552 | i = (Item)ns.pop(); | |
553 |
1
1. up : Replaced integer addition with subtraction → NO_COVERAGE |
i.child++; |
554 | switch (i.child) { | |
555 | case 1: | |
556 |
1
1. up : negated conditional → NO_COVERAGE |
if (sc[i.parent] != 0) { |
557 | res = eq[i.parent]; | |
558 | ns.push(i.clone()); | |
559 | ks.append(sc[i.parent]); | |
560 | } else { | |
561 |
1
1. up : Replaced integer addition with subtraction → NO_COVERAGE |
i.child++; |
562 | ns.push(i.clone()); | |
563 | res = hi[i.parent]; | |
564 | } | |
565 | climb = false; | |
566 | break; | |
567 | ||
568 | case 2: | |
569 | res = hi[i.parent]; | |
570 | ns.push(i.clone()); | |
571 |
2
1. up : changed conditional boundary → NO_COVERAGE 2. up : negated conditional → NO_COVERAGE |
if (ks.length() > 0) { |
572 |
2
1. up : Replaced integer subtraction with addition → NO_COVERAGE 2. up : removed call to java/lang/StringBuffer::setLength → NO_COVERAGE |
ks.setLength(ks.length() - 1); // pop |
573 | } | |
574 | climb = false; | |
575 | break; | |
576 | ||
577 | default: | |
578 |
1
1. up : negated conditional → NO_COVERAGE |
if (ns.empty()) { |
579 |
1
1. up : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return -1; |
580 | } | |
581 | climb = true; | |
582 | break; | |
583 | } | |
584 | } | |
585 |
1
1. up : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return res; |
586 | } | |
587 | ||
588 | /** | |
589 | * traverse the tree to find next key | |
590 | */ | |
591 | private int run() { | |
592 |
1
1. run : negated conditional → NO_COVERAGE |
if (cur == -1) { |
593 |
1
1. run : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return -1; |
594 | } | |
595 | ||
596 | boolean leaf = false; | |
597 | while (true) { | |
598 | // first go down on low branch until leaf or compressed branch | |
599 |
1
1. run : negated conditional → NO_COVERAGE |
while (cur != 0) { |
600 |
1
1. run : negated conditional → NO_COVERAGE |
if (sc[cur] == 0xFFFF) { |
601 | leaf = true; | |
602 | break; | |
603 | } | |
604 | ns.push(new Item((char)cur, '\u0000')); | |
605 |
1
1. run : negated conditional → NO_COVERAGE |
if (sc[cur] == 0) { |
606 | leaf = true; | |
607 | break; | |
608 | } | |
609 | cur = lo[cur]; | |
610 | } | |
611 |
1
1. run : negated conditional → NO_COVERAGE |
if (leaf) { |
612 | break; | |
613 | } | |
614 | // nothing found, go up one node and try again | |
615 | cur = up(); | |
616 |
1
1. run : negated conditional → NO_COVERAGE |
if (cur == -1) { |
617 |
1
1. run : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return -1; |
618 | } | |
619 | } | |
620 | // The current node should be a data node and | |
621 | // the key should be in the key stack (at least partially) | |
622 | StringBuilder buf = new StringBuilder(ks.toString()); | |
623 |
1
1. run : negated conditional → NO_COVERAGE |
if (sc[cur] == 0xFFFF) { |
624 | int p = lo[cur]; | |
625 |
1
1. run : negated conditional → NO_COVERAGE |
while (kv.get(p) != 0) { |
626 |
1
1. run : Changed increment from 1 to -1 → NO_COVERAGE |
buf.append(kv.get(p++)); |
627 | } | |
628 | } | |
629 | curkey = buf.toString(); | |
630 |
1
1. run : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return 0; |
631 | } | |
632 | ||
633 | } | |
634 | ||
635 | public void printStats() { | |
636 |
1
1. printStats : removed call to java/io/PrintStream::println → NO_COVERAGE |
System.out.println("Number of keys = " + length); |
637 |
1
1. printStats : removed call to java/io/PrintStream::println → NO_COVERAGE |
System.out.println("Node count = " + freenode); |
638 | // System.out.println("Array length = " + Integer.toString(eq.length)); | |
639 |
1
1. printStats : removed call to java/io/PrintStream::println → NO_COVERAGE |
System.out.println("Key Array length = " |
640 | + kv.length()); | |
641 | ||
642 | /* | |
643 | * for(int i=0; i<kv.length(); i++) | |
644 | * if ( kv.get(i) != 0 ) | |
645 | * System.out.print(kv.get(i)); | |
646 | * else | |
647 | * System.out.println(""); | |
648 | * System.out.println("Keys:"); | |
649 | * for(Enumeration enum = keys(); enum.hasMoreElements(); ) | |
650 | * System.out.println(enum.nextElement()); | |
651 | */ | |
652 | ||
653 | } | |
654 | ||
655 | /* public static void main(String[] args) throws Exception { | |
656 | TernaryTree tt = new TernaryTree(); | |
657 | tt.insert("Carlos", 'C'); | |
658 | tt.insert("Car", 'r'); | |
659 | tt.insert("palos", 'l'); | |
660 | tt.insert("pa", 'p'); | |
661 | tt.trimToSize(); | |
662 | System.out.println((char)tt.find("Car")); | |
663 | System.out.println((char)tt.find("Carlos")); | |
664 | System.out.println((char)tt.find("alto")); | |
665 | tt.printStats(); | |
666 | }*/ | |
667 | ||
668 | } | |
669 | ||
Mutations | ||
116 |
1.1 |
|
140 |
1.1 |
|
142 |
1.1 2.2 3.3 |
|
143 |
1.1 2.2 |
|
145 |
1.1 |
|
146 |
1.1 |
|
152 |
1.1 |
|
153 |
1.1 2.2 3.3 |
|
154 |
1.1 2.2 |
|
164 |
1.1 |
|
168 |
1.1 |
|
170 |
1.1 |
|
172 |
1.1 2.2 |
|
174 |
1.1 |
|
176 |
1.1 |
|
181 |
1.1 |
|
184 |
1.1 |
|
188 |
1.1 |
|
192 |
1.1 2.2 |
|
195 |
1.1 |
|
196 |
1.1 |
|
212 |
1.1 |
|
213 |
1.1 |
|
217 |
1.1 2.2 |
|
219 |
1.1 |
|
220 |
1.1 |
|
221 |
1.1 |
|
229 |
1.1 |
|
236 |
1.1 2.2 3.3 |
|
237 |
1.1 |
|
238 |
1.1 |
|
241 |
1.1 2.2 |
|
249 |
1.1 2.2 3.3 |
|
250 |
1.1 2.2 |
|
251 |
1.1 |
|
252 |
1.1 |
|
254 |
1.1 2.2 |
|
255 |
1.1 |
|
258 |
1.1 2.2 |
|
259 |
1.1 2.2 3.3 |
|
261 |
1.1 |
|
266 |
1.1 |
|
267 |
1.1 2.2 |
|
274 |
1.1 2.2 3.3 4.4 |
|
275 |
1.1 |
|
277 |
1.1 |
|
281 |
1.1 |
|
286 |
1.1 |
|
287 |
1.1 |
|
290 |
1.1 |
|
299 |
1.1 |
|
300 |
1.1 |
|
301 |
1.1 |
|
302 |
1.1 |
|
304 |
1.1 |
|
308 |
1.1 |
|
309 |
1.1 |
|
310 |
1.1 |
|
311 |
1.1 |
|
313 |
1.1 |
|
315 |
1.1 2.2 |
|
321 |
1.1 |
|
325 |
1.1 2.2 3.3 |
|
330 |
1.1 2.2 |
|
332 |
1.1 |
|
335 |
1.1 |
|
338 |
1.1 |
|
341 |
1.1 |
|
360 |
1.1 |
|
371 |
1.1 2.2 |
|
374 |
1.1 |
|
376 |
1.1 2.2 3.3 |
|
377 |
1.1 |
|
379 |
1.1 2.2 3.3 4.4 5.5 |
|
393 |
1.1 |
|
395 |
1.1 |
|
397 |
1.1 |
|
398 |
1.1 |
|
419 |
1.1 |
|
422 |
1.1 |
|
428 |
1.1 |
|
430 |
1.1 |
|
435 |
1.1 |
|
438 |
1.1 |
|
440 |
1.1 2.2 |
|
441 |
1.1 |
|
442 |
1.1 |
|
443 |
1.1 |
|
447 |
1.1 |
|
448 |
1.1 |
|
449 |
1.1 |
|
451 |
1.1 |
|
457 |
1.1 |
|
487 |
1.1 |
|
506 |
1.1 |
|
510 |
1.1 |
|
511 |
1.1 |
|
520 |
1.1 |
|
524 |
1.1 2.2 |
|
525 |
1.1 |
|
527 |
1.1 |
|
531 |
1.1 2.2 |
|
541 |
1.1 |
|
542 |
1.1 |
|
545 |
1.1 2.2 |
|
546 |
1.1 |
|
551 |
1.1 |
|
553 |
1.1 |
|
556 |
1.1 |
|
561 |
1.1 |
|
571 |
1.1 2.2 |
|
572 |
1.1 2.2 |
|
578 |
1.1 |
|
579 |
1.1 |
|
585 |
1.1 |
|
592 |
1.1 |
|
593 |
1.1 |
|
599 |
1.1 |
|
600 |
1.1 |
|
605 |
1.1 |
|
611 |
1.1 |
|
616 |
1.1 |
|
617 |
1.1 |
|
623 |
1.1 |
|
625 |
1.1 |
|
626 |
1.1 |
|
630 |
1.1 |
|
636 |
1.1 |
|
637 |
1.1 |
|
639 |
1.1 |