#
# sets implemented using mappings
# Copyright Aaron Robert Watters, 1994
#
# these only work for "immutable" elements.
# probably not terribly efficient, but easy to implement
# and not as slow as concievably possible.
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
|