Source Code Cross Referenced for ModelList.java in  » IDE » DrJava » edu » rice » cs » drjava » model » definitions » reducedmodel » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » IDE » DrJava » edu.rice.cs.drjava.model.definitions.reducedmodel 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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:        }
w_w_w_._ja__v___a___2s_.___c_o_m___ | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.