27. Spájané zoznamy


Predchádzajúca prednáška sa venovala spájanej dátovej štruktúre, v ktorej mal každý prvok svojho nasledovníka (okrem posledného). Takejto štruktúre sme hovorili spájaný zoznam (linked list).

Zhrňme z minulej prednášky najdôležitejšie funkcie, ktoré pracujú so spájanými zoznamami. Používali sme túto deklaráciu triedy Vrchol:

class Vrchol:
    def __init__(self, data, next=None):
        self.data, self.next = data, next

Pre spájané zoznamy, ktoré sú poskladané z takýchto vrcholov Vrchol sme definovali niekoľko funkcií:

def vypis(zoz):                         # vypíše prvky zoznamu
    while zoz is not None:
        print(repr(zoz.data), end=' -> ')
        zoz = zoz.next
    print(None)

def vyrob(postupnost):                  # z prvkov danej postupnosti vytvorí nový zoznam
    zoz = None
    for hodnota in reversed(postupnost):
        zoz = Vrchol(hodnota, zoz)
    return zoz

def pocet(zoz):                         # zistí počet prvkov zoznamu
    vysl = 0
    while zoz is not None:
        vysl += 1
        zoz = zoz.next
    return vysl

def zisti(zoz, hodnota):                # zistí, či je prvok v zozname
    while zoz is not None:
        if zoz.data == hodnota:
            return True
        zoz = zoz.next
    return False

def pridaj_zaciatok(zoz, hodnota):      # pridaj prvok na začiatok zoznamu
    return Vrchol(hodnota, zoz)

def pridaj_koniec(zoz, hodnota):        # pridaj prvok na koniec zoznamu
    if zoz is None:
        return Vrchol(hodnota)
    posledny = zoz
    while posledny.next is not None:
        posledny = posledny.next
    posledny.next = Vrchol(hodnota)
    return zoz

Tieto funkcie môžeme ešte otestovať:

>>> zoz = None
>>> zoz = pridaj_zaciatok(zoz, 7)
>>> zoz = pridaj_koniec(zoz, 'abc')
>>> zoz = pridaj_zaciatok(zoz, (1, 2))
>>> vypis(zoz)
(1, 2) -> 7 -> 'abc' -> None
>>> pocet(zoz)
3
>>> zisti(zoz, 'abc')
True

V podobnom duchu boli aj ďalšie funkcie, ktoré ste programovali na cvičeniach.

Keď sa vytvára nejaká nová dátová štruktúra, veľmi často sa všetky funkcie zapuzdria do jedného celku - do jednej triedy, pričom sa skryjú realizačné detaily a aj nejaké pomocné funkcie a atribúty (hovoríme tomu enkapsulácia).


Trieda spájaný zoznam

Navrhneme novú triedu SpajanyZoznam (v anglickej verzii by sme ju nazvali LinkedList), pre ktorú zadefinujeme najdôležitejšie metódy. Všimnite si, že definíciu pomocnej triedy Vrchol sme vnorili do triedy SpajanyZoznam. Tým, že sme definíciu tejto triedy vnorili, oznamujeme, že patrí do triedy SpajanyZoznam a zrejme sa bude využívať v metódach tejto triedy. Všetky funkcie, ktoré pracovali so spájaným zoznamom, mali prvý parameter referenciu na prvý prvok zoznamu. Teraz tento parameter zastúpi atribút self.zac, teda začiatok zoznamu. Už vieme, že si bude treba dať pozor, aby sme túto referenciu nepokazili:

class SpajanyZoznam:

    #----- vnorená trieda -----
    class Vrchol:
        def __init__(self, data, next=None):
            self.data, self.next = data, next

    #----- koniec vnorenej definície triedy -----

    def __init__(self):
        self.zac = None                   # začiatok zoznamu

    def vypis(self):                      # vypíše prvky zoznamu
        zoz = self.zac
        while zoz is not None:
            print(repr(zoz.data), end=' -> ')
            zoz = zoz.next
        print(None)

    def vyrob(self, postupnost):          # z prvkov danej postupnosti vytvorí nový zoznam
        self.zac = None
        for hodnota in reversed(postupnost):
            self.zac = self.Vrchol(hodnota, self.zac)

    def pocet(self):                      # zistí počet prvkov zoznamu
        vysl = 0
        zoz = self.zac
        while zoz is not None:
            vysl += 1
            zoz = zoz.next
        return vysl

    def zisti(self, hodnota):             # zistí, či je prvok v zozname
        zoz = self.zac
        while zoz is not None:
            if zoz.data == hodnota:
                return True
            zoz = zoz.next
        return False

    def pridaj_zaciatok(self, hodnota):   # pridaj prvok na začiatok zoznamu
        self.zac = self.Vrchol(hodnota, self.zac)

    def pridaj_koniec(self, hodnota):     # pridaj prvok na koniec zoznamu
        if self.zac is None:
            self.zac = self.Vrchol(hodnota)
        else:
            posledny = self.zac
            while posledny.next is not None:
                posledny = posledny.next
            posledny.next = self.Vrchol(hodnota)

Skôr, ako to budeme testovať, všimnite si, že metódy pridaj_zaciatok(), pridaj_koniec(), ale aj vyrob už nie sú také funkcie, ktoré vždy vracali novú referenciu na začiatok zoznamu - teraz túto referenciu už nepotrebujeme ako výsledok funkcie. Samotné metódy zmenia referenciu na začiatok v atribúte self.zac. Tiež vidíte použitie vnorenej triedy Vrchol: aby sme mohli vytvoriť nový vrchol, musíme zapísať self.Vrchol(hodnota). Zapíšme nejaký jednoduchý test, aby sme si zvykli na prácu s touto dátovou štruktúrou:

>>> zoz = SpajanyZoznam()
>>> zoz.pridaj_zaciatok(7)
>>> zoz.pridaj_koniec('abc')
>>> zoz.pridaj_zaciatok((1, 2))
>>> zoz.vypis()
(1, 2) -> 7 -> 'abc' -> None
>>> zoz.pocet()
3
>>> zoz.zisti('abc')
True

Funguje to podľa očakávania dobre. Len by to mohlo byť viac pythonovské (pythonic):

  • namiesto metódy vyrob(), ktorá zruší momentálny obsah zoznamu a vyrobí nový (inicializuje) z nejakej postupnosti hodnôt, presunieme túto inicializáciu do __init__, teraz bude fungovať zoz = SpajanyZoznam(post)

  • namiesto metódy vypis() by mohlo byť radšej __repr__() alebo __str__() a teda by mohlo fungovať, napríklad print(zoz)

  • namiesto pocet() by mohlo byť radšej __len__() a teda by vďaka tomu fungovalo nielen zoz.__len__() ale aj len(zoz)

  • namiesto pridaj_koniec() by mohlo byť radšej append(), aby sa to podobalo pythonovskému pridávaniu na koniec pythonovského zoznamu

  • namiesto zisti() by mohlo byť radšej __contains__() a teda by fungovalo hodnota in zoz

