LList


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