Java > Open Source Codes > org > objectstyle > cayenne > modeler > util > CircularArray


1 /* ====================================================================
2  *
3  * The ObjectStyle Group Software License, version 1.1
4  * ObjectStyle Group - http://objectstyle.org/
5  *
6  * Copyright (c) 2002-2005, Andrei (Andrus) Adamchik and individual authors
7  * of the software. All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * 1. Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  *
16  * 2. Redistributions in binary form must reproduce the above copyright
17  * notice, this list of conditions and the following disclaimer in
18  * the documentation and/or other materials provided with the
19  * distribution.
20  *
21  * 3. The end-user documentation included with the redistribution, if any,
22  * must include the following acknowlegement:
23  * "This product includes software developed by independent contributors
24  * and hosted on ObjectStyle Group web site (http://objectstyle.org/)."
25  * Alternately, this acknowlegement may appear in the software itself,
26  * if and wherever such third-party acknowlegements normally appear.
27  *
28  * 4. The names "ObjectStyle Group" and "Cayenne" must not be used to endorse
29  * or promote products derived from this software without prior written
30  * permission. For written permission, email
31  * "andrus at objectstyle dot org".
32  *
33  * 5. Products derived from this software may not be called "ObjectStyle"
34  * or "Cayenne", nor may "ObjectStyle" or "Cayenne" appear in their
35  * names without prior written permission.
36  *
37  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
38  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
39  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
40  * DISCLAIMED. IN NO EVENT SHALL THE OBJECTSTYLE GROUP OR
41  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
42  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
43  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
44  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
45  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
46  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
47  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
48  * SUCH DAMAGE.
49  * ====================================================================
50  *
51  * This software consists of voluntary contributions made by many
52  * individuals and hosted on ObjectStyle Group web site. For more
53  * information on the ObjectStyle Group, please see
54  * <http://objectstyle.org/>.
55  */
56
57 package org.objectstyle.cayenne.modeler.util;
58 /**
59  * A circular array is an array of fixed size as objects are added it will push objects off of the end to
60  * allow space for new objects to be added. This is useful for things like a fixed history size for a navigation tool.
61  *
62  * @author Garry Watkins
63  * @since 1.2
64  */
65 public class CircularArray extends Object {
66     private Object array[] = null;
67     private int head = 0;
68     private int tail = 0;
69     private int count = 0;
70     private int capacity = 0;
71     
72     /**
73      * Creates an array of capacity size.
74      *
75      * @param capacity - size of the new array
76      */
77     public CircularArray(int capacity){
78         if (capacity <= 0){
79             throw new IllegalArgumentException ("Capacity must be greater than zero");
80         }
81         array = new Object [capacity];
82         this.capacity = capacity;
83     }
84     
85     /**
86      * Clears out the contents of the array.
87      */
88     public void clear(){
89         array = new Object [capacity];
90         head = 0;
91         tail = 0;
92         count = 0;
93     }
94     
95     /**
96      * Returns true if the array has no elements;
97      */
98     public boolean isEmpty(){
99         return count == 0;
100     }
101     
102     /**
103      * Adds a new object to the array. If the array is full it will push the oldest
104      * item out of the array.
105      *
106      * @param obj - the object to be added
107      */
108     public void add(Object obj){
109         // we have wrapped and we have to move the head pointer
110 if (count == capacity && tail == head){
111             head = (head + 1) % capacity;
112         }
113
114         array[tail] = obj;
115
116         tail = (tail + 1) % capacity;
117         
118         count++;
119         if (count > capacity) count = capacity;
120     }
121
122     /**
123      * Returns the number of objects stored in the array.
124      */
125     public int capacity(){
126         return capacity;
127     }
128     
129     /*
130      * Converts the logical index into a physical index.
131      */
132     private int convert(int index){
133         return (index + head) % capacity;
134     }
135     
136     /*
137      * Makes sure that the index is within range.
138      */
139     private void rangeCheck(int index) {
140         if (index >= capacity || index < 0){
141             throw new IndexOutOfBoundsException ("Index: " + index+ ", Size: " + capacity);
142         }
143     }
144
145     /**
146      * Returns true if the array contains the specified object.
147      *
148      * @param obj the object to be checked
149      */
150     public boolean contains(Object obj){
151         return indexOf(obj) >= 0;
152     }
153     
154     /**
155      * Gets the object at the specified index.
156      *
157      * @param index the index of the object to be retrieved
158      */
159     public Object get(int index){
160         rangeCheck(index);
161         if (count == 0){
162             return null;
163         }
164         return array[convert(index)];
165     }
166     
167     /**
168      * Returns the index of the specified object
169      *
170      * @param obj the object that is being searched for
171      */
172     public int indexOf(Object obj){
173         for (int i=0; i < capacity; i++){
174             int index = convert(i);
175             if (array[index] == obj){
176                 return i;
177             }
178         }
179         // not found
180 return -1;
181     }
182
183     /**
184      * Removes the specified object from the array
185      *
186      * @param i the index of the object to be removed
187      */
188     public void remove(Object obj) {
189         if (count == 0) return;
190         int i = indexOf(obj);
191
192         while (i >= 0){
193             // convert from logical to physical location
194 int pos = convert(i);
195     
196             if (pos == head){
197                 // move the head up one
198 head = (head+1) % capacity;
199                 array[pos] = null;
200                 count--;
201             }
202             else if (pos == tail){
203                 // move the tail back one
204 tail = (tail -1 + capacity) % capacity;
205                 array[pos] = null;
206                 count--;
207             }
208             else {
209                 // create a brand new array and start it back out at zero
210 Object [] a = new Object [capacity];
211                 int destPos = 0;
212                 int len = 0;
213                 
214                 if (head == tail) {
215                     // most likeley scenario when it is full
216 if (head < pos){
217                         // copy from head to position
218 len = pos - head;
219                         System.arraycopy(array, head, a, destPos, len);
220                         destPos += len;
221
222                         // copy from pos +1 to end
223 len = (capacity -1) - pos;
224                         if (len > 0){
225                             System.arraycopy(array, pos+1, a, destPos, len);
226                             destPos += len;
227                         }
228                         
229                         // copy from zero to head
230 len = head;
231                         if (len > 0){
232                             System.arraycopy(array, 0 , a, destPos, len);
233                         }
234                     }
235                     else if (head > pos){
236                         // copy from head to end of array
237 len = capacity - head;
238                         if (len > 0){
239                             System.arraycopy(array, head, a, destPos, len);
240                             destPos += len;
241                         }
242                         
243                         // copy from zero to pos -1
244 len = pos;
245                         if (len > 0){
246                             System.arraycopy(array, 0, a, destPos, len);
247                             destPos += len;
248                         }
249                         
250                         // copy from pos + 1 to tail
251 len = tail - pos - 1;
252                         if (len > 0){
253                             System.arraycopy(array, pos+1, a, destPos, len);
254                         }
255                     }
256                 }
257                 else if (head < tail){
258                     // copy from head to position -1
259 len = pos - head;
260                     if (len > 0){
261                         System.arraycopy(array, head, a, destPos, len);
262                         destPos += len;
263                     }
264
265                     // copy from position + 1 to tail
266 len = tail - pos;
267                     if (len > 0){
268                         System.arraycopy(array, pos+1, a, destPos, len);
269                         destPos += len;
270                     }
271                 }
272                 else if (head > tail) {
273                     if (head < pos){
274                         // copy from head to position
275 len = pos - head;
276                         System.arraycopy(array, head, a, destPos, len);
277                         destPos += len;
278
279                         // copy from pos +1 to end
280 len = capacity -1 - pos;
281                         if (len > 0){
282                             System.arraycopy(array, pos+1 , a, destPos, len);
283                             destPos += len;
284                         }
285                         
286                         // copy from beginning to tail
287 len = tail;
288                         if (len > 0){
289                             System.arraycopy(array, 0 , a, destPos, len);
290                         }
291                     }
292                     else if (head > pos){
293                         // copy from head to end of array
294 len = capacity - head;
295                         if (len > 0){
296                             System.arraycopy(array, head, a, destPos, len);
297                             destPos += len;
298                         }
299                         
300                         // copy from zero to pos -1
301 len = pos -1;
302                         if (len > 0){
303                             System.arraycopy(array, 0, a, destPos, len);
304                             destPos += len;
305                         }
306                         
307                         // copy from pos+1 to tail
308 len = tail - pos;
309                         if (len > 0){
310                             System.arraycopy(array, pos+1, a, destPos, len);
311                         }
312                     }
313                 }
314                 count--;
315                 array = a;
316                 head = 0;
317                 tail = count;
318             }
319             i = indexOf(obj);
320         }
321     }
322
323     /**
324      * Resizes the array to the specified new size. If the new capacity is smaller than
325      * the current object count in the array, it will keep the newCapacity most recent objects.
326      *
327      * @param newCapacity the new capacity of the array
328      */
329     public void resize(int newCapacity){
330         int i = 0;
331         int offset = 0;
332         if (newCapacity < count){
333             // making it smaller so we want to readjust the first object
334 // to be copied into the new array
335 i = count - newCapacity;
336             offset = count - newCapacity;
337         }
338         Object newArray[] = new Object [newCapacity];
339         for (; i<count; i++){
340              newArray[i - offset] = array[convert(i)];
341         }
342         head = 0;
343         tail = 0;
344         capacity = newCapacity;
345         
346         // adjust the count if it is more than the new capacity
347 if (capacity < count) count = capacity;
348         array = newArray;
349     }
350     
351     /**
352      * Returns the number of objects stored in the array.
353      */
354     public int size(){
355         return count;
356     }
357     
358     /**
359      * Converts the array to an Object array.
360      */
361     public Object [] toArray(){
362         Object [] o = new Object [capacity];
363         for (int i=0; i<capacity; i++){
364              o[i] = array[convert(i)];
365         }
366         return o;
367     }
368     
369     public String internalRep(){
370         Object o = null;
371         
372         StringBuffer sb = new StringBuffer ();
373         sb.append("\n");
374         for (int i=0; i<array.length; i++){
375             sb.append('(').append(i).append(") ");
376                         
377             o = array[i];
378             if (o == null) {
379                 sb.append("null");
380             }
381             else {
382                 sb.append(o.toString());
383             }
384             if (i == head || i == tail){
385                 sb.append('<');
386                 if (i == head) sb.append("h");
387                 if (i == tail) sb.append("t");
388             }
389             sb.append("\n");
390         }
391         
392         sb.append("count = [");
393         sb.append(count);
394         sb.append("]");
395
396         sb.append("\nhead = [");
397         sb.append(head);
398         sb.append("]");
399
400         sb.append("\ntail = [");
401         sb.append(tail);
402         sb.append("]");
403
404         return sb.toString();
405     }
406     
407     public String toString(){
408         Object [] oa = toArray();
409         Object o = null;
410         
411         StringBuffer sb = new StringBuffer ();
412         sb.append("[");
413         for (int i=0; i<oa.length; i++){
414             o = oa[i];
415             if (i>0){
416                 sb.append(", ");
417             }
418             if (o == null) {
419                 sb.append("null");
420             }
421             else {
422                 sb.append(o.toString());
423             }
424         }
425         sb.append("]");
426         return sb.toString();
427     }
428     
429     public static void test(CircularArray a, String expected){
430         String actual = a.toString();
431         if (!actual.equals(expected)){
432             System.out.println("toString() should be \"" + expected + "\" instead got \"" + actual + "\"");
433         }
434     }
435
436     public static void testAdd(CircularArray a, Object obj, String expected, boolean debug){
437         String before = a.internalRep();
438         a.add(obj);
439         String after = a.internalRep();
440         String actual = a.toString();
441         if (debug || !actual.equals(expected)){
442             System.out.println("\n\nAdding = [" + obj + "]");
443             System.out.println("Before =" + before);
444             System.out.println("\nAfter =" + after);
445             System.out.println("toString() should be \"" + expected + "\" instead got \"" + actual + "\"");
446         }
447     }
448
449     public static void testRemove(CircularArray a, Object obj, String expected, boolean debug){
450         int i = a.indexOf(obj);
451         i = a.convert(i);
452         String before = a.internalRep();
453         a.remove(obj);
454         String after = a.internalRep();
455         String actual = a.toString();
456         if (debug || !actual.equals(expected)){
457             System.out.println("\n\nRemoving = [" + obj + "] pos = [" + String.valueOf(i) + "]");
458             System.out.println("Before =" + before);
459             System.out.println("\nAfter =" + after);
460             System.out.println("toString() should be \"" + expected + "\" instead got \"" + actual + "\"");
461         }
462     }
463
464     public static void main(String [] args) {
465         // The following are some unit tests for this class. I don't know how to use JUnit, so I did these in a main class.
466 // Maybe someday I will get some time to learn JUnit.
467 String a = "A";
468         String b = "B";
469         String c = "C";
470         String d = "D";
471         String e = "E";
472         String f = "F";
473         String g = "G";
474         String h = "H";
475         
476         String s = null;
477         
478         CircularArray q = new CircularArray(5);
479         boolean debug = true;
480
481         test(q, "[null, null, null, null, null]");
482         
483         testAdd(q, a, "[A, null, null, null, null]", debug);
484         testRemove(q, a, "[null, null, null, null, null]", debug);
485         testAdd(q, a, "[A, null, null, null, null]", debug);
486
487         testAdd(q, b, "[A, B, null, null, null]", debug);
488         testRemove(q, b, "[A, null, null, null, null]", debug);
489         testAdd(q, b, "[A, B, null, null, null]", debug);
490         
491         testAdd(q, c, "[A, B, C, null, null]", debug);
492         testRemove(q, c, "[A, B, null, null, null]", debug);
493         testAdd(q, c, "[A, B, C, null, null]", debug);
494
495         testAdd(q, d, "[A, B, C, D, null]", debug);
496         testRemove(q, d, "[A, B, C, null, null]", debug);
497         testAdd(q, d, "[A, B, C, D, null]", debug);
498         
499         testAdd(q, e, "[A, B, C, D, E]", debug);
500         testRemove(q, e, "[A, B, C, D, null]", debug);
501         testAdd(q, e, "[A, B, C, D, E]", debug);
502         
503         testAdd(q, f, "[B, C, D, E, F]", debug);
504         testRemove(q, f, "[B, C, D, E, null]", debug);
505         testAdd(q, f, "[B, C, D, E, F]", debug);
506         
507
508         testAdd(q, g, "[C, D, E, F, G]", debug);
509         
510         testRemove(q, e, "[C, D, F, G, null]", debug);
511         
512         testAdd(q, h, "[C, D, F, G, H]", debug);
513         
514         testRemove(q, c, "[D, F, G, H, null]", debug);
515
516         testRemove(q, h, "[D, F, G, null, null]", debug);
517
518         testRemove(q, f, "[D, G, null, null, null]", debug);
519         
520         testRemove(q, g, "[D, null, null, null, null]", debug);
521
522         testRemove(q, d, "[null, null, null, null, null]", debug);
523                 
524         q = new CircularArray(3);
525         q.add(a);
526         int i = q.indexOf(a);
527         if (i != 0){
528             System.out.println("indexOf(a) should be zero instead got [" + String.valueOf(i) + "]");
529         }
530         s = (String ) q.get(0);
531         if (s != a){
532             System.out.println("get(0) should be 'a' instead got [" + s + "]");
533         }
534         i = q.size();
535         if (i != 1){
536             System.out.println("size() should be 1 instead got [" + String.valueOf(i) + "]");
537         }
538         
539         q.add(b);
540         i = q.indexOf(b);
541         if (i != 1){
542             System.out.println("indexOf(b) should be 1 instead got [" + String.valueOf(i) + "]");
543         }
544         s = (String ) q.get(0);
545         if (s != a){
546             System.out.println("get(0) should be 'a' instead got [" + s + "]");
547         }
548         s = (String ) q.get(1);
549         if (s != b){
550             System.out.println("get(1) should be 'b' instead got [" + s + "]");
551         }
552
553         i = q.size();
554         if (i != 2){
555             System.out.println("size() should be 2 instead got [" + String.valueOf(i) + "]");
556         }
557         
558         q.add(c);
559         i = q.indexOf(c);
560         if (i != 2){
561             System.out.println("indexOf(c) should be 2 instead got [" + String.valueOf(i) + "]");
562         }
563         s = (String ) q.get(0);
564         if (s != a){
565             System.out.println("get(0) should be 'a' instead got [" + s + "]");
566         }
567         s = (String ) q.get(1);
568         if (s != b){
569             System.out.println("get(1) should be 'b' instead got [" + s + "]");
570         }
571         s = (String ) q.get(2);
572         if (s != c){
573             System.out.println("get(1) should be 'c' instead got [" + s + "]");
574         }
575         i = q.size();
576         if (i != 3){
577             System.out.println("size() should be 3 instead got [" + String.valueOf(i) + "]");
578         }
579         
580         q.add(d);
581         i = q.size();
582         if (i != 3){
583             System.out.println("size() should be 3 instead got [" + String.valueOf(i) + "]");
584         }
585                 
586         q.add(e);
587         i = q.size();
588         if (i != 3){
589             System.out.println("size() should be 3 instead got [" + String.valueOf(i) + "]");
590         }
591         
592         if (q.contains(a)){
593             System.out.println("A should not be in the q");
594         }
595         
596         i = q.indexOf(c);
597         if (i != 0){
598             System.out.println("indexOf(c) should be zero instead got [" + String.valueOf(i) + "]");
599         }
600         s = (String ) q.get(0);
601         if (s != c){
602             System.out.println("get(0) should be 'c' instead got [" + s + "]");
603         }
604         
605         i = q.indexOf(d);
606         if (i != 1){
607             System.out.println("indexOf(d) should be 1 instead got [" + String.valueOf(i) + "]");
608         }
609         s = (String ) q.get(1);
610         if (s != d){
611             System.out.println("get(1) should be 'd' instead got [" + s + "]");
612         }
613         
614         i = q.indexOf(e);
615         if (i != 2){
616             System.out.println("indexOf(e) should be 2 instead got [" + String.valueOf(i) + "]");
617         }
618         s = (String ) q.get(2);
619         if (s != e){
620             System.out.println("get(2) should be 'e' instead got [" + s + "]");
621         }
622         
623         q.resize(5);
624         i = q.capacity();
625         if (i != 5){
626             System.out.println("size() should be 5 after resizing to 5 instead got [" + String.valueOf(i) + "]");
627         }
628
629         // should be the same after resizing
630 i = q.size();
631         if (i != 3){
632             System.out.println("size() should be 3 instead got [" + String.valueOf(i) + "]");
633         }
634
635         i = q.indexOf(e);
636         if (i != 2){
637             System.out.println("indexOf(e) should be 2 instead got [" + String.valueOf(i) + "]");
638         }
639         s = (String ) q.get(2);
640         if (s != e){
641             System.out.println("get(2) should be 'e' instead got [" + s + "]");
642         }
643         
644         q.resize(2);
645         i = q.capacity();
646         if (i != 2){
647             System.out.println("size() should be 2 after resizing to 2 instead got [" + String.valueOf(i) + "]");
648         }
649     }
650 }
651

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags