hashtables-plus-0.2.0: Extensions for a "hashtables" library

HashtablesPlus

Synopsis

# Data Structures

type Map a k v = a RealWorld k vSource

A type synonym for an `IOHashTable` with `Algorithm` `a`.

E.g.:

``` type CuckooTable k v = `Map` `Cuckoo` k v
```

data Set a v Source

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 Source

A specialized set of `HashRef`s.

`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 Source

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 Source

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

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 = HashTableSource

The fastest, but the most memory-hungry implementation.

The implementation with a medium performance and memory consumption.

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

# Interface

type Key k = (Hashable k, Eq k)Source

A constraint for values usable as hash table key.

type family Row c Source

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 Source

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 Source

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

type family Value c Source

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 whereSource

Methods

new :: IO cSource

Create a new collection.

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

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]Source

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

class Collection c => Lookup c whereSource

Methods

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

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 whereSource

Methods

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

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]Source

Lookup multiple items by a non-unique key.

class Collection c => Elem c whereSource

Methods

elem :: c -> UniqueKey c -> IO BoolSource

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 whereSource

Methods

insert :: c -> Row c -> IO BoolSource

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

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 whereSource

Methods

delete :: c -> UniqueKey c -> IO BoolSource

Delete a row from a collection by its identifier.

Returns a boolean signifying whether a row has been removed.

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

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 whereSource

Methods

size :: c -> IO IntSource

Get the size of a collection.

Instances

 Collection c => Size (Sized c)

class Collection c => Null c whereSource

Methods

null :: c -> IO BoolSource

Check whether a collection is empty.

Instances

 Collection c => Null (Sized c)