# Ponazoritev skladov in vrst v Pythonu

class Sklad():
    def __init__(self):
        self.elementi = []

    def __repr__(self):
        return str(self.elementi)

    def prazno(self):
        return (len(self.elementi) == 0)

    def vzemi(self):
        x = self.elementi.pop()
        return x

    def dodaj(self, x):
        self.elementi.append(x)


class Vrsta():
    def __init__(self):
        self.elementi = []

    def __repr__(self):
        return str(self.elementi)

    def prazno(self):
        return (len(self.elementi) == 0)

    def vzemi(self):
        x = self.elementi.pop(0) # Edina razlika glede na Sklad
        return x

    def dodaj(self, x):
        self.elementi.append(x)

def isci(prostor, struktura):
    # struktura je podatkovna struktura, v kateri
    # hranimo tiste, ki jih moramo se pregledati,
    # na zacetku je prazna
    struktura.dodaj(prostor.zacetno_stanje())
    while not struktura.prazno():
        x = struktura.vzemi()
        if prostor.jeResitev(x):
            return x
        else:
            for y in prostor.sosedi(x):
                struktura.dodaj(y)
    return None

def isciVGlobino(prostor):
    return isci(prostor, Sklad())

def isciVSirino(prostor):
    return isci(prostor, Vrsta())

class ProstorVsote():
    def __init__(self, stevila, ciljnaVsota):
        self.stevila = stevila
        self.ciljnaVsota = ciljnaVsota

    def zacetno_stanje(self):
        return ((), 0)

    def jeResitev(self, stanje):
        (xs, k) = stanje
        return sum(xs) == self.ciljnaVsota

    def sosedi(self, stanje):
        (xs, k) = stanje
        if k < len(self.stevila):
            return ((xs, k+1), (xs + (self.stevila[k],), k+1))
        else:
            return ()

class ProstorPoti():
    def __init__(self, graf, zacetek, konec):
        self.graf = graf
        self.zacetek = zacetek
        self.konec = konec

    def zacetno_stanje(self):
        # pot dolžine 1
        return (self.zacetek,)

    def jeResitev(self, pot):
        return pot[-1] == self.konec

    def sosedi(self, pot):
        zadnje = pot[-1] # Zadnje vozlisce v poti
        for v in self.graf[zadnje]:
            # v gre cez sosede zadnjega vozlisca
            if v not in pot:
                yield (pot + (v,))

# Primer:
g = {1 : (2, 3),
     2 : (7,),
     3 : (4, 5),
     4 : (6,),
     5 : (),
     6 : (7,),
     7 : ()}