POSet.hs

-- |
-- Module      :  Data.POSet
-- Copyright   :  (c) Sebastian Graf 2017
-- License     :  MIT
-- Maintainer  :  sgraf1337@gmail.com
-- Portability :  portable
--
-- A reasonably efficient implementation of partially ordered sets.
--
-- These modules are intended to be imported qualified, to avoid name
-- clashes with Prelude functions, e.g.
--
-- > import qualified Data.POSet as POSet
--
-- The implementation of 'POSet' is based on a decomposition of
-- chains (totally ordered submaps), inspired by
-- [\"Sorting and Selection in Posets\"](https://arxiv.org/abs/0707.1532).
--
-- Operation comments contain the operation time complexity in
-- [Big-O notation](http://en.wikipedia.org/wiki/Big_O_notation) and
-- commonly refer to two characteristics of the poset from which keys are drawn:
-- The number of elements in the set \(n\) and the /width/ \(w\) of the poset,
-- referring to the size of the biggest anti-chain (set of incomparable elements).
--
-- Generally speaking, lookup and mutation operations incur an additional
-- factor of \(\mathcal{O}(w)\) compared to their counter-parts in "Data.Set".
--
-- Note that for practical applications, the width of the poset should be
-- in the order of \(w\in \mathcal{O}(\frac{n}{\log n})\), otherwise a simple lookup list
-- is asymptotically superior.
-- Even if that holds, the constants might be too big to be useful for any \(n\) that can
-- can happen in practice.
--
-- The following examples assume the following definitions for a set on the divisibility
-- relation on `Int`egers:
--
-- @
-- {-\# LANGUAGE GeneralizedNewtypeDeriving \#-}
--
-- import           Algebra.PartialOrd
-- import           Data.POSet (POSet)
-- import qualified Data.POSet as POSet
--
-- newtype Divisibility
--   = Div Int
--   deriving (Eq, Read, Show, Num)
--
-- default (Divisibility)
--
-- instance 'PartialOrd' Divisibility where
--   Div a \`leq\` Div b = b \`mod\` a == 0
--
-- type DivSet = POSet Divisibility
--
-- -- We want integer literals to be interpreted as 'Divisibility's
-- -- and default 'empty's to DivSet.
-- default (Divisibility, DivSet)
-- @
--
-- 'Divisility' is actually an example for a 'PartialOrd' that should not be used as keys of 'POSet'.
-- Its width is \(w=\frac{n}{2}\in\Omega(n)\)!

module Data.POSet
  (
  -- * Set type
    Impl.POSet
  -- * Query
  , Foldable.null
  , Impl.size
  , Impl.member
  , Impl.notMember
  , Impl.lookupLT
  , Impl.lookupGT
  , Impl.lookupLE
  , Impl.lookupGE
  , Impl.isSubsetOf
  , Impl.isProperSubsetOf

  -- * Construction
  , Impl.empty
  , Impl.singleton
  , Impl.insert
  , Impl.delete

  -- * Combine
  , Impl.union
  , Impl.unions
  , Impl.difference
  , Impl.intersection

  -- * Filter
  , Impl.filter
  , Impl.partition

  -- * Map
  , Impl.map
  , Impl.mapMonotonic

  -- * Folds
  , Foldable.foldr
  , Foldable.foldl
  -- ** Strict folds
  , Impl.foldr'
  , Impl.foldl'

  -- * Min\/Max
  , Impl.lookupMin
  , Impl.lookupMax

  -- * Conversion
  , Impl.elems
  , Impl.toList
  , Impl.fromList
  ) where

import qualified Data.Foldable       as Foldable
import qualified Data.POSet.Internal as Impl