ModelList


1   /*BEGIN_COPYRIGHT_BLOCK
2    *
3    * This file is part of DrJava.  Download the current version of this project from http://www.drjava.org/
4    * or http://sourceforge.net/projects/drjava/
5    *
6    * DrJava Open Source License
7    * 
8    * Copyright (C) 2001-2005 JavaPLT group at Rice University (javaplt@rice.edu).  All rights reserved.
9    *
10   * Developed by:   Java Programming Languages Team, Rice University, http://www.cs.rice.edu/~javaplt/
11   * 
12   * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated 
13   * documentation files (the "Software"), to deal with the Software without restriction, including without limitation
14   * the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and 
15   * to permit persons to whom the Software is furnished to do so, subject to the following conditions:
16   * 
17   *     - Redistributions of source code must retain the above copyright notice, this list of conditions and the 
18   *       following disclaimers.
19   *     - Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the 
20   *       following disclaimers in the documentation and/or other materials provided with the distribution.
21   *     - Neither the names of DrJava, the JavaPLT, Rice University, nor the names of its contributors may be used to 
22   *       endorse or promote products derived from this Software without specific prior written permission.
23   *     - Products derived from this software may not be called "DrJava" nor use the term "DrJava" as part of their 
24   *       names without prior written permission from the JavaPLT group.  For permission, write to javaplt@rice.edu.
25   * 
26   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO 
27   * THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
28   * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF 
29   * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 
30   * WITH THE SOFTWARE.
31   * 
32   *END_COPYRIGHT_BLOCK*/
33  
34  package edu.rice.cs.drjava.model.definitions.reducedmodel;
35  
36  import edu.rice.cs.plt.collect.WeakHashSet;
37  import java.util.Set  ;
38  
39  /* TODO: convert ModelList representation to a doubly linked circular list;
40     separate head and tail nodes are ugly and unnecessary. */
41  
42  /**
43   * A list class with some extra features.
44   * Allows multiple iterators to make modifications to the same list
45   * without failing like the iterators for java.util.*List.
46   * @version $Id: ModelList.java 4095 2007-01-26 23:34:02Z c45207 $
47   */
48  class ModelList<T> {
49    private Node<T> _head;
50    private Node<T> _tail;
51    /** keep track of length for constant time length lookup */
52    private int _length;
53    /** a set of objects that can trigger and listen for updates to the list */
54    private Set<Iterator> _listeners;
55  
56    /**
57     * Constructor.
58     * Initializes the head and tail nodes, as well as the listener table
59     * and the length variable.
60     */
61    ModelList() {
62      // This node is the only node that exists in an empty list.
63      // If an Iterator points to this node, the iterator is considered
64      // to be in "initial position."
65      _head = new Node<T>();
66      _tail = new Node<T>();
67      _head.pred = null;
68      _head.succ = _tail;
69      _tail.pred = _head;
70      _tail.succ = null;
71      _length = 0;
72      /*
73       * We use a WeakHashSet so that listeners do not leak. That is, even
74       * if the dispose method is not called, when they are no longer
75       * strongly referenced, they will be automatically removed from the
76       * listener set.
77       */
78      _listeners = new WeakHashSet<Iterator>();
79    }
80  
81    /**
82     * Insert an item before a certain node in the list.
83     * Can never be called on head node.
84     */
85    private void insert(Node<T> point, T item) {
86      Node<T> ins = new Node<T>(item, point.pred, point);
87      point.pred.succ = ins;
88      point.pred = ins;
89      _length++;
90    }
91  
92    public void insertFront(T item) {
93      Iterator it = new Iterator();
94      it.insert(item);
95      it.dispose();
96    }
97  
98    /**
99     * Remove a node from the list.
100    * Can't remove head or tail node - exception thrown.
101    */
102   private void remove(Node<T> point) {
103     if ((point == _head) || (point == _tail))
104       throw new RuntimeException  ("Can't remove head.");
105     else
106     {
107       point.succ.pred = point.pred;
108       point.pred.succ = point.succ;
109       _length--;
110     }
111   }
112 
113   private void addListener(Iterator thing) {
114     this._listeners.add(thing);
115   }
116 
117   private void removeListener(Iterator thing) {
118     this._listeners.remove(thing);
119   }
120 
121   public int listenerCount() {
122     return _listeners.size();
123   }
124   /**
125    * Returns true if the list is empty.
126    */
127   public boolean isEmpty() {
128     return (_head.succ == _tail);
129   }
130 
131   public int length() {
132     return _length;
133   }
134 
135   /**
136    * Create a new iterator for this list.  The constructor for the
137    * iterator adds itself to the list's listeners.  The iterator
138    * must be notified of changes so it does not become out-of-date.
139    */
140   public Iterator getIterator() {
141     return new Iterator();
142   }
143 
144 
145   /**
146    * A node class for the list.
147    * Each node has a successor and predecessor, which is also a node
148    * as well as an item of type T.
149    * We keep it private inside this class so Node is never shown to
150    * the outside world to wreak havoc upon the list.
151    */
152   private static class Node<T> {
153     Node<T> pred;
154     Node<T> succ;
155     private T _item;
156 
157     Node() {
158       _item = null;
159       pred = this;
160       succ = this;
161     }
162 
163     Node(T item, Node<T> previous, Node<T> successor) {
164       _item = item;
165       pred = previous;
166       succ = successor;
167     }
168 
169     T getItem() {
170       return _item;
171     }
172   }
173 
174   /**
175    * Iterators for model list.
176    * The iterators are intimately coupled with the ModelList to which they
177    * belong.  They are the only public interface for manipulating
178    * ModelList.  The iterators are also fail-safe with regards to
179    * manipulation of the same list, although probably not thread-safe.
180    */
181   class Iterator {
182     private Node<T> _point;
183     private int _pos;
184 
185     /**
186      * Constructor.
187      * Initializes an iterator to point to its list's head.
188      */
189     public Iterator() {
190       _point = ModelList.this._head;
191       _pos = 0;
192       ModelList.this.addListener(this);
193     }
194 
195     /**
196      * Copy constructor.
197      * Creates a new iterator with the same values as the progenitor.
198      * Adds it to the list's set of listeners.
199      */
200     public Iterator(Iterator iter) {
201       _point = iter._point;
202       _pos = iter._pos;
203       ModelList.this.addListener(this);
204     }
205 
206     public Iterator copy() {
207       return new Iterator(this);
208     }
209 
210     /**
211      * an equals test
212      */
213     public boolean eq(Object   thing) {
214       return this._point == ((Iterator)(thing))._point;
215     }
216 
217     /**
218      * Force this iterator to take the values of the given iterator.
219      */
220     public void setTo(Iterator it) {
221       this._point = it._point;
222       this._pos = it._pos;
223     }
224 
225     /**
226      * Disposes of an iterator by removing it from the list's set of
227      * listeners.  When an iterator is no longer necessary, it
228      * should be disposed of.  Otherwise, there will be memory leaks
229      * because the listener set of the list provides a root reference
230      * for the duration of the list's existence.  What this means is that
231      * unless an iterator is disposed of, it will continue to exist even
232      * after garbage collection as long as the list itself is not
233      * garbage collected.
234      */
235     public void dispose() { ModelList.this.removeListener(this); }
236 
237     /** Return true if we're pointing at the head.*/
238     public boolean atStart() { return (_point == ModelList.this._head); }
239 
240     /** Return true if we're pointing at the tail. */
241     public boolean atEnd() { return (_point == ModelList.this._tail); }
242 
243     /** Return true if we're pointing at the node after the head. */
244     public boolean atFirstItem() { return (_point.pred == ModelList.this._head); }
245 
246     /** Return true if we're pointing at the node before the tail. */
247     public boolean atLastItem() { return (_point.succ == ModelList.this._tail); }
248 
249     /** Return the item associated with the current node. */
250     public T current() {
251       if (atStart())
252         throw new RuntimeException  ("Attempt to call current on an " +
253                                    "iterator in the initial position");
254       if (atEnd())
255         throw new RuntimeException  ("Attempt to call current on an " +
256                                    "iterator in the final position");
257       return _point.getItem();
258     }
259 
260     /**
261      * Return the item associated with the node before the current node.
262      */
263     public T prevItem() {
264       if (atFirstItem() || atStart() || ModelList.this.isEmpty())
265         throw new RuntimeException  ("No more previous items.");
266       return _point.pred.getItem();
267     }
268 
269     /**
270      * Return the item associated with the node after the current node.
271      */
272     public T nextItem() {
273       if (atLastItem() || atEnd() || ModelList.this.isEmpty())
274         throw new RuntimeException  ("No more following items.");
275       return _point.succ.getItem();
276     }
277 
278     /**
279      * Insert an item before the current item.
280      * If at the containing list's head, we need to move to the next node
281      * to perform the insert properly.  Otherwise, we'll get a null pointer
282      * exception because the function will try to insert the new item
283      * before the head.
284      *
285      * Ends pointing to inserted item.
286      */
287     public void insert(T item) {
288       //so as not to insert at head
289       if (this.atStart()) next();
290       ModelList.this.insert(_point, item);
291       _point = _point.pred; //puts pointer on inserted item
292       notifyOfInsert(_pos);
293 
294       //because notifyOfInsert will change the position of this iterator
295       //we must change it back.
296       _pos -= 1;
297     }
298 
299     /**
300      * Remove the current item from the list.
301      * Ends pointing to the node following the removed node.
302      * Throws exception if performed atStart() or atEnd().
303      */
304     public void remove() {
305       Node<T> tempNode = _point.succ;
306       ModelList.this.remove(_point);
307       _point = tempNode;
308       notifyOfRemove(_pos, _point);
309     }
310 
311     /**
312      * Move to the previous node.
313      * Throws exception atStart().
314      */
315     public void prev() {
316       if (atStart()) {
317         throw new RuntimeException  ("Can't cross list boundary.");
318       }
319       _point = _point.pred;
320       _pos--;
321     }
322 
323     /**
324      * Move to the next node.
325      * Throws exception atEnd().
326      */
327     public void next() {
328       if (atEnd()) throw new RuntimeException  ("Can't cross list boundary.");
329       _point = _point.succ;
330       _pos++;
331     }
332 
333     /**
334      * Delete all nodes between the current position of this and the
335      * current position of the given iterator.
336      *
337      * 1)Two iterators pointing to same node: do nothing
338      * 2)Iterator 2 is before iterator 1    : remove between iterator 2 and
339      *                                       iterator 1
340      * 3)Iterator 1 is before iterator 2    : remove between iterator 1 and
341      *                                       iterator 2
342      *
343      * Does not remove points iterators point to.
344      */
345     public void collapse(Iterator iter) {
346       int leftPos;
347       int rightPos;
348       Node<T> rightPoint;
349 
350       if (this._pos > iter._pos) {
351         leftPos = iter._pos;
352         rightPos = this._pos;
353         rightPoint = this._point;
354 
355         this._point.pred = iter._point;
356         iter._point.succ = this._point;
357         //determine new length
358         ModelList.this._length -= this._pos - iter._pos - 1;
359         notifyOfCollapse(leftPos, rightPos, rightPoint);
360       }
361       else if (this._pos < iter._pos) {
362         leftPos = this._pos;
363         rightPos = iter._pos;
364         rightPoint = iter._point;
365 
366         iter._point.pred = this._point;
367         this._point.succ = iter._point;
368 
369         ModelList.this._length -= iter._pos - this._pos - 1;
370         notifyOfCollapse(leftPos, rightPos, rightPoint);
371       }
372       else { // this._pos == iter._pos
373       }
374     }
375 
376     /** When an iterator inserts an item, it notifies other iterators
377      *  in the set of listeners so they can stay updated.
378      */
379     private void notifyOfInsert(int pos) {
380       for (Iterator listener : ModelList.this._listeners) {
381         if ( listener._pos < pos ) {
382           // do nothing
383         }
384         else { // ( next._pos == pos ) || next._pos > pos
385           listener._pos += 1;
386         }
387       } 
388     }
389 
390     /**
391      * When an iterator removes an item, it notifies other iterators
392      * in the set of listeners so they can stay updated.
393      */
394     private void notifyOfRemove(int pos, Node<T> point) {
395       for (Iterator listener : ModelList.this._listeners) {
396         if ( listener._pos < pos ) {
397           // do nothing
398         }
399         else if ( listener._pos == pos ) {
400           listener._point = point;
401         }
402         else { // next._pos > pos
403           listener._pos -= 1;
404         }
405       }
406     }
407 
408     /** When an iterator collapses part of the list, it notifies other iterators
409      *  in the set of listeners so they can stay updated.
410      */
411     private void notifyOfCollapse(int leftPos, int rightPos, Node<T> rightPoint) {
412       for (Iterator listener : ModelList.this._listeners) {
413         if ( listener._pos <= leftPos ) {
414           // do nothing
415         }
416         else if (( listener._pos > leftPos ) && ( listener._pos <= rightPos )) {
417           listener._pos = leftPos + 1;
418           listener._point = rightPoint;
419         }
420         else { // next._pos > rightPos
421           listener._pos -= (rightPos - leftPos - 1);
422         }
423       }
424     }
425   }
426 }
427
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags