DList


1   package com.quadcap.util;
2   
3   /* Copyright 1997 - 2003 Quadcap Software.  All rights reserved.
4    *
5    * This software is distributed under the Quadcap Free Software License.
6    * This software may be used or modified for any purpose, personal or
7    * commercial.  Open Source redistributions are permitted.  Commercial
8    * redistribution of larger works derived from, or works which bundle
9    * this software requires a "Commercial Redistribution License"; see
10   * http://www.quadcap.com/purchase.
11   *
12   * Redistributions qualify as "Open Source" under  one of the following terms:
13   *   
14   *    Redistributions are made at no charge beyond the reasonable cost of
15   *    materials and delivery.
16   *
17   *    Redistributions are accompanied by a copy of the Source Code or by an
18   *    irrevocable offer to provide a copy of the Source Code for up to three
19   *    years at the cost of materials and delivery.  Such redistributions
20   *    must allow further use, modification, and redistribution of the Source
21   *    Code under substantially the same terms as this license.
22   *
23   * Redistributions of source code must retain the copyright notices as they
24   * appear in each source code file, these license terms, and the
25   * disclaimer/limitation of liability set forth as paragraph 6 below.
26   *
27   * Redistributions in binary form must reproduce this Copyright Notice,
28   * these license terms, and the disclaimer/limitation of liability set
29   * forth as paragraph 6 below, in the documentation and/or other materials
30   * provided with the distribution.
31   *
32   * The Software is provided on an "AS IS" basis.  No warranty is
33   * provided that the Software is free of defects, or fit for a
34   * particular purpose.  
35   *
36   * Limitation of Liability. Quadcap Software shall not be liable
37   * for any damages suffered by the Licensee or any third party resulting
38   * from use of the Software.
39   */
40  
41  import java.io.*;
42  
43  import java.util.Enumeration  ;
44  /**
45   * This class manages a doubly linked list, with head and tail.  It's
46   * actually implemented as a circular list, with a single head pointer,
47   * and the tail is <code>head.prev</code>.<p>
48   *
49   * It would be good to have list primitives that worked well moving items
50   * from one list to another.  moveFront(), in particular, should be able
51   * to splice an object out of one list and put it at the front of a
52   * different list.<p>
53   *
54   * @author Stan Bailes
55   */
56  public class DList {
57      /** The number of entries in the list.  We are careful to track the
58       * size accurately. */
59      int             size;
60  
61      /** The head of the list, null if the list is empty.  Also, an indirect
62       * pointer to the tail of the list, since the list is linked circularly. */
63      DListItem           head;
64  
65      /**
66       * Construct an empty DList.
67       */
68      public DList() {
69      head = null;
70      size = 0;
71      }
72  
73      /**
74       * Make the DList a specified size, adding null entries or deleting
75       * tail entries.
76       *
77       * @param newsize the new size of the list
78       */
79      public void resize(int newsize) {
80      while (size < newsize) addBack((Object  )null);
81      try {
82          while (size > newsize) popBack();
83      } catch (ListException e) {
84          // rethrow as exception?
85          throw new RuntimeException  (e.toString());
86      }
87      }
88  
89      /**
90       * Return the number of items in the list.
91       *
92       * @return the list's size
93       */
94      public int size() {
95      return this.size;
96      }
97  
98      /**
99       * Add an object to the front of the list.
100      *
101      * @param obj the object to add
102      */
103     public DListItem addFront(Object   obj) {
104     DListItem d = new DListItem(obj);
105     addFront(d);
106     return d;
107     }
108 
109     /**
110      * Add an object after an existing list item.
111      *
112      * @param d the item after which the object is added
113      * @param obj the object to add
114      */
115     public void addAfter(DListItem d, Object   obj) {
116     DListItem e = new DListItem(obj);
117     e.next = d.next;
118     e.next.prev = e;
119     e.prev = d;
120     d.next = e;
121     }
122 
123     /**
124      * Add an object before an existing list item.
125      *
126      * @param d the item before which the object is added
127      * @param obj the object to add
128      */
129     public void addBefore(DListItem d, Object   obj) {
130     DListItem e = new DListItem(obj);
131     e.next = d;
132     e.prev = d.prev;
133     e.prev.next = e;
134     d.prev = e;
135     }
136 
137     /**
138      * Add an object to the back of the list.
139      * @param obj the object to add
140      */
141     public DListItem addBack(Object   obj) {
142     DListItem d = new DListItem(obj);
143     addBack(d);
144     return d;
145     }
146 
147     /**
148      * Access the object at the front of the list.  Throw an exception
149      * if the list is empty.
150      *
151      * @return the item at the head of the list
152      */
153     public DListItem head() throws ListException {
154     if (head == null) throw new ListException("head() of empty list");
155     return head;
156     }
157 
158     /**
159      * Access the object at the back of the list.  Throw an exception
160      * if the list is empty.
161      *
162      * @return the item at the tail of the list
163      */
164     public DListItem tail() throws ListException {
165     if (head == null) throw new ListException("tail() of empty list");
166     return head.prev;
167     }
168 
169     /**
170      * Remove and return the item at the front of the list.
171      *
172      * @return the item at the head of the list
173      */
174     public DListItem popFront() throws ListException {
175     if (head == null) throw new ListException("popFront() of empty list");
176     DListItem d = head;
177     unlink(d);
178     if (d == d.next) head = null;
179     else head = d.next;
180     return d;
181     }
182     
183     /**
184      * Remove and return the item at the back of the list.
185      *
186      * @return the item at the tail of the list
187      */     
188     public DListItem popBack() throws ListException {
189     if (head == null) throw new ListException("popBack() of empty list");
190     DListItem d = head.prev;
191     unlink(d);
192     if (d == d.next) head = null;
193     return d;
194     }
195     
196     /**
197      * This method returns a string containing the display representation
198      * of this list.
199      */
200     public String   toString() {
201     ByteArrayOutputStream bos = new ByteArrayOutputStream();
202     show(new PrintStream(bos));
203     return bos.toString();
204     }
205 
206     /**
207      * This method displays a list on the specified output stream.
208      */
209     public void show(PrintWriter os, String   delim) {
210     String   delimiter = "";
211     os.print("(");
212     if (head != null) {
213         boolean started = false;
214         for (DListItem d = head; !started || d != head; d = d.next) {
215         if (d.obj == null) continue;
216         started = true;
217         os.print(delimiter + d.obj);
218         delimiter = delim;
219         }
220     }
221     os.println(")");
222     }
223 
224     /**
225      * This method displays a list using commas as delimiters.
226      *
227      * @param os the PrintStream on which to display this list.
228      */
229     public void show(PrintStream os) {
230     show(new PrintWriter(os), ", ");
231     }      
232 
233     /**
234      * This method displays a list using commas as delimiters.
235      *
236      * @param os the PrintWriter on which to display this list.
237      */
238     public void show(PrintWriter os) {
239     show(os, ", ");
240     }      
241 
242     //------------------------------------------------------------------------
243     // private implementation
244     //------------------------------------------------------------------------
245 
246     /**
247      * Move the specified item, which is assumed to be already in the
248      * list, to the front of this list.
249      *
250      * @param d the item to be placed at the front of this list.
251      */
252     public final void moveFront(DListItem d) {
253         if (d != head) {
254         d.next.prev = d.prev;
255         d.prev.next = d.next;
256             d.next = head != null ? head : d;
257             d.prev = head != null ? head.prev : d;
258             d.prev.next = d;
259             d.next.prev = d;
260             head = d;
261     }
262     }
263 
264     /* addFront */
265     final void addFront(DListItem d) {
266     addBack(d);
267     head = d;
268     }
269 
270     /* addBack */
271     final void addBack(DListItem d) {
272     size++;
273     d.next = head != null ? head : d;
274     d.prev = head != null ? head.prev : d;
275     d.prev.next = d;
276     d.next.prev = d;
277     if (head == null) head = d;
278     }
279 
280     /* unlink */
281     public final void unlink(DListItem d) {
282     if (d != null) {
283         d.next.prev = d.prev;
284         d.prev.next = d.next;
285         if (d == d.next) {
286         head = null;
287         } else if (head == d) {
288         head = d.next;
289         }
290         size--;
291     }
292     }
293 
294     /**
295      * Return an enumeration of all of the items in this list.
296      */
297     public Enumeration   elements() {
298     final DList thislist = this;
299     final DListItem thisd = head;
300     
301     return new Enumeration  () {
302         DList       dlist = thislist;
303         DListItem       d = thisd;
304         boolean     first = true;
305         public boolean hasMoreElements() {
306         return d != null && first || d != dlist.head;
307         }
308         public Object   nextElement() {
309         Object   obj = d.obj;
310         d = d.next;
311         first = false;
312         return obj;
313         }
314     };
315     }
316 }
317
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags