001: /*BEGIN_COPYRIGHT_BLOCK
002: *
003: * Copyright (c) 2001-2007, JavaPLT group at Rice University (javaplt@rice.edu)
004: * All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions are met:
008: * * Redistributions of source code must retain the above copyright
009: * notice, this list of conditions and the following disclaimer.
010: * * Redistributions in binary form must reproduce the above copyright
011: * notice, this list of conditions and the following disclaimer in the
012: * documentation and/or other materials provided with the distribution.
013: * * Neither the names of DrJava, the JavaPLT group, Rice University, nor the
014: * names of its contributors may be used to endorse or promote products
015: * derived from this software without specific prior written permission.
016: *
017: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
018: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
019: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
020: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
021: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
022: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
023: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
024: * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
025: * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
026: * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
027: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
028: *
029: * This software is Open Source Initiative approved Open Source Software.
030: * Open Source Initative Approved is a trademark of the Open Source Initiative.
031: *
032: * This file is part of DrJava. Download the current version of this project
033: * from http://www.drjava.org/ or http://sourceforge.net/projects/drjava/
034: *
035: * END_COPYRIGHT_BLOCK*/
036:
037: package edu.rice.cs.drjava.model.definitions.reducedmodel;
038:
039: import edu.rice.cs.plt.collect.WeakHashSet;
040: import java.util.Set;
041:
042: /** A doubly-linked list class with header and trailer nodes. Allows multiple iterators to make modifications to the
043: * same list without failing unlike the iterators for java.util.*List.
044: * @version $Id: ModelList.java 4255 2007-08-28 19:17:37Z mgricken $
045: */
046: class ModelList<T> {
047: private Node<T> _head;
048: private Node<T> _tail;
049: /** keep track of length for constant time length lookup */
050: private int _length;
051: /** a set of objects that can trigger and listen for updates to the list */
052: private Set<Iterator> _listeners;
053:
054: /** Constructor. Initializes the head and tail nodes, as well as the listener table and the length variable. */
055: ModelList() {
056: // This node is the only node that exists in an empty list.
057: // If an Iterator points to this node, the iterator is considered to be in "initial position."
058: _head = new Node<T>();
059: _tail = new Node<T>();
060: _head._prev = null;
061: _head._next = _tail;
062: _tail._prev = _head;
063: _tail._next = null;
064: _length = 0;
065:
066: /* We use a WeakHashSet so that listeners do not leak. That is, even if the dispose method is not called, when they
067: * are no longer strongly referenced, they will be automatically removed from the listener set. */
068: _listeners = new WeakHashSet<Iterator>();
069: }
070:
071: public void insertFront(T item) {
072: insert(_head._next, item);
073: }
074:
075: /** Insert a node immediately before the specified point. Returns the inserted node. Assumes point is not head. */
076: private Node<T> insert(Node<T> point, T item) {
077: assert point != _head;
078: Node<T> newNode = point.insert(item);
079: _length++;
080: return newNode;
081: }
082:
083: /** Remove a node from the list. Assumes point is not head or tail. */
084: private void remove(Node<T> point) {
085: assert point != _head && point != _tail;
086: point.remove();
087: _length--;
088: }
089:
090: private void addListener(Iterator that) {
091: _listeners.add(that);
092: }
093:
094: private void removeListener(Iterator that) {
095: _listeners.remove(that);
096: }
097:
098: public int listenerCount() {
099: return _listeners.size();
100: }
101:
102: /** Returns true if the list is empty. */
103: public boolean isEmpty() {
104: return _head._next == _tail;
105: }
106:
107: public int length() {
108: return _length;
109: }
110:
111: /** Create a new iterator for this list and register it as one of the listeners which are notified when the list is
112: * updated.
113: */
114: public Iterator getIterator() {
115: return new Iterator();
116: }
117:
118: /** The Node class for ModelLists. The _prev and _next pointers are mutable. The _item field is null in _head and _tail. */
119: private static class Node<T> {
120: Node<T> _prev;
121: Node<T> _next;
122: T _item;
123:
124: /** Constructor for _head and _tail nodes. */
125: Node() {
126: }
127:
128: /** Constructor for nodes containing data. */
129: Node(T item, Node<T> pred, Node<T> succ) {
130: _item = item;
131: _prev = pred;
132: _next = succ;
133: }
134:
135: /** Insert a new node before "this". Returns the new node. Assumes that "this" is not the head node. */
136: Node<T> insert(T item) {
137: assert _prev != null;
138: Node<T> newNode = new Node<T>(item, _prev, this );
139: _prev._next = newNode;
140: _prev = newNode;
141: return newNode;
142: }
143:
144: /** Remove the current node. Assumes that this is neither _head not _tail. */
145: void remove() {
146: assert _prev != null && _next != null;
147: _prev._next = _next;
148: _next._prev = _prev;
149: }
150: }
151:
152: /** The uterator class for ModelList. Package private instead of private so that it can be extended. The methods of
153: * this class constitute the only public interface for traversing and modifying ModelList objects (other than
154: * insertFront). These iterators support concurrent modification from within the same thread. They are NOT thread
155: * safe.
156: */
157: class Iterator {
158: private Node<T> _point; // the current node
159: private int _pos; // the offset of _point within the list; _head has index 0
160:
161: /** Standard constructor that creates an iterator pointing to the list head (_head) and adds it the listeners. */
162: public Iterator() {
163: _point = _head;
164: _pos = 0;
165: addListener(this );
166: }
167:
168: /** Copy constructor that creates a copy of an existing iterator and adds it to the listeners. */
169: public Iterator(Iterator iter) {
170: _point = iter._point;
171: _pos = iter._pos;
172: addListener(this );
173: }
174:
175: public Iterator copy() {
176: return new Iterator(this );
177: }
178:
179: /** Tests "that" for equality with "this". */
180: public boolean eq(Iterator that) {
181: return _point == that._point;
182: }
183:
184: /** Force "this" iterator to take the values of "that". */
185: public void setTo(Iterator that) {
186: _point = that._point;
187: _pos = that._pos;
188: }
189:
190: /** Disposes of an iterator by removing it from the listeners. If an iterator becomes unreachable, it is
191: * automatically reclaimed as part of system garbage collection. The manual use of dispose() reduces the
192: * cost of notifying the listeners because it reduces the size of the listener set.
193: */
194: public void dispose() {
195: removeListener(this );
196: }
197:
198: /** Return true if we're pointing at the head.*/
199: public boolean atStart() {
200: return _point == _head;
201: }
202:
203: /** Return true if we're pointing at the tail. */
204: public boolean atEnd() {
205: return _point == _tail;
206: }
207:
208: /** Return true if we're pointing at the node after the head. */
209: public boolean atFirstItem() {
210: return _point._prev == _head;
211: }
212:
213: /** Return true if we're pointing at the node before the tail. */
214: public boolean atLastItem() {
215: return _point._next == _tail;
216: }
217:
218: /** Return the item associated with the current node. */
219: public T current() {
220: assert !atStart() && !atEnd();
221: return _point._item;
222: }
223:
224: /** Returns the item associated with the node before the current node. */
225: public T prevItem() {
226: assert !atStart() && !isEmpty() && !atFirstItem();
227: return _point._prev._item;
228: }
229:
230: /** Returns the item associated with the node after the current node. */
231: public T nextItem() {
232: assert !atStart() && !isEmpty() && !atLastItem();
233: return _point._next._item;
234: }
235:
236: public int pos() {
237: return _pos;
238: }
239:
240: /** Inserts an item before the current item. If current is head, we need to move to the next node
241: * to perform the insert properly. Otherwise, we'll get a null pointer exception because the function will try
242: * to insert the new item before the head. Ends pointing to inserted item.
243: */
244: public void insert(T item) {
245: //so as not to insert at head
246: if (atStart())
247: next();
248: _point = ModelList.this .insert(_point, item);
249: int savPos = _pos;
250: notifyOfInsert(_pos);
251:
252: _pos = savPos; // this._pos is incremented by notify; reverse this change
253: }
254:
255: /** Removes the current item from the list. Ends pointing to the node following the removed node.
256: * Throws exception if performed atStart() or atEnd().
257: */
258: public void remove() {
259: Node<T> succ = _point._next;
260: ModelList.this .remove(_point);
261: _point = succ;
262: notifyOfRemove(_pos, succ);
263: }
264:
265: /** Moves to the previous node. Throws exception atStart(). */
266: public void prev() {
267: assert !atStart();
268: _point = _point._prev;
269: _pos--;
270: }
271:
272: /** Moves to the next node. Throws exception atEnd(). */
273: public void next() {
274: assert !atEnd();
275: _point = _point._next;
276: _pos++;
277: }
278:
279: /** Delete all nodes between the current position of this and the current position of the given iterator.
280: * 1) Two iterators pointing to same node: do nothing
281: * 2) Iterator 2 is before iterator 1: remove between iterator 2 and iterator 1
282: * 3) Iterator 1 is before iterator 2: remove between iterator 1 and iterator 2
283: * Does not remove points iterators point to.
284: */
285: public void collapse(Iterator iter) {
286: int itPos = iter._pos;
287: int diff = Math.abs(_pos - itPos);
288: if (diff <= 1)
289: return; // _pos and iter.pos are either equal or adjacent
290:
291: int leftPos, rightPos;
292: Node<T> leftPoint, rightPoint;
293:
294: if (_pos > itPos) {
295: leftPos = itPos;
296: leftPoint = iter._point;
297: rightPos = _pos;
298: rightPoint = _point;
299: } else /* _pos < iter._pos */{
300: leftPos = _pos;
301: leftPoint = _point;
302: rightPos = itPos;
303: rightPoint = iter._point;
304: }
305:
306: rightPoint._prev = leftPoint;
307: leftPoint._next = rightPoint;
308: _length -= rightPos - leftPos - 1; //determine new length
309: notifyOfCollapse(leftPos, rightPos, rightPoint);
310: }
311:
312: /** Notifies the iterators in _listeners that a node has been inserted. */
313: private void notifyOfInsert(int pos) {
314: for (Iterator listener : _listeners) {
315: int lisPos = listener._pos;
316: if (lisPos >= pos)
317: listener._pos = lisPos + 1;
318: }
319: }
320:
321: /** Notifies the iterators in _listeners that a node has been removed. */
322: private void notifyOfRemove(int pos, Node<T> point) {
323: for (Iterator listener : _listeners) {
324: int lisPos = listener._pos;
325: if (lisPos == pos)
326: listener._point = point;
327: else if (lisPos > pos)
328: listener._pos = lisPos - 1;
329: }
330: }
331:
332: /** Notifies the iterators in _listeners that a range of nodes has been collapsed. */
333: private void notifyOfCollapse(int leftPos, int rightPos,
334: Node<T> rightPoint) {
335: for (Iterator listener : _listeners) {
336: int lisPos = listener._pos;
337: if (lisPos <= leftPos)
338: continue;
339: if (lisPos < rightPos) {
340: listener._pos = leftPos + 1;
341: listener._point = rightPoint;
342: } else { // lisPos >+ rightPos
343: listener._pos = lisPos - (rightPos - leftPos - 1);
344: }
345: }
346: }
347: }
348: }
|