001: /*
002:
003: Licensed to the Apache Software Foundation (ASF) under one or more
004: contributor license agreements. See the NOTICE file distributed with
005: this work for additional information regarding copyright ownership.
006: The ASF licenses this file to You under the Apache License, Version 2.0
007: (the "License"); you may not use this file except in compliance with
008: the License. You may obtain a copy of the License at
009:
010: http://www.apache.org/licenses/LICENSE-2.0
011:
012: Unless required by applicable law or agreed to in writing, software
013: distributed under the License is distributed on an "AS IS" BASIS,
014: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015: See the License for the specific language governing permissions and
016: limitations under the License.
017:
018: */
019: package org.apache.batik.util;
020:
021: /**
022: * A simple Doubly Linked list class, designed to avoid
023: * O(n) behaviour on insert and delete.
024: *
025: * @author <a href="mailto:thomas.deweese@kodak.com">Thomas DeWeese</a>
026: * @version $Id: DoublyLinkedList.java 475685 2006-11-16 11:16:05Z cam $
027: */
028: public class DoublyLinkedList {
029:
030: /**
031: * Basic doubly linked list node interface.
032: */
033: public static class Node {
034: private Node next = null;
035: private Node prev = null;
036:
037: public final Node getNext() {
038: return next;
039: }
040:
041: public final Node getPrev() {
042: return prev;
043: }
044:
045: protected final void setNext(Node newNext) {
046: next = newNext;
047: }
048:
049: protected final void setPrev(Node newPrev) {
050: prev = newPrev;
051: }
052:
053: /**
054: * Unlink this node from it's current list...
055: */
056: protected final void unlink() {
057: if (getNext() != null)
058: getNext().setPrev(getPrev());
059: if (getPrev() != null)
060: getPrev().setNext(getNext());
061:
062: setNext(null);
063: setPrev(null);
064: }
065:
066: /**
067: * Link this node in, infront of nde (unlinks it's self
068: * before hand if needed).
069: * @param nde the node to link in before.
070: */
071: protected final void insertBefore(Node nde) {
072: // Already here...
073: if (this == nde)
074: return;
075:
076: if (getPrev() != null)
077: unlink();
078:
079: // Actually insert this node...
080: if (nde == null) {
081: // empty lst...
082: setNext(this );
083: setPrev(this );
084: } else {
085: setNext(nde);
086: setPrev(nde.getPrev());
087: nde.setPrev(this );
088: if (getPrev() != null)
089: getPrev().setNext(this );
090: }
091: }
092: }
093:
094: private Node head = null;
095: private int size = 0;
096:
097: public DoublyLinkedList() {
098: }
099:
100: /**
101: * Returns the number of elements currently in the list.
102: */
103: public synchronized int getSize() {
104: return size;
105: }
106:
107: /**
108: * Removes all elements from the list.
109: */
110: public synchronized void empty() {
111: while (size > 0)
112: pop();
113: }
114:
115: /**
116: * Get the current head element
117: * @return The current 'first' element in list.
118: */
119: public Node getHead() {
120: return head;
121: }
122:
123: /**
124: * Get the current tail element
125: * @return The current 'last' element in list.
126: */
127: public Node getTail() {
128: return head.getPrev();
129: }
130:
131: /**
132: * Moves <tt>nde</tt> to the head of the list (equivilent to
133: * remove(nde); add(nde); but faster.
134: */
135: public void touch(Node nde) {
136: if (nde == null)
137: return;
138: nde.insertBefore(head);
139: head = nde;
140: }
141:
142: public void add(int index, Node nde) {
143: if (nde == null)
144: return;
145: if (index == 0) {
146: // This makes it the first element in the list.
147: nde.insertBefore(head);
148: head = nde;
149: } else if (index == size) {
150: // Because the list is circular this
151: // makes it the last element in the list.
152: nde.insertBefore(head);
153: } else {
154: Node after = head;
155: while (index != 0) {
156: after = after.getNext();
157: index--;
158: }
159: nde.insertBefore(after);
160: }
161: size++;
162: }
163:
164: /**
165: * Adds <tt>nde</tt> to the head of the list.
166: * In perl this is called an 'unpop'. <tt>nde</tt> should
167: * not currently be part of any list.
168: * @param nde the node to add to the list.
169: */
170: public void add(Node nde) {
171: if (nde == null)
172: return;
173: nde.insertBefore(head);
174: head = nde;
175: size++;
176: }
177:
178: /**
179: * Removes nde from the list it is part of (should be this
180: * one, otherwise results are undefined). If nde is the
181: * current head element, then the next element becomes head,
182: * if there are no more elements the list becomes empty.
183: * @param nde node to remove.
184: */
185: public void remove(Node nde) {
186: if (nde == null)
187: return;
188: if (nde == head) {
189: if (head.getNext() == head)
190: head = null; // Last node...
191: else
192: head = head.getNext();
193: }
194: nde.unlink();
195: size--;
196: }
197:
198: /**
199: * Removes 'head' from list and returns it. Returns null if list is empty.
200: * @return current head element, next element becomes head.
201: */
202: public Node pop() {
203: if (head == null)
204: return null;
205:
206: Node nde = head;
207: remove(nde);
208: return nde;
209: }
210:
211: /**
212: * Removes 'tail' from list and returns it. Returns null if list is empty.
213: * @return current tail element.
214: */
215: public Node unpush() {
216: if (head == null)
217: return null;
218:
219: Node nde = getTail();
220: remove(nde);
221: return nde;
222: }
223:
224: /**
225: * Adds <tt>nde</tt> to tail of list
226: */
227: public void push(Node nde) {
228: nde.insertBefore(head);
229: if (head == null)
230: head = nde;
231: size++;
232: }
233:
234: /**
235: * Adds <tt>nde</tt> to head of list
236: */
237: public void unpop(Node nde) {
238: nde.insertBefore(head);
239: head = nde;
240: size++;
241: }
242: }
|