Budeme sa snažiť aj ďalšie metódy zapisovať tak, aby sa so spájaným zoznamom pracovalo podobne ako s inými dátovými typmi. Prepíšme triedu SpajanyZoznam:

class SpajanyZoznam:
    class Vrchol:
        def __init__(self, data, next=None):
            self.data, self.next = data, next

    def __init__(self, postupnost=None):
        self.zac = None                   # začiatok zoznamu
        if postupnost is not None:
            for hodnota in reversed(postupnost):
                self.insert0(hodnota)

    def __repr__(self):
        vysl, zoz = [], self.zac
        while zoz is not None:
            vysl.append(repr(zoz.data))
            zoz = zoz.next
        vysl.append('None')
        return ' -> '.join(vysl)

    def __len__(self):
        vysl, zoz = 0, self.zac
        while zoz is not None:
            vysl += 1
            zoz = zoz.next
        return vysl

    def __contains__(self, hodnota):
        zoz = self.zac
        while zoz is not None:
            if zoz.data == hodnota:
                return True
            zoz = zoz.next
        return False

    def insert0(self, hodnota):
        self.zac = self.Vrchol(hodnota, self.zac)

    def append(self, hodnota):
        if self.zac is None:
            self.zac = self.Vrchol(hodnota)
        else:
            posledny = self.zac
            while posledny.next is not None:
                posledny = posledny.next
            posledny.next = self.Vrchol(hodnota)

Pristavme sa na dvoch posledných metódach:

  • metóda insert0(), ktorá pridáva nový prvok na začiatok zoznamu (podobná list.insert(0, hodnota)), je veľmi rýchla, lebo obsahuje len jedno priradenie a bude trvať rovnaký čas bez ohľadu na to, či je doterajší zoznam krátky alebo obsahuje už veľa prvkov

  • metóda append(), ktorá pridáva nový prvok na koniec zoznamu, je v niektorých prípadoch veľmi pomalá: ak už doterajší zoznam obsahuje obrovské množstvo prvkov (napríklad 100000), pridať nový prvok na koniec bude trvať už nejaký nezanedbateľný čas (napríklad, 0.01 sekundy); keď takéto pridávanie urobíme 1000 krát, už to môžu byť desiatky sekúnd.

Všimnite si, že v tejto metóde môže takto výrazne zdržovať len vnútorný while-cyklus. Ak by sme sa ho dokázali zbaviť, aj metóda append() by mohla byť dostatočne rýchla. Tento cyklus nerobí nič iné, len hľadá momentálne posledný vrchol v zozname. Ak by sme ale okrem referencie na začiatok zoznamu zabezpečili pamätanie aj referencie na posledný vrchol, všetko by sa vyriešilo.

Do triedy SpajanyZoznam k atribútu zac pridáme ďalší: kon, v ktorom si budeme ukladať referenciu na posledný vrchol zoznamu. Počiatočnú hodnotu (None) mu priradíme v inicializácii __init__(). Ďalej vo všetkých metódach, ktoré nejako modifikujú samotný spájaný zoznam, zabezpečíme, aby sa správne nastavila aj táto koncová referencia. V našom programe sa okrem inicializácie a metódy append() musí opraviť aj metóda insert0():

class SpajanyZoznam:
    class Vrchol:
        def __init__(self, data, next=None):
            self.data, self.next = data, next

    def __init__(self, postupnost=None):
        self.zac = self.kon = None                   # začiatok a koniec zoznamu
        if postupnost is not None:
            for hodnota in postupnost:
                self.append(hodnota)

    ...

    def insert0(self, hodnota):
        self.zac = self.Vrchol(hodnota, self.zac)
        if self.kon is None:
            self.kon = self.zac

    def append(self, hodnota):
        if self.zac is None:
            self.kon = self.zac = self.Vrchol(hodnota)
        else:
            self.kon.next = self.Vrchol(hodnota)
            self.kon = self.kon.next

V tejto novej verzii v metóde append() už nie je žiaden cyklus a obsahuje len jeden test a niekoľko priradení. Môžete otestovať rýchlosť tejto metódy napríklad takto:

>>> zoz = SpajanyZoznam(range(100000))
>>> for i in range(100000):
        zoz.append(i)
>>> len(zoz)
200000

Doplňme do tejto triedy SpajanyZoznam aj metódy pop0() a pop(), ktoré vyhodia 1. prvok, resp. posledný prvok zoznamu a vrátia príslušnú hodnotu vyhadzovaného prvku (podobne, ako to robia metódy list.pop(0) a list.pop()):

class SpajanyZoznam:
    ...

    def pop0(self):
        if self.zac is None:
            raise EmptyError
        vysl = self.zac.data
        self.zac = self.zac.next
        if self.zac is None:
            self.kon = None
        return vysl                   # hodnota vyhodeného prvku

    def pop(self):
        if self.zac is None:
            raise EmptyError
        if self.zac.next is None:     # jednoprvkový zoznam
            vysl = self.zac.data
            self.zac = self.kon = None
            return vysl
        self.kon = self.zac
        while self.kon.next.next is not None:
            self.kon = self.kon.next
        vysl = self.kon.next.data
        self.kon.next = None
        return vysl                   # hodnota vyhodeného prvku

Vidíme, že vyhodenie prvého prvku zoznamu (metóda pop0()) je veľmi jednoduché a rýchle (nezávisí od momentálnej veľkosti zoznamu). Metóda na vyhodenie posledného prvku je už náročnejšia a obsahuje while-cyklus na nájdenie predposledného vrcholu zoznamu. Preto je táto metóda veľmi pomalá a už nám tu nepomôže ani „finta“ s udržiavaním si referencie na posledný vrchol.

Otestujme:

>>> zoz = SpajanyZoznam(range(10000))
>>> for i in range(10000):
        x = zoz.pop()

Zhrňme základné metódy, ktoré pridávajú, resp. odoberajú prvok zo začiatku alebo konca zoznamu:

  • metóda insert0() vloží prvok na začiatok zoznamu - je veľmi rýchla

  • metóda append() vloží prvok na koniec zoznamu - je veľmi rýchla len vtedy, ak využíva pomocnú referenciu na koniec zoznamu (inak je pomalá)

  • metóda pop0() vyberie prvok zo začiatku zoznamu - je veľmi rýchla

  • metóda pop() vyberie prvok z konca zoznamu - je veľmi pomalá a pre jednosmerný spájaný zoznam neexistuje spôsob, ako to urýchliť

Keď sa budete niekedy rozhodovať, ako budete pracovať s nejakým spájaným zoznamom, spomeňte si na toto porovnanie rýchlostí a ak sa bude dať, snažte sa vyhnúť odoberaniu prvku z konca zoznamu.


Mapovacie metódy

Zapíšme metódu, ktorá postupne prejde všetky vrcholy spájaného zoznamu a každému zmení hodnotu podľa zadanej funkcie:

class SpajanyZoznam:
    ...

    def mapuj(self, funkcia):
        zoz = self.zac
        while zoz is not None:
            zoz.data = funkcia(zoz.data)
            zoz = zoz.next

Otestujeme:

>>> def fun(x): return x * x
>>> zoz = SpajanyZoznam(range(5))
>>> zoz
0 -> 1 -> 2 -> 3 -> 4 -> None
>>> zoz.mapuj(fun)
>>> zoz
0 -> 1 -> 4 -> 9 -> 16 -> None

Funguje to aj s lambda konštrukciou, napríklad:

>>> zoz = SpajanyZoznam('Python')
>>> zoz
'P' -> 'y' -> 't' -> 'h' -> 'o' -> 'n' -> None
>>> zoz.mapuj(lambda x: x.upper())
>>> zoz
'P' -> 'Y' -> 'T' -> 'H' -> 'O' -> 'N' -> None

Parametrom funkcie môže byť aj nejaká podmienka, napríklad takáto verzia mapuj:

class SpajanyZoznam:
    ...

    def mapuj(self, podmienka, funkcia):
        zoz = self.zac
        while zoz is not None:
            if podmienka(zoz.data):
                zoz.data = funkcia(zoz.data)
            zoz = zoz.next

Napríklad:

>>> zoz = SpajanyZoznam(range(1, 20, 2))
>>> zoz
1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15 -> 17 -> 19 -> None
>>> zoz.mapuj(lambda x: x%3, lambda x: x*x)
>>> zoz
1 -> 3 -> 25 -> 49 -> 9 -> 121 -> 169 -> 15 -> 289 -> 361 -> None

Ďalšia metóda vytvorí obyčajný pythonovský zoznam prvkov (typu list) z prvkov spájaného zoznamu, ktoré spĺňajú nejakú podmienku:

class SpajanyZoznam:
    ...

    def tolist(self, podmienka=None):
        lst = []
        zoz = self.zac
        while zoz is not None:
            if podmienka is None or podmienka(zoz.data):
                lst.append(zoz.data)
            zoz = zoz.next
        return lst

Napríklad:

>>> zoz = SpajanyZoznam((1, 2, 'A', 4, 'B'))
>>> zoz.tolist(lambda x: isinstance(x, int))
[1, 2, 4]
>>> zoz.tolist()
[1, 2, 'A', 4, 'B']
>>> def podm(x): return type(x) == str
>>> zoz.tolist(podm)
['A', 'B']

Spájaný zoznam a for-cyklus

Už sme si zvykli, že prvky spájaného zoznamu môžeme prechádzať while cyklom, napríklad:

class SpajanyZoznam:
    ...

    def sucet(self):
        zoz = self.zac
        vysl = 0
        while zoz is not None:
            vysl += zoz.data
            zoz = zoz.next
        return vysl

Žiaľ, prechádzať prvky spájaného zoznamu tak, ako to vie Python so zoznamom, n-ticou, množinou, atď. sa zatiaľ nedá. Ak by sme vyskúšali:

>>> zoz = SpajanyZoznam((2, 3, 5, 7, 11))
>>> for prvok in zoz:
        print(prvok)
...
TypeError: 'SpajanyZoznam' object is not iterable

alebo

>>> for prvok in zoz.zac:
        print(prvok.data)
...
TypeError: 'Vrchol' object is not iterable

Python vyhlási chybu TypeError, lebo nevie, akým spôsobom by mal postupne prechádzať (iterovať) všetky prvky spájaného zoznamu. Uvidíme neskôr, že Python to dokáže, ale bude potrebovať, aby sme mu niečo o našej štruktúre prezradili.


Rekurzia v metóde

Na predchádzajúcich cvičeniach ste zostavovali rekurzívnu funkciu (napríklad 15. úloha), ktorá zisťovala počet prvkov spájaného zoznamu. Vaše riešenie mohlo vyzerať, napríklad takto:

def pocet(zoz):
    if zoz is None:
        return 0
    return pocet(zoz.next) + 1

Ak by sme túto rekurziu chceli zapísať ako metódu triedy SpajanyZoznam (problémom je parameter zoz), môžeme to urobiť niekoľkými spôsobmi. Najlepšie to ale urobíme ako vnorenú rekurzívnu funkciu do príslušnej metódy:

class SpajanyZoznam:
    ...

    def pocet(self):
        #----- vnorená funkcia
        def pocet_rek(zoz):
            if zoz is None:
                return 0
            return pocet_rek(zoz.next) + 1
        #----- koniec vnorenej funkcie

        return pocet_rek(self.zac)

Hoci táto rekurzívna funkcia nemá žiaden praktický význam (funguje len pre zoznamy kratšie ako 1000), ideu vnorených a hlavne rekurzívnych funkcií budeme neskôr používať veľmi často.


Realizácia zásobníka a radu

V prednáške 25. Zásobníky a rady sme sa zoznámili s dátovou štruktúrou zásobník. Využili sme ho hlavne pri spracovávaní aritmetických výrazov, ale aj ako mechanizmus, pomocou ktorého vieme nahradiť rekurziu zásobníkom.

Zásobník sme vtedy realizovali pomocou pythonovského zoznamu (typ list):

  • operácia push() pridávala nový prvok na koniec zoznamu pomocou metódy list.append()

  • operácia pop() odoberala zo zoznamu posledný prvok pomocou metódy list.pop()

  • operácia is_empty() zisťovala, či je zoznam prázdny

Zásobník sa dá veľmi elegantne realizovať aj pomocou spájaného zoznamu:

  • v tomto prípade bude vrch zásobníka na začiatku zoznamu

  • operácia push() pridá nový prvok na začiatok spájaného zoznamu

  • operácia pop() odoberie prvok zo začiatku spájaného zoznamu

  • operácia is_empty() zistí, či je spájaný zoznam prázdny

  • operácia top() vráti hodnotu prvého prvku spájaného zoznamu

  • opäť použijeme novú výnimku EmptyError

Zapíšme kompletný kód:

class EmptyError(Exception): pass

class Stack:
    class _Vrchol:                          # vnorená trieda
        def __init__(self, data, next):
            self.data, self.next = data, next

    def __init__(self):
        self._zac = None

    def push(self, hodnota):                # pridá na začiatok zoznamu
        self._zac = self._Vrchol(hodnota, self._zac)

    def pop(self):                          # odoberie zo začiatku zoznamu
        if self.is_empty():
            raise EmptyError
        vysl = self._zac.data
        self._zac = self._zac.next
        return vysl

    def top(self):                          # vráti hodnotu prvého prvku
        if self.is_empty():
            raise EmptyError
        return self._zac.data

    def is_empty(self):
        return self._zac is None

