-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Vector clocks for versioning message flows
--   
--   This package provides a ready to use implementation of the vector
--   clock data-structures, which may be used to version messages and
--   determine causality relations between them in a distributed system.
--   
--   See <tt>Fundamentals of Distributed Computing: A Practical Tour of
--   Vector Clock Systems</tt> by R. Baldoni and M. Raynal for an overview
--   of vector clocks.
--   
--   See the README.md file for details.
@package vector-clock
@version 0.2.0


-- | A vector clock implementation in terms of simply-linked lists.
module Data.VectorClock.Simple

-- | A vector clock is, conceptually, an associtive list sorted by the
--   value of the key, where each key appears only once.
data VectorClock a b

-- | <i>O(1)</i>. The empty vector clock.
empty :: VectorClock a b

-- | <i>O(1)</i>. A vector clock with a single element.
singleton :: Ord a => a -> b -> VectorClock a b

-- | <i>O(N)</i>. Insert each entry in the list one at a time.
fromList :: Ord a => [(a, b)] -> VectorClock a b

-- | <i>O(1)</i>. Is the vector clock empty?
null :: VectorClock a b -> Bool

-- | <i>O(N)</i>. The number of entries in the vector clock.
size :: VectorClock a b -> Int

-- | <i>O(N)</i>. Is the given key a key in an entry of the vector clock?
member :: Ord a => a -> VectorClock a b -> Bool

-- | <i>O(N)</i>. Lookup the value for a key in the vector clock.
lookup :: Ord a => a -> VectorClock a b -> Maybe b

-- | <i>O(1)</i>. All the entries in the vector clock. Note that this is
--   <i>not</i> the inverse of <a>fromList</a>.
toList :: VectorClock a b -> [(a, b)]

-- | <i>O(N)</i>. Insert or replace the entry for a key.
insert :: Ord a => a -> b -> VectorClock a b -> VectorClock a b

-- | <i>O(N)</i>. Increment the entry for a key.
inc :: (Ord a, Num b) => a -> VectorClock a b -> Maybe (VectorClock a b)

-- | <i>O(N)</i>. Increment the entry for a key. If the key does not exist,
--   assume it was the default.
incWithDefault :: (Ord a, Num b) => a -> VectorClock a b -> b -> VectorClock a b

-- | <i>O(N)</i>. Delete an entry from the vector clock. If the requested
--   entry does not exist, does nothing.
delete :: Ord a => a -> VectorClock a b -> VectorClock a b

-- | <i>O(max(N, M))</i>. Combine two vector clocks entry-by-entry.
combine :: (Ord a, Ord b) => (a -> Maybe b -> Maybe b -> Maybe b) -> VectorClock a b -> VectorClock a b -> VectorClock a b

-- | <i>O(max(N, M))</i>. The maximum of the two vector clocks.
max :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> VectorClock a b

-- | The relations two vector clocks may find themselves in.
data Relation
Causes :: Relation
CausedBy :: Relation
Concurrent :: Relation

-- | <i>O(min(N, M))</i>. The relation between the two vector clocks.
relation :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Relation

-- | <i>O(min(N, M))</i>. Short-hand for <tt>relation vc1 vc2 ==
--   Causes</tt>.
causes :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Bool

-- | <i>O(N)</i>. Check whether the vector clock is valid or not.
valid :: (Ord a, Ord b) => VectorClock a b -> Bool
instance [safe] (Eq a, Eq b) => Eq (VectorClock a b)
instance [safe] Eq Relation
instance [safe] Show Relation
instance [safe] (Binary a, Binary b) => Binary (VectorClock a b)
instance [safe] (Show a, Show b) => Show (VectorClock a b)


-- | An approximate vector clock implementation in terms of
--   <a>Data.VectorClock.Simple</a>.
module Data.VectorClock.Approximate

