Aufgabe 1. Wir realisieren in diesem U?bungsblatt die Intervalle aus Hinweis 1. Implementieren Sie dazu die Schnittstelle Interval mit einer Implementierung der Klasse LinkedInterval.
Verwenden Sie als interne Datenstruktur eine verkettete Liste, in der jedes Listenelement ein einfaches Intervall repra?sentiert. Stellen Sie sicher, dass jedes Intervall eine eineindeutige Darstel- lung hat. Die Klasse LinkedInterval ist eine Werteklasse, also unvera?nderbar. Realisieren Sie die angegebenen Methoden union fu?r ?, intersect fu?r ? und contains fu?r ?. Ignorieren Sie zu- na?chst difference; Sie ko?nnen die Ausnahme UnsupportedOperationException werfen. Reali- sieren Sie die angegebenen Methoden so effizient wie mo?glich. Verwenden Sie fu?r die Realisierung keine vorgefertigten Klassen (also insbesondere nichts aus java.util.*), sondern realisieren Sie die Knotenelemente selbst. Es muss einen parameterlosen Konstruktor geben, der ein leeres In- terval erzeugt. Realisieren Sie alle relevanten Methoden. Vergessen Sie nicht eine aussagekra?ftige toString-Methode, die ein Interval scho?n darstellt.
Testen Sie Ihre Implementierung ausgiebig. Versuchen Sie alle mo?glichen Kombinationen von Fa?llen, die durch Ihre Realisierung abgedeckt werden soll auch zu testen. Ihre Tests sind Teil der Abgabe. Dieser Teil der Aufgabenstellung wird wegen der Wichtigkeit wiederholt. Ihre Tests sind Teil der Abgabe.
Machen Sie sich die verschiedenen Fa?lle, die auftreten ko?nnen klar, indem Sie sich Intervalle auf Zahlengeraden visualisieren. Erla?utern Sie zumindest eine der beiden Implementierungen der Methoden union oder intersect anhand einer ca. zweiseitigen separaten Dokumentation, also zusa?tzlich zum aussagekra?ftig dokumentierten Quellcode.
Aufgabe 2. Realisieren Sie zusa?tzlich die difference Methode fu?r /. Beachten Sie, dass I/I? leider nicht immer ein Intervall ist. Betrachten wir zum Beispiel I0..2/I1..1, dann gibt es keine Ober-/Untergrenzen a,b, so dass nur die Zahl 1 fehlen kann1.
Wir behelfen uns damit difference so zu realisieren, dass Intervalle, die sich nur um eine Zahl unterscheiden aber mehr als eine Zahl beinhalten als gleich angesehen werden und wir jeweils das Interval verwenden, das wir darstellen ko?nnen. Im obigen Beispiel wa?re also I0..2/I1..1 = I0..2 aber I1..1/I1..1 = ?. Im allgemeinen verlangen wir zusa?tzlich, dass Ia..b/Ix..x = Ia..b fu?r a < b und a ? x ? b gilt.
Wie in der letzten Aufgabe geho?ren die Tests als integraler Bestandteil zu Ihrer Abgabe.
Hinweis 1. Sie realisieren und nutzen in diesem U?bungsblatt Operationen auf Mengen von Inter- vallen. Ein einfaches Intervall Ia..b ist eine Menge von rationalen Zahlen, die sowohl gro?ßer oder gleich einer Untergrenze a als auch kleiner oder gleich einer Obergrenze b sind. Die Untergrenze muss immer kleiner gleich der Obergrenze sein.
Ia..b ={x?Q | a?x?b?a,b?Q?a?b} Ein Intervall I ist eine Menge von einfachen Intervallen. Eine eindeutige Darstellung erhalten wir
wenn wir verlangen, dass die einfachen Intervalle u?berlappungsfrei sind.
??n i=1
:Iai..bi mit?1?i<n:bi <ai+1 Ein Wert x ist in einem Intervall, wenn er in einem einfachen Intervall des Intervalls ist.
??n i=1
I=
:Iai..bi)gdw?1?i?n:ai ?x?bi Auf Intervallen kann man einige Operationen definieren, wie Vereinigung, Schnitt und Differenz.
Seien I und I? Intervalle, dann definieren wir wie folgt:
I?I? = {x|x?I?x?I?} I?I? = {x|x?I?x?I?} I/I? = {x|x?I?x?/I?}
Beachten Sie, dass I ? I? und I ? I? wieder Intervalle sind.
Hinweis 2. Verwenden Sie fu?r Ihre Tests eine Methode
void assertEquals(Interval expected, Interval actual) ,
die eine Ausnahme wirft, wenn ein Fehler auftritt (also die beiden Intervalle ungleich sind) und nichts passiert, wenn alles passt (also die Intervalle gleich, nicht unbedingt identisch, sind). Das Intervall expected ko?nnen Sie sich mit sicher funktionierenden, einfachen Methoden erzeu- gen und entspricht dem erwartetem Ergebnis. Alternativ ko?nnen Sie auch Listen oder Mengen (aus java.util) von einfachen Intervallen zum U?berpru?fen als expected verwenden. Der Wert actual entsteht durch Anwendung einer der zu testenden Operationen und repra?sentiert das aktuelle Ergebnis.