Vidíte, že táto trieda Stack je veľmi zjednodušená verzia triedy SpajanyZoznam. Mohli by sme ju použiť všade tam, kde sme doteraz pracovali so zásobníkom, ktorý bol realizovaný pomocou pythonovského zoznamu list.

Zamyslite sa nad tým, ako by fungoval zásobník, ktorého vrch by bol na konci spájaného zoznamu (pridávame aj odoberáme prvky z konca spájaného zoznamu). Bol by rovnako rýchly ako táto verzia s vrchom zásobníka na začiatku spájaného zoznamu?


Realizácia radu (frontu)

V prednáške 25. Úvodná prednáška v letnom semestri sme sa zoznámili aj s ďalšou dátovou štruktúrou rad. Aj rad sme realizovali pomocou obyčajného zoznamu (typ list):

  • operácia enqueue() pridávala nový prvok na koniec zoznamu pomocou metódy list.append()

  • operácia dequeue() odoberala zo zoznamu prvý prvok pomocou metódy list.pop(0)

  • operácia is_empty() zisťovala, či je zoznam prázdny

Pri realizovaní radu pomocou spájaného zoznamu sa musíme zamyslieť nad tým, či:

  1. bude začiatok radu na začiatku spájaného zoznamu

    • pridávať budeme na koniec zoznamu a odoberať budeme zo začiatku

  2. bude začiatok radu na konci spájaného zoznamu

    • pridávať budeme na začiatok zoznamu a odoberať budeme z konca

My už vieme, že pridávanie, resp. odoberanie zo začiatku spájaného zoznamu sú rýchle operácie. Ale pridávanie na koniec je rýchle len s pomocnou referencie na koniec zoznamu a odoberanie z konca je vždy pomalé. Preto si zvolíme variant (a), pri ktorom vieme rýchlo pridávať na koniec a rýchlo odoberať zo začiatku zoznamu:

  • operácia enqueue() pridá nový prvok na koniec spájaného zoznamu (použije referenciu na posledný vrchol zoznamu)

  • operácia dequeue() odoberie prvok zo začiatku spájaného zoznamu

  • operácia is_empty() zistí, či je spájaný zoznam prázdny

  • operácia front() vráti hodnotu prvého prvku spájaného zoznamu

  • opäť použijeme výnimku EmptyError

Zapíšme kompletný kód:

class EmptyError(Exception): pass

class Queue:
    class _Vrchol:                          # vnorená trieda
        def __init__(self, data):
            self.data, self.next = data, None

    def __init__(self):
        self._zac = self._kon = None

    def enqueue(self, hodnota):             # pridá na koniec zoznamu
        novy = self._Vrchol(hodnota)
        if self._zac is None:
            self._zac = self._kon = novy
        else:
            self._kon.next = novy
            self._kon = novy

    def dequeue(self):                      # odoberie zo začiatku zoznamu
        if self.is_empty():
            raise EmptyError
        vysl = self._zac.data
        self._zac = self._zac.next
        if self._zac is None:
            self._kon = None
        return vysl

    def front(self):                        # vráti hodnotu prvého prvku
        if self.is_empty():
            raise EmptyError
        return self._zac.data

    def is_empty(self):
        return self._zac is None

Vidíte, že aj trieda Queue je veľmi zjednodušená verzia triedy SpajanyZoznam.


Operátory indexovania

Pre pythonovský obyčajný zoznam (typ list) sú veľmi typické operácie indexovania, t.j. keď vieme zistiť hodnotu nejakého prvku podľa jeho indexu (pozície v zozname), resp. keď vieme zmeniť hodnotu prvku zadaného indexom. Zapíšme tieto dve operácie ako metódy triedy SpajanyZoznam:

class SpajanyZoznam:
    ...

    def _ity(self, index):                      # zistí referenciu i-teho prvku
        if index < 0:
            raise IndexError
        zoz = self.zac
        while zoz is not None and index > 0:
            zoz = zoz.next
            index -= 1
        if zoz is None:
            raise IndexError
        return zoz

    def daj_ity(self, index):                   # vráti hodnotu i-teho prvku
        return self._ity(index).data

    def zmen_ity(self, index, hodnota):         # zmení hodnotu i-teho prvku
        self._ity(index).data = hodnota

Vytvorili sme pomocnú (súkromnú) metódu _ity(), ktorá vráti referenciu na príslušný vrchol (alebo spadne na chybe IndexError). Opäť tu prvý znak mena _ označuje, že je to pomocná metóda, ktorú by sme radšej nemali používať mimo metód samotnej triedy.

Budeme to testovať takto - najprv si ukážme zápis pomocou obyčajného zoznamu list:

>>> lst = list(range(1, 20, 2))
>>> for i in range(len(lst)):
        lst[i] = lst[i] ** 2
>>> lst
[1, 9, 25, 49, 81, 121, 169, 225, 289, 361]

a prepíšeme to pre spájaný zoznam:

>>> zoz = SpajanyZoznam(range(1, 20, 2))
>>> for i in range(len(zoz)):
        x = zoz.daj_ity(i)
        zoz.zmen_ity(i, x ** 2)     # zoz.zmen_ity(i, zoz.daj_ity(i) ** 2)
>>> zoz
1 -> 9 -> 25 -> 49 -> 81 -> 121 -> 169 -> 225 -> 289 -> 361 -> None

Vidíme, že v oboch prípadoch dostávame rovnakú postupnosť čísel, len zápis lst[i] = lst[i] ** 2 je výrazne lepšie čitateľný ako zoz.zmen_ity(i, zoz.daj_ity(i) ** 2).

Hodilo by sa nám, keby sme

  • namiesto volania zoz.daj_ity(i) mohli zapísať zoz[i] a Python by to pochopil ako vyhľadanie i-teho prvku zoznamu a vrátil by príslušnú hodnotu

  • namiesto volania zoz.zmen_ity(i, hodnota) mohli zapísať zoz[i] = hodnota a Python by to pochopil ako vyhľadanie i-teho prvku zoznamu a potom aj zmenu jeho hodnoty

Naozaj toto v Pythone funguje. Rovnako ako sme prekryli, teda preťažili (overload) operácie súčtu pomocou magickej metódy __add__(), ako sme preťažili operáciu in pomocou __contains__(), atď. môžeme preťažiť aj operácie indexovania. Funguje to takto:

  • keď v Pythone zapíšeme napríklad lst[i], toto sa Pythonom prepíše na magické volanie lst.__getitem__(i) a až táto magická metóda vykoná výber hodnoty

  • keď v Pythone zapíšeme napríklad lst[i] = hodnota, toto sa prepíše na magické volanie lst.__setitem__(i, hodnota) a až táto magická metóda vykoná zmenu hodnoty

  • keď v Pythone zapíšeme napríklad del lst[i], toto sa prepíše na magické volanie lst.__delitem__(i) a až táto magická metóda vykoná zrušenie hodnoty