-- | An approximate vector clock is a normal vector clock, but several keys
--   are mapped to the same value. This can lead to <i>false</i>
--   <i>positive</i> <a>relation</a>s. In other words, the fact that one
--   vector clock causes another is no longer enough information to say
--   that one message causes the other. That said, experimental results
--   show that approximate vector clocks have good results in practice; see
--   the paper by R. Baldoni and M. Raynal for details.
data VectorClock a b

-- | <i>O(1)</i>. The empty vector clock.
empty :: Int -> VectorClock a b

-- | <i>O(1)</i>. A vector clock with a single element.
singleton :: Hashable a => Int -> a -> b -> VectorClock a b

-- | <i>O(N)</i>. Insert each entry in the list one at a time.
fromList :: Hashable a => Int -> [(a, b)] -> VectorClock a b

-- | <i>O(1)</i>. All the entries in the vector clock. Note that this is
--   <i>not</i> the inverse of <a>fromList</a>. Note that the keys are
--   returned <i>hashed</i>.
toList :: VectorClock a b -> [(Int, b)]

-- | <i>O(1)</i>. Is the vector clock empty?
null :: VectorClock a b -> Bool

-- | <i>O(N)</i>. The number of entries in the vector clock. Note that this
--   may be less than the <i>size</i> at construction.
size :: VectorClock a b -> Int

-- | <i>O(N)</i>. Is the given key a key in an entry of the vector clock?
member :: Hashable a => a -> VectorClock a b -> Bool

-- | <i>O(N)</i>. Lookup the value for a key in the vector clock.
lookup :: Hashable a => a -> VectorClock a b -> Maybe b

-- | <i>O(N)</i>. Insert or replace the entry for a key.
insert :: Hashable a => a -> b -> VectorClock a b -> VectorClock a b

-- | <i>O(N)</i>. Increment the entry for a key.
inc :: (Hashable a, Num b) => a -> VectorClock a b -> Maybe (VectorClock a b)

-- | <i>O(N)</i>. Increment the entry for a key. If the key does not exist,
--   assume it was the default.
incWithDefault :: (Hashable a, Num b) => a -> VectorClock a b -> b -> VectorClock a b

-- | <i>O(N)</i>. Delete an entry from the vector clock. If the requested
--   entry does not exist, does nothing.
delete :: Hashable a => a -> VectorClock a b -> VectorClock a b

-- | <i>O(max(N, M))</i>. Combine two vector clocks entry-by-entry. The
--   size of the resulting vector clock is the maximum of the sizes of the
--   given ones.
combine :: Ord b => (Int -> Maybe b -> Maybe b -> Maybe b) -> VectorClock a b -> VectorClock a b -> VectorClock a b

-- | <i>O(max(N, M))</i>. The maximum of the two vector clocks.
max :: Ord b => VectorClock a b -> VectorClock a b -> VectorClock a b

-- | The relations two vector clocks may find themselves in.
data Relation
Causes :: Relation
CausedBy :: Relation
Concurrent :: Relation

-- | <i>O(min(N, M))</i>. The relation between the two vector clocks.
relation :: Ord b => VectorClock a b -> VectorClock a b -> Relation

-- | <i>O(min(N, M))</i>. Short-hand for <tt>relation vc1 vc2 ==
--   Causes</tt>.
causes :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Bool

-- | <i>O(N)</i>. Check whether the vector clock is valid or not.
valid :: Ord b => VectorClock a b -> Bool
instance Binary b => Binary (VectorClock a b)
instance Show b => Show (VectorClock a b)
instance Eq b => Eq (VectorClock a b)


-- | A vector clock implementation.
--   
--   This module re-exports <a>Data.VectorClock.Simple</a>, which is the
--   fully-featured vector clock library. If you wish to use approximate
--   vector clocks, which are significantly smaller and have bounded size,
--   but are not exact, use <a>Data.VectorClock.Approximate</a> instead.
--   
--   See <tt>Fundamentals of Distributed Computing: A Practical Tour of
--   Vector Clock Systems</tt> by R. Baldoni and M. Raynal for an overview
--   of vector clocks.
module Data.VectorClock