vector-clock-0.1.2: Vector clocks for versioning message flows

Data.VectorClock.Simple

Description

A vector clock implementation in terms of simply-linked lists.

Synopsis

# Usage example

To create a vector clock, start from `empty` and `insert` elements into it. As a shortcut, `fromList` just inserts all the elements in a list, in order.

``` let vc = empty in
let vc' = insert 'a' 1 vc in
let vc'' = insert 'b' 2 vc in
vc'' == fromList [('a', 1), ('b', 2)]
```

Note that, for different keys, the order of insertion does not matter:

``` fromList [('a', 1), ('b', 2)] == fromList [('b', 2), ('a', 1)]
```

Once you have a given vector clock, you can `lookup` its fields, check that keys are `member`s, or convert it back `toList` form.

``` lookup 'a' [('a', 1), ('b', 2)] == Just 1
lookup 'c' [('a', 1), ('b', 2)] == Nothing
```

The main operations that you would do with a vector clcok are to `inc`crement the entry corresponding to the current process and to update the process's vector clock with the `max` of its and the received message's clocks.

``` inc 'a' [('a', 1), ('b', 2)] = Just [('a', 2), ('b', 2)]
max [('a', 1), ('b', 2)] [('c', 3), ('b', 1)] == [('a', 1), ('b', 2), ('c' 3)]
```

Finally, upon receiving different messages, you may wish to discover the `relation`ship, if any, between them. This information could be useful in determining the correct order to process the messages.

``` relation (fromList [('a', 1), ('b', 2)]) (fromList [('a', 2), ('b', 2)]) == Causes
relation (fromList [('a', 2), ('b', 2)]) (fromList [('a', 1), ('b', 2)]) == CausedBy
relation (fromList [('a', 2), ('b', 2)]) (fromList [('a', 1), ('b', 3)]) == Concurrent
```

# Vector clock type

data VectorClock a b Source

A vector clock is, conceptually, an associtive list sorted by the value of the key, where each key appears only once.

Instances

 (Eq a, Eq b) => Eq (VectorClock a b) (Show a, Show b) => Show (VectorClock a b) (Binary a, Binary b) => Binary (VectorClock a b)

# Construction

O(1). The empty vector clock.

singleton :: a -> b -> VectorClock a bSource

O(1). A vector clock with a single element.

fromList :: Ord a => [(a, b)] -> VectorClock a bSource

O(N). Insert each entry in the list one at a time.

# Query

null :: VectorClock a b -> BoolSource

O(1). Is the vector clock empty?

size :: VectorClock a b -> IntSource

O(N). The number of entries in the vector clock.

member :: Ord a => a -> VectorClock a b -> BoolSource

O(N). Is the given key a key in an entry of the vector clock?

lookup :: Ord a => a -> VectorClock a b -> Maybe bSource

O(N). Lookup the value for a key in the vector clock.

toList :: VectorClock a b -> [(a, b)]Source

O(1). All the entries in the vector clock. Note that this is not the inverse of `fromList`.

# Insertion

insert :: Ord a => a -> b -> VectorClock a b -> VectorClock a bSource

O(N). Insert or replace the entry for a key.

inc :: (Ord a, Num b) => a -> VectorClock a b -> Maybe (VectorClock a b)Source

O(N). Increment the entry for a key.

incWithDefault :: (Ord a, Num b) => a -> VectorClock a b -> b -> VectorClock a bSource

O(N). Increment the entry for a key. If the key does not exist, assume it was the default.

# Deletion

delete :: Ord a => a -> VectorClock a b -> VectorClock a bSource

O(N). Delete an entry from the vector clock. If the requested entry does not exist, does nothing.

# Merges

combine :: (Ord a, Ord b) => (a -> Maybe b -> Maybe b -> Maybe b) -> VectorClock a b -> VectorClock a b -> VectorClock a bSource

O(max(N, M)). Combine two vector clocks entry-by-entry.

max :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> VectorClock a bSource

O(max(N, M)). The maximum of the two vector clocks.

# Relations

data Relation Source

The relations two vector clocks may find themselves in.

Constructors

 Causes CausedBy Concurrent

Instances

 Eq Relation Show Relation

relation :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> RelationSource

O(min(N, M)). The relation between the two vector clocks.

causes :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> BoolSource

O(min(N, M)). Short-hand for `relation vc1 vc2 == Causes`.

# Debugging

valid :: (Ord a, Ord b) => VectorClock a b -> BoolSource

O(N). Check whether the vector clock is valid or not.