Class SubArray

java.lang.Object
  SubArray

All Implemented Interfaces:

Comparable

public class SubArray
extends Object
implements Comparable

Datentyp, der einen bestimmten (definierbaren) Teil eines Arrays darstellt. Dieser Teil wird Sub-Array genannt.

Ein Sub-Array ist eindeutig definiert durch drei Angaben:

1. der Gesamt-Array, von dem der Sub-Array einen Teil darstellt,
2. die Stelle im Gesamt-Array, an welcher der Sub-Array beginnt, und
3. die Anzahl der Elemente (also die Laenge) des Sub-Arrays.

In dieser Klasse wird diese Eindeutigkeit umgesetzt durch interne Speicherung

1. einer Referenz zum Gesamt-Array,
2. des Indizes desjenigen Elements des Gesamt-Arrays, mit dem der Sub-Array beginnt, und
3. der Laenge des Sub-Arrays.

Alternativ zu Start-Stelle und Laenge des Sub-Arrays waeren natuerlich auch Start-Stelle und End-Stelle ausreichend, um den Sub-Array eindeutig zu definieren. Warum Start und Laenge besser sind als Beginn und Ende, beschrieb E. W. Dijkstra im Jahre 1982 recht anschaulich. [vgl. EWD831] Diese Klasse stellt der Bequemlichkeit halber Methoden zur Verfuegung, die direkt Beginn- und End-Stelle zurueckliefern, so dass eine entsprechende Umrechnung nur beim Setzen der End-Stelle notwendig ist. Diese Umrechnung ist weiter unten erklaert.

Bemerkenswert ist, dass die Summe der Elemente des Sub-Arrays diesen nicht definiert. Vielmehr ist die Summe eine Eigenschaft des Sub-Arrays. Immer, wenn man Start und Laenge des Sub-Arrays kennt, ist das Berechnen der Summe trivial. Aus einer Summe allein kann man aber selbst bei bekanntem Gesamt-Array oft nicht eindeutig auf das zugehoerige Sub-Array schliessen.

Um das Arbeiten mit der Summe zu erleichtern, verfuegt jede Instanz dieser Klasse ueber einen Cache, der die aktuelle Summe zwischenspeichert, wann immer sie bekannt ist. Dieser Cache bleibt bis zur naechsten Aenderung der Definition des Sub-Arrays gueltig. Die Objektmethoden setSum(int) und getSum() erlauben den direkten Zugruff auf den Cache. Falls beim Aufruf von getSum() der Cache gerade veraltet ist, wird die Summe automatisch mit einer Schleife neu berechnet und der Cache aktualisiert.

Beim Arbeiten mit dieser Klassse wird man in der Regel zunaechst mit einem Konstruktor und dem new-Operator eine neue Instanz, also ein neues Objekt vom Typ SubArray, erstellen. Auf diesem Objekt wird man dann je nach Bedarf Objektmethoden aufrufen (das sind die ohne static), z. B. variablenname.print();.

Eine interessante Anwendung dieser Klasse besteht darin, den Rueckgabe-Typ einer Methode als SubArray zu definieren. Dadurch wird es moeglich, statt etwa einer einzigen Zahl mehrere Zahlen zuruckzugeben -- naemlich genau diejenigen Zahlen, durch die ein Sub-Array definiert wird.

Abgesehen von den Objektmethoden stehen auch einige Klassenmethoden zum Aufruf zur Verfuegung: Die Methoden findLeftEdgeMaximum(int[],int,int) und findRightEdgeMaximum(int[],int,int) ermitteln innerhalb des angegebenen Array-Teils das linke bzw. rechte Randmaximum und geben das Ergebnis als Objekt vom Typ SubArray zurueck. Das kann nuetzlich sein bei Divide-and-Conquer--Algorithmen mit Sub-Arrays.

