class Database:
    rules = set()
    i = 0
    dirty = True
    rentr = False
    class Symbol:
        def __init__(self, name=None):
            self.name = name
        def __repr__(self):
            if self.name:
                return "<symbol "+str(self.name)+">"
            else:
                return "<symbol "+str(hash(self))+">"
    class TripleDex:
        def __init__(self):
            self.dex = ([],[],[])
            self.greatest = object()
            self.least = object()
        def cmp2(self,a,b):
            def is_number(x):
                if isinstance(x, int):
                    return True
                if isinstance(x, float):
                    return True
                return False

            if a == self.greatest:
                return 1
            if a == self.least:
                return -1

            if b == self.greatest:
                return -1
            if b == self.least:
                return 1
            
            if is_number(a) and isinstance(b,str):
                return -1

            if is_number(b) and isinstance(a,str):
                return 1
            
            if is_number(a) and is_number(b):
                if a > b:
                    return 1
                elif a < b:
                    return -1
                else:
                    return 0

            if isinstance(a,str) and isinstance(b,str):
                if a > b:
                    return 1
                elif a < b:
                    return -1
                else:
                    return 0

            if isinstance(a, tuple) and not isinstance(b, tuple):
                return -1

            if isinstance(b, tuple) and not isinstance(a, tuple):
                return 1

            if isinstance(a, tuple) and isinstance(b, tuple):
                al = len(a)
                bl = len(b)
                cl = max(al,bl)
                for i in range(cl):
                    if i > (al - 1):
                        return -1
                    if i > (bl - 1):
                        return 1
                    if self.cmp2(a[i], b[i]) < 0:
                        return -1
                    if self.cmp2(a[i],b[i]) > 0:
                        return 1
                return 0
            
            print(a, type(a), is_number(a))
            print(b, type(b), is_number(b))
            raise Exception()
        def find(self, prefix):
            L = 0
            R = len(self.dex[0]) - 1
            M = 0
            present = False
            while L <= R:
                M = (L + R) // 2
                x = self.cmp2((self.dex[0][M], self.dex[1][M], self.dex[2][M]), prefix)
                if x < 0:
                    L = M + 1
                elif x > 0:
                    R = M - 1
                else:
                    present = True
                    break
            self.L = L
            self.R = R
            self.M = M
            self.present = present
        def add(self, triple):
            (a,b,c) = triple
            if len(self.dex[0]) == 0:
                self.dex[0].append(a)
                self.dex[1].append(b)
                self.dex[2].append(c)
                return True
            self.find(triple)
            L = self.L
            R = self.R
            M = self.M
            present = self.present
            if not present:
                self.dex[0].insert(L,a)
                self.dex[1].insert(L,b)
                self.dex[2].insert(L,c)
                return True
            return False
        def remove(self, triple):
            self.find(triple)
            L = self.L
            R = self.R
            M = self.M
            present = self.present
            if present:
                self.dex[0].pop(L,a)
                self.dex[1].pop(L,b)
                self.dex[2].pop(L,c)
                return True
            return False
        def slice(self, start, end):
            self.find(start)
            L = self.L
            R = self.R
            M = self.M
            present = self.present
            while L < len(self.dex[0]):
                t = (self.dex[0][L], self.dex[1][L], self.dex[2][L])
                L = L + 1
                c = self.cmp2(t, end)
                if c > 0:
                    break
                yield t
    def __init__(self):
        # EAV
        # AEV
        # AVE
        self.relations2 = (self.TripleDex(),self.TripleDex(),self.TripleDex())
    def nextID(self):
        x = self.i
        self.i = self.i + 1
        return x
    def symbols(self, n):
        return [self.Symbol() for symbol in range(n)]
    def symbol(self, n):
        return self.Symbol(name=n)
    def assert_fact(self, a, b, c):
        assert(not(isinstance(a,self.Symbol)))
        assert(not(isinstance(b,self.Symbol)))
        assert(not(isinstance(c,self.Symbol)))
        #print("assert_fact",a,b,c)
        is_new = self.relations2[0].add((a,b,c))
        self.relations2[1].add((b,a,c))
        self.relations2[2].add((b,c,a))
        self.dirty = is_new or self.dirty
    def fact(self, a, b, c):
        self.assert_fact(a,b,c)
    def query2(self, fact):
        self.quiescence()
        a=isinstance(fact[0], self.Symbol)
        b=isinstance(fact[1], self.Symbol)
        c=isinstance(fact[2], self.Symbol)

        if a and b and c:
            return self.relations2[0].slice((self.relations2[0].least,), (self.relations2[0].greatest,))

        if not(a) and not(b) and not(c):
            return self.relations2[0].slice(fact,fact)

        if not(a) and not(b) and c:
            return self.relations2[0].slice((fact[0],fact[1]),(fact[0],fact[1],self.relations2[0].greatest))

        if not(a) and b and c:
            return self.relations2[0].slice((fact[0],),(fact[0],self.relations2[0].greatest))
        
        if a and not(b) and not(c):
            results = self.relations2[2].slice((fact[1],fact[2]),(fact[1],fact[2],self.relations2[2].greatest))
            return ((x,y,z) for (y,z,x) in results)

        if a and not(b) and c:
            results = self.relations2[2].slice((fact[1],),(fact[1],self.relations2[2].greatest))
            return ((x,y,z) for (y,z,x) in results)

        print(a,b,c)
        raise Exception()
    def query3(self, *clauses):
        def f(clause):
            for fact in self.query2(clause):
                env = {}
                clause1 = self.reify(clause,env)
                if self.unify(clause1, fact, env):
                    yield env
        def g(clause,results):
            for env in results:
                for fact in self.query2(clause):
                    env = dict(env)
                    clause1 = self.reify(clause,env)
                    if self.unify(clause1,fact,env):
                        yield env
        self.quiescence()
        results = None
        for clause in clauses:
            if results is not None:
                results = g(clause,results)
            else:
                results = f(clause)
        return results
    def q(self, *clauses):
        return self.query3(*clauses)
    def rule(self, head, *body):
        self.rules.add((head, body))
        self.dirty = True
    def unify1(self, a, b, env):
        if a == b:
            return True
        if not(isinstance(a, self.Symbol)) and not(isinstance(b, self.Symbol)):
            return a == b
        if isinstance(a, self.Symbol) and a not in env:
            env[a] = b
            return True

        print(a, b, env)
        raise Exception()
    def unify(self,q, w, env):
        (a, b, c) = q
        (x, y, z) = w
        if self.unify1(a,x, env) and self.unify1(b,y,env) and self.unify1(c,z,env):
            return True
        else:
            return False
    def reify(self,triple,env):
        (a, b, c) = triple
        while (a in env) or (b in env) or (c in env):
            if a in env:
                a = env[a]
            if b in env:
                b = env[b]
            if c in env:
                c = env[c]
        return (a, b, c)
    def quiescence(self):
        """Run rules until all facts have been asserted"""
        while self.dirty and not self.rentr:
            self.dirty = False
            self.rentr = True
            for (head, body) in self.rules:
                for env in self.query3(*body):
                    (fst, snd, thd) = self.reify(head, env)
                    self.assert_fact(fst,snd,thd)
            self.rentr = False

db = Database()

xerces_id=db.nextID()
db.fact(xerces_id, "name", "xerces")

brooke_id=db.nextID()
db.fact(brooke_id, "name", "brooke")

damocles_id=db.nextID()
db.fact(damocles_id, "name", "damocles")

db.fact(brooke_id, "parent", xerces_id)
db.fact(damocles_id, "parent", brooke_id)


(W,X,Y,Z) = db.symbols(4)

db.rule((X, "ancestor", Y), (X, "parent", Y))
db.rule((X, "ancestor", Y), (X, "parent", Z), (Z, "ancestor", Y))

# db.quiescence()

print(db.relations2[0].dex)

print("--------------------")
print(list(db.q((X,"ancestor", Y),  (Y, "name", "xerces"))))
# print(len(list(db.q((X,"ancestor", Y), (X, "name", Z)))))
#print(list(db.q((Y, "name", W))))

        

# t = TripleDex()

# t.add((1,2,3))
# t.add((1,2,3))
# t.add((1,3,3))
# t.add((1,1,3))
# t.add((1,3,2))

# print(t.dex[0])
# print(t.dex[1])
# print(t.dex[2])

# print(list(t.slice((1,),(t.greatest,))))

Generated At 2023-03-31T18:41:09-0700 original