-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Directed acyclic word graphs
--   
--   The library implements <i>directed acyclic word graphs</i> (DAWGs)
--   internally represented as <i>minimal acyclic deterministic
--   finite-state automata</i>. The implemented version of DAWG can be seen
--   as a map from sequences of alphabet symbols (keys) to values.
--   
--   The library allows to build DAWGs over any symbols and values provided
--   that they both have <a>Ord</a> instances (see the <a>Data.DAWG.Ord</a>
--   module). It also provides a fast insert operation which can be used to
--   construct DAWGs on-the-fly.
@package dawg-ord
@version 0.5.1.0


-- | The module implements <i>directed acyclic word graphs</i> (DAWGs)
--   internaly represented as <i>minimal acyclic deterministic finite-state
--   automata</i>. The implementation provides fast insert and delete
--   operations which can be used to build the DAWG structure incrementaly.
--   
--   See the <a>Data.DAWG.Ord</a> module if you look for a more generic
--   solution (which, for the moment, lacks some of the functionality
--   provided here, e.g. the <a>delete</a> function).
module Data.DAWG.Int

-- | A directed acyclic word graph (DAWG), which can be seen as a map from
--   keys (sequences of <a>Sym</a>'s) to values <a>Val</a>. See
--   <a>Data.DAWG.Ord</a> for a more generic version of DAWGs.
data DAWG

-- | Identifier of a DAWG node (automaton state).
type ID = Int

-- | A transition symbol.
type Sym = Int

-- | A type of DAWG values, stored in accept states.
type Val = Int

-- | The root (start state) of the DAWG.
root :: DAWG -> ID

-- | Find value associated with the key.
lookup :: [Sym] -> DAWG -> Maybe Val

-- | Number of states in the automaton.
numStates :: DAWG -> Int

-- | Number of transitions in the automaton.
numEdges :: DAWG -> Int

-- | Value stored in the given automaton state.
value :: ID -> DAWG -> Maybe Val

-- | A list of outgoing edges (automaton transitions).
edges :: ID -> DAWG -> [(Sym, ID)]

-- | Follow a transition with the given symbol from the given state.
follow :: ID -> Sym -> DAWG -> Maybe ID

-- | Empty DAWG.
empty :: DAWG

-- | Construct DAWG from the list of (key, value) pairs.
fromList :: [([Sym], Val)] -> DAWG

-- | Construct DAWG from the list of (key, value) pairs with a combining
--   function. The combining function is applied strictly.
fromListWith :: (Val -> Val -> Val) -> [([Sym], Val)] -> DAWG

-- | Make DAWG from the list of words (by annotating each word with a dummy
--   value).
fromLang :: [[Sym]] -> DAWG

-- | Insert the (key, value) pair into the DAWG.
insert :: [Sym] -> Val -> DAWG -> DAWG

-- | Insert with a function, combining new value and old value.
--   <a>insertWith</a> f key value d will insert the pair (key, value) into
--   d if key does not exist in the DAWG. If the key does exist, the
--   function will insert the pair (key, f new_value old_value).
insertWith :: (Val -> Val -> Val) -> [Sym] -> Val -> DAWG -> DAWG

-- | Delete the key from the DAWG.
delete :: [Sym] -> DAWG -> DAWG

-- | Return all key/value pairs in the DAWG in ascending key order.
assocs :: DAWG -> [([Sym], Val)]

-- | Return all keys of the DAWG in ascending order.
keys :: DAWG -> [[Sym]]

-- | Return all elements of the DAWG in the ascending order of their keys.
elems :: DAWG -> [Val]


-- | A version of <a>Data.DAWG.Int</a> adapted to keys and values with
--   <a>Ord</a> instances.
module Data.DAWG.Ord

-- | A directed acyclic word graph (DAWG) with type <tt>a</tt> representing
--   the type of alphabet symbols (over which keys are constructed) and
--   type <tt>b</tt> -- the type of values.
--   
--   A DAWG can be seen as a map from keys (sequences of <tt>a</tt>'s) to
--   values <tt>b</tt>.
data DAWG a b

-- | Identifier of a DAWG node (automaton state).
type ID = Int

-- | The root (start state) of the DAWG.
root :: DAWG a b -> ID

-- | Find value associated with the key.
lookup :: (Ord a) => [a] -> DAWG a b -> Maybe b

-- | Number of states in the underlying automaton.
numStates :: DAWG a b -> Int

-- | Number of transitions in the underlying automaton.
numEdges :: DAWG a b -> Int

-- | Value stored in the given automaton state.
value :: ID -> DAWG a b -> Maybe b

-- | A list of outgoing edges (automaton transitions).
edges :: ID -> DAWG a b -> [(a, ID)]

-- | Follow a transition with the given symbol from the given state.
follow :: Ord a => ID -> a -> DAWG a b -> Maybe ID

-- | Empty DAWG.
empty :: DAWG a b

-- | Construct DAWG from the list of (key, value) pairs.
fromList :: (Ord a, Ord b) => [([a], b)] -> DAWG a b

-- | Make DAWG from the list of words (annotate each word with the
--   <tt>()</tt> value).
fromLang :: Ord a => [[a]] -> DAWG a ()

-- | Insert the (key, value) pair into the DAWG.
insert :: (Ord a, Ord b) => [a] -> b -> DAWG a b -> DAWG a b

-- | Return all key/value pairs in the DAWG in ascending key order.
assocs :: DAWG a b -> [([a], b)]

-- | Return all keys of the DAWG in ascending order.
keys :: DAWG a b -> [[a]]

-- | Return all elements of the DAWG in the ascending order of their keys.
elems :: DAWG a b -> [b]
