001: package antlr.collections.impl;
002:
003: /* ANTLR Translator Generator
004: * Project led by Terence Parr at http://www.cs.usfca.edu
005: * Software rights: http://www.antlr.org/license.html
006: */
007:
008: import antlr.collections.List;
009: import antlr.collections.Stack;
010:
011: import java.util.Enumeration;
012: import java.util.NoSuchElementException;
013:
014: import antlr.collections.impl.LLCell;
015:
016: /**A Linked List Implementation (not thread-safe for simplicity)
017: * (adds to the tail) (has an enumeration)
018: */
019: public class LList implements List, Stack {
020: protected LLCell head = null, tail = null;
021: protected int length = 0;
022:
023: /** Add an object to the end of the list.
024: * @param o the object to add
025: */
026: public void add(Object o) {
027: append(o);
028: }
029:
030: /** Append an object to the end of the list.
031: * @param o the object to append
032: */
033: public void append(Object o) {
034: LLCell n = new LLCell(o);
035: if (length == 0) {
036: head = tail = n;
037: length = 1;
038: } else {
039: tail.next = n;
040: tail = n;
041: length++;
042: }
043: }
044:
045: /**Delete the object at the head of the list.
046: * @return the object found at the head of the list.
047: * @exception NoSuchElementException if the list is empty.
048: */
049: protected Object deleteHead() throws NoSuchElementException {
050: if (head == null)
051: throw new NoSuchElementException();
052: Object o = head.data;
053: head = head.next;
054: length--;
055: return o;
056: }
057:
058: /**Get the ith element in the list.
059: * @param i the index (from 0) of the requested element.
060: * @return the object at index i
061: * NoSuchElementException is thrown if i out of range
062: */
063: public Object elementAt(int i) throws NoSuchElementException {
064: int j = 0;
065: for (LLCell p = head; p != null; p = p.next) {
066: if (i == j)
067: return p.data;
068: j++;
069: }
070: throw new NoSuchElementException();
071: }
072:
073: /**Return an enumeration of the list elements */
074: public Enumeration elements() {
075: return new LLEnumeration(this );
076: }
077:
078: /** How high is the stack? */
079: public int height() {
080: return length;
081: }
082:
083: /** Answers whether or not an object is contained in the list
084: * @param o the object to test for inclusion.
085: * @return true if object is contained else false.
086: */
087: public boolean includes(Object o) {
088: for (LLCell p = head; p != null; p = p.next) {
089: if (p.data.equals(o))
090: return true;
091: }
092: return false;
093: }
094:
095: // The next two methods make LLQueues and LLStacks easier.
096:
097: /** Insert an object at the head of the list.
098: * @param o the object to add
099: */
100: protected void insertHead(Object o) {
101: LLCell c = head;
102: head = new LLCell(o);
103: head.next = c;
104: length++;
105: if (tail == null)
106: tail = head;
107: }
108:
109: /**Return the length of the list.*/
110: public int length() {
111: return length;
112: }
113:
114: /** Pop the top element of the stack off.
115: * @return the top of stack that was popped off.
116: * @exception NoSuchElementException if the stack is empty.
117: */
118: public Object pop() throws NoSuchElementException {
119: Object o = deleteHead();
120: return o;
121: }
122:
123: // Satisfy the Stack interface now.
124:
125: /** Push an object onto the stack.
126: * @param o the object to push
127: */
128: public void push(Object o) {
129: insertHead(o);
130: }
131:
132: public Object top() throws NoSuchElementException {
133: if (head == null)
134: throw new NoSuchElementException();
135: return head.data;
136: }
137: }
|