001: package org.drools.util;
002:
003: import java.io.Serializable;
004: import java.util.NoSuchElementException;
005:
006: /*
007: * Copyright 2005 JBoss Inc
008: *
009: * Licensed under the Apache License, Version 2.0 (the "License");
010: * you may not use this file except in compliance with the License.
011: * You may obtain a copy of the License at
012: *
013: * http://www.apache.org/licenses/LICENSE-2.0
014: *
015: * Unless required by applicable law or agreed to in writing, software
016: * distributed under the License is distributed on an "AS IS" BASIS,
017: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
018: * See the License for the specific language governing permissions and
019: * limitations under the License.
020: */
021:
022: /**
023: * This is a simple linked linked implementation. Each node must implement </code>LinkedListNode<code> so that it references
024: * the node before and after it. This way a node can be removed without having to scan the list to find it. This class
025: * does not provide an Iterator implementation as its designed for efficiency and not genericity. There are a number of
026: * ways to iterate the list.
027: * <p>
028: * Simple iterator:
029: * <pre>
030: * for ( LinkedListNode node = list.getFirst(); node != null; node = node.getNext() ) {
031: * }
032: * </pre>
033: *
034: * Iterator that pops the first entry:
035: * <pre>
036: * for ( LinkedListNode node = list.removeFirst(); node != null; node = list.removeFirst() ) {
037: * }
038: * </pre>
039: *
040: *
041: * @author <a href="mailto:mark.proctor@jboss.com">Mark Proctor</a>
042: * @author <a href="mailto:bob@werken.com">Bob McWhirter</a>
043: *
044: */
045: public class LinkedList implements Serializable {
046: private static final long serialVersionUID = 400L;
047:
048: private LinkedListNode firstNode;
049: private LinkedListNode lastNode;
050:
051: private int size;
052:
053: private LinkedListIterator iterator;
054:
055: /**
056: * Construct an empty <code>LinkedList</code>
057: */
058: public LinkedList() {
059: this .iterator = new LinkedListIterator();
060: }
061:
062: /**
063: * Add a <code>LinkedListNode</code> to the list. If the <code>LinkedList</code> is empty then the first and
064: * last nodes are set to the added node.
065: *
066: * @param node
067: * The <code>LinkedListNode</code> to be added
068: */
069: public void add(final LinkedListNode node) {
070: if (this .firstNode == null) {
071: this .firstNode = node;
072: this .lastNode = node;
073: ;
074: } else {
075: this .lastNode.setNext(node);
076: node.setPrevious(this .lastNode);
077: this .lastNode = node;
078: }
079: this .size++;
080: }
081:
082: /**
083: * Removes a <code>LinkedListNode</code> from the list. This works by attach the previous reference to the child reference.
084: * When the node to be removed is the first node it calls <code>removeFirst()</code>. When the node to be removed is the last node
085: * it calls <code>removeLast()</code>.
086: *
087: * @param node
088: * The <code>LinkedListNode</code> to be removed.
089: */
090: public void remove(final LinkedListNode node) {
091: if (this .firstNode == node) {
092: removeFirst();
093: } else if (this .lastNode == node) {
094: removeLast();
095: } else {
096: node.getPrevious().setNext(node.getNext());
097: (node.getNext()).setPrevious(node.getPrevious());
098: this .size--;
099: node.setPrevious(null);
100: node.setNext(null);
101: }
102: }
103:
104: /**
105: * Return the first node in the list
106: * @return
107: * The first <code>LinkedListNode</code>.
108: */
109: public final LinkedListNode getFirst() {
110: return this .firstNode;
111: }
112:
113: /**
114: * Return the last node in the list
115: * @return
116: * The last <code>LinkedListNode</code>.
117: */
118: public final LinkedListNode getLast() {
119: return this .lastNode;
120: }
121:
122: /**
123: * Remove the first node from the list. The next node then becomes the first node. If this is the last
124: * node then both first and last node references are set to null.
125: *
126: * @return
127: * The first <code>LinkedListNode</code>.
128: */
129: public LinkedListNode removeFirst() {
130: if (this .firstNode == null) {
131: return null;
132: }
133: final LinkedListNode node = this .firstNode;
134: this .firstNode = node.getNext();
135: node.setNext(null);
136: if (this .firstNode != null) {
137: this .firstNode.setPrevious(null);
138: } else {
139: this .lastNode = null;
140: }
141: this .size--;
142: return node;
143: }
144:
145: public void insertAfter(final LinkedListNode existingNode,
146: final LinkedListNode newNode) {
147: if (newNode.getPrevious() != null || newNode.getNext() != null) {
148: //do nothing if this node is already inserted somewhere
149: return;
150: }
151:
152: if (existingNode == null) {
153: if (this .isEmpty()) {
154: this .firstNode = newNode;
155: this .lastNode = newNode;
156: } else {
157: // if existing node is null, then insert it as a first node
158: final LinkedListNode node = this .firstNode;
159: node.setPrevious(newNode);
160: newNode.setNext(node);
161: this .firstNode = newNode;
162: }
163: } else if (existingNode == this .lastNode) {
164: existingNode.setNext(newNode);
165: newNode.setPrevious(existingNode);
166: this .lastNode = newNode;
167: } else {
168: (existingNode.getNext()).setPrevious(newNode);
169: newNode.setNext(existingNode.getNext());
170: existingNode.setNext(newNode);
171: newNode.setPrevious(existingNode);
172: }
173: this .size++;
174: }
175:
176: /**
177: * Remove the last node from the list. The previous node then becomes the last node. If this is the last
178: * node then both first and last node references are set to null.
179: *
180: * @return
181: * The first <code>LinkedListNode</code>.
182: */
183: public LinkedListNode removeLast() {
184: if (this .lastNode == null) {
185: return null;
186: }
187: final LinkedListNode node = this .lastNode;
188: this .lastNode = node.getPrevious();
189: node.setPrevious(null);
190: if (this .lastNode != null) {
191: this .lastNode.setNext(null);
192: } else {
193: this .firstNode = this .lastNode;
194: }
195: this .size--;
196: return node;
197: }
198:
199: /**
200: * @return
201: * boolean value indicating the empty status of the list
202: */
203: public final boolean isEmpty() {
204: return (this .firstNode == null);
205: }
206:
207: /**
208: * Iterates the list removing all the nodes until there are no more nodes to remove.
209: */
210: public void clear() {
211: while (removeFirst() != null) {
212: }
213: }
214:
215: /**
216: * @return
217: * return size of the list as an int
218: */
219: public final int size() {
220: return this .size;
221: }
222:
223: public int hashCode() {
224: final int PRIME = 31;
225: int result = 1;
226: for (LinkedListNode node = this .firstNode; node != null; node = node
227: .getNext()) {
228: result = PRIME * result + node.hashCode();
229: }
230: return result;
231: }
232:
233: public boolean equals(final Object object) {
234: if (object == this ) {
235: return true;
236: }
237:
238: if (object == null || !(object instanceof LinkedList)) {
239: return false;
240: }
241:
242: final LinkedList other = (LinkedList) object;
243:
244: if (this .size() != other.size()) {
245: return false;
246: }
247:
248: for (LinkedListNode this Node = this .firstNode, otherNode = other.firstNode; this Node != null
249: && otherNode != null; this Node = this Node.getNext(), otherNode = otherNode
250: .getNext()) {
251: if (!this Node.equals(otherNode)) {
252: return false;
253: }
254: }
255: return true;
256: }
257:
258: public Iterator iterator() {
259: this .iterator.reset(this );
260: return this .iterator;
261: }
262:
263: public java.util.Iterator javaUtilIterator() {
264: return new JavaUtilIterator(this );
265: }
266:
267: /**
268: * Returns a list iterator
269: * @return
270: */
271: public class LinkedListIterator implements Iterator, Serializable {
272: private LinkedList list;
273: private LinkedListNode current;
274:
275: public void reset(final LinkedList list) {
276: this .list = list;
277: this .current = this .list.firstNode;
278: }
279:
280: public Object next() {
281: if (this .current == null) {
282: return null;
283: }
284: final LinkedListNode node = this .current;
285: this .current = this .current.getNext();
286: return node;
287: }
288: }
289:
290: public static class JavaUtilIterator implements java.util.Iterator,
291: Serializable {
292: private LinkedList list;
293: private LinkedListNode currentNode;
294: private LinkedListNode nextNode;
295: private boolean immutable;
296:
297: public JavaUtilIterator(final LinkedList list) {
298: this (list, true);
299: }
300:
301: public JavaUtilIterator(final LinkedList list,
302: final boolean immutable) {
303: this .list = list;
304: this .nextNode = this .list.getFirst();
305: this .immutable = immutable;
306: }
307:
308: public boolean hasNext() {
309: return (this .nextNode != null);
310: }
311:
312: public Object next() {
313: this .currentNode = this .nextNode;
314: if (this .currentNode != null) {
315: this .nextNode = this .currentNode.getNext();
316: } else {
317: throw new NoSuchElementException(
318: "No more elements to return");
319: }
320: return this .currentNode;
321: }
322:
323: public void remove() {
324: if (this .immutable) {
325: throw new UnsupportedOperationException(
326: "This Iterator is immutable, you cannot call remove()");
327: }
328:
329: if (this .currentNode != null) {
330: this .list.remove(this .currentNode);
331: this .currentNode = null;
332: } else {
333: throw new IllegalStateException(
334: "No item to remove. Call next() before calling remove().");
335: }
336: }
337: }
338:
339: }
|