{-
Encoding of SOLE from the paper found here:

    http://cs.nyu.edu/~dodis/ps/prefix.pdf

The primary difference is the use of 4 as the multplier instead of 3 (plus some other details)
-}
import Data.Word
import Data.Bits ((.&.), shiftR, shiftL)

type B = Integer

b = 5 :: Int

bMask = (1 `shiftL` b) - 1 :: Integer

bigB :: B
bigB = 2 ^ b

eof :: B
eof = bigB + 1


-- !
-- Compose two integers into a larger number by a large B
compose :: Integer -> Integer -> B -> Integer
compose x y b = x * b + y

-- !
-- Decompose a large number into two smaller numbers by a number B
--
-- The decomposition is a division by B returning the (remainder, quotient)
decompose :: Integer -> B -> (Integer, Integer)
decompose v b =  (v `mod` b, v `div` b)


pass1 :: Integer -> [Word32] -> [Integer]
pass1 i [] = let (z, y) = decompose (compose bigB bigB (bigB + 1)) (bigB - 4*i)
             in  [z, y]
pass1 i [x] = let (z, y) = decompose (compose bigB (fromIntegral x) (bigB + 1)) (bigB - 4*i)
              in [z, y]
pass1 i (x:y:xs) = let (v1, v2) = decompose (compose (fromIntegral y) (fromIntegral x) (bigB + 1)) (bigB - 4*i)
                     in  v1 : v2 : (pass1 (i+1) xs)


pass2 :: [Integer] -> [Word32]
pass2 (z:xs) = (fromIntegral z) : (pass2c 1 xs)
  where pass2c :: Integer -> [Integer] -> [Word32]
        pass2c i (y:z:xs) = let w        = z * (bigB + 4*i) + y
                                (w1, w2) = (w `mod` bigB, w `div` bigB)
                            in (fromIntegral w1) : (fromIntegral w2) : (pass2c (i+1) xs)
        pass2c _ [y]      = [fromIntegral (y `shiftR` b), fromIntegral (y .&. bMask) ] -- artificial zero 0 * (bigB + 3*i) inserted
        pass2c _ []       = undefined

encode :: [Word32] -> [Word32]
encode = pass2 . pass1 0

-- !
-- Output: [12,  3,26,1,6]  when b = 5
-- Output: [12,211,51,1,5]  when b = 32
encode_example = encode [5, 7, 31]