home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / linkedbu.jav < prev    next >
Encoding:
Text File  |  1995-12-14  |  10.9 KB  |  426 lines
  1. /*
  2.   File: LinkedBuffer.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.   24Sep95  dl@cs.oswego.edu   Create from collections.java  working file
  11.   13Oct95  dl                 Changed protection statuses
  12.  
  13. */
  14.   
  15. package collections;
  16.  
  17. import java.util.Enumeration;
  18. import java.util.NoSuchElementException;
  19.  
  20. /**
  21.  *
  22.  * Linked Buffer implementation of Bags. The Bag consists of
  23.  * any number of buffers holding elements, arranged in a list.
  24.  * Each buffer holds an array of elements. The size of each
  25.  * buffer is the value of chunkSize that was current during the
  26.  * operation that caused the Bag to grow. The chunkSize() may
  27.  * be adjusted at any time. (It is not considered a version change.)
  28.  * 
  29.  * <P>
  30.  * All but the final buffer is always kept full.
  31.  * When a buffer has no elements, it is released (so is
  32.  * available for garbage collection).
  33.  * <P>
  34.  * LinkedBuffers are good choices for collections in which
  35.  * you merely put a lot of things in, and then look at
  36.  * them via enumerations, but don't often look for
  37.  * particular elements.
  38.  * 
  39.  * @author Doug Lea
  40.  * @version 0.93
  41.  *
  42.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  43. **/
  44.  
  45. public class LinkedBuffer extends UpdatableBagImpl implements UpdatableBag {
  46.  
  47.  
  48. /**
  49.  * The default chunk size to use for buffers
  50. **/
  51.  
  52.   public static final int defaultChunkSize = 32;
  53.  
  54. // instance variables
  55.  
  56. /**
  57.  * The last node of the circular list of chunks. Null if empty.
  58. **/
  59.  
  60.   protected CLCell tail_;
  61.  
  62. /**
  63.  * The number of elements of the tail node actually used. (all others
  64.  * are kept full).
  65. **/
  66.   protected int lastCount_;
  67.  
  68. /**
  69.  * The chunk size to use for making next buffer
  70. **/
  71.  
  72.   protected int chunkSize_;
  73.  
  74. // constructors
  75.  
  76. /**
  77.  * Make an empty buffer.
  78. **/
  79.   public LinkedBuffer() { this(null, 0, null, 0, defaultChunkSize); }
  80.  
  81. /**
  82.  * Make an empty buffer, using the supplied element screener.
  83. **/
  84.  
  85.   public LinkedBuffer(Predicate s) { this(s, 0, null, 0, defaultChunkSize); }
  86.  
  87. /**
  88.  * Special version of constructor needed by clone()
  89. **/
  90.   protected LinkedBuffer(Predicate s, int n, CLCell t, int lc, int cs) { 
  91.     super(s); 
  92.     count_ = n;
  93.     tail_ = t;
  94.     lastCount_ = lc;
  95.     chunkSize_ = cs;
  96.   }
  97.  
  98. /**
  99.  * Make an independent copy. Does not clone elements.
  100. **/
  101.   protected Object clone() throws CloneNotSupportedException { 
  102.     if (count_ == 0) return new LinkedBuffer(screener_);
  103.     else {
  104.       CLCell h = tail_.copyList();
  105.       CLCell p = h;
  106.       do {
  107.         Object obuff[] = (Object[])(p.element());
  108.         Object nbuff[] = new Object[obuff.length];
  109.         for (int i = 0; i < obuff.length; ++i) nbuff[i] = obuff[i];
  110.         p.element(nbuff);
  111.         p = p.next();
  112.       } while (p != h);
  113.       return new LinkedBuffer(screener_, count_, h, lastCount_, chunkSize_);
  114.     }
  115.   }
  116.  
  117.  
  118. /**
  119.  * Report the chunk size used when adding new buffers to the list
  120. **/
  121.  
  122.   public synchronized int chunkSize() { return chunkSize_; }
  123.  
  124. /**
  125.  * Set the chunk size to be used when adding new buffers to the 
  126.  * list during future add() operations.
  127.  * Any value greater than 0 is OK. (A value of 1 makes this a
  128.  * into very slow simulation of a linked list!)
  129. **/
  130.  
  131.   public synchronized void chunkSize(int newChunkSize) 
  132.   throws IllegalArgumentException {
  133.     if (newChunkSize > 0) 
  134.       chunkSize_ = newChunkSize;
  135.     else
  136.       throw new IllegalArgumentException("Attempt to set impossible chunk size value of " + newChunkSize);
  137.   }
  138.  
  139. // Collection methods  
  140.  
  141. /*
  142.   This code is pretty repetitive, but I don't know a nice way to
  143.   separate traversal logic from actions
  144. */
  145.         
  146. /**
  147.  * Implements collections.Collection.includes.
  148.  * Time complexity: O(n).
  149.  * @see collections.Collection#includes
  150. **/
  151.   public synchronized boolean includes(Object element) {
  152.     if (element == null || count_ == 0) return false;
  153.     CLCell p = tail_.next();
  154.     for (;;) {
  155.       Object buff[] = (Object[])(p.element());
  156.       boolean isLast = p == tail_;
  157.       int n;
  158.       if (isLast) n = lastCount_;
  159.       else n = buff.length;
  160.       for (int i = 0; i < n; ++i) {
  161.         if (buff[i].equals(element)) 
  162.           return true;
  163.       }
  164.       if (isLast) break;
  165.       else p = p.next();
  166.     }
  167.     return false;
  168.   }
  169.  
  170. /**
  171.  * Implements collections.Collection.occurrencesOf.
  172.  * Time complexity: O(n).
  173.  * @see collections.Collection#occurrencesOf
  174. **/
  175.   public synchronized int occurrencesOf(Object element) {
  176.     if (element == null || count_ == 0) return 0;
  177.     int c = 0;
  178.     CLCell p = tail_.next();
  179.     for (;;) {
  180.       Object buff[] = (Object[])(p.element());
  181.       boolean isLast = p == tail_;
  182.       int n;
  183.       if (isLast) n = lastCount_;
  184.       else n = buff.length;
  185.       for (int i = 0; i < n; ++i) {
  186.         if (buff[i].equals(element)) 
  187.           ++c;
  188.       }
  189.       if (isLast) break;
  190.       else p = p.next();
  191.     }
  192.     return c;
  193.   }
  194.  
  195. /**
  196.  * Implements collections.Collection.elements.
  197.  * Time complexity: O(1).
  198.  * @see collections.Collection#elements
  199. **/
  200.   public synchronized CollectionEnumeration elements() { 
  201.     return new LBEnumeration(this, ((tail_ == null) ? null : tail_.next()));
  202.   }
  203.  
  204. // UpdatableCollection methods
  205.  
  206. /**
  207.  * Implements collections.UpdatableCollection.clear.
  208.  * Time complexity: O(1).
  209.  * @see collections.UpdatableCollection#clear
  210. **/
  211.   public synchronized void clear() { 
  212.     setCount(0);
  213.     tail_ = null;
  214.     lastCount_ = 0;
  215.   }
  216.  
  217. /**
  218.  * Implements collections.UpdatableCollection.exclude.
  219.  * Time complexity: O(n).
  220.  * @see collections.UpdatableCollection#exclude
  221. **/
  222.   public synchronized void exclude(Object element) {
  223.     remove_(element, true);
  224.   }
  225.  
  226.  
  227. /**
  228.  * Implements collections.UpdatableCollection.removeOneOf.
  229.  * Time complexity: O(n).
  230.  * @see collections.UpdatableCollection#removeOneOf
  231. **/
  232.   public synchronized void removeOneOf(Object element) {
  233.     remove_(element, false);
  234.   }
  235.  
  236. /**
  237.  * Implements collections.UpdatableCollection.replaceOneOf
  238.  * Time complexity: O(n).
  239.  * @see collections.UpdatableCollection#replaceOneOf
  240. **/
  241.   public synchronized void replaceOneOf(Object oldElement, Object newElement)  
  242.   throws IllegalElementException { 
  243.     replace_(oldElement, newElement, false);
  244.   }
  245.  
  246. /**
  247.  * Implements collections.UpdatableCollection.replaceAllOf.
  248.  * Time complexity: O(n).
  249.  * @see collections.UpdatableCollection#replaceAllOf
  250. **/
  251.   public synchronized void replaceAllOf(Object oldElement, 
  252.                                                  Object newElement) 
  253.   throws IllegalElementException {
  254.     replace_(oldElement, newElement, true);
  255.   }
  256.  
  257. /**
  258.  * Implements collections.UpdatableCollection.take.
  259.  * Time complexity: O(1).
  260.  * Takes the least element.
  261.  * @see collections.UpdatableCollection#take
  262. **/
  263.   public synchronized Object take() 
  264.   throws NoSuchElementException {
  265.     if (count_ != 0) {
  266.       Object buff[] = (Object[])(tail_.element());
  267.       Object v = buff[lastCount_-1];
  268.       buff[lastCount_-1] = null;
  269.       shrink_();
  270.       return v;
  271.     }
  272.     checkIndex(0);
  273.     return null; // not reached
  274.   }
  275.  
  276.  
  277.  
  278. // UpdatableBag methods
  279.  
  280. /**
  281.  * Implements collections.UpdatableBag.addIfAbsent.
  282.  * Time complexity: O(n).
  283.  * @see collections.UpdatableBag#addIfAbsent
  284. **/
  285.   public synchronized void addIfAbsent(Object element) 
  286.   throws IllegalElementException {
  287.     if (!includes(element)) add(element);
  288.   }
  289.  
  290.  
  291. /**
  292.  * Implements collections.UpdatableBag.add.
  293.  * Time complexity: O(1).
  294.  * @see collections.UpdatableBag#add
  295. **/
  296.   public synchronized void add(Object element) 
  297.   throws IllegalElementException {
  298.     checkElement(element);
  299.     
  300.     incCount();
  301.     if (tail_ == null) {
  302.       tail_ = new CLCell(new Object[chunkSize_]);
  303.       lastCount_ = 0;
  304.     }
  305.  
  306.     Object buff[] = (Object[])(tail_.element());
  307.     if (lastCount_ == buff.length) {
  308.       buff = new Object[chunkSize_];
  309.       tail_.addNext(buff);
  310.       tail_ = tail_.next();
  311.       lastCount_ = 0;
  312.     }
  313.     buff[lastCount_++] = element;
  314.   }
  315.  
  316. /**
  317.  * helper for remove/exclude
  318. **/
  319.  
  320.   private void remove_(Object element, boolean allOccurrences) {
  321.     if (element == null || count_ == 0) return;
  322.     CLCell p = tail_;
  323.     for (;;) {
  324.       Object buff[] = (Object[])(p.element());
  325.       int i = (p == tail_)? lastCount_ - 1 : buff.length - 1;
  326.       while (i >= 0) {
  327.         if (buff[i].equals(element)) {
  328.  
  329.           Object lastBuff[] = (Object[])(tail_.element());
  330.           buff[i] = lastBuff[lastCount_-1];
  331.           lastBuff[lastCount_-1] = null;
  332.           shrink_();
  333.  
  334.           if (!allOccurrences || count_ == 0)
  335.             return;
  336.  
  337.           if (p == tail_ && i >= lastCount_) i = lastCount_-1;
  338.         }
  339.         else
  340.           --i;
  341.       }
  342.       if (p == tail_.next()) break;
  343.       else p = p.prev();
  344.     }
  345.   }
  346.  
  347.   private void replace_(Object oldElement, Object newElement, boolean allOccurrences) 
  348.   throws IllegalElementException {
  349.     if (oldElement == null || count_ == 0 || oldElement.equals(newElement)) 
  350.       return;
  351.     CLCell p = tail_.next();
  352.     for (;;) {
  353.       Object buff[] = (Object[])(p.element());
  354.       boolean isLast = p == tail_;
  355.       int n;
  356.       if (isLast) n = lastCount_;
  357.       else n = buff.length;
  358.       for (int i = 0; i < n; ++i) {
  359.         if (buff[i].equals(oldElement)) {
  360.           checkElement(newElement);
  361.           incVersion();
  362.           buff[i] = newElement;
  363.           if (!allOccurrences)
  364.             return;
  365.         }
  366.       }
  367.       if (isLast) break;
  368.       else p = p.next();
  369.     }
  370.   }
  371.  
  372.   private void shrink_() {
  373.     decCount();
  374.     lastCount_--;
  375.     if (lastCount_ == 0) {
  376.       if (count_ == 0)
  377.         clear();
  378.       else {
  379.         CLCell tmp = tail_;
  380.         tail_ = tail_.prev();
  381.         tmp.unlink();
  382.         Object buff[] = (Object[])(tail_.element());
  383.         lastCount_ = buff.length;
  384.       }
  385.     }
  386.   }
  387.  
  388. // ImplementationCheckable methods
  389.  
  390. /**
  391.  * Implements collections.ImplementationCheckable.checkImplementation.
  392.  * @see collections.ImplementationCheckable#checkImplementation
  393. **/
  394.   public void checkImplementation() 
  395.   throws ImplementationError {
  396.  
  397.     super.checkImplementation();
  398.     assert(chunkSize_ >= 0);
  399.     assert(lastCount_ >= 0);
  400.     assert(((count_ == 0) == (tail_ == null)));
  401.     
  402.     if (tail_ == null) return;
  403.     int c = 0;
  404.     CLCell p = tail_.next();
  405.     for (;;) {
  406.       Object buff[] = (Object[])(p.element());
  407.       boolean isLast = p == tail_;
  408.       int n;
  409.       if (isLast) n = lastCount_;
  410.       else n = buff.length;
  411.       c += n;
  412.       for (int i = 0; i < n; ++i) {
  413.         Object v = buff[i];
  414.         assert(canInclude(v) && includes(v));
  415.       }
  416.       if (isLast) break;
  417.       else p = p.next();
  418.     }
  419.  
  420.     assert(c == count_);
  421.  
  422.   }
  423.  
  424. }
  425.  
  426.