KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > netbeans > mdr > persistence > btreeimpl > btreestorage > IntrusiveList


1 /*
2  * The contents of this file are subject to the terms of the Common Development
3  * and Distribution License (the License). You may not use this file except in
4  * compliance with the License.
5  *
6  * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7  * or http://www.netbeans.org/cddl.txt.
8  *
9  * When distributing Covered Code, include this CDDL Header Notice in each file
10  * and include the License file at http://www.netbeans.org/cddl.txt.
11  * If applicable, add the following below the CDDL Header, with the fields
12  * enclosed by brackets [] replaced by your own identifying information:
13  * "Portions Copyrighted [year] [name of copyright owner]"
14  *
15  * The Original Software is NetBeans. The Initial Developer of the Original
16  * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17  * Microsystems, Inc. All Rights Reserved.
18  */
19 package org.netbeans.mdr.persistence.btreeimpl.btreestorage;
20 import java.util.*;
21
22 /** A doubly linked list in which the objects contain their pointers.
23 * this is used in preference to forte.util.LinkedList since objects can
24 * be removed from it in constant time.
25 * <p>
26 * Although this implements java.util.List, it has a few restrictions:
27 * <ol>
28 * <li>
29 * Each element in an IntrusiveList must be a subclass of IntrusiveList.Member.
30 * <li>
31 * An element can only be a member of one IntrusiveList at a time, and
32 * can only appear at one postion in that list.
33 * </ol>
34 * An IntrusiveList will often be manipulated with its native operations
35 * ([add|remove][First|Last]) rather than via the List interface.
36 */
37 public class IntrusiveList extends AbstractSequentialList implements List {
38     /* list head */
39     private Member head;
40
41     private int mySize;
42     private int modLevel;
43
44     /** create a new list */
45     public IntrusiveList() {
46         head = new Member();
47         head.previous = head.next = head;
48     modLevel = 0;
49     }
50     
51     /** add an object at the head of the list */
52     public void addFirst(Member m) {
53         addAfter(m, head);
54     }
55
56     /** add an object at the end of the list */
57     public void addLast(Member m) {
58         addAfter(m, head.previous);
59     }
60
61     /** remove an object from the list */
62     public void remove(Member m) {
63     if (checkOwner(m)) {
64             m.previous.next = m.next;
65             m.next.previous = m.previous;
66             m.previous = m.next = null;
67             m.owner = null;
68             mySize--;
69             modLevel++;
70         }
71     }
72
73     /** remove the object at the head of the list */
74     public Member removeFirst() {
75         Member m = head.next;
76         if (m == head)
77             return null;
78         remove(m);
79         return m;
80     }
81
82     /** remove the object at the end of the list */
83     public Member removeLast() {
84         Member m = head.previous;
85         if (m == head)
86             return null;
87         remove(m);
88         return m;
89     }
90
91     /** return the number of elements in the list */
92     public int size() {
93         return mySize;
94     }
95     
96     /** return a ListIterator */
97     public ListIterator listIterator(int index) {
98         return new ListItr(modLevel, index);
99     }
100
101     /* Add after aother element */
102     private void addAfter(Member toAdd, Member afterMe) {
103         if (checkUnowned(toAdd)) {
104             toAdd.next = afterMe.next;
105             toAdd.previous = afterMe;
106             toAdd.next.previous = toAdd;
107             toAdd.previous.next = toAdd;
108             toAdd.owner = this;
109             mySize++;
110             modLevel++;
111         }
112     }
113
114     /* Check that the object is a member of this list */
115     private boolean checkOwner(Member m) {
116         return m.owner == this;
117     }
118
119     private boolean checkUnowned(Member m) {
120         if (m.owner != null) {
121             if (m.owner == this) return false;
122             throw new IllegalArgumentException JavaDoc (
123                 "The object is already a member of some list!");
124     }
125         return true;
126     }
127
128     /** This class is an iterator over IntrusiveLists, returned by
129     * IntrusiveList.listIterator. It exists to allow IntrusiveList to
130     * implement java.util.List as a modifiable, variable-sized list.
131     */
132     class ListItr implements ListIterator {
133     /* the member to be returned by next() */
134     private Member nextMember;
135
136     /* the last member returned by next() or previous() */
137     private Member lastReturned;
138
139     /* the index of the ember to be returned by next() */
140     private int nextIndex;
141
142     /* The modification level of the parent list the last time
143      * the iterator and parent synchronized
144      */
145     private int itrModLevel;
146
147     /* true if the last time we returned a Member, it was from next(),
148      * not previous(). Only valid if lastReturned is non-null.
149      */
150     boolean forward;
151
152     ListItr(int level, int index) {
153         if (index < 0 || index > mySize) {
154             throw new IndexOutOfBoundsException JavaDoc();
155         }
156         Member start = head;
157         for (int i = 0; i < index; i++) {
158             start = start.next;
159         }
160         nextMember = start.next;
161         lastReturned = null;
162         nextIndex = index;
163         itrModLevel = level;
164     }
165
166     /** See if there's a next member, i.e. if we haven't
167     * wrapped around to the head */
168     public boolean hasNext() {
169         checkLevel();
170         return nextMember != head;
171     }
172
173     /** See if there's a previous member, i.e. if we're not at the
174     * beginning */
175     public boolean hasPrevious() {
176         checkLevel();
177         return nextMember.previous != head;
178     }
179
180     /** Return the index of the next member */
181     public int nextIndex() {
182         checkLevel();
183         return nextIndex;
184     }
185
186     /** Return the index of the previous member */
187     public int previousIndex() {
188         checkLevel();
189         return nextIndex - 1;
190     }
191
192     /** Get the next member */
193     public Object JavaDoc next() {
194         checkLevel();
195         if (nextMember == head) {
196             throw new NoSuchElementException();
197         }
198         lastReturned = nextMember;
199         nextMember = nextMember.next;
200         nextIndex++;
201         forward = true;
202         return lastReturned;
203     }
204
205     /** Get the previous member */
206     public Object JavaDoc previous() {
207         checkLevel();
208         if (nextMember.previous == head) {
209             throw new NoSuchElementException();
210         }
211         lastReturned = nextMember.previous;
212         nextMember = lastReturned;
213         nextIndex--;
214         forward = false;
215         return lastReturned;
216     }
217
218     /** remove the last member returned by next or previous (if any) */
219     public void remove() {
220         checkLevel();
221         if (lastReturned == null) {
222             throw new IllegalStateException JavaDoc();
223         }
224         nextMember = lastReturned.next;
225         IntrusiveList.this.remove(lastReturned);
226         lastReturned = null;
227         if (forward) {
228             nextIndex--;
229         }
230         itrModLevel = modLevel;
231     }
232
233     /** Replace the last element returned by next or previous (if any) */
234     public void set(Object JavaDoc o) {
235         checkLevel();
236         if (lastReturned == null) {
237             throw new IllegalStateException JavaDoc();
238         }
239         Member m = (Member)o;
240         addAfter(m, lastReturned);
241         IntrusiveList.this.remove(lastReturned);
242         lastReturned = m;
243         nextMember = forward ? m.next : m;
244         itrModLevel = modLevel;
245     }
246
247     /** Insert a new member into the current position in the list
248     * (directly before the next element to be returned by next) */
249     public void add(Object JavaDoc o) {
250         checkLevel();
251         Member m = (Member)o;
252         addAfter(m, nextMember.previous);
253         nextIndex++;
254         lastReturned = null;
255         itrModLevel = modLevel;
256     }
257
258     /* Check for concurrent modifications */
259     private void checkLevel() {
260         if (itrModLevel != modLevel) {
261             throw new ConcurrentModificationException();
262         }
263     }
264     }
265
266     /** objects in an intrusive list must inherit from Member */
267     public static class Member {
268     IntrusiveList owner;
269         Member previous;
270         Member next;
271
272     }
273 }
274
Popular Tags