# kjbuckets in pure python
### needs more thorough testing!
#import sys # for debug
def kjtabletest(x):
#print "kjtabletest"
try:
return x.is_kjtable
except:
return 0
unhashable = "unhashable key error"
class kjGraph:
is_kjtable = 1
def __init__(self, *args):
#print "kjGraph.__init__", args
key_to_list = self.key_to_list = {}
self.dirty = 0
self.hashed = None
#print args
if args:
if len(args)>1:
raise ValueError, "only 1 or 0 argument supported"
from types import IntType,ListType,TupleType
arg = args[0]
targ = type(arg)
test = key_to_list.has_key
if type(arg) is IntType:
return # ignore int initializer (presize not implemented)
elif type(arg) is ListType or type(arg) is TupleType:
for (x,y) in arg:
if test(x):
key_to_list[x].append(y)
else:
key_to_list[x] = [y]
return
aclass = arg.__class__
if aclass is kjGraph:
aktl = arg.key_to_list
for k in aktl.keys():
key_to_list[k] = aktl[k][:]
return
if aclass is kjDict or aclass is kjSet:
adict = arg.dict
for k in adict.keys():
key_to_list[k] = [ adict[k] ]
return
raise ValueError, "arg for kjGraph must be tuple, list, or kjTable"
def __repr__(self):
return "%s(%s)" % (self.__class__.__name__, self.items())
def _setitems(self, thing):
#print "kjGraph._setitem", thing
#print "setitems", thing
if self.hashed is not None:
raise ValueError, "table has been hashed, it is immutable"
try:
for (k,v) in thing:
#print k,v, "going"
#inlined __setitem__
try:
klist = self.key_to_list[k]
#print "klist gotten"
except KeyError:
try:
klist = self.key_to_list[k] = []
except TypeError:
raise unhashable
if v not in klist:
klist.append(v)
except (TypeError, KeyError):
#print sys.exc_type, sys.exc_value
if kjtabletest(thing):
self._setitems(thing._pairs())
self.dirty = thing.dirty
else: raise ValueError, "cannot setitems with %s" % type(thing)
except unhashable:
raise TypeError, "unhashable type"
def __setitem__(self, item, value):
ktl = self.key_to_list
if ktl.has_key(item):
l = ktl[item]
if value not in l:
l.append(value)
else:
ktl[item] = [value]
def __getitem__(self, item):
return self.key_to_list[item][0]
def __delitem__(self, item):
self.dirty = 1
del self.key_to_list[item]
def choose_key(self):
return self.key_to_list.keys()[0]
def _pairs(self, justtot=0):
myitems = self.key_to_list.items()
tot = 0
for (k, v) in myitems:
tot = tot + len(v)
if justtot: return tot
else:
result = [None]*tot
i = 0
for (k,v) in myitems:
for x in v:
result[i] = (k,x)
i = i+1
return result
def __len__(self):
v = self.key_to_list.values()
lv = map(len, v)
from operator import add
return reduce(add, lv, 0)
def items(self):
return self._pairs()
def values(self):
v = self.key_to_list.values()
from operator import add
tot = reduce(add, map(len, v), 0)
result = [None] * tot
count = 0
for l in v:
next = count + len(l)
result[count:next] = l
count = next
return result
def keys(self):
return self.key_to_list.keys()
def member(self, k, v):
ktl = self.key_to_list
if ktl.has_key(k):
return v in ktl[k]
return 0
_member = member # because member redefined for kjSet
def add(self, k, v):
ktl = self.key_to_list
if ktl.has_key(k):
l = ktl[k]
if v not in l:
l.append(v)
else:
ktl[k] = [v]
def delete_arc(self, k, v):
self.dirty = 1
if self.hashed is not None:
raise ValueError, "table has been hashed, it is immutable"
try:
l = self.key_to_list[k]
i = l.index(v)
del l[i]
if not l:
del self.key_to_list[k]
except:
raise KeyError, "not in table"# % (k,v)
def has_key(self, k):
return self.key_to_list.has_key(k)
def subset(self, other):
oc = other.__class__
if oc is kjGraph:
oktl = other.key_to_list
sktl = self.key_to_list
otest = oktl.has_key
for k in sktl.keys():
if otest(k):
l = sktl[k]
ol = oktl[k]
for x in l:
if x not in ol:
return 0
else:
return 0
return 1
elif oc is kjSet or oc is kjDict:
sktl = self.key_to_list
odict = other.dict
otest = odict.has_key
for k in sktl.keys():
if otest(k):
l = sktl[k]
ov = odict[k]
for x in l:
if ov!=x: return 0
else:
return 0
return 1
def neighbors(self, k):
try:
return self.key_to_list[k][:]
except:
return []
def reachable(self, k):
try:
horizon = self.key_to_list[k]
except:
return kjSet()
else:
if not horizon: return []
d = {}
for x in horizon: d[x] = 1
done = 0
while horizon:
newhorizon = []
for n in horizon:
for n2 in self.neighbors(n):
if not d.has_key(n2):
newhorizon.append(n2)
d[n2] = 1
horizon = newhorizon
return kjSet(d.keys())
def items(self):
return self._pairs()
# ????
def ident(self):
result = kjDict(self)
result.dirty = self.dirty or result.dirty
return result
def tclosure(self):
# quick and dirty
try:
raise self
except (kjSet, kjDict):
raise ValueError, "tclosure only defined on graphs"
except kjGraph:
pass
except:
raise ValueError, "tclosure only defined on graphs"
result = kjGraph(self)
result.dirty = self.dirty
addit = result.add
while 1:
#print result
more = result*result
if more.subset(result):
return result
for (x,y) in more.items():
addit(x,y)
def Clean(self):
if self.dirty: return None
return self
def Wash(self):
self.dirty = 0
def Soil(self):
self.dirty = 1
def remap(self, X):
# really only should be defined for kjdict, but whatever
return kjDict(X*self).Clean()
def dump(self, seq):
result = map(None, seq)
for i in range(len(result)):
result[i] = self[result[i]]
if len(seq) == 1:
return result[0]
return tuple(result)
def __hash__(self): # should test better
"""in conformance with kjbuckets, permit unhashable keys"""
if self.hashed is not None:
return self.hashed
items = self._pairs()
for i in xrange(len(items)):
(a,b) = items[i]
try:
b = hash(b)
except:
b = 1877777
items[i] = hash(a)^~b
items.sort()
result = self.hashed = hash(tuple(items))
return result
def __cmp__(self, other):
#print "kjGraph.__cmp__"
ls = len(self)
lo = len(other)
test = cmp(ls, lo)
if test:
return test
si = self._pairs()
oi = other._pairs()
si.sort()
oi.sort()
return cmp(si, oi)
def __nonzero__(self):
if self.key_to_list: return 1
return 0
def __add__(self, other):
result = kjGraph(self)
rktl = result.key_to_list
rtest = rktl.has_key
result.dirty = self.dirty or other.dirty
oc = other.__class__
if oc is kjGraph:
oktl = other.key_to_list
for k in oktl.keys():
l = oktl[k]
if rtest(k):
rl = rktl[k]
for x in l:
if x not in rl:
rl.append(x)
else:
rktl[k] = l[:]
elif oc is kjSet or oc is kjDict:
odict = other.dict
for k in odict.keys():
ov = odict[k]
if rtest(k):
rl = rktl[k]
if ov not in rl:
rl.append(ov)
else:
rktl[k] = [ov]
else:
raise ValueError, "kjGraph adds only with kjTable"
return result
__or__ = __add__
def __sub__(self, other):
result = kjGraph()
rktl = result.key_to_list
sktl = self.key_to_list
oc = other.__class__
if oc is kjGraph:
oktl = other.key_to_list
otest = oktl.has_key
for k in sktl.keys():
l = sktl[k][:]
if otest(k):
ol = oktl[k]
for x in ol:
if x in l:
l.remove(x)
if l:
rktl[k] = l
else:
rktl[k] = l
elif oc is kjSet or oc is kjDict:
odict = other.dict
otest = odict.has_key
for k in sktl.keys():
l = sktl[k][:]
if otest(k):
ov = odict[k]
if ov in l:
l.remove(ov)
if l:
rktl[k] = l
else:
raise ValueError, "kjGraph diffs only with kjTable"
return result
def __mul__(self, other):
result = kjGraph()
rktl = result.key_to_list
sktl = self.key_to_list
oc = other.__class__
if oc is kjGraph:
oktl = other.key_to_list
otest = other.has_key
for sk in sktl.keys():
sklist = []
for sv in sktl[sk]:
if otest(sv):
sklist[0:0] = oktl[sv]
if sklist:
rktl[sk] = sklist
elif oc is kjSet or oc is kjDict:
odict = other.dict
otest = odict.has_key
for sk in sktl.keys():
sklist=[]
for sv in sktl[sk]:
if otest(sv):
sklist.append(odict[sv])
if sklist:
rktl[sk] = sklist
else:
raise ValueError, "kjGraph composes only with kjTable"
return result
def __invert__(self):
result = self.__class__()
pairs = self._pairs()
for i in xrange(len(pairs)):
(k,v) = pairs[i]
pairs[i] = (v,k)
result._setitems(pairs)
result.dirty = self.dirty or result.dirty
return result
def __and__(self, other):
sktl = self.key_to_list
oc = other.__class__
if oc is kjGraph:
result = kjGraph()
rktl = result.key_to_list
oktl = other.key_to_list
otest = oktl.has_key
for k in self.keys():
if otest(k):
l = sktl[k]
ol = oktl[k]
rl = []
for x in l:
if x in ol:
rl.append(x)
if rl:
rktl[k] = rl
elif oc is kjSet or oc is kjDict:
result = oc() # less general!
rdict = result.dict
odict = other.dict
stest = sktl.has_key
for k in odict.keys():
if stest(k):
v = odict[k]
l = sktl[k]
if v in l:
rdict[k] = v
else:
raise ValueError, "kjGraph intersects only with kjTable"
result.dirty = self.dirty or other.dirty
return result
def __coerce__(self, other):
return (self, other) # ?is this sufficient?
class kjDict(kjGraph):
def __init__(self, *args):
#print "kjDict.__init__", args
self.hashed = None
dict = self.dict = {}
self.dirty = 0
if not args: return
if len(args)==1:
from types import TupleType,ListType,IntType
arg0 = args[0]
targ0 = type(arg0)
if targ0 is IntType: return
if targ0 is ListType or targ0 is TupleType:
otest = dict.has_key
for (a,b) in arg0:
if otest(a):
if dict[a]!=b:
self.dirty = 1
dict[a] = b
return
argc = arg0.__class__
if argc is kjGraph:
ktl = arg0.key_to_list
for k in ktl.keys():
l = ktl[k]
if len(l)>1: self.dirty=1
for v in l:
dict[k] = v
return
if argc is kjSet or argc is kjDict:
adict = arg0.dict
for (k,v) in adict.items():
dict[k]=v
return
raise ValueError, "kjDict initializes only from list, tuple, kjTable, or int"
def _setitems(self, thing):
#print "kjDict._setitem", thing
if self.hashed is not None:
raise KeyError, "table hashed, cannot modify"
dict = self.dict
try:
for (k,v) in thing:
if dict.has_key(k) and dict[k]!=v:
self.dirty = 1
dict[k] = v
except:
self._setitems(thing._pairs()) # maybe too tricky!
def dump(self, dumper):
ld = len(dumper)
if ld==1:
return self.dict[dumper[0]]
else:
sdict = self.dict
result = [None] * ld
for i in xrange(ld):
result[i] = sdict[ dumper[i] ]
return tuple(result)
def __setitem__(self, item, value):
if self.hashed is not None:
raise ValueError, "table has been hashed, it is immutable"
d = self.dict
if d.has_key(item):
if d[item]!=value:
self.dirty = 1
self.dict[item]=value
def __getitem__(self, item):
return self.dict[item]
def __delitem__(self, item):
if self.hashed is not None:
raise ValueError, "table has been hashed, it is immutable"
self.dirty = 1
del self.dict[item]
def choose_key(self):
return self.dict.keys()[0]
def __len__(self):
return len(self.dict)
def _pairs(self, justtot=0):
if justtot: return len(self.dict)
return self.dict.items()
def values(self):
return self.dict.values()
def keys(self):
return self.dict.keys()
def items(self):
return self.dict.items()
def remap(self, X):
if X.__class__ is kjGraph:
if self.dirty or X.dirty: return None
result = kjDict()
resultd = result.dict
selfd = self.dict
inself = selfd.has_key
inresult = resultd.has_key
ktl = X.key_to_list
for k in ktl.keys():
for v in ktl[k]:
if inself(v):
map = selfd[v]
if inresult(k):
if resultd[k]!=map:
return None
else:
resultd[k]=map
return result
else:
return (kjDict(X*self)).Clean()
def __cmp__(s,o):
from types import InstanceType
if type(o) is not InstanceType:
return -1
oc = o.__class__
if oc is kjDict or oc is kjSet:
return cmp(s.dict, o.dict)
return kjGraph.__cmp__(s, o)
def __hash__(s):
h = s.hashed
if h is not None: return h
return kjGraph.__hash__(s)
def __add__(s,o):
oc = o.__class__
if oc is kjDict or oc is kjSet:
result = kjDict()
result.dirty = s.dirty or o.dirty
rdict = result.dict
rtest = result.has_key
sdict = s.dict
for k in sdict.keys():
rdict[k] = sdict[k]
odict = o.dict
for k in odict.keys():
if rtest(k):
if rdict[k]!=odict[k]:
result.dirty=1
else:
rdict[k] = odict[k]
return result
if oc is kjGraph:
return kjGraph.__add__(o,s)
else:
raise ValueError, "kjDict unions only with kjTable"
__or__ = __add__
def __and__(s,o):
oc = o.__class__
if oc is kjDict or oc is kjSet:
result = oc()
result.dirty = s.dirty or o.dirty
rdict = result.dict
odict = o.dict
sdict = s.dict
stest = sdict.has_key
for k in odict.keys():
v = odict[k]
if stest(k) and sdict[k]==v:
rdict[k] = v
return result
elif oc is kjGraph:
return kjGraph.__and__(o,s)
def __sub__(s,o):
oc = o.__class__
result = kjDict()
result.dirty = s.dirty or o.dirty
sdict = s.dict
rdict = result.dict
if oc is kjDict:
odict = o.dict
otest = odict.has_key
for k in sdict.keys():
v = sdict[k]
if otest(k):
if odict[k]!=v:
rdict[k] = v
else:
rdict[k] = v
return result
if oc is kjGraph:
oktl = o.key_to_list
otest = oktl.has_key
for k in sdict.keys():
v = sdict[k]
if otest(k):
if v not in oktl[k]:
rdict[k] = v
else:
rdict[k] = v
return result
raise ValueError, "kjDict only diffs with kjGraph, kjDict"
def __mul__(s,o):
oc = o.__class__
sdict = s.dict
if oc is kjDict or oc is kjSet:
result = kjDict()
result.dirty = s.dirty or o.dirty
rdict = result.dict
odict = o.dict
otest = odict.has_key
for k in sdict.keys():
kv = sdict[k]
if otest(kv):
rdict[k] = odict[kv]
return result
elif oc is kjGraph:
return kjGraph(s) * o
else:
raise ValueError, "kjDict only composes with kjTable"
def member(self, k, v):
d = self.dict
try:
return d[k] == v
except:
return 0
_member = member
def delete_arc(self, k, v):
if self.dict[k] == v:
del self.dict[k]
else:
raise KeyError, "pair not in table"
def has_key(self, k):
return self.dict.has_key(k)
def neighbors(self, k):
try:
return [ self.dict[k] ]
except: return []
def reachable(self, k):
result = {}
d = self.dict
try:
while 1:
next = d[k]
if result.has_key(next): break
result[next] = 1
k = next
except KeyError:
pass
return kjSet(result.keys())
def __invert__(self):
result = kjDict()
dr = result.dict
drtest = dr.has_key
ds = self.dict
for (a,b) in ds.items():
if drtest(b):
result.dirty=1
dr[b]=a
result.dirty = self.dirty or result.dirty
return result
def __nonzero__(self):
if self.dict: return 1
return 0
def subset(s, o):
oc = o.__class__
sdict = s.dict
if oc is kjDict or oc is kjSet:
odict = o.dict
otest = odict.has_key
for k in sdict.keys():
v = sdict[k]
if otest(k):
if odict[k]!=v:
return 0
else:
return 0
elif oc is kjGraph:
oktl = o.key_to_list
otest = oktl.has_key
for k in sdict.keys():
v = sdict[k]
if otest(k):
if v not in oktl[k]:
return 0
else:
return 0
else:
raise ValueError, "kjDict subset test only for kjTable"
return 1
def add(s, k, v):
if s.hashed is not None:
raise ValueError, "table has been hashed, immutable"
sdict = s.dict
if sdict.has_key(k):
if sdict[k]!=v:
s.dirty = 1
sdict[k] = v
class kjSet(kjDict):
def __init__(self, *args):
#print "kjSet.__init__", args
# usual cases first
dict = self.dict = {}
self.hashed = None
self.dirty = 0
largs = len(args)
if largs<1: return
if largs>1:
raise ValueError, "at most one argument supported"
from types import IntType,TupleType,ListType
arg0 = args[0]
targ0 = type(arg0)
if targ0 is IntType: return
if targ0 is TupleType or targ0 is ListType:
for x in arg0:
dict[x] = x
return
argc = arg0.__class__
if argc is kjDict or argc is kjSet:
stuff = arg0.dict.keys()
elif argc is kjGraph:
stuff = arg0.key_to_list.keys()
else:
raise ValueError, "kjSet from kjTable, int, list, tuple only"
for x in stuff:
dict[x] = x
def __add__(s,o):
oc = o.__class__
if oc is kjSet:
result = kjSet()
result.dirty = s.dirty or o.dirty
rdict = result.dict
for x in s.dict.keys():
rdict[x]=x
for x in o.dict.keys():
rdict[x]=x
return result
elif oc is kjDict:
return kjDict.__add__(o,s)
elif oc is kjGraph:
return kjGraph.__add__(o,s)
__or__ = __add__
def __sub__(s,o):
if o.__class__ is kjSet:
result = kjSet()
result.dirty = s.dirty or o.dirty
rdict = result.dict
otest = o.dict.has_key
for x in s.dict.keys():
if not otest(x):
rdict[x] = x
return result
else:
return kjDict.__sub__(s,o)
def __and__(s,o):
oc = o.__class__
if oc is kjSet or oc is kjDict:
result = kjSet()
result.dirty = s.dirty or o.dirty
rdict = result.dict
odict = o.dict
otest = odict.has_key
for x in s.dict.keys():
if otest(x) and odict[x]==x:
rdict[x] = x
return result
elif oc is kjGraph:
return kjGraph.__and__(o,s)
raise ValueError, "kjSet only intersects with kjTable"
# illegal methods
values = keys = remap = None
def __repr__(self):
return "kjSet(%s)" % self.items()
def _setelts(self, items):
#print "kjSet.setelts", items
try:
items = items._pairs()
except:
items = list(items)
for i in xrange(len(items)):
items[i] = (items[i], items[i])
self._setitems(items)
else:
items = list(items)
for i in xrange(len(items)):
items[i] = (items[i][0], items[i][0])
self._setitems(items)
# hack!
#D = self.dict
#for x in D.keys():
# D[x] = x
def _pairs(self, justtot=0):
if justtot: return kjDict._pairs(self, justtot=1)
pairs = kjDict.keys(self)
for i in xrange(len(pairs)):
pairs[i] = (pairs[i], pairs[i])
return pairs
member = kjDict.has_key
items = kjDict.keys
#def neighbors(self, x):
# raise ValueError, "operation on kjSet undefined"
#reachable = neighbors
def __getitem__(self, item):
test = self.dict.has_key(item)
if test: return 1
raise KeyError, "item not in set"
def __setitem__(self, item, ignore):
d = self.dict
if self.hashed:
raise ValueError, "table hashed, immutable"
d[item] = item
def add(self, elt):
if self.hashed:
raise ValueError, "table hashed, immutable"
self.dict[elt] = elt
def __mul__(s,o):
oc = o.__class__
if oc is kjSet:
return s.__and__(o)
else:
return kjDict.__mul__(s, o)
def more_general(t1, t2):
try:
raise t1
except kjSet:
try:
raise t2
except (kjGraph, kjDict, kjSet):
return t2.__class__
except kjDict:
try:
raise t2
except kjSet:
return t1.__class__
except (kjDict, kjGraph):
return t2.__class__
except kjGraph:
return t1.__class__
except:
raise ValueError, "cannot coerce, not kjtable"
def less_general(t1,t2):
try:
raise t1
except kjSet:
return t1.__class__
except kjDict:
try:
raise t2
except kjSet:
return t2.__class__
except (kjDict, kjGraph):
return t1.__class__
except kjGraph:
return t2.__class__
except:
raise ValueError, "cannot coerce, not kjtable"
def kjUndump(t1, t2):
result = kjDict()
rdict = result.dict
lt1 = len(t1)
if lt1 == 1:
rdict[t1[0]] = t2
else:
# tightly bound to implementation
for i in xrange(lt1):
rdict[t1[i]] = t2[i]
return result
def test():
global S, D, G
G = kjGraph()
r3 = range(3)
r = map(None, r3, r3)
for i in range(3):
G[i] = i+1
D = kjDict(G)
D[9]=0
G[0]=10
S = kjSet(G)
S[-1] = 5
print "%s.remap(%s) = %s" % (D, G, D.remap(G))
print "init test"
for X in (S, D, G, r, tuple(r), 1):
print "ARG", X
for C in (kjGraph, kjSet, kjDict):
print "AS", C
T = C(X)
T2 = C()
print X, T, T2
ALL = (S, D, G)
for X in ALL:
print "X=", X
print "key", X.choose_key()
print "len", len(X)
print "items", X.items()
print X, "Clean before", X.Clean()
del X[2]
print X, "Clean after", X.Clean()
if not X.subset(X):
raise "trivial subset fails", X
if not X==X:
raise "trivial cmp fails", X
if not X:
raise "nonzero fails", X
if X is S:
if not S.member(0):
raise "huh 1?"
if S.member(123):
raise "huh 2?", S
S.add(999)
del S[1]
if not S.has_key(999):
raise "huh 3?", S
else:
print "values", X.values()
print "keys", X.keys()
print X, "inverted", ~X
if not X.member(0,1):
raise "member test fails (0,1)", X
print "adding to", X
X.add(999,888)
print "added", X
X.delete_arc(999,888)
print "deleted", X
if X.member(999,888):
raise "member test fails (999,888)", X
if X.has_key(999):
raise "has_key fails 999", X
if not X.has_key(0):
raise "has_key fails 0", X
for Y in ALL:
print "Y", Y
if (X!=S and Y!=S):
print "diff", X, Y
print "%s-%s=%s" % (X,Y,X-Y)
elif X==S:
D = kjSet(Y)
print "diff", X, D
print "%s-%s=%s" % (X,D,X-D)
print "%s+%s=%s" % (X,Y,X+Y)
print "%s&%s=%s" % (X,Y,X&Y)
print "%s*%s=%s" % (X,Y,X*Y)
x,y = cmp(X,Y), cmp(Y,X)
if x!=-y: raise "bad cmp!", (X, Y)
print "cmp(X,Y), -cmp(Y,X)", x,-y
print "X.subset(Y)", X.subset(Y)
|