Môžete to otestovať na pythonovskom zozname list:

>>> lst = list(range(1, 20, 2))
>>> for i in range(len(lst)):
        lst.__setitem__(i, lst.__getitem__(i) ** 2)

Tomuto v programovacích jazykoch hovoríme syntaktický cukor a slúži len na uľahčenie zápisu a čitateľnosť kódu. Už sme sa s tým stretli pri aritmetických operáciách, keď a+b často označuje a.__add__(b).

Takže prepíšme naše dve metódy daj_ity() a zmen_ity() na magické __getitem__() a __setitem__():

class SpajanyZoznam:
    ...

    def _ity(self, index):                        # pomocná metóda
        if index < 0:
            raise IndexError
        zoz = self.zac
        while zoz is not None and index > 0:
            zoz = zoz.next
            index -= 1
        if zoz is None:
            raise IndexError
        return zoz

    def __getitem__(self, index):                 # vráti hodnotu i-teho prvku
        return self._ity(index).data

    def __setitem__(self, index, hodnota):        # zmení hodnotu i-teho prvku
        self._ity(index).data = hodnota

Samozrejme, že môžeme programy písať aj bez „syntaktického cukru“:

>>> zoz.__setitem__(i, zoz.__getitem__(i) ** 2)

ale určite čitateľnejšie to bude „osladené“:

>>> zoz[i] = zoz[i] ** 2

Treba si ale pri tomto zápise uvedomiť, že pre dlhé spájané zoznamy a pre veľký index toto nevinne vyzerajúce priradenie dvakrát prelieza spájaný zoznam, aby našiel (a zmenil) i-ty prvok. Už by sme si mohli pamätať, že napríklad hľadanie posledného prvku v zozname môže naozaj trvať veľmi dlho.


Spájaný zoznam a for-cyklus

Python je pre programátora veľmi ústretový a snaží sa mu čo najviac vychádzať v ústrety. Keď zadefinujeme magickú metódu __getitem__(), Python z vlastnej iniciatívy „pochopí“, že takáto štruktúra by sa mohla dať prechádzať aj for-cyklom (iterovať). Veď zrejme mu stačí postupne indexovať s indexom 0, potom 1, potom 2, atď. až kým to nespadne na chybe a vtedy ukončí aj for-cyklus (bez chybovej správy). Otestujme:

>>> zoz = SpajanyZoznam(x**2 for x in range(1, 20, 2))
>>> for prvok in zoz:
        print(prvok, end=' -> ')
1 -> 9 -> 25 -> 49 -> 81 -> 121 -> 169 -> 225 -> 289 -> 361 ->

Teda to naozaj urobí presne to, čo sme očakávali. Ale pozor! Tento for-cyklus pre každý prvok zoznamu prelieza celý zoznam vždy od začiatku. Pre krátke zoznamy to asi vadiť nebude, ale pre dlhé to bude neprijateľne pomalé!

Na rovnakom princípe potom funguje aj rozbaľovací parameter, napríklad:

>>> print(*zoz)
1 9 25 49 81 121 169 225 289 361

A vy už teraz viete, že tento „syntaktický cukor“ za sebou skrýva veľmi neefektívny kód.


Dvojsmerný a cyklický spájaný zoznam

Zatiaľ sme sa zoznámili s tzv. jednosmerným spájaným zoznamom (Singly Linked List). Slovo „jednosmerný“ tu označuje, že v každom vrchole sa uchováva jedna referencia na nasledovný vrchol. Vďaka tejto vlastnosti, vždy keď potrebujeme zistiť predchodcu nejakého vrcholu (napríklad predchodcu posledného), musíme prejsť zoznam od začiatku až po hľadaný vrchol. O tomto už vieme, že je to drahá operácia.

V situáciách, keď budeme často potrebovať pre nejaké vrcholy zisťovať ich predchodcov, využijeme alternatívnu organizáciu spájaných zoznamov, tzv. dvojsmerné spájané zoznamy (Doubly Linked List). Každý vrchol v takomto zozname si okrem referencie na nasledovníka uchováva aj referenciu na svojho predchodcu. A zrejme prvý vrchol má svojho predchodcu None (tak ako posledný svojho nasledovníka). Dvojsmerný spájaný zoznam by sme si mohli zakresliť, napríklad takto:

sedemprvkový dvojsmerný spájaný zoznam

Zapíšme niekoľko metód:

class DvojsmernyZoznam:
    class Vrchol:
        def __init__(self, data, prev=None, next=None):
            self.data = data
            self.prev = prev
            self.next = next

    def __init__(self, postupnost):
        self.zac = self.kon = None
        for prvok in postupnost:
            self.append(prvok)

    def __repr__(self):
        vysl, zoz = [], self.zac
        while zoz is not None:
            vysl.append(repr(zoz.data))
            zoz = zoz.next
        vysl.append('None')
        return ' <-> '.join(vysl)

    def insert0(self, hodnota):
        self.zac = self.Vrchol(hodnota, None, self.zac)
        if self.kon is None:
            self.kon = self.zac
        else:
            self.zac.next.prev = self.zac

    def append(self, hodnota):
        if self.zac is None:
            self.insert0(hodnota)
        else:
            novy = self.Vrchol(hodnota, self.kon)
            self.kon.next = novy
            self.kon = novy

V rámci cvičení si vyskúšate naprogramovať aj ďalšie metódy.


Cyklický spájaný zoznam

Spomenieme ešte jeden variant spájaných zoznamov, ktorý sa reálne využíva v niektorých špeciálnych situáciách. Cyklický spájaný zoznam (Circular Linked List) môže byť jednosmerný aj dvojsmerný - my sa tu budeme zaoberať len jednosmerným zoznamom. Označuje, že posledný vrchol v zozname nemá svojho nasledovníka označeného ako None ale nejaký iný vrchol v zozname. Najčastejšie to býva práve prvý vrchol zoznamu. Pri cyklickom zozname si musíte dať veľmi dobrý pozor na to, aby ste nevytvorili nekonečný cyklus. Cyklický spájaný zoznam by sme si mohli zakresliť, napríklad takto:

sedemprvkový cyklický spájaný zoznam

Zapíšme na ukážku niekoľko metód:

class CyklickyZoznam:
    class Vrchol:
        def __init__(self, data, next=None):
            self.data, self.next = data, next

    def __init__(self, postupnost=None):
        self.zac = self.kon = None
        if postupnost is not None:
            for hodnota in postupnost:
                self.append(hodnota)

    def __repr__(self):
        vysl, zoz = [], self.zac
        while zoz is not None:
            vysl.append(repr(zoz.data))
            zoz = zoz.next
            if zoz == self.zac:
                break
        vysl.append('...')
        return ' -> '.join(vysl)

    def __len__(self):
        vysl, zoz = 0, self.zac
        while zoz is not None:
            vysl += 1
            zoz = zoz.next
            if zoz == self.zac:
                break
        return vysl

    def insert0(self, hodnota):
        if self.zac is None:
            self.zac = self.kon = self.Vrchol(hodnota)
            self.zac.next = self.zac
        else:
            self.kon.next = self.Vrchol(hodnota, self.zac)
            self.zac = self.kon.next

    def append(self, hodnota):
        if self.zac is None:
            self.insert0(hodnota)
        else:
            self.kon.next = self.Vrchol(hodnota, self.zac)
            self.kon = self.kon.next

Cvičenia

L.I.S.T.


  1. Poskladaj triedu SpajanyZoznam z prednášky s atribútmi zac a kon a s týmito metódami:

    • __repr__(), __len__(), __contains__(hodnota), insert0(hodnota), append(hodnota) (rýchla verzia), pop0() a pop()

    Potom ručne bez počítača zisti, čo sa vypíše:

    zoz = SpajanyZoznam('abcdefgh')
    while len(zoz) >= 3:
        print(zoz.pop(), zoz.pop0(), zoz.pop())
    zoz.append(zoz.pop0())
    zoz.insert0('x')
    print(zoz)
    

    Otestuj to na počítači.


  1. Metóda __len__ zisťuje veľkosť spájaného zoznamu pomocou while-cyklu (prechádza a počíta všetky prvky zoznamu). Prepíš túto metódu tak, aby neobsahovala cyklus: v triede zadefinuješ ešte jeden atribút (počítadlo) a potom každá metóda, ktorá zvyšuje počet prvkov zoznamu (napríklad append()) zvýši toto počítadlo o 1 a každá metóda, ktorá nejaké prvky zo zoznamu vyhadzuje (napríklad pop()), zníži toto počítadlo. Otestuj, napríklad:

    z = SpajanyZoznam(range(1000))
    for i in range(495):
        z.pop(); z.pop0()
    for i in range(5):
        z.append(i); z.insert0(i)
    print(len(z))
    

    Vedel by si ručne bez počítača zistiť, aké prvky obsahuje tento výsledný 20-prvkový zoznam?

    Ak by si nemal túto rýchlu verziu __len__, nasledovný test by bežal veľmi dlho, otestuj:

    zz = SpajanyZoznam()
    pocet = 0
    for i in range(20000):
        zz.insert0(i)
        pocet += len(zz)
    print(pocet)
    
    200010000
    

  1. Len pomocou metód triedy SpajanyZoznam vymeň prvý a posledný prvok zoznamu (použi niektoré z metód append, insert0, pop, pop0). Napríklad:

    >>> zoz = SpajanyZoznam('PYTHON')
    >>> zoz
    'P' -> 'Y' -> 'T' -> 'H' -> 'O' -> 'N' -> None
    >>> ...
    >>> ...
    >>> ...
    >>> zoz
    'N' -> 'Y' -> 'T' -> 'H' -> 'O' -> 'P' -> None
    

    Tvoje riešenie by malo fungovať pre ľubovoľný spájaný zoznam, ktorý má aspoň 2 prvky. Samozrejme, že nebudeš pracovať priamo s atribútom zac.


  1. Ručne bez počítača zisti, čo robí nasledovná metóda corobi():

    class SpajanyZoznam:
    
        ...
    
        def corobi(self):
            vysl = 0
            p = self.zac
            while p and p.next:
                vysl += p.data <= p.next.data
                p = p.next
            return vysl
    

    Napríklad, po otestovaní, by si mohol dostať takýto výstup:

    z = SpajanyZoznam('abbacccaab')
    print(z.corobi())
    z = SpajanyZoznam([abs(x%3-1) for x in range(100)])
    print(z.corobi())
    
    7
    66
    

  1. Do triedy SpajanyZoznam pridaj metódu clear(vzor=[0]), ktorá nahradí hodnoty v spájanom zozname prvkami postupnosti vzor. Tieto prvky berie z neprázdnej postupnosti postupne a keď sa minú, začne z nich brať od začiatku. Postupnosťou by mohol byť zoznam, n-tica, reťazec alebo range. Malo by fungovať, napríklad aj toto:

    >>> zoz = SpajanyZoznam('pocitac')
    >>> zoz.clear()
    >>> zoz
    0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> None
    >>> zoz.clear('ab')
    >>> zoz
    'a' -> 'b' -> 'a' -> 'b' -> 'a' -> 'b' -> 'a' -> None
    >>> zoz.clear((1, 'a', 3.14))
    >>> zoz
    1 -> 'a' -> 3.14 -> 1 -> 'a' -> 3.14 -> 1 -> None
    >>> zoz.clear(range(2, 6))
    >>> zoz
    2 -> 3 -> 4 -> 5 -> 2 -> 3 -> 4 -> None
    

  1. Do triedy SpajanyZoznam zapíš metódu count(podret). Táto metóda bude postupne prechádzať prvky spájaného zoznamu a v tých z nich, ktoré sú znakové reťazce, zistí počet výskytov reťazca podret. Výsledkom metódy bude celkový počet týchto výskytov. Napríklad:

    zoz = SpajanyZoznam('anicka dusicka kde si bola'.split())
    for r in 'a', 'ic', 'kde si':
        print(repr(r), zoz.count(r))
    print(SpajanyZoznam(('123', 232, '321', 433)).count('3'))
    
    'a' 4
    'ic' 2
    'kde si' 0
    2
    

  1. Do triedy SpajanyZoznam dopíš metódy, ktoré všetky vrátia (pomocou return) nový SpajanyZoznam a pôvodný zoznam nechajú bez zmeny.

    • metóda copy() vráti presnú kópiu pôvodného zoznamu

    • metóda reversed() vráti prevrátenú kópiu pôvodného zoznamu

    • metóda filter(podmienka) vráti kópiu pôvodného zoznamu, ale len tých prvkov, ktoré spĺňanú danú podmienku (parameter podmienka je logická funkcia)

    • metóda map(funkcia) vráti kópiu pôvodného zoznamu, ale na každý prvok aplikuje danú funkciu (parameter funkcia je nejaká funkcia, s jedným parametrom, napríklad str) - metóda sa podobá na funkciu mapuj z prednášky, ale teraz nemodifikuje samotný zoznam, ale vyrába kópiu

    • metóda enumerate() vráti kópiu pôvodného zoznamu, ale z každého prvku vyrobí dvojicu (tuple), v ktorej prvým prvkom bude poradové číslo (od 0) a druhým prvkom bude samotná hodnota vo vrchole, malo by to fungovať podobne ako štandardná funkcia enumerate()

    Napríklad:

    >>> z = SpajanyZoznam('Python')
    >>> z
    'P' -> 'y' -> 't' -> 'h' -> 'o' -> 'n' -> None
    >>> z1 = z.copy()
    >>> z1
    'P' -> 'y' -> 't' -> 'h' -> 'o' -> 'n' -> None
    >>> z2 = z.reversed()
    >>> z2
    'n' -> 'o' -> 'h' -> 't' -> 'y' -> 'P' -> None
    >>> z3 = z.filter(lambda x: x in 'aeiouy')
    >>> z3
    'y' -> 'o' -> None
    >>> z4 = z.map(lambda x: x.upper()+'!')
    >>> z4
    'P!' -> 'Y!' -> 'T!' -> 'H!' -> 'O!' -> 'N!' -> None
    >>> z5 = z.enumerate()
    >>> z5
    (0, 'P') -> (1, 'y') -> (2, 't') -> (3, 'h') -> (4, 'o') -> (5, 'n') -> None
    >>> z
    'P' -> 'y' -> 't' -> 'h' -> 'o' -> 'n' -> None
    

  1. Do triedy SpajanyZoznam zapíš metódu opakuje_sa(), ktorá v danom zozname nájde taký prvok, ktorý sa tam opakuje aspoň raz. Rieš to dvomi vnorenými while-cyklami: postupne pre každý prvok zoznamu prejdeš celý zvyšok až do konca a hľadáš prvok s rovnakou hodnotou. Ak taký prvok neexistuje, metóda vráti None. Napríklad:

    a = SpajanyZoznam((*range(100), *range(90, 200)))
    print(a.opakuje_sa())
    b = SpajanyZoznam('mama ma emu a ema Ma mamu'.split())
    print(b.opakuje_sa())
    
    90
    None
    

  1. Do triedy SpajanyZoznam dopíš magickú metódu __eq__(druhy), pomocou ktorej sa dajú porovnať dva zoznamy. Parametrom tejto metódy je druhý porovnávaný zoznam (objekt typu SpajanyZoznam). Python potom zo zápisu z1==z2 vyrobí volanie z1.__eq__(z2). Malo by teraz fungovať napríklad:

    >>> z1 = SpajanyZoznam(range(2, 7))
    >>> z2 = SpajanyZoznam((3, 4, 5, 6, 7))
    >>> z2.pop(); z2.insert0(2)
    7
    >>> z1 == z2
    True
    >>> z1.pop()
    6
    >>> z1 == z2
    False
    

  1. Do triedy SpajanyZoznam doplň metódy __getitem__() a __setitem__() z prednášky. Potom odmeraj čas pre obe verzie zvyšovania hodnôt prvkov zoznamu o 1:

    import time
    
    start = time.time()
    zoz1 = SpajanyZoznam(range(10000))
    z = zoz1.zac
    while z is not None:
        z.data += 1
        z = z.next
    print('čas1 =', ...)
    
    ...
    zoz2 = SpajanyZoznam(range(10000))
    for i in range(len(zoz2)):
        zoz2[i] = zoz2[i] + 1
    ...
    

    Prečo je taký veľký rozdiel v čase vytvárania týchto zoznamov?

    Tiež sa zamysli, prečo je rôzna rýchlosť pre vytvorenie týchto dvoch pythonovských zoznamov list1 a list2:

    list1 = list(SpajanyZoznam(range(10000)))
    print('list1 hotovo')
    zoz = SpajanyZoznam(range(10000))
    list2 = []
    z = zoz.zac
    while z:
        list2.append(z.data)
        z = z.next
    print('list2 hotovo')
    print(list1 == list2)
    

  1. Metóda __delitem__(index) by mala umožniť vyhodiť zo zoznamu prvok s príslušným indexom. Dopíš ju do triedy SpajanyZoznam. Teraz by malo fungovať, napríklad:

    >>> z = SpajanyZoznam(range(3, 22, 4))
    >>> z
    3 -> 7 -> 11 -> 15 -> 19 -> None
    >>> del z[2]
    >>> z
    3 -> 7 -> 15 -> 19 -> None
    

  1. Napíš metódu extend(), ktorá bude fungovať podobne ako metóda extend pre pythonovský zoznam (typu list): parametrom je postupnosť alebo iný spájaný zoznam. Metóda pridá prvky postupnosti, resp. iného spájaného zoznamu na koniec pôvodného zoznamu. Metóda nič nevracia. Napríklad:

    >>> z = SpajanyZoznam(range(3, 8))
    >>> z.extend('hello')
    >>> z.extend(SpajanyZoznam([1, 'a', 3.14]))
    >>> z
    3 -> 4 -> 5 -> 6 -> 7 -> 'h' -> 'e' -> 'l' -> 'l' -> 'o' -> 1 -> 'a' -> 3.14 -> None
    >>> z1 = SpajanyZoznam('x')
    >>> z2 = SpajanyZoznam(range(10000))
    >>> z1.extend(z2)
    >>> len(z1)
    10001
    

    Zamysli sa nad tým, ako spraviť, aby z1.extend(z2) nebolo tak veľmi pomalé.


  1. Do triedy SpajanyZoznam dopíš magickú metódu __add__(druhy), vďaka ktorej sa budú dať veľmi elegantne zreťazovať spájané zoznamy podobne ako sa zreťazujú znakové reťazce. Parametrom druhy tejto metódy je druhý spájaný zoznam (objekt typu SpajanyZoznam). Python potom zo zápisu z1+z2 vyrobí volanie z1.__add__(z2). Metóda teda vráti nový spájaný zoznam, ktorý vznikne spojením pôvodných dvoch zoznamov (tieto nepokazí). Otestuj:

    >>> z1 = SpajanyZoznam('abc')
    >>> z2 = SpajanyZoznam(range(2, 10, 2))
    >>> z3 = z1 + z2
    >>> z3
    'a' -> 'b' -> 'c' -> 2 -> 4 -> 6 -> 8 -> None
    >>> z1
    'a' -> 'b' -> 'c' -> None
    >>> z2
    2 -> 4 -> 6 -> 8 -> None
    >>> z2 + z1
    2 -> 4 -> 6 -> 8 -> 'a' -> 'b' -> 'c' -> None
    

  1. Zisti, čo sa stane so spájaným zoznamom:

    >>> z = SpajanyZoznam('abc')
    >>> z
    'a' -> 'b' -> 'c' -> None
    >>> z.zac.next.next.next = z.zac.next
    >>> z
    

    Ručne bez počítača zisti, čo sa vypíše:

    >>> p = z.zac
    >>> for i in range(10):
            print(repr(p.data), end=' -> ')
            p = p.next
    

  1. Implementuj metódy tried Stack a Queue pomocou cyklického spájaného zoznamu: udržiavaj jedinú referenciu a to na posledný vrchol (jeho nasledovníkom je začiatok zoznamu). Potom otestuj rýchlosť práce s takýmito zásobníkmi a radmi v porovnaní s realizáciou pomocou obyčajného pythonovského zoznamu (typ list):

    • najprv vytvor n prvkovú štruktúru (zásobník alebo rad)

    • potom z neho postupne vyberaj všetky prvky - testuj aj pre veľké n, napríklad 100000


3. Týždenný projekt

L.I.S.T.


Nástroj vyfarbovania nejakej oblasti je súčasťou každého grafického editora a umožňuje vyfarbiť nejako ohraničenú oblasť rastrového obrázka. Niečo podobné budeme programovať aj v tomto projekte. Namiesto rastrového obrázka budeme pracovať s dvojrozmernou tabuľkou (dvojrozmerným poľom, zoznam zoznamov) znakov, pričom rôzne farby budeme reprezentovať rôznymi znakmi (jednoznakovými reťazcami).

Napíš modul riesenie.py s definíciou triedy Fill, pomocou ktorej sa bude realizovať algoritmus vypĺňania nejakej ohraničenej oblasti v dvojrozmernej tabuľke. Takéto vyfarbovanie (vypĺňanie farbami) sa bude riadiť dvoma stratégiami:

  1. vylievanie (nahrádzanie) konkrétnej farby od zadanej pozície až po obrys, ktorým je ľubovoľná iná farba (v niektorých grafických systémoch sa tomu hovorí „surface fill style“ alebo „flood-fill“):

    • algoritmus určí, ktoré políčka štvorcovej siete susedia a majú rovnakú farbu ako štartové políčko (každé políčko okrem krajných má štyroch susedov) - zrejme hranicou tejto oblasti sú políčka ľubovoľnej inej farby alebo okraj celej plochy

    • celú túto oblasť zafarbí nejakou danou farbou

    • tento algoritmus potrebuje poznať pozíciu štartového políčka (pos) a farbu, ktorou sa celá oblasť zafarbí (color)

  2. vylievanie farby od zadanej pozície až po obrys danej konkrétnej farby (v niektorých grafických systémoch sa tomu hovorí „border fill style“ alebo „boundary-fill“):

    • v tomto algoritme sa zafarbuje celá oblasť, ktorá je ohraničená nejakou danou konkrétnou farbou

    • políčka v tejto zafarbovanej oblasti môžu mať na začiatku rôznu farbu, ale po zafarbení sa zmenia na zadanú farbu

    • tento algoritmus potrebuje poznať pozíciu štartového políčka (pos), farbu, ktorou sa celá oblasť zafarbí (color) a farbu, ktorá určuje obrys (border)

    • algoritmus si musí dať pozor na to, že niektoré políčka vyfarbovanej oblasti už môžu mať vyfarbovanú farbu (color) a tiež by nemal spracovávať tie políčka plochy, ktoré už spracoval predtým

