man das mit den einrücken ist echt ätzend. Lief erst garnichts und dann hab ich alle Dateien nochmal neu eingerückt.
xlist.py:
Code: Alles auswählen
#!/usr/bin/python
from inspect import *
class xlist(list):
def __init__(self,*a):
super(xlist, self).__init__(*a)
def cp(self):
return xlist(self[:])
#map
def map(self, fun):
return xmap(fun,self)
#filter functions
def filter(self, fun):
return xfilter(fun,self)
def partition(self,fun):
return xpartition(fun,self)
def split(self, x):
return xsplit(x,self)
#reduce
def reduce(self, fun, init=None):
return xreduce(fun,init,self)
#flatten
def flatten(self):
return xflatten(self)
#zip/unzip
def zip(self,a,c=None):
if c: return xzip(a,self,c)
else: return xzip(self,a)
def unzip(fun):
return xunzip(fun,self)
#other:
def isempty(self):
return len(self) == 0
def empty(self):
self=xlist([])
return self
def len(self):
return len(self)
def smart_iter(self):
for elem in self:
yield elem
def action(self, fun):
xaction(fun,self)
#operator overloading
def __mul__(self, a):
'''
mapping:
l * (...)
'''
try: return self.map(a)
except TypeError: return super(xlist,self).__mul__(a)
def __rmul__(self, a):
return self * a
def __or__(self, a):
'''
filter:
list | (...)
'''
return self.filter(a)
def __ror__(self,a):
return self | a
def __div__(self, a):
'''
reduce:
self / (...)
'''
try: return self.reduce(*a)
except TypeError: return self.reduce(a)
def __rdiv__(self,a):
return self / a
def __and__(self,a):
'''
action:
self & (...)
'''
self.action(a)
def __rand__(self,a):
return self & a
def __getslice__(self,*a):
return xlist(super(xlist, self).__getslice__(*a))
#List Funtions
def xmap(fun,seq=None):
def __map(seq):
return xlist(map(fun, seq))
if seq: return __map(seq)
else: return __map
def xfilter(fun,seq=None):
def __filter(seq):
return xlist(filter(fun, seq))
if seq: return __filter(seq)
else: return __filter
def xpartition(fun,seq=None):
def __partition(seq):
left=[]
right=[]
for elem in seq:
if fun(elem):
left.append(elem)
else:
right.append(elem)
return (xlist(left),xlist(right))
if seq: return __partition(seq)
return __partition
def xsplit(f,seq=None):
def __splitfun(seq):
left=[]
right=[]
for elem in seq:
if(f(elem)): break
else: left.append(elem)
right=seq[len(left) + 1:]
return (xlist(left),xlist(right))
def __splitvar(seq):
try:
i=seq.index(f)
left=seq[0:i]
right=seq[i+1:]
return (xlist(left),xlist(right))
except ValueError:
return (xlist(seq[:]),xlist([]))
if (isfunction(f) or ismethod(f)):
if seq: return __splitfun(seq)
else: return __splitfun
else:
if seq: return __splitvar(seq)
else: return __splitvar
def xreduce(fun,init=None,seq=None):
def __reduce(seq):
if None!=init: ret = reduce(fun, seq, init)
else: ret = reduce(fun,seq)
if isinstance(ret,list):
return xlist(ret)
return ret
if seq: return __reduce(seq)
else: return __reduce
def xflatten(nested):
def __flatten(nested):
try:
try: nested + ''
except TypeError: pass
else: raise TypeError
for sublist in nested:
for elem in __flatten(sublist):
yield elem
except TypeError:
yield nested
return xlist(__flatten(nested))
def xzip(a,b=None,c=None):
def __xzip(seq1,seq2):
return xmap(lambda t: a(t[0],t[1])) (zip(seq1, seq2))
if (ismethod(a) or isfunction(a)) \
and not (b and c): return __xzip
elif b and c: return __xzip(b,c)
else: return xlist(zip(a,b))
def xunzip(fun,seq=None):
def __unzip(seq):
left=[]
right=[]
tmp=()
for elem in seq:
tmp=fun(elem)
left.append(tmp[0])
right.append(tmp[1])
return xlist(left),xlist(right)
if seq: return __unzip(seq)
else: return __unzip
def xaction(fun,seq=None):
def __action(seq):
for elem in seq:
fun(elem)
if seq: __action(seq)
else: return __action
def xfind(obj,seq=None,start=0,stop=None):
def __find(seq,start=0,stop=None):
try:
if stop: cstop=stop
else: cstop=len(seq)+1
return seq.index(obj,start,cstop)
except ValueError: return -1
if seq: return __find(seq,start,stop)
else: return __find
def xxfind(obj,seq=None):
def __xfind(seq):
return lambda start=0,stop=None: xfind(obj,seq,start,stop)
if seq: return __xfind(seq)
else: return __xfind
if __name__ == "__main__":
l = xlist([1,3,6,2])
tmp=l.cp()
print l
x=lambda a: a+a
print "map: ", l * (lambda a: a + a)
print
print l
l*=lambda a: a + a
print "map l*=...", l
print
print "filter: ", l.filter(lambda x: x < 4)
print l | (lambda x: x < 4)
print
print "reduce: ", tmp / (lambda a,b: a + b)
print tmp / (lambda a,b: a + b, 0)
print tmp.reduce(lambda a,b: a + b)
print
tmp.extend([1,2,3])
print tmp
print isinstance(tmp,xlist)
print
del tmp[0]
print tmp
print isinstance(tmp,xlist)
h=tmp[2:4]
print h
print isinstance(h,xlist)
print
print tmp.split(1)
print tmp.split(lambda x: x == 1)
print
print tmp.partition(lambda x: x < 3)
print
h=xlist([1,3,[3,[4,6,[7]]]])
print h
h=h.flatten()
print h
print isinstance(h,xlist)
print len(h)
print h.len()
h+= tmp
print h
print isinstance(h,xlist)
h+= [1,3,4]
print h
print isinstance(h,xlist)
print
def xt(a):
print a,
h & xt
print
xt & h
print
print xzip(lambda x,y: x + y)(h,tmp)
print xzip(lambda x,y: x + y,h,tmp)
print h.zip(tmp)
print h.zip(lambda x,y: x + y, tmp)
print
def qsort(seq):
if len(seq) <= 1: return seq
else:
return (lambda left,right: qsort(left) + [seq[0]] + qsort(right) )(
*xpartition(lambda a: a <= seq[0], seq[1:]) )
print qsort(h)
xptree.py:
Code: Alles auswählen
#!/usr/bin/python
from xlist import *
import pdb
class xptree:
def __init__(self, val, c=[]):
self.val=val
self.children=c
def isleaf(self):
try: return not self.children
except NameError: return 1
def isnode(self):
return not self.isleaf()
def depth(self):
if self.isleaf(): return 0
else: return 1 + xmap(xptree.depth, self.children) / max
def countNodes(self):
if self.isleaf(): return 0
else: return 1 + xmap(xptree.countNodes, self.children) / (lambda a,b: a+b)
def __len__(self):
if self.isleaf(): return 1
else: return 1 + xmap(xptree.__len__, self.children) / (lambda a,b: a+b)
def len(self):
return len(self)
def flatten(self):
if self.isleaf(): return [self.val]
else: return [self.val] + xmap(xptree.flatten, self.children).flatten()
def leafs(self):
if self.isleaf(): return [self.val]
else: return xmap(xptree.leafs, self.children).flatten()
def map(self, fun):
return xpmap(fun,self)
def reduce(self, fun, init=0):
return xpreduce(fun,init,self)
def filter(self, fun):
return xpfilter(fun, self)
def action(self, fun):
xpaction(fun, self)
def __str__(self):
if self.isleaf(): return '[' + str(self.val) + ']'
else:
ret='< [' + str(self.val) + '] : '
ret+= xmap(str,self.children) / (lambda a,b: str(a) + ', ' + str(b))
return ret + ' >'
def __iter__(self):
yield self.val
if self.isnode():
for elem in self.children:
for val in elem: yield val
#operator overloading
def __nonzero__(self):
return True
def __mul__(self, a):
'''
mapping:
l * (...)
'''
return self.map(a)
def __rmul__(self, a):
return self * a
def __or__(self, a):
'''
filter:
list | (...)
'''
return self.filter(a)
def __ror__(self,a):
return self | a
def __div__(self, a):
'''
reduce:
self / (...)
'''
try: return self.reduce(*a)
except TypeError: return self.reduce(a)
def __rdiv__(self,a):
return self / a
def __and__(self,a):
'''
action:
self & (...)
'''
self.action(a)
def __rand__(self,a):
return self & a
def xpleaf(val): # alpha -> xptree
return xptree(val)
def xpnode(val,children): # (alpha,seq of xptree) -> xptree
return xptree(val,children)
def xpbuild(seq):
if (seq == None) or (seq == []): return None
val = seq[0]
children=[]
for elem in seq[1:]:
if isinstance(elem,list):
children.append(xpbuild(elem))
if children: return xpnode(val,children)
else: return xpleaf(val)
def xpmap(fun,tree=None):
def __pmap(tree):
if tree.isleaf(): return xpleaf( fun(tree.val) )
else: return xpnode( fun(tree.val) , xmap(__pmap, tree.children ))
if tree: return __pmap(tree)
else: return __pmap
def xpreduce(fun,init=0,tree=None):
hlp=lambda var,tree: xpreduce(fun,var,tree)
def __preduce(tree):
if tree.isleaf(): return fun(init,tree.val)
else: return fun(init, xreduce(hlp, tree.val, tree.children) )
if tree: return __preduce(tree)
else: return __preduce
def xpfilter(fun,tree=None):
def __pfilter(tree):
if not fun(tree.val): return None
if tree.isleaf(): return xpleaf(tree.val)
else:
ch = xmap(__pfilter, tree.children) | (lambda x: not x == None)
return xpnode(tree.val,ch)
if tree: return __pfilter(tree)
else: return __pfilter
def xpaction(fun,tree=None):
def __paction(tree):
fun(tree.val)
if tree.isnode():
xaction(__paction, tree.children)
if tree: __paction(tree)
else: return __paction
if __name__ == '__main__':
tmp = [1,
[2,
[5,
[8],
[2]
],
[6]
],
[3],
[4,
[23],
[12]
]
]
hlp=xpbuild(tmp)
print str(hlp)
print "depth: ", hlp.depth()
print "nodes: ", hlp.countNodes()
print "len: ", hlp.len()
print "flatten: ", hlp.flatten()
print "leafs: " , hlp.leafs()
print "map: ", hlp * (lambda x: 2*x)
print "reduce: ", hlp / (lambda a,b: a + b,0)
print "filter: ", hlp | (lambda x: x < 7)
print "action: ",
def pfun(p):
print p,
hlp & pfun
print
print "iterator: ",
for i in hlp:
print i,
print
btree.py:
Code: Alles auswählen
#!/usr/bin/python
from xlist import xlist
from inspect import *
import pdb
def _val(fun,obj=None,ne=0):
def __val(obj,ne=0):
if obj: return fun(obj)
else: return ne
if obj: return __val(obj,ne)
else: return __val
class btree:
def __init__(self, v, l=None, r=None):
self.val=v
self.left=l
self.right=r
def isleaf(self):
return (None==self.left) and (None==self.right)
def isnode(self):
return not self.isleaf()
def toleaf(self):
self.left=None
self.right=None
return self
def depth(self):
if self.isleaf(): return 0
else:
cdepth=_val(btree.depth)
return 1 + max(cdepth(self.left),cdepth(self.right))
def c_nodes(self):
if self.isleaf(): return 0
else:
cnodes=_val(btree.c_nodes)
return 1 + cnodes(self.left) + cnodes(self.right)
def width(self):
'''
number of leafs
'''
if self.isleaf(): return 1
else:
cwidth=_val(btree.width)
return (cwidth(self.left) + cwidth(self.right))
def len(self):
return len(self)
def __len__(self):
if self.isleaf(): return 1
else:
clen=_val(btree.__len__)
return 1 + clen(self.left) + clen(self.right)
def flatten(self):
'''
in order flatten
'''
if self.isleaf(): return [self.val]
else:
fl=_val(btree.flatten)
return xlist( fl(self.left,[]) + [self.val] + fl(self.right,[]) )
def zip(self,a,b=None):
if b: return xzip(a,self,b)
else: return xzip(self,a)
def leafs(self):
'''
first left, then right tree
'''
if self.isleaf(): return [self.val]
else:
fl=_val(btree.leafs)
return xlist( fl(self.left,[]) + fl(self.right,[]) )
def map(self, fun):
return xmap(fun,self)
def reduce(self, fun, neutral):
return xreduce(fun,neutral, self)
def filter(self, fun):
return xfilter(fun, self)
def action(self, fun):
xaction(fun, self)
def swap(self):
tmp=self.right
self.right=self.left
self.left=tmp
return self
def reflect(self):
self.swap()
def hlp(x):
if x: x.reflect()
hlp(self.left)
hlp(self.right)
return self
def lrotate(self):
'''
rotate left
'''
tmp=self.right
if tmp:
self.right=tmp.left
tmp.left=self
return tmp
else: return self
def rrotate(self):
tmp=self.left
if tmp:
self.left=tmp.right
tmp.right=self
return tmp
else: return self
def dlrotate(self):
if self.right:
self.right=self.right.rrotate()
return self.lrotate()
def drrotate(self):
if self.left:
self.left=self.left.lrotate()
return self.rrotate()
def __str__(self):
if self.isleaf(): return '[' + str(self.val) + ']'
else:
st=_val(str)
ret='< [' + str(self.val) + '] <'
ret+=st(self.left,'<empty>') + ' | ' + st(self.right,'<empty>')
return ret + '> >'
def __iter__(self):
'''
iteratr inorder
'''
if self.isnode():
def hlp(obj):
if isinstance(obj, btree):
for elem in obj: yield elem
for e in hlp(self.left): yield e
yield self.val
for e in hlp(self.right): yield e
else: yield self.val
def __contains__(self,obj):
for elem in self:
if elem == obj: return 1
return 0
def leftmost(self):
if self.isleaf() or not self.left: return self.val
else: return self.left.leftmost()
def rightmost(self):
if self.isleaf() or not self.right: return self.val
else: return self.right.rightmost()
def children(self):
if(self.isleaf()) or not self: return None
ret=xlist()
if self.left: ret.append(self.left.val)
if self.right: ret.append(self.right.val)
return ret
def grandchildren(self):
lc=self.left.children()
rc=self.right.children()
if (not lc) and (not rc): return None
elif not lc: return rc
elif not rc: return lc
else: return lc + rc
def level(self,i):
if i==0 : return [self.val]
else:
ret=xlist()
if self.left:
ret.extend(self.left.level(i-1))
if self.right:
ret.extend(self.right.level(i-1))
return ret
def eq(self,other):
def teq(a,b):
if (not a) and (not b): return True
if (not a) or (not b): return False
else: return (a.val == b.val) and teq(a.left,b.left) and teq(a.right,b.right)
return teq(self,other)
def isomorphic(self,other):
def tiso(a,b):
if (not a) and (not b): return True
else: return tiso(a.left,b.left) and tiso(a.right,b.right)
return tiso(self,other)
#operator overloading
def __eq__(self, other):
return self.eq(other)
def __nonzero__(self):
return True
def __mul__(self, a):
'''
mapping:
l * (...)
'''
return self.map(a)
def __rmul__(self, a):
return self * a
def __or__(self, a):
'''
filter:
list | (...)
'''
return self.filter(a)
def __ror__(self,a):
return self | a
def __div__(self, a):
'''
reduce:
self / (...)
'''
return self.reduce(a[0],a[1])
def __rdiv__(self,a):
return self / (a)
def __and__(self,a):
'''
action:
self & (...)
'''
self.action(a)
def __rand__(self,a):
return self & a
def bleaf(val):
return btree(val)
def bnode(val,left,right):
return btree(val,left,right)
def xmap(fun,tree=None):
def __map(tree):
if not tree: return None
if tree.isleaf(): return bleaf( fun(tree.val) )
else:
return bnode( fun(tree.val),
__map(tree.left),
__map(tree.right)
)
if tree: return __map(tree)
else: return __map
def xfilter(fun,tree=None):
def __filter(tree):
if (not tree) or not fun(tree.val): return None
elif tree.isleaf(): return bleaf(tree.val)
else:
return bnode(tree.val,
__filter(tree.left),
__filter(tree.right)
)
if tree: return __filter(tree)
else: return __filter
def xreduce(fun,neutral,tree=None):
def __reduce(tree):
'''
inorder traversing
'''
if not tree: return neutral
if tree.isleaf(): return fun(tree.val,neutral)
else:
lr=__reduce(tree.left)
rr=__reduce(tree.right)
return fun( lr, fun(tree.val, rr))
if tree: return __reduce(tree)
else: return __reduce
def xaction(fun,tree=None):
def __action(tree):
if tree:
__action(tree.left)
fun(tree.val)
__action(tree.right)
if tree: __action(tree)
else: return __action
def xzip(a,b=None,c=None):
def __zip(fun, tree1, tree2):
if (not tree1) or (not tree2): return None
else:
return bnode( fun(tree1.val, tree2.val),
__zip(fun,tree1.left,tree2.left),
__zip(fun,tree1.right,tree2.right)
)
if (ismethod(a) or isfunction(a)) \
and not (b and c): return __zip(a)
elif b and c: return __zip(fun,b,c)
else: return __zip(lambda x,y: (x,y), a, b)
if __name__=='__main__':
hlp=bnode(1,
bnode(2,
bleaf(3),
bleaf(4)
),
bnode(5,
bnode(6,
bleaf(7),
bleaf(8)
),
bleaf(9)
)
)
print hlp
print "depth: ", (hlp.depth())
print "nodes: ", str(hlp.c_nodes())
print "len: ", str(hlp.len())
print "width: ", hlp.width()
print "flatten: ", hlp.flatten()
print "leafs: ", hlp.leafs()
print "map: ", hlp * (lambda a: 2 * a)
print "filter: ", hlp | (lambda a: a % 2 == 1)
print "reduce: ", hlp / (lambda a,b: a + b, 0)
o = hlp | (lambda a: a % 2 == 1)
print "filter->reduce: ", o / (lambda a,b: a + b, 0)
print "depth: ", (o.depth())
print "nodes: ", str(o.c_nodes())
print "map: ", o * (lambda a: 2 * a)
print "zip: ", hlp.zip(o)
print "action: ",
def pfun(p):
print p,
hlp & pfun
print
print "iterator: ",
for i in hlp:
print i,
print
import copy
o=copy.copy(hlp)
print "swap: ", o.swap()
o=copy.deepcopy(hlp)
print "reflect: ", o.reflect()
print
print "leftmost: ", hlp.leftmost()
print "rightmost: ", hlp.rightmost()
print "children: ", hlp.children()
print "grandchildren: ", hlp.grandchildren()
print "level: ", hlp.level(3)
print "o == hlp: ", o == hlp
print "copy(hlp) == hlp: ", hlp == copy.copy(hlp)
o=bnode('a',
bleaf('A'),
bnode('b',
bleaf('B'),
bleaf('C')))
print "rotate start: ",o
o=o.lrotate()
print "lrotate: ", o
o=o.rrotate()
print "rrotate: ", o
o=bnode('a',
bleaf('A'),
bnode('b',
bnode('c',
bleaf('B'),
bleaf('C')
),
bleaf('D')
)
)
print "start dlrotate: ", o
print "dlrotate: ", o.dlrotate()
o=bnode('c',
bnode('a',
bleaf('A'),
bnode('b',
bleaf('B'),
bleaf('C')
)
),
bleaf('D')
)
print "start drrotate: ", o
print "drrotate: ", o.drrotate()
ich hoffe das mit den einrückungen funktioniert soweit
bye