### if.03.22 Procedural Programming
# Römische Zahlen

Diese Aufgabe zielt auf die Analyse und Validierung von Zeichenketten, die Bearbeitung von Zeigern sowie eine einfache rekursive Berechnung ab.

## Einführung

Römische Zahlen werden seit der Antike verwendet. Sie werden durch Buchstaben ausgedrückt, die folgende Werte haben:

+ I: 1
+ V: 5
+ X: 10
+ L: 50
+ C: 100
+ D: 500
+ M: 1000
+ einige weitere Zeichen mit höheren Werten

Der numerische Wert wird einfach durch Addition des Werts jedes Buchstabens berechnet:
> MMCLXXXVII => 1000 + 1000 + 100 + 50 + 10 + 10 + 10 + 5 + 1 + 1 = 2187

Zusätzlich werden Werte abgezogen, wenn ein `I, X oder C` vor dem nächsten größeren Wert steht.
> IV => -1 + 5 = 4   
> IX => -1 + 10 = 9   
> XL => -10 + 50 = 40   
> CD => -100 + 500 = 400

Eine Erweiterung dieser Regel erlaubt das Subtrahieren der darüber liegenden Buchstaben, wenn sie vor noch größeren Werten stehen.

> IC => -1 + 100 = 99 anstelle von XCIX => -10 + 100 - 1 + 10

was die Verwendung der Zahlen vereinfacht. Die Buchstaben `V, L, D` werden niemals als subtraktive Werte verwendet.

Römische Zahlen werden in absteigender Reihenfolge ihres Nennwerts geschrieben, mit Ausnahme des speziellen Falls der Subtraktion.

> MCMLXVII (1967) darf nicht in anderer Reihenfolge geschrieben werden, z.B. IIVXLMCM ist nicht erlaubt

## Aufgabe

Ihre Aufgabe besteht darin, einen abstrakten Datentyp namens `RomanNumber` zu implementieren, der die numerische Darstellung einer Zeichenkette kapselt, die eine gültige römische Zahl darstellt.

Die folgenden Funktionen für den ADT `RomanNumber` sollen implementiert werden:

+ `rn_is_valid_number_str`   
Eine private Funktion, die feststellt, ob eine gegebene Zeichenkette eine gültige römische Zahl darstellt. Wenn die Zeichenkette andere Zeichen als die oben definierten enthält, stellt sie KEINE gültige Zahl dar!   
Die Gültigkeit kann leicht überprüft werden, indem alle Zeichen der Zeichenkette durchlaufen und getestet wird, ob der aktuelle Buchstabe einer definierten entspricht und sein numerischer Wert gleich oder kleiner ist als der numerische Wert des vorherigen Buchstabens. Die einzige Ausnahme von dieser Regel sind gültige Subtraktionsmuster (z.B. IX). Wenn das aktuelle und das nächste Zeichen ein gültiges Subtraktionsmuster bilden, kann mit der bereits implementierten privaten Funktion `rn_is_valid_subtraction` getestet werden. Wenn ein solches gültiges Muster erkannt wurde, bleibt die Zeichenkette für den aktuellen Buchstaben gültig, und die oben genannte Überprüfung kann übersprungen werden. Trotzdem muss der 'nächste' Buchstabe (der zum Testen des Subtraktionsmusters verwendet wurde) weiterhin regelmäßig überprüft werden.
+ `rn_get_value_for_letter`:   
Eine private Funktion, die den numerischen Wert eines einzelnen Buchstabens liefert. Beachten Sie, dass `switch / case`-Anweisungen auch für Zeichen funktionieren.
+  `rn_create`:   
Alloziert eine neue `RomanNumber` aus einem statisch allokierten Pool von Datenstrukturen für den ADT. Der Pool von `RomanNumber`-Daten wird im globalen Bereich mit einer Größe von `MAX_ROMAN_NUMBER_COUNT` wie in `roman_number.c` definiert, allokiert.   
Es kann darauf vertraut werden, dass der Pool ausreichend groß ist, um Instanzen für alle Unittests bereitzustellen, ohne dass Instanzen an den Pool zurückgegeben werden müssen.   
Es kann darauf vertraut werden, dass eine gültige Zeichenkette bereitgestellt wird, jedoch nicht unbedingt eine gültige römische Zahl. Wenn die Zeichenkette keine gültige römische Zahl darstellt, soll eine ungültige (nicht-null) `RomanNumber` bereitgestellt werden. Die gegebene Zeichenkette muss daher mit der privaten Funktion `rn_is_valid_number_str` überprüft werden, ob die Zeichenkette eine gültige römische Zahl darstellt.   
Wenn die gegebene Zeichenkette eine gültige römische Zahl ist, soll ihr numerischer Wert bei der Erstellung berechnet und in den Daten des ADTs gespeichert werden. Die römische Zahl wird einfach durch Addition der Werte ihrer Buchstaben umgewandelt, es sei denn, ein Subtraktionsmuster wird erkannt. In diesem Fall muss der Wert des Buchstabens subtrahiert werden. Verwenden Sie die Funktion `rn_is_valid_subtraction`, um nach Subtraktionen zu suchen.   
*Beachten Sie*, dass eine leere Zeichenkette gültig ist und zu einem Wert von null (0) führt, während eine null-Zeichenkette ungültig ist.
+ `rn_is_valid`:   
Bestimmt, ob die gegebene `RomanNumber` gültig ist. Sie ist gültig, wenn sie weder 0 ist noch aus einer ungültigen römischen Zahl erstellt wurde.
+ `rn_get_value`:   
Liefert den numerischen Wert der gegebenen `RomanNumber`, wie er in den Daten des ADTs gespeichert ist, oder einen Wert kleiner als null, wenn die `RomanNumber` nicht gültig ist.
+ `rn_gcd`:   
Berechnet den größten gemeinsamen Teiler (GGT / GCD) von zwei `RomanNumber`s und gibt das Ergebnis erneut als `RomanNumber` zurück.   
__Wichtiger Hinweis:__ Diese Funktion berechnet DEN GGT NICHT tatsächlich, sondern verwendet die Funktion `int_gcd` zu diesem Zweck. Sie wandelt die römische Zahl nur hin und her.
+ `int_gcd`:
Berechnet tatsächlich den größten gemeinsamen Teiler (GGT / GCD) von zwei positiven Ganzzahlen __mit Rekursion__. Es kann darauf vertraut werden, dass die gegebenen Ganzzahlen immer positiv sind.   
Der GGT ist definiert als:


  - `ggd(x, 0) = x;`
  - `ggd(x, y) = ggd(y, x % y);`   
wobei `%` der Modulo-Operator ist.   
_Beachten Sie_, dass diese Funktion unabhängig getestet wird und implementiert werden kann, auch wenn der ADT nicht funktioniert.

## Aufgaben
+ Erstellen Sie eine Skelettimplementierung des ADTs, um die Unittests kompilierbar zu machen.
+ Implementieren Sie alle erforderlichen Funktionen, um die Unittests zu bestehen.
+ Eine Hauptanwendung ist nicht erforderlich.

### Viel Erfolg!