-- | GraphQuery: Portable, composable graph query interface.
--
-- This module provides 'GraphQuery v', a record-of-functions that abstracts
-- over any graph representation. Algorithms in "Pattern.Graph.Algorithms"
-- accept 'GraphQuery v' and are therefore independent of whether the
-- underlying graph is a 'GraphLens' or a 'PatternGraph'.
--
-- == Categorical Interpretation
--
-- 'GraphQuery v' is a coalgebra: given a graph element, it produces the
-- elements reachable from it. 'queryContainers' is the upward dual — given
-- an element, it produces the structures that contain it. Together they form
-- a bidirectional traversal interface.
--
-- == Design Principles
--
-- 1. Record-of-functions (not a typeclass) — consistent with 'GraphClassifier'.
-- 2. 'TraversalWeight' is a call-site parameter, not part of the interface.
-- 3. Combinators ('frameQuery', 'memoizeIncidentRels') are plain functions.
--
-- == Example
--
-- > import Pattern.Graph (fromGraphLens)
-- > import Pattern.PatternGraph (fromPatternGraph)
-- > import Pattern.Graph.GraphQuery (directed)
-- > import qualified Pattern.Graph.Algorithms as Alg
-- >
-- > -- From a PatternGraph (O(log n) lookups):
-- > let gq = fromPatternGraph myPatternGraph
-- > let path = Alg.shortestPath gq directed nodeA nodeB
-- >
-- > -- From a GraphLens (O(n) lookups):
-- > let gq2 = fromGraphLens myLens
-- > let comps = Alg.connectedComponents gq2 undirected
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE FlexibleContexts #-}
module Pattern.Graph.GraphQuery
  ( -- * Traversal types
    TraversalDirection(..)
  , TraversalWeight
  , undirected
  , directed
  , directedReverse
    -- * GraphQuery interface
  , GraphQuery(..)
    -- * Combinators
    -- Note: 'fromGraphLens' is defined in "Pattern.Graph" to avoid a circular
    -- import (GraphQuery → Graph → GraphQuery).
    -- Note: 'fromPatternGraph' is defined in "Pattern.PatternGraph" to avoid
    -- a circular import (GraphQuery → PatternGraph → Graph → GraphQuery).
    -- Import constructors from their respective modules directly.
  , frameQuery
  , memoizeIncidentRels
  ) where

import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map
import Pattern.Core (Pattern(..))
import Pattern.Graph.GraphClassifier (GraphValue(..))

-- Note: 'fromPatternGraph' is defined in "Pattern.PatternGraph" to avoid
-- a circular import cycle. The Map imports are kept for memoizeIncidentRels.

-- ============================================================================
-- TraversalDirection
-- ============================================================================

-- | The two orientations along a directed relationship.
--
-- 'Forward' follows the relationship from source to target;
-- 'Backward' follows it from target to source.
data TraversalDirection = Forward | Backward
  deriving (TraversalDirection -> TraversalDirection -> Bool
(TraversalDirection -> TraversalDirection -> Bool)
-> (TraversalDirection -> TraversalDirection -> Bool)
-> Eq TraversalDirection
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: TraversalDirection -> TraversalDirection -> Bool
== :: TraversalDirection -> TraversalDirection -> Bool
$c/= :: TraversalDirection -> TraversalDirection -> Bool
/= :: TraversalDirection -> TraversalDirection -> Bool
Eq, Int -> TraversalDirection -> ShowS
[TraversalDirection] -> ShowS
TraversalDirection -> String
(Int -> TraversalDirection -> ShowS)
-> (TraversalDirection -> String)
-> ([TraversalDirection] -> ShowS)
-> Show TraversalDirection
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> TraversalDirection -> ShowS
showsPrec :: Int -> TraversalDirection -> ShowS
$cshow :: TraversalDirection -> String
show :: TraversalDirection -> String
$cshowList :: [TraversalDirection] -> ShowS
showList :: [TraversalDirection] -> ShowS
Show)

-- ============================================================================
-- TraversalWeight
-- ============================================================================

-- | A function assigning a traversal cost to each (relationship, direction) pair.
--
-- Infinity (@1\/0 :: Double@) encodes impassability — traversal is blocked in
-- that direction. Non-negative values encode traversal cost. Negative weights
-- are not supported by the standard Dijkstra-based algorithms.
--
-- Canonical values: 'undirected', 'directed', 'directedReverse'.
type TraversalWeight v = Pattern v -> TraversalDirection -> Double

-- | Uniform cost in both directions. Direction is ignored.
undirected :: TraversalWeight v
undirected :: forall v. TraversalWeight v
undirected Pattern v
_ TraversalDirection
_ = Double
1.0

-- | Forward traversal only. Backward traversal is impassable.
directed :: TraversalWeight v
directed :: forall v. TraversalWeight v
directed Pattern v
_ TraversalDirection
Forward  = Double
1.0
directed Pattern v
_ TraversalDirection
Backward = Double
1 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
0

-- | Backward traversal only. Forward traversal is impassable.
directedReverse :: TraversalWeight v
directedReverse :: forall v. TraversalWeight v
directedReverse Pattern v
_ TraversalDirection
Forward  = Double
1 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
0
directedReverse Pattern v
_ TraversalDirection
Backward = Double
1.0

-- ============================================================================
-- GraphQuery
-- ============================================================================

-- | A record-of-functions representing a graph query interface.
--
-- Construct via 'fromGraphLens' or 'fromPatternGraph'. Compose with
-- 'frameQuery' and 'memoizeIncidentRels'.
--
-- == Performance note (Haskell-specific)
--
-- The hot-path fields ('queryIncidentRels', 'querySource', 'queryTarget',
-- 'queryDegree') are function-typed. GHC will inline their applications at
-- call sites when the 'GraphQuery' value is known statically; use
-- @{-# INLINE #-}@ on algorithms that receive 'GraphQuery' as a parameter
-- to encourage this. @{-# UNPACK #-}@ does not apply here because all fields
-- are either function types or boxed list types — neither can be unboxed.
--
-- == Invariants
--
-- * @querySource r = Just s@ implies @s ∈ queryNodes@.
-- * @queryTarget r = Just t@ implies @t ∈ queryNodes@.
-- * @r ∈ queryIncidentRels n@ implies @querySource r = Just n ∨ queryTarget r = Just n@.
-- * @queryDegree n = length (queryIncidentRels n)@ (default; implementations may be faster).
-- * @queryNodeById (identify (value n)) = Just n@ for all @n ∈ queryNodes@.
-- * @queryRelationshipById (identify (value r)) = Just r@ for all @r ∈ queryRelationships@.
-- * @queryContainers@ returns only direct containers — does not recurse transitively.
data GraphQuery v = GraphQuery
  { forall v. GraphQuery v -> [Pattern v]
queryNodes            :: [Pattern v]
    -- ^ All node-classified elements in the graph. O(n).
  , forall v. GraphQuery v -> [Pattern v]
queryRelationships    :: [Pattern v]
    -- ^ All relationship-classified elements. O(r).
  , forall v. GraphQuery v -> Pattern v -> [Pattern v]
queryIncidentRels     :: Pattern v -> [Pattern v]
    -- ^ All relationships where the given node is source or target. O(r).
  , forall v. GraphQuery v -> Pattern v -> Maybe (Pattern v)
querySource           :: Pattern v -> Maybe (Pattern v)
    -- ^ The source (first endpoint) of a relationship; 'Nothing' if not a relationship. O(1).
  , forall v. GraphQuery v -> Pattern v -> Maybe (Pattern v)
queryTarget           :: Pattern v -> Maybe (Pattern v)
    -- ^ The target (second endpoint) of a relationship; 'Nothing' if not a relationship. O(1).
  , forall v. GraphQuery v -> Pattern v -> Int
queryDegree           :: Pattern v -> Int
    -- ^ Count of incident relationships for a node. O(r) default; O(1) if indexed.
  , forall v. GraphQuery v -> Id v -> Maybe (Pattern v)
queryNodeById         :: Id v -> Maybe (Pattern v)
    -- ^ Node lookup by identity. O(log n) from PatternGraph; O(n) from GraphLens.
  , forall v. GraphQuery v -> Id v -> Maybe (Pattern v)
queryRelationshipById :: Id v -> Maybe (Pattern v)
    -- ^ Relationship lookup by identity. O(log r) from PatternGraph; O(r) from GraphLens.
  , forall v. GraphQuery v -> Pattern v -> [Pattern v]
queryContainers       :: Pattern v -> [Pattern v]
    -- ^ All higher-order structures (relationships, walks, annotations) that directly
    -- contain the given element. O(r + w + a).
  }

-- ============================================================================
-- Combinators
-- ============================================================================

-- | Produce a 'GraphQuery' restricted to elements satisfying a predicate.
--
-- 'queryIncidentRels' on the framed query excludes relationships whose
-- endpoints fall outside the frame. All 'GraphQuery' invariants are preserved.
--
-- == Example
--
-- > let subgraph = frameQuery (\(Pattern v _) -> v == "Person") gq
frameQuery :: (Pattern v -> Bool) -> GraphQuery v -> GraphQuery v
frameQuery :: forall v. (Pattern v -> Bool) -> GraphQuery v -> GraphQuery v
frameQuery Pattern v -> Bool
include GraphQuery v
base = GraphQuery
  { queryNodes :: [Pattern v]
queryNodes            = (Pattern v -> Bool) -> [Pattern v] -> [Pattern v]
forall a. (a -> Bool) -> [a] -> [a]
filter Pattern v -> Bool
include (GraphQuery v -> [Pattern v]
forall v. GraphQuery v -> [Pattern v]
queryNodes GraphQuery v
base)
  , queryRelationships :: [Pattern v]
queryRelationships    = (Pattern v -> Bool) -> [Pattern v] -> [Pattern v]
forall a. (a -> Bool) -> [a] -> [a]
filter Pattern v -> Bool
include (GraphQuery v -> [Pattern v]
forall v. GraphQuery v -> [Pattern v]
queryRelationships GraphQuery v
base)
  , queryIncidentRels :: Pattern v -> [Pattern v]
queryIncidentRels     = \Pattern v
n ->
      (Pattern v -> Bool) -> [Pattern v] -> [Pattern v]
forall a. (a -> Bool) -> [a] -> [a]
filter (\Pattern v
r -> Bool -> (Pattern v -> Bool) -> Maybe (Pattern v) -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False Pattern v -> Bool
include (GraphQuery v -> Pattern v -> Maybe (Pattern v)
forall v. GraphQuery v -> Pattern v -> Maybe (Pattern v)
querySource GraphQuery v
base Pattern v
r)
                 Bool -> Bool -> Bool
&& Bool -> (Pattern v -> Bool) -> Maybe (Pattern v) -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False Pattern v -> Bool
include (GraphQuery v -> Pattern v -> Maybe (Pattern v)
forall v. GraphQuery v -> Pattern v -> Maybe (Pattern v)
queryTarget GraphQuery v
base Pattern v
r))
             (GraphQuery v -> Pattern v -> [Pattern v]
forall v. GraphQuery v -> Pattern v -> [Pattern v]
queryIncidentRels GraphQuery v
base Pattern v
n)
  , querySource :: Pattern v -> Maybe (Pattern v)
querySource           = GraphQuery v -> Pattern v -> Maybe (Pattern v)
forall v. GraphQuery v -> Pattern v -> Maybe (Pattern v)
querySource GraphQuery v
base
  , queryTarget :: Pattern v -> Maybe (Pattern v)
queryTarget           = GraphQuery v -> Pattern v -> Maybe (Pattern v)
forall v. GraphQuery v -> Pattern v -> Maybe (Pattern v)
queryTarget GraphQuery v
base
  , queryDegree :: Pattern v -> Int
queryDegree           = \Pattern v
n ->
      [Pattern v] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Pattern v] -> Int) -> [Pattern v] -> Int
forall a b. (a -> b) -> a -> b
$ (Pattern v -> Bool) -> [Pattern v] -> [Pattern v]
forall a. (a -> Bool) -> [a] -> [a]
filter (\Pattern v
r -> Bool -> (Pattern v -> Bool) -> Maybe (Pattern v) -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False Pattern v -> Bool
include (GraphQuery v -> Pattern v -> Maybe (Pattern v)
forall v. GraphQuery v -> Pattern v -> Maybe (Pattern v)
querySource GraphQuery v
base Pattern v
r)
                          Bool -> Bool -> Bool
&& Bool -> (Pattern v -> Bool) -> Maybe (Pattern v) -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False Pattern v -> Bool
include (GraphQuery v -> Pattern v -> Maybe (Pattern v)
forall v. GraphQuery v -> Pattern v -> Maybe (Pattern v)
queryTarget GraphQuery v
base Pattern v
r))
                      (GraphQuery v -> Pattern v -> [Pattern v]
forall v. GraphQuery v -> Pattern v -> [Pattern v]
queryIncidentRels GraphQuery v
base Pattern v
n)
  , queryNodeById :: Id v -> Maybe (Pattern v)
queryNodeById         = \Id v
i -> case GraphQuery v -> Id v -> Maybe (Pattern v)
forall v. GraphQuery v -> Id v -> Maybe (Pattern v)
queryNodeById GraphQuery v
base Id v
i of
      Just Pattern v
n | Pattern v -> Bool
include Pattern v
n -> Pattern v -> Maybe (Pattern v)
forall a. a -> Maybe a
Just Pattern v
n
      Maybe (Pattern v)
_                  -> Maybe (Pattern v)
forall a. Maybe a
Nothing
  , queryRelationshipById :: Id v -> Maybe (Pattern v)
queryRelationshipById = \Id v
i -> case GraphQuery v -> Id v -> Maybe (Pattern v)
forall v. GraphQuery v -> Id v -> Maybe (Pattern v)
queryRelationshipById GraphQuery v
base Id v
i of
      Just Pattern v
r | Pattern v -> Bool
include Pattern v
r -> Pattern v -> Maybe (Pattern v)
forall a. a -> Maybe a
Just Pattern v
r
      Maybe (Pattern v)
_                  -> Maybe (Pattern v)
forall a. Maybe a
Nothing
  , queryContainers :: Pattern v -> [Pattern v]
queryContainers       = \Pattern v
p ->
      (Pattern v -> Bool) -> [Pattern v] -> [Pattern v]
forall a. (a -> Bool) -> [a] -> [a]
filter Pattern v -> Bool
include (GraphQuery v -> Pattern v -> [Pattern v]
forall v. GraphQuery v -> Pattern v -> [Pattern v]
queryContainers GraphQuery v
base Pattern v
p)
  }

