KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > ro > infoiasi > donald > compiler > cfg > Word


1 package ro.infoiasi.donald.compiler.cfg;
2
3 import java.util.*;
4
5 public class Word {
6     private Node first;
7     private Node last;
8     private int size;
9     
10     private class Node {
11         Symbol sym;
12         Node prev;
13         Node next;
14
15         Node(Symbol sym, Node prev, Node next) {
16             this.sym = sym;
17             this.prev = prev;
18             this.next = next;
19         }
20
21         Node() {
22             this(null, null, null);
23         }
24     }
25     
26     private class WordIteratorP implements WordIterator {
27         private final int LEFT = -1;
28         private final int NONE = 0;
29         private final int RIGHT = +1;
30         private Node p;
31         private Node n;
32         private int direction;
33         private int index;
34         
35         public WordIteratorP(boolean end) {
36             direction = NONE;
37             if (!end) {
38                 p = null;
39                 n = first;
40                 index = 0;
41             } else {
42                 p = last;
43                 n = null;
44                 index = Word.this.size();
45             }
46         }
47
48         public WordIteratorP() {
49             this(false);
50         }
51
52         public Object JavaDoc clone() {
53             try {
54                 return super.clone();
55             } catch (CloneNotSupportedException JavaDoc e) {
56                 throw new RuntimeException JavaDoc(e);
57             }
58         }
59
60
61         public boolean hasNext() {
62             return n != null;
63         }
64
65         public boolean hasNextTerminal() {
66             Node q = n;
67             while (q != null) {
68                 if (q.sym.isTerminal()) {
69                     return true;
70                 }
71                 q = q.next;
72             }
73             return false;
74         }
75
76         public boolean hasNextNonTerminal() {
77             Node q = n;
78             while (q != null) {
79                 if (!q.sym.isTerminal()) {
80                     return true;
81                 }
82                 q = q.next;
83             }
84             return false;
85         }
86
87         public Symbol getNext() {
88             return n.sym;
89         }
90
91         public Symbol next() {
92             direction = RIGHT;
93             index++;
94             p = n;
95             n = n.next;
96             return p.sym;
97         }
98
99         public Terminal nextTerminal() {
100             direction = RIGHT;
101             while (true) {
102                 index++;
103                 p = n;
104                 n = n.next;
105                 if (p.sym.isTerminal()) {
106                     return (Terminal)p.sym;
107                 }
108             }
109         }
110
111         public NonTerminal nextNonTerminal() {
112             direction = RIGHT;
113             while (true) {
114                 index++;
115                 p = n;
116                 n = n.next;
117                 if (!p.sym.isTerminal()) {
118                     return (NonTerminal)p.sym;
119                 }
120             }
121         }
122
123         public int nextIndex() {
124             return index;
125         }
126
127         public boolean hasPrev() {
128             return p != null;
129         }
130
131         public boolean hasPrevTerminal() {
132             Node q = p;
133             while (q != null) {
134                 if (q.sym.isTerminal()) {
135                     return true;
136                 }
137                 q = q.prev;
138             }
139             return false;
140         }
141
142         public boolean hasPrevNonTerminal() {
143             Node q = p;
144             while (q != null) {
145                 if (!q.sym.isTerminal()) {
146                     return true;
147                 }
148                 q = q.prev;
149             }
150             return false;
151         }
152
153         public Symbol getPrev() {
154             return p.sym;
155         }
156
157         public Symbol prev() {
158             direction = LEFT;
159             index--;
160             n = p;
161             p = p.prev;
162             return n.sym;
163         }
164
165         public Terminal prevTerminal() {
166             direction = LEFT;
167             while (true) {
168                 index--;
169                 n = p;
170                 p = p.prev;
171                 if (n.sym.isTerminal()) {
172                     return (Terminal)n.sym;
173                 }
174             }
175         }
176
177         public NonTerminal prevNonTerminal() {
178             direction = LEFT;
179             while (true) {
180                 index--;
181                 n = p;
182                 p = p.prev;
183                 if (!n.sym.isTerminal()) {
184                     return (NonTerminal)n.sym;
185                 }
186             }
187         }
188
189         public int prevIndex() {
190             return index-1;
191         }
192
193         public void remove() {
194             if (direction == LEFT) {
195                 Word.this.remove(n);
196             } else if (direction == RIGHT) {
197                 Word.this.remove(p);
198                 index--;
199             } else {
200                 throw new IllegalStateException JavaDoc();
201             }
202         }
203
204         public void set(Symbol sym) {
205             if (direction == LEFT) {
206                 n.sym = sym;
207             } else if (direction == RIGHT) {
208                 p.sym = sym;
209             } else {
210                 throw new IllegalStateException JavaDoc();
211             }
212         }
213
214         public void addBefore(Symbol sym) {
215             if (n == null) {
216                 addLast(sym);
217                 p = last;
218             } else {
219                 addBeforeNode(n, sym);
220                 p = n.prev;
221             }
222             index++;
223         }
224
225         public void addAfter(Symbol sym) {
226             if (p == null) {
227                 addFirst(sym);
228                 n = first;
229             } else {
230                 addAfterNode(p, sym);
231                 n = p.next;
232             }
233         }
234
235         public void addWordBefore(Word w) {
236             if (!w.isEmpty()) {
237                 if (n == null) {
238                     addWordLast(w);
239                     p = last;
240                 } else {
241                     addWordBeforeNode(n, w);
242                     p = n.prev;
243                 }
244                 index += w.size();
245             }
246         }
247
248         public void addWordAfter(Word w) {
249             if (!w.isEmpty()) {
250                 if (p == null) {
251                     addWordFirst(w);
252                     n = first;
253                 } else {
254                     addWordAfterNode(p, w);
255                     n = p.next;
256                 }
257             }
258         }
259
260         public Word suffix() {
261             Word w = new Word();
262             Node q = n;
263             while (q != null) {
264                 w.addLast(q.sym);
265                 q = q.next;
266             }
267             return w;
268             
269 /* if (n != null) {
270                 return new Word(n, last, size-index);
271             } else {
272                 return new Word();
273             }
274             //might be so wrong 2004-10-13
275             */
276         }
277
278         public Word prefix() {
279             Word w = new Word();
280             Node q = p;
281             while (q != null) {
282                 w.addFirst(q.sym);
283                 q = q.prev;
284             }
285             return w;
286             // cannot get the prefix without seting p.next
287 // to null which would break the word
288 // if (p != null) {
289 // return new Word(first, p, index);
290 // } else {
291 // return new Word();
292 // }
293 }
294     }
295
296     /** Total constructor (private) */
297     private Word(Node first, Node last, int size) {
298         this.first = first;
299         this.last = last;
300         this.size = size;
301     }
302
303     /** Constructs a new empty word (labmda/epsilon) */
304     public Word() {
305         this(null, null, 0);
306     }
307
308     /** Constructs a word as a copy of the specified word w */
309     public Word(Word w) {
310         this();
311         addWordLast(w);
312     }
313
314     /** Constructs a word containing only one simbol sym */
315     public Word(Symbol sym) {
316         this();
317         addLast(sym);
318 // this.first = this.last = new Node(sym, null, null);
319 // this.size = 1;
320 }
321
322     /** Constructs a word containing the symbols sym1 sym2 */
323     public Word(Symbol sym1, Symbol sym2) {
324         this(sym1);
325         addLast(sym2);
326     }
327
328     /** Constructs a new word from a collection of symbols.
329     The order of the symbols in the new word is the order in
330     witch they are returned by the collection's iterator. */
331     public Word(Collection c) {
332         this(null, null, 0);
333         Iterator it = c.iterator();
334         while (it.hasNext()) {
335             addLast((Symbol)it.next());
336         }
337     }
338
339     /** Returns a view of the portion of this word between the specified p and q
340     (both inclusive), The returned word is backed by this word, so non-structural
341     changes in the returned word are reflected in this word, and vice-versa */
342     private Word subWord(Node p, Node q) {
343         int s = 1;
344         Node it = p;
345         while (it != q) {
346             it = it.next;
347             s++;
348         }
349         return new Word(p, q, s);
350     }
351
352     /** Returns the number of symbols in this word. */
353     public int size() {
354         return size;
355     }
356
357     /** Returns true if this word has no symbols - lambda. */
358     public boolean isEmpty() {
359         return first == null;
360     }
361
362     public boolean equals(Object JavaDoc o) {
363         if (!(o instanceof Word)) {
364             return false;
365         }
366         Word w = (Word)o;
367         if (w.size() != size()) {
368             return false;
369         }
370         WordIterator it1 = iterator();
371         WordIterator it2 = w.iterator();
372         while (it1.hasNext()) {
373             if (!it1.next().equals(it2.next())) {
374                 return false;
375             }
376         }
377         return true;
378     }
379
380     public int hashCode() {
381         int code = size();
382         WordIterator it = iterator();
383         while (it.hasNext()) {
384             code = 37 * code + it.next().hashCode();
385         }
386         return code;
387     }
388
389
390     /** Returns true if this word contains the specified symbol. */
391     public boolean contains(Symbol sym) {
392         Node p = first;
393         while (p != null) {
394             if (p.sym.equals(sym)) {
395                 return true;
396             }
397             p = p.next;
398         }
399         return false;
400     }
401
402     /** Returns an iterator over the symbols in this word in proper sequence. */
403     public WordIterator iterator() {
404         return new WordIteratorP();
405     }
406
407     /** Returns an iterator over the symbols in this word in proper sequence.
408     If the given argument is true the iterator will start at the end of the sequence*/
409     public WordIterator iterator(boolean end) {
410         return new WordIteratorP(end);
411     }
412
413     /** Returns a array containing all of the
414     symbols in this word in proper sequence. */
415     public Symbol[] toArray() {
416         Symbol[] arr = new Symbol[size];
417         Node p = first;
418         int i = 0;
419         while (p != null) {
420             arr[i++] = p.sym;
421             p = p.next;
422         }
423         return arr;
424     }
425
426     /** Adds the specified symbol at the begining of this word */
427     public void addFirst(Symbol sym) {
428         Node p = new Node(sym, null, first);
429         if (first == null) {
430             first = last = p;
431         } else {
432             first.prev = p;
433             first = p;
434         }
435         size++;
436     }
437
438     /** Appends the specified symbol to the end of this word */
439     public void addLast(Symbol sym) {
440         Node p = new Node(sym, last, null);
441         if (last == null) {
442             first = last = p;
443         } else {
444             last.next = p;
445             last = p;
446         }
447         size++;
448     }
449
450     /** Adds the specified symbol before the specified node n */
451     private void addBeforeNode(Node n, Symbol sym) {
452         if (n == first) {
453             addFirst(sym);
454         } else {
455             Node p = n.prev;
456             Node q = new Node(sym, p, n);
457             p.next = q;
458             n.prev = q;
459             size++;
460         }
461     }
462
463     /** Adds the specified symbol after the specified node p */
464     private void addAfterNode(Node p, Symbol sym) {
465         if (p == last) {
466             addLast(sym);
467         } else {
468             Node n = p.next;
469             Node q = new Node(sym, p, n);
470             p.next = q;
471             n.prev = q;
472             size++;
473         }
474     }
475
476     /* Adds the specified word at the beginning of this word */
477     public void addWordFirst(Word w) {
478         if (!w.isEmpty()) {
479             Word temp = new Word(w);
480             if (first != null) {
481                 first.prev = temp.last;
482             }
483             if (temp.last != null) {
484                 temp.last.next = first;
485                 first = temp.first;
486             }
487             size += temp.size;
488         }
489     }
490
491     /* Appends the specified word to the end of this word */
492     public void addWordLast(Word w) {
493         if (!w.isEmpty()) {
494             WordIterator it = w.iterator();
495             while (it.hasNext()) {
496                 addLast(it.next());
497             }
498         }
499     }
500
501     /** Adds the specified symbol before the specified node n */
502     private void addWordBeforeNode(Node n, Word w) {
503         if (!w.isEmpty()) {
504             if (n == first) {
505                 addWordFirst(w);
506             } else {
507                 Node p = n.prev;
508                 Word temp = new Word(w);
509                 temp.first.prev = p;
510                 temp.last.next = n;
511                 p.next = temp.first;
512                 n.prev = temp.last;
513                 size += temp.size;
514             }
515         }
516     }
517
518     /** Adds the specified symbol after the specified node p */
519     private void addWordAfterNode(Node p, Word w) {
520         if (!w.isEmpty()) {
521             if (p == last) {
522                 addWordLast(w);
523             } else {
524                 Node n = p.next;
525                 Word temp = new Word(w);
526                 temp.first.prev = p;
527                 temp.last.next = n;
528                 p.next = temp.first;
529                 n.prev = temp.last;
530                 size += temp.size;
531             }
532         }
533     }
534
535     public Symbol getFirst() {
536         if (isEmpty()) {
537             throw new NoSuchElementException();
538         } else {
539             return first.sym;
540         }
541     }
542
543     public Symbol getLast() {
544         if (isEmpty()) {
545             throw new NoSuchElementException();
546         } else {
547             return last.sym;
548         }
549     }
550
551     /** Removes the specified node from the word */
552     private void remove(Node p) {
553         if (p.prev == null) {
554             first = p.next;
555         } else {
556             p.prev.next = p.next;
557         }
558         if (p.next == null) {
559             last = p.prev;
560         } else {
561             p.next.prev = p.prev;
562         }
563         size--;
564     }
565
566     public Symbol removeFirst() {
567         if (first == null) {
568             throw new NoSuchElementException();
569         } else {
570             Symbol ret = first.sym;
571             if (first.next == null) {
572                 first = last = null;
573                 size = 0;
574             } else {
575                 first.next.prev = null;
576                 first = first.next;
577                 size--;
578             }
579             return ret;
580         }
581     }
582
583     public Symbol removeLast() {
584         if (last == null) {
585             throw new NoSuchElementException();
586         } else {
587             Symbol ret = last.sym;
588             if (last.prev == null) {
589                 first = last = null;
590                 size = 0;
591             } else {
592                 last.prev.next = null;
593                 last = last.prev;
594                 size--;
595             }
596             return ret;
597         }
598     }
599
600     /* Removes the first occurrence in this word of the specified symbol */
601     public boolean remove(Symbol sym) {
602         Node p = first;
603         while (p != null) {
604             if (p.sym.equals(sym)) {
605                 remove(p);
606                 return true;
607             }
608             p = p.next;
609         }
610         return false;
611     }
612
613     /** Removes all of the symbols from this word */
614     public void clear() {
615         size = 0;
616         first = last = null;
617     }
618
619     /** Returnes the word obtained by reversing the
620     order of the simbols in this word */
621     public Word mirror() {
622         Word w = new Word();
623         WordIterator it = iterator();
624         while (it.hasNext()) {
625             w.addFirst(it.next());
626         }
627         return w;
628     }
629
630     public String JavaDoc toString() {
631         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
632         WordIterator it = iterator();
633         while (it.hasNext()) {
634             sb.append(it.next());
635             if (it.hasNext()) {
636                 sb.append(" ");
637             }
638         }
639         return sb.toString();
640     }
641
642
643     public static void main(String JavaDoc args[]) {
644         List symbols = new LinkedList();
645         NonTerminals v = new NonTerminals();
646         Terminals t = new Terminals();
647
648         symbols.add(t.addNew("LPARA"));
649         symbols.add(v.addNew("exp1"));
650         symbols.add(t.addNew("PLUS"));
651         symbols.add(v.addNew("exp2"));
652         symbols.add(t.addNew("RPARA"));
653         Word w = new Word(symbols);
654         System.out.println(w);
655
656         // Terminals only
657 System.out.print("Terminals only: {");
658         WordIterator it = w.iterator();
659         while (it.hasNextTerminal()) {
660             Symbol sym = it.nextTerminal();
661             System.out.print(sym+" ");
662         }
663         System.out.println("}");
664
665         // Terminals backwards
666 System.out.print("Terminals backwards: {");
667         while (it.hasPrevTerminal()) {
668             Symbol sym = it.prevTerminal();
669             System.out.print(sym+" ");
670         }
671         System.out.println("}");
672
673
674         // Non-Terminals only
675 System.out.print("NonTerminals only: {");
676         it = w.iterator();
677         while (it.hasNextNonTerminal()) {
678             Symbol sym = it.nextNonTerminal();
679             System.out.print(sym+" ");
680         }
681         System.out.println("}");
682
683         // Non-Terminals backwards
684 System.out.print("NonTerminals backwards: {");
685         while (it.hasPrevNonTerminal()) {
686             Symbol sym = it.prevNonTerminal();
687             System.out.print(sym+" ");
688         }
689         System.out.println("}");
690
691         Symbol[] s = w.toArray();
692         System.out.print("Array: {");
693         for (int i = 0; i<s.length; i++) {
694             System.out.print(s[i]+" ");
695         }
696         System.out.println("}");
697
698         System.out.println(w.contains(t.find(1)));
699         System.out.println(w.contains(t.find("EOF")));
700     }
701 }
702
Popular Tags