[Python-checkins] python/nondist/sandbox/setobj automata.py, 1.1, 1.2 cube.py, 1.1, 1.2

Sun Nov 16 11:36:00 EST 2003

Update of /cvsroot/python/python/nondist/sandbox/setobj
In directory sc8-pr-cvs1:/tmp/cvs-serv18199
Modified Files:
	automata.py cube.py 
Log Message:
Update the demo programs to use the builtins
Index: automata.py
===================================================================
RCS file: /cvsroot/python/python/nondist/sandbox/setobj/automata.py,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** automata.py	16 Nov 2003 03:10:40 -0000	1.1
--- automata.py	16 Nov 2003 16:35:58 -0000	1.2
***************
*** 5,13 ****
 """

- try:
- from set import frozenset as ImmutableSet, set as Set
- except ImportError:
- from sets import ImmutableSet, Set
- 
 class InputError(Exception): pass

--- 5,8 ----
***************
*** 20,24 ****
 functions.
 """
! self.alphabet = ImmutableSet(Sigma)
 self.transition = delta
 self.initialState = S0
--- 15,19 ----
 functions.
 """
! self.alphabet = frozenset(Sigma)
 self.transition = delta
 self.initialState = S0
***************
*** 27,32 ****
 def states(self):
 """Generate all states of the DFA."""
! explored = Set()
! unexplored = Set([self.initialState])
 while unexplored:
 s = unexplored.pop()
--- 22,27 ----
 def states(self):
 """Generate all states of the DFA."""
! explored = set()
! unexplored = set([self.initialState])
 while unexplored:
 s = unexplored.pop()
***************
*** 55,71 ****
 and result of the transition function are both sets.
 """
! self.alphabet = ImmutableSet(Sigma)
 self.transition = delta
! self.initialStates = ImmutableSet(S0)
 self.isfinal = F

 def setTransition(self,states,c):
 """States reachable from input set by input c."""
! result = Set()
 for s in states:
 result |= self.transition(s,c)
! return ImmutableSet(result)

! def finalSet(self,states):
 """Test whether any of given set of states is final."""
 for s in states:
--- 50,66 ----
 and result of the transition function are both sets.
 """
! self.alphabet = frozenset(Sigma)
 self.transition = delta
! self.initialStates = frozenset(S0)
 self.isfinal = F

 def setTransition(self,states,c):
 """States reachable from input set by input c."""
! result = set()
 for s in states:
 result |= self.transition(s,c)
! return frozenset(result)

! def finalset(self,states):
 """Test whether any of given set of states is final."""
 for s in states:
***************
*** 77,81 ****
 """Convert NFA to DFA."""
 return DFA(self.alphabet,self.setTransition,
! self.initialStates,self.finalSet)

 def __call__(self,input):
--- 72,76 ----
 """Convert NFA to DFA."""
 return DFA(self.alphabet,self.setTransition,
! self.initialStates,self.finalset)

 def __call__(self,input):
***************
*** 94,98 ****
 4: ([], []),
 }
! def delta(s,i): return ImmutableSet(Sipser_1_13[s][int(i)])
 def final(s): return s == 4
 N2 = NFA("01",delta,[1],final)
--- 89,93 ----
 4: ([], []),
 }
! def delta(s,i): return frozenset(Sipser_1_13[s][int(i)])
 def final(s): return s == 4
 N2 = NFA("01",delta,[1],final)
Index: cube.py
===================================================================
RCS file: /cvsroot/python/python/nondist/sandbox/setobj/cube.py,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** cube.py	16 Nov 2003 02:41:33 -0000	1.1
--- cube.py	16 Nov 2003 16:35:58 -0000	1.2
***************
*** 1,22 ****
- try:
- from set import frozenset as ImmutableSet
- except ImportError:
- from sets import ImmutableSet
- 
 def powerset(U):
 """Generates all subsets of a set or sequence U."""
 U = iter(U)
 try:
! x = ImmutableSet([U.next()])
 for S in powerset(U):
 yield S
 yield S | x
 except StopIteration:
! yield ImmutableSet()

 def cube(n):
 """Graph of n-dimensional hypercube."""
! singletons = [ImmutableSet([x]) for x in range(n)]
! return dict([(x, ImmutableSet([x^s for s in singletons]))
 for x in powerset(range(n))])

--- 1,17 ----
 def powerset(U):
 """Generates all subsets of a set or sequence U."""
 U = iter(U)
 try:
! x = frozenset([U.next()])
 for S in powerset(U):
 yield S
 yield S | x
 except StopIteration:
! yield frozenset()

 def cube(n):
 """Graph of n-dimensional hypercube."""
! singletons = [frozenset([x]) for x in range(n)]
! return dict([(x, frozenset([x^s for s in singletons]))
 for x in powerset(range(n))])

***************
*** 28,34 ****
 for x in G:
 for y in G[x]:
! nx = [ImmutableSet([x,z]) for z in G[x] if z != y]
! ny = [ImmutableSet([y,z]) for z in G[y] if z != x]
! L[ImmutableSet([x,y])] = ImmutableSet(nx+ny)
 return L

--- 23,29 ----
 for x in G:
 for y in G[x]:
! nx = [frozenset([x,z]) for z in G[x] if z != y]
! ny = [frozenset([y,z]) for z in G[y] if z != x]
! L[frozenset([x,y])] = frozenset(nx+ny)
 return L