vector-hashtables-0.1.2.1: Efficient vector-based mutable hashtables implementation.

Copyright | (c) klapaucius swamp_agr 2016-2021
License | BSD3
Safe Haskell | None
Language | Haskell2010

Data.Vector.Hashtables.Internal

Contents

- Combine
- Difference and intersection
- List conversions
- Extras

Description

Synopsis

- type IntArray s = MutablePrimArray s Int
- newtype Dictionary s (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v = DRef {
  - getDRef :: MutVar s (Dictionary_ s ks k vs v)
  }
- data Dictionary_ s (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v = Dictionary {
  - hashCode :: !(IntArray s)
  - next :: !(IntArray s)
  - buckets :: !(IntArray s)
  - refs :: !(IntArray s)
  - key :: !(ks s k)
  - value :: !(vs s v)
  - remSize :: !FastRem
  }
- getCount :: Int
- getFreeList :: Int
- getFreeCount :: Int
- data FrozenDictionary (ks :: Type -> Type) k (vs :: Type -> Type) v = FrozenDictionary {
  - fhashCode :: !(PrimArray Int)
  - fnext :: !(PrimArray Int)
  - fbuckets :: !(PrimArray Int)
  - count :: !Int
  - freeList :: !Int
  - freeCount :: !Int
  - fkey :: !(ks k)
  - fvalue :: !(vs v)
  - fremSize :: !FastRem
  }
- findElem :: forall (ks :: Type -> Type) k (vs :: Type -> Type) v. (Vector ks k, Vector vs v, Hashable k, Eq k) => FrozenDictionary ks k vs v -> k -> Int
- (!~) :: (MVector v a, PrimMonad m) => v (PrimState m) a -> Int -> m a
- (!.~) :: Vector v a => v a -> Int -> a
- (<~~) :: (MVector v a, PrimMonad m) => v (PrimState m) a -> Int -> a -> m ()
- (!) :: PrimMonad m => MutablePrimArray (PrimState m) Int -> Int -> m Int
- (!.) :: PrimArray Int -> Int -> Int
- (<~) :: PrimMonad m => MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
- initialize :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m) => Int -> m (Dictionary (PrimState m) ks k vs v)
- clone :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)
- unsafeFreeze :: forall (ks :: Type -> Type) k (vs :: Type -> Type) v m. (Vector ks k, Vector vs v, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v -> m (FrozenDictionary ks k vs v)
- unsafeThaw :: forall (ks :: Type -> Type) k (vs :: Type -> Type) v m. (Vector ks k, Vector vs v, PrimMonad m) => FrozenDictionary ks k vs v -> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v)
- keys :: forall ks k m (vs :: Type -> Type -> Type) v. (Vector ks k, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k vs v -> m (ks k)
- values :: forall vs v m (ks :: Type -> Type -> Type) k. (Vector vs v, PrimMonad m) => Dictionary (PrimState m) ks k (Mutable vs) v -> m (vs v)
- at :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m v
- at' :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
- atWithOrElse :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m a. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> (Dictionary (PrimState m) ks k vs v -> Int -> m a) -> (Dictionary (PrimState m) ks k vs v -> m a) -> m a
- findEntry :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m Int
- findEntry_ :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary_ (PrimState m) ks k vs v -> k -> m Int
- insert :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
- insertWithIndex :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Int -> Int -> k -> v -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v) -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
- addOrResize :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Int -> Int -> k -> v -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v) -> Dictionary_ (PrimState m) ks k vs v -> m ()
- add :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Int -> Int -> Int -> k -> v -> Dictionary_ (PrimState m) ks k vs v -> m ()
- resize :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary_ (PrimState m) ks k vs v -> Int -> Int -> k -> v -> m (Dictionary_ (PrimState m) ks k vs v)
- class DeleteEntry (xs :: Type -> Type -> Type) where
  - deleteEntry :: (MVector xs x, PrimMonad m) => xs (PrimState m) x -> Int -> m ()
- delete :: forall k (ks :: Type -> Type -> Type) (vs :: Type -> Type -> Type) v m. (Eq k, MVector ks k, MVector vs v, Hashable k, PrimMonad m, DeleteEntry ks, DeleteEntry vs) => Dictionary (PrimState m) ks k vs v -> k -> m ()
- deleteWithIndex :: forall k (ks :: Type -> Type -> Type) (vs :: Type -> Type -> Type) v m. (Eq k, MVector ks k, MVector vs v, Hashable k, PrimMonad m, DeleteEntry ks, DeleteEntry vs) => Int -> Int -> Dictionary_ (PrimState m) ks k vs v -> k -> Int -> Int -> m ()
- lookup :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
- lookup' :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m v
- lookupIndex :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe Int)
- null :: forall (ks :: Type -> Type -> Type) k m (vs :: Type -> Type -> Type) v. (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Bool
- length :: forall (ks :: Type -> Type -> Type) k m (vs :: Type -> Type -> Type) v. (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Int
- size :: forall (ks :: Type -> Type -> Type) k m (vs :: Type -> Type -> Type) v. (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Int
- member :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m Bool
- findWithDefault :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> v -> k -> m v
- upsert :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> v) -> k -> m ()
- alter :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> Maybe v) -> k -> m ()
- alterM :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> m (Maybe v)) -> k -> m ()
- union :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)
- unionWith :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => (v -> v -> v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)
- unionWithKey :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => (k -> v -> v -> v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)
- difference :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v w m. (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v)
- differenceWith :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v w m. (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => (v -> w -> Maybe v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v)
- intersection :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v w m. (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v)
- intersectionWith :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v1 v2 v3 m. (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k) => (v1 -> v2 -> v3) -> Dictionary (PrimState m) ks k vs v1 -> Dictionary (PrimState m) ks k vs v2 -> m (Dictionary (PrimState m) ks k vs v3)
- intersectionWithKey :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v1 v2 v3 m. (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k) => (k -> v1 -> v2 -> v3) -> Dictionary (PrimState m) ks k vs v1 -> Dictionary (PrimState m) ks k vs v2 -> m (Dictionary (PrimState m) ks k vs v3)
- fromList :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => [(k, v)] -> m (Dictionary (PrimState m) ks k vs v)
- toList :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> m [(k, v)]
- primesWithFastRem :: Vector (Int, Int, Int)
- getFastRem :: Int -> FastRem
- data FastRem = FastRem {
  - frmPrime :: !Int
  - _frmMulHi :: !Int
  - _frmShift :: !Int
  }
- fastRem :: Int -> FastRem -> Int

# Documentation

type IntArray s = MutablePrimArray s Int Source #

Alias for `MutablePrimArray` `s` `Int`.

newtype Dictionary s (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v Source #

Single-element mutable array of `Dictionary_` with primitive state token parameterized with state, keys and values types.

Different flavors of `MVector` could be used for keys and values. It's preferable to use Data.Vector.Unboxed.Mutable or Data.Vector.Storable.Mutable if possible. Otherwise, if you must use boxed vectors, consider employing strict ones from `strict-containers` to eliminate potential accumulation of thunks.

#### Example

    >>> import qualified Data.Vector.Storable.Mutable as VM
    >>> import qualified Data.Vector.Unboxed.Mutable  as UM
    >>> import Data.Vector.Hashtables
    >>> type HashTable k v = Dictionary (PrimState IO) VM.MVector k UM.MVector v

Constructors

DRef |

Fields

- getDRef :: MutVar s (Dictionary_ s ks k vs v)

data Dictionary_ s (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v Source #

Represents collection of hashtable internal primitive arrays and vectors.

- hash codes,
- references to the next element,
- buckets,
- keys
- and values.

Constructors

Dictionary |

Fields

- hashCode :: !(IntArray s)
- next :: !(IntArray s)
- buckets :: !(IntArray s)
- refs :: !(IntArray s)
- key :: !(ks s k)
- value :: !(vs s v)
- remSize :: !FastRem

getCount :: Int Source #

getFreeList :: Int Source #

getFreeCount :: Int Source #

data FrozenDictionary (ks :: Type -> Type) k (vs :: Type -> Type) v Source #

Represents immutable dictionary as collection of immutable arrays and vectors. See `unsafeFreeze` and `unsafeThaw` for conversions from/to mutable dictionary.

Constructors

FrozenDictionary |

Fields

- fhashCode :: !(PrimArray Int)
- fnext :: !(PrimArray Int)
- fbuckets :: !(PrimArray Int)
- count :: !Int
- freeList :: !Int
- freeCount :: !Int
- fkey :: !(ks k)
- fvalue :: !(vs v)
- fremSize :: !FastRem

#### Instances

Instances details

(Show (ks k), Show (vs v)) => Show (FrozenDictionary ks k vs v) Source # |
Instance details Defined in Data.Vector.Hashtables.Internal Methods showsPrec :: Int -> FrozenDictionary ks k vs v -> ShowS Source # show :: FrozenDictionary ks k vs v -> String Source # showList :: [FrozenDictionary ks k vs v] -> ShowS Source #
(Eq (ks k), Eq (vs v)) => Eq (FrozenDictionary ks k vs v) Source # |
Instance details Defined in Data.Vector.Hashtables.Internal Methods (==) :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool Source # (/=) :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool Source #
(Ord (ks k), Ord (vs v)) => Ord (FrozenDictionary ks k vs v) Source # |

Instance details

Defined in Data.Vector.Hashtables.Internal

Methods

compare :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Ordering Source #

(<) :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool Source #

(<=) :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool Source #

(>) :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool Source #

(>=) :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool Source #

max :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v Source #

min :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v Source #

findElem :: forall (ks :: Type -> Type) k (vs :: Type -> Type) v. (Vector ks k, Vector vs v, Hashable k, Eq k) => FrozenDictionary ks k vs v -> k -> Int Source #

O(1) in the best case, O(n) in the worst case. Find dictionary entry by given key in immutable `FrozenDictionary`. If entry not found `-1` returned.

(!~) :: (MVector v a, PrimMonad m) => v (PrimState m) a -> Int -> m a Source #

Infix version of `unsafeRead`.

(!.~) :: Vector v a => v a -> Int -> a Source #

Infix version of `unsafeIndex`.

(<~~) :: (MVector v a, PrimMonad m) => v (PrimState m) a -> Int -> a -> m () Source #

Infix version of `unsafeWrite`.

(!) :: PrimMonad m => MutablePrimArray (PrimState m) Int -> Int -> m Int Source #

Infix version of `readPrimArray`.

(!.) :: PrimArray Int -> Int -> Int Source #

Infix version of `indexPrimArray`.

(<~) :: PrimMonad m => MutablePrimArray (PrimState m) Int -> Int -> Int -> m () Source #

Infix version of `writePrimArray`.

initialize :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m) => Int -> m (Dictionary (PrimState m) ks k vs v) Source #

O(1) Dictionary with given capacity.

clone :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v) Source #

Create a copy of mutable dictionary.

unsafeFreeze :: forall (ks :: Type -> Type) k (vs :: Type -> Type) v m. (Vector ks k, Vector vs v, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v -> m (FrozenDictionary ks k vs v) Source #

O(1) Unsafe convert a mutable dictionary to an immutable one without copying. The mutable dictionary may not be used after this operation.

unsafeThaw :: forall (ks :: Type -> Type) k (vs :: Type -> Type) v m. (Vector ks k, Vector vs v, PrimMonad m) => FrozenDictionary ks k vs v -> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v) Source #

O(1) Unsafely convert immutable `FrozenDictionary` to a mutable `Dictionary` without copying. The immutable dictionary may not be used after this operation.

keys :: forall ks k m (vs :: Type -> Type -> Type) v. (Vector ks k, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k vs v -> m (ks k) Source #

O(n) Retrieve list of keys from `Dictionary`.

values :: forall vs v m (ks :: Type -> Type -> Type) k. (Vector vs v, PrimMonad m) => Dictionary (PrimState m) ks k (Mutable vs) v -> m (vs v) Source #

O(n) Retrieve list of values from `Dictionary`.

at :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m v Source #

O(1) in the best case, O(n) in the worst case. Find value by given key in `Dictionary`. Throws an error if value not found.

at' :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v) Source #

O(1) in the best case, O(n) in the worst case. Find value by given key in `Dictionary`. Like `at'` but return `Nothing` if value not found.

atWithOrElse :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m a. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> (Dictionary (PrimState m) ks k vs v -> Int -> m a) -> (Dictionary (PrimState m) ks k vs v -> m a) -> m a Source #

findEntry :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m Int Source #

O(1) in the best case, O(n) in the worst case. Find dictionary entry by given key. If entry not found `-1` returned.

findEntry_ :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary_ (PrimState m) ks k vs v -> k -> m Int Source #

O(1) in the best case, O(n) in the worst case. Same as `findEntry`, but for `Dictionary_`.

insert :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> v -> m () Source #

O(1) in the best case, O(n) in the worst case. Insert key and value in dictionary by key's hash. If entry with given key found value will be replaced.

insertWithIndex Source #

Arguments

:: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) |
=> Int | Target bucket, key's hash modulo table size
-> Int | Key's hash
-> k | Key
-> v | Value
-> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v) | MutVar with `Dictionary_`
-> Dictionary_ (PrimState m) ks k vs v | `Dictionary_` itself
-> Int |
-> m () |

addOrResize Source #

Arguments

:: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) |
=> Int | Target bucket, key's hash modulo table size
-> Int | Key's hash
-> k | Key
-> v | Value
-> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v) | MutVar with `Dictionary_`
-> Dictionary_ (PrimState m) ks k vs v | `Dictionary_` itself
-> m () |

add :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Int -> Int -> Int -> k -> v -> Dictionary_ (PrimState m) ks k vs v -> m () Source #

resize Source #

Arguments

:: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) |
=> Dictionary_ (PrimState m) ks k vs v | The original `Dictionary_`
-> Int |
-> Int | Key's hash
-> k | Key
-> v | Value
-> m (Dictionary_ (PrimState m) ks k vs v) |

class DeleteEntry (xs :: Type -> Type -> Type) where Source #

Methods

deleteEntry :: (MVector xs x, PrimMonad m) => xs (PrimState m) x -> Int -> m () Source #

#### Instances

Instances details

DeleteEntry MVector Source # |
Instance details Defined in Data.Vector.Hashtables.Internal Methods deleteEntry :: (MVector MVector x, PrimMonad m) => MVector (PrimState m) x -> Int -> m () Source #
DeleteEntry MVector Source # |
Instance details Defined in Data.Vector.Hashtables.Internal Methods deleteEntry :: (MVector MVector x, PrimMonad m) => MVector (PrimState m) x -> Int -> m () Source #
DeleteEntry MVector Source # |
Instance details Defined in Data.Vector.Hashtables.Internal Methods deleteEntry :: (MVector MVector x, PrimMonad m) => MVector (PrimState m) x -> Int -> m () Source #

delete :: forall k (ks :: Type -> Type -> Type) (vs :: Type -> Type -> Type) v m. (Eq k, MVector ks k, MVector vs v, Hashable k, PrimMonad m, DeleteEntry ks, DeleteEntry vs) => Dictionary (PrimState m) ks k vs v -> k -> m () Source #

O(1) in the best case, O(n) in the worst case. Delete entry from `Dictionary` by given key.

deleteWithIndex :: forall k (ks :: Type -> Type -> Type) (vs :: Type -> Type -> Type) v m. (Eq k, MVector ks k, MVector vs v, Hashable k, PrimMonad m, DeleteEntry ks, DeleteEntry vs) => Int -> Int -> Dictionary_ (PrimState m) ks k vs v -> k -> Int -> Int -> m () Source #

lookup :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v) Source #

O(1) in the best case, O(n) in the worst case. Find value by given key in `Dictionary`. Like `lookup'` but return `Nothing` if value not found.

lookup' :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m v Source #

O(1) in the best case, O(n) in the worst case. Find value by given key in `Dictionary`. Throws an error if value not found.

lookupIndex :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe Int) Source #

O(1) in the best case, O(n) in the worst case. Lookup the index of a key, which is its zero-based index in the sequence sorted by keys. The index is a number from 0 up to, but not including, the size of the dictionary.

null :: forall (ks :: Type -> Type -> Type) k m (vs :: Type -> Type -> Type) v. (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Bool Source #

O(1) Return `True` if dictionary is empty, `False` otherwise.

length :: forall (ks :: Type -> Type -> Type) k m (vs :: Type -> Type -> Type) v. (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Int Source #

O(1) Return the number of non-empty entries of dictionary.

size :: forall (ks :: Type -> Type -> Type) k m (vs :: Type -> Type -> Type) v. (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Int Source #

O(1) Return the number of non-empty entries of dictionary. Synonym of `length`.

member :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m Bool Source #

O(1) in the best case, O(n) in the worst case. Return `True` if the specified key is present in the dictionary, `False` otherwise.

findWithDefault :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> v -> k -> m v Source #

O(1) in the best case, O(n) in the worst case. The expression ``findWithDefault` ht def k` returns the value at key `k` or returns default value `def` when the key is not in the dictionary.

upsert :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> v) -> k -> m () Source #

O(1) in the best case, O(n) in the worst case. The expression (``upsert` ht f k`) updates or inserts the value `x` at `k`.

It's a responsibility of `MVector` `vs` to force evaluation of the updated value. Unboxed / storable vectors do it automatically. If you use boxed vectors, consider employing strict ones from `strict-containers` to eliminate potential accumulation of thunks.

    let f _ = "c"
    ht <- fromList [(5,"a"), (3,"b")]
    upsert ht f 7
    toList ht
    [(3, "b"), (5, "a"), (7, "c")]

    ht <- fromList [(5,"a"), (3,"b")]
    upsert ht f 5
    toList ht
    [(3, "b"), (5, "c")]

alter :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> Maybe v) -> k -> m () Source #

O(1) in the best case, O(n) in the worst case. The expression (``alter` ht f k`) alters the value `x` at `k`, or absence thereof. `alter` can be used to insert, delete, or update a value in a `Dictionary`.

It's a responsibility of `MVector` `vs` to force evaluation of the updated value. Unboxed / storable vectors do it automatically. If you use boxed vectors, consider employing strict ones from `strict-containers` to eliminate potential accumulation of thunks.

    let f _ = Nothing
    ht <- fromList [(5,"a"), (3,"b")]
    alter ht f 7
    toList ht
    [(3, "b"), (5, "a")]

    ht <- fromList [(5,"a"), (3,"b")]
    alter ht f 5
    toList ht
    [(3 "b")]

    let f _ = Just "c"
    ht <- fromList [(5,"a"), (3,"b")]
    alter ht f 7
    toList ht
    [(3, "b"), (5, "a"), (7, "c")]

    ht <- fromList [(5,"a"), (3,"b")]
    alter ht f 5
    toList ht
    [(3, "b"), (5, "c")]

alterM :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> m (Maybe v)) -> k -> m () Source #

O(1) in the best case, O(n) in the worst case. The expression (``alterM` ht f k`) alters the value `x` at `k`, or absence thereof. `alterM` can be used to insert, delete, or update a value in a `Dictionary` in the same ``PrimMonad` m`.

# Combine

union :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v) Source #

O(min n m) in the best case, O(min n m * max n m) in the worst case. The union of two maps. If a key occurs in both maps, the mapping from the first will be the mapping in the result.

unionWith :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => (v -> v -> v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v) Source #

O(min n m) in the best case, O(min n m * max n m) in the worst case. The union of two maps. The provided function (first argument) will be used to compute the result.

unionWithKey :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => (k -> v -> v -> v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v) Source #

O(min n m) in the best case, O(min n m * max n m) in the worst case. The union of two maps. If a key occurs in both maps, the provided function (first argument) will be used to compute the result.

# Difference and intersection

difference :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v w m. (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v) Source #

O(n) in the best case, O(n * m) in the worst case. Difference of two tables. Return elements of the first table not existing in the second.

differenceWith :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v w m. (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => (v -> w -> Maybe v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v) Source #

O(n) in the best case, O(n * m) in the worst case. Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. If it returns `Nothing`, the element is discarded (proper set difference). If it returns (``Just` y`), the element is updated with a new value `y`.

intersection :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v w m. (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v) Source #

O(n) in the best case, O(n * m) in the worst case. Intersection of two maps. Return elements of the first map for keys existing in the second.

intersectionWith :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v1 v2 v3 m. (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k) => (v1 -> v2 -> v3) -> Dictionary (PrimState m) ks k vs v1 -> Dictionary (PrimState m) ks k vs v2 -> m (Dictionary (PrimState m) ks k vs v3) Source #

Intersection of two maps. If a key occurs in both maps the provided function is used to combine the values from the two maps.

intersectionWithKey :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v1 v2 v3 m. (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k) => (k -> v1 -> v2 -> v3) -> Dictionary (PrimState m) ks k vs v1 -> Dictionary (PrimState m) ks k vs v2 -> m (Dictionary (PrimState m) ks k vs v3) Source #

Intersection of two maps. If a key occurs in both maps the provided function is used to combine the values from the two maps.

# List conversions

fromList :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => [(k, v)] -> m (Dictionary (PrimState m) ks k vs v) Source #

O(n) Convert list to a `Dictionary`.

toList :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> m [(k, v)] Source #

O(n) Convert `Dictionary` to a list.

# Extras

primesWithFastRem :: Vector (Int, Int, Int) Source #

This data is auto-generated by GenPrimes.hs. The vector contains tuples (p, m, s) such that p is prime and (assuming 64-bit architecture) for every n >= 0 it holds that n ``quot`` p = (n * m) ``shiftR`` (64 + s), enabling faster computation of remainders.

getFastRem :: Int -> FastRem Source #

data FastRem Source #

For 64-bit architectures `frmPrime` is a prime number such that for each `n` >= 0 it holds that `n` ``quot`` `frmPrime` = (n * `_frmMulHi`) ``shiftR`` (64 + s).

Constructors

FastRem |

Fields

- frmPrime :: !Int
- _frmMulHi :: !Int
- _frmShift :: !Int

#### Instances

Instances details

Show FastRem Source # |
Instance details Defined in Data.Vector.Hashtables.Internal Methods showsPrec :: Int -> FastRem -> ShowS Source # show :: FastRem -> String Source # showList :: [FastRem] -> ShowS Source #
Eq FastRem Source # |
Instance details Defined in Data.Vector.Hashtables.Internal Methods (==) :: FastRem -> FastRem -> Bool Source # (/=) :: FastRem -> FastRem -> Bool Source #
Ord FastRem Source # |
Instance details Defined in Data.Vector.Hashtables.Internal Methods compare :: FastRem -> FastRem -> Ordering Source # (<) :: FastRem -> FastRem -> Bool Source # (<=) :: FastRem -> FastRem -> Bool Source # (>) :: FastRem -> FastRem -> Bool Source # (>=) :: FastRem -> FastRem -> Bool Source # max :: FastRem -> FastRem -> FastRem Source # min :: FastRem -> FastRem -> FastRem Source #

fastRem :: Int -> FastRem -> Int Source #