LList


1   package antlr.collections.impl;
2   
3   /* ANTLR Translator Generator
4    * Project led by Terence Parr at http://www.jGuru.com
5    * Software rights: http://www.antlr.org/RIGHTS.html
6    *
7    * $Id: //depot/code/org.antlr/main/main/antlr/collections/impl/LList.java#4 $
8    */
9   
10  import antlr.collections.List;
11  import antlr.collections.Stack;
12  
13  import java.util.Enumeration  ;
14  import java.util.NoSuchElementException  ;
15  
16  import antlr.collections.impl.LLCell;
17  
18  /**A Linked List Implementation (not thread-safe for simplicity)
19   * (adds to the tail) (has an enumeration)
20   */
21  public class LList implements List, Stack {
22      protected LLCell head = null, tail = null;
23      protected int length = 0;
24  
25  
26      /** Add an object to the end of the list.
27       * @param o the object to add
28       */
29      public void add(Object   o) {
30          append(o);
31      }
32  
33      /** Append an object to the end of the list.
34       * @param o the object to append
35       */
36      public void append(Object   o) {
37          LLCell n = new LLCell(o);
38          if (length == 0) {
39              head = tail = n;
40              length = 1;
41          }
42          else {
43              tail.next = n;
44              tail = n;
45              length++;
46          }
47      }
48  
49      /**Delete the object at the head of the list.
50       * @return the object found at the head of the list.
51       * @exception NoSuchElementException if the list is empty.
52       */
53      protected Object   deleteHead() throws NoSuchElementException   {
54          if (head == null) throw new NoSuchElementException  ();
55          Object   o = head.data;
56          head = head.next;
57          length--;
58          return o;
59      }
60  
61      /**Get the ith element in the list.
62       * @param i the index (from 0) of the requested element.
63       * @return the object at index i
64       * NoSuchElementException is thrown if i out of range
65       */
66      public Object   elementAt(int i) throws NoSuchElementException   {
67          int j = 0;
68          for (LLCell p = head; p != null; p = p.next) {
69              if (i == j) return p.data;
70              j++;
71          }
72          throw new NoSuchElementException  ();
73      }
74  
75      /**Return an enumeration of the list elements */
76      public Enumeration   elements() {
77          return new LLEnumeration(this);
78      }
79  
80      /** How high is the stack? */
81      public int height() {
82          return length;
83      }
84  
85      /** Answers whether or not an object is contained in the list
86       * @param o the object to test for inclusion.
87       * @return true if object is contained else false.
88       */
89      public boolean includes(Object   o) {
90          for (LLCell p = head; p != null; p = p.next) {
91              if (p.data.equals(o)) return true;
92          }
93          return false;
94      }
95      // The next two methods make LLQueues and LLStacks easier.
96  
97      /** Insert an object at the head of the list.
98       * @param o the object to add
99       */
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) tail = head;
106     }
107 
108     /**Return the length of the list.*/
109     public int length() {
110         return length;
111     }
112 
113     /** Pop the top element of the stack off.
114      * @return the top of stack that was popped off.
115      * @exception NoSuchElementException if the stack is empty.
116      */
117     public Object   pop() throws NoSuchElementException   {
118         Object   o = deleteHead();
119         return o;
120     }
121     // Satisfy the Stack interface now.
122 
123     /** Push an object onto the stack.
124      * @param o the object to push
125      */
126     public void push(Object   o) {
127         insertHead(o);
128     }
129 
130     public Object   top() throws NoSuchElementException   {
131         if (head == null) throw new NoSuchElementException  ();
132         return head.data;
133     }
134 }
135
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags