obdd 0.3.1 → 0.3.2
raw patch · 3 files changed
+54/−52 lines, 3 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- obdd.cabal +3/−2
- src/OBDD/Data.hs +27/−26
- src/OBDD/Operation.hs +24/−24
obdd.cabal view
@@ -1,5 +1,5 @@ Name: obdd-Version: 0.3.1+Version: 0.3.2 Cabal-Version: >= 1.6 Build-type: Simple Synopsis: Ordered Reduced Binary Decision Diagrams@@ -9,7 +9,8 @@ License: GPL License-file: LICENSE Author: Johannes Waldmann-Maintainer: Johannes Waldmann <waldmann@imn.htwk-leipzig.de>+Maintainer: Johannes Waldmann+Homepage: https://github.com/jwaldmann/haskell-obdd library Build-Depends: base==4.*, random, mtl, containers>=0.5, array
src/OBDD/Data.hs view
@@ -1,5 +1,6 @@ {-# language GeneralizedNewtypeDeriving #-} {-# language RecursiveDo #-}+{-# language FlexibleContexts #-} -- | implementation of reduced ordered binary decision diagrams. @@ -62,17 +63,17 @@ -- | assumes total ordering on variables data OBDD v = OBDD- { core :: !(IntMap ( Node v Index ))- + { core :: !(IntMap ( Node v Index ))+ -- , icore :: !(Map ( Node v Index ) Index) , icore :: !(VarIntIntMap v Index)- , next :: !Index- , top :: !Index- + , next :: !Index+ , top :: !Index+ , cache :: !(IntIntMap Index) -- ^ inputs and output for binary op -- (unary will be simulated by binary)- }+ } fold :: Ord v => ( Bool -> a )@@ -149,7 +150,7 @@ } data Node v i = Leaf !Bool- | Branch !v !i !i+ | Branch !v !i !i deriving ( Eq, Ord ) access :: OBDD v -> Node v ( OBDD v )@@ -160,7 +161,7 @@ Nothing -> error "OBDD.Data.access" Just n -> case n of Leaf p -> error "Leaf in core"- Branch v l r -> + Branch v l r -> Branch v ( s { top = l } ) ( s { top = r } ) @@ -228,22 +229,22 @@ return i cached :: Ord v- => (Index, Index) - -> ( State ( OBDD v ) Index )- -> State ( OBDD v ) Index+ => (Index, Index) + -> ( State ( OBDD v ) Index )+ -> State ( OBDD v ) Index cached (l,r) action = do s <- get case IIM.lookup (l, r) $ cache s of Just i -> return i- Nothing -> do- i <- action- s <- get- put $! s { cache = IIM.insert (l, r) i + Nothing -> do+ i <- action+ s <- get+ put $! s { cache = IIM.insert (l, r) i $ cache s }- return i+ return i register :: Ord v- => Node v Index+ => Node v Index -> State ( OBDD v ) Index register n = case n of Leaf False -> return 0@@ -252,18 +253,18 @@ s <- get case VIIM.lookup (v, l, r) ( icore s ) of Just i -> return i- Nothing -> do- i <- fresh- s <- get- put $! s - { core = IM.insert i n $ core s- , icore = VIIM.insert (v, l, r) i + Nothing -> do+ i <- fresh+ s <- get+ put $! s + { core = IM.insert i n $ core s+ , icore = VIIM.insert (v, l, r) i $ icore s- }- return i+ }+ return i checked_register :: Ord v- => Node v Index+ => Node v Index -> State ( OBDD v ) Index checked_register n = case n of Branch v l r -> do
src/OBDD/Operation.hs view
@@ -67,11 +67,11 @@ -> OBDD v -> OBDD v unary op x = make $ do let handle x = cached ( top x, top x ) $ case access x of- Leaf p -> register $ Leaf $ op p- Branch v l r -> do- l' <- handle l- r' <- handle r- register $ Branch v l' r'+ Leaf p -> register $ Leaf $ op p+ Branch v l r -> do+ l' <- handle l+ r' <- handle r+ register $ Branch v l' r' handle x @@ -81,25 +81,25 @@ binary op x y = make $ do let -- register = checked_register -- for testing handle x y = cached (top x, top y) $ case ( access x , access y ) of- ( Leaf p , Leaf q ) -> register $ Leaf $ op p q- ( ax, ay ) -> case comp ax ay of- LT -> do- let Branch v l r = ay- l' <- handle x l- r' <- handle x r- register $ Branch v l' r'- GT -> do- let Branch v l r = ax- l' <- handle l y- r' <- handle r y- register $ Branch v l' r'- EQ -> do- let Branch v1 l1 r1 = ax- Branch v2 l2 r2 = ay- v = if v1 == v2 then v1 else error "OBDD.Operation.handle"- l' <- handle l1 l2- r' <- handle r1 r2- register $ Branch v l' r'+ ( Leaf p , Leaf q ) -> register $ Leaf $ op p q+ ( ax, ay ) -> case comp ax ay of+ LT -> do+ let Branch v l r = ay+ l' <- handle x l+ r' <- handle x r+ register $ Branch v l' r'+ GT -> do+ let Branch v l r = ax+ l' <- handle l y+ r' <- handle r y+ register $ Branch v l' r'+ EQ -> do+ let Branch v1 l1 r1 = ax+ Branch v2 l2 r2 = ay+ v = if v1 == v2 then v1 else error "OBDD.Operation.handle"+ l' <- handle l1 l2+ r' <- handle r1 r2+ register $ Branch v l' r' handle x y -- | remove variables existentially