Beispiel. Die folgende Klasse ermittelt die rechte Haelfte eines an der Kommandozeile eingegebenen Arrays und zeigt ihre Lage im Gesamt-Array an:

 public class RechteHaelfteFinder {
     
     public SubArray findeRechteHaelfte (int[] array) {
          // rechte Haelfte ermitteln:
         int mitte = array.length / 2;
         int startRechteHaelfte = mitte;
         int laengeRechteHaelfte = array.length - mitte;
          // SubArray-Objekt konstruieren und zurueckgeben:
         SubArray ergebnis = new SubArray(array);
         ergebnis.setStart(startRechteHaelfte);
         ergebnis.setLength(laengeRechteHaelfte);
         return ergebnis;
     }
     
     public static void main (String[] args) {
         int[] eingabeArray = SubArray.parseStringArray(args);
          // weil die Methode findeRechteHaelfte(int[]) eine
          // Objektmethode ist (nicht static!), muessen wir
          // erst ein neues Objekt konstruieren:
         RechteHaelfteFinder finder = new RechteHaelfteFinder();
         SubArray rechteHaelfte;
         rechteHaelfte = finder.findeRechteHaelfte(eingabeArray);
         rechteHaelfte.print();
     }
 }
 

Beim Aufruf von der Kommandozeile mit
java RechteHaelfteFinder 1 2 3 4 5 6
wird folgendes Ergebnis ausgegeben:
1 2 3 [4 5 6]

Hinweis. Soll ein Sub-Array subArray anhand der Indizes des ersten und letzten Elements (beginIndex respektive endIndex) definiert werden, koennen folgende Objektmethoden-Aufrufe dazu verwendet werden:

 subArray.setStart(beginIndex);
 subArray.setLength(endIndex - beginIndex + 1);
 

(Die + 1 sind dabei notwendig, denn offensichtlich hat ein Sub-Array, dessen erstes und letztes Element identisch sind (endIndex == beginIndex), immer die Laenge eins. Bei einer einfachen Differenz endIndex - beginIndex wuerde sich dann jedoch faelschlich null fuer die Laenge ergeben. Folglich muss diese Differenz um eins erhoeht werden.)

Warnung. Diese Klasse arbeitet unmittelbar auf dem durch array referenzierten Array. Das Verhalten dieser Klasse bei externer Veraenderung dieses Arrays ist nicht definiert. Um daraus resultierende Probleme zu umgehen, kann der Array beim Instanziieren dieser Klasse dupliziert werden:

 int[] array = new int[] {1, 2, 3};
 SubArray subArray = new SubArray(array.clone());
 

Anmerkung. Die ueberschreibbaren Methoden dieser Klasse werden nicht von anderen Methoden oder Konstruktoren dieser Klasse aufgerufen. Das bedeutet, dass diese Klasse durch Vererbung erweitert werden kann.

Version:

$Revision: 1.2 $

Author:

Arne Johannessen

Constructor Summary

SubArray(int[] array)
Konstruktor; erstellt ein neues SubArray-Objekt fuer den ganzen uebergebenen Array.

SubArray(int[] array, int subArrayStart, int subArrayLength)
Konstruktor; erstellt ein neues SubArray-Objekt mit bestimmten Grenzen.

SubArray(SubArray array, int beginIndex, int endIndex)
Konstruktor; erstellt eine Kopie der uebergebenen SubArray-Instanz mit veraenderten Sub-Array--Grenzen.

Method Summary

