-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Multimap
-- Maintainer  :  Ziyang Liu <free@cofree.io>
--
-- Multimaps, where values behave like (non empty) lists.
--
-- Multimaps whose values behave like sets are in "Data.Multimap.Set".
-- Multimaps whose values behave like maps (i.e., two-dimensional
-- tables) are in "Data.Multimap.Table".
--
-- The implementation is backed by a @'Map' k ('NonEmpty' a)@. The
-- differences between @'Multimap' k a@ and @'Map' k ('NonEmpty' a)@ include:
--
--   * 'lookup' (or '!') returns a possibly empty list. Unlike regular maps,
--     the '!' operator is total for multimaps.
--
--   * Functions like 'map', 'adjust', 'traverse', etc., take functions on
--     individual values (e.g., @a -> b@) as opposed to, e.g.,
--     @'NonEmpty' a -> 'NonEmpty' b@.
--
--   * 'union' and 'unions' concatenate the values when there are duplicate
--     keys, rather than being left- or right-biased.
--
--   * The 'difference' function computes list differences for values of
--     keys that exist in both maps.
--
--   * The 'size' function returns the total number of values for all keys in
--     the multimap, not the number of distinct keys. The latter can be obtained
--     by first getting the 'keysSet' or first converting the multimap to
--     a regular map via 'toMap'.
--
-- In the following Big-O notations, unless otherwise noted, /n/ denotes
-- the size of the multimap, /k/ denotes the number of distinct keys, and
-- /m/ denotes the maximum number of values associated with a single key.
module Data.Multimap (
  -- * Multimap type
  Multimap

  -- * Construction
  , empty
  , singleton
  , fromMap
  , fromMap'

  -- ** From Unordered Lists
  , fromList

  -- * Insertion
  , insert

  -- * Deletion\/Update
  , delete
  , deleteWithValue
  , deleteOne
  , adjust
  , adjustWithKey
  , update
  , update'
  , updateWithKey
  , updateWithKey'
  , alter
  , alterWithKey

  -- * Query
  -- ** Lookup
  , lookup
  , (!)
  , member
  , notMember

  -- ** Size
  , null
  , notNull
  , size

  -- * Combine
  -- ** Union
  , union
  , unions

  -- ** Difference
  , difference

  -- * Traversal
  -- ** Map
  , map
  , mapWithKey
  , traverseWithKey
  , traverseMaybeWithKey

  -- ** Folds
  , foldr
  , foldl
  , foldrWithKey
  , foldlWithKey
  , foldMapWithKey

  -- ** Strict Folds
  , foldr'
  , foldl'
  , foldrWithKey'
  , foldlWithKey'

  -- * Conversion
  , elems
  , keys
  , assocs
  , keysSet

  -- ** Lists
  , toList

  -- ** Ordered lists
  , toAscList
  , toDescList
  , toAscListBF
  , toDescListBF

  -- ** Maps
  , toMap

  -- ** SetMultimaps
  , fromSetMultimapAsc
  , fromSetMultimapDesc
  , toSetMultimap

  -- * Filter
  , filter
  , filterWithKey
  , filterKey
  , filterM
  , filterWithKeyM

  , mapMaybe
  , mapMaybeWithKey
  , mapEither
  , mapEitherWithKey

  -- * Min\/Max
  , lookupMin
  , lookupMax
  , lookupLT
  , lookupGT
  , lookupLE
  , lookupGE
  ) where

import Data.Multimap.Conversions
import Data.Multimap.Internal
import Data.Multimap.Set.Internal (SetMultimap)
import Prelude hiding (filter, foldl, foldr, lookup, map, null)

-- | Convert a t'Data.Multimap.Set.SetMultimap' to a t'Data.Multimap.Multimap' where the values of each key
-- are in ascending order.
--
-- > fromSetMultimapAsc (Data.Multimap.Set.fromList [(1,'a'),(1,'b'),(2,'c')]) === Data.Multimap.fromList [(1,'a'),(1,'b'),(2,'c')]
fromSetMultimapAsc :: SetMultimap k a -> Multimap k a
fromSetMultimapAsc :: SetMultimap k a -> Multimap k a
fromSetMultimapAsc = SetMultimap k a -> Multimap k a
forall k a. SetMultimap k a -> Multimap k a
toMultimapAsc

-- | Convert a t'Data.Multimap.Set.SetMultimap' to a t'Data.Multimap.Multimap' where the values of each key
-- are in descending order.
--
-- > fromSetMultimapDesc (Data.Multimap.Set.fromList [(1,'a'),(1,'b'),(2,'c')]) === Data.Multimap.fromList [(1,'b'),(1,'a'),(2,'c')]
fromSetMultimapDesc :: SetMultimap k a -> Multimap k a
fromSetMultimapDesc :: SetMultimap k a -> Multimap k a
fromSetMultimapDesc = SetMultimap k a -> Multimap k a
forall k a. SetMultimap k a -> Multimap k a
toMultimapDesc