Java > Open Source Codes > org > ozoneDB > collections > FullLinkedListImpl


1 package org.ozoneDB.collections;
2
3 /* LinkedList.java -- Linked list implementation of the List interface
4    Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
5
6 This file is part of GNU Classpath.
7
8 GNU Classpath is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
11 any later version.
12
13 GNU Classpath is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GNU Classpath; see the file COPYING. If not, write to the
20 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21 02111-1307 USA.
22
23 Linking this library statically or dynamically with other modules is
24 making a combined work based on this library. Thus, the terms and
25 conditions of the GNU General Public License cover the whole
26 combination.
27
28 As a special exception, the copyright holders of this library give you
29 permission to link this library with independent modules to produce an
30 executable, regardless of the license terms of these independent
31 modules, and to copy and distribute the resulting executable under
32 terms of your choice, provided that you also meet, for each linked
33 independent module, the terms and conditions of the license of that
34 module. An independent module is a module which is not derived from
35 or based on this library. If you modify this library, you may extend
36 this exception to your version of the library, but you are not
37 obligated to do so. If you do not wish to do so, delete this
38 exception statement from your version. */
39
40 import java.io.ObjectOutputStream ;
41 import java.io.ObjectInputStream ;
42 import java.io.IOException ;
43 import java.lang.reflect.Array ;
44 import java.util.*;
45
46 /**
47  * Linked list implementation of the List interface. In addition to the
48  * methods of the List interface, this class provides access to the first
49  * and last list elements in O(1) time for easy stack, queue, or double-ended
50  * queue (deque) creation. The list is doubly-linked, with traversal to a
51  * given index starting from the end closest to the element.<p>
52  *
53  * LinkedList is not synchronized, so if you need multi-threaded access,
54  * consider using:<br>
55  * <code>List l = Collections.synchronizedList(new LinkedList(...));</code>
56  * <p>
57  *
58  * The iterators are <i>fail-fast</i>, meaning that any structural
59  * modification, except for <code>remove()</code> called on the iterator
60  * itself, cause the iterator to throw a
61  * {@link java.util.ConcurrentModificationException} rather than exhibit
62  * non-deterministic behavior.
63  *
64  * @author Original author unknown
65  * @author Bryce McKinlay
66  * @author Eric Blake <ebb9@email.byu.edu>
67  * @see java.util.List
68  * @see java.util.ArrayList
69  * @see java.util.Vector
70  * @see java.util.Collections#synchronizedList(java.util.List)
71  * @since 1.2
72  * @status missing javadoc, but complete to 1.4
73  */
74 public class FullLinkedListImpl extends BaseListImpl implements FullLinkedList {
75
76     /**
77      * The first element in the list.
78      */
79     private transient Entry first;
80
81     /**
82      * The last element in the list.
83      */
84     private transient Entry last;
85
86     /**
87      * The current length of the list.
88      */
89     private transient int size = 0;
90
91     /**
92      * Class to represent an entry in the list. Holds a single element.
93      */
94     private static final class Entry {
95         /** The element in the list. */
96         Object data;
97
98         /** The next list entry, null if this is last. */
99         Entry next;
100
101         /** The previous list entry, null if this is first. */
102         Entry previous;
103
104         /**
105          * Construct an entry.
106          * @param data the list element
107          */
108         Entry(Object data) {
109             this.data = data;
110         }
111     } // class Entry
112
113     /**
114      * Obtain the Entry at a given position in a list. This method of course
115      * takes linear time, but it is intelligent enough to take the shorter of the
116      * paths to get to the Entry required. This implies that the first or last
117      * entry in the list is obtained in constant time, which is a very desirable
118      * property.
119      * For speed and flexibility, range checking is not done in this method:
120      * Incorrect values will be returned if (n &lt; 0) or (n &gt;= size).
121      *
122      * @param n the number of the entry to get
123      * @return the entry at position n
124      */
125     // Package visible for use in nested classes.
126 Entry getEntry(int n) {
127         Entry e;
128         if (n < size / 2) {
129             e = first;
130             // n less than size/2, iterate from start
131 while (n-- > 0) {
132                 e = e.next;
133             }
134         }
135         else {
136             e = last;
137             // n greater than size/2, iterate from end
138 while (++n < size) {
139                 e = e.previous;
140             }
141         }
142         return e;
143     }
144
145     /**
146      * Remove an entry from the list. This will adjust size and deal with
147      * `first' and `last' appropriatly.
148      *
149      * @param e the entry to remove
150      */
151     // Package visible for use in nested classes.
152 void removeEntry(Entry e) {
153         modCount++;
154         size--;
155         if (size == 0) {
156             first = last = null;
157         } else {
158             if (e == first) {
159                 first = e.next;
160                 e.next.previous = null;
161             } else if (e == last) {
162                 last = e.previous;
163                 e.previous.next = null;
164             } else {
165                 e.next.previous = e.previous;
166                 e.previous.next = e.next;
167             }
168         }
169     }
170
171     /**
172      * Checks that the index is in the range of possible elements (inclusive).
173      *
174      * @param index the index to check
175      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size
176      */
177     private void checkBoundsInclusive(int index) {
178         if (index < 0 || index > size)
179             throw new IndexOutOfBoundsException ("Index: " + index + ", Size:"
180             + size);
181     }
182
183     /**
184      * Checks that the index is in the range of existing elements (exclusive).
185      *
186      * @param index the index to check
187      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size
188      */
189     private void checkBoundsExclusive(int index) {
190         if (index < 0 || index >= size)
191             throw new IndexOutOfBoundsException ("Index: " + index + ", Size:"
192             + size);
193     }
194
195     /**
196      * Create an empty linked list.
197      */
198     public FullLinkedListImpl() {
199     }
200
201     /**
202      * Create a linked list containing the elements, in order, of a given
203      * collection.
204      *
205      * @param c the collection to populate this list from
206      * @throws NullPointerException if c is null
207      */
208     public FullLinkedListImpl(Collection c) {
209         addAll(c);
210     }
211
212     /**
213      * Returns the first element in the list.
214      *
215      * @return the first list element
216      * @throws java.util.NoSuchElementException if the list is empty
217      */
218     public Object getFirst() {
219         if (size == 0)
220             throw new NoSuchElementException();
221         return first.data;
222     }
223
224     /**
225      * Returns the last element in the list.
226      *
227      * @return the last list element
228      * @throws NoSuchElementException if the list is empty
229      */
230     public Object getLast() {
231         if (size == 0)
232             throw new NoSuchElementException();
233         return last.data;
234     }
235
236     /**
237      * Remove and return the first element in the list.
238      *
239      * @return the former first element in the list
240      * @throws NoSuchElementException if the list is empty
241      */
242     public Object removeFirst() {
243         if (size == 0)
244             throw new NoSuchElementException();
245         modCount++;
246         size--;
247         Object r = first.data;
248
249         if (first.next != null)
250             first.next.previous = null;
251         else
252             last = null;
253
254         first = first.next;
255
256         return r;
257     }
258
259     /**
260      * Remove and return the last element in the list.
261      *
262      * @return the former last element in the list
263      * @throws NoSuchElementException if the list is empty
264      */
265     public Object removeLast() {
266         if (size == 0)
267             throw new NoSuchElementException();
268         modCount++;
269         size--;
270         Object r = last.data;
271
272         if (last.previous != null)
273             last.previous.next = null;
274         else
275             first = null;
276
277         last = last.previous;
278
279         return r;
280     }
281
282     /**
283      * Insert an element at the first of the list.
284      *
285      * @param o the element to insert
286      */
287     public void addFirst(Object o) {
288         Entry e = new Entry(o);
289
290         modCount++;
291         if (size == 0)
292             first = last = e;
293         else {
294             e.next = first;
295             first.previous = e;
296             first = e;
297         }
298         size++;
299     }
300
301     /**
302      * Insert an element at the last of the list.
303      *
304      * @param o the element to insert
305      */
306     public void addLast(Object o) {
307         addLastEntry(new Entry(o));
308     }
309
310     /**
311      * Inserts an element at the end of the list.
312      *
313      * @param e the entry to add
314      */
315     private void addLastEntry(Entry e) {
316         modCount++;
317         if (size == 0)
318             first = last = e;
319         else {
320             e.previous = last;
321             last.next = e;
322             last = e;
323         }
324         size++;
325     }
326
327     /**
328      * Returns true if the list contains the given object. Comparison is done by
329      * <code>o == null ? e = null : o.equals(e)</code>.
330      *
331      * @param o the element to look for
332      * @return true if it is found
333      */
334     public boolean contains(Object o) {
335         Entry e = first;
336         while (e != null) {
337             if (equals(o, e.data))
338                 return true;
339             e = e.next;
340         }
341         return false;
342     }
343
344     /**
345      * Returns the size of the list.
346      *
347      * @return the list size
348      */
349     public int size() {
350         return size;
351     }
352
353     /**
354      * Adds an element to the end of the list.
355      *
356      * @param o the entry to add
357      * @return true, as it always succeeds
358      */
359     public boolean add(Object o) {
360         addLastEntry(new Entry(o));
361         return true;
362     }
363
364     /**
365      * Removes the entry at the lowest index in the list that matches the given
366      * object, comparing by <code>o == null ? e = null : o.equals(e)</code>.
367      *
368      * @param o the object to remove
369      * @return true if an instance of the object was removed
370      */
371     public boolean remove(Object o) {
372         Entry e = first;
373         while (e != null) {
374             if (equals(o, e.data)) {
375                 removeEntry(e);
376                 return true;
377             }
378             e = e.next;
379         }
380         return false;
381     }
382
383     /**
384      * Append the elements of the collection in iteration order to the end of
385      * this list. If this list is modified externally (for example, if this
386      * list is the collection), behavior is unspecified.
387      *
388      * @param c the collection to append
389      * @return true if the list was modified
390      * @throws NullPointerException if c is null
391      */
392     public boolean addAll(Collection c) {
393         return addAll(size, c);
394     }
395
396     /**
397      * Insert the elements of the collection in iteration order at the given
398      * index of this list. If this list is modified externally (for example,
399      * if this list is the collection), behavior is unspecified.
400      *
401      * @param c the collection to append
402      * @return true if the list was modified
403      * @throws NullPointerException if c is null
404      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
405      */
406     public boolean addAll(int index, Collection c) {
407         checkBoundsInclusive(index);
408         int csize = c.size();
409
410         if (csize == 0)
411             return false;
412
413         Iterator itr = c.iterator();
414
415         // Get the entries just before and after index. If index is at the start
416 // of the list, BEFORE is null. If index is at the end of the list, AFTER
417 // is null. If the list is empty, both are null.
418 Entry after = null;
419         Entry before = null;
420         if (index != size) {
421             after = getEntry(index);
422             before = after.previous;
423         }
424         else
425             before = last;
426
427         // Create the first new entry. We do not yet set the link from `before'
428 // to the first entry, in order to deal with the case where (c == this).
429 // [Actually, we don't have to handle this case to fufill the
430 // contract for addAll(), but Sun's implementation appears to.]
431 Entry e = new Entry(itr.next());
432         e.previous = before;
433         Entry prev = e;
434         Entry firstNew = e;
435
436         // Create and link all the remaining entries.
437 for (int pos = 1; pos < csize; pos++) {
438             e = new Entry(itr.next());
439             e.previous = prev;
440             prev.next = e;
441             prev = e;
442         }
443
444         // Link the new chain of entries into the list.
445 modCount++;
446         size += csize;
447         prev.next = after;
448         if (after != null)
449             after.previous = e;
450         else
451             last = e;
452
453         if (before != null)
454             before.next = firstNew;
455         else
456             first = firstNew;
457         return true;
458     }
459
460     /**
461      * Remove all elements from this list.
462      */
463     public void clear() {
464         if (size > 0) {
465             modCount++;
466             first = null;
467             last = null;
468             size = 0;
469         }
470     }
471
472     /**
473      * Return the element at index.
474      *
475      * @param index the place to look
476      * @return the element at index
477      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
478      */
479     public Object get(int index) {
480         checkBoundsExclusive(index);
481         return getEntry(index).data;
482     }
483
484     /**
485      * Replace the element at the given location in the list.
486      *
487      * @param index which index to change
488      * @param o the new element
489      * @return the prior element
490      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
491      */
492     public Object set(int index, Object o) {
493         checkBoundsExclusive(index);
494         Entry e = getEntry(index);
495         Object old = e.data;
496         e.data = o;
497         return old;
498     }
499
500     /**
501      * Inserts an element in the given position in the list.
502      *
503      * @param index where to insert the element
504      * @param o the element to insert
505      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
506      */
507     public void add(int index, Object o) {
508         checkBoundsInclusive(index);
509         Entry e = new Entry(o);
510
511         if (index < size) {
512             modCount++;
513             Entry after = getEntry(index);
514             e.next = after;
515             e.previous = after.previous;
516             if (after.previous == null)
517                 first = e;
518             else
519                 after.previous.next = e;
520             after.previous = e;
521             size++;
522         }
523         else
524             addLastEntry(e);
525     }
526
527     /**
528      * Removes the element at the given position from the list.
529      *
530      * @param index the location of the element to remove
531      * @return the removed element
532      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
533      */
534     public Object remove(int index) {
535         checkBoundsExclusive(index);
536         Entry e = getEntry(index);
537         removeEntry(e);
538         return e.data;
539     }
540
541     /**
542      * Returns the first index where the element is located in the list, or -1.
543      *
544      * @param o the element to look for
545      * @return its position, or -1 if not found
546      */
547     public int indexOf(Object o) {
548         int index = 0;
549         Entry e = first;
550         while (e != null) {
551             if (equals(o, e.data))
552                 return index;
553             index++;
554             e = e.next;
555         }
556         return -1;
557     }
558
559     /**
560      * Returns the last index where the element is located in the list, or -1.
561      *
562      * @param o the element to look for
563      * @return its position, or -1 if not found
564      */
565     public int lastIndexOf(Object o) {
566         int index = size - 1;
567         Entry e = last;
568         while (e != null) {
569             if (equals(o, e.data))
570                 return index;
571             index--;
572             e = e.previous;
573         }
574         return -1;
575     }
576
577     public Iterator _org_ozoneDB_internalIterator() {
578         throw new RuntimeException ("Not yet implemented");
579     }
580
581     /**
582      * Obtain a ListIterator over this list, starting at a given index. The
583      * ListIterator returned by this method supports the add, remove and set
584      * methods.
585      *
586      * @param index the index of the element to be returned by the first call to
587      * next(), or size() to be initially positioned at the end of the list
588      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
589      */
590     public ListIterator listIterator(int index) {
591         checkBoundsInclusive(index);
592         return new LinkedListItr(index);
593     }
594
595     /**
596      * Create a shallow copy of this LinkedList (the elements are not cloned).
597      *
598      * @return an object of the same class as this object, containing the
599      * same elements in the same order
600      */
601     public Object clone() {
602         LinkedList copy = null;
603         try {
604             copy = (LinkedList) super.clone();
605         }
606         catch (CloneNotSupportedException ex) {
607         }
608         copy.clear();
609         copy.addAll(this);
610         return copy;
611     }
612
613     /**
614      * Returns an array which contains the elements of the list in order.
615      *
616      * @return an array containing the list elements
617      */
618     public Object [] toArray() {
619         Object [] array = new Object [size];
620         Entry e = first;
621         for (int i = 0; i < size; i++) {
622             array[i] = e.data;
623             e = e.next;
624         }
625         return array;
626     }
627
628     /**
629      * Returns an Array whose component type is the runtime component type of
630      * the passed-in Array. The returned Array is populated with all of the
631      * elements in this LinkedList. If the passed-in Array is not large enough
632      * to store all of the elements in this List, a new Array will be created
633      * and returned; if the passed-in Array is <i>larger</i> than the size
634      * of this List, then size() index will be set to null.
635      *
636      * @param a the passed-in Array
637      * @return an array representation of this list
638      * @throws ArrayStoreException if the runtime type of a does not allow
639      * an element in this list
640      * @throws NullPointerException if a is null
641      */
642     public Object [] toArray(Object [] a) {
643         if (a.length < size)
644             a = (Object []) Array.newInstance(a.getClass().getComponentType(), size);
645         else if (a.length > size)
646             a[size] = null;
647         Entry e = first;
648         for (int i = 0; i < size; i++) {
649             a[i] = e.data;
650             e = e.next;
651         }
652         return a;
653     }
654
655     public int _org_ozoneDB_getModCount() {
656         throw new RuntimeException ("Not yet Implemented");
657     }
658
659     public List _org_ozoneDB_emptyClientCollection() {
660         throw new RuntimeException ("Not yet Implemented");
661     }
662
663     /**
664      * Serializes this object to the given stream.
665      *
666      * @param s the stream to write to
667      * @throws IOException if the underlying stream fails
668      * @serialData the size of the list (int), followed by all the elements
669      * (Object) in proper order
670      */
671     private void writeObject(ObjectOutputStream s) throws IOException {
672         s.defaultWriteObject();
673         s.writeInt(size);
674         Entry e = first;
675         while (e != null) {
676             s.writeObject(e.data);
677             e = e.next;
678         }
679     }
680
681     /**
682      * Deserializes this object from the given stream.
683      *
684      * @param s the stream to read from
685      * @throws ClassNotFoundException if the underlying stream fails
686      * @throws IOException if the underlying stream fails
687      * @serialData the size of the list (int), followed by all the elements
688      * (Object) in proper order
689      */
690     private void readObject(ObjectInputStream s)
691     throws IOException , ClassNotFoundException {
692         s.defaultReadObject();
693         int i = s.readInt();
694         while (--i >= 0)
695             addLastEntry(new Entry(s.readObject()));
696     }
697
698     /**
699      * A ListIterator over the list. This class keeps track of its
700      * position in the list and the two list entries it is between.
701      *
702      * @author Original author unknown
703      * @author Eric Blake <ebb9@email.byu.edu>
704      */
705     private final class LinkedListItr implements ListIterator {
706         /** Number of modifications we know about. */
707         private int knownMod = modCount;
708
709         /** Entry that will be returned by next(). */
710         private Entry next;
711
712         /** Entry that will be returned by previous(). */
713         private Entry previous;
714
715         /** Entry that will be affected by remove() or set(). */
716         private Entry lastReturned;
717
718         /** Index of `next'. */
719         private int position;
720
721         /**
722          * Initialize the iterator.
723          *
724          * @param index the initial index
725          */
726         LinkedListItr(int index) {
727             if (index == size) {
728                 next = null;
729                 previous = last;
730             }
731             else {
732                 next = getEntry(index);
733                 previous = next.previous;
734             }
735             position = index;
736         }
737
738         /**
739          * Checks for iterator consistency.
740          *
741          * @throws ConcurrentModificationException if the list was modified
742          */
743         private void checkMod() {
744             if (knownMod != modCount)
745                 throw new ConcurrentModificationException();
746         }
747
748         /**
749          * Returns the index of the next element.
750          *
751          * @return the next index
752          * @throws ConcurrentModificationException if the list was modified
753          */
754         public int nextIndex() {
755             checkMod();
756             return position;
757         }
758
759         /**
760          * Returns the index of the previous element.
761          *
762          * @return the previous index
763          * @throws ConcurrentModificationException if the list was modified
764          */
765         public int previousIndex() {
766             checkMod();
767             return position - 1;
768         }
769
770         /**
771          * Returns true if more elements exist via next.
772          *
773          * @return true if next will succeed
774          * @throws ConcurrentModificationException if the list was modified
775          */
776         public boolean hasNext() {
777             checkMod();
778             return (next != null);
779         }
780
781         /**
782          * Returns true if more elements exist via previous.
783          *
784          * @return true if previous will succeed
785          * @throws ConcurrentModificationException if the list was modified
786          */
787         public boolean hasPrevious() {
788             checkMod();
789             return (previous != null);
790         }
791
792         /**
793          * Returns the next element.
794          *
795          * @return the next element
796          * @throws ConcurrentModificationException if the list was modified
797          * @throws NoSuchElementException if there is no next
798          */
799         public Object next() {
800             checkMod();
801             if (next == null)
802                 throw new NoSuchElementException();
803             position++;
804             lastReturned = previous = next;
805             next = lastReturned.next;
806             return lastReturned.data;
807         }
808
809         /**
810          * Returns the previous element.
811          *
812          * @return the previous element
813          * @throws ConcurrentModificationException if the list was modified
814          * @throws NoSuchElementException if there is no previous
815          */
816         public Object previous() {
817             checkMod();
818             if (previous == null)
819                 throw new NoSuchElementException();
820             position--;
821             lastReturned = next = previous;
822             previous = lastReturned.previous;
823             return lastReturned.data;
824         }
825
826         /**
827          * Remove the most recently returned element from the list.
828          *
829          * @throws ConcurrentModificationException if the list was modified
830          * @throws IllegalStateException if there was no last element
831          */
832         public void remove() {
833             checkMod();
834             if (lastReturned == null)
835                 throw new IllegalStateException ();
836
837             // Adjust the position to before the removed element, if the element
838 // being removed is behind the cursor.
839 if (lastReturned == previous)
840                 position--;
841
842             next = lastReturned.next;
843             previous = lastReturned.previous;
844             removeEntry(lastReturned);
845             knownMod++;
846
847             lastReturned = null;
848         }
849
850         /**
851          * Adds an element between the previous and next, and advance to the next.
852          *
853          * @param o the element to add
854          * @throws ConcurrentModificationException if the list was modified
855          */
856         public void add(Object o) {
857             checkMod();
858             modCount++;
859             knownMod++;
860             size++;
861             position++;
862             Entry e = new Entry(o);
863             e.previous = previous;
864             e.next = next;
865
866             if (previous != null)
867                 previous.next = e;
868             else
869                 first = e;
870
871             if (next != null)
872                 next.previous = e;
873             else
874                 last = e;
875
876             previous = e;
877             lastReturned = null;
878         }
879
880         /**
881          * Changes the contents of the element most recently returned.
882          *
883          * @param o the new element
884          * @throws ConcurrentModificationException if the list was modified
885          * @throws IllegalStateException if there was no last element
886          */
887         public void set(Object o) {
888             checkMod();
889             if (lastReturned == null)
890                 throw new IllegalStateException ();
891             lastReturned.data = o;
892         }
893     } // class LinkedListItr
894
895 }
896

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags