001: // You can redistribute this software and/or modify it under the terms of
002: // the Ozone Core License version 1 published by ozone-db.org.
003: //
004: // The original code and portions created by SMB are
005: // Copyright (C) 1997-@year@ by SMB GmbH. All rights reserved.
006: //
007: // $Id: SimpleArrayList.java,v 1.1 2002/07/26 12:25:03 per_nyfelt Exp $
008: package org.ozoneDB.data;
009:
010: import java.util.Arrays;
011: import java.util.Comparator;
012: import java.util.Iterator;
013: import java.util.NoSuchElementException;
014: import java.util.Collection;
015:
016: /**
017: Eine Reimplementation einer ArrayList. Eine SimpleArrayList implementiert ein sich nach Bedarf vergrößerndes Array.
018: Das An- und Abhängen am Ende der Liste verläuft in konstanter Zeit, für viele Elemente also linear,
019: am Anfang ist der Rechenzeitverbrauch pro Element linear, für viele Elemente also quadratisch.
020: <P>
021: Alle Zugriffe sind unsynchronisiert. Wenn nötig, muss synchronisiert werden.
022: </P>
023:
024: @author <A HREF="http://www.medium.net/">Medium.net</A>
025: */
026: public class SimpleArrayList {
027:
028: /** Die konkreten Elemente */
029: protected Object data[];
030:
031: /** Index nach dem letzten gültigen Element */
032: protected int size;
033:
034: /**
035: Erzeugt eine neue SimpleArrayList.
036:
037: @param bufferSize die vorraussichtliche maximale Anzahl von Elementen
038: */
039: public SimpleArrayList(int bufferSize) {
040: data = new Object[bufferSize];
041: }
042:
043: /**
044: Erzeugt eine neue SimpleArrayList, die mit den angegebenen Elementen gefüllt ist.
045:
046: @param bufferSize die vorraussichtliche maximale Anzahl von Elementen
047: @param dataSource die Quelle der Elemente, mit denen diese SimpleArrayList anfänglich gefüllt werden soll.
048: */
049: public SimpleArrayList(int bufferSize, Iterator dataSource) {
050: this (bufferSize);
051:
052: while (dataSource.hasNext())
053: add(dataSource.next());
054: }
055:
056: /**
057: Erzeugt eine neue SimpleArrayList, die mit den angegebenen Elementen gefüllt ist.
058:
059: @param bufferSize die vorraussichtliche maximale Anzahl von Elementen
060: @param dataSource die Quelle der Elemente, mit denen diese SimpleArrayList anfänglich gefüllt werden soll.
061: */
062: public SimpleArrayList(int bufferSize, Collection dataSource) {
063: this (bufferSize, dataSource.iterator());
064: }
065:
066: /**
067: Erzeugt eine neue SimpleArrayList, die mit den angegebenen Elementen gefüllt ist.
068:
069: @param dataSource die Quelle der Elemente, mit denen diese SimpleArrayList anfänglich gefüllt werden soll.
070: */
071: public SimpleArrayList(Collection dataSource) {
072: this (dataSource.size(), dataSource);
073: }
074:
075: /**
076: Stellt eine Mindestkapazität sicher.
077:
078: @param minCapacity Anzahl der Einträge, die diese SimpleArrayList mindestens aufnehmen können muss.
079: @throws OutOfMemoryError wenn kein Speicher mehr da war.
080: */
081: protected void ensureCapacity(int minCapacity)
082: throws OutOfMemoryError {
083: if (minCapacity > data.length) {
084: rebuild(calcNewMinCapacityAfterEnlarge(minCapacity));
085: }
086: }
087:
088: /**
089: Berechnet die Anzahl der Elemente, die das Daten-Array mindestens haben sollte,
090: wenn diese SimpleArrayList jetzt erweitert werden würde..
091: */
092: protected int calcNewMinCapacityAfterEnlarge() {
093: return (data.length * 3) / 2 + 1;
094: }
095:
096: /**
097: Berechnet die Anzahl der Elemente, die das Daten-Array mindestens haben sollte,
098: wenn diese SimpleArrayList jetzt erweitert werden würde und mindestens
099: minCapacity Elemente gebrucht werden würden.
100: */
101: protected int calcNewMinCapacityAfterEnlarge(int minCapacity) {
102: int newSize = calcNewMinCapacityAfterEnlarge();
103:
104: if (newSize > minCapacity)
105: minCapacity = newSize;
106:
107: return minCapacity;
108: }
109:
110: /**
111: Erzeugt ein neues Array.
112:
113: @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.
114: @throws OutOfMemoryError wenn kein Speicher mehr da war.
115: */
116: protected void rebuild(int newCapacity) {
117: Object[] newData = new Object[newCapacity];
118:
119: System.arraycopy(data, 0, newData, 0, size);
120: data = newData;
121: }
122:
123: /**
124: Hängt ein neues Element an das Ende der Liste an.
125:
126: @param o das anzuhängende Element
127: */
128: public void add(Object o) {
129: ensureCapacity(size + 1);
130: data[size++] = o;
131: }
132:
133: public void push(Object o) {
134: add(o);
135: }
136:
137: /**
138: Setzt das Element o an die Stelle index. Ist die Größe dieser ArrayList nicht größer als die Index-Nummer,
139: so wird die ArrayList entsprechend erweitert. An den neuen Zellen entstehen null-Werte.
140:
141: @param o das zu setzende Element
142: @param index die Nummer der Stelle, an der das Element gesetzt werden soll.
143: */
144: public void set(int index, Object o) {
145: ensureCapacity(index + 1);
146: data[index] = o;
147: if (size <= index)
148: size = index + 1;
149: }
150:
151: /**
152: Setzt eine Reihe zusammenhängender Elemente.
153:
154: @param start Index des ersten zu überschreibenden Elements
155: @param end Index nach dem letzten zu überschreibenden Element
156: @param o das zu setzende Objekt.
157: */
158: public void setArea(int start, int end, Object o) {
159: ensureCapacity(end);
160:
161: for (; start < end; start++)
162: data[start] = o;
163:
164: if (size < end)
165: size = end;
166: }
167:
168: /**
169: Gibt das Objekt an dem angegeben Index zurück.
170: */
171: public Object get(int index) {
172: return data[index];
173: }
174:
175: /**
176: Versucht den Index des angegebenen Objekts in dieser Liste herauszufinden. Die Suche nach dem Objekt wird vom Start der Liste an durchgeführt.
177:
178: @param o das gesuchte Objekt.
179: @return der Index des Objekts, oder -1, wenn das Objekt nicht gefunden wurde.
180: */
181: public int indexOf(Object o) {
182: return indexOf(o, 0);
183: }
184:
185: /**
186: Versucht den Index des angegebenen Objekts in dieser Liste herauszufinden. Die Suche wird vorwärts durchgeführt.
187:
188: @param o das gesuchte Objekt.
189: @param startIndex Index, an dem die Suche angefangen werden soll.
190: @return der Index des Objekts, oder -1, wenn das Objekt nicht gefunden wurde.
191: */
192: public int indexOf(Object o, int startIndex) {
193: for (; startIndex < size; startIndex++)
194: if (data[startIndex] == o)
195: return startIndex;
196:
197: return -1;
198: }
199:
200: /**
201: Versucht den Index des angegebenen Objekts in dieser Liste herauszufinden. Die Suche nach dem Objekt wird vom Ende der Liste an durchgeführt.
202:
203: @param o das gesuchte Objekt.
204: @return der Index des Objekts, oder -1, wenn das Objekt nicht gefunden wurde.
205: */
206: public int lastIndexOf(Object o) {
207: return lastIndexOf(o, size);
208: }
209:
210: /**
211: Versucht den Index des angegebenen Objekts in dieser Liste herauszufinden. Die Suche wird rückwarts durchgeführt.
212:
213: @param o das gesuchte Objekt.
214: @param startIndex Index nach dem Objekt, an dem die Rückwärts-Suche angefangen werden soll.
215: @return der Index des Objekts, oder -1, wenn das Objekt nicht gefunden wurde.
216: */
217: public int lastIndexOf(Object o, int startIndex) {
218: for (; --startIndex >= 0;)
219: if (data[startIndex] == o)
220: return startIndex;
221:
222: return -1;
223: }
224:
225: /**
226: Entfernt das angegebene Objekt aus dieser Liste. Die Suche nach dem Objekt wird vom Start der Liste an durchgeführt.
227:
228: @param o das zu entfernende Objekt.
229: @return true, wenn das Objekt gefunden wurde, false, wenn nicht.
230: */
231: public boolean remove(Object o) {
232: int index = indexOf(o);
233:
234: if (index >= 0) {
235: remove(index);
236:
237: return true;
238: }
239:
240: return false;
241: }
242:
243: /**
244: Entfernt das angegebene Objekt aus dieser Liste. Die Suche nach dem Objekt wird vom Ende der Liste an durchgeführt.
245:
246: @param o das zu entfernende Objekt.
247: @return true, wenn das Objekt gefunden wurde, false, wenn nicht.
248: */
249: public boolean removeL(Object o) {
250: int index = lastIndexOf(o);
251:
252: if (index >= 0) {
253: remove(index);
254:
255: return true;
256: }
257:
258: return false;
259: }
260:
261: /**
262: Entfernt das Objekt an dem angegebenen Index.
263:
264: @param index Index des zu entfernenden Objekts. Er muss kleiner als {@link #size()} sein.
265: @return das Objekt, was an dem Index stand.
266: */
267: public Object remove(int index) {
268: Object o = data[index];
269:
270: System
271: .arraycopy(data, index + 1, data, index, size - index
272: - 1);
273:
274: data[--size] = null; // GarbageCollector
275:
276: return o;
277: }
278:
279: /**
280: Entfernt das letzte Objekt.
281:
282: @return das letzte Objekt in der Liste oder null, wenn die Liste leer war.
283: */
284: public Object removeLast() {
285: int i = size - 1;
286:
287: if (i >= 0) {
288: Object o = data[i];
289:
290: data[size = i] = null; // Für den GarbageCollector
291: return o;
292: } else
293: return null;
294: }
295:
296: public Object pop() {
297: return removeLast();
298: }
299:
300: public Object peek() {
301: if (size != 0) {
302: return data[size - 1];
303: } else {
304: return null;
305: }
306: }
307:
308: /**
309: Entfernt das erste Objekt. Dies Zeit linear zu Listengröße
310:
311: @return das erste Objekt in der Liste oder null, wenn es kein solches Objekt gibt, die Liste also leer war.
312: */
313: public Object removeFirst() {
314: if (size > 0) {
315: Object o = data[0];
316:
317: System.arraycopy(data, 0 + 1, data, 0, --size);
318:
319: data[size] = null; // GarbageCollector
320:
321: return o;
322: } else
323: return null;
324: }
325:
326: /**
327: Fügt ein Element am Anfang dieser ArrayList ein. Alle bestehende Elemente wandern um einen Index weiter.
328: */
329: public void insertAtStart(Object o) {
330: insertSpaceAtStart(1);
331: data[0] = o;
332: }
333:
334: /**
335: Verschiebt die Elemente der ArrayList um elementCount Elemente nach hinten. Der Inhalt der Elemente 0..elementCount-1
336: ist nicht definiert.
337: */
338: public void insertSpaceAtStart(int elementCount) {
339: int newSize = size + elementCount;
340:
341: if (newSize > data.length) {
342: int newCapacity = calcNewMinCapacityAfterEnlarge(elementCount);
343: Object[] newData = new Object[newCapacity];
344:
345: System.arraycopy(data, 0, newData, elementCount, size);
346: data = newData;
347: } else {
348: System.arraycopy(data, 0, data, elementCount, size);
349: }
350: size = newSize;
351: }
352:
353: /**
354: Gibt die aktuelle Größe dieser ArrayList zurück.
355: */
356: public int size() {
357: return size;
358: }
359:
360: /**
361: Sortiert diese SimpleArrayList nach ihrer <I>natürlichen Ordnung</I> mittels {@link java.util.Arrays#sort(Object[],int,int)}.
362: */
363: public void sort() {
364: sort(0, size);
365: }
366:
367: /**
368: Sortiert diese SimpleArrayList nach ihrer <I>natürlichen Ordnung</I> mittels {@link java.util.Arrays#sort(Object[],int,int)}.
369:
370: @param start Index des ersten Elements, was in die Sortierung mit einbezogen werden soll.
371: @param end Index nach dem letzten Elements, was in die Sortierung mit einbezogen werden soll.
372: */
373: public void sort(int start, int end) {
374: Arrays.sort(data, start, end);
375: }
376:
377: /**
378: Sortiert diese SimpleArrayList nach dem angegebenen Vergleicher mittels {@link java.util.Arrays#sort(Object[],int,int,Comparator)}.
379:
380: @param c der Vergleicher, der beim Sortieren benutzt werden soll.
381: */
382: public void sort(Comparator c) {
383: sort(c, 0, size);
384: }
385:
386: /**
387: Sortiert diese SimpleArrayList nach dem angegebenen Vergleicher mittels {@link java.util.Arrays#sort(Object[],int,int,Comparator)}.
388:
389: @param c der Vergleicher, der beim Sortieren benutzt werden soll.
390: @param start Index des ersten Elements, was in die Sortierung mit einbezogen werden soll.
391: @param end Index nach dem letzten Elements, was in die Sortierung mit einbezogen werden soll.
392: */
393: public void sort(Comparator c, int start, int end) {
394: Arrays.sort(data, start, end, c);
395: }
396:
397: /**
398: Löscht den gesamten Inhalt dieser SimpleArrayList. Anschließend werden 0 Elemente enthalten sein.
399: */
400: public void clear() {
401: Arrays.fill(data, 0, size, null);
402: size = 0;
403: }
404:
405: /**
406: Gibt eine Aufzählung aller Elemente dieser SimpleArrayList zurück.
407: Der Zurückgegebene Iterator darf nur solange benutzt werden, wie auf dieses Objekt nicht schreibend zugegriffen wird.
408: */
409: public Iterator iterator() {
410: return new SimpleIterator() {
411: int index = 0;
412:
413: public boolean hasNext() {
414: return index < size;
415: }
416:
417: public Object next() {
418: if (index < size) {
419: return data[index++];
420: } else
421: throw new NoSuchElementException();
422: }
423: };
424: }
425:
426: /**
427: Druckt alle enthaltenen Elemente aus.
428: */
429: public String toString() {
430: int size = size();
431: StringBuffer b = new StringBuffer(30 + size * 32);
432:
433: b.append("SimpleArrayList[size=");
434: b.append(size);
435: b.append(",data={");
436:
437: Iterator i = iterator();
438:
439: while (i.hasNext()) {
440: b.append(i.next().toString());
441:
442: if (i.hasNext())
443: b.append(',');
444: }
445: b.append("}]");
446: return b.toString();
447: }
448: }
|