Java > Open Source Codes > org > ozoneDB > data > SimpleArrayList


1 // You can redistribute this software and/or modify it under the terms of
2 // the Ozone Core License version 1 published by ozone-db.org.
3 //
4 // The original code and portions created by SMB are
5 // Copyright (C) 1997-@year@ by SMB GmbH. All rights reserved.
6 //
7 // $Id: SimpleArrayList.java,v 1.1 2001/12/18 10:31:30 per_nyfelt Exp $
8 package org.ozoneDB.data;
9 import java.util.Arrays ;
10 import java.util.Comparator ;
11 import java.util.Iterator ;
12 import java.util.NoSuchElementException ;
13 import java.util.Collection ;
14
15 /**
16     Eine Reimplementation einer ArrayList. Eine SimpleArrayList implementiert ein sich nach Bedarf vergrößerndes Array.
17     Das An- und Abhängen am Ende der Liste verläuft in konstanter Zeit, für viele Elemente also linear,
18     am Anfang ist der Rechenzeitverbrauch pro Element linear, für viele Elemente also quadratisch.
19     <P>
20         Alle Zugriffe sind unsynchronisiert. Wenn nötig, muss synchronisiert werden.
21     </P>
22
23     @author <A HREF="http://www.medium.net/">Medium.net</A>
24 */
25 public class SimpleArrayList {
26
27     /** Die konkreten Elemente */
28     protected Object data[];
29
30     /** Index nach dem letzten gültigen Element */
31     protected int size;
32
33     /**
34         Erzeugt eine neue SimpleArrayList.
35
36         @param bufferSize die vorraussichtliche maximale Anzahl von Elementen
37     */
38     public SimpleArrayList(int bufferSize) {
39         data = new Object [bufferSize];
40     }
41
42     /**
43         Erzeugt eine neue SimpleArrayList, die mit den angegebenen Elementen gefüllt ist.
44
45         @param bufferSize die vorraussichtliche maximale Anzahl von Elementen
46         @param dataSource die Quelle der Elemente, mit denen diese SimpleArrayList anfänglich gefüllt werden soll.
47     */
48     public SimpleArrayList(int bufferSize,Iterator dataSource) {
49         this(bufferSize);
50
51         while (dataSource.hasNext())
52             add(dataSource.next());
53     }
54
55
56     /**
57         Erzeugt eine neue SimpleArrayList, die mit den angegebenen Elementen gefüllt ist.
58
59         @param bufferSize die vorraussichtliche maximale Anzahl von Elementen
60         @param dataSource die Quelle der Elemente, mit denen diese SimpleArrayList anfänglich gefüllt werden soll.
61     */
62     public SimpleArrayList(int bufferSize,Collection dataSource) {
63         this(bufferSize,dataSource.iterator());
64     }
65
66     /**
67         Erzeugt eine neue SimpleArrayList, die mit den angegebenen Elementen gefüllt ist.
68
69         @param dataSource die Quelle der Elemente, mit denen diese SimpleArrayList anfänglich gefüllt werden soll.
70     */
71     public SimpleArrayList(Collection dataSource) {
72         this(dataSource.size(),dataSource);
73     }
74
75     /**
76         Stellt eine Mindestkapazität sicher.
77
78         @param minCapacity Anzahl der Einträge, die diese SimpleArrayList mindestens aufnehmen können muss.
79         @throws OutOfMemoryError wenn kein Speicher mehr da war.
80     */
81     protected void ensureCapacity(int minCapacity) throws OutOfMemoryError {
82         if (minCapacity>data.length) {
83             rebuild(calcNewMinCapacityAfterEnlarge(minCapacity));
84         }
85     }
86
87     /**
88         Berechnet die Anzahl der Elemente, die das Daten-Array mindestens haben sollte,
89         wenn diese SimpleArrayList jetzt erweitert werden würde..
90     */
91     protected int calcNewMinCapacityAfterEnlarge() {
92         return (data.length*3)/2+1;
93     }
94
95     /**
96         Berechnet die Anzahl der Elemente, die das Daten-Array mindestens haben sollte,
97         wenn diese SimpleArrayList jetzt erweitert werden würde und mindestens
98         minCapacity Elemente gebrucht werden würden.
99     */
100     protected int calcNewMinCapacityAfterEnlarge(int minCapacity) {
101         int newSize = calcNewMinCapacityAfterEnlarge();
102
103         if (newSize>minCapacity)
104             minCapacity = newSize;
105
106         return minCapacity;
107     }
108
109     /**
110         Erzeugt ein neues Array.
111
112         @param newCapacity die Anzahl der Einträge, die das neue Array halten können soll. Dies muss größer oder gleich von {@link #size} sein.
113         @throws OutOfMemoryError wenn kein Speicher mehr da war.
114     */
115     protected void rebuild(int newCapacity) {
116         Object [] newData = new Object [newCapacity];
117
118         System.arraycopy(data,0,newData,0,size);
119         data = newData;
120     }
121
122     /**
123         Hängt ein neues Element an das Ende der Liste an.
124
125         @param o das anzuhängende Element
126     */
127     public void add(Object o) {
128         ensureCapacity(size+1);
129         data[size++] = o;
130     }
131
132     public void push(Object o) {
133         add(o);
134     }
135
136     /**
137         Setzt das Element o an die Stelle index. Ist die Größe dieser ArrayList nicht größer als die Index-Nummer,
138         so wird die ArrayList entsprechend erweitert. An den neuen Zellen entstehen null-Werte.
139
140         @param o das zu setzende Element
141         @param index die Nummer der Stelle, an der das Element gesetzt werden soll.
142     */
143     public void set(int index,Object o) {
144         ensureCapacity(index+1);
145         data[index] = o;
146         if (size<=index)
147             size = index+1;
148     }
149
150     /**
151         Setzt eine Reihe zusammenhängender Elemente.
152
153         @param start Index des ersten zu überschreibenden Elements
154         @param end Index nach dem letzten zu überschreibenden Element
155         @param o das zu setzende Objekt.
156     */
157     public void setArea(int start,int end,Object o) {
158         ensureCapacity(end);
159
160         for (;start<end;start++)
161             data[start] = o;
162
163         if (size<end)
164             size = end;
165     }
166
167     /**
168         Gibt das Objekt an dem angegeben Index zurück.
169     */
170     public Object get(int index) {
171         return data[index];
172     }
173
174     /**
175         Versucht den Index des angegebenen Objekts in dieser Liste herauszufinden. Die Suche nach dem Objekt wird vom Start der Liste an durchgeführt.
176
177         @param o das gesuchte Objekt.
178         @return der Index des Objekts, oder -1, wenn das Objekt nicht gefunden wurde.
179     */
180     public int indexOf(Object o) {
181         return indexOf(o,0);
182     }
183
184     /**
185         Versucht den Index des angegebenen Objekts in dieser Liste herauszufinden. Die Suche wird vorwärts durchgeführt.
186
187         @param o das gesuchte Objekt.
188         @param startIndex Index, an dem die Suche angefangen werden soll.
189         @return der Index des Objekts, oder -1, wenn das Objekt nicht gefunden wurde.
190     */
191     public int indexOf(Object o,int startIndex) {
192         for (;startIndex<size;startIndex++)
193             if (data[startIndex]==o)
194                 return startIndex;
195
196         return -1;
197     }
198
199     /**
200         Versucht den Index des angegebenen Objekts in dieser Liste herauszufinden. Die Suche nach dem Objekt wird vom Ende der Liste an durchgeführt.
201
202         @param o das gesuchte Objekt.
203         @return der Index des Objekts, oder -1, wenn das Objekt nicht gefunden wurde.
204     */
205     public int lastIndexOf(Object o) {
206         return lastIndexOf(o,size);
207     }
208
209     /**
210         Versucht den Index des angegebenen Objekts in dieser Liste herauszufinden. Die Suche wird rückwarts durchgeführt.
211
212         @param o das gesuchte Objekt.
213         @param startIndex Index nach dem Objekt, an dem die Rückwärts-Suche angefangen werden soll.
214         @return der Index des Objekts, oder -1, wenn das Objekt nicht gefunden wurde.
215     */
216     public int lastIndexOf(Object o,int startIndex) {
217         for (;--startIndex>=0;)
218             if (data[startIndex]==o)
219                 return startIndex;
220
221         return -1;
222     }
223
224     /**
225         Entfernt das angegebene Objekt aus dieser Liste. Die Suche nach dem Objekt wird vom Start der Liste an durchgeführt.
226
227         @param o das zu entfernende Objekt.
228         @return true, wenn das Objekt gefunden wurde, false, wenn nicht.
229     */
230     public boolean remove(Object o) {
231         int index = indexOf(o);
232
233         if (index>=0) {
234             remove(index);
235
236             return true;
237         }
238
239         return false;
240     }
241
242     /**
243         Entfernt das angegebene Objekt aus dieser Liste. Die Suche nach dem Objekt wird vom Ende der Liste an durchgeführt.
244
245         @param o das zu entfernende Objekt.
246         @return true, wenn das Objekt gefunden wurde, false, wenn nicht.
247     */
248     public boolean removeL(Object o) {
249         int index = lastIndexOf(o);
250
251         if (index>=0) {
252             remove(index);
253
254             return true;
255         }
256
257         return false;
258     }
259
260     /**
261         Entfernt das Objekt an dem angegebenen Index.
262
263         @param index Index des zu entfernenden Objekts. Er muss kleiner als {@link #size()} sein.
264         @return das Objekt, was an dem Index stand.
265     */
266     public Object remove(int index) {
267         Object o = data[index];
268
269         System.arraycopy(data,index+1,data,index,size-index-1);
270
271         data[--size] = null; // GarbageCollector
272
273         return o;
274     }
275
276     /**
277         Entfernt das letzte Objekt.
278
279         @return das letzte Objekt in der Liste oder null, wenn die Liste leer war.
280     */
281     public Object removeLast() {
282         int i = size-1;
283
284         if (i>=0) {
285             Object o = data[i];
286
287             data[size = i] = null; // Für den GarbageCollector
288 return o;
289         } else
290             return null;
291     }
292
293     public Object pop() {
294         return removeLast();
295     }
296
297     public Object peek() {
298         if (size!=0) {
299             return data[size-1];
300         } else {
301             return null;
302         }
303     }
304
305     /**
306         Entfernt das erste Objekt. Dies Zeit linear zu Listengröße
307
308         @return das erste Objekt in der Liste oder null, wenn es kein solches Objekt gibt, die Liste also leer war.
309     */
310     public Object removeFirst() {
311         if (size>0) {
312             Object o = data[0];
313
314             System.arraycopy(data,0+1,data,0,--size);
315
316             data[size] = null; // GarbageCollector
317
318             return o;
319         } else
320             return null;
321     }
322
323     /**
324         Fügt ein Element am Anfang dieser ArrayList ein. Alle bestehende Elemente wandern um einen Index weiter.
325     */
326     public void insertAtStart(Object o) {
327         insertSpaceAtStart(1);
328         data[0] = o;
329     }
330
331     /**
332         Verschiebt die Elemente der ArrayList um elementCount Elemente nach hinten. Der Inhalt der Elemente 0..elementCount-1
333         ist nicht definiert.
334     */
335     public void insertSpaceAtStart(int elementCount) {
336         int newSize = size+elementCount;
337
338         if (newSize>data.length) {
339             int newCapacity = calcNewMinCapacityAfterEnlarge(elementCount);
340             Object [] newData = new Object [newCapacity];
341
342             System.arraycopy(data,0,newData,elementCount,size);
343             data = newData;
344         } else {
345             System.arraycopy(data,0,data,elementCount,size);
346         }
347         size = newSize;
348     }
349
350     /**
351         Gibt die aktuelle Größe dieser ArrayList zurück.
352     */
353     public int size() {
354         return size;
355     }
356
357     /**
358         Sortiert diese SimpleArrayList nach ihrer <I>natürlichen Ordnung</I> mittels {@link java.util.Arrays#sort(Object[],int,int)}.
359     */
360     public void sort() {
361         sort(0,size);
362     }
363
364     /**
365         Sortiert diese SimpleArrayList nach ihrer <I>natürlichen Ordnung</I> mittels {@link java.util.Arrays#sort(Object[],int,int)}.
366
367         @param start Index des ersten Elements, was in die Sortierung mit einbezogen werden soll.
368         @param end Index nach dem letzten Elements, was in die Sortierung mit einbezogen werden soll.
369     */
370     public void sort(int start,int end) {
371         Arrays.sort(data,start,end);
372     }
373
374     /**
375         Sortiert diese SimpleArrayList nach dem angegebenen Vergleicher mittels {@link java.util.Arrays#sort(Object[],int,int,Comparator)}.
376
377         @param c der Vergleicher, der beim Sortieren benutzt werden soll.
378     */
379     public void sort(Comparator c) {
380         sort(c,0,size);
381     }
382
383     /**
384         Sortiert diese SimpleArrayList nach dem angegebenen Vergleicher mittels {@link java.util.Arrays#sort(Object[],int,int,Comparator)}.
385
386         @param c der Vergleicher, der beim Sortieren benutzt werden soll.
387         @param start Index des ersten Elements, was in die Sortierung mit einbezogen werden soll.
388         @param end Index nach dem letzten Elements, was in die Sortierung mit einbezogen werden soll.
389     */
390     public void sort(Comparator c,int start,int end) {
391         Arrays.sort(data,start,end,c);
392     }
393
394     /**
395         Löscht den gesamten Inhalt dieser SimpleArrayList. Anschließend werden 0 Elemente enthalten sein.
396     */
397     public void clear() {
398         Arrays.fill(data,0,size,null);
399         size = 0;
400     }
401
402     /**
403         Gibt eine Aufzählung aller Elemente dieser SimpleArrayList zurück.
404         Der Zurückgegebene Iterator darf nur solange benutzt werden, wie auf dieses Objekt nicht schreibend zugegriffen wird.
405     */
406     public Iterator iterator() {
407         return new SimpleIterator() {
408             int index = 0;
409
410             public boolean hasNext() {
411                 return index<size;
412             }
413
414             public Object next() {
415                 if (index<size) {
416                     return data[index++];
417                 } else
418                     throw new NoSuchElementException ();
419             }
420         };
421     }
422
423     /**
424         Druckt alle enthaltenen Elemente aus.
425     */
426     public String toString() {
427         int size = size();
428         StringBuffer b = new StringBuffer (30+size*32);
429
430         b.append("SimpleArrayList[size=");
431         b.append(size);
432         b.append(",data={");
433
434         Iterator i = iterator();
435
436         while (i.hasNext()) {
437             b.append(i.next().toString());
438
439             if (i.hasNext())
440                 b.append(',');
441         }
442         b.append("}]");
443     return b.toString();
444     }
445 }
446

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags