HashtablesPlus

Data Structures

type Map a k v = a RealWorld k v

A type synonym for an IOHashTable with Algorithm a.

E.g.:

 type CuckooTable k v = Map Cuckoo k v

data Set a v

A set of values, which have instances for Eq and Hashable.

a is the underlying Algorithm, v is the item.

E.g.:

 type CuckooSet v = Set Cuckoo v

Instances

(Algorithm a, Key v) => Delete (Set a v)

(Algorithm a, Key v) => Insert (Set a v)

(Algorithm a, Key v) => Elem (Set a v)

(Algorithm a, Key v) => Collection (Set a v)

data HashRefSet a v

A specialized set of HashRefs.

a is the underlying Algorithm, v is the item.

E.g.:

 type LinearHashRefSet v = HashRefSet Linear v

Instances

Algorithm a => Delete (HashRefSet a v)

Algorithm a => Insert (HashRefSet a v)

Algorithm a => Elem (HashRefSet a v)

Algorithm a => Collection (HashRefSet a v)

data Multimap a k s

A multimap with an underlying Algorithm a, a key k and a set implementation s.

E.g.:

 type BasicMultimap k v = Multimap Basic k (Set Basic v)

If a Sized implementation of set is specified, a more space efficient instance of Delete will be used. E.g.:

 Multimap Basic k (Sized (Set Basic v))

Instances

(Algorithm a, Key k, Delete s) => Delete (Multimap a k (Sized s))

(Algorithm a, Key k, Delete s) => Delete (Multimap a k s)

(Algorithm a, Key k, Insert s) => Insert (Multimap a k s)

(Algorithm a, Key k, Elem s) => Elem (Multimap a k s)

(Algorithm a, Key k, Collection s, ~ * (Value s) (Row s)) => TraverseMulti (Multimap a k s)

(Algorithm a, Key k, Collection s) => Collection (Multimap a k s)

data Sized c

A wrapper over a Collection, which adds null and size functions of O(1) complexity.

E.g.:

 type SizedLinearTable k v = Sized (Map Linear k v)

Instances

Collection c => Null (Sized c)

Collection c => Size (Sized c)

Delete c => Delete (Sized c)

Insert c => Insert (Sized c)

Elem c => Elem (Sized c)

TraverseMulti c => TraverseMulti (Sized c)

Lookup c => Lookup (Sized c)

Collection c => Collection (Sized c)

(Algorithm a, Key k, Delete s) => Delete (Multimap a k (Sized s))

Algorithm

type Algorithm = HashTable

An alias to a HashTable constraint of the "hashtables" library.

Implementations

Aliases of implementations of a class HashTable, which provide different performance and memory consumption characteristics. They are used as parameters to data structures. For more info refer to the documentation on aliased types.

type Basic = HashTable

The fastest, but the most memory-hungry implementation.

type Cuckoo = HashTable

The implementation with a medium performance and memory consumption.

type Linear = HashTable

The implementation with a low performance, but also a low memory consumption.

Interface

type Key k = (Hashable k, Eq k)

A constraint for values usable as hash table key.

type family Row c

A row of a collection. For tables and multitables it's a key-value pair, for sets it's just the item.

type family UniqueKey c

A unique row identifier. For tables it's a key, for multitables it's a key-value pair, for sets it's the item itself.

type family MultiKey c

A non-unique row identifier. For tables and sets there is none, for multitables it's a key.

type family Value c

An item of a collection. For tables and multitables it's a value (from the key-value pair), for sets it's the item.

class Collection c where

Methods

new :: IO c

Create a new collection.

traverse :: c -> (Row c -> IO ()) -> IO ()

Traverse thru all the rows of with side effects.

Instances

Collection c => Collection (Sized c)

Algorithm a => Collection (HashRefSet a v)

(Algorithm a, Key v) => Collection (Set a v)

(Algorithm a, Key k, Collection s) => Collection (Multimap a k s)

(Algorithm a, Key k) => Collection (Map a k v)

toList :: Collection c => c -> IO [Row c]

O(n). Convert a collection to a list.

class Collection c => Lookup c where

Methods

lookup :: c -> UniqueKey c -> IO (Maybe (Value c))

Lookup an item by a unique key.

Instances

Lookup c => Lookup (Sized c)

(Algorithm a, Key k) => Lookup (Map a k v)

class Collection c => TraverseMulti c where

Methods

traverseMulti :: c -> MultiKey c -> (Value c -> IO ()) -> IO ()

Traverse items matching a non-unique key.

Instances

TraverseMulti c => TraverseMulti (Sized c)

(Algorithm a, Key k, Collection s, ~ * (Value s) (Row s)) => TraverseMulti (Multimap a k s)

lookupMulti :: TraverseMulti c => c -> MultiKey c -> IO [Value c]

Lookup multiple items by a non-unique key.

class Collection c => Elem c where

Methods

elem :: c -> UniqueKey c -> IO Bool

Check whether the collection contains a row by the given unique key.

Instances

Elem c => Elem (Sized c)

Algorithm a => Elem (HashRefSet a v)

(Algorithm a, Key v) => Elem (Set a v)

(Algorithm a, Key k, Elem s) => Elem (Multimap a k s)

(Algorithm a, Key k) => Elem (Map a k v)

class Collection c => Insert c where

Methods

insert :: c -> Row c -> IO Bool

Insert a row into a collection.

Returns a boolean signifying whether a new row has been inserted. Note that if a row has been replaced it returns False.

insertFast :: c -> Row c -> IO ()

Same as insert, but avoiding the calculation of the operation result.

Instances

Insert c => Insert (Sized c)

Algorithm a => Insert (HashRefSet a v)

(Algorithm a, Key v) => Insert (Set a v)

(Algorithm a, Key k, Insert s) => Insert (Multimap a k s)

(Algorithm a, Key k) => Insert (Map a k v)

class Collection c => Delete c where

Methods

delete :: c -> UniqueKey c -> IO Bool

Delete a row from a collection by its identifier.

Returns a boolean signifying whether a row has been removed.

deleteFast :: c -> UniqueKey c -> IO ()

Same as delete, but avoiding the calculation of the operation result.

Instances

Delete c => Delete (Sized c)

Algorithm a => Delete (HashRefSet a v)

(Algorithm a, Key v) => Delete (Set a v)

(Algorithm a, Key k, Delete s) => Delete (Multimap a k (Sized s))

(Algorithm a, Key k, Delete s) => Delete (Multimap a k s)

(Algorithm a, Key k) => Delete (Map a k v)

class Collection c => Size c where

Methods

size :: c -> IO Int

Get the size of a collection.

Instances

Collection c => Size (Sized c)

class Collection c => Null c where

Methods

null :: c -> IO Bool

Check whether a collection is empty.

Instances

Collection c => Null (Sized c)