protected Object	clone() Erstellt eine exakte Bitkopie dieses SubArray-Objekts, einschliesslich des Inhalts des Gesamt-Arrays.
int	compareTo(Object o) Vergleicht dieses Objekt mit dem angegebenen Objekt.
boolean	equals(Object obj) Prueft, ob ein anderes Objekt gleich diesem ist.
void	findLeftEdgeMaximum() Errechnet das linke Randmaximum dieses Sub-Arrays.
static SubArray	findLeftEdgeMaximum(int[] array, int beginIndex, int endIndex) Errechnet das linke Randmaximum eines Arrays-Teils.
void	findRightEdgeMaximum() Errechnet das rechte Randmaximum dieses Sub-Arrays.
static SubArray	findRightEdgeMaximum(int[] array, int beginIndex, int endIndex) Errechnet das rechte Randmaximum eines Arrays-Teils.
int	getBeginIndex() Liefert den auf den Gesamt-Array bezogenen Index des ersten Elements des Sub-Arrays.
int	getEndIndex() Liefert den auf den Gesamt-Array bezogenen Index des letzten Elements des Sub-Arrays.
(package private) int[]	getFullArray() Zugriffsmethode; liefert den bei der Instanziierung gesetzten Gesamt-Array.
int	getLength() Zugriffsmethode; liefert die Laenge des Sub-Arrays.
int	getStart() Zugriffsmethode; liefert den Index des Beginns des Sub-Arrays.
int	getSum() Liefert die Summe aller Elemente des Sub-Arrays in seinen derzeitigen Grenzen.
int	hashCode() Liefert den Hash-Code fuer diesen Sub-Array.
void	print() Gibt eine String-Repraesentation dieses Objekts auf dem Standard-Ausgabe-Stream aus.
void	setLength(int subArrayLength) Zugriffsmethode; setzt die Laenge des Sub-Arrays.
void	setStart(int subArrayStart) Zugriffsmethode; setzt den Index des Beginns des Sub-Arrays.
void	setSum(int subArraySum) Setzt den Cache der Summe des Sub-Arrays.
int[]	toArray() Kopiert den Sub-Array in einen neu angelegten Integer-Array.
String	toString() Liefert eine String-Repraesentation dieses Objekts.

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

SubArray

public SubArray(int[] array)

Konstruktor; erstellt ein neues SubArray-Objekt fuer den ganzen uebergebenen Array. Der Sub-Array umfasst also den kompletten Gesamt-Array. Der Aufruf dieses Konstruktors ist damit genau gleichbedeutend mit dem folgenden Code-Abschnitt:

 SubArray subArray = new SubArray(array);
 subArray.setStart(0);
 subArray.setLength(array.length);
 

Der Gesamt-Array kann in dieser Instanz nicht veraendert werden; noetigenfalls ist eine neue Instanz dieser Klasse mit einem anderen Array zu erstellen.

Beispiel:

 int[] array = {1, 2, 3};
 SubArray subArray = new SubArray(array);
 System.out.println(subArray);  // [1 2 3]
 

Parameters:

array - der Gesamt-Array fuer die neue Instanz

Throws:

NullPointerException - falls array == null

See Also:

setStart(int), setLength(int)

SubArray

public SubArray(int[] array,
                int subArrayStart,
                int subArrayLength)

Konstruktor; erstellt ein neues SubArray-Objekt mit bestimmten Grenzen. Die Grenzen werden zusammen mit dem Gesamt-Array, auf den sie sich beziehen, als Parameter uebergeben. Der Aufruf dieses Konstruktors ist also genau gleichbedeutend mit dem folgenden Code-Abschnitt:

 SubArray subArray = new SubArray(array);
 subArray.setStart(subArrayStart);
 subArray.setLength(subArrayLength);
 

Der Gesamt-Array kann in dieser Instanz nicht veraendert werden; noetigenfalls ist eine neue Instanz dieser Klasse mit einem anderen Array zu erstellen.

Beispiel:

 int[] array = {1, 2, 3};
 SubArray subArray = new SubArray(array, 1, 1);
 System.out.println(subArray);  // 1 [2] 3
 

Parameters:

array - der Gesamt-Array fuer die neue Instanz

subArrayStart - der Index des Beginns des Sub-Arrays

subArrayLength - die Laenge des Sub-Arrays

Throws:

NullPointerException - falls array == null

See Also:

setStart(int), setLength(int)

SubArray

public SubArray(SubArray array,
                int beginIndex,
                int endIndex)

Konstruktor; erstellt eine Kopie der uebergebenen SubArray-Instanz mit veraenderten Sub-Array--Grenzen. Der Aufruf dieses Konstruktors ist also genau gleichbedeutend mit dem folgenden Code-Abschnitt:

 SubArray subArray = new SubArray(array.getFullArray());
 subArray.setStart(beginIndex);
 subArray.setLength(endIndex - BeginIndex + 1);
 

Im Gegensatz zu den meisten anderen Konstruktoren und Methoden werden hier Indizes auf den Gesamt-Array als Parameter gefordert. Die Indizes zaehlen dabei einschliesslich, so dass im Falle beginIndex == endIndex der neue Sub-Array die Laenge 1 hat.

Der Gesamt-Array kann in dieser Instanz nicht veraendert werden; noetigenfalls ist eine neue Instanz dieser Klasse mit einem anderen Array zu erstellen.

Beispiel. In diesem Code-Schnipsel wird array2 als exakte Kopie von array1 erstellt:

 SubArray original = ...;  // beliebiger Sub-Array
 int beginIndex = original.getStart();
 int endIndex = original.getStart() + original.getLength() - 1;
 SubArray kopie = new SubArray(original, beginIndex, endIndex);
 System.out.println(kopie.equals(original));  // true
 

Parameters:

array - der Gesamt-Array fuer die neue Instanz

beginIndex - der Index des ersten Elements im neuen Sub-Array

endIndex - der Index des letzten Elements im neuen Sub-Array

Throws:

NullPointerException - falls array == null

See Also:

setStart(int), setLength(int)

Method Detail

getFullArray

int[] getFullArray()

Zugriffsmethode; liefert den bei der Instanziierung gesetzten Gesamt-Array.

Returns:

den Gesamt-Array

setStart

public void setStart(int subArrayStart)

Zugriffsmethode; setzt den Index des Beginns des Sub-Arrays. Es werden keinerlei Ueberpruefungen auf sinnvolle Werte durchgefuehrt.

Beispiel:

 int[] array = new int[] {1, 2, 3};
 SubArray subArray = new SubArray(array, 1, 1);
 System.out.println(subArray);  // 1 [2] 3
 subArray.setStart(0);
 System.out.println(subArray);  // [1] 2 3
 

Beim Aufruf dieser Methode wird der interne Cache der Sub-Array--Summe als veraltet markiert. Ein anschliessender Aufruf von getSum() fuehrt zu einer Neuberechnung der Sub-Array--Summe.

Parameters:

subArrayStart - auf den Gesamt-Array bezogener Array-Index, an dem der Sub-Array beginnen soll

See Also:

getSum()

getStart

public int getStart()

Zugriffsmethode; liefert den Index des Beginns des Sub-Arrays.

Der zurueckgegebene Index ist so angepasst, dass sich immer eine gueltige Definition des Sub-Arrays ergibt.

Beispiel:

Wenn
System.out.println(subArray) die Ausgabe "1 2 3 [4 5] 6" erzeugt, hat subArray.getStart() genau den Wert 3.

Returns:

auf den Gesamt-Array bezogener Array-Index, an dem der Sub-Array beginnt

See Also:

getLength()

setLength

public void setLength(int subArrayLength)

Zugriffsmethode; setzt die Laenge des Sub-Arrays. Es werden keinerlei Ueberpruefungen auf sinnvolle Werte durchgefuehrt.

Beispiel:

 int[] array = new int[] {1, 2, 3};
 SubArray subArray = new SubArray(array, 1, 1);
 System.out.println(subArray);  // 1 [2] 3
 subArray.setLength(2);
 System.out.println(subArray);  // 1 [2 3]
 

Beim Aufruf dieser Methode wird der interne Cache der Sub-Array--Summe als veraltet markiert. Ein anschliessender Aufruf von getSum() fuehrt zu einer Neuberechnung der Sub-Array--Summe.

Parameters:

subArrayLength - Laenge des Sub-Arrays

See Also:

getSum()

getLength

public int getLength()

Zugriffsmethode; liefert die Laenge des Sub-Arrays.

Die zurueckgegebene Laenge ist so angepasst, dass sich immer eine gueltige Definition des Sub-Arrays ergibt.

Beispiel:

Wenn
System.out.println(subArray) die Ausgabe "1 2 3 [4 5] 6" erzeugt, hat subArray.getLength() genau den Wert 2.

Returns:

Laenge des Sub-Arrays

See Also:

getStart()

setSum

public void setSum(int subArraySum)

Setzt den Cache der Summe des Sub-Arrays. Es werden keinerlei Ueberpruefungen auf sinnvolle Werte durchgefuehrt.

Diese Methode kann bei bereits bekannter Summe aufgerufen werden, um den internen Cache der Summe aufzufrischen. Beim naechsten Aufruf von getSum() wird direkt der dieser Methode uebergebene Wert zurueckgeliefert, eine Neuberechnung der Sub-Array--Summe findet dann nicht statt.

