python-gadfly 1.0.0-15.1 / usr / share / pyshared / gadfly / kjbuckets0.py

""" kjbuckets in pure python

:Author: Aaron Watters
:Maintainers: http://gadfly.sf.net/
:Copyright: Aaron Robert Watters, 1994
:Id: $Id: kjbuckets0.py,v 1.4 2002/05/11 02:59:05 richard Exp $:
"""

### needs more thorough testing!

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):
            #import sys
            #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 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

#
# $Log: kjbuckets0.py,v $
# Revision 1.4  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.3  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.2  2002/05/07 04:04:02  anthonybaxter
# removing duplicate 'items' call.
#
# Revision 1.1.1.1  2002/05/06 07:31:09  richard
#
#
#