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