-- | Wrap 'queryIncidentRels' with a pure memoization layer.
--
-- Builds a complete cache from 'queryNodes' eagerly, then serves all
-- subsequent 'queryIncidentRels' calls from the cache. All other fields
-- are passed through unchanged.
--
-- Useful for algorithms (e.g. betweenness centrality) that call
-- 'queryIncidentRels' repeatedly on the same node.
--
-- Note: The cache is per-'GraphQuery' value, not global.
memoizeIncidentRels :: (GraphValue v, Ord (Id v)) => GraphQuery v -> GraphQuery v
memoizeIncidentRels :: forall v.
(GraphValue v, Ord (Id v)) =>
GraphQuery v -> GraphQuery v
memoizeIncidentRels GraphQuery v
base =
  let cache :: Map (Id v) [Pattern v]
cache = [(Id v, [Pattern v])] -> Map (Id v) [Pattern v]
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList
        [ (v -> Id v
forall v. GraphValue v => v -> Id v
identify (Pattern v -> v
forall v. Pattern v -> v
value Pattern v
n), GraphQuery v -> Pattern v -> [Pattern v]
forall v. GraphQuery v -> Pattern v -> [Pattern v]
queryIncidentRels GraphQuery v
base Pattern v
n)
        | Pattern v
n <- GraphQuery v -> [Pattern v]
forall v. GraphQuery v -> [Pattern v]
queryNodes GraphQuery v
base
        ]
      cachedIncident :: Pattern v -> [Pattern v]
cachedIncident Pattern v
n = [Pattern v] -> Id v -> Map (Id v) [Pattern v] -> [Pattern v]
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault [] (v -> Id v
forall v. GraphValue v => v -> Id v
identify (Pattern v -> v
forall v. Pattern v -> v
value Pattern v
n)) Map (Id v) [Pattern v]
cache
  in GraphQuery v
base { queryIncidentRels = cachedIncident
          , queryDegree       = \Pattern v
n -> [Pattern v] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (Pattern v -> [Pattern v]
cachedIncident Pattern v
n)
          }