Parameters:

subArraySum - Summe des Sub-Arrays

See Also:

getSum()

getSum

public int getSum()

Liefert die Summe aller Elemente des Sub-Arrays in seinen derzeitigen Grenzen.

Um Rechenzeit zu sparen, wird nach Moeglichkeit der interne Cache der Summe verwendet. Ist der Cache jedoch nicht mehr frisch, muss die Summe neu berechnet werden. Dies geschieht mittels einer Iteration mit O(n)-Komplexitaet.

Diese Methoden frischen den Cache auf:

• setSum(int)
• getSum()
• findLeftEdgeMaximum()
• findRightEdgeMaximum()

Diese Methoden markieren den Cache als veraltet:

• setStart(int)
• setLength(int)

Beispiel:

 int[] array = new int[] {1, 2, 3};
 SubArray subArray = new SubArray(array, 1, 2);
 System.out.println(subArray);  // 1 [2 3]
 System.out.println(subArray.getSum());  // 5
 

Returns:

die Sub-Array--Summe

See Also:

setSum(int)

getBeginIndex

public int getBeginIndex()

Liefert den auf den Gesamt-Array bezogenen Index des ersten Elements des Sub-Arrays.

subArray.getBeginIndex()
entspricht genau:
subArray.getStart()

Diese Methode ist nur ein Alias fuer die Methode getStart(). Sie stellt das Gegenstueck zu getEndIndex() dar.

Returns:

Index des ersten Elements im Sub-Array

See Also:

getStart()

getEndIndex

public int getEndIndex()

Liefert den auf den Gesamt-Array bezogenen Index des letzten Elements des Sub-Arrays.

subArray.getEndIndex()
entspricht genau:
subArray.getStart() + subArray.getLength() - 1

Returns:

Index des letzten Elements im Sub-Array

findLeftEdgeMaximum

public void findLeftEdgeMaximum()

Errechnet das linke Randmaximum dieses Sub-Arrays. Dies ist genau das Sub-Array, dessen erstes Element mit dem ersten Element dieses Sub-Arrays identisch ist und dessen Summe der Elemente so gross wie moeglich ist.

Das zurueckgegebene Objekt hat einen erfrischten Cache der Sub-Array--Summe.

Beispiel:

 int[] array = new int[] {1, -4, 2};
 SubArray subArray = new SubArray(array);
 System.out.println(subArray);  // [1 -4 2]
 subArray.findLeftEdgeMaximum();
 System.out.println(subArray);  // [1] -4 2
 

See Also:

setSum(int)

findRightEdgeMaximum

public void findRightEdgeMaximum()

Errechnet das rechte Randmaximum dieses Sub-Arrays. Dies ist genau das Sub-Array, dessen letzte Element mit dem letzten Element dieses Sub-Arrays identisch ist und dessen Summe der Elemente so gross wie moeglich ist.

Das zurueckgegebene Objekt hat einen erfrischten Cache der Sub-Array--Summe.

Beispiel:

 int[] array = new int[] {1, -4, 2};
 SubArray subArray = new SubArray(array);
 System.out.println(subArray);  // [1 -4 2]
 subArray.findRightEdgeMaximum();
 System.out.println(subArray);  // 1 -4 [2]
 

See Also:

setSum(int)

findLeftEdgeMaximum

public static SubArray findLeftEdgeMaximum(int[] array,
                                           int beginIndex,
                                           int endIndex)

Errechnet das linke Randmaximum eines Arrays-Teils. Das ist genau das Sub-Array, dessen erstes Element in array den Index beginIndex hat und dessen Summe der Elemente so gross wie moeglich ist.

Das zurueckgegebene Objekt hat einen erfrischten Cache der Sub-Array--Summe.

Beispiel:

 int[] array = new int[] {1, -4, 2};
 SubArray subArray = SubArray.findLeftEdgeMaximum(array, 0, 2);
 System.out.println(subArray);  // [1] -4 2
 

Parameters:

array - der Array, in dem sich der Array-Teil befindet, von dem das Randmaximum zu ermitteln ist

beginIndex - der Index des ersten Elements des Array-Teils

endIndex - der Index des letzten Elements des Array-Teils

