import Data.List 


infixl 5 `Or`
infixl 6 `And`

data Expr = Top 
          | Atomic String 
          | Not Expr 
          | Expr `And` Expr 
          | Expr `Or` Expr
          | Exists String Expr 
          | All String Expr 
          | AtLeast Int String
          | AtMost Int String 
          deriving (Eq, Ord, Show)

data Tableau = Tableau { nodes :: [Node], 
                         edges :: [Edge], 
                         topExpr :: Expr,
                         nextId :: Id, 
                         diffs :: [(Id,Id)]
                       } deriving (Eq, Show)

type Id = Int

data Node = Node { nid :: Id, 
                   exprs :: [Expr]
                 } deriving (Eq, Ord, Show)

data Edge = Edge { parentId :: Id, 
                   role :: String, 
                   childId :: Id
                 } deriving (Eq, Ord, Show)




nnf :: Expr -> Expr
nnf (Not (Not e)) = nnf e
nnf (Not (e1 `And` e2)) = (nnf (Not e1)) `Or`  (nnf (Not e2))
nnf (Not (e1 `Or`  e2)) = (nnf (Not e1)) `And` (nnf (Not e2))
nnf (Not (Exists r e))  = All r (nnf (Not e))
nnf (Not (All r e))     = Exists r (nnf (Not e))
nnf (Not (AtMost n r))  = AtLeast (n+1) r
nnf (Not (AtLeast n r)) = AtMost (n-1) r
nnf (e1 `And` e2) = nnf e1 `And` nnf e2
nnf (e1 `Or` e2)  = nnf e1 `Or` nnf e2
nnf (Exists r e)  = Exists r (nnf e)
nnf (All r e)     = All r (nnf e)
nnf e = e




infixl 4 `Implies`
data Axiom = Expr `Implies` Expr

formExpr :: Axiom -> Expr
formExpr (Top `Implies` e) = e
formExpr (e1 `Implies` e2) = Not e1 `Or` e2

tboxFormula :: [Axiom] -> Expr
tboxFormula [] = Top
tboxFormula axioms = nnf (foldl1 op concepts)
      where op e1 e2 = e1 `And` e2
            concepts = map formExpr axioms

initTableau :: Expr -> Expr -> [Tableau]
initTableau c tbox = [Tableau [n] [] ntbox 1 []]
    where n = Node 0 [nnf c `And` ntbox]
          ntbox = nnf tbox

models :: Expr -> [Axiom] -> [Tableau]
models c tbox = tableau$initTableau c (tboxFormula tbox)

satisfiable :: Expr -> [Axiom] -> Bool
satisfiable c tbox = not$null (models c tbox)

subsumes :: Expr -> Expr -> [Axiom] -> Bool
subsumes c1 c2 tbox = not$satisfiable (Not c1 `And` c2) tbox

equivalent :: Expr -> Expr -> [Axiom] -> Bool
equivalent c1 c2 tbox = (subsumes c1 c2 tbox) 
                     && (subsumes c2 c1 tbox)

disjoint :: Expr -> Expr -> [Axiom] -> Bool
disjoint c1 c2 tbox = not$satisfiable (c1 `And` c2) tbox

consistent :: [Axiom] -> Bool
consistent tbox = satisfiable Top tbox






type TableauTransform = Tableau -> [Tableau]

tableau :: [Tableau] -> [Tableau]
tableau ts = applyTransforms transforms ts
 where applyTransforms _ [] = []
       applyTransforms [] (t:ts) = t:tableau ts
       applyTransforms (f:fs) (t:ts) = 
                       if c then tableau ts'
                       else applyTransforms fs ts'
           where (c,ts') = apply f t ts
       transforms = [clash,applyAnd,applyAll,applyAtMost,
                     applyOr,applyExists,applyAtLeast]

apply :: TableauTransform -> Tableau -> [Tableau] -> (Bool,[Tableau])
apply f t ts = (changed ns,ns ++ ts)
    where ns = f t
          changed [t'] = t /= t'
          changed _ = True

clash :: TableauTransform
clash t = if any check (nodes t) then [] else [t]

check :: Node -> Bool
check n = elem (Not Top) es 
          || any checkPair [(e1,e2) | (e1:t) <- tails es, e2 <- t]
    where es = exprs n
          checkPair (a,Not b) = a == b
          checkPair (Not b,a) = a == b
          checkPair (AtLeast l r1,AtMost m r2) = r1 == r2 && l > m
          checkPair (AtMost m r1,AtLeast l r2) = r1 == r2 && l > m
          checkPair _ = False

applyAnd :: TableauTransform
applyAnd t = [t {nodes = map andRule (nodes t)}]

andRule :: Node -> Node
andRule n = n {exprs = usort (andRule' es es)}
    where es = exprs n
          andRule' [] es = es
          andRule' (e:es) es' = andRule' (l ++ es) (l ++ es')
              where l = andRuleBase e
                    andRuleBase (lhs `And` rhs) = [lhs,rhs]
                    andRuleBase _ = []

unique :: Eq a => [a] -> [a]
unique (x:y:l) = if x == y then unique (y:l) else x:unique (y:l)
unique l = l


usort :: Ord a => [a] -> [a]
usort = unique . sort

applyAll :: TableauTransform
applyAll t = [t {nodes = allRule (nodes t) (edges t)}]

allRule :: [Node] -> [Edge] -> [Node]
allRule nodes edges = if null toDo 
                      then nodes 
                      else allRule nodes' edges
 where toDo = [x | e <- edges, p <- nodes, 
                   parentNode p e, x <- needAll e p]
       parentNode p e = nid p == parentId e
       needAll e p = [(nid n,consequence c) | 
                      c <- exprs p, match e c,
                      n <- nodes, nid n == childId e,
                      consequence c `notElem` exprs n]
       match e (All rname _) = rname == role e
       match _ _ = False
       consequence (All _ expr) = expr
       nodes' = foldl op nodes toDo
       op nodes x = map (f x) nodes
       f (xid,expr) n = if nid n == xid 
                        then n {exprs = expr:exprs n} else n

colourings :: Int -> [Int] -> [(Int,Int)] -> [[[Int]]]
colourings l vs es = map first (equiv vs [([],l,length vs)])
    where first (a,_,_) = a
          equiv [] states = states
          equiv (v:vs) states = 
                   equiv vs [state' | state <- states,
                                      state' <- f state
                            ]
              where f (cs,ac,av) = 
                         if (av<ac) then []
                         else if (av==ac) then  [ncs]
                         else if (ac>0) then ncs:rcss 
                         else rcss
                       where ncs = ([v]:cs,ac-1,av-1)
                             rcss = foldl ins [] (select cs)
                             ins rcss (c,cs) = 
                                   if noEdge v c
                                   then ((v:c):cs,ac,av-1):rcss
                                   else rcss
          noEdge v c = all noEdge' c
              where noEdge' w = 
                      notElem (if v < w then (v,w) else (w,v)) es

select :: [a] -> [(a,[a])]
select [] = []
select (h:t) = (h,t):map f (select t)
   where f (x,l) = (x,h:l)

roleOccurrences :: Int -> String -> Tableau -> [Id]
roleOccurrences pid ename t = 
               [childId e | e <- edges t, match e]
    where match (Edge pid' ename' cid') = 
               pid == pid' && ename == ename'

removeNode :: Int -> [Node] -> [Node]
removeNode n ns = filter f ns
   where f x = nid x /= n

findNode   :: Int -> [Node] -> [Node]
findNode n ns   = filter f ns
   where f x = nid x == n

unifyNodes :: Id -> Id -> Tableau -> (Id,Tableau)
unifyNodes i1 i2 t = (i1,t {nodes = n:ns', 
                            edges = usort$map f (edges t),
                            diffs = usort$map g (diffs t)
                           }
                     )
    where n = n1 {exprs = usort$(exprs n1 ++ exprs n2)}
          ([n1],[n2]) = (findNode i1 ns,findNode i2 ns)
          ns' = removeNode i1$removeNode i2 ns
          ns = nodes t
          f e = if      parentId e == i2 then e {parentId = i1}
                else if childId  e == i2 then e {childId = i1}
                else e
          g (x,y) = if x==i2 then if i1<y then (i1,y) 
                                  else (y,i1)
                    else if y==i2 then if x<i1 then (x,i1) 
                                       else (i1,x)
                    else (x,y)

unifyNodeList :: Tableau -> [Id] -> Tableau
unifyNodeList t [] = t
unifyNodeList t (i:is) = t'
    where (_,t') = foldl op (i,t) is
          op (i1,t) i2 = unifyNodes i1 i2 t

applyAtMost :: TableauTransform
applyAtMost t = if null l then [t]
                else if any null l then [] 
                else atMostRule (minimum (map lpair l))
    where l = foldl f [] [(nid n,m,rn) | 
                          n <- nodes t, AtMost m rn <- exprs n
                         ]
          f ts (pid,l,rn) = if length rocs <= l then ts
                            else (colourings l rocs (diffs t)):ts
              where rocs = roleOccurrences pid rn t
          lpair l = (length l,l)
          atMostRule (_,us) = map (foldl unifyNodeList t) us


applyOr :: TableauTransform
applyOr t = f toDo
  where toDo = [(n,e) | n <- nodes t, e <- exprs n, orExpr e n]
        orExpr (e1 `Or` e2) n = 
             (notElem e1 (exprs n)) && (notElem e2 (exprs n))
        orExpr _ _ = False
        f [] = [t]
        f ((n,e1 `Or` e2):_) = 
          [t {nodes = n1:nodes'}, t {nodes = n2:nodes'}]
          where (n1,n2) = (n {exprs = e1:es},n {exprs = e2:es})
                es = exprs n  
                nodes' = removeNode (nid n) (nodes t)


newEdge :: Tableau -> [Id] -> Int -> String -> Expr -> Tableau
newEdge t dvs pid roleName expr = 
   t {nodes = n:nodes t, edges = e:edges t, 
      nextId = cid+1, diffs = diffs'
     }
   where n = Node cid [expr `And` topExpr t]
         e = Edge pid roleName cid
         cid = nextId t
         diffs' = addDiffs cid (diffs t) dvs

addDiffs :: a -> [(b,a)] -> [b] -> [(b,a)]
addDiffs v = foldl op
   where op x e = (e,v):x

applyExists :: TableauTransform
applyExists t = [foldl f t toDo]
  where (ns,es) = (nodes t,edges t)
        toDo = take 1 [(nid n,c) | n <- ns, nonBlocked n ns es,
                       c <- exprs n, match n c
                      ]
        match n (Exists ename expr) =
            all (notElem expr) 
                [(exprs node) | e <- es,parentId e == nid n,
                 role e == ename,node <- ns, 
                 childId e == nid node
                ]
        match _ _ = False
        f t (pid,Exists ename expr) = 
            newEdge t [] pid ename expr


applyAtLeast :: TableauTransform
applyAtLeast t = [first (foldl addEdge (t,[]) toDo)]
    where (ns,es) = (nodes t,edges t)
          toDo = [(nid n,ename,count) | 
                  n <- ns, nonBlocked n ns es,
                  AtLeast rcount ename <- exprs n,
                  count <- match (nid n) ename rcount
                 ]
          match pid ename rcount = if missing > 0 
                                   then [rcount] else []
              where missing = rcount - length (filter f es)
                    f e = parentId e == pid && 
                          role e == ename
          addEdge (t,dvs) (pid,ename,rcount) =
              if rcount < 1 then (t,dvs)
              else addEdge (t',(nextId t):dvs) (pid,ename,rcount-1)
              where t' = newEdge t dvs pid ename Top
          first (a,_) = a

ancestors :: Node -> [Node] -> [Edge] -> [Node]
ancestors n ns es = [p | pid <- ancestorIds [nid n] [],
                         p <- ns, nid p == pid
                    ]
  where ancestorIds nidl aidl = if null pidl then aidl'
                                else ancestorIds pidl aidl'
              where (pidl,aidl') = 
                        foldl parentIds ([],aidl) nidl
        parentIds (pidl,aidl) cid = (ps ++ pidl,ps ++ aidl)
              where ps = [parentId e | 
                          e <- es, childId e == cid
                         ]

nonBlocked :: Node -> [Node] -> [Edge] -> Bool
nonBlocked n ns es = 
        not$any (blocks$exprs n) (ancestors n ns es)
  where blocks exs node = all f exs
          where f x = elem x (exprs node)

