packages feed

set-cover 0.1.1 → 0.1.1.1

raw patch · 6 files changed

+116/−156 lines, 6 filesdep +llvm-dsldep ~comfort-arraydep ~containersdep ~knead

Dependencies added: llvm-dsl

Dependency ranges changed: comfort-array, containers, knead, llvm-extra, llvm-tf, random, storable-endian, utility-ht

Files

example/Queen8.hs view
@@ -47,7 +47,7 @@ Since the search algorithm treats every element the same way, the generic algorithm chooses in every step a row, a column or a diagonal-where there the least possibilities to place a queen.+with the smallest number of possibilities to place a queen. -} assign :: Int -> Int -> Assign assign i j =
set-cover.cabal view
@@ -1,10 +1,11 @@+Cabal-Version:    2.2 Name:             set-cover-Version:          0.1.1-License:          BSD3+Version:          0.1.1.1+License:          BSD-3-Clause License-File:     LICENSE Author:           Henning Thielemann, Helmut Podhaisky Maintainer:       Henning Thielemann <haskell@henning-thielemann.de>-Homepage:         http://hub.darcs.net/thielema/set-cover/+Homepage:         https://hub.darcs.net/thielema/set-cover/ Category:         Math, Algorithms Synopsis:         Solve exact set cover problems like Sudoku, 8 Queens, Soma Cube, Tetris Cube Description:@@ -29,7 +30,6 @@   There is also an experimental implementation using LLVM and @knead@.   Do not rely on that interface in released packages. Tested-With:      GHC==7.4.2, GHC==7.6.3, GHC==7.8.2-Cabal-Version:    >=1.8 Build-Type:       Simple Extra-Source-Files:   Changes.md@@ -40,32 +40,33 @@   Default:     False  Flag llvm-  Description: Enable efficient signal processing using LLVM+  Description: Enable efficient array processing using LLVM   Manual:      True   Default:     False  Source-Repository this-  Tag:         0.1.1+  Tag:         0.1.1.1   Type:        darcs-  Location:    http://hub.darcs.net/thielema/set-cover/+  Location:    https://hub.darcs.net/thielema/set-cover/  Source-Repository head   Type:        darcs-  Location:    http://hub.darcs.net/thielema/set-cover/+  Location:    https://hub.darcs.net/thielema/set-cover/  Library   Build-Depends:     psqueues >=0.2 && <0.3,-    enummapset >=0.1 && <0.7,-    transformers >=0.2 && <0.6,+    enummapset >=0.1 && <0.8,+    transformers >=0.2 && <0.7,     array >=0.4 && <0.6,-    containers >=0.4 && <0.7,+    containers >=0.4 && <0.8,     non-empty >=0.2 && <0.4,     semigroups >=0.1 && <1.0,     utility-ht >=0.0.12 && <0.1,     prelude-compat ==0.*,     base >=4 && <5 +  Default-Language: Haskell98   GHC-Options:      -Wall   Hs-Source-Dirs:   src   Exposed-Modules:@@ -89,13 +90,14 @@    If flag(llvm)     Build-Depends:-      knead >=0.4 && <0.6,-      llvm-extra >=0.10 && <0.11,-      llvm-tf >=9.2 && <9.3,+      knead >=1.0 && <1.1,+      llvm-dsl >=0.1 && <0.2,+      llvm-extra >=0.11 && <0.12,+      llvm-tf >=9.2 && <17.1,       tfp >=1.0 && <1.1,-      comfort-array >=0.3 && <0.5,+      comfort-array >=0.3 && <0.6,       storable-record >=0.0.5 && <0.1,-      storable-endian >=0.2.6 && <0.3,+      storable-endian >=0.2.5 && <0.3,       bool8 >=0.0 && <0.1,       lazyio >=0.1 && <0.2     Exposed-Modules:@@ -109,7 +111,7 @@   Type: exitcode-stdio-1.0   Build-Depends:     set-cover,-    transformers >=0.2 && <0.6,+    transformers >=0.2 && <0.7,     enummapset,     containers,     array >=0.1 && <0.6,@@ -122,7 +124,8 @@     Hs-Source-Dirs: test/knead   Else     Hs-Source-Dirs: test/plain-  GHC-Options:    -Wall+  Default-Language: Haskell98+  GHC-Options:      -Wall   Other-Modules:     Mastermind.Test     Mastermind.Guess@@ -130,158 +133,136 @@     Test.Knead     Test.Utility +Common example+  Default-Language: Haskell98+  GHC-Options:    -Wall+  Hs-Source-Dirs: example+  Build-Depends:+    set-cover,+    utility-ht,+    base+ Executable tetris-cube+  Import: example   If flag(buildExamples)     Build-Depends:       haha >=0.3.1 && <0.4,       pooled-io >=0.0 && <0.1,-      set-cover,-      containers,-      utility-ht,-      base+      containers   Else     Buildable: False-  GHC-Options:    -Wall -rtsopts -threaded-  Hs-Source-Dirs: example+  GHC-Options:    -rtsopts -threaded   Main-Is: TetrisCube.hs   Other-Modules:     Utility  Executable soma-cube+  Import: example   If flag(buildExamples)     Build-Depends:-      set-cover,-      containers,-      utility-ht,-      base+      containers   Else     Buildable: False-  GHC-Options:    -Wall -rtsopts -threaded-  Hs-Source-Dirs: example+  GHC-Options:    -rtsopts -threaded   Main-Is: Soma.hs  Executable queen8+  Import: example   If flag(buildExamples)     Build-Depends:-      set-cover,-      containers,       array >=0.1 && <0.6,-      utility-ht,-      base+      containers   Else     Buildable: False-  GHC-Options:    -Wall -rtsopts -threaded-  Hs-Source-Dirs: example+  GHC-Options:    -rtsopts -threaded   Main-Is: Queen8.hs  Executable sudoku-setcover+  Import: example   If flag(buildExamples)     Build-Depends:-      set-cover,       haha >=0.3.1 && <0.4,-      random >=1.0 && <1.2,-      transformers >=0.2 && <0.6,-      containers,+      random >=1.0 && <1.3,+      transformers >=0.2 && <0.7,       array >=0.1 && <0.6,-      utility-ht,-      base+      containers   Else     Buildable: False-  GHC-Options:    -Wall -rtsopts -threaded-  Hs-Source-Dirs: example+  GHC-Options:      -rtsopts -threaded   Main-Is: Sudoku.hs   Other-Modules: Random, Mastermind.Utility  Executable lcube+  Import: example   If flag(buildExamples)     Build-Depends:-      set-cover,       pooled-io >=0.0 && <0.1,-      containers,-      utility-ht,-      base+      containers   Else     Buildable: False-  GHC-Options:    -Wall -rtsopts -threaded-  Hs-Source-Dirs: example+  GHC-Options:    -rtsopts -threaded   Main-Is: LCube.hs   Other-Modules:     Utility  Executable baumeister+  Import: example   If flag(buildExamples)     Build-Depends:-      set-cover,-      containers,-      utility-ht,-      base+      containers   Else     Buildable: False-  GHC-Options:    -Wall -rtsopts -threaded-  Hs-Source-Dirs: example+  GHC-Options:    -rtsopts -threaded   Main-Is: Baumeister.hs   Other-Modules:     Utility  Executable lonpos-pyramid+  Import: example   If flag(buildExamples)     Build-Depends:-      set-cover,-      containers,-      utility-ht,-      base+      containers   Else     Buildable: False-  GHC-Options:    -Wall -rtsopts -threaded-  Hs-Source-Dirs: example+  GHC-Options:    -rtsopts -threaded   Main-Is: LonposPyramid.hs   Other-Modules:     Utility  Executable alphametics+  Import: example   If flag(buildExamples)     Build-Depends:-      set-cover,       non-empty >=0.2 && <0.4,-      transformers >=0.2 && <0.6,-      containers,-      utility-ht,-      base+      transformers >=0.2 && <0.7,+      containers   Else     Buildable: False-  GHC-Options:    -Wall -rtsopts -threaded-  Hs-Source-Dirs: example+  GHC-Options:    -rtsopts -threaded   Main-Is: Alphametics.hs  Executable domino+  Import: example   If flag(buildExamples)     Build-Depends:-      set-cover,       unicode >=0.0 && <0.1,-      containers,       semigroups,-      utility-ht,-      base+      containers   Else     Buildable: False-  GHC-Options:    -Wall -rtsopts -threaded-  Hs-Source-Dirs: example+  GHC-Options:    -rtsopts -threaded   Main-Is: Domino.hs  Executable nonogram+  Import: example   If flag(buildExamples)     Build-Depends:-      set-cover,       non-empty >=0.2 && <0.4,       psqueues,       enummapset,-      containers,-      utility-ht,-      base+      containers   Else     Buildable: False-  GHC-Options:    -Wall-  Hs-Source-Dirs: example   Main-Is: Nonogram.hs   Other-Modules:     Nonogram.Example@@ -292,20 +273,16 @@     Nonogram.Base  Executable mastermind-setcover+  Import: example   If flag(buildExamples)     Build-Depends:-      set-cover,-      random >=1.0 && <1.2,-      transformers >=0.2 && <0.6,-      enummapset,-      containers,+      random >=1.0 && <1.3,+      transformers >=0.2 && <0.7,       array >=0.1 && <0.6,-      utility-ht,-      base+      enummapset,+      containers   Else     Buildable: False-  GHC-Options:    -Wall-  Hs-Source-Dirs: example   Main-Is: Mastermind.hs   Other-Modules:     Mastermind.Utility@@ -315,24 +292,20 @@     Random  Executable mastermind-knead+  Import: example   If flag(buildExamples) && flag(llvm)     GHC-Prof-Options: -rtsopts -auto-all     Build-Depends:-      set-cover,       haha >=0.3.1 && <0.4,-      random >=1.0 && <1.2,+      random >=1.0 && <1.3,       lazyio,-      transformers >=0.2 && <0.6,-      enummapset,-      containers,+      transformers >=0.2 && <0.7,       array >=0.1 && <0.6,-      utility-ht,-      base+      enummapset,+      containers   Else     Buildable: False   Extra-Libraries: stdc++-  GHC-Options:    -Wall-  Hs-Source-Dirs: example   Main-Is: MastermindKnead.hs   Other-Modules:     Mastermind.Utility@@ -342,20 +315,16 @@     Random  Benchmark mastermind-benchmark+  Import: example   Type: exitcode-stdio-1.0   Build-Depends:-    set-cover,     timeit,     QuickCheck >=2.5 && <3.0,-    random >=1.0 && <1.2,-    transformers >=0.2 && <0.6,-    enummapset,-    containers,+    random >=1.0 && <1.3,+    transformers >=0.2 && <0.7,     array >=0.1 && <0.6,-    utility-ht,-    base-  GHC-Options:    -Wall-  Hs-Source-Dirs: example+    enummapset,+    containers   Main-Is: Mastermind/Benchmark.hs   Other-Modules:     Mastermind.Test@@ -363,29 +332,24 @@     Mastermind.Utility  Executable pangram+  Import: example   If flag(buildExamples)     Build-Depends:-      set-cover,-      containers,-      base+      containers   Else     Buildable: False-  GHC-Options:    -Wall-  Hs-Source-Dirs: example   Main-Is: Pangram.hs  Executable conway-puzzle+  Import: example   If flag(buildExamples)     Build-Depends:-      set-cover,       pooled-io >=0.0 && <0.1,       transformers,-      containers,-      base+      containers   Else     Buildable: False-  GHC-Options:    -Wall -rtsopts -threaded-  Hs-Source-Dirs: example+  GHC-Options:    -rtsopts -threaded   Main-Is: ConwayPuzzle.hs   Other-Modules:     Utility
src/Math/SetCover/Exact/Knead.hs view
@@ -28,10 +28,10 @@ import Control.Monad (foldM) import Control.Applicative (liftA3, pure, (<$>)) -import qualified Data.Array.Knead.Parameterized.Render as Render-import qualified Data.Array.Knead.Simple.Physical as Phys-import qualified Data.Array.Knead.Simple.Symbolic as Symb-import qualified Data.Array.Knead.Simple.Slice as Slice+import qualified Data.Array.Knead.Symbolic.Render as Render+import qualified Data.Array.Knead.Symbolic.Physical as Phys+import qualified Data.Array.Knead.Symbolic as Symb+import qualified Data.Array.Knead.Symbolic.Slice as Slice import qualified Data.Array.Knead.Shape as Shape import qualified Data.Array.Knead.Expression as Expr import Data.Array.Knead.Expression ((.|.*))
src/Math/SetCover/Exact/Knead/Saturated.hs view
@@ -18,14 +18,14 @@ import Control.Monad (foldM) import Control.Applicative (liftA3, pure, (<$>)) -import qualified Data.Array.Knead.Parameterized.Render as Render-import qualified Data.Array.Knead.Simple.Physical as Phys-import qualified Data.Array.Knead.Simple.Symbolic as Symb-import qualified Data.Array.Knead.Simple.Slice as Slice+import qualified Data.Array.Knead.Symbolic.Render as Render+import qualified Data.Array.Knead.Symbolic.Physical as Phys+import qualified Data.Array.Knead.Symbolic as Symb+import qualified Data.Array.Knead.Symbolic.Slice as Slice import qualified Data.Array.Knead.Shape as Shape-import qualified Data.Array.Knead.Expression.Vector as ExprVec-import qualified Data.Array.Knead.Expression as Expr-import Data.Array.Knead.Expression (Exp, (/=*), (<*), (.&.*), )+import qualified LLVM.DSL.Expression.Vector as ExprVec+import qualified LLVM.DSL.Expression as Expr+import LLVM.DSL.Expression (Exp, (/=*), (<*), (.&.*), )  import qualified Data.Array.Comfort.Boxed as Array import Data.Array.Comfort.Boxed (Array)@@ -137,7 +137,7 @@  incSatX86 :: Exp Counters -> Exp Counters -> Exp Counters incSatX86 =-   Expr.liftTupleM2 (\x y -> fromMaybe incSatGeneric Intr.maybeUAddSat x y)+   Expr.liftReprM2 (\x y -> fromMaybe incSatGeneric Intr.maybeUAddSat x y)  sumRows ::    Symb.Array (SetDim, blockDim) Counters ->@@ -158,7 +158,7 @@    Expr.fromInteger' numCounters  toCounters :: Exp Block -> Exp Counters-toCounters = Expr.liftTupleM LLVM.bitcast+toCounters = Expr.liftReprM LLVM.bitcast  _pickBits :: Exp BitId -> Exp Block -> Exp Counters _pickBits k block =@@ -166,13 +166,13 @@   word16 :: Exp BitId -> Exp Word.Word16-word16 = Expr.liftTupleM LLVM.ext . bitPos+word16 = Expr.liftReprM LLVM.ext . bitPos  toBlock16 :: Exp Block -> Exp Block16-toBlock16 = Expr.liftTupleM LLVM.bitcast+toBlock16 = Expr.liftReprM LLVM.bitcast  fromBlock16 :: Exp Block16 -> Exp Counters-fromBlock16 = Expr.liftTupleM LLVM.bitcast+fromBlock16 = Expr.liftReprM LLVM.bitcast  pickBitsX86 :: Exp BitId -> Exp Block -> Exp Counters pickBitsX86 k block =@@ -212,7 +212,7 @@  extractBlock :: Exp CounterId -> Exp Block -> Exp Subblock extractBlock =-   Expr.liftTupleM2 (\k v -> LLVM.extractelement v =<< LLVM.zext k)+   Expr.liftReprM2 (\k v -> LLVM.extractelement v =<< LLVM.zext k)  flattenCounters ::    Symb.Array (BlockDim, BitDim) Counters ->@@ -223,7 +223,7 @@   bitPos :: Exp BitId -> Exp Subblock-bitPos = Expr.liftTupleM LLVM.bitcast+bitPos = Expr.liftReprM LLVM.bitcast  singleBit :: Exp BitId -> Exp Subblock singleBit = Expr.shl 1 . bitPos
src/Math/SetCover/Exact/Knead/Symbolic.hs view
@@ -18,14 +18,14 @@ import Control.Monad.HT ((<=<)) import Control.Applicative (liftA2, (<$>)) -import qualified Data.Array.Knead.Parameterized.Render as Render-import qualified Data.Array.Knead.Simple.Physical as Phys-import qualified Data.Array.Knead.Simple.Symbolic as Symb-import qualified Data.Array.Knead.Simple.Slice as Slice+import qualified Data.Array.Knead.Symbolic.Render as Render+import qualified Data.Array.Knead.Symbolic.Physical as Phys+import qualified Data.Array.Knead.Symbolic as Symb+import qualified Data.Array.Knead.Symbolic.Slice as Slice import qualified Data.Array.Knead.Shape as Shape-import qualified Data.Array.Knead.Expression as Expr-import Data.Array.Knead.Simple.Symbolic ((!))-import Data.Array.Knead.Expression+import qualified LLVM.DSL.Expression as Expr+import Data.Array.Knead.Symbolic ((!))+import LLVM.DSL.Expression          (Exp, (==*), (<*), xor, (.|.*), (.&.*), )  import qualified Data.Array.Comfort.Shape as ComfortShape@@ -33,8 +33,8 @@ import qualified Data.Array.Comfort.Boxed as Array import Data.Array.Comfort.Boxed (Array) +import qualified LLVM.Extra.Multi.Value.Storable as Storable import qualified LLVM.Extra.Multi.Value as MultiValue-import qualified LLVM.Extra.Storable as Storable import LLVM.Extra.Multi.Value (atom)  import qualified Data.Word as Word
src/Math/SetCover/Exact/Knead/Vector.hs view
@@ -10,11 +10,10 @@ import Control.Monad ((<=<)) import Control.Applicative (liftA2) -import qualified Data.Array.Knead.Expression as Expr+import qualified LLVM.DSL.Expression as Expr -import qualified LLVM.Extra.Storable as Storable+import qualified LLVM.Extra.Multi.Value.Storable as Storable import qualified LLVM.Extra.Multi.Value as MultiValue-import qualified LLVM.Extra.Tuple as Tuple import qualified LLVM.Extra.Arithmetic as A  import qualified LLVM.Core as LLVM@@ -61,11 +60,8 @@       let ptr64 = castPtr ptr       in  liftA2 Block (peekLE ptr64) (peekLE (advancePtr ptr64 1)) -instance Tuple.Value Block where-   type ValueOf Block = LLVM.Value ByteVector-   valueOf = LLVM.valueOf . blockVector- instance MultiValue.C Block where+   type Repr Block = LLVM.Value ByteVector    cons = MultiValue.consPrimitive . blockVector    undef = MultiValue.undefPrimitive    zero = MultiValue.zeroPrimitive@@ -86,8 +82,8 @@    xor = MultiValue.liftM2 LLVM.xor; inv = MultiValue.liftM LLVM.inv  instance Storable.C Block where-   load = Storable.load <=< castBlockPtr-   store b = Storable.store b <=< castBlockPtr+   load = fmap MultiValue.cast . Storable.load <=< castBlockPtr+   store b = Storable.store (MultiValue.cast b) <=< castBlockPtr  castBlockPtr ::    LLVM.Value (Ptr Block) ->@@ -107,7 +103,7 @@  instance BitSet Block where    nullBlock =-      Expr.liftTupleM (\x ->+      Expr.liftReprM (\x ->          A.cmp LLVM.CmpEQ (LLVM.value LLVM.zero) =<< toWord128 x)    blocksFromSets sets =       let (avails, free) = Blocks.blocksFromSets sets@@ -119,5 +115,5 @@             NonEmptyM.sliceVertical . (++ repeat 0)       in  (map sliceRow avails, sliceRow free)    keepMinimumBit =-      Expr.liftTupleM (\x0 ->+      Expr.liftReprM (\x0 ->          do x <- toWord128 x0; fromWord128 =<< A.and x =<< A.neg x)