-- 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 Fundamentals of Distributed Computing: A Practical Tour of -- Vector Clock Systems 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.1 -- | 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 -- | O(1). The empty vector clock. empty :: VectorClock a b -- | O(1). A vector clock with a single element. singleton :: Ord a => a -> b -> VectorClock a b -- | O(N). Insert each entry in the list one at a time. fromList :: Ord a => [(a, b)] -> VectorClock a b -- | O(1). Is the vector clock empty? null :: VectorClock a b -> Bool -- | O(N). The number of entries in the vector clock. size :: VectorClock a b -> Int -- | O(N). Is the given key a key in an entry of the vector clock? member :: Ord a => a -> VectorClock a b -> Bool -- | O(N). Lookup the value for a key in the vector clock. lookup :: Ord a => a -> VectorClock a b -> Maybe b -- | O(1). All the entries in the vector clock. Note that this is -- not the inverse of fromList. toList :: VectorClock a b -> [(a, b)] -- | O(N). Insert or replace the entry for a key. insert :: Ord a => a -> b -> VectorClock a b -> VectorClock a b -- | O(N). Increment the entry for a key. inc :: (Ord a, Num b) => a -> VectorClock a b -> Maybe (VectorClock a b) -- | O(N). 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 -- | O(N). 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 -- | O(max(N, M)). 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 -- | O(max(N, M)). The maximum of the two vector clocks. max :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> VectorClock a b -- | O(M). If vc2 causes vc1, compute the smallest -- vc3 s.t. max vc3 vc2 == vc1. Note that the -- first parameter is the newer vector clock. diff :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Maybe (VectorClock a b) -- | The relations two vector clocks may find themselves in. data Relation Causes :: Relation CausedBy :: Relation Concurrent :: Relation -- | O(min(N, M)). The relation between the two vector clocks. relation :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Relation -- | O(min(N, M)). Short-hand for relation vc1 vc2 == -- Causes. causes :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Bool -- | O(N). Check whether the vector clock is valid or not. valid :: (Ord a, Ord b) => VectorClock a b -> Bool instance [safe] Typeable2 VectorClock instance [safe] (Eq a, Eq b) => Eq (VectorClock a b) instance [safe] (Data a, Data b) => Data (VectorClock a b) instance [safe] Generic (VectorClock a b) instance [safe] Eq Relation instance [safe] Show Relation instance [safe] Datatype D1VectorClock instance [safe] Constructor C1_0VectorClock instance [safe] Selector S1_0_0VectorClock instance [safe] Traversable (VectorClock a) instance [safe] Functor (VectorClock a) instance [safe] Foldable (VectorClock a) 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 -- Data.VectorClock.Simple. 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 false -- positive relations. 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 -- | O(1). The empty vector clock. empty :: Int -> VectorClock a b -- | O(1). A vector clock with a single element. singleton :: Hashable a => Int -> a -> b -> VectorClock a b -- | O(N). Insert each entry in the list one at a time. fromList :: Hashable a => Int -> [(a, b)] -> VectorClock a b -- | O(1). All the entries in the vector clock. Note that this is -- not the inverse of fromList. Note that the keys are -- returned hashed. toList :: VectorClock a b -> [(Int, b)] -- | O(1). Is the vector clock empty? null :: VectorClock a b -> Bool -- | O(N). The number of entries in the vector clock. Note that this -- may be less than the size at construction. size :: VectorClock a b -> Int -- | O(N). Is the given key a key in an entry of the vector clock? member :: Hashable a => a -> VectorClock a b -> Bool -- | O(N). Lookup the value for a key in the vector clock. lookup :: Hashable a => a -> VectorClock a b -> Maybe b -- | O(N). Insert or replace the entry for a key. insert :: Hashable a => a -> b -> VectorClock a b -> VectorClock a b -- | O(N). Increment the entry for a key. inc :: (Hashable a, Num b) => a -> VectorClock a b -> Maybe (VectorClock a b) -- | O(N). 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 -- | O(N). 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 -- | O(max(N, M)). 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 -- | O(max(N, M)). The maximum of the two vector clocks. max :: Ord b => VectorClock a b -> VectorClock a b -> VectorClock a b -- | O(M). If vc2 causes vc1, compute the smallest -- vc3 s.t. max vc3 vc2 == vc1. Note that the -- first parameter is the newer vector clock. diff :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Maybe (VectorClock a b) -- | The relations two vector clocks may find themselves in. data Relation Causes :: Relation CausedBy :: Relation Concurrent :: Relation -- | O(min(N, M)). The relation between the two vector clocks. relation :: Ord b => VectorClock a b -> VectorClock a b -> Relation -- | O(min(N, M)). Short-hand for relation vc1 vc2 == -- Causes. causes :: (Ord a, Ord b) => VectorClock a b -> VectorClock a b -> Bool -- | O(N). Check whether the vector clock is valid or not. valid :: Ord b => VectorClock a b -> Bool instance Typeable2 VectorClock instance (Data a, Data b) => Data (VectorClock a b) instance Generic (VectorClock a b) instance Datatype D1VectorClock instance Constructor C1_0VectorClock instance Selector S1_0_0VectorClock instance Selector S1_0_1VectorClock instance Traversable (VectorClock a) instance Functor (VectorClock a) instance Foldable (VectorClock a) 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 Data.VectorClock.Simple, 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 Data.VectorClock.Approximate instead. -- -- See Fundamentals of Distributed Computing: A Practical Tour of -- Vector Clock Systems by R. Baldoni and M. Raynal for an overview -- of vector clocks. module Data.VectorClock