unordered-containers-0.2.1.0: Efficient hashing-based container types

Safe HaskellSafe-Infered

Data.HashMap.Base

Contents

Synopsis

Documentation

data HashMap k v Source

A map from keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

Constructors

Empty 
BitmapIndexed !Bitmap !(Array (HashMap k v)) 
Leaf !Hash !(Leaf k v) 
Full !(Array (HashMap k v)) 
Collision !Hash !(Array (Leaf k v)) 

Instances

Typeable2 HashMap 
Functor (HashMap k) 
Foldable (HashMap k) 
Traversable (HashMap k) 
(Eq k, Eq v) => Eq (HashMap k v) 
(Show k, Show v) => Show (HashMap k v) 
(Eq k, Hashable k) => Monoid (HashMap k v) 
(NFData k, NFData v) => NFData (HashMap k v) 

data Leaf k v Source

Constructors

L !k v 

Instances

(NFData k, NFData v) => NFData (Leaf k v) 

Construction

empty :: HashMap k vSource

O(1) Construct an empty map.

singleton :: Hashable k => k -> v -> HashMap k vSource

O(1) Construct a map with a single element.

Basic interface

null :: HashMap k v -> BoolSource

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

size :: HashMap k v -> IntSource

O(n) Return the number of key-value mappings in this map.

member :: (Eq k, Hashable k) => k -> HashMap k a -> BoolSource

O(log n) Return True if the specified key is present in the map, False otherwise.

lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe vSource

O(log n) Return the value to which the specified key is mapped, or Nothing if this map contains no mapping for the key.

lookupDefaultSource

Arguments

:: (Eq k, Hashable k) 
=> v

Default value to return.

-> k 
-> HashMap k v 
-> v 

O(log n) Return the value to which the specified key is mapped, or the default value if this map contains no mapping for the key.

(!) :: (Eq k, Hashable k) => HashMap k v -> k -> vSource

O(log n) Return the value to which the specified key is mapped. Calls error if this map contains no mapping for the key.

insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k vSource

O(log n) Associate the specified value with the specified key in this map. If this map previously contained a mapping for the key, the old value is replaced.

insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k vSource

O(log n) Associate the value with the key in this map. If this map previously contained a mapping for the key, the old value is replaced by the result of applying the given function to the new and old value. Example:

 insertWith f k v map
   where f new old = new + old

unsafeInsert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k vSource

In-place update version of insert

delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k vSource

O(log n) Remove the mapping for the specified key from this map if present.

adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k vSource

O(log n) Adjust the value tied to a given key in this map only if it is present. Otherwise, leave the map alone.

Combine

Union

union :: (Eq k, Hashable k) => HashMap k v -> HashMap k v -> HashMap k vSource

O(n+m) 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 :: (Eq k, Hashable k) => (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k vSource

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

unions :: (Eq k, Hashable k) => [HashMap k v] -> HashMap k vSource

Construct a set containing all elements from a list of sets.

Transformations

map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2Source

O(n) Transform this map by applying a function to every value.

traverseWithKey :: Applicative f => (k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)Source

O(n) Transform this map by accumulating an Applicative result from every value.

Difference and intersection

difference :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k vSource

O(n+m) Difference of two maps. Return elements of the first map not existing in the second.

intersection :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k vSource

O(n+m) Intersection of two maps. Return elements of the first map for keys existing in the second.

Folds

foldl' :: (a -> v -> a) -> a -> HashMap k v -> aSource

O(n) Reduce this map by applying a binary operator to all elements, using the given starting value (typically the left-identity of the operator). Each application of the operator is evaluated before before using the result in the next application. This function is strict in the starting value.

foldlWithKey' :: (a -> k -> v -> a) -> a -> HashMap k v -> aSource

O(n) Reduce this map by applying a binary operator to all elements, using the given starting value (typically the left-identity of the operator). Each application of the operator is evaluated before before using the result in the next application. This function is strict in the starting value.

foldr :: (v -> a -> a) -> a -> HashMap k v -> aSource

O(n) Reduce this map by applying a binary operator to all elements, using the given starting value (typically the right-identity of the operator).

foldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> aSource

O(n) Reduce this map by applying a binary operator to all elements, using the given starting value (typically the right-identity of the operator).

Filter

filter :: (v -> Bool) -> HashMap k v -> HashMap k vSource

O(n) Filter this map by retaining only elements which values satisfy a predicate.

filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k vSource

O(n) Filter this map by retaining only elements satisfying a predicate.

Conversions

keys :: HashMap k v -> [k]Source

O(n) Return a list of this map's keys. The list is produced lazily.

elems :: HashMap k v -> [v]Source

O(n) Return a list of this map's values. The list is produced lazily.

Lists

toList :: HashMap k v -> [(k, v)]Source

O(n) Return a list of this map's elements. The list is produced lazily.

fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k vSource

O(n) Construct a map with the supplied mappings. If the list contains duplicate mappings, the later mappings take precedence.

fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k vSource

O(n*log n) Construct a map from a list of elements. Uses the provided function to merge duplicate entries.

collision :: Hash -> Leaf k v -> Leaf k v -> HashMap k vSource

Create a Collision value with two Leaf values.

hash :: Hashable a => a -> HashSource

Convenience function. Compute a hash value for the given value.

mask :: Word -> Shift -> BitmapSource

index :: Hash -> Shift -> IntSource

Mask out the bitsPerSubkey bits used for indexing at this level of the tree.

fullNodeMask :: BitmapSource

A bitmask with the bitsPerSubkey least significant bits set.

two :: Shift -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)Source

Create a map from two key-value pairs which hashes don't collide.

unionArrayBy :: (a -> a -> a) -> Bitmap -> Bitmap -> Array a -> Array a -> Array aSource

Strict in the result of f.

update16 :: Array e -> Int -> e -> Array eSource

O(n) Update the element at the given position in this array.

update16' :: Array e -> Int -> e -> ST s (Array e)Source

O(n) Update the element at the given position in this array.

update16With :: Array e -> Int -> (e -> e) -> Array eSource

O(n) Update the element at the given position in this array, by applying a function to it.

updateOrConcatWith :: Eq k => (v -> v -> v) -> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)Source