KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sun > jdo > spi > persistence > utility > DoubleLinkedList


1 /*
2  * The contents of this file are subject to the terms
3  * of the Common Development and Distribution License
4  * (the License). You may not use this file except in
5  * compliance with the License.
6  *
7  * You can obtain a copy of the license at
8  * https://glassfish.dev.java.net/public/CDDLv1.0.html or
9  * glassfish/bootstrap/legal/CDDLv1.0.txt.
10  * See the License for the specific language governing
11  * permissions and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL
14  * Header Notice in each file and include the License file
15  * at glassfish/bootstrap/legal/CDDLv1.0.txt.
16  * If applicable, add the following below the CDDL Header,
17  * with the fields enclosed by brackets [] replaced by
18  * you own identifying information:
19  * "Portions Copyrighted [year] [name of copyright owner]"
20  *
21  * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
22  */
23
24 /*
25  * ConnectionImpl.java
26  *
27  * Create on March 3, 2000
28  */
29
30 package com.sun.jdo.spi.persistence.utility;
31
32 /**
33  * This class defines a thread-safe double linked-list.
34  * The list is usable by any class that implements the
35  * com.forte.util.Linkable interface. This class allows
36  * a linkable object it be inserted or removed from anywhere
37  * in the list.
38  *
39  * RESTRICTION: An object can only be a member of 1 list
40  * at a time.
41  */
42 public class DoubleLinkedList
43 {
44
45     // Instance variables.
46
47     /**
48      * Head of linked list.
49      */
50     public Linkable head;
51
52     /**
53      * Tail of linked list.
54      */
55     public Linkable tail;
56
57     /**
58      * Size of linked list.
59      */
60     public int size;
61
62     /**
63      * Default constructor.
64      */
65     public DoubleLinkedList()
66     {
67         this.head = null;
68         this.size = 0;
69         this.tail = null;
70     }
71
72
73     // Public Methods.
74
75     /**
76      * Return the object at the head of a linked list.
77      *
78      */
79     public synchronized Linkable getHead()
80     {
81         return this.head;
82     }
83
84     /**
85      * Return the object at the tail of a linked list.
86      *
87      */
88     public synchronized Linkable getTail()
89     {
90         return this.tail;
91     }
92
93
94     /**
95      * Return size of the linked list.
96      *
97      */
98     public synchronized int getSize()
99     {
100         return this.size;
101     }
102
103
104     /**
105      * Insert an object at the head of a linked list.
106      *
107      */
108     public synchronized void insertAtHead(Linkable node)
109     {
110         if (node instanceof Linkable)
111         {
112             if (this.head == null)
113             {
114                 node.setNext(null); // Fixup node nextlink.
115 node.setPrevious(null); // Fixup node backlink.
116 this.head = node; // Insert node at head of list.
117 }
118             else
119             {
120                 Linkable oldHead = this.head; // Fixup current head node.
121 oldHead.setPrevious(node); // Set backlink to new node.
122 node.setNext(oldHead); // Fixup new node nextlink.
123 node.setPrevious(null); // Fixup new node backlink.
124 this.head = node; // Insert node at head of list.
125 }
126             if (this.tail == null) // If list was empty,
127 {
128                 this.tail = node; // Insert node at tail of list.
129 }
130             this.size++;
131         }
132     }
133
134     /**
135      * Insert an object at the tail of a linked list.
136      *
137      */
138     public synchronized void insertAtTail(Linkable node)
139     {
140         if (node instanceof Linkable)
141         {
142             if (this.tail == null)
143             {
144                 node.setNext(null); // Fixup node nextlink.
145 node.setPrevious(null); // Fixup node backlink.
146 this.tail = node; // Insert node at end of list.
147 }
148             else
149             {
150                 Linkable oldTail = this.tail; // Fixup current tail node.
151 oldTail.setNext(node); // Set backlink to new node.
152 node.setNext(null) ; // Fixup new node backlink.
153 node.setPrevious(oldTail); // Fixup new node nextlink.
154 this.tail = node; // Insert node at end of list.
155 }
156             if (this.head == null) // If list was empty,
157 {
158                 this.head = node; // Insert node at head of list.
159 }
160             this.size++;
161         }
162     }
163
164
165
166     /**
167      * Remove and return an object from the head of a linked list.
168      *
169      */
170     public synchronized Linkable removeFromHead()
171     {
172         Linkable node = this.head;
173         if (node instanceof Linkable)
174         {
175             this.head = node.getNext(); // Set head to next node.
176 if (this.head == null) // If we emptied the list,
177 {
178                 this.tail = null; // Fixup the tail pointer.
179 }
180             else
181             {
182                 this.head.setPrevious(null);// Clear head node backlink.
183 }
184             node.setNext(null); // Clear removed node nextlink.
185 node.setPrevious(null); // Clear romoved node backlink.
186 this.size--;
187         }
188         return node;
189     }
190
191     /**
192      * Remove and return an object from the tail of a linked list.
193      *
194      */
195     public synchronized Linkable removeFromTail()
196     {
197         Linkable node = this.tail;
198         if (node instanceof Linkable)
199         {
200             this.tail = node.getPrevious(); // Set tail to previous node.
201 if (this.tail == null) // If we emptied the list,
202 {
203                 this.head = null; // Fixup the head pointer.
204 }
205             else
206             {
207                 this.tail.setNext(null); // Clear tail node nextlink.
208 }
209             node.setNext(null); // Clear removed node nextlink.
210 node.setPrevious(null); // Clear removed node backlink.
211 this.size--;
212         }
213         return node;
214     }
215
216     /**
217      * Remove the specified object from anywhere in the linked list.
218      * This method is usually used by the object to remove itself
219      * from the list.
220      *
221      */
222     public synchronized void removeFromList(Linkable node)
223     {
224         if ((this.size <= 0) || ((this.head == null) && (this.tail == null)))
225         {
226             return;
227         }
228         if (node instanceof Linkable)
229         {
230             Linkable p = node.getPrevious(); // Reference to previous node.
231 Linkable n = node.getNext(); // Reference to next node.
232
233             if (p == null) // Is this the first (or only) node in the list?
234 {
235                 this.head = n; // Yes, set the head of the list to point to the next.
236 }
237             else
238             {
239                 p.setNext(n); // No, set the previous node to point to the next.
240 }
241
242             if (n == null) // Is this the last (or only) node in the list?
243 {
244                 this.tail = p; // Yes, set the tail to point to the previous.
245 }
246             else
247             {
248                 n.setPrevious(p); // No, set the next node to point to the previous.
249 }
250
251             node.setNext(null);
252             node.setPrevious(null);
253             this.size--;
254         }
255     }
256
257
258     /**
259      * Insert an object anywhere into the linked list.
260      *
261      * @param afternode the new node will be inserted after this node
262      * @param newnode the new node to be inserted
263      */
264     public synchronized void insertIntoList(Linkable afternode, Linkable newnode)
265     {
266         if ((newnode instanceof Linkable) && (afternode instanceof Linkable))
267         {
268             if (this.tail == afternode) // If inserting at the tail,
269 {
270                 this.insertAtTail(newnode); // Use insertAtTail method.
271 }
272             else
273             {
274                 Linkable nextnode = afternode.getNext();
275                 newnode.setNext(nextnode); // Point to next node.
276 newnode.setPrevious(afternode); // Point to previous node.
277 afternode.setNext(newnode); // Fixup backlink in afternode.
278 nextnode.setPrevious(newnode); // Fixup nextlink in next node.
279 }
280             this.size++;
281         }
282     }
283
284     /**
285      * Return a string representation of this DoubleLinkedList object.
286      * <p>
287      * @return String representation of this object.
288      */
289     public synchronized String JavaDoc toString()
290     {
291         /* boolean dif = ThreadContext.lgr().test
292             ( // Check for trace flag sp:1:1
293                 TraceLogger.CONFIGURATION,
294                 TraceLogger.SVC_SP,
295                 SPLogFlags.CFG_DIFFABLE_EXCEPTS,
296                 1
297             );
298         String buf = "DoubleLinkedList@\n";
299         if(!dif)
300         {
301             buf = buf + " head = " + this.head + "\n";
302             buf = buf + " tail = " + this.tail + "\n";
303         }
304         buf = buf + " size = " + this.size + "\n";
305         return buf;
306         */
307
308         return null;
309     }
310 }
311
312
Popular Tags