BaseListImpl


1   /*
2    * $Id: BaseListImpl.java,v 1.4 2003/11/20 23:18:41 per_nyfelt Exp $
3    * This file is based on AbstractList.java from GNU Classpath. Quote:
4   
5   AbstractList.java -- Abstract implementation of most of List
6   Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
7   
8   This file is part of GNU Classpath.
9   
10  GNU Classpath is free software; you can redistribute it and/or modify
11  it under the terms of the GNU General Public License as published by
12  the Free Software Foundation; either version 2, or (at your option)
13  any later version.
14  
15  GNU Classpath is distributed in the hope that it will be useful, but
16  WITHOUT ANY WARRANTY; without even the implied warranty of
17  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  General Public License for more details.
19  
20  You should have received a copy of the GNU General Public License
21  along with GNU Classpath; see the file COPYING.  If not, write to the
22  Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
23  02111-1307 USA.
24  
25  Linking this library statically or dynamically with other modules is
26  making a combined work based on this library.  Thus, the terms and
27  conditions of the GNU General Public License cover the whole
28  combination.
29  
30  As a special exception, the copyright holders of this library give you
31  permission to link this library with independent modules to produce an
32  executable, regardless of the license terms of these independent
33  modules, and to copy and distribute the resulting executable under
34  terms of your choice, provided that you also meet, for each linked
35  independent module, the terms and conditions of the license of that
36  module.  An independent module is a module which is not derived from
37  or based on this library.  If you modify this library, you may extend
38  this exception to your version of the library, but you are not
39  obligated to do so.  If you do not wish to do so, delete this
40  exception statement from your version.
41  
42   * end quote.
43   *
44   * This file is licenced under the same conditions as its original (GPL +
45   * "special exception").
46   */
47  
48  package org.ozoneDB.collections;
49  
50  import java.util.Collection  ;
51  import java.util.ConcurrentModificationException  ;
52  import java.util.Iterator  ;
53  import java.util.List  ;
54  import java.util.ListIterator  ;
55  import java.util.RandomAccess  ;
56  
57  /**
58   * A basic implementation of most of the methods in the List interface to make
59   * it easier to create a List based on a random-access data structure. If
60   * the list is sequential (such as a linked list), use AbstractSequentialList.
61   * To create an unmodifiable list, it is only necessary to override the
62   * size() and get(int) methods (this contrasts with all other abstract
63   * collection classes which require an iterator to be provided). To make the
64   * list modifiable, the set(int, Object) method should also be overridden, and
65   * to make the list resizable, the add(int, Object) and remove(int) methods
66   * should be overridden too. Other methods should be overridden if the
67   * backing data structure allows for a more efficient implementation.
68   * The precise implementation used by AbstractList is documented, so that
69   * subclasses can tell which methods could be implemented more efficiently.
70   * <p>
71   *
72   * As recommended by Collection and List, the subclass should provide at
73   * least a no-argument and a Collection constructor. This class is not
74   * synchronized.
75   *
76   * @author Original author unknown
77   * @author Bryce McKinlay
78   * @author Eric Blake <ebb9@email.byu.edu>
79   * @see Collection
80   * @see List
81   * @see java.util.AbstractSequentialList
82   * @see java.util.AbstractCollection
83   * @see ListIterator
84   * @since 1.2
85   * @status updated to 1.4
86   */
87  public abstract class BaseListImpl extends AbstractOzoneCollection implements BaseList {
88  
89      /**
90       * A count of the number of structural modifications that have been made to
91       * the list (that is, insertions and removals). Structural modifications
92       * are ones which change the list size or affect how iterations would
93       * behave. This field is available for use by Iterator and ListIterator,
94       * in order to throw a {@link ConcurrentModificationException} in response
95       * to the next operation on the iterator. This <i>fail-fast</i> behavior
96       * saves the user from many subtle bugs otherwise possible from concurrent
97       * modification during iteration.
98       * <p>
99       *
100      * To make lists fail-fast, increment this field by just 1 in the
101      * <code>add(int, Object)</code> and <code>remove(int)</code> methods.
102      * Otherwise, this field may be ignored.
103      */
104     protected int modCount;
105 
106     /**
107      * The main constructor, for use by subclasses.
108      */
109     protected BaseListImpl() {
110     }
111 
112     public void add(int index, Object   o) {
113         throw new UnsupportedOperationException  ();
114     }
115 
116     /**
117      * Add an element to the end of the list (optional operation). If the list
118      * imposes restraints on what can be inserted, such as no null elements,
119      * this should be documented. This implementation calls
120      * <code>add(size(), o);</code>, and will fail if that version does.
121      *
122      * @param o the object to add
123      * @return true, as defined by Collection for a modified list
124      * @throws UnsupportedOperationException if this list does not support the
125      *         add operation
126      * @throws ClassCastException if o cannot be added to this list due to its
127      *         type
128      * @throws IllegalArgumentException if o cannot be added to this list for
129      *         some other reason
130      * @see #add(int, Object)
131      */
132     public boolean add(Object   o) {
133         add(size(), o);
134         return true;
135     }
136 
137     public boolean addAll(int index, Collection   c) {
138         Iterator   itr = c.iterator();
139         int size = c.size();
140         for (int pos = size; pos > 0; pos--)
141             add(index++, itr.next());
142         return size > 0;
143     }
144 
145     /**
146      * Clear the list, such that a subsequent call to isEmpty() would return
147      * true (optional operation). This implementation calls
148      * <code>removeRange(0, size())</code>, so it will fail unless remove
149      * or removeRange is overridden.
150      *
151      * @throws UnsupportedOperationException if this list does not support the
152      *         clear operation
153      * @see #remove(int)
154      * @see #_org_ozoneDB_removeRange(int, int)
155      */
156     public void clear() {
157         _org_ozoneDB_removeRange(0, size());
158     }
159 
160     /**
161      * Test whether this list is equal to another object. A List is defined to be
162      * equal to an object if and only if that object is also a List, and the two
163      * lists have the same sequence. Two lists l1 and l2 are equal if and only
164      * if <code>l1.size() == l2.size()</code>, and for every integer n between 0
165      * and <code>l1.size() - 1</code> inclusive, <code>l1.get(n) == null ?
166      * l2.get(n) == null : l1.get(n).equals(l2.get(n))</code>.
167      * <p>
168      *
169      * This implementation returns true if the object is this, or false if the
170      * object is not a List.  Otherwise, it iterates over both lists (with
171      * iterator()), returning false if two elements compare false or one list
172      * is shorter, and true if the iteration completes successfully.
173      *
174      * @param o the object to test for equality with this list
175      * @return true if o is equal to this list
176      * @see Object#equals(Object)
177      * @see #hashCode()
178      */
179     public boolean equals(Object   o) {
180         if (o == this)
181             return true;
182         if (! (o instanceof List  ))
183             return false;
184         int size = size();
185         if (size != ((List  ) o).size())
186             return false;
187 
188         Iterator   itr1 = iterator();
189         Iterator   itr2 = ((List  ) o).iterator();
190 
191         while (--size >= 0)
192             if (! equals(itr1.next(), itr2.next()))
193                 return false;
194         return true;
195     }
196 
197     /**
198      * Obtains a hash code for this list. In order to obey the general
199      * contract of the hashCode method of class Object, this value is
200      * calculated as follows:
201      *
202 <pre>hashCode = 1;
203 Iterator i = list.iterator();
204 while (i.hasNext())
205 {
206   Object obj = i.next();
207   hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
208 }</pre>
209      *
210      * This ensures that the general contract of Object.hashCode() is adhered to.
211      *
212      * @return the hash code of this list
213      *
214      * @see Object#hashCode()
215      * @see #equals(Object)
216      */
217     public int hashCode() {
218         int hashCode = 1;
219         Iterator   itr = iterator();
220         int pos = size();
221         while (--pos >= 0)
222             hashCode = 31 * hashCode + hashCode(itr.next());
223         return hashCode;
224     }
225 
226     public int indexOf(Object   o) {
227         ListIterator   itr = listIterator();
228         int size = size();
229         for (int pos = 0; pos < size; pos++)
230             if (equals(o, itr.next()))
231                 return pos;
232         return -1;
233     }
234 
235     /**
236      * Obtain an Iterator over this list, whose sequence is the list order.
237      * This implementation uses size(), get(int), and remove(int) of the
238      * backing list, and does not support remove unless the list does. This
239      * implementation is fail-fast if you correctly maintain modCount.
240      * Also, this implementation is specified by Sun to be distinct from
241      * listIterator, although you could easily implement it as
242      * <code>return listIterator(0)</code>.
243      *
244      * @return an Iterator over the elements of this list, in order
245      * @see #modCount
246      */
247     public Iterator   iterator() {
248 // TODO: replace when FakeFactoryGenerator is ready
249 //        return = _BaseList_IteratorImplFactory.getDefault.create(self());
250         return (Iterator  ) database().createObject(_BaseList_IteratorImpl.class.getName(),
251                 BaseList.class.getName(),
252                 new Object  [] {self()});
253     }
254 
255 
256 
257     /**
258      * Obtain the last index at which a given object is to be found in this
259      * list. This implementation grabs listIterator(size()), then searches
260      * backwards for a match or returns -1.
261      *
262      * @return the greatest integer n such that <code>o == null ? get(n) == null
263      *         : o.equals(get(n))</code>, or -1 if there is no such index
264      */
265     public int lastIndexOf(Object   o) {
266         int pos = size();
267         ListIterator   itr = listIterator(pos);
268         while (--pos >= 0)
269             if (equals(o, itr.previous()))
270                 return pos;
271         return -1;
272     }
273 
274     /**
275      * Obtain a ListIterator over this list, starting at the beginning. This
276      * implementation returns listIterator(0).
277      *
278      * @return a ListIterator over the elements of this list, in order, starting
279      *         at the beginning
280      */
281     public ListIterator   listIterator() {
282         return listIterator(0);
283     }
284 
285     /**
286      * Obtain a ListIterator over this list, starting at a given position.
287      * A first call to next() would return the same as get(index), and a
288      * first call to previous() would return the same as get(index - 1).
289      * <p>
290      *
291      * This implementation uses size(), get(int), set(int, Object),
292      * add(int, Object), and remove(int) of the backing list, and does not
293      * support remove, set, or add unless the list does. This implementation
294      * is fail-fast if you correctly maintain modCount.
295      *
296      * @param index the position, between 0 and size() inclusive, to begin the
297      *        iteration from
298      * @return a ListIterator over the elements of this list, in order, starting
299      *         at index
300      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
301      * @see #modCount
302      */
303     public ListIterator   listIterator(final int index) {
304         if (index < 0 || index > size()) {
305             throw new IndexOutOfBoundsException  ("Index: " + index + ", Size:"
306             + size());
307         }
308 // TODO: replace when FakeFactoryGenerator is ready
309         return (ListIterator  ) database().createObject(_BaseList_ListIteratorImpl.class,
310                 new Class  [] {BaseList.class, int.class},
311                 new Object  [] {self(), new Integer  (index)});
312     }
313 
314     /**
315      * Remove the element at a given position in this list (optional operation).
316      * Shifts all remaining elements to the left to fill the gap. This
317      * implementation always throws an UnsupportedOperationException.
318      * If you want fail-fast iterators, be sure to increment modCount when
319      * overriding this.
320      *
321      * @param index the position within the list of the object to remove
322      * @return the object that was removed
323      * @throws UnsupportedOperationException if this list does not support the
324      *         remove operation
325      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
326      * @see #modCount
327      */
328     public Object   remove(int index) {
329         throw new UnsupportedOperationException  ();
330     }
331 
332     /**
333      * Remove a subsection of the list. This is called by the clear and
334      * removeRange methods of the class which implements subList, which are
335      * difficult for subclasses to override directly. Therefore, this method
336      * should be overridden instead by the more efficient implementation, if one
337      * exists. Overriding this can reduce quadratic efforts to constant time
338      * in some cases!
339      * <p>
340      *
341      * This implementation first checks for illegal or out of range arguments. It
342      * then obtains a ListIterator over the list using listIterator(fromIndex).
343      * It then calls next() and remove() on this iterator repeatedly, toIndex -
344      * fromIndex times.
345      *
346      * @param fromIndex the index, inclusive, to remove from.
347      * @param toIndex the index, exclusive, to remove to.
348      */
349     public void _org_ozoneDB_removeRange(int fromIndex, int toIndex) {
350         ListIterator   itr = listIterator(fromIndex);
351         for (int index = fromIndex; index < toIndex; index++) {
352             itr.next();
353             itr.remove();
354         }
355     }
356 
357     /**
358      * Replace an element of this list with another object (optional operation).
359      * This implementation always throws an UnsupportedOperationException.
360      *
361      * @param index the position within this list of the element to be replaced
362      * @param o the object to replace it with
363      * @return the object that was replaced
364      * @throws UnsupportedOperationException if this list does not support the
365      *         set operation
366      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
367      * @throws ClassCastException if o cannot be added to this list due to its
368      *         type
369      * @throws IllegalArgumentException if o cannot be added to this list for
370      *         some other reason
371      */
372     public Object   set(int index, Object   o) {
373         throw new UnsupportedOperationException  ();
374     }
375 
376     /**
377      * Obtain a List view of a subsection of this list, from fromIndex
378      * (inclusive) to toIndex (exclusive). If the two indices are equal, the
379      * sublist is empty. The returned list should be modifiable if and only
380      * if this list is modifiable. Changes to the returned list should be
381      * reflected in this list. If this list is structurally modified in
382      * any way other than through the returned list, the result of any subsequent
383      * operations on the returned list is undefined.
384      * <p>
385      *
386      * This implementation returns a subclass of AbstractList. It stores, in
387      * private fields, the offset and size of the sublist, and the expected
388      * modCount of the backing list. If the backing list implements RandomAccess,
389      * the sublist will also.
390      * <p>
391      *
392      * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>,
393      * <code>add(int, Object)</code>, <code>remove(int)</code>,
394      * <code>addAll(int, Collection)</code> and
395      * <code>removeRange(int, int)</code> methods all delegate to the
396      * corresponding methods on the backing abstract list, after
397      * bounds-checking the index and adjusting for the offset. The
398      * <code>addAll(Collection c)</code> method merely returns addAll(size, c).
399      * The <code>listIterator(int)</code> method returns a "wrapper object"
400      * over a list iterator on the backing list, which is created with the
401      * corresponding method on the backing list. The <code>iterator()</code>
402      * method merely returns listIterator(), and the <code>size()</code> method
403      * merely returns the subclass's size field.
404      * <p>
405      *
406      * All methods first check to see if the actual modCount of the backing
407      * list is equal to its expected value, and throw a
408      * ConcurrentModificationException if it is not.
409      *
410      * @param fromIndex the index that the returned list should start from
411      *        (inclusive)
412      * @param toIndex the index that the returned list should go to (exclusive)
413      * @return a List backed by a subsection of this list
414      * @throws IndexOutOfBoundsException if fromIndex &lt; 0
415      *         || toIndex &gt; size()
416      * @throws IllegalArgumentException if fromIndex &gt; toIndex
417      * @see ConcurrentModificationException
418      * @see RandomAccess
419      */
420     public List   subList(int fromIndex, int toIndex) {
421         // This follows the specification of AbstractList, but is inconsistent
422         // with the one in List. Don't you love Sun's inconsistencies?
423         if (fromIndex > toIndex)
424             throw new IllegalArgumentException  (fromIndex + " > " + toIndex);
425         if (fromIndex < 0 || toIndex > size())
426             throw new IndexOutOfBoundsException  ();
427 
428         if (this instanceof RandomAccess  ) {
429             return (List  ) database().createObject(
430                     _BaseList_RandomAccessSubListImpl.class,
431                     new Class  [] {BaseList.class, int.class, int.class},
432                     new Object  [] {self(), new Integer  (fromIndex), new Integer  (toIndex)});
433         }
434         return (List  ) database().createObject(
435                 _BaseList_SubListImpl.class,
436                 new Class  [] {BaseList.class, int.class, int.class},
437                 new Object  [] {self(), new Integer  (fromIndex), new Integer  (toIndex)}
438         );
439     }
440     public List   getClientList() {
441         return (List  ) getClientCollection();
442     }
443 
444     protected Iterator   internalIterator() {
445         // todo fix this, need to return an iterator
446         return null;
447     }
448 
449 }
450
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags