-------------------------------------------------------------------------------
--- $Id: BatchersBitonicSorter.hs#1 2009/10/01 10:31:09 REDMOND\\satnams $ 
-------------------------------------------------------------------------------
  
module Lava.Samples.BatchersBitonicSorter
where

import Lava
import Xilinx
import Lava.Samples.TwoSorter  

-------------------------------------------------------------------------------
-- This module contains butterfly definitions a la Geraint Jones
-- and Mary Sheeran.
-------------------------------------------------------------------------------

-- Two places one copy of the circuit above the other.
-- The input is split between the two and their outputs
-- are concatentated together.

two :: Monad m => ([a] -> m [b]) -> [a] -> m [b]
two r = halve >-> par2 r r >-> unhalve
 
-------------------------------------------------------------------------------
-- Many twos.

twoN :: Monad m => Int -> ([a] -> m [b]) -> [a] -> m [b]
twoN 0 r = r
twoN n r = two (twoN (n-1) r)

-------------------------------------------------------------------------------

riffle :: Monad m => [a] -> m [a]
riffle = halveList >-> zipList >-> unpair

-------------------------------------------------------------------------------

unriffle :: Monad m => [a] -> m [a]
unriffle = pair >-> unzipList >-> unhalveList

-------------------------------------------------------------------------------
 
ilv :: Monad m => ([a] -> m [b]) -> [a] -> m [b]
ilv r = unriffle >-> two r >-> riffle

-------------------------------------------------------------------------------

ilvN :: Monad m => Int -> ([a] -> m [b]) -> [a] -> m [b]
ilvN 0 r = r
ilvN n r = ilv (ilvN (n-1) r)

-------------------------------------------------------------------------------

evens :: Monad m => ([a] -> m [b]) -> [a] -> m [b]
evens f = chop 2 >-> mapM f >-> concaT

-------------------------------------------------------------------------------

type ButterflyElement m a = [a] -> m [a]
type Butterfly m a = [a] -> m [a]

butterfly :: Monad m => ButterflyElement m a -> Int -> Butterfly m a 
butterfly circuit 1 = circuit
butterfly circuit n
  = ilv (butterfly circuit (n-1)) >-> evens circuit

-------------------------------------------------------------------------------

sortB cmp 1 = cmp
sortB cmp n
  = two (sortB cmp (n-1)) >-> sndList reversE >-> butterfly cmp n

-------------------------------------------------------------------------------

bsort :: Xilinx m bit => Int -> [[bit]] -> m [[bit]]
bsort = sortB twoSorter

-------------------------------------------------------------------------------

bsort_top :: Int -> Int -> Out ()
bsort_top size bw
  = do as <- sequence [input_vec ("a"++show i) (bw-1) downto 0 | 
                       i <- [1..2^size]]
       bs <- bsort size as
       sequence_ [output_vec ("b"++show i) (bs!!(i-1)) (bw-1) downto 0 |
                       i <- [1..2^size]]

-------------------------------------------------------------------------------