Ring der Macht

Aufgabe

Sauron hat in seinem Heer von Untergebenen nur eine begrenzte Menge an Platz. Als Ringliebhaber möchte er diese Untergebenen in einem sogenannten Ringbuffer organisieren.

Untergebene werden in der Reihenfolge des Eintritts in sein Heer gespeichert. Möchte Sauron mal einen Untergebenen loswerden, entfernt er immer den “dienstältesten” (am frühesten in das Heer eingetretenen) Untergebenen zuerst. Möchte Sauron einen neuen Untergebenen in sein Heer aufnehmen, hat aber keinen Platz mehr, wird der älteste untergebene automatisch durch den neuen Untergebenen ersetzt. Sauron möchte außerdem zu jedem Zeitpunkt erfahren können, wie viele Untergebene teil seines Heers sind, und wieviel Platz in seinem Heer ist.

Anforderungen in formal
  • RingBuffer(capacity): Erzeugt einen neuen Ringbuffer mit Kapazität capacity.
  • RingBuffer.push(e): Fügt das Element e als neuestes Element in den Ringbuffer ein. Ist der Ringbuffer voll, wird das älteste Element verdrängt (und das bis dahin zweitälteste Element wird somit zum ältesten Element).
  • RingBuffer.pop(): Gibt das älteste (am frühesten Eingefügte) Element des Ringbuffers aus (welches sich noch im Speicher befindet) und entfernt es aus dem Ringbuffer (aber nicht gezwungenermaßen aus dem unterliegenden Speicher). Ist der Ringbuffer leer, wird None zurückgegeben.
  • RingBuffer.peek(): Gibt das älteste Element des Ringbuffers aus, ohne es zu entfernen. Ist der Ringbuffer leer, wird None zurückgegeben.
  • len(RingBuffer): Gibt die Anzahl an Elementen, welche sich aktuell im Ringbuffer befinden, aus. Siehe auch die Dokumentation zu “special method names” __len__.
  • RingBuffer.capacity: Gibt zurück wie viele Elemente in den Ringbuffer passen.

Du kannst das folgende Template benutzen um deinen Ringbuffer zu Implementieren. Die Tests können dabei Helfen zu überprüfen, ob deine Implementierung korrekt ist. Sie werden mit Ausführung der Datei ausgeführt.

from typing import Any, Optional


class RingBuffer:
    def __init__(self, capacity: int):
      pass

    def __len__(self) -> int:
        raise NotImplementedError

    def push(self, element: Any):
        raise NotImplementedError

    def pop(self) -> Optional[Any]:
        raise NotImplementedError

    def peek(self) -> Optional[Any]:
        raise NotImplementedError


def test():
    # Test normal operation without overwrites
    buffer = RingBuffer(3)
    assert buffer.capacity == 3
    assert len(buffer) == 0
    buffer.push(1)
    buffer.push(3)
    buffer.push(4)
    assert buffer.peek() == 1
    assert len(buffer) == 3
    assert buffer.pop() == 1
    assert buffer.pop() == 3
    assert buffer.pop() == 4
    assert buffer.pop() is None

    # Test operation with overwrites
    buffer.push(10)
    buffer.push(20)
    buffer.push(30)
    buffer.push(40)
    buffer.push(50)
    assert buffer.pop() == 30
    assert buffer.pop() == 40
    assert buffer.pop() == 50
    assert buffer.pop() is None


if __name__ == "__main__":
    test()

Hinweise

Wo sollen Daten gespeichert werden

Zur Speicherung der Daten eignet sich zum beispiel eine list. Diese sollte beim initialisieren der Klasse die feste Größe capacity bekommen. Das lässt sich zum beispiel durch self.buffer = [None for _ in range(capacity)] in der __init__ Methode realisieren.

Woher weiß ich welches das neueste / älteste Element ist?

Hierfür speichert man sich am besten zwei Attribute self.newest und self.oldest, welche den Index des aktuell neuesten und ältesten Elements beinhalten. Ist der unterliegende buffer leer, kann es sinnvoll sein in self.newest den Index zu speichern vor dem man als nächstes einfügen möchte, und in self.oldest genau den Index zu speichern, in den man als nächstes Einfügt. Das ist aber kein muss, sondern nur optimierung. Bei einem push oder pop müssen diese Indizes gegebenenfalls verschoben werden.

Wie verfolge ich das neueste / älteste Element über die ‘Ränder’ meines Speichers hinweg?

Wenn der unterliegende Speicher eine Länge von 3 hat (also der größte Index 2 ist) und unser neuestes Element bereits am Index 2 liegt, wäre der nächste Index zum Einfügen der Index 0 (also quasi am “rechten” Rand / Ende des Speichers raus, und am linken Rand / Anfang wieder angefangen). Um bei einer Inkrementierung des Indexes auch auf diesen Wert zu kommen, kann der Modulo operator % zusammen mit der Kapazität des Ringbuffers genutzt werden.