001: ///////////////////////////////////////////////////////////////////////////////
002: // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
003: //
004: // This library is free software; you can redistribute it and/or
005: // modify it under the terms of the GNU Lesser General Public
006: // License as published by the Free Software Foundation; either
007: // version 2.1 of the License, or (at your option) any later version.
008: //
009: // This library is distributed in the hope that it will be useful,
010: // but WITHOUT ANY WARRANTY; without even the implied warranty of
011: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: // GNU General Public License for more details.
013: //
014: // You should have received a copy of the GNU Lesser General Public
015: // License along with this program; if not, write to the Free Software
016: // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
017: ///////////////////////////////////////////////////////////////////////////////
018:
019: package gnu.trove;
020:
021: import java.io.*;
022: import java.util.AbstractSequentialList;
023: import java.util.ListIterator;
024: import java.util.NoSuchElementException;
025:
026: /**
027: * A LinkedList implementation which holds instances of type
028: * <tt>TLinkable</tt>.
029: *
030: * <p>Using this implementation allows you to get java.util.LinkedList
031: * behavior (a doubly linked list, with Iterators that support insert
032: * and delete operations) without incurring the overhead of creating
033: * <tt>Node</tt> wrapper objects for every element in your list.</p>
034: *
035: * <p>The requirement to achieve this time/space gain is that the
036: * Objects stored in the List implement the <tt>TLinkable</tt>
037: * interface.</p>
038: *
039: * <p>The limitations are that you cannot put the same object into
040: * more than one list or more than once in the same list. You must
041: * also ensure that you only remove objects that are actually in the
042: * list. That is, if you have an object A and lists l1 and l2, you
043: * must ensure that you invoke List.remove(A) on the correct list. It
044: * is also forbidden to invoke List.remove() with an unaffiliated
045: * TLinkable (one that belongs to no list): this will destroy the list
046: * you invoke it on.</p>
047: *
048: * <p>
049: * Created: Sat Nov 10 15:25:10 2001
050: * </p>
051: *
052: * @author Eric D. Friedman
053: * @version $Id: TLinkedList.java,v 1.12 2007/11/01 16:08:14 robeden Exp $
054: * @see gnu.trove.TLinkable
055: */
056:
057: public class TLinkedList<T extends TLinkable> extends
058: AbstractSequentialList<T> implements Externalizable {
059:
060: static final long serialVersionUID = 1L;
061:
062: /** the head of the list */
063: protected T _head;
064: /** the tail of the list */
065: protected T _tail;
066: /** the number of elements in the list */
067: protected int _size = 0;
068:
069: /**
070: * Creates a new <code>TLinkedList</code> instance.
071: *
072: */
073: public TLinkedList() {
074: super ();
075: }
076:
077: /**
078: * Returns an iterator positioned at <tt>index</tt>. Assuming
079: * that the list has a value at that index, calling next() will
080: * retrieve and advance the iterator. Assuming that there is a
081: * value before <tt>index</tt> in the list, calling previous()
082: * will retrieve it (the value at index - 1) and move the iterator
083: * to that position. So, iterating from front to back starts at
084: * 0; iterating from back to front starts at <tt>size()</tt>.
085: *
086: * @param index an <code>int</code> value
087: * @return a <code>ListIterator</code> value
088: */
089: public ListIterator<T> listIterator(int index) {
090: return new IteratorImpl(index);
091: }
092:
093: /**
094: * Returns the number of elements in the list.
095: *
096: * @return an <code>int</code> value
097: */
098: public int size() {
099: return _size;
100: }
101:
102: /**
103: * Inserts <tt>linkable</tt> at index <tt>index</tt> in the list.
104: * All values > index are shifted over one position to accommodate
105: * the new addition.
106: *
107: * @param index an <code>int</code> value
108: * @param linkable an object of type TLinkable
109: */
110: public void add(int index, T linkable) {
111: if (index < 0 || index > size()) {
112: throw new IndexOutOfBoundsException("index:" + index);
113: }
114: insert(index, linkable);
115: }
116:
117: /**
118: * Appends <tt>linkable</tt> to the end of the list.
119: *
120: * @param linkable an object of type TLinkable
121: * @return always true
122: */
123: public boolean add(T linkable) {
124: insert(_size, linkable);
125: return true;
126: }
127:
128: /**
129: * Inserts <tt>linkable</tt> at the head of the list.
130: *
131: * @param linkable an object of type TLinkable
132: */
133: public void addFirst(T linkable) {
134: insert(0, linkable);
135: }
136:
137: /**
138: * Adds <tt>linkable</tt> to the end of the list.
139: *
140: * @param linkable an object of type TLinkable
141: */
142: public void addLast(T linkable) {
143: insert(size(), linkable);
144: }
145:
146: /**
147: * Empties the list.
148: *
149: */
150: public void clear() {
151: if (null != _head) {
152: for (TLinkable link = _head.getNext(); link != null; link = link
153: .getNext()) {
154: TLinkable prev = link.getPrevious();
155: prev.setNext(null);
156: link.setPrevious(null);
157: }
158: _head = _tail = null;
159: }
160: _size = 0;
161: }
162:
163: /**
164: * Copies the list's contents into a native array. This will be a
165: * shallow copy: the Tlinkable instances in the Object[] array
166: * have links to one another: changing those will put this list
167: * into an unpredictable state. Holding a reference to one
168: * element in the list will prevent the others from being garbage
169: * collected unless you clear the next/previous links. <b>Caveat
170: * programmer!</b>
171: *
172: * @return an <code>Object[]</code> value
173: */
174: public Object[] toArray() {
175: Object[] o = new Object[_size];
176: int i = 0;
177: for (TLinkable link = _head; link != null; link = link
178: .getNext()) {
179: o[i++] = link;
180: }
181: return o;
182: }
183:
184: /**
185: * Copies the list to a native array, destroying the next/previous
186: * links as the copy is made. This list will be emptied after the
187: * copy (as if clear() had been invoked). The Object[] array
188: * returned will contain TLinkables that do <b>not</b> hold
189: * references to one another and so are less likely to be the
190: * cause of memory leaks.
191: *
192: * @return an <code>Object[]</code> value
193: */
194: public Object[] toUnlinkedArray() {
195: Object[] o = new Object[_size];
196: int i = 0;
197: for (T link = _head, tmp = null; link != null; i++) {
198: o[i] = link;
199: tmp = link;
200: link = (T) link.getNext();
201: tmp.setNext(null); // clear the links
202: tmp.setPrevious(null);
203: }
204: _size = 0; // clear the list
205: _head = _tail = null;
206: return o;
207: }
208:
209: /**
210: * A linear search for <tt>o</tt> in the list.
211: *
212: * @param o an <code>Object</code> value
213: * @return a <code>boolean</code> value
214: */
215: public boolean contains(Object o) {
216: for (TLinkable link = _head; link != null; link = link
217: .getNext()) {
218: if (o.equals(link)) {
219: return true;
220: }
221: }
222: return false;
223: }
224:
225: /**
226: * {@inheritDoc}
227: */
228: @Override
229: public T get(int index) {
230: // Blow out for bogus values
231: if (index < 0 || index >= _size) {
232: throw new IndexOutOfBoundsException("Index: " + index
233: + ", Size: " + _size);
234: }
235:
236: // Determine if it's better to get there from the front or the back
237: if (index > (_size >> 1)) {
238: int position = _size - 1;
239: T node = _tail;
240:
241: while (position > index) {
242: node = (T) node.getPrevious();
243: position--;
244: }
245:
246: return node;
247: } else {
248: int position = 0;
249: T node = _head;
250:
251: while (position < index) {
252: node = (T) node.getNext();
253: position++;
254: }
255:
256: return node;
257: }
258: }
259:
260: /**
261: * Returns the head of the list
262: *
263: * @return an <code>Object</code> value
264: */
265: public T getFirst() {
266: return _head;
267: }
268:
269: /**
270: * Returns the tail of the list.
271: *
272: * @return an <code>Object</code> value
273: */
274: public T getLast() {
275: return _tail;
276: }
277:
278: /**
279: * Return the node following the given node. This method exists for two reasons:
280: * <ol>
281: * <li>It's really not recommended that the methods implemented by TLinkable be
282: * called directly since they're used internally by this class.</li>
283: * <li>This solves problems arising from generics when working with the linked
284: * objects directly.</li>
285: * </ol>
286: * <p>
287: * NOTE: this should only be used with nodes contained in the list. The results are
288: * undefined with anything else.
289: */
290: public T getNext(T current) {
291: return (T) current.getNext();
292: }
293:
294: /**
295: * Return the node preceding the given node. This method exists for two reasons:
296: * <ol>
297: * <li>It's really not recommended that the methods implemented by TLinkable be
298: * called directly since they're used internally by this class.</li>
299: * <li>This solves problems arising from generics when working with the linked
300: * objects directly.</li>
301: * </ol>
302: * <p>
303: * NOTE: this should only be used with nodes contained in the list. The results are
304: * undefined with anything else.
305: */
306: public T getPrevious(T current) {
307: return (T) current.getPrevious();
308: }
309:
310: /**
311: * Remove and return the first element in the list.
312: *
313: * @return an <code>Object</code> value
314: */
315: public T removeFirst() {
316: T o = _head;
317: T n = (T) o.getNext();
318: o.setNext(null);
319:
320: if (null != n) {
321: n.setPrevious(null);
322: }
323:
324: _head = n;
325: if (--_size == 0) {
326: _tail = null;
327: }
328: return o;
329: }
330:
331: /**
332: * Remove and return the last element in the list.
333: *
334: * @return an <code>Object</code> value
335: */
336: public T removeLast() {
337: T o = _tail;
338: T prev = (T) o.getPrevious();
339: o.setPrevious(null);
340:
341: if (null != prev) {
342: prev.setNext(null);
343: }
344: _tail = prev;
345: if (--_size == 0) {
346: _head = null;
347: }
348: return o;
349: }
350:
351: /**
352: * Implementation of index-based list insertions.
353: *
354: * @param index an <code>int</code> value
355: * @param linkable an object of type TLinkable
356: */
357: protected void insert(int index, T linkable) {
358: T newLink = linkable;
359:
360: if (_size == 0) {
361: _head = _tail = newLink; // first insertion
362: } else if (index == 0) {
363: newLink.setNext(_head); // insert at front
364: _head.setPrevious(newLink);
365: _head = newLink;
366: } else if (index == _size) { // insert at back
367: _tail.setNext(newLink);
368: newLink.setPrevious(_tail);
369: _tail = newLink;
370: } else {
371: T node = get(index);
372:
373: T before = (T) node.getPrevious();
374: if (before != null)
375: before.setNext(linkable);
376:
377: linkable.setPrevious(before);
378: linkable.setNext(node);
379: node.setPrevious(linkable);
380: }
381: _size++;
382: }
383:
384: /**
385: * Removes the specified element from the list. Note that
386: * it is the caller's responsibility to ensure that the
387: * element does, in fact, belong to this list and not another
388: * instance of TLinkedList.
389: *
390: * @param o a TLinkable element already inserted in this list.
391: * @return true if the element was a TLinkable and removed
392: */
393: public boolean remove(Object o) {
394: if (o instanceof TLinkable) {
395: T p, n;
396: TLinkable link = (TLinkable) o;
397:
398: p = (T) link.getPrevious();
399: n = (T) link.getNext();
400:
401: if (n == null && p == null) { // emptying the list
402: _head = _tail = null;
403: } else if (n == null) { // this is the tail
404: // make previous the new tail
405: link.setPrevious(null);
406: p.setNext(null);
407: _tail = p;
408: } else if (p == null) { // this is the head
409: // make next the new head
410: link.setNext(null);
411: n.setPrevious(null);
412: _head = n;
413: } else { // somewhere in the middle
414: p.setNext(n);
415: n.setPrevious(p);
416: link.setNext(null);
417: link.setPrevious(null);
418: }
419:
420: _size--; // reduce size of list
421: return true;
422: } else {
423: return false;
424: }
425: }
426:
427: /**
428: * Inserts newElement into the list immediately before current.
429: * All elements to the right of and including current are shifted
430: * over.
431: *
432: * @param current a <code>TLinkable</code> value currently in the list.
433: * @param newElement a <code>TLinkable</code> value to be added to
434: * the list.
435: */
436: public void addBefore(T current, T newElement) {
437: if (current == _head) {
438: addFirst(newElement);
439: } else if (current == null) {
440: addLast(newElement);
441: } else {
442: TLinkable p = current.getPrevious();
443: newElement.setNext(current);
444: p.setNext(newElement);
445: newElement.setPrevious(p);
446: current.setPrevious(newElement);
447: _size++;
448: }
449: }
450:
451: /**
452: * Inserts newElement into the list immediately after current.
453: * All elements to the left of and including current are shifted
454: * over.
455: *
456: * @param current a <code>TLinkable</code> value currently in the list.
457: * @param newElement a <code>TLinkable</code> value to be added to
458: * the list.
459: */
460: public void addAfter(T current, T newElement) {
461: if (current == _tail) {
462: addLast(newElement);
463: } else if (current == null) {
464: addFirst(newElement);
465: } else {
466: TLinkable n = current.getNext();
467: newElement.setPrevious(current);
468: newElement.setNext(n);
469: current.setNext(newElement);
470: n.setPrevious(current);
471: _size++;
472: }
473: }
474:
475: /**
476: * Executes <tt>procedure</tt> for each entry in the list.
477: *
478: * @param procedure a <code>TObjectProcedure</code> value
479: * @return false if the loop over the values terminated because
480: * the procedure returned false for some value.
481: */
482: public boolean forEachValue(TObjectProcedure<T> procedure) {
483: T node = _head;
484: while (node != null) {
485: boolean keep_going = procedure.execute(node);
486: if (!keep_going)
487: return false;
488:
489: node = (T) node.getNext();
490: }
491:
492: return true;
493: }
494:
495: public void writeExternal(ObjectOutput out) throws IOException {
496: // VERSION
497: out.writeByte(0);
498:
499: // NUMBER OF ENTRIES
500: out.writeInt(_size);
501:
502: // HEAD
503: out.writeObject(_head);
504:
505: // TAIL
506: out.writeObject(_head);
507: }
508:
509: public void readExternal(ObjectInput in) throws IOException,
510: ClassNotFoundException {
511:
512: // VERSION
513: in.readByte();
514:
515: // NUMBER OF ENTRIED
516: _size = in.readInt();
517:
518: // HEAD
519: _head = (T) in.readObject();
520:
521: // TAIL
522: _tail = (T) in.readObject();
523: }
524:
525: /**
526: * A ListIterator that supports additions and deletions.
527: *
528: */
529: protected final class IteratorImpl implements ListIterator<T> {
530: private int _nextIndex = 0;
531: private T _next;
532: private T _lastReturned;
533:
534: /**
535: * Creates a new <code>Iterator</code> instance positioned at
536: * <tt>index</tt>.
537: *
538: * @param position an <code>int</code> value
539: */
540: IteratorImpl(int position) {
541: if (position < 0 || position > _size) {
542: throw new IndexOutOfBoundsException();
543: }
544:
545: _nextIndex = position;
546: if (position == 0) {
547: _next = _head;
548: } else if (position == _size) {
549: _next = null;
550: } else if (position < (_size >> 1)) {
551: int pos = 0;
552: for (_next = _head; pos < position; pos++) {
553: _next = (T) _next.getNext();
554: }
555: } else {
556: int pos = _size - 1;
557: for (_next = _tail; pos > position; pos--) {
558: _next = (T) _next.getPrevious();
559: }
560: }
561: }
562:
563: /**
564: * Insert <tt>linkable</tt> at the current position of the iterator.
565: * Calling next() after add() will return the added object.
566: *
567: * @param linkable an object of type TLinkable
568: */
569: public final void add(T linkable) {
570: _lastReturned = null;
571: _nextIndex++;
572:
573: if (_size == 0) {
574: TLinkedList.this .add(linkable);
575: } else {
576: TLinkedList.this .addBefore(_next, linkable);
577: }
578: }
579:
580: /**
581: * True if a call to next() will return an object.
582: *
583: * @return a <code>boolean</code> value
584: */
585: public final boolean hasNext() {
586: return _nextIndex != _size;
587: }
588:
589: /**
590: * True if a call to previous() will return a value.
591: *
592: * @return a <code>boolean</code> value
593: */
594: public final boolean hasPrevious() {
595: return _nextIndex != 0;
596: }
597:
598: /**
599: * Returns the value at the Iterator's index and advances the
600: * iterator.
601: *
602: * @return an <code>Object</code> value
603: * @exception NoSuchElementException if there is no next element
604: */
605: public final T next() {
606: if (_nextIndex == _size) {
607: throw new NoSuchElementException();
608: }
609:
610: _lastReturned = _next;
611: _next = (T) _next.getNext();
612: _nextIndex++;
613: return _lastReturned;
614: }
615:
616: /**
617: * returns the index of the next node in the list (the
618: * one that would be returned by a call to next()).
619: *
620: * @return an <code>int</code> value
621: */
622: public final int nextIndex() {
623: return _nextIndex;
624: }
625:
626: /**
627: * Returns the value before the Iterator's index and moves the
628: * iterator back one index.
629: *
630: * @return an <code>Object</code> value
631: * @exception NoSuchElementException if there is no previous element.
632: */
633: public final T previous() {
634: if (_nextIndex == 0) {
635: throw new NoSuchElementException();
636: }
637:
638: if (_nextIndex == _size) {
639: _lastReturned = _next = _tail;
640: } else {
641: _lastReturned = _next = (T) _next.getPrevious();
642: }
643:
644: _nextIndex--;
645: return _lastReturned;
646: }
647:
648: /**
649: * Returns the previous element's index.
650: *
651: * @return an <code>int</code> value
652: */
653: public final int previousIndex() {
654: return _nextIndex - 1;
655: }
656:
657: /**
658: * Removes the current element in the list and shrinks its
659: * size accordingly.
660: *
661: * @exception IllegalStateException neither next nor previous
662: * have been invoked, or remove or add have been invoked after
663: * the last invocation of next or previous.
664: */
665: public final void remove() {
666: if (_lastReturned == null) {
667: throw new IllegalStateException(
668: "must invoke next or previous before invoking remove");
669: }
670:
671: if (_lastReturned != _next) {
672: _nextIndex--;
673: }
674: _next = (T) _lastReturned.getNext();
675: TLinkedList.this .remove(_lastReturned);
676: _lastReturned = null;
677: }
678:
679: /**
680: * Replaces the current element in the list with
681: * <tt>linkable</tt>
682: *
683: * @param linkable an object of type TLinkable
684: */
685: public final void set(T linkable) {
686: if (_lastReturned == null) {
687: throw new IllegalStateException();
688: }
689: T l = linkable;
690:
691: // need to check both, since this could be the only
692: // element in the list.
693: if (_lastReturned == _head) {
694: _head = l;
695: }
696:
697: if (_lastReturned == _tail) {
698: _tail = l;
699: }
700:
701: swap(_lastReturned, l);
702: _lastReturned = l;
703: }
704:
705: /**
706: * Replace from with to in the list.
707: *
708: * @param from a <code>TLinkable</code> value
709: * @param to a <code>TLinkable</code> value
710: */
711: private void swap(T from, T to) {
712: T p = (T) from.getPrevious();
713: T n = (T) from.getNext();
714:
715: if (null != p) {
716: to.setPrevious(p);
717: p.setNext(to);
718: }
719: if (null != n) {
720: to.setNext(n);
721: n.setPrevious(to);
722: }
723: from.setNext(null);
724: from.setPrevious(null);
725: }
726: }
727: } // TLinkedList
|