Data.Vector.Hashtables.Internal

Documentation

type IntArray s = MutablePrimArray s Int

Alias for MutablePrimArray s Int.

newtype Dictionary s ks k vs v

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 k vs v

Represents collection of hashtable internal primitive arrays and vectors.

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

Constructors

Dictionary

Fields

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

getCount :: Int

getFreeList :: Int

getFreeCount :: Int

data FrozenDictionary ks k vs v

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

Constructors

FrozenDictionary

Fields

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

Instances

(Show (ks k), Show (vs v)) => Show (FrozenDictionary ks k vs v)

Defined in Data.Vector.Hashtables.Internal

Methods

showsPrec :: Int -> FrozenDictionary ks k vs v -> ShowS

show :: FrozenDictionary ks k vs v -> String

showList :: [FrozenDictionary ks k vs v] -> ShowS

(Eq (ks k), Eq (vs v)) => Eq (FrozenDictionary ks k vs v)

Defined in Data.Vector.Hashtables.Internal

Methods

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

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

(Ord (ks k), Ord (vs v)) => Ord (FrozenDictionary ks k vs v)

Defined in Data.Vector.Hashtables.Internal

Methods

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

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

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

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

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

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

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

findElem :: (Vector ks k, Vector vs v, Hashable k, Eq k) => FrozenDictionary ks k vs v -> k -> Int

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

Infix version of unsafeRead.

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

Infix version of unsafeIndex.

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

Infix version of unsafeWrite.

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

Infix version of readPrimArray.

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

Infix version of indexPrimArray.

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

Infix version of writePrimArray.

initialize :: (MVector ks k, MVector vs v, PrimMonad m) => Int -> m (Dictionary (PrimState m) ks k vs v)

O(1) Dictionary with given capacity.

clone :: (MVector ks k, MVector vs v, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)

Create a copy of mutable dictionary.

unsafeFreeze :: (Vector ks k, Vector vs v, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v -> m (FrozenDictionary ks k vs v)

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

unsafeThaw :: (Vector ks k, Vector vs v, PrimMonad m) => FrozenDictionary ks k vs v -> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v)

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

keys :: (Vector ks k, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k vs v -> m (ks k)

O(n) Retrieve list of keys from Dictionary.

values :: (Vector vs v, PrimMonad m) => Dictionary (PrimState m) ks k (Mutable vs) v -> m (vs v)

O(n) Retrieve list of values from Dictionary.

at :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m v

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' :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)

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 :: (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 :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m Int

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_ :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary_ (PrimState m) ks k vs v -> k -> m Int

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

insert :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> v -> m ()

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

Arguments

:: (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

Arguments

:: (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 :: (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

Arguments

:: (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 where

Methods

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

Instances

DeleteEntry MVector

Defined in Data.Vector.Hashtables.Internal

Methods

deleteEntry :: (MVector0 MVector x, PrimMonad m) => MVector (PrimState m) x -> Int -> m ()

DeleteEntry MVector

Defined in Data.Vector.Hashtables.Internal

Methods

deleteEntry :: (MVector0 MVector x, PrimMonad m) => MVector (PrimState m) x -> Int -> m ()

DeleteEntry MVector

Defined in Data.Vector.Hashtables.Internal

Methods

deleteEntry :: (MVector0 MVector x, PrimMonad m) => MVector (PrimState m) x -> Int -> m ()

delete :: (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 ()

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

deleteWithIndex :: (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 :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)

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' :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m v

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 :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe Int)

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 :: (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Bool

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

length :: (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Int

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

size :: (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Int

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

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

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 :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> v -> k -> m v

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 :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> v) -> k -> m ()

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 :: (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 ()

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 :: (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 ()

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 :: (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)

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 :: (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)

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 :: (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)

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 :: (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)

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 :: (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)

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 :: (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)

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 :: (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)

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 :: (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)

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 :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => [(k, v)] -> m (Dictionary (PrimState m) ks k vs v)

O(n) Convert list to a Dictionary.

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

O(n) Convert Dictionary to a list.

Extras

primesWithFastRem :: Vector (Int, Int, Int)

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

data FastRem

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

Show FastRem

Defined in Data.Vector.Hashtables.Internal

Methods

showsPrec :: Int -> FastRem -> ShowS

show :: FastRem -> String

showList :: [FastRem] -> ShowS

Eq FastRem

Defined in Data.Vector.Hashtables.Internal

Methods

(==) :: FastRem -> FastRem -> Bool

(/=) :: FastRem -> FastRem -> Bool

Ord FastRem

Defined in Data.Vector.Hashtables.Internal

Methods

compare :: FastRem -> FastRem -> Ordering

(<) :: FastRem -> FastRem -> Bool

(<=) :: FastRem -> FastRem -> Bool

(>) :: FastRem -> FastRem -> Bool

(>=) :: FastRem -> FastRem -> Bool

max :: FastRem -> FastRem -> FastRem

min :: FastRem -> FastRem -> FastRem

fastRem :: Int -> FastRem -> Int