2 files changed, 49 insertions, 0 deletions
diff --git a/src/Storage/Internal.hs b/src/Storage/Internal.hs
index 88741e0..76adaab 100644
--- a/src/Storage/Internal.hs
+++ b/src/Storage/Internal.hs
@@ -86,6 +86,15 @@ showRefDigest = B.concat . map showHexByte . BA.unpack
 data Head' c = Head String (Ref' c)
     deriving (Show)
 
+data Stored' c a = Stored (Ref' c) a
+    deriving (Show)
+
+instance Eq (Stored' c a) where
+    Stored r1 _ == Stored r2 _  =  refDigest r1 == refDigest r2
+
+instance Ord (Stored' c a) where
+    compare (Stored r1 _) (Stored r2 _) = compare (refDigest r1) (refDigest r2)
+
 
 type Complete = Identity
 type Partial = Either RefDigest
diff --git a/src/Storage/Merge.hs b/src/Storage/Merge.hs
new file mode 100644
index 0000000..ac80c96
--- /dev/null
+++ b/src/Storage/Merge.hs
@@ -0,0 +1,40 @@
+module Storage.Merge (
+    generations,
+    ancestors,
+    precedes,
+) where
+
+import qualified Data.ByteString.Char8 as BC
+import Data.List
+import Data.Maybe
+import Data.Set (Set)
+import qualified Data.Set as S
+
+import Storage
+import Storage.Internal
+
+previous :: Storable a => Stored a -> [Stored a]
+previous (Stored ref _) = case load ref of
+    Rec items | Just (RecRef dref) <- lookup (BC.pack "SDATA") items
+              , Rec ditems <- load dref ->
+                    map wrappedLoad $ catMaybes $ map (\case RecRef r -> Just r; _ -> Nothing) $
+                        map snd $ filter ((== BC.pack "SPREV") . fst) ditems
+
+              | otherwise ->
+                    map wrappedLoad $ catMaybes $ map (\case RecRef r -> Just r; _ -> Nothing) $
+                        map snd $ filter ((== BC.pack "PREV") . fst) items
+    _ -> []
+
+
+generations :: Storable a => [Stored a] -> [Set (Stored a)]
+generations = unfoldr gen . (,S.empty)
+    where gen (hs, cur) = case filter (`S.notMember` cur) $ previous =<< hs of
+              []    -> Nothing
+              added -> let next = foldr S.insert cur added
+                        in Just (next, (added, next))
+
+ancestors :: Storable a => [Stored a] -> Set (Stored a)
+ancestors = last . (S.empty:) . generations
+
+precedes :: Storable a => Stored a -> Stored a -> Bool
+precedes x y = x `S.member` ancestors [y]