home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / linkedli.jav < prev    next >
Encoding:
Text File  |  1995-12-14  |  15.3 KB  |  599 lines
  1. /*
  2.   File: LinkedList.java
  3.  
  4.   Originally written by Doug Lea and released into the public domain. 
  5.   Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  6.   Inc, Loral, and everyone contributing, testing, and using this code.
  7.  
  8.   History:
  9.   Date     Who                What
  10.   2Oct95  dl@cs.oswego.edu   repack from LLSeq.java
  11.  
  12. */
  13.   
  14. package collections;
  15. import java.util.Enumeration;
  16. import java.util.NoSuchElementException;
  17.  
  18. /**
  19.  *
  20.  * LinkedList implementation.
  21.  * Publically implements only those methods defined in its interfaces.
  22.  *
  23.  * @author Doug Lea
  24.  * @version 0.93
  25.  *
  26.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  27. **/
  28.  
  29. public class LinkedList extends    UpdatableSeqImpl 
  30.                         implements UpdatableSeq,
  31.                                    SortableCollection {
  32. // instance variables
  33.  
  34. /**
  35.  * The head of the list. Null iff count_ == 0
  36. **/
  37.  
  38.   protected LLCell list_;
  39.  
  40. // constructors
  41.  
  42. /**
  43.  * Create a new empty list
  44. **/
  45.  
  46.   public LinkedList() { this(null, null, 0); }
  47.  
  48. /**
  49.  * Create a list with a given element screener
  50. **/
  51.  
  52.   public LinkedList(Predicate screener) { this(screener, null, 0); }
  53.  
  54. /**
  55.  * Special version of constructor needed by clone()
  56. **/
  57.  
  58.   protected LinkedList(Predicate s, LLCell l, int c) { 
  59.     super(s); list_ = l; count_ = c; 
  60.   }
  61.  
  62. /**
  63.  * Build an independent copy of the list.
  64.  * The elements themselves are not cloned
  65. **/
  66.  
  67.   protected Object clone() throws CloneNotSupportedException { 
  68.     if (list_ == null) return new LinkedList(screener_, null, 0); 
  69.     else return new LinkedList(screener_, list_.copyList(), count_);  
  70.   }
  71.  
  72.       
  73. // Collection methods
  74.  
  75. /**
  76.  * Implements collections.Collection.includes.
  77.  * Time complexity: O(n).
  78.  * @see collections.Collection#includes
  79. **/
  80.   public synchronized boolean includes(Object element) {
  81.     if (element == null || count_ == 0) return false;
  82.     return list_.find(element) != null;
  83.   }
  84.  
  85. /**
  86.  * Implements collections.Collection.occurrencesOf.
  87.  * Time complexity: O(n).
  88.  * @see collections.Collection#occurrencesOf
  89. **/
  90.   public synchronized int occurrencesOf(Object element) {
  91.     if (element == null || count_ == 0) return 0;
  92.     return list_.count(element);
  93.   }
  94.  
  95. /**
  96.  * Implements collections.Collection.elements.
  97.  * Time complexity: O(1).
  98.  * @see collections.Collection#elements
  99. **/
  100.   public synchronized CollectionEnumeration elements() { 
  101.     return new LLCellEnumeration(this, list_); 
  102.   }
  103.  
  104.  
  105.  
  106. // Seq Methods
  107.  
  108. /**
  109.  * Implements collections.Seq.first.
  110.  * Time complexity: O(1).
  111.  * @see collections.Seq#first
  112. **/
  113.   public synchronized Object first()
  114.   throws  NoSuchElementException {
  115.     return firstCell().element();   
  116.   }
  117.  
  118. /**
  119.  * Implements collections.Seq.last.
  120.  * Time complexity: O(n).
  121.  * @see collections.Seq#last
  122. **/
  123.   public synchronized Object last()
  124.   throws  NoSuchElementException {
  125.     return lastCell().element();  
  126.   }
  127.  
  128. /**
  129.  * Implements collections.Seq.at.
  130.  * Time complexity: O(n).
  131.  * @see collections.Seq#at
  132. **/
  133.   public synchronized Object at(int index) 
  134.   throws  NoSuchElementException {
  135.     return cellAt(index).element();  
  136.   }
  137.  
  138. /**
  139.  * Implements collections.Seq.firstIndexOf.
  140.  * Time complexity: O(n).
  141.  * @see collections.Seq#firstIndexOf
  142. **/
  143.   public synchronized int firstIndexOf(Object element, int startingIndex) {
  144.     if (element == null || list_ == null) return -1;
  145.     if (startingIndex < 0) startingIndex = 0;
  146.     LLCell p = list_.nth(startingIndex);
  147.     if (p != null) {
  148.       int i = p.index(element);
  149.       if (i >= 0) return i + startingIndex;
  150.     }
  151.     return -1;
  152.   }
  153.  
  154. /**
  155.  * Implements collections.Seq.firstIndexOf.
  156.  * Time complexity: O(n).
  157.  * @see collections.Seq#firstIndexOf
  158. **/
  159.   public synchronized int firstIndexOf(Object element) {
  160.     return firstIndexOf(element, 0);
  161.   }
  162.  
  163. /**
  164.  * Implements collections.Seq.lastIndexOf.
  165.  * Time complexity: O(n).
  166.  * @see collections.Seq#lastIndexOf
  167. **/
  168.   public synchronized int lastIndexOf(Object element, int startingIndex) {
  169.     if (element == null || list_ == null) return -1;
  170.     int i = 0;
  171.     if (startingIndex >= size()) startingIndex = size()-1;
  172.     int index = -1;
  173.     LLCell p = list_;
  174.     while (i <= startingIndex && p != null) {
  175.       if (p.element().equals(element)) 
  176.         index = i;
  177.       ++i;
  178.       p = p.next();
  179.     }
  180.     return index;
  181.   }
  182.  
  183. /**
  184.  * Implements collections.Seq.lastIndexOf.
  185.  * Time complexity: O(n).
  186.  * @see collections.Seq#lastIndexOf
  187. **/
  188.   public synchronized int lastIndexOf(Object element) {
  189.     return lastIndexOf(element, size()-1);
  190.   }
  191.  
  192.  
  193.  
  194. /**
  195.  * Implements collections.Seq.subseq.
  196.  * Time complexity: O(length).
  197.  * @see collections.Seq#subseq
  198. **/
  199.   public synchronized /* LinkedList */ Seq subseq(int from, int length) 
  200.   throws  NoSuchElementException {
  201.     if (length > 0) {
  202.       LLCell p = cellAt(from);
  203.       LLCell newlist = new LLCell(p.element(), null);
  204.       LLCell current = newlist;
  205.       for (int i = 1; i < length; ++i) {
  206.         p = p.next();
  207.         if (p == null) checkIndex(from+i); // force exception
  208.         current.linkNext(new LLCell(p.element(), null));
  209.         current = current.next();
  210.       }
  211.       return new LinkedList(screener_, newlist, length);
  212.     }
  213.     else
  214.       return new LinkedList(screener_, null, 0);
  215.   }
  216.  
  217.  
  218. // UpdatableCollection methods
  219.  
  220. /**
  221.  * Implements collections.UpdatableCollection.clear.
  222.  * Time complexity: O(1).
  223.  * @see collections.UpdatableCollection#clear
  224. **/
  225.   public synchronized void clear() { 
  226.     if (list_ != null) { list_ = null; setCount(0);  }
  227.   }
  228.  
  229. /**
  230.  * Implements collections.UpdatableCollection.exclude.
  231.  * Time complexity: O(n).
  232.  * @see collections.UpdatableCollection#exclude
  233. **/
  234.   public synchronized void exclude(Object element)  { 
  235.     remove_(element, true);
  236.   }
  237.  
  238. /**
  239.  * Implements collections.UpdatableCollection.removeOneOf.
  240.  * Time complexity: O(n).
  241.  * @see collections.UpdatableCollection#removeOneOf
  242. **/
  243.   public synchronized void removeOneOf(Object element)  { 
  244.     remove_(element, false);
  245.   }
  246.  
  247. /**
  248.  * Implements collections.UpdatableCollection.replaceOneOf
  249.  * Time complexity: O(n).
  250.  * @see collections.UpdatableCollection#replaceOneOf
  251. **/
  252.   public synchronized void replaceOneOf(Object oldElement, Object newElement)  
  253.   throws IllegalElementException { 
  254.     replace_(oldElement, newElement, false);
  255.   }
  256.  
  257. /**
  258.  * Implements collections.UpdatableCollection.replaceAllOf.
  259.  * Time complexity: O(n).
  260.  * @see collections.UpdatableCollection#replaceAllOf
  261. **/
  262.   public synchronized void replaceAllOf(Object oldElement, 
  263.                                                  Object newElement) 
  264.   throws IllegalElementException {
  265.     replace_(oldElement, newElement, true);
  266.   }
  267.  
  268.  
  269. /**
  270.  * Implements collections.UpdatableCollection.take.
  271.  * Time complexity: O(1).
  272.  * takes the first element on the list
  273.  * @see collections.UpdatableCollection#take
  274. **/
  275.   public synchronized Object take() 
  276.   throws NoSuchElementException {
  277.     Object v = first();
  278.     removeFirst();
  279.     return v;
  280.   }
  281.  
  282. // SortableCollection methods
  283.  
  284. /**
  285.  * Implements collections.SortableCollection.sort.
  286.  * Time complexity: O(n log n).
  287.  * Uses a merge-sort-based algorithm.
  288.  * @see collections.SortableCollection#sort
  289. **/
  290.   public synchronized void sort(Comparator cmp) {
  291.     if (list_ != null) {
  292.       list_ = LLCell.mergeSort(list_, cmp);
  293.       incVersion();
  294.     }
  295.   }
  296.  
  297.  
  298. // UpdatableSeq methods
  299.  
  300. /**
  301.  * Implements collections.UpdatableSeq.insertFirst.
  302.  * Time complexity: O(1).
  303.  * @see collections.UpdatableSeq#insertFirst
  304. **/
  305.   public synchronized void insertFirst(Object element) 
  306.   throws IllegalElementException {
  307.     checkElement(element);
  308.     list_ = new LLCell(element, list_);
  309.     incCount();
  310.   }
  311.  
  312. /**
  313.  * Implements collections.UpdatableSeq.replaceFirst.
  314.  * Time complexity: O(1).
  315.  * @see collections.UpdatableSeq#replaceFirst
  316. **/
  317.   public synchronized void replaceFirst(Object element) 
  318.   throws IllegalElementException {
  319.     checkElement(element);
  320.     firstCell().element(element);
  321.     incVersion();
  322.   }
  323.  
  324. /**
  325.  * Implements collections.UpdatableSeq.removeFirst.
  326.  * Time complexity: O(1).
  327.  * @see collections.UpdatableSeq#removeFirst
  328. **/
  329.   public synchronized void removeFirst() 
  330.   throws NoSuchElementException {
  331.     list_ = firstCell().next();
  332.     decCount();
  333.   }
  334.  
  335. /**
  336.  * Implements collections.UpdatableSeq.insertLast.
  337.  * Time complexity: O(n).
  338.  * @see collections.UpdatableSeq#insertLast
  339. **/
  340.   public synchronized void insertLast(Object element) 
  341.   throws IllegalElementException {
  342.     checkElement(element);
  343.     if (list_ == null) insertFirst(element);
  344.     else { 
  345.       list_.last().next(new LLCell(element)); 
  346.       incCount(); 
  347.     }
  348.   }
  349.  
  350. /**
  351.  * Implements collections.UpdatableSeq.replaceLast.
  352.  * Time complexity: O(n).
  353.  * @see collections.UpdatableSeq#replaceLast
  354. **/
  355.   public synchronized void replaceLast(Object element) 
  356.   throws IllegalElementException, NoSuchElementException {
  357.     checkElement(element);
  358.     lastCell().element(element);
  359.     incVersion();
  360.   }
  361.  
  362. /**
  363.  * Implements collections.UpdatableSeq.removeLast.
  364.  * Time complexity: O(n).
  365.  * @see collections.UpdatableSeq#removeLast
  366. **/
  367.   public synchronized void removeLast()
  368.   throws NoSuchElementException {
  369.     if (firstCell().next() == null ) removeFirst();
  370.     else {
  371.       LLCell trail = list_;
  372.       LLCell p = trail.next();
  373.       while (p.next() != null) { trail = p; p = p.next(); }
  374.       trail.next(null);
  375.       decCount();
  376.     }
  377.   }
  378.  
  379. /**
  380.  * Implements collections.UpdatableSeq.insertAt.
  381.  * Time complexity: O(n).
  382.  * @see collections.UpdatableSeq#insertAt
  383. **/
  384.   public synchronized void insertAt(int index, Object element) 
  385.   throws IllegalElementException, NoSuchElementException {
  386.     if (index == 0) insertFirst(element);
  387.     else { 
  388.       checkElement(element);
  389.       cellAt(index - 1).linkNext(new LLCell(element)); 
  390.       incCount(); 
  391.     }
  392.   }
  393.  
  394. /**
  395.  * Implements collections.UpdatableSeq.removeAt.
  396.  * Time complexity: O(n).
  397.  * @see collections.UpdatableSeq#removeAt
  398. **/
  399.   public synchronized void removeAt(int index) 
  400.   throws NoSuchElementException {
  401.     if (index == 0) removeFirst();
  402.     else { 
  403.       cellAt(index - 1).unlinkNext(); 
  404.       decCount(); 
  405.     }
  406.   }
  407.     
  408. /**
  409.  * Implements collections.UpdatableSeq.replaceAt.
  410.  * Time complexity: O(n).
  411.  * @see collections.UpdatableSeq#replaceAt
  412. **/
  413.   public synchronized void replaceAt(int index, Object element) 
  414.   throws IllegalElementException, NoSuchElementException {
  415.     cellAt(index).element(element);
  416.     incVersion();
  417.   }
  418.  
  419. /**
  420.  * Implements collections.UpdatableSeq.prependElements.
  421.  * Time complexity: O(number of elements in e).
  422.  * @see collections.UpdatableSeq#prependElements
  423. **/
  424.   public synchronized void prependElements(Enumeration e) 
  425.   throws IllegalElementException, CorruptedEnumerationException {
  426.     splice_(e, null, list_);
  427.   }
  428.  
  429. /**
  430.  * Implements collections.UpdatableSeq.appendElements.
  431.  * Time complexity: O(n + number of elements in e).
  432.  * @see collections.UpdatableSeq#appendElements
  433. **/
  434.   public synchronized void appendElements(Enumeration e) 
  435.   throws IllegalElementException, CorruptedEnumerationException {
  436.     if (list_ == null) splice_(e, null, null);
  437.     else splice_(e, list_.last(), null);
  438.   }
  439.  
  440. /**
  441.  * Implements collections.UpdatableSeq.insertElementsAt.
  442.  * Time complexity: O(n + number of elements in e).
  443.  * @see collections.UpdatableSeq#insertElementsAt
  444. **/
  445.   public synchronized void insertElementsAt(int index, Enumeration e) 
  446.   throws IllegalElementException, CorruptedEnumerationException,
  447.   NoSuchElementException {
  448.     if (index == 0) splice_(e, null, list_);
  449.     else {
  450.       LLCell p = cellAt(index - 1);
  451.       splice_(e, p, p.next());
  452.     }
  453.   }
  454.   
  455. /**
  456.  * Implements collections.UpdatableSeq.removeFromTo.
  457.  * Time complexity: O(n).
  458.  * @see collections.UpdatableSeq#removeFromTo
  459. **/
  460.   public synchronized void removeFromTo(int fromIndex, int toIndex) 
  461.   throws NoSuchElementException {
  462.     checkIndex(toIndex);
  463.     if (fromIndex <= toIndex) {
  464.       if (fromIndex == 0) {
  465.         LLCell p = firstCell();
  466.         for (int i = fromIndex; i <= toIndex; ++i) p = p.next();
  467.         list_ = p;  
  468.       }
  469.       else {
  470.         LLCell f = cellAt(fromIndex-1);
  471.         LLCell p = f;
  472.         for (int i = fromIndex; i <= toIndex; ++i) p = p.next();
  473.         f.next(p.next());
  474.       }
  475.       addToCount(-(toIndex-fromIndex+1));
  476.     }
  477.   }
  478.     
  479.  
  480.  
  481. // helper methods
  482.  
  483.   private final LLCell firstCell() throws NoSuchElementException { 
  484.     if (list_ != null) return list_; 
  485.     checkIndex(0);
  486.     return null; // not reached!
  487.   }
  488.  
  489.   private final LLCell lastCell()  throws NoSuchElementException {
  490.     if (list_ != null) return list_.last();
  491.     checkIndex(0);
  492.     return null; // not reached!
  493.   }
  494.  
  495.   private final LLCell cellAt(int index) throws NoSuchElementException {
  496.     checkIndex(index);
  497.     return list_.nth(index);
  498.   }
  499.  
  500. /**
  501.  * Helper method for removeOneOf()
  502. **/
  503.  
  504.   private void remove_(Object element, boolean allOccurrences)  { 
  505.     if (element == null || count_ == 0) return;
  506.     LLCell p = list_;
  507.     LLCell trail = p;
  508.     while (p != null) {
  509.       LLCell n = p.next();
  510.       if (p.element().equals(element)) {
  511.         decCount();
  512.         if (p == list_) { list_ = n; trail = n; }
  513.         else trail.next(n);
  514.         if (!allOccurrences || count_ == 0) return;
  515.         else p = n;
  516.       }
  517.       else {
  518.         trail = p;
  519.         p = n;
  520.       }
  521.     }
  522.   }
  523.  
  524.  
  525. /**
  526.  * Helper for replace
  527. **/
  528.  
  529.   private void replace_(Object oldElement, Object newElement, 
  530.                           boolean allOccurrences)  
  531.   throws IllegalElementException { 
  532.     if (count_ == 0 || oldElement == null || oldElement.equals(newElement))
  533.       return;
  534.     LLCell p = list_.find(oldElement);
  535.     while (p != null) { 
  536.       checkElement(newElement);
  537.       p.element(newElement);
  538.       incVersion();
  539.       if (!allOccurrences) return;
  540.       p = p.find(oldElement);
  541.     }
  542.   }
  543.  
  544. /**
  545.  * Splice elements of e between hd and tl. if hd is null return new hd
  546. **/
  547.  
  548.   private void splice_(Enumeration e, LLCell hd, LLCell tl) 
  549.     throws IllegalElementException, CorruptedEnumerationException {
  550.     if (e.hasMoreElements()) {
  551.       LLCell newlist = null;
  552.       LLCell current = null;
  553.       while (e.hasMoreElements()) {
  554.         Object v = e.nextElement();
  555.         checkElement(v);
  556.         incCount();
  557.         LLCell p = new LLCell(v, null);
  558.         if (newlist == null) 
  559.           newlist = p;
  560.         else 
  561.           current.next(p);
  562.         current = p;
  563.       }
  564.       if (current != null) current.next(tl);
  565.       if (hd == null) list_ = newlist;
  566.       else hd.next(newlist);
  567.     }
  568.   }
  569.  
  570. // ImplementationCheckable methods
  571.  
  572. /**
  573.  * Implements collections.ImplementationCheckable.checkImplementation.
  574.  * @see collections.ImplementationCheckable#checkImplementation
  575. **/
  576.   public synchronized void checkImplementation() 
  577.   throws ImplementationError {
  578.  
  579.     super.checkImplementation();
  580.  
  581.     assert(((count_ == 0) == (list_ == null)));
  582.     assert((list_ == null || list_.length() == count_));
  583.  
  584.     int c = 0;
  585.     for (LLCell p = list_; p != null; p = p.next()) {
  586.       assert(canInclude(p.element()));
  587.       assert(occurrencesOf(p.element()) > 0);
  588.       assert(includes(p.element()));
  589.       ++c;
  590.     }
  591.     assert(c == count_);
  592.  
  593.   }
  594.  
  595. }
  596.  
  597.  
  598.  
  599.