CircularArrayList


1   /* 
2   * ################################################################
3   * 
4   * ProActive: The Java(TM) library for Parallel, Distributed, 
5   *            Concurrent computing with Security and Mobility
6   * 
7   * Copyright (C) 1997-2002 INRIA/University of Nice-Sophia Antipolis
8   * Contact: proactive-support@inria.fr
9   * 
10  * This library is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU Lesser General Public
12  * License as published by the Free Software Foundation; either
13  * version 2.1 of the License, or any later version.
14  *  
15  * This library is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  * Lesser General Public License for more details.
19  * 
20  * You should have received a copy of the GNU Lesser General Public
21  * License along with this library; if not, write to the Free Software
22  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
23  * USA
24  *  
25  *  Initial developer(s):               The ProActive Team
26  *                        http://www.inria.fr/oasis/ProActive/contacts.html
27  *  Contributor(s): 
28  * 
29  * ################################################################
30  */
31  package org.objectweb.proactive.core.util;
32  
33  import org.apache.log4j.Logger;
34  
35  /**
36   * <p>
37   * Originally written by Dr. Heinz Kabutz in the very excellent 
38   * <a HREF="http://www.smotricz.com/kabutz/">The Java Specialists Newsletter</a>
39   * </p><p>
40   * Cleaned from many infamous bugs and completed.
41   * </p>
42   *
43   * @author  Heinz Kabutz
44   * @version 1.0,  2001/10/23
45   * @since   ProActive 0.9
46   *
47   */
48  public class CircularArrayList
49      extends java.util.AbstractList  
50      implements java.util.List  , java.io.Serializable   {
51          
52      static Logger logger = Logger.getLogger(CircularArrayList.class.getName());
53  
54      private static final int DEFAULT_SIZE = 5;
55  
56      protected Object  [] array;
57      // head points to the first logical element in the array, and
58      // tail points to the element following the last.  This means
59      // that the list is empty when head == tail.  It also means
60      // that the array array has to have an extra space in it.
61      protected int head = 0, tail = 0;
62      // Strictly speaking, we don't need to keep a handle to size,
63      // as it can be calculated programmatically, but keeping it
64      // makes the algorithms faster.
65      protected int size = 0;
66  
67      public CircularArrayList() {
68          this(DEFAULT_SIZE);
69      }
70  
71      public CircularArrayList(int size) {
72          array = new Object  [size];
73      }
74  
75      public CircularArrayList(java.util.Collection   c) {
76          tail = c.size();
77          array = new Object  [c.size()];
78          c.toArray(array);
79      }
80  
81      public String   toString() {
82          StringBuffer   sb = new StringBuffer  ();
83          sb.append("CircularArray size=");
84          sb.append(size);
85          sb.append("\n");
86          for (int i = 0; i < size; i++) {
87              sb.append("[");
88              sb.append(convert(i));
89              sb.append("]=>");
90              sb.append(array[convert(i)]);
91              sb.append(", ");
92          }
93          sb.append("\n");
94          return sb.toString();
95      }
96  
97      public static void main(String  [] args) {
98          CircularArrayList c = new CircularArrayList(5);
99          c.add(0, new Integer  (8));
100         logger.info(c.toString());
101         c.add(0, new Integer  (7));
102         logger.info(c.toString());
103         c.add(0, new Integer  (6));
104         logger.info(c.toString());
105         c.add(0, new Integer  (5));
106         logger.info(c.toString());
107         c.add(0, new Integer  (4));
108         logger.info(c.toString());
109         c.add(0, new Integer  (3));
110         logger.info(c.toString());
111         c.add(0, new Integer  (2));
112         logger.info(c.toString());
113         c.add(0, new Integer  (1));
114         logger.info(c.toString());
115         c.add(0, new Integer  (0));
116         logger.info(c.toString());
117     }
118 
119     public boolean isEmpty() {
120         return head == tail; // or size == 0
121     }
122 
123     // We use this method to ensure that the capacity of the
124     // list will suffice for the number of elements we want to
125     // insert.  If it is too small, we make a new, bigger array
126     // and copy the old elements in.
127     public void ensureCapacity(int minCapacity) {
128         int oldCapacity = array.length;
129         if (minCapacity > oldCapacity) {
130             int newCapacity = (oldCapacity * 3) / 2 + 1;
131             if (newCapacity < minCapacity)
132                 newCapacity = minCapacity;
133             Object   newData[] = new Object  [newCapacity];
134             toArray(newData);
135             tail = size;
136             head = 0;
137             array = newData;
138         }
139     }
140 
141     public int size() {
142         // the size can also be worked out each time as:
143         // (tail + array.length - head) % array.length
144         return size;
145     }
146 
147     public boolean contains(Object   elem) {
148         return indexOf(elem) >= 0;
149     }
150 
151     public int indexOf(Object   elem) {
152         if (elem == null) {
153             for (int i = 0; i < size; i++)
154                 if (array[convert(i)] == null)
155                     return i;
156         } else {
157             for (int i = 0; i < size; i++)
158                 if (elem.equals(array[convert(i)]))
159                     return i;
160         }
161         return -1;
162     }
163 
164     public int lastIndexOf(Object   elem) {
165         if (elem == null) {
166             for (int i = size - 1; i >= 0; i--)
167                 if (array[convert(i)] == null)
168                     return i;
169         } else {
170             for (int i = size - 1; i >= 0; i--)
171                 if (elem.equals(array[convert(i)]))
172                     return i;
173         }
174         return -1;
175     }
176 
177     public Object  [] toArray() {
178         return toArray(new Object  [size]);
179     }
180 
181     public Object  [] toArray(Object   a[]) {
182         //System.out.println("head="+head+" tail="+tail+" size="+size);
183         if (size == 0)
184             return a;
185         if (a.length < size)
186             a =
187                 (Object  []) java.lang.reflect.Array.newInstance(
188                     a.getClass().getComponentType(),
189                     size);
190         if (head < tail) {
191             System.arraycopy(array, head, a, 0, tail - head);
192         } else {
193             System.arraycopy(array, head, a, 0, array.length - head);
194             System.arraycopy(array, 0, a, array.length - head, tail);
195         }
196         if (a.length > size) {
197             a[size] = null;
198         }
199         return a;
200     }
201 
202     public Object   get(int index) {
203         rangeCheck(index);
204         return array[convert(index)];
205     }
206 
207     public Object   set(int index, Object   element) {
208         modCount++;
209         rangeCheck(index);
210         int convertedIndex = convert(index);
211         Object   oldValue = array[convertedIndex];
212         array[convertedIndex] = element;
213         return oldValue;
214     }
215 
216     public boolean add(Object   o) {
217         modCount++;
218         // We have to have at least one empty space
219         ensureCapacity(size + 1 + 1);
220         array[tail] = o;
221         tail = (tail + 1) % array.length;
222         size++;
223         return true;
224     }
225 
226     // This method is the main reason we re-wrote the class.
227     // It is optimized for removing first and last elements
228     // but also allows you to remove in the middle of the list.
229     public Object   remove(int index) {
230         modCount++;
231         rangeCheck(index);
232         int pos = convert(index);
233         // an interesting application of try/finally is to avoid
234         // having to use local variables
235         try {
236             return array[pos];
237         } finally {
238             array[pos] = null; // Let gc do its work
239             // optimized for FIFO access, i.e. adding to back and
240             // removing from front
241             if (pos == head) {
242                 head = (head + 1) % array.length;
243             } else if (pos == tail) {
244                 tail = (tail - 1 + array.length) % array.length;
245             } else {
246                 if (pos > head && pos > tail) { // tail/head/pos
247                     System.arraycopy(array, head, array, head + 1, pos - head);
248                     head = (head + 1) % array.length;
249                 } else {
250                     System.arraycopy(
251                         array,
252                         pos + 1,
253                         array,
254                         pos,
255                         tail - pos - 1);
256                     tail = (tail - 1 + array.length) % array.length;
257                 }
258             }
259             size--;
260         }
261     }
262 
263     public void clear() {
264         modCount++;
265         // Let gc do its work
266         for (int i = 0; i != size; i++) {
267             array[convert(i)] = null;
268         }
269         head = tail = size = 0;
270     }
271 
272     public boolean addAll(java.util.Collection   c) {
273         modCount++;
274         int numNew = c.size();
275         // We have to have at least one empty space
276         ensureCapacity(size + numNew + 1);
277         java.util.Iterator   e = c.iterator();
278         for (int i = 0; i < numNew; i++) {
279             array[tail] = e.next();
280             tail = (tail + 1) % array.length;
281             size++;
282         }
283         return numNew != 0;
284     }
285 
286     public void add(int index, Object   element) {
287         if (index == size) {
288             add(element);
289             return;
290         }
291         modCount++;
292         rangeCheck(index);
293         // We have to have at least one empty space
294         ensureCapacity(size + 1 + 1);
295         int pos = convert(index);
296         if (pos == head) {
297             head = (head - 1 + array.length) % array.length;
298             array[head] = element;
299         } else if (pos == tail) {
300             array[tail] = element;
301             tail = (tail + 1) % array.length;
302         } else {
303             if (pos > head && pos > tail) { // tail/head/pos
304                 System.arraycopy(array, pos, array, head - 1, pos - head + 1);
305                 head = (head - 1 + array.length) % array.length;
306             } else { // head/pos/tail
307                 System.arraycopy(array, pos, array, pos + 1, tail - pos);
308                 tail = (tail + 1) % array.length;
309             }
310             array[pos] = element;
311         }
312         size++;
313     }
314 
315     public boolean addAll(int index, java.util.Collection   c) {
316         throw new UnsupportedOperationException  ("This method left as an exercise to the reader ;-)");
317     }
318 
319     // The convert() method takes a logical index (as if head was
320     // always 0) and calculates the index within array
321     private int convert(int index) {
322         return (index + head) % array.length;
323     }
324 
325     private void rangeCheck(int index) {
326         if (index >= size || index < 0)
327             throw new IndexOutOfBoundsException  (
328                 "Index: " + index + ", Size: " + size);
329     }
330 
331     private void writeObject(java.io.ObjectOutputStream   s)
332         throws java.io.IOException   {
333         s.writeInt(size);
334         for (int i = 0; i != size; i++) {
335             s.writeObject(array[convert(i)]);
336         }
337     }
338 
339     private void readObject(java.io.ObjectInputStream   s)
340         throws java.io.IOException  , ClassNotFoundException   {
341         // Read in size of list and allocate array
342         head = 0;
343         size = tail = s.readInt();
344         if (tail < DEFAULT_SIZE) {
345             array = new Object  [DEFAULT_SIZE];
346         } else {
347             array = new Object  [tail];
348         }
349         // Read in all elements in the proper order.
350         for (int i = 0; i < tail; i++)
351             array[i] = s.readObject();
352     }
353 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags