simplearraylist.java

Java的面向对象数据库系统的源代码

// You can redistribute this software and/or modify it under the terms of
// the Ozone Core License version 1 published by ozone-db.org.
//
// The original code and portions created by SMB are
// Copyright (C) 1997-@year@ by SMB GmbH. All rights reserved.
//
// $Id: SimpleArrayList.java,v 1.1 2001/12/18 10:31:30 per_nyfelt Exp $
package org.ozoneDB.data;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Collection;

/**
	Eine Reimplementation einer ArrayList. Eine SimpleArrayList implementiert ein sich nach Bedarf vergr鲞erndes Array.
	Das An- und Abh鋘gen am Ende der Liste verl鋟ft in konstanter Zeit, f黵 viele Elemente also linear,
	am Anfang ist der Rechenzeitverbrauch pro Element linear, f黵 viele Elemente also quadratisch.
	<P>
		Alle Zugriffe sind unsynchronisiert. Wenn n鰐ig, muss synchronisiert werden.
	</P>

	@author <A HREF="http://www.medium.net/">Medium.net</A>
*/
public class SimpleArrayList {

	/** Die konkreten Elemente */
	protected Object data[];

	/** Index nach dem letzten g黮tigen Element */
	protected int size;

	/**
		Erzeugt eine neue SimpleArrayList.

		@param bufferSize die vorraussichtliche maximale Anzahl von Elementen
	*/
	public SimpleArrayList(int bufferSize) {
		data = new Object[bufferSize];
	}

	/**
		Erzeugt eine neue SimpleArrayList, die mit den angegebenen Elementen gef黮lt ist.

		@param bufferSize die vorraussichtliche maximale Anzahl von Elementen
		@param dataSource die Quelle der Elemente, mit denen diese SimpleArrayList anf鋘glich gef黮lt werden soll.
	*/
	public SimpleArrayList(int bufferSize,Iterator dataSource) {
		this(bufferSize);

		while (dataSource.hasNext())
			add(dataSource.next());
	}


	/**
		Erzeugt eine neue SimpleArrayList, die mit den angegebenen Elementen gef黮lt ist.

		@param bufferSize die vorraussichtliche maximale Anzahl von Elementen
		@param dataSource die Quelle der Elemente, mit denen diese SimpleArrayList anf鋘glich gef黮lt werden soll.
	*/
	public SimpleArrayList(int bufferSize,Collection dataSource) {
		this(bufferSize,dataSource.iterator());
	}

	/**
		Erzeugt eine neue SimpleArrayList, die mit den angegebenen Elementen gef黮lt ist.

		@param dataSource die Quelle der Elemente, mit denen diese SimpleArrayList anf鋘glich gef黮lt werden soll.
	*/
	public SimpleArrayList(Collection dataSource) {
		this(dataSource.size(),dataSource);
	}

	/**
		Stellt eine Mindestkapazit鋞 sicher.

		@param minCapacity Anzahl der Eintr鋑e, die diese SimpleArrayList mindestens aufnehmen k鰊nen muss.
		@throws OutOfMemoryError wenn kein Speicher mehr da war.
	*/
	protected void ensureCapacity(int minCapacity) throws OutOfMemoryError {
		if (minCapacity>data.length) {
			rebuild(calcNewMinCapacityAfterEnlarge(minCapacity));
		}
	}

	/**
		Berechnet die Anzahl der Elemente, die das Daten-Array mindestens haben sollte,
		wenn diese SimpleArrayList jetzt erweitert werden w黵de..
	*/
	protected int calcNewMinCapacityAfterEnlarge() {
		return (data.length*3)/2+1;
	}

	/**
		Berechnet die Anzahl der Elemente, die das Daten-Array mindestens haben sollte,
		wenn diese SimpleArrayList jetzt erweitert werden w黵de und mindestens
		minCapacity Elemente gebrucht werden w黵den.
	*/
	protected int calcNewMinCapacityAfterEnlarge(int minCapacity) {
		int newSize = calcNewMinCapacityAfterEnlarge();

		if (newSize>minCapacity)
			minCapacity = newSize;

		return minCapacity;
	}

	/**
		Erzeugt ein neues Array.

		@param newCapacity die Anzahl der Eintr鋑e, die das neue Array halten k鰊nen soll. Dies muss gr鲞er oder gleich von {@link #size} sein.
		@throws OutOfMemoryError wenn kein Speicher mehr da war.
	*/
	protected void rebuild(int newCapacity) {
		Object[] newData = new Object[newCapacity];

		System.arraycopy(data,0,newData,0,size);
		data = newData;
	}

	/**
		H鋘gt ein neues Element an das Ende der Liste an.

		@param o das anzuh鋘gende Element
	*/
	public void add(Object o) {
		ensureCapacity(size+1);
		data[size++] = o;
	}

	public void push(Object o) {
		add(o);
	}

	/**
		Setzt das Element o an die Stelle index. Ist die Gr鲞e dieser ArrayList nicht gr鲞er als die Index-Nummer,
		so wird die ArrayList entsprechend erweitert. An den neuen Zellen entstehen null-Werte.

		@param o			das zu setzende Element
		@param index	die Nummer der Stelle, an der das Element gesetzt werden soll.
	*/
	public void set(int index,Object o) {
		ensureCapacity(index+1);
		data[index] = o;
		if (size<=index)
			size = index+1;
	}

	/**
		Setzt eine Reihe zusammenh鋘gender Elemente.

		@param start	Index des ersten zu 黚erschreibenden Elements
		@param end		Index nach dem letzten zu 黚erschreibenden Element
		@param o			das zu setzende Objekt.
	*/
	public void setArea(int start,int end,Object o) {
		ensureCapacity(end);

		for (;start<end;start++)
			data[start] = o;

		if (size<end)
			size = end;
	}

	/**
		Gibt das Objekt an dem angegeben Index zur點k.
	*/
	public Object get(int index) {
		return data[index];
	}

	/**
		Versucht den Index des angegebenen Objekts in dieser Liste herauszufinden. Die Suche nach dem Objekt wird vom Start der Liste an durchgef黨rt.

		@param o das gesuchte Objekt.
		@return der Index des Objekts, oder -1, wenn das Objekt nicht gefunden wurde.
	*/
	public int indexOf(Object o) {
		return indexOf(o,0);
	}

	/**
		Versucht den Index des angegebenen Objekts in dieser Liste herauszufinden. Die Suche wird vorw鋜ts durchgef黨rt.

		@param o das gesuchte Objekt.
		@param startIndex Index, an dem die Suche angefangen werden soll.
		@return der Index des Objekts, oder -1, wenn das Objekt nicht gefunden wurde.
	*/
	public int indexOf(Object o,int startIndex) {
		for (;startIndex<size;startIndex++)
			if (data[startIndex]==o)
				return startIndex;

		return -1;
	}

	/**
		Versucht den Index des angegebenen Objekts in dieser Liste herauszufinden. Die Suche nach dem Objekt wird vom Ende der Liste an durchgef黨rt.

		@param o das gesuchte Objekt.
		@return der Index des Objekts, oder -1, wenn das Objekt nicht gefunden wurde.
	*/
	public int lastIndexOf(Object o) {
		return lastIndexOf(o,size);
	}

	/**
		Versucht den Index des angegebenen Objekts in dieser Liste herauszufinden. Die Suche wird r點kwarts durchgef黨rt.

		@param o das gesuchte Objekt.
		@param startIndex Index nach dem Objekt, an dem die R點kw鋜ts-Suche angefangen werden soll.
		@return der Index des Objekts, oder -1, wenn das Objekt nicht gefunden wurde.
	*/
	public int lastIndexOf(Object o,int startIndex) {
		for (;--startIndex>=0;)
			if (data[startIndex]==o)
				return startIndex;

		return -1;
	}

	/**
		Entfernt das angegebene Objekt aus dieser Liste. Die Suche nach dem Objekt wird vom Start der Liste an durchgef黨rt.

		@param o das zu entfernende Objekt.
		@return true, wenn das Objekt gefunden wurde, false, wenn nicht.
	*/
	public boolean remove(Object o) {
		int index = indexOf(o);

		if (index>=0) {
			remove(index);

			return true;
		}

		return false;
	}

	/**
		Entfernt das angegebene Objekt aus dieser Liste. Die Suche nach dem Objekt wird vom Ende der Liste an durchgef黨rt.

		@param o das zu entfernende Objekt.
		@return true, wenn das Objekt gefunden wurde, false, wenn nicht.
	*/
	public boolean removeL(Object o) {
		int index = lastIndexOf(o);

		if (index>=0) {
			remove(index);

			return true;
		}

		return false;
	}

	/**
		Entfernt das Objekt an dem angegebenen Index.

		@param index Index des zu entfernenden Objekts. Er muss kleiner als {@link #size()} sein.
		@return das Objekt, was an dem Index stand.
	*/
	public Object remove(int index) {
		Object o = data[index];

		System.arraycopy(data,index+1,data,index,size-index-1);

		data[--size] = null; // GarbageCollector

		return o;
	}

	/**
		Entfernt das letzte Objekt.

		@return das letzte Objekt in der Liste oder null, wenn die Liste leer war.
	*/
	public Object removeLast() {
		int i = size-1;

		if (i>=0) {
			Object o = data[i];

			data[size = i] = null; // F黵 den GarbageCollector
			return o;
		} else
			return null;
	}

	public Object pop() {
		return removeLast();
	}

	public Object peek() {
		if (size!=0) {
			return data[size-1];
		} else {
			return null;
		}
	}

	/**
		Entfernt das erste Objekt. Dies Zeit linear zu Listengr鲞e

		@return das erste Objekt in der Liste oder null, wenn es kein solches Objekt gibt, die Liste also leer war.
	*/
	public Object removeFirst() {
		if (size>0) {
			Object o = data[0];

			System.arraycopy(data,0+1,data,0,--size);

			data[size] = null; // GarbageCollector

			return o;
		} else
			return null;
	}

	/**
		F黦t ein Element am Anfang dieser ArrayList ein. Alle bestehende Elemente wandern um einen Index weiter.
	*/
	public void insertAtStart(Object o) {
		insertSpaceAtStart(1);
		data[0] = o;
	}

	/**
		Verschiebt die Elemente der ArrayList um elementCount Elemente nach hinten. Der Inhalt der Elemente 0..elementCount-1
		ist nicht definiert.
	*/
	public void insertSpaceAtStart(int elementCount) {
		int newSize = size+elementCount;

		if (newSize>data.length) {
			int				newCapacity = calcNewMinCapacityAfterEnlarge(elementCount);
			Object[]	newData			= new Object[newCapacity];

			System.arraycopy(data,0,newData,elementCount,size);
			data = newData;
		} else {
			System.arraycopy(data,0,data,elementCount,size);
		}
		size = newSize;
	}

	/**
		Gibt die aktuelle Gr鲞e dieser ArrayList zur點k.
	*/
	public int size() {
		return size;
	}

	/**
		Sortiert diese SimpleArrayList nach ihrer <I>nat黵lichen Ordnung</I> mittels {@link java.util.Arrays#sort(Object[],int,int)}.
	*/
	public void sort() {
		sort(0,size);
	}

	/**
		Sortiert diese SimpleArrayList nach ihrer <I>nat黵lichen Ordnung</I> mittels {@link java.util.Arrays#sort(Object[],int,int)}.

		@param start Index des ersten Elements, was in die Sortierung mit einbezogen werden soll.
		@param end Index nach dem letzten Elements, was in die Sortierung mit einbezogen werden soll.
	*/
	public void sort(int start,int end) {
		Arrays.sort(data,start,end);
	}

	/**
		Sortiert diese SimpleArrayList nach dem angegebenen Vergleicher mittels {@link java.util.Arrays#sort(Object[],int,int,Comparator)}.

		@param c der Vergleicher, der beim Sortieren benutzt werden soll.
	*/
	public void sort(Comparator c) {
		sort(c,0,size);
	}

	/**
		Sortiert diese SimpleArrayList nach dem angegebenen Vergleicher mittels {@link java.util.Arrays#sort(Object[],int,int,Comparator)}.

		@param c der Vergleicher, der beim Sortieren benutzt werden soll.
		@param start Index des ersten Elements, was in die Sortierung mit einbezogen werden soll.
		@param end Index nach dem letzten Elements, was in die Sortierung mit einbezogen werden soll.
	*/
	public void sort(Comparator c,int start,int end) {
		Arrays.sort(data,start,end,c);
	}

	/**
		L鰏cht den gesamten Inhalt dieser SimpleArrayList. Anschlie遝nd werden 0 Elemente enthalten sein.
	*/
	public void clear() {
		Arrays.fill(data,0,size,null);
		size = 0;
	}

	/**
		Gibt eine Aufz鋒lung aller Elemente dieser SimpleArrayList zur點k.
		Der Zur點kgegebene Iterator darf nur solange benutzt werden, wie auf dieses Objekt nicht schreibend zugegriffen wird.
	*/
	public Iterator iterator() {
		return new SimpleIterator() {
			int index = 0;

			public boolean hasNext() {
				return index<size;
			}

			public Object next() {
				if (index<size) {
					return data[index++];
				} else
					throw new NoSuchElementException();
			}
		};
	}

	/**
		Druckt alle enthaltenen Elemente aus.
	*/
	public String toString() {
		int						size	= size();
		StringBuffer	b			= new StringBuffer(30+size*32);

		b.append("SimpleArrayList[size=");
		b.append(size);
		b.append(",data={");

		Iterator i = iterator();

		while (i.hasNext()) {
			b.append(i.next().toString());

			if (i.hasNext())
				b.append(',');
		}
		b.append("}]");
  	return b.toString();
	}
}