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


-- | Solve exact set cover problems like Sudoku, 8 Queens, Soma Cube, Tetris Cube
--   
--   Solver for exact set cover problems. Included examples: Sudoku,
--   Nonogram, 8 Queens, Domino tiling, Mastermind, Soma Cube, Tetris Cube,
--   Cube of L's, Logika's Baumeister puzzle. The generic algorithm allows
--   to choose between slow but flexible <tt>Set</tt> from
--   <tt>containers</tt> package and fast but cumbersome bitvectors.
--   
--   For getting familiar with the package I propose to study the Queen8
--   example along with <a>Math.SetCover.Exact</a>.
--   
--   Build examples with <tt>cabal install -fbuildExamples</tt>.
--   
--   The package needs only Haskell 98.
@package set-cover
@version 0.0.9

module Math.SetCover.Bit

-- | This class is similar to the <a>Bits</a> class from the <tt>base</tt>
--   package but adds <a>keepMinimum</a> and misses the rotation stuff.
class Ord bits => C bits
empty :: C bits => bits
complement :: C bits => bits -> bits
keepMinimum :: C bits => bits -> bits
xor :: C bits => bits -> bits -> bits
(.&.) :: C bits => bits -> bits -> bits
(.|.) :: C bits => bits -> bits -> bits
difference :: C bits => bits -> bits -> bits
data Sum a b
Sum :: !a -> !b -> Sum a b
bitLeft :: (Bits a, C b) => Int -> Sum a b
bitRight :: (C a, Bits b) => Int -> Sum a b
instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (Math.SetCover.Bit.Sum a b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Math.SetCover.Bit.Sum a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Math.SetCover.Bit.Sum a b)
instance (Math.SetCover.Bit.C a, Math.SetCover.Bit.C b) => Math.SetCover.Bit.C (Math.SetCover.Bit.Sum a b)
instance Math.SetCover.Bit.C GHC.Word.Word8
instance Math.SetCover.Bit.C GHC.Word.Word16
instance Math.SetCover.Bit.C GHC.Word.Word32
instance Math.SetCover.Bit.C GHC.Word.Word64
instance Math.SetCover.Bit.C GHC.Integer.Type.Integer

module Math.SetCover.BitSet
newtype Set bits
Set :: bits -> Set bits
empty :: C bits => Set bits
null :: C bits => Set bits -> Bool
keepMinimum :: C bits => Set bits -> Set bits
disjoint :: C bits => Set bits -> Set bits -> Bool
difference :: C bits => Set bits -> Set bits -> Set bits
instance GHC.Show.Show bits => GHC.Show.Show (Math.SetCover.BitSet.Set bits)
instance GHC.Classes.Ord bits => GHC.Classes.Ord (Math.SetCover.BitSet.Set bits)
instance GHC.Classes.Eq bits => GHC.Classes.Eq (Math.SetCover.BitSet.Set bits)
instance Math.SetCover.Bit.C bits => GHC.Base.Semigroup (Math.SetCover.BitSet.Set bits)
instance Math.SetCover.Bit.C bits => GHC.Base.Monoid (Math.SetCover.BitSet.Set bits)

module Math.SetCover.BitPosition
class C bits => C bits
unpack :: C bits => Set bits -> [Int]
singleton :: (C bits) => Int -> Set bits
bitPosition :: (C bits) => Set bits -> Int
instance Math.SetCover.BitPosition.C GHC.Word.Word8
instance Math.SetCover.BitPosition.C GHC.Word.Word16
instance Math.SetCover.BitPosition.C GHC.Word.Word32
instance Math.SetCover.BitPosition.C GHC.Word.Word64
instance Math.SetCover.BitPosition.C GHC.Integer.Type.Integer
instance (GHC.Real.Integral a, Math.SetCover.BitPosition.C a, Math.SetCover.BitPosition.C b) => Math.SetCover.BitPosition.C (Math.SetCover.Bit.Sum a b)

module Math.SetCover.BitMap
newtype Map bits
Map :: [bits] -> Map bits
[unMap] :: Map bits -> [bits]
fromSet :: C bits => Set bits -> Map bits
add :: C bits => Map bits -> Map bits -> Map bits
inc :: C bits => Set bits -> Map bits -> Map bits
sub :: C bits => Map bits -> Map bits -> Map bits
dec :: C bits => Set bits -> Map bits -> Map bits
intersectionSet :: (C bits) => Map bits -> Set bits -> Map bits
differenceSet :: (C bits) => Map bits -> Set bits -> Map bits
minimumSet :: C bits => Set bits -> Map bits -> Set bits
instance GHC.Show.Show bits => GHC.Show.Show (Math.SetCover.BitMap.Map bits)
instance Math.SetCover.Bit.C bits => GHC.Base.Semigroup (Math.SetCover.BitMap.Map bits)
instance Math.SetCover.Bit.C bits => GHC.Base.Monoid (Math.SetCover.BitMap.Map bits)

module Math.SetCover.Cuboid
data Coords a
Coords :: a -> a -> a -> Coords a
coordsFromString :: [[String]] -> [Coords Int]
coordsFrom2LayerString :: [String] -> [Coords Int]
numberOf2LayerAtoms :: [[String]] -> Int
forNestedCoords :: (Enum a, Num a) => ([z] -> b) -> ([y] -> z) -> ([x] -> y) -> (Coords a -> x) -> Coords a -> b
newtype PackedCoords
PackedCoords :: Int -> PackedCoords
dx :: Num a => Coords a -> Coords a
dy :: Num a => Coords a -> Coords a
dz :: Num a => Coords a -> Coords a
rotations :: Num a => [Coords a -> Coords a]
type Size = Coords Int
unpackCoords :: Size -> PackedCoords -> Coords Int
packCoords :: Size -> Coords Int -> PackedCoords
normalForm :: (Ord a, Num a) => [Coords a] -> [Coords a]

-- | Object must be in <a>normalForm</a>.
size :: [Coords Int] -> Coords Int
move :: Coords Int -> [Coords Int] -> [Coords Int]
allPositions :: Size -> [Coords Int] -> [[Coords Int]]
allOrientations :: (Num a, Ord a) => [Coords a] -> [[Coords a]]
instance GHC.Show.Show Math.SetCover.Cuboid.PackedCoords
instance GHC.Classes.Ord Math.SetCover.Cuboid.PackedCoords
instance GHC.Classes.Eq Math.SetCover.Cuboid.PackedCoords
instance GHC.Show.Show a => GHC.Show.Show (Math.SetCover.Cuboid.Coords a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Math.SetCover.Cuboid.Coords a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Math.SetCover.Cuboid.Coords a)
instance GHC.Base.Functor Math.SetCover.Cuboid.Coords
instance GHC.Base.Applicative Math.SetCover.Cuboid.Coords
instance Data.Foldable.Foldable Math.SetCover.Cuboid.Coords
instance Data.Traversable.Traversable Math.SetCover.Cuboid.Coords


-- | This module provides a solver for exact set cover problems.
--   <a>http://en.wikipedia.org/wiki/Exact_cover</a>
module Math.SetCover.Exact

-- | <a>Assign</a> allows to associate a set with a label. If a particular
--   set is chosen for a set cover, then its label is included in the
--   output of <a>partitions</a>.
--   
--   I have decided to separate sets and labels this way, since it is the
--   easiest way to assign a meaning to a set. If you really want to know
--   the sets in a partition, then you can fill the <a>label</a> field with
--   the set.
data Assign label set
Assign :: label -> set -> Assign label set
[label] :: Assign label set -> label
[labeledSet] :: Assign label set -> set

-- | Construction of a labeled set.
assign :: label -> set -> Assign label set

-- | You may use this to post-process a set of <a>Assign</a>s in order to
--   speedup the solver considerably. You must process the whole set of
--   <a>Assign</a>s at once, i.e. do not process only parts of the
--   assignment list. The output of <a>bitVectorFromSetAssigns</a> should
--   go into the solver as is.
bitVectorFromSetAssigns :: (Ord a) => [Assign label (Set a)] -> [Assign label (Set Integer)]

-- | <tt>partitions [assign '0' set0, assign '1' set1, assign '2'
--   set2]</tt> computes <tt>unions [set0, set1, set2]</tt> and tries to
--   partition the union set using the sets <tt>set0</tt>, <tt>set1</tt>,
--   <tt>set2</tt>. <a>partitions</a> returns all such partitions. If a set
--   is chosen for a partition, then its label is included in the output.
--   E.g. <tt>set0 = Set.fromList [0,1], set1 = Set.fromList [2], set2 =
--   Set.fromList [0,1,2]</tt>, then <a>partitions</a> returns <tt>["01",
--   "2"]</tt>.
--   
--   The order of partitions and the order of labels depends on the
--   implementation and you must not rely on them.
--   
--   You may use <tt>listToMaybe</tt> in order to select only the first
--   solution.
partitions :: Set set => [Assign label set] -> [[label]]

-- | Start the search for partitions on a certain search state. This can be
--   an <a>initState</a> or the result of performing some search
--   <a>step</a>s. In the examples we use this for parallelization: We
--   perform some steps manually and then run <a>search</a> on the results
--   in parallel.
search :: Set set => State label set -> [[label]]

-- | This is the key of the search algorithm. The search algorithm tries to
--   build partitions by adding sets to a partition list successively. A
--   step starts on a partial partition and looks for new sets that could
--   be added. The goal is to avoid to check a set again down in a search
--   branch and to quickly determine search directions that lead to a dead
--   end. To this end a search step selects a certain set element and tries
--   all sets that contain that element and that do not overlap with the
--   partial partition. Practically, <a>step</a> selects an element with
--   the minimal number of non-overlapping sets it is contained in. If this
--   number is zero, then the search can be aborted in this branch.
--   
--   Most oftenly the power of the algorithm originates from the
--   formulation of a problem as a set-cover problem and from the equal
--   treatment of all elements. E.g. in the Soma cube example the algorithm
--   chooses whether to do a case analysis on all bricks that cover a
--   certain position, or to do a case analysis on all positions that are
--   possible for a certain brick.
--   
--   The algorithm might not be extraordinarily fast, but in all cases it
--   consumes only little memory since it only has to maintain the current
--   state of search.
step :: Set set => State label set -> [State label set]

