001: package com.quadcap.util;
002:
003: /* Copyright 1997 - 2003 Quadcap Software. All rights reserved.
004: *
005: * This software is distributed under the Quadcap Free Software License.
006: * This software may be used or modified for any purpose, personal or
007: * commercial. Open Source redistributions are permitted. Commercial
008: * redistribution of larger works derived from, or works which bundle
009: * this software requires a "Commercial Redistribution License"; see
010: * http://www.quadcap.com/purchase.
011: *
012: * Redistributions qualify as "Open Source" under one of the following terms:
013: *
014: * Redistributions are made at no charge beyond the reasonable cost of
015: * materials and delivery.
016: *
017: * Redistributions are accompanied by a copy of the Source Code or by an
018: * irrevocable offer to provide a copy of the Source Code for up to three
019: * years at the cost of materials and delivery. Such redistributions
020: * must allow further use, modification, and redistribution of the Source
021: * Code under substantially the same terms as this license.
022: *
023: * Redistributions of source code must retain the copyright notices as they
024: * appear in each source code file, these license terms, and the
025: * disclaimer/limitation of liability set forth as paragraph 6 below.
026: *
027: * Redistributions in binary form must reproduce this Copyright Notice,
028: * these license terms, and the disclaimer/limitation of liability set
029: * forth as paragraph 6 below, in the documentation and/or other materials
030: * provided with the distribution.
031: *
032: * The Software is provided on an "AS IS" basis. No warranty is
033: * provided that the Software is free of defects, or fit for a
034: * particular purpose.
035: *
036: * Limitation of Liability. Quadcap Software shall not be liable
037: * for any damages suffered by the Licensee or any third party resulting
038: * from use of the Software.
039: */
040:
041: import java.io.*;
042:
043: import java.util.Enumeration;
044:
045: /**
046: * This class manages a doubly linked list, with head and tail. It's
047: * actually implemented as a circular list, with a single head pointer,
048: * and the tail is <code>head.prev</code>.<p>
049: *
050: * It would be good to have list primitives that worked well moving items
051: * from one list to another. moveFront(), in particular, should be able
052: * to splice an object out of one list and put it at the front of a
053: * different list.<p>
054: *
055: * @author Stan Bailes
056: */
057: public class DList {
058: /** The number of entries in the list. We are careful to track the
059: * size accurately. */
060: int size;
061:
062: /** The head of the list, null if the list is empty. Also, an indirect
063: * pointer to the tail of the list, since the list is linked circularly. */
064: DListItem head;
065:
066: /**
067: * Construct an empty DList.
068: */
069: public DList() {
070: head = null;
071: size = 0;
072: }
073:
074: /**
075: * Make the DList a specified size, adding null entries or deleting
076: * tail entries.
077: *
078: * @param newsize the new size of the list
079: */
080: public void resize(int newsize) {
081: while (size < newsize)
082: addBack((Object) null);
083: try {
084: while (size > newsize)
085: popBack();
086: } catch (ListException e) {
087: // rethrow as exception?
088: throw new RuntimeException(e.toString());
089: }
090: }
091:
092: /**
093: * Return the number of items in the list.
094: *
095: * @return the list's size
096: */
097: public int size() {
098: return this .size;
099: }
100:
101: /**
102: * Add an object to the front of the list.
103: *
104: * @param obj the object to add
105: */
106: public DListItem addFront(Object obj) {
107: DListItem d = new DListItem(obj);
108: addFront(d);
109: return d;
110: }
111:
112: /**
113: * Add an object after an existing list item.
114: *
115: * @param d the item after which the object is added
116: * @param obj the object to add
117: */
118: public void addAfter(DListItem d, Object obj) {
119: DListItem e = new DListItem(obj);
120: e.next = d.next;
121: e.next.prev = e;
122: e.prev = d;
123: d.next = e;
124: }
125:
126: /**
127: * Add an object before an existing list item.
128: *
129: * @param d the item before which the object is added
130: * @param obj the object to add
131: */
132: public void addBefore(DListItem d, Object obj) {
133: DListItem e = new DListItem(obj);
134: e.next = d;
135: e.prev = d.prev;
136: e.prev.next = e;
137: d.prev = e;
138: }
139:
140: /**
141: * Add an object to the back of the list.
142: * @param obj the object to add
143: */
144: public DListItem addBack(Object obj) {
145: DListItem d = new DListItem(obj);
146: addBack(d);
147: return d;
148: }
149:
150: /**
151: * Access the object at the front of the list. Throw an exception
152: * if the list is empty.
153: *
154: * @return the item at the head of the list
155: */
156: public DListItem head() throws ListException {
157: if (head == null)
158: throw new ListException("head() of empty list");
159: return head;
160: }
161:
162: /**
163: * Access the object at the back of the list. Throw an exception
164: * if the list is empty.
165: *
166: * @return the item at the tail of the list
167: */
168: public DListItem tail() throws ListException {
169: if (head == null)
170: throw new ListException("tail() of empty list");
171: return head.prev;
172: }
173:
174: /**
175: * Remove and return the item at the front of the list.
176: *
177: * @return the item at the head of the list
178: */
179: public DListItem popFront() throws ListException {
180: if (head == null)
181: throw new ListException("popFront() of empty list");
182: DListItem d = head;
183: unlink(d);
184: if (d == d.next)
185: head = null;
186: else
187: head = d.next;
188: return d;
189: }
190:
191: /**
192: * Remove and return the item at the back of the list.
193: *
194: * @return the item at the tail of the list
195: */
196: public DListItem popBack() throws ListException {
197: if (head == null)
198: throw new ListException("popBack() of empty list");
199: DListItem d = head.prev;
200: unlink(d);
201: if (d == d.next)
202: head = null;
203: return d;
204: }
205:
206: /**
207: * This method returns a string containing the display representation
208: * of this list.
209: */
210: public String toString() {
211: ByteArrayOutputStream bos = new ByteArrayOutputStream();
212: show(new PrintStream(bos));
213: return bos.toString();
214: }
215:
216: /**
217: * This method displays a list on the specified output stream.
218: */
219: public void show(PrintWriter os, String delim) {
220: String delimiter = "";
221: os.print("(");
222: if (head != null) {
223: boolean started = false;
224: for (DListItem d = head; !started || d != head; d = d.next) {
225: if (d.obj == null)
226: continue;
227: started = true;
228: os.print(delimiter + d.obj);
229: delimiter = delim;
230: }
231: }
232: os.println(")");
233: }
234:
235: /**
236: * This method displays a list using commas as delimiters.
237: *
238: * @param os the PrintStream on which to display this list.
239: */
240: public void show(PrintStream os) {
241: show(new PrintWriter(os), ", ");
242: }
243:
244: /**
245: * This method displays a list using commas as delimiters.
246: *
247: * @param os the PrintWriter on which to display this list.
248: */
249: public void show(PrintWriter os) {
250: show(os, ", ");
251: }
252:
253: //------------------------------------------------------------------------
254: // private implementation
255: //------------------------------------------------------------------------
256:
257: /**
258: * Move the specified item, which is assumed to be already in the
259: * list, to the front of this list.
260: *
261: * @param d the item to be placed at the front of this list.
262: */
263: public final void moveFront(DListItem d) {
264: if (d != head) {
265: d.next.prev = d.prev;
266: d.prev.next = d.next;
267: d.next = head != null ? head : d;
268: d.prev = head != null ? head.prev : d;
269: d.prev.next = d;
270: d.next.prev = d;
271: head = d;
272: }
273: }
274:
275: /* addFront */
276: final void addFront(DListItem d) {
277: addBack(d);
278: head = d;
279: }
280:
281: /* addBack */
282: final void addBack(DListItem d) {
283: size++;
284: d.next = head != null ? head : d;
285: d.prev = head != null ? head.prev : d;
286: d.prev.next = d;
287: d.next.prev = d;
288: if (head == null)
289: head = d;
290: }
291:
292: /* unlink */
293: public final void unlink(DListItem d) {
294: if (d != null) {
295: d.next.prev = d.prev;
296: d.prev.next = d.next;
297: if (d == d.next) {
298: head = null;
299: } else if (head == d) {
300: head = d.next;
301: }
302: size--;
303: }
304: }
305:
306: /**
307: * Return an enumeration of all of the items in this list.
308: */
309: public Enumeration elements() {
310: final DList this list = this ;
311: final DListItem this d = head;
312:
313: return new Enumeration() {
314: DList dlist = this list;
315: DListItem d = this d;
316: boolean first = true;
317:
318: public boolean hasMoreElements() {
319: return d != null && first || d != dlist.head;
320: }
321:
322: public Object nextElement() {
323: Object obj = d.obj;
324: d = d.next;
325: first = false;
326: return obj;
327: }
328: };
329: }
330: }
|