#! /usr/bin/env python
# ______________________________________________________________________
"""Module ANOITrie.py
Jonathan Riehl
$Id: ANOITrie.py,v 1.11 2005/01/21 00:28:05 jriehl Exp $
"""
# ______________________________________________________________________
# Module imports
import types
import ANOIBaseSpace
import ANOITypes
# ______________________________________________________________________
# Module data
__DEBUG__ = False
if __DEBUG__:
import ANOIUtil
# ______________________________________________________________________
# Class definitions
class ANOITrieError (ANOIBaseSpace.ANOIException):
pass
# ______________________________________________________________________
class ANOISimpleTrie (object):
"""Class ANOISimpleTrie
Basically a string dictionary. The namespace is encoded as a trie,
hanging off the root UID. Namespace lookup is handled by converting
a string into a vector of UID's, which are then crossed with each other.
The root UID doubles as a reference pointer to the contained value, (this
allows substrings of keys to map to values as well).
getName('abcd') = (((((ROOT x a) x b) x c) x d) x REF)
setName('abc', 1011) => ((((ROOT x a) x b) x c) x REF) = 1011
(Where REF = ROOT for ANOISimpleTrie)
This was created with the intention of being the preferred way to encode
properties in a space (as demonstrated in ANOITrie).
"""
# ____________________________________________________________
def __init__ (self, space, root):
"""ANOISimpleTrie.__init__()
"""
self.space = space
self.root = root
self.ref = root
# ____________________________________________________________
def getVectors (self, crntUid = None, crntVec = None, visited = None,
result = None):
"""ANOISimpleTrie.getVectors()
Return a dictionary of vectors in the trie. This should be
overloaded by child classes since this implementation will chase type
and parent links.
"""
if __DEBUG__:
print "ANOISimpleTrie.getVectors():", crntUid, crntVec
if crntUid == None:
crntUid = self.root
if crntVec == None:
crntVec = [crntUid]
if visited == None:
visited = []
if result == None:
result = {}
assert crntUid not in visited, ("You should know better than "
"to run this method on a trie"
" that has circular edges!")
visited.append(crntUid)
keyUidList = self.space.getUidKeys(crntUid)
for keyUid in keyUidList:
if keyUid == self.ref:
referencedUid = self.space.cross(crntUid, keyUid)
if referencedUid != ANOIBaseSpace.NIL:
result[tuple(crntVec[1:])] = referencedUid
else:
nextUid = self.space.cross(crntUid, keyUid)
crntVec.append(keyUid)
self.getVectors(nextUid, crntVec, visited, result)
del crntVec[-1]
return result
# ____________________________________________________________
def getVector (self, vec):
"""ANOISimpleTrie.getVector()
"""
vec = vec[:]
vec.insert(0, self.root)
vec.append(self.ref)
return self.space.getVector(vec)
# ____________________________________________________________
def setVector (self, vec, uid):
"""ANOISimpleTrie.setVector()
"""
vec = vec[:]
vec.insert(0, self.root)
vec.append(self.ref)
return self.space.setVector(vec, uid, self.createTrieNode)
# ____________________________________________________________
def hasName (self, name):
"""ANOISimpleTrie.hasName()
"""
return self.getName(name) != ANOIBaseSpace.NIL
# ____________________________________________________________
def getName (self, name):
"""ANOISimpleTrie.getName()
"""
retVal = self.getVector(map(ord, list(name)))
if __DEBUG__:
print self, "ANOISimpleTrie.getName('%s') = %d" % (name, retVal)
return retVal
# ____________________________________________________________
def setName (self, name, uid):
"""ANOISimpleTrie.setName()
"""
if __DEBUG__:
print self, "ANOISimpleTrie.setName('%s', %d)" % (name, uid)
return self.setVector(map(ord, list(name)), uid)
# ____________________________________________________________
def createTrieNode (self, space, prevUid, keyUid):
"""ANOISimpleTrie.createTrieNode()
"""
retVal = space.getUid()
space.crossEquals(prevUid, keyUid, retVal)
if __DEBUG__:
print "ANOISimpleTrie.createTrieNode():", prevUid, "x", keyUid,
print "=", retVal
return retVal
# ______________________________________________________________________
class ANOITrie (ANOISimpleTrie):
"""Class ANOITrie
"""
# ____________________________________________________________
def __init__ (self, space, root, baseTrie = None):
"""ANOITrie.__init__()
So there is some circular foo going on here. ANOITrie will need to
register with the type system, but the type system will need a trie
to set itself up. So the first step is to get provisional property
keys, then initialize the type system, then register the provisional
property keys with the type system.
"""
assert type(root) == types.IntType
self.space = space
self.root = root
if baseTrie == None:
self.baseTrie = self
# See if we need a base trie to get going.
self.ref = root
refUid = self.getName("REF")
if refUid != ANOIBaseSpace.NIL:
# A bootstrap REF was found, ignore the baseTrie
self.ref = refUid
# Ensure trie was properly bootstrapped.
assert self.getName("REF") == self.ref
self.typeUid = self.getName("ANOITrieType")
self.parent = self.getName("PARENT")
else:
# We need to bootstrap; create a simple trie, initialize
# a type system internal to the simple trie, then copy
# it.
bootTrieUid = self.space.getUid()
bootTrieObj = ANOISimpleTrie(self.space, bootTrieUid)
bootTypeSystem = ANOITypes.ANOITypeManager(space, bootTrieObj)
self.ref = bootTypeSystem.createPropertyKey("REF")
self.parent = bootTypeSystem.createPropertyKey("PARENT")
slots = {self.ref : bootTypeSystem.atomType,
self.parent : None}
self.typeUid = bootTypeSystem.createType("ANOITrieType",
slots)
self.typeSystem = bootTypeSystem
self.copySimpleTrie(bootTrieObj)
refVec = map(ord, list("REF"))
refVec.insert(0, self.root)
refVec.append(self.root) # Bootstrap REF
if __DEBUG__:
print "ANOITrie.__init__(): refVec =", refVec
self.space.setVector(refVec, self.ref)
else:
self.baseTrie = baseTrie
self.typeUid = baseTrie.getName("ANOITrieType")
self.ref = baseTrie.getName("REF")
self.parent = baseTrie.getName("PARENT")
self.typeSystem = ANOITypes.ANOITypeManager(space, self.baseTrie)
# Now coerrce myself into being properly typed.
myTypeUid = space.cross(self.root, self.typeSystem.typeAttr)
if myTypeUid == ANOIBaseSpace.NIL:
space.crossEquals(self.root, self.typeSystem.typeAttr,
self.typeUid)
space.crossEquals(self.root, self.ref, ANOIBaseSpace.NIL)
space.crossEquals(self.root, self.parent, ANOIBaseSpace.NIL)
else:
assert myTypeUid == self.typeUid
# ____________________________________________________________
def copySimpleTrie (self, simpleTrieObj):
"""ANOITrie.copySimpleTrie()
"""
if __DEBUG__:
print "ANOITrie.copySimpleTrie():", simpleTrieObj
simpleTrieDict = simpleTrieObj.getVectors()
for key, value in simpleTrieDict.items():
if __DEBUG__:
print `ANOIUtil.uidVecToStr(key)`, "=>", value
self.setVector(list(key), value)
# ____________________________________________________________
def getNameOrCreate (self, name):
"""ANOITrie.getNameOrCreate()
Should only be used for bootstrap
"""
retVal = self.getName(name)
if retVal == ANOIBaseSpace.NIL:
retVal = self.space.getUid()
self.setName(name, retVal)
return retVal
# ____________________________________________________________
def createTrieNode (self, space, prevUid, keyUid):
"""ANOITrie.createTrieNode()
"""
if __DEBUG__:
print self, "createTrieNode(..., %d, %d)" % (prevUid, keyUid)
assert space == self.space
retVal = self.typeSystem.createInstance(self.typeUid)
self.space.crossEquals(retVal, self.ref, ANOIBaseSpace.NIL)
self.space.crossEquals(retVal, self.parent, prevUid)
self.space.crossEquals(prevUid, keyUid, retVal)
return retVal
# ____________________________________________________________
def getVectors (self, crntUid = None, crntVec = None, visited = None,
result = None):
"""ANOITrie.getVectors()
"""
retVal = {}
if __DEBUG__:
print "ANOITrie.getVectors():", crntUid, crntVec
if crntUid == None:
crntUid = self.root
if crntVec == None:
crntVec = [crntUid]
if visited == None:
visited = []
if result == None:
result = {}
if crntUid in visited:
if __DEBUG__:
print "ANOITrie.getVectors(): Warning! Circular trie key!"
print "\t", crntUid, crntVec, visited
else:
visited.append(crntUid)
keyUidList = self.space.getUidKeys(crntUid)
for keyUid in keyUidList:
if keyUid == self.ref:
referencedUid = self.space.cross(crntUid, keyUid)
if referencedUid != ANOIBaseSpace.NIL:
result[tuple(crntVec[1:])] = referencedUid
else:
nextUid = self.space.cross(crntUid, keyUid)
if self.typeSystem.getType(nextUid) == self.typeUid:
crntVec.append(keyUid)
self.getVectors(nextUid, crntVec, visited, result)
del crntVec[-1]
return result
# ____________________________________________________________
def compressVector (self, uidVec):
"""ANOITrie.compressVector()
"""
retVal = []
cross = self.space.cross
NIL = ANOIBaseSpace.NIL
i = 0
uidVecLen = len(uidVec)
while i < uidVecLen:
crntUid = cross(self.root, uidVec[i])
lastGoodRef = NIL
lastGoodPos = i
j = i + 1
# At loop entry, b/c i < uidVecLen, j = i + 1 <= uidVecLen
# To avoid redundant comparisons, the uidVecLen guard is handled
# below, using break.
while (NIL != crntUid):
crntRef = cross(crntUid, self.ref)
if NIL != crntRef:
lastGoodRef = crntRef
lastGoodPos = j
if j < uidVecLen:
crntUid = cross(crntUid, uidVec[j])
else:
break
j = j + 1
if lastGoodRef == NIL:
retVal.append(uidVec[i])
i = i + 1
else:
retVal.append(lastGoodRef)
i = lastGoodPos
return retVal
# ______________________________________________________________________
def getNamespace (space, rootNS):
retVal = None
rootNSType = type(rootNS)
if rootNSType == types.IntType:
retVal = ANOITrie(space, rootNS)
else:
assert rootNSType in (ANOISimpleTrie, ANOITrie)
retVal = rootNS
return retVal
# ______________________________________________________________________
# End of ANOITrie.py
