001: /*
002:
003: ============================================================================
004: The Apache Software License, Version 1.1
005: ============================================================================
006:
007: Copyright (C) 1999-2003 The Apache Software Foundation. All rights reserved.
008:
009: Redistribution and use in source and binary forms, with or without modifica-
010: tion, are permitted provided that the following conditions are met:
011:
012: 1. Redistributions of source code must retain the above copyright notice,
013: this list of conditions and the following disclaimer.
014:
015: 2. Redistributions in binary form must reproduce the above copyright notice,
016: this list of conditions and the following disclaimer in the documentation
017: and/or other materials provided with the distribution.
018:
019: 3. The end-user documentation included with the redistribution, if any, must
020: include the following acknowledgment: "This product includes software
021: developed by the Apache Software Foundation (http://www.apache.org/)."
022: Alternately, this acknowledgment may appear in the software itself, if
023: and wherever such third-party acknowledgments normally appear.
024:
025: 4. The names "Batik" and "Apache Software Foundation" must not be
026: used to endorse or promote products derived from this software without
027: prior written permission. For written permission, please contact
028: apache@apache.org.
029:
030: 5. Products derived from this software may not be called "Apache", nor may
031: "Apache" appear in their name, without prior written permission of the
032: Apache Software Foundation.
033:
034: THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
035: INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
036: FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
037: APACHE SOFTWARE FOUNDATION OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
038: INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLU-
039: DING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
040: OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
041: ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
042: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
043: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
044:
045: This software consists of voluntary contributions made by many individuals
046: on behalf of the Apache Software Foundation. For more information on the
047: Apache Software Foundation, please see <http://www.apache.org/>.
048:
049: */
050:
051: package org.apache.batik.util;
052:
053: /**
054: * A simple Doubly Linked list class, designed to avoid
055: * O(n) behaviour on insert and delete.
056: */
057: public class DoublyLinkedList {
058:
059: /**
060: * Basic doubly linked list node interface.
061: */
062: public static class Node {
063: private Node next = null;
064: private Node prev = null;
065:
066: public final Node getNext() {
067: return next;
068: }
069:
070: public final Node getPrev() {
071: return prev;
072: }
073:
074: protected final void setNext(Node newNext) {
075: next = newNext;
076: }
077:
078: protected final void setPrev(Node newPrev) {
079: prev = newPrev;
080: }
081:
082: /**
083: * Unlink this node from it's current list...
084: */
085: protected final void unlink() {
086: if (getNext() != null)
087: getNext().setPrev(getPrev());
088: if (getPrev() != null)
089: getPrev().setNext(getNext());
090:
091: setNext(null);
092: setPrev(null);
093: }
094:
095: /**
096: * Link this node in, infront of nde (unlinks it's self
097: * before hand if needed).
098: * @param nde the node to link in before.
099: */
100: protected final void insertBefore(Node nde) {
101: // Already here...
102: if (this == nde)
103: return;
104:
105: if (getPrev() != null)
106: unlink();
107:
108: // Actually insert this node...
109: if (nde == null) {
110: // empty lst...
111: setNext(this );
112: setPrev(this );
113: } else {
114: setNext(nde);
115: setPrev(nde.getPrev());
116: nde.setPrev(this );
117: if (getPrev() != null)
118: getPrev().setNext(this );
119: }
120: }
121: }
122:
123: private Node head = null;
124: private int size = 0;
125:
126: public DoublyLinkedList() {
127: }
128:
129: /**
130: * Returns the number of elements currently in the list.
131: */
132: public synchronized int getSize() {
133: return size;
134: }
135:
136: /**
137: * Removes all elements from the list.
138: */
139: public synchronized void empty() {
140: while (size > 0)
141: pop();
142: }
143:
144: /**
145: * Get the current head element
146: * @return The current 'first' element in list.
147: */
148: public Node getHead() {
149: return head;
150: }
151:
152: /**
153: * Get the current tail element
154: * @return The current 'last' element in list.
155: */
156: public Node getTail() {
157: return head.getPrev();
158: }
159:
160: /**
161: * Moves <tt>nde</tt> to the head of the list (equivilent to
162: * remove(nde); add(nde); but faster.
163: */
164: public void touch(Node nde) {
165: if (nde == null)
166: return;
167: nde.insertBefore(head);
168: head = nde;
169: }
170:
171: public void add(int index, Node nde) {
172: if (nde == null)
173: return;
174: if (index == 0) {
175: // This makes it the first element in the list.
176: nde.insertBefore(head);
177: head = nde;
178: } else if (index == size) {
179: // Because the list is circular this
180: // makes it the last element in the list.
181: nde.insertBefore(head);
182: } else {
183: Node after = head;
184: while (index != 0) {
185: after = after.getNext();
186: index--;
187: }
188: nde.insertBefore(after);
189: }
190: size++;
191: }
192:
193: /**
194: * Adds <tt>nde</tt> to the head of the list.
195: * In perl this is called an 'unpop'. <tt>nde</tt> should
196: * not currently be part of any list.
197: * @param nde the node to add to the list.
198: */
199: public void add(Node nde) {
200: if (nde == null)
201: return;
202: nde.insertBefore(head);
203: head = nde;
204: size++;
205: }
206:
207: /**
208: * Removes nde from the list it is part of (should be this
209: * one, otherwise results are undefined). If nde is the
210: * current head element, then the next element becomes head,
211: * if there are no more elements the list becomes empty.
212: * @param nde node to remove.
213: */
214: public void remove(Node nde) {
215: if (nde == null)
216: return;
217: if (nde == head) {
218: if (head.getNext() == head)
219: head = null; // Last node...
220: else
221: head = head.getNext();
222: }
223: nde.unlink();
224: size--;
225: }
226:
227: /**
228: * Removes 'head' from list and returns it. Returns null if list is empty.
229: * @returns current head element, next element becomes head.
230: */
231: public Node pop() {
232: if (head == null)
233: return null;
234:
235: Node nde = head;
236: remove(nde);
237: return nde;
238: }
239:
240: /**
241: * Removes 'tail' from list and returns it. Returns null if list is empty.
242: * @returns current tail element.
243: */
244: public Node unpush() {
245: if (head == null)
246: return null;
247:
248: Node nde = getTail();
249: remove(nde);
250: return nde;
251: }
252:
253: /**
254: * Adds <tt>nde</tt> to tail of list
255: */
256: public void push(Node nde) {
257: nde.insertBefore(head);
258: if (head == null)
259: head = nde;
260: size++;
261: }
262:
263: /**
264: * Adds <tt>nde</tt> to head of list
265: */
266: public void unpop(Node nde) {
267: nde.insertBefore(head);
268: head = nde;
269: size++;
270: }
271: }
|