Oba algoritmu by mali využiť dátovú štruktúru rad, ktorá je realizovaná pomocou spájaného zoznamu:

  • na začiatku sa do radu vloží štartová pozícia (pos)

  • v cykle sa z radu vyberie prvý prvok, dané políčko sa spracuje a do radu sa vložia pozície 4 susedných políčok

Zostav triedu Fill s týmito metódami:

class Fill:

    class Queue:
        class Node:
            def __init__(self, data):
                ...

        def __init__(self):
            ...

        def enqueue(self, data):
            ...

        def dequeue(self):
            return ...

        def is_empty(self):
            return ...

        def front(self):
            return ...

    def __init__(self, file_name):
        '''prečíta zadaný súbor s dvojrozmerným zoznamom znakov'''

    def perform(self, pos, color, border=None):
        '''vykoná vypĺňanie oblasti: začne na znaku na pozícii pos=(r, s) a vypĺňa zadaným znakom;
           (r, s) označuje riadok a stĺpec v dvojrozmernom poli (číslujeme od 0)
           ak obrys nie je None, vyfarbuje stratégiou po obrys
           vráti počet vyfarbených políčok (počet políčok, ktoré pri vyfarbovaní zmenili farbu)
        '''
        return 0

    def get_dict(self):
        '''vráti frekvenčnú tabuľku výskytov všetkých znakov v tabuľke v tvare slovníka
        '''
        return {}

    def __repr__(self):
        '''vráti obsah dvojrozmerného zoznamu ako jeden reťazec znakov,
           v ktorom sú riadky oddelené '\n';
           mal by to byť rovnaký tvar ako mal vstupný súbor
        '''
        return ''

Napríklad, ak by bol vstupný súbor 'subor1.txt' takýto:

...............
...............
...xxxxxxxxx...
...x.......x...
...xx.ooo.xx...
....x.o.o.x....
...xx..o..xx...
...x.......x...
...xxxxxxxxx...
...............
...............

po zadaní f.perform((5, 0), '+') (funkcia vrátila 104) sa pole zmení na

+++++++++++++++
+++++++++++++++
+++xxxxxxxxx+++
+++x.......x+++
+++xx.ooo.xx+++
++++x.o.o.x++++
+++xx..o..xx+++
+++x.......x+++
+++xxxxxxxxx+++
+++++++++++++++
+++++++++++++++

Ak by sme teraz zisťovali f.get_dict(), funkcia vráti:

{'+': 104, 'x': 32, '.': 23, 'o': 6}

Ďalšie volanie f.perform((7, 5), 'o', 'x') (vráti 23) a f.get_dict() vráti:

{'+': 104, 'x': 32, 'o': 29}

Samotná plocha sa zmení takto:

+++++++++++++++
+++++++++++++++
+++xxxxxxxxx+++
+++xooooooox+++
+++xxoooooxx+++
++++xooooox++++
+++xxoooooxx+++
+++xooooooox+++
+++xxxxxxxxx+++
+++++++++++++++
+++++++++++++++

Triedu rad (Queue) zadefinuj ako vnorenú v triede Fill. Používaj ju potom ako self.Queue().

Obmedzenia

  • riešenie odovzdaj v súbore riesenie.py, pričom sa v ňom bude nachádzať len jedna definícia triedy Fill, trieda Queue bude vnorená v triede Fill

  • odovzdaj ho najneskôr 21. marca do 23:00, môžeš zaň získať 5 bodov

  • prvé dvtria riadky tohto súboru budú obsahovať:

    # 3. zadanie: fill
    # autor: Janko Hrasko
    # datum: 10.3.2021
    
  • zrejme ako autora uvedieš svoje meno

  • program by nemal počas testovania testovačom nič vypisovať (žiadne vaše testovacie print())