Bei der Programmierung der Methode equals für die Reihungsimplementierung stellt sich eine Reihe von Fragen, wann genau zwei Warteschlangen als gleich erkannt werden sollen. Beispielsweise sollten sie gleich sein, wenn in die erste die Zahlen (z.B. als Integer-Objekte) 1, 2, 3 und 4 eingetragen und dann die Älteste (nämlich 1) gelöscht wurde, in die zweite die Zahlen 5, 2, 3 und 4 eingetragen und dann die Älteste (nämlich 5) gelöscht wurde. Am (vereinfachten[1]) Objektdiagramm der Reihungsimplementierung kann die Situation folgendermaßen dargestellt werden:
Abbildung 26: Gleiche Warteschlangen
Sie sollen ebenso gleich sein, wenn sich der Inhalt folgendermaßen gestaltet:
Abbildung 27: Weitere gleiche Warteschlangen
Bei der Überprüfung der Gleichheit soll also kein „Müll“ (schon gelöschte Elemente und „leere Plätze“) beachtet werden. Die Position der Elemente ist irrelevant, d.h. etwaige „Verschiebungen“ sollen berücksichtigt werden; alleine ihre Reihenfolge zählt. Die Möglichkeit des Überlaufs in der Reihung soll auch mit einbezogen werden.
Weitere Fragen stellen sich beim Vergleich der einzelnen Elemente miteinander. Sollen zum Beispiel die folgenden beiden Warteschlangen als gleich erkannt werden?
Abbildung 28: Elemente mit gleichem Inhalt
Hier handelt es sich um Elemente mit dem gleichen Inhalt, aber nicht identische Elemente. Oder sollte für die Gleichheit folgende Situation erwartet werden?
Abbildung 29: Gleiche Elemente
Bei einfach strukturierten Elementen (wie hier vom Typ Integer) ist es nicht schwer, die inhaltliche Gleichheit zu überprüfen; aber die eingetragenen Objekte können auch ganz komplexe Objektstrukturen (mit teilweise sich überlappenden Teilen) sein, wo die Gleichheit untereinander nicht trivial ist. Aus diesem Grund ist es zweckmäßig, die zwei Warteschlangen auf der Abbildung 28 als ungleich, auf der Abbildung 29 als gleich zu betrachten: Wir definieren zwei Warteschlangen als gleich, wenn sie identische Objekte in derselben Reihenfolge enthalten.
Bei der Implementierung der Methode equals aus der obigen Schnittstelle taucht noch ein technisches Problem auf. Der Parameter von equals ist vom Schnittstellentyp, da bei der Definition der Schnittstelle noch keine Klassen zur Verfügung stehen. Die Methode equals muss jedoch auf die Attribute des Parameterobjekts zugreifen können, um die gespeicherten Elemente zu lesen. Aus diesem Grund wird in der Schnittstelle beschrieben (@result), dass bei unterschiedlichen Warteschlangentypen das Ergebnis false ist: Unsere Methoden sollen nicht eine Reihung mit einer verkettete Liste vergleichen können, geschweige von weiteren Implementierungen, die mit anderen Techniken möglich sind.
Wir müssen also den Parameter vom Schnittstellentyp zum Klassentyp konvertieren („heruntercasten“). Wenn wir zuvor den Typ des übergebenen Parameterobjekts überprüft haben, wird dabei keine ClassCastException ausgelöst.
Anschließend können wir die Anzahl der in beiden Warteschlangen enthaltenen Elemente mit Referenzgleichheit (==) vergleichen[2]. Wenn sie ungleich sind, ist das Ergebnis false. Ansonsten können die Elemente miteinander verglichen werden.
Hierbei verwenden wir zwei Indizes dieses und jenes, die die beiden Reihungen (angefangen jeweils bei ältestes, unter Berücksichtigung des Überlaufs) durchlaufen. In jedem Schritt vergleichen wir die enthaltenen Elemente mit dem Operator für Referenzgleichheit == bzw. !=. Wenn sich keines der Elementpaare als ungleich erwiesen hat, ist das Ergebnis true.
Aus diesen Überlegungen ergibt sich die folgende Methodenimplementierung:
def equals(q: ExtQ[E]): Boolean = { // ExtItArrayQ.scala if (q.getClass != this.getClass) return false val that = q.asInstanceOf[ExtArrayQ[E]] // [3] if (this.anzahl != that.anzahl) return false
var dieses = this.ältestes // [4] var jenes = that.ältestes for (i <- 0 until anzahl) { if (this.inhalt(dieses) != that.inhalt(jenes)) return false dieses = (dieses + 1) % this.inhalt.length jenes = (jenes + 1) % that.inhalt.length } return true }
[1] In unsere Warteschlangen werden keine Zahlen, sondern Objekte eingetragen: Sie enthalten also keine Werte, sondern Referenzen (hier auf Integer-Objekte, z.B. mit dem Inhalt 1, 2, 3 und 4).
[2] In Scala kann (im Gegensatz zu Java) auch die Referenzgleichheit überschrieben werden – aber das ist dann eine Angelegenheit des Benutzers.
[3] casting in Scala mit asInstanceOf
[4] Int durch Inferenz
Version: 5. Dezember 2010
© Prof. Solymosi, 2010, Beuth-Hochschule für Technik Berlin