001: /*
002: *
003: *
004: * Portions Copyright 2000-2007 Sun Microsystems, Inc. All Rights
005: * Reserved. Use is subject to license terms.
006: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
007: *
008: * This program is free software; you can redistribute it and/or
009: * modify it under the terms of the GNU General Public License version
010: * 2 only, as published by the Free Software Foundation.
011: *
012: * This program is distributed in the hope that it will be useful, but
013: * WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * General Public License version 2 for more details (a copy is
016: * included at /legal/license.txt).
017: *
018: * You should have received a copy of the GNU General Public License
019: * version 2 along with this work; if not, write to the Free Software
020: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
021: * 02110-1301 USA
022: *
023: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
024: * Clara, CA 95054 or visit www.sun.com if you need additional
025: * information or have any questions.
026: */
027:
028: /*****************************************************************************
029: * Copyright (C) The Apache Software Foundation. All rights reserved. *
030: * ------------------------------------------------------------------------- *
031: * This software is published under the terms of the Apache Software License *
032: * version 1.1, a copy of which has been included with this distribution in *
033: * the LICENSE file. *
034: *****************************************************************************/package com.sun.perseus.util;
035:
036: /**
037: * A simple Doubly Linked list class, designed to avoid
038: * O(n) behaviour on insert and delete.
039: *
040: * @author <a href="mailto:deweese@apache.org">Thomas DeWeese</a>
041: * @version $Id: DoublyLinkedList.java,v 1.2 2006/04/21 06:35:47 st125089 Exp $
042: */
043: public class DoublyLinkedList {
044:
045: // ========================================================================
046: // Inner static Node class
047: // ========================================================================
048:
049: /**
050: * Basic doubly linked list node interface.
051: */
052: public static class Node {
053: /**
054: * This node's next neighbour
055: */
056: private Node next = null;
057:
058: /**
059: * This node's previous neighbour
060: */
061: private Node prev = null;
062:
063: /**
064: * @return this node's next neighbour in the list
065: */
066: public final Node getNext() {
067: return next;
068: }
069:
070: /**
071: * @return this node's previous neighbour
072: */
073: public final Node getPrev() {
074: return prev;
075: }
076:
077: /**
078: * @param newNext the new next node
079: */
080: protected final void setNext(final Node newNext) {
081: next = newNext;
082: }
083:
084: /**
085: * @param newPrev the new previous node
086: */
087: protected final void setPrev(final Node newPrev) {
088: prev = newPrev;
089: }
090:
091: /**
092: * Unlink this node from it's current list...
093: */
094: protected final void unlink() {
095: if (getNext() != null) {
096: getNext().setPrev(getPrev());
097: }
098:
099: if (getPrev() != null) {
100: getPrev().setNext(getNext());
101: }
102: setNext(null);
103: setPrev(null);
104: }
105:
106: /**
107: * Link this node in, infront of nde (unlinks it's self
108: * before hand if needed).
109: * @param nde the node to link in before.
110: */
111: protected final void insertBefore(final Node nde) {
112: // Already here...
113: if (this == nde) {
114: return;
115: }
116:
117: if (getPrev() != null) {
118: unlink();
119: }
120:
121: // Actually insert this node...
122: if (nde == null) {
123: // empty lst...
124: setNext(this );
125: setPrev(this );
126: } else {
127: setNext(nde);
128: setPrev(nde.getPrev());
129: nde.setPrev(this );
130: if (getPrev() != null) {
131: getPrev().setNext(this );
132: }
133: }
134: }
135: }
136:
137: // ========================================================================
138: // End of inner static Node class
139: // ========================================================================
140:
141: /**
142: * The list's head. The previous node is the tail of the list
143: */
144: private Node head = null;
145:
146: /**
147: * The list's size
148: */
149: private int size = 0;
150:
151: /**
152: * Default constructor
153: */
154: public DoublyLinkedList() {
155: }
156:
157: /**
158: * @return the number of elements currently in the list.
159: */
160: public int getSize() {
161: return size;
162: }
163:
164: /**
165: * Removes all elements from the list.
166: */
167: public void empty() {
168: while (size > 0) {
169: pop();
170: }
171: }
172:
173: /**
174: * Get the current head element
175: * @return The current 'first' element in list.
176: */
177: public Node getHead() {
178: return head;
179: }
180:
181: /**
182: * Get the current tail element
183: * @return The current 'last' element in list.
184: */
185: public Node getTail() {
186: if (head != null) {
187: return head.getPrev();
188: } else {
189: return null;
190: }
191: }
192:
193: /**
194: * Adds <code>nde</code> to the head of the list.
195: * In perl this is called an 'unpop'. <code>nde</code> should
196: * not currently be part of any list.
197: * @param nde the node to add to the list.
198: */
199: public void add(final Node nde) {
200: nde.insertBefore(head);
201: head = nde;
202: size++;
203: }
204:
205: /**
206: * Removes nde from the list it is part of (should be this
207: * one, otherwise results are undefined). If nde is the
208: * current head element, then the next element becomes head,
209: * if there are no more elements the list becomes empty.
210: * @param nde <code>Node</code> to remove.
211: */
212: public void remove(final Node nde) {
213: if (nde == head) {
214: if (head.getNext() == head) {
215: head = null; // Last node...
216: } else {
217: head = head.getNext();
218: }
219: }
220: nde.unlink();
221: size--;
222: }
223:
224: /**
225: * Removes 'head' from list and returns it. Returns null if list is empty.
226: * @return current head element, next element becomes head.
227: */
228: public Node pop() {
229: if (head == null) {
230: return null;
231: }
232:
233: Node nde = head;
234: remove(nde);
235: return nde;
236: }
237:
238: /**
239: * Removes 'tail' from list and returns it. Returns null if list is empty.
240: * @return current tail element.
241: */
242: public Node unpush() {
243: if (head == null) {
244: return null;
245: }
246:
247: Node nde = getTail();
248: remove(nde);
249: return nde;
250: }
251:
252: /**
253: * @param nde the <code>Node</code> to add to tail of list
254: */
255: public void push(final Node nde) {
256: nde.insertBefore(head);
257: if (head == null) {
258: head = nde;
259: }
260: size++;
261: }
262:
263: /**
264: * @param nde the <code>Node</code> to put to the head of list
265: */
266: public void unpop(final Node nde) {
267: nde.insertBefore(head);
268: head = nde;
269: size++;
270: }
271: }
|