-- | The state of the search. <tt>usedSubsets</tt> contains the partial
--   partition built up so far. <tt>availableSubsets</tt> is the list of
--   sets we can still try to put into a partition. The lists
--   <tt>usedSubsets</tt> and <tt>availableSubsets</tt> are disjoint, but
--   their union is not necessarily equal to the list of initially given
--   sets. There are sets not contained in the partial partition that
--   overlap with the partial partition. Those sets are not available for
--   extending the partition.
--   
--   <tt>freeElements</tt> contains the elements that are not covered by
--   the partial partition in <tt>usedSubsets</tt>. <tt>unions
--   usedSubset</tt> and <tt>freeElements</tt> are disjoint and their union
--   is the set of all elements.
data State label set
State :: [Assign label set] -> set -> [Assign label set] -> State label set
[availableSubsets] :: State label set -> [Assign label set]
[freeElements] :: State label set -> set
[usedSubsets] :: State label set -> [Assign label set]
initState :: Set set => [Assign label set] -> State label set
updateState :: Set set => Assign label set -> State label set -> State label set

-- | This class provides all operations needed for the set cover algorithm.
--   It allows to use the same algorithm both for <tt>containers</tt>'
--   <a>Set</a> and for sets represented by bit vectors.
class Set set
null :: Set set => set -> Bool
disjoint :: Set set => set -> set -> Bool
unions :: Set set => [set] -> set
difference :: Set set => set -> set -> set

-- | Unchecked preconditions: <tt>set</tt> must be a superset of all sets
--   in the assign list. <tt>set</tt> must be non-empty. The list of
--   assignments must be non-empty. The output of assigns must be a
--   subsequence of the input assigns, that is, it must be a subset of the
--   input and it must be in the same order. This requirement was
--   originally needed by <a>minimize</a> for <a>Map</a>, but currently it
--   is not utilized anywhere.
minimize :: Set set => set -> [Assign label set] -> [Assign label set]
instance GHC.Base.Functor (Math.SetCover.Exact.State label)
instance GHC.Classes.Ord a => Math.SetCover.Exact.Set (Data.Set.Internal.Set a)
instance (GHC.Classes.Ord k, Math.SetCover.Exact.Set a) => Math.SetCover.Exact.Set (Data.Map.Internal.Map k a)
instance Math.SetCover.Bit.C a => Math.SetCover.Exact.Set (Math.SetCover.BitSet.Set a)
instance Math.SetCover.Exact.Set Data.IntSet.Internal.IntSet
instance GHC.Base.Functor (Math.SetCover.Exact.Assign label)

module Math.SetCover.Queue
newtype SetId
SetId :: Int -> SetId
data Methods queue set
Methods :: EnumMap SetId set -> queue -> queue -> set -> (EnumSet SetId, queue) -> queue -> EnumMap SetId set -> queue -> queue -> Maybe (EnumSet SetId) -> queue -> Bool -> Methods queue set
[fromEnumMap] :: Methods queue set -> EnumMap SetId set -> queue
[partition] :: Methods queue set -> queue -> set -> (EnumSet SetId, queue)
[difference] :: Methods queue set -> queue -> EnumMap SetId set -> queue
[findMin] :: Methods queue set -> queue -> Maybe (EnumSet SetId)
[null] :: Methods queue set -> queue -> Bool
instance GHC.Enum.Enum Math.SetCover.Queue.SetId


-- | This implementation uses priority queues and avoids full scans through
--   available sets. It can be faster than <a>Math.SetCover.Exact</a> if
--   there is a huge number of sets.
module Math.SetCover.Exact.Priority

-- | <a>Assign</a> allows to associate a set with a label. If a particular
--   set is chosen for a set cover, then its label is included in the
--   output of <a>partitions</a>.
--   
--   I have decided to separate sets and labels this way, since it is the
--   easiest way to assign a meaning to a set. If you really want to know
--   the sets in a partition, then you can fill the <a>label</a> field with
--   the set.
data Assign label set
label :: Assign label set -> label
labeledSet :: Assign label set -> set

-- | Construction of a labeled set.
assign :: label -> set -> Assign label set
partitions :: Methods queue set -> [Assign label set] -> [[label]]
search :: Methods queue set -> State queue label set -> [[label]]
step :: Methods queue set -> State queue label set -> [State queue label set]
data State queue label set
State :: EnumMap SetId (Assign label set) -> queue -> [label] -> State queue label set
[availableSubsets] :: State queue label set -> EnumMap SetId (Assign label set)
[queue] :: State queue label set -> queue
[usedSubsets] :: State queue label set -> [label]
initState :: Methods queue set -> [Assign label set] -> State queue label set
updateState :: Methods queue set -> Assign label set -> State queue label set -> State queue label set
data SetId
queueMap :: Ord a => Methods queue set -> Methods a queue set
queueSet :: Ord a => Methods a
queueBit :: C bits => Methods bits
queueBitPQ :: C bits => Methods bits
