tas.py

#!/usr/bin/env python

class RefElement(object):
    def __init__(self, noeud, get_tas):
        self.ref = noeud
        self.get_tas = get_tas
        self.existe = True

    def __str__(self):
        if self.existe:
            return "<Tas Binomial Référant à '%s'>" % str(self.ref.val)
        else:
            return "<Référence du tas inexistante>"

    def descendre(self, new_key):
        # Met à jour la priorité de l'élément.
        assert self.existe
        assert self.ref.ref == self
        self.ref.descendre(new_key)

    def supprimer(self):
        # Retire l'élément du tas.
        self.descendre(self)
        v = self.get_tas().extraireMin()
        assert not self.existe
        assert v is self.ref.valeur

    def dans_tas(self, tas):
        """Retourne True si l'élément appartient au tas entré en paramètre;
        False sinon.
        """
        return self.existe and self.get_tas() == tas

    def __lt__(self, autre):
        "Agit comme une positive infinie: Toujours True."
        return True

    def __gt__(self, autre):
        "Agit comme une négative infinie: Toujours False."
        return False


class TasBinomial(object):
    class Noeud(object):
        def __init__(self, get_tas, index, valeur=None):
            self.niveau = 0
            self.parent = None
            self.suivant = None
            self.fils = None
            self.index = index
            self.ref = RefElement(self, get_tas)
            if valeur == None:
                valeur = index
            self.valeur = valeur

        def __str__(self):
            def k(x): return str(x.index) if x else 'NIL'
            return '(Valeur:%s, Fils:%s, Suivant:%s)' % (k(self), k(self.fils), k(self.suivant))

        def link(self, other):
            "Crée un sous arbre."
            other.parent = self
            other.suivant = self.fils
            self.fils = other
            self.niveau += 1

        def descendre(self, new_key):
            noeud = self
            assert new_key < noeud.index
            noeud.index = new_key
            cur = noeud
            parent = cur.parent
            while parent and cur.index < parent.index:
                # need to bubble up
                # swap refs
                parent.ref.ref, cur.ref.ref = cur, parent
                parent.ref, cur.ref = cur.ref, parent.ref
                # now swap keys and payload
                parent.index, cur.index = cur.index, parent.index
                parent.valeur, cur.valeur = cur.valeur, parent.valeur
                # step up
                cur = parent
                parent = cur.parent

        @staticmethod
        def roots_merge(h1, h2):
            # Union de deux tas, ordonné par degré.
            # Retourne une nouvelle racine.
            if not h1:
                return h2
            if not h2:
                return h1
            if h1.niveau < h2.niveau:
                h = h1
                h1 = h.suivant
            else:
                h = h2
                h2 = h2.suivant
            p = h
            while h2 and h1:
                if h1.niveau < h2.niveau:
                    p.suivant = h1
                    h1 = h1.suivant
                else:
                    p.suivant = h2
                    h2 = h2.suivant
                p = p.suivant
            if h2:
                p.suivant = h2
            else:
                p.suivant = h1
            return h

        @staticmethod
        def roots_reverse(h):
            # Inverse la liste des racine du tas.
            # Retourn la nouvelle racine. Nettoie aussi la référence des parents.
            if not h:
                return None
            tail = None
            suivant = h
            h.parent = None
            while h.suivant:
                suivant = h.suivant
                h.suivant = tail
                tail = h
                h = suivant
                h.parent = None
            h.suivant = tail
            return h

    class __Ref(object):
        def __init__(self, h):
            self.tas = h
            self.ref = None

        def get_ref_tas(self):
            if not self.ref:
                return self
            else:
                # compact
                self.ref = self.ref.get_ref_tas()
                return self.ref

        def get_tas(self):
            return self.get_ref_tas().get_tas

    def __init__(self, list=[]):
        # Populate a new heap with the (key, value) pairs in 'lst'.
        # If the elements of lst are not subscriptable, then they are treated as
        # opaque elements and inserted into the heap themselves.
        self.racine = None
        self.taille = 0
        self.ref = TasBinomial.__Ref(self)
        for x in list:
            try:
                self.inserer(x[0], x[1])
            except TypeError:
                self.inserer(x)

    def inserer(self, key, value=None):
        # Insert 'value' in to the heap with priority 'key'. If 'value' is omitted,
        # then 'key' is used as the value.
        # Returns a reference (of type ItemRef) to the internal node in the tree.
        # Use this reference to delete the key or to change its priority.
        n = TasBinomial.Noeud(self.ref.get_tas, key, value)
        self.__union(n)
        self.taille += 1
        return n.ref

    def union(self, other):
        # Merge 'other' into 'self'. Returns None.
        # Note: This is a destructive operation; 'other' is an empty heap afterwards.
        self.taille = self.taille + other.taille
        h2 = other.racine
        self.__union(h2)
        other.ref.ref = self.ref
        other.__init__()

    def min(self):
        # Returns the value with the minimum key (= highest priority) in the heap
        # without removing it, or None if the heap is empty.
        pos = self.__min()
        return pos[0].valeur if pos else None

    def extraire_min(self):
        # Returns the value with the minimum key (= highest priority) in the heap
        # AND removes it from the heap, or None if the heap is empty.
        #
        # find mininum
        pos = self.__min()
        if not pos:
            return None
        else:
            (x, prev) = pos
            # remove from list
            if prev:
                prev.suivant = x.suivant
            else:
                self.racine = x.suivant
            fils = TasBinomial.Noeud.roots_reverse(x.fils)
            self.__union(fils)
            x.ref.existe = False
            self.taille -= 1
            return x.valeur

    def __nonzero__(self):
        # True si le tas n'est pas vide; False sinon.
        return self.tas != None

    def __len__(self):
        # Retourne le nombre d'élément dans le tas.
        return self.taille

    def __setitem__(self, key, value):
        # Insertion.
        # H[key] = value  équivaut à  H.insert(key, value)
        self.inserer(key, value)

    def __iadd__(self, other):
        # Merge.
        # a += b  équivaut à  a.union(b).
        self.union(other)
        return self

    def suivant(self):
        # Returns the value with the minimum key (= highest priority) in the hseap
        # AND removes it from the heap; raises StopIteration if the heap is empty.
        if self.racine:
            return self.extraire_min()
        else:
            raise StopIteration

    def __contains__(self, ref):
        # Test whether a given reference 'ref' (of RefElement) is in this heap.
        if type(ref) != RefElement:
            raise TypeError
        else:
            return ref.dans_tas(self)

    def __min(self):
        if not self.racine:
            return None
        min = self.racine
        min_prev = None
        prev = min
        cur = min.suivant
        while cur:
            if cur.index < min.index:
                min = cur
                min_prev = prev
            prev = cur
            cur = cur.suivant
        return (min, min_prev)

    def __union(self, h2):
        if not h2:
            # nothing to do
            return

        h1 = self.racine

        if not h1:
            self.racine = h2
            return

        h1 = TasBinomial.Noeud.roots_merge(h1, h2)
        prev = None
        x = h1
        next = x.suivant
        while next:
            if x.niveau != next.niveau or \
                    (next.suivant and next.suivant.niveau == x.niveau):
                prev = x
                x = next
            elif x.index <= next.index:
                # x becomes the root of next
                x.suivant = next.suivant
                x.link(next)
            else:
                # next becomes the root of x
                if not prev:
                    # update the "master" head
                    h1 = next
                else:
                    # just update previous link
                    prev.suivant = next
                next.link(x)
                # x is not toplevel anymore, update ref by advancing
                x = next
            next = x.suivant
        self.racine = h1


def créerTas(list=[]):
    # Création d'un nouveau tas en utilisant *list* qui est une séquence de (clé, valeur)
    # Avec la clé
    return TasBinomial(list)


if __name__ == "__main__":
    tokens1 = [10, 12, 11, 1, 5, 22, 99, 20, 70, 60, 65, 23, 6, 4]
    tokens2 = [80, 19, 51, 30, 82, 65, 45, 55, 75, 88, 28, 27, 3, 6, 7, 2]

    tas1 = créerTas(tokens1)
    tas2 = créerTas(tokens2)
    h3 = créerTas()
    # print(tas1.racine)
    # print(tas2.racine)
    # tas1.union(tas2)
    # print(tas1.taille)
    h3.inserer(50)
    h3.inserer(3)
    print(h3.racine)
    print(h3.taille)
    h3.inserer(5)
    h3.inserer(2)
    h3.inserer(24)
    print(h3.racine)
    print(h3.taille)