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