Returns:

das linke Randmaximum als neues SubArray-Objekt

See Also:

findLeftEdgeMaximum(), setSum(int)

findRightEdgeMaximum

public static SubArray findRightEdgeMaximum(int[] array,
                                            int beginIndex,
                                            int endIndex)

Errechnet das rechte Randmaximum eines Arrays-Teils. Das ist genau das Sub-Array, dessen letztes Element in array den Index endIndex hat und dessen Summe der Elemente so gross wie moeglich ist.

Das zurueckgegebene Objekt hat einen erfrischten Cache der Sub-Array--Summe.

Beispiel:

 int[] array = new int[] {1, -4, 2};
 SubArray subArray = SubArray.findRightEdgeMaximum(array, 0, 2);
 System.out.println(subArray);  // 1 -4 [2]
 

Parameters:

array - der Array, in dem sich der Array-Teil befindet, von dem das Randmaximum zu ermitteln ist

beginIndex - der Index des ersten Elements des Array-Teils

endIndex - der Index des letzten Elements des Array-Teils

Returns:

das rechte Randmaximum als neues SubArray-Objekt

See Also:

findRightEdgeMaximum(), setSum(int)

print

public void print()

Gibt eine String-Repraesentation dieses Objekts auf dem Standard-Ausgabe-Stream aus.

Beispiel:

 int[] array = new int[] {1, 2, 3};
 SubArray subArray = new SubArray(array);
 subArray.print();  // [1 2 3]
 

Im vorstehenden Beispiel koennte man anstelle von subArray.print(); genau so gut auch System.out.println(subArray); schreiben. Diese beiden Schreibweisen sind genau gleichbedeutend.

See Also:

toString(), PrintStream.println(Object)

toString

public String toString()

Liefert eine String-Repraesentation dieses Objekts. Sie zeigt den Gesamt-Array mit markierten Grenzen des Sub-Arrays, getrennt durch Leerzeichen.

Overrides:

toString in class Object

Returns:

dieses Objekt als String

toArray

public int[] toArray()

Kopiert den Sub-Array in einen neu angelegten Integer-Array.

Returns:

ein Array, dessen Inhalt diesem Sub-Array in seinen derzeitigen Grenzen entspricht.

clone

protected Object clone()
                throws CloneNotSupportedException

Erstellt eine exakte Bitkopie dieses SubArray-Objekts, einschliesslich des Inhalts des Gesamt-Arrays.

Overrides:

clone in class Object

Returns:

ein Klon dieses Objekts vom Typ SubArray

Throws:

CloneNotSupportedException - falls die runtime class dieses Objekts nicht Cloneable implementiert

See Also:

Object.clone(), Cloneable

compareTo

public int compareTo(Object o)

Vergleicht dieses Objekt mit dem angegebenen Objekt. Ist dieses Objekt kleiner, gleich, oder groesser als das angegebene Objekt, wird entsprechend eine negative Zahl, null, oder eine positive Zahl zurueckgegeben.

Hinweis: Diese Klasse hat eine natuerliche Ordnung, die nicht mit equals uebereinstimmt.

Specified by:

compareTo in interface Comparable

Parameters:

o - das zu vergleichende Objekt

Returns:

die Differenz aus der Summe dieses Sub-Arrays und der Summe des Sub-Arrays o

Throws:

NullPointerException - falls o == null

ClassCastException - falls o kein Sub-Array ist

ConcurrentModificationException - falls die beiden Sub-Arrays ungleiche Gesamt-Arrays haben

equals

public boolean equals(Object obj)

Prueft, ob ein anderes Objekt gleich diesem ist. Das ist der Fall genau dann, wenn die beiden Gesamt-Arrays gleich sind und die Definitionen der Sub-Arrays uebereinstimmen.

Overrides:

equals in class Object

Parameters:

obj - das auf Gleichheit zu pruefende Objekt

Returns:

true, falls obj gleich diesem Objekt ist

hashCode

public int hashCode()

Liefert den Hash-Code fuer diesen Sub-Array.

Overrides:

hashCode in class Object

Returns:

den Hash-Code-Wert dieses Sub-Arrays

See Also:

Object.hashCode()