########################################################################
# $Header: /var/local/cvsroot/4Suite/Ft/Rdf/Parsers/Versa/ResourceExpressions.py,v 1.25 2004/09/07 14:17:12 uogbuji Exp $
"""
Implementation and utilities for resource processing Versa

Copyright 2003 Fourthought, Inc. (USA).
Detailed license and copyright information: http://4suite.org/COPYRIGHT
Project home, documentation, distributions: http://4suite.org/
"""

import DataTypes
from Ft.Rdf import RDF_MS_BASE, RDF_SCHEMA_BASE
from Ft.Rdf import OBJECT_TYPE_RESOURCE, OBJECT_TYPE_UNKNOWN
from Ft.Rdf.Drivers import PROPERTIES
from Ft.Xml.XPath import Util

class ResourceExpression:
    """
    Base class for all resource expressions
    """
    pass

class PureQNameExpression(ResourceExpression):
    """
    Expand a QName into a string.  Uses the NsMapping on the context
    """
    def __init__(self,expr):
        self.expr = expr

    def evaluate(self,con):
        res = Util.ExpandQName(self.expr, namespaces=con.nsMapping)
        if res[0] is None:
            return DataTypes.Resource(res[1])
        return DataTypes.Resource(res[0] + res[1])


class LiteralExpression(ResourceExpression):
    """
    Use the resource as is
    """
    def __init__(self, value):
        self.value = value

    def evaluate(self, con):
        return self.value


class CurrentExpression(ResourceExpression):
    """
    Return the current resource if there is one
    """
    def evaluate(self,con):
        return con.current


def GetRelations(start, property, con, inverse, useSubProps=1,
                 forceTransitive=0):
    """
    Returns a dictionary of dictionaries.  The outer dict maps properties
    to relations.  The relation dicts match subjects to objects for each
    property.
    """
    #print "GetRelations"
    property = DataTypes.ToResource(property)
    start = start and DataTypes.ToSet(start) or None
    suspects = con.driver.complete(None, str(property), None, None, con.scope, {})
    if useSubProps:
        subprops = con.getCachedSuperProps().get(property, [])
        for sp in subprops:
            suspects.extend(con.driver.complete(None, str(sp), None, None, con.scope, {}))
    sdict = {}
    #print "GetRelations checkpoint 1"
    if not inverse:
        for s in suspects:
            subj = DataTypes.ToResource(s[0])
            obj = s[5] == OBJECT_TYPE_RESOURCE and DataTypes.ToResource(s[2]) or s[2]
            if not sdict.has_key(subj):
                sdict[subj] = []
            sdict[subj].append(obj)
    else:
        for s in suspects:
            subj = DataTypes.ToResource(s[0])
            obj = s[5] == OBJECT_TYPE_RESOURCE and DataTypes.ToResource(s[2]) or s[2]
            if not sdict.has_key(obj):
                sdict[obj] = []
            sdict[obj].append(subj)

    #print "Raw result dict:", sdict
    #Compute transitive closure
    #print "GetRelations checkpoint 2"
    if forceTransitive or con.isTransitive(property):
        #if forceTransitive:
        #    print property, "treated transitively"
        #else:
        #    print property, "is transitive"
        sdict = TransitiveClosure(sdict)
        #_HandleTransitive(sdict, inverse, con)

    #print "After transitive closure:", sdict
    #Note: in the case of transitives, we have to wait until the end to
    #Cull to start nodes
    #print "GetRelations checkpoint 3"
    if start:
        for k in sdict.keys():
            if not start._d.has_key(k):
                del sdict[k]
    #print "After culling to start nodes:", sdict
    #print "GetRelations end"
    return sdict

def TransitiveClosure(edge_dict):
    """
    edge_dict expresses connectedness in the form:
    { a: [b, f, g], c: [a], d: [f], e: [d], f: [e], g: [c, j],
      h: [g, i], i: [h], j: [k, l, m], l: [g, m], m: [l] }
    Return value is new dict f the same form, but transitivly closed
    """
    #Convert to form for Warshall's algorithm
    #Gather all unique vertices
    vertices = {}
    for k in edge_dict.keys():
        vertices[k] = None
        for i in edge_dict[k]:
            vertices[i] = None
    vertices = vertices.keys()
    #vertices.sort() #Handy for debug
    #print vertices
    vcount = len(vertices)

    adjacency = []
    for v in vertices:
        if edge_dict.has_key(v):
            #Could be more efficient
            adjacency.append([ (i in edge_dict[v]) for i in vertices ])
        else:
            adjacency.append([0] * vcount)

    #print adjacency
    #Run Warshall's
    for i in range(vcount):
        for j in range(vcount):
            if adjacency[j][i]:
                for k in range(vcount):
                    #The j!=k condition is an addition because Warshall's
                    #Assumes connectedness between a vertex and itself, which
                    #Is not always useful in the practical case (e.g. RDF)
                    if adjacency[i][k] and j != k:
                        adjacency[j][k] = 1

    #print adjacency
    #Back to edge dictionary form
#
    new_dict = {}
    for i in range(vcount):
        for j in range(vcount):
            if adjacency[i][j]:
                if not new_dict.has_key(vertices[i]):
                    new_dict[vertices[i]] = []
                new_dict[vertices[i]].append(vertices[j])

    return new_dict
    

def TCTest():
    import string
    for letter in string.ascii_lowercase: exec "%s = '%s'"%(letter, letter)
    closed = TransitiveClosure({a: [b, f, g], c: [a], d: [f], e: [d], f: [e], g: [c, j], h: [g, i], i: [h], j: [k, l, m], l: [g, m], m: [l]})
    return

