Logo Search packages:      
Sourcecode: gadfly version File versions  Download package

kjSet.py

00001 """ 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
#
#
#

Generated by  Doxygen 1.6.0   Back to index