python-gadfly 1.0.0-15.1 / usr / share / pyshared / gadfly / kjSet.py

""" Sets implemented using mappings.

These only work for "immutable" elements.
probably not terribly efficient, but easy to implement
and not as slow as concievably possible.

:Author: Aaron Watters
:Maintainers: http://gadfly.sf.net/
:Copyright: Aaron Robert Watters, 1994
:Id: $Id: kjSet.py,v 1.3 2002/05/11 02:59:05 richard Exp $:
"""

def NewSet(Sequence):
    Result = {}
    for Elt in Sequence:
        Result[Elt] = 1
    return Result

def Empty(Set):
    if Set == {}:
        return 1
    else:
        return 0

def get_elts(Set):
    return Set.keys()

def member(Elt,Set):
    return Set.has_key(Elt)

# in place mutators:
# returns if no change otherwise 1

def addMember(Elt,Set):
    change = 0
    if not Set.has_key(Elt):
        Set[Elt] = 1
        change = 1
    return change

def Augment(Set, OtherSet):
    change = 0
    for Elt in OtherSet.keys():
        if not Set.has_key(Elt):
            Set[Elt] = 1
            change = 1
    return change


def Mask(Set, OtherSet):
    change = 0
    for Elt in OtherSet.keys():
        if Set.has_key(Elt):
            del Set[Elt]
            change = 1
    return change

# side effect free functions

def Intersection(Set1, Set2):
    Result = {}
    for Elt in Set1.keys():
        if Set2.has_key(Elt):
            Result[Elt] = 1
    return Result

def Difference(Set1, Set2):
    Result = {}
    for Elt in Set1.keys():
        if not Set2.has_key(Elt):
            Result[Elt] = 1
    return Result

def Union(Set1,Set2):
    Result = {}
    Augment(Result,Set1)
    Augment(Result,Set2)
    return Result

def Subset(Set1,Set2):
    Result = 1
    for Elt in Set1.keys():
        if not Set2.has_key(Elt):
            Result = 0
            return Result # nonlocal
    return Result

def Same(Set1,Set2):
    if Subset(Set1,Set2) and Subset(Set2,Set1):
        return 1
    else:
        return 0

# directed graphs as Dictionaries of Sets
#   also only works for immutable nodes

def NewDG(pairlist):
    Result = {}
    for (source,dest) in pairlist:
        AddArc(Result, source, dest)
    return Result

def GetPairs(Graph):
    result = []
    Sources = Graph.keys()
    for S in Sources:
        Dests = get_elts( Graph[S] )
        ThesePairs = [None] * len(Dests)
        for i in range(0,len(Dests)):
            D = Dests[i]
            ThesePairs[i] = (S, D)
        result = result + ThesePairs
    return result

def AddArc(Graph, Source, Dest):
    change = 0
    if Graph.has_key(Source):
        Adjacent = Graph[Source]
        if not member(Dest,Adjacent):
            addMember(Dest,Adjacent)
            change = 1
    else:
        Graph[Source] = NewSet( [ Dest ] )
        change = 1
    return change

def Neighbors(Graph,Source):
    if Graph.has_key(Source):
        return get_elts(Graph[Source])
    else:
        return []

def HasArc(Graph, Source, Dest):
    result = 0
    if Graph.has_key(Source) and member(Dest, Graph[Source]):
        result = 1
    return result

def Sources(Graph):
    return Graph.keys()

# when G1, G2 and G3 are different graphs this results in
#   G1 = G1 U ( G2 o G3 )
# If G1 is identical to one of G2,G3 the result is somewhat
# nondeterministic (depends on dictionary implementation).
# However, guaranteed that AddComposition(G,G,G) returns
#    G1 U (G1 o G1) <= G <= TC(G1)
# where G1 is G's original value and TC(G1) is its transitive closure
# hence this function can be used for brute force transitive closure
#
def AddComposition(G1, G2, G3):
    change = 0
    for G2Source in Sources(G2):
        for Middle in Neighbors(G2,G2Source):
            for G3Dest in Neighbors(G3, Middle):
                if not HasArc(G1, G2Source, G3Dest):
                    change = 1
                    AddArc(G1, G2Source, G3Dest)
    return change

# in place transitive closure of a graph
def TransClose(Graph):
    change = AddComposition(Graph, Graph, Graph)
    somechange = change
    while change:
        change = AddComposition(Graph, Graph, Graph)
        if not somechange:
            somechange = change
    return somechange

########### SQueue stuff
#
#  A GrabBag should be used to hold objects temporarily for future
#  use.  You can put things in and take them out, with autodelete
#  that's all!

# make a new baggy with nothing in it
#   BG[0] is insert cursor BG[1] is delete cursor, others are elts
#
OLD = 1
NEW = 0
START = 2
def NewBG():
    B = [None]*8 #default size
    B[OLD] = START
    B[NEW] = START
    return B

def BGempty(B):
    # other ops must maintain this: old == new iff empty
    return B[OLD] == B[NEW]

# may return new, larger structure
# must be used with assignment...  B = BGadd(e,B)
def BGadd(elt, B):
    cursor = B[NEW]
    oldlen = len(B)
    # look for an available position
    while B[cursor] != None:
        cursor = cursor+1
        if cursor >= oldlen: cursor = START
        if cursor == B[NEW]: #back to beginning
            break
    # resize if wrapped
    if B[cursor] != None:
        B = B + [None] * oldlen
        cursor = oldlen
        B[OLD] = START
    if B[cursor] != None:
        raise IndexError, "can't insert?"
    # add the elt
    B[cursor] = (elt,)
    B[NEW] = cursor
    # B nonempty so OLD and NEW should differ.
    if B[OLD] == cursor:
        B[NEW] = cursor + 1
        if B[NEW]<=len(B): B[NEW] = START
    return B

def BGgetdel(B):
    # find something to delete:
    cursor = B[OLD]
    blen = len(B)
    while B[cursor]==None:
        cursor = cursor+1
        if cursor>=blen: cursor = START
        if cursor == B[OLD]: break # wrapped
    if B[cursor] == None:
        raise IndexError, "delete from empty grabbag(?)"
    # test to see if bag is empty (position cursor2 at nonempty slot)
    cursor2 = cursor+1
    if cursor2>=blen: cursor2 = START
    while B[cursor2]==None:
        cursor2 = cursor2+1
        if cursor2>=blen: cursor2 = START
        # since B[cursor] not yet deleted while will terminate
    # get and delete the elt
    (result,) = B[cursor]
    B[cursor] = None
    # cursor == cursor2 iff bag is empty
    B[OLD] = cursor2
    if B[NEW] == cursor2: B[NEW] = cursor
    return result

def BGtest(n):
    B = NewBG()
    rn = range(n)
    rn2 = range(n-2)
    for i in rn:
        for j in rn:
            B = BGadd( (i,j), B)
            B = BGadd( (j,i), B)
            x = BGgetdel(B)
        for j in rn2:
            y = BGgetdel(B)
        print (i, x, y)
    return B

#
# $Log: kjSet.py,v $
# Revision 1.3  2002/05/11 02:59:05  richard
# Added info into module docstrings.
# Fixed docco of kwParsing to reflect new grammar "marshalling".
# Fixed bug in gadfly.open - most likely introduced during sql loading
# re-work (though looking back at the diff from back then, I can't see how it
# wasn't different before, but it musta been ;)
# A buncha new unit test stuff.
#
# Revision 1.2  2002/05/08 00:49:00  anthonybaxter
# El Grande Grande reindente! Ran reindent.py over the whole thing.
# Gosh, what a lot of checkins. Tests still pass with 2.1 and 2.2.
#
# Revision 1.1.1.1  2002/05/06 07:31:09  richard
#
#
#