16. Kopie bei der Reihungsimplementierung

Bei der Semantik der Methode copy ist folgende Überlegung wichtig. Nach dem Aufruf von

kopie = original.copy

soll der Aufruf

kopie.equals(original)

das Ergebnis true ergeben. Wenn anschließend mit

kopie.add(einElement)

der Kopie ein Element hinzugefügt wird, sollen die beiden Warteschlangen nicht mehr gleich sein: Der Aufruf

kopie.equals(original)

soll das Ergebnis false ergeben. Wenn dann dasselbe Element auch dem Original mit

original.add(einElement)

hinzugefügt wird, soll der Vergleich

kopie.equals(original)

wieder true ergeben.

Des Weiteren, nach den Aufrufen von

kopie.copy(original);

original.add(einElement);

kopie.add(anderesElement); // einElement != anderesElement

mit

einElement != anderesElement

soll der Aufruf

kopie.equals(original);

das Ergebnis false ergeben.

Dieser Umstand kann in einer Scala-Testprozedur[1] folgendermaßen wiedergegeben werden:

def copySemantics[T](original: ExtQ[T], kopie: ExtQ[T], einElement: T, anderesElement: T) = {

assert(einElement != anderesElement) // Kriterium für Parameter

kopie.copy(original)

assert(kopie.equals(original)) // [2]

kopie.add(einElement);

assert(!kopie.equals(original))

original.add(einElement)

assert(kopie.equals(original))

kopie.copy(original);

original.add(einElement);

kopie.add(anderesElement);

assert(!kopie.equals(original)); }

Diese Forderung hilft, die Entscheidung zwischen vier Alternativen zu treffen. Sie können durch folgende Objektdiagramme dargestellt werden:

Abbildung30: Erste Alternative: Referenzkopie

Abbildung 31: Zweite Alternative: flache Kopie

Abbildung 32: Dritte Alternative: logische Kopie

Abbildung 33: Vierte Alternative: tiefe Kopie

Die Überprüfung durch die obigen Kriterien ergibt, zeigt, dass die obige Forderung nur durch die dritte Alternative erfüllt wird.

1. Die erste Alternative verletzt das Kriterium

kopie.copy(original)

assert(kopie.equals(original))

kopie.add(anElement)

assert(!kopie.equals(original)) // AssertionException

Der Grund hierfür ist, dass die Variablen kopie und original dasselbe ArrayQ-Objekt referenzieren, daher das Eintragen in kopie auch eine Eintragung von original bewirkt. Diese Vorgehensweise heißt Referenzkopie.

2. Die zweite Alternative (die flache Kopie) verletzt das Kriterium

kopie.copy(original)

original.add(anElement)

kopie.add(otherElement)

assert(!kopie.equals(original)) // AssertionException

Der Grund hierfür ist, dass kopie und original einen gemeinsamen Datenbereich teilen und das Eintragen von otherElement in kopie die Eintragung von anElement überschreibt.

3. Die dritte Alternative erfüllt alle Kriterien; wir nennen diese logische Kopie.

4. Die vierte Alternative verletzt das Kriterium

kopie.copy(original)

assert(kopie.equals(original) // AssertionException

Der Grund hierfür ist, dass wir equals nur dann true zurückgibt, wenn die beiden ExtArrayQ-Objekte dieselben (und nicht nur gleiche) Elemente enthalten: equals erwartet gleiche Referenzen in den ExtArrayQ-Objekten. Hier wurden jedoch auch die in original eingetragenen Elementobjekte kopiert. So ein Kopiervorgang heißt tiefe Kopie. Wenn equals als tiefe Gleichheit definiert wird, dann soll auch tiefe Kopie programmiert werden. Bei komplexen Datenstrukturen[3] kann dies jedoch sehr aufwändig werden.

Wir wählen also die logische Kopie für die Implementierung der Methode copy aus:

def copy(q: ExtQ[E]) = { // ExtItArrayQ.scala

this.clear

val that = q.asInstanceOf[ExtArrayQ[E]]

for (i <- 0 until that.anzahl)

this.add(that.inhalt((that.ältestes + i) % that.inhalt.length)) }

Die Ausnahme OutOfMemoryError kann beim Erzeugen des Ergebnisobjekts ausgeworfen werden. Wenn das nicht der Fall ist, können die Elemente der aktuellen Warteschlange in einer Schleife gelesen und in die neue Warteschlange eingetragen werden.

Eine primitivere (aber ebenfalls funktionsfähige) Lösung würde den gesamten Inhalt des Parameterobjekts (samt „Müll“) kopieren:

this jüngstes = that.jüngstes

this ältestes = that.ältestes

this anzahl = that.anzahl

for (i <- 0 until that.inhalt.length)

this.inhalt(i) = that.inhalt(i)

[1] dies ist eine generische Methode; beim Aufruf wird aus den aktuellen Parametern der Typparameter vom Compiler ermittelt

[2] assert ist eine Methode aus scala.Predef, entspricht assert in Java

[3] z.B. bei einer komplexen Programmoberfläche mit sehr vielen Button, Canvas, usw. Elementen.

Version: 5. Dezember 2010