Programmieren in C++ im SS 2011 — Projekt

Hier finden Sie der Spezifikation der möglichen Projekte.

Allgemeine Anforderungen für alle Projekte

Unabhängig vom Projekt sollen Sie natürlich Code nach der Art schreiben, wie Sie es in der Vorlesung gelernt haben, insbesondere:

• Gutes Klassendesign, mit zwei separaten Dateien pro Klasse (Deklarationen in einer .h Datei, Implementierungen in einer .cpp Datei). Dazu ein funktionierendes Makefile, das nur das kompiliert, was sich geändert hat, und die vier Standard-Targets build, test, lint und clean realisiert.

• Nachvollziehbare Benennung von Klassen, Methoden und Membervariablen. In der Regel wird nicht abgekürzt, es sei denn ein zentrale Variable taucht in einer Funktion viele Male auf und ein langer Name würde den Code deutlich schwerer lesbar machen. Private Membervariablen beginnen grundsätzlich mit einem Unterstrich.
• Jede Klasse, jede Methode und jede Membervariable sollte dokumentiert werden. Wenn die Funktion einfach / klar ersichtlich ist, reicht eine kurze Erklärung, ansonsten eine angemessen ausführliche Erklärung. Das gilt auch für Codeblöcke in größeren Funktionen.

• Unit tests für jede Methode, die für die korrekte Funktion des Programms wichtig ist. Bei Methoden mit vielen Spezial/Grenzfällen, nicht unbedingt alle aber mindestens drei solcher Fälle testen. Bei allen Klassen, wo es Sinn macht, eine asString Methode implementieren, das hilft beim Debuggen und beim Testen.

• Der gesamte Code sollte mit null Fehlern durch den Linter gehen. Benutzung von // NOLINT nur in Ausnahme- (= von der Dozentin genehmigten) Fällen.

• Alle ausführbaren Programme enden auf Main. Bei Aufruf ohne Argument kommt eine "usage info", die genug Information enthält um zu verstehen, wie man das Programm benutzt. Handling von Kommandozeilenoptionen über die getopt Bibliothek, siehe Vorlesung 7.

Projekt 1 (Suchmaschine)

Kurzbeschreibung: Eine Suchmaschine für eine gegebene Menge von Dateien auf der eigenen Festplatte.

Geforderte Funktionalität:

• Ein ausführbares Programm BuildIndexMain, das eine (über die Kommandozeile) gegebene Menge von Dateien "parsed" (= in die einzelnen Worte zerlegt), dafür einen invertierten Index baut (= pro Wort, das irgendwo vorkommt, die Liste aller Dateien, die dieses Wort enthalten, berechnet), und diesen in einer bzw. mehreren Datei speichert (siehe "Technische Realisierung").

• Ein ausführbares Programm QueryIndexMain, das mit Hilfe eines zuvor gebauten Indexes eine gegebene Suchanfrage (= einfach eine Folge von Wörtern, wie bei Google) beantwortet, und den Namen von den Dateien (mit vollständiger Pfadangabe) zurückliefert, die diese Suchworte enthalten. Dabei sollte von dem vorberechneten Index nur der Teil eingelesen werden, der auch zur Beantwortung der Suchanfrage benötigt wird.

• Zusätzlich zu den Namen der Dateien sollten auch Zeilen aus der Datei angezeigt werden, die die eingegebenen Suchworte enthalten, sogenannte result snippets, siehe "Technische Realisierung".

Optionale Funktionalität:

• Eine Kommandozeilenoption mit der man den Namen von (einem oder mehreren) Verzeichnissen übergeben kann, die dann rekursiv durchsucht werden.
• Eine Indexdatei, statt im einfachsten Fall eine pro indiziertem Suchwort.
• Markierung der Suchworte in den result snippets.
• Höhere Gewichtung von Worten, die im Dateinamen bzw. im Pfad zu der Datei vorkommen.
• Was immer Ihnen einfällt.

Technische Realisierung:

• Für die invertierten Listen sollte jede Datei eine eindeutige ID haben; die invertierte Liste für ein Wort ist dann die Liste der IDs aller Dateien, die dieses Wort enthalten. Man braucht dann eine Variable (bei fortlaufenden IDs reicht ein std::vector), die die Zuordnung von IDs zu Dateinamen speichert.

