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