• Am einfachsten ist es, wenn Sie jede invertierte Liste in einer eigenen Datei speichern, deren Name von dem Wort dieser invertierten Liste ableitet ist. Schöner wäre es, wenn Sie alle invertierten Listen in eine Datei schreiben. Dann brauchen Sie aber eine Art Inhaltsverzeichnis (in einer separaten Datei oder ebenfalls in der einen Indexdatei), damit Sie die invertierten Listen, die für die Suchanfragen benötigt werden, lesen können ohne die ganze Indexdatei zu lesen.
• Zur Beantwortung einer Suchanfrage einfach die Schnittmenge der invertierten Liste der in der Anfrage enthaltenen Suchworte berechnen. Die Schnittmenge enthält dann die IDs von genau den Dateien, die alle Suchworte enthalten. Zur effizienten Berechnung der Schnittmenge sollten die invertierten Listen (bei der Vorberechnung schon) sortiert werden, siehe Übungsblatt 9.

• Die result snippets kann man selber implementieren (die jeweilige Datei öffnen und nach Vorkommen der Suchworte suchen), oder aus dem Programm heraus ein externes Programm wie grep aufrufen (am einfachsten über system, siehe man 3 system, oder, wenn man die Ausgabe des externen Programms vor der Ausgabe auf den Bildschirm intern nachbearbeiten möchte, über exec, siehe man 3 exec; letzteres hat auch den Vorteil, das man einen unit test dafür schreiben kann).

Projekt 2 (Pong)

Kurzbeschreibung: Realisierung einer einfach Version des Uralt-Video-Spiels Pong mit ASCII-Zeichen auf der Konsole. Siehe zum Beispiel http://de.wikipedia.org/wiki/Pong oder http://www.youtube.com/watch?v=BkzK9q_FcH0 .

Geforderte Funktionalität:

• Ein ausführbares Programm PongMain, mit dem die Grundversion des Spieles gespielt werden kann (über insgesamt vier Tasten, zwei für das Auf und Ab des linken Schlägers, zwei für das Auf und Ab des rechten Schlägers)

• Mitzählen und Anzeige des Spielstandes, wer zuerst 3 Punkt hat, hat gewonnen
• Größe des Spielfeldes (Anzahl Reihen und Spalten) über Kommandozeilenparameter einstellbar. Ebenso die Länge des Schläger und die Geschwindigkeit des Spieles. Vernünftige Defaultwerte dafür.

Optionale Funktionalität:

• "Anschneiden" des Balles (falls der Schläger beim Ausprall des Balles gerade in Bewegung ist / war).
• Verändern der Schlägergröße, Spielgeschwindigkeit, etc. während des Spiels.
• Möglichkeit, dass der Computer einen der Spieler steuert, mit einer einstellbaren "Geschicklichkeit"
• Mehrere Spiele, Merken des Highscores
• Was immer Ihnen einfällt.

Technische Realisierung:

• Positionierung auf dem Bildschirm mittels ANSI espace codes: http://en.wikipedia.org/wiki/ANSI_escape_code . Siehe dazu auch das einfach Beispiel aus der Vorlesung. Damit kann auch der Bildschirm gelöscht werden, in verschiedenen Farben oder fett gedruckt werden, etc. Sie sollten immer nur soviel malen wie nötig, also nicht jedes Mal das ganze Spielfeld neu malen, wenn sich nur wenige Zeichen darauf verändert haben.

• Alternativ können Sie auch die "Curses" Bibliothek benutzen: http://heather.cs.ucdavis.edu/~matloff/UnixAndC/CLanguage/Curses.pdf , die ist portabler.

Projekt 3 (selbstgewählt)

Bei dieser Alternative, ist die Spezifikation des Projektes Ihnen überlassen. Einzige Bedingung ist, dass es in Umfang und Komplexität den ersten beiden Projekten ähnlich ist. Insbesondere sollte es vom Schwierigkeitsgrad nicht zu weit darüber hinaus gehen, Ihr Tutor muss es schließlich verstehen und korrigieren können.

Projekt 3 ist etwas für Teilnehmer/innen, die sich in der Sprache C++ schon sehr sicher fühlen und denen die bisherigen Übungsblätter leicht gefallen sind.