--------------------------------------------------------------------------------
-- Copyright © 2011 National Institute of Aerospace / Galois, Inc.
--------------------------------------------------------------------------------

-- | An implementation of the Boyer-Moore Majority Vote Algorithm for Copilot.
--
-- For details of the Boyer-Moore Majority Vote Algorithm see the following
-- papers:
--
-- * Wim H. Hesselink,
-- \"The Boyer-Moore Majority Vote Algorithm\", 2005
--
-- * Robert S. Boyer and J Strother Moore,
-- \"MJRTY - A Fast Majority Vote Algorithm\", 1982

{-# LANGUAGE RebindableSyntax #-}

module Copilot.Library.Voting 
  ( majority, aMajority ) where

import Copilot.Language
import Copilot.Language.Prelude
import qualified Prelude as P

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

majority :: (P.Eq a, Typed a) => [Stream a] -> Stream a
majority []     = badUsage "majority: empty list not allowed"
majority (x:xs) = majority' xs x 1

majority' :: (P.Eq a, Typed a)
   => [Stream a] -> Stream a -> Stream Word32 -> Stream a
majority' []     can _   = can
majority' (x:xs) can cnt =
  local (cnt == 0) $ \ zero -> 
    local (if zero then x else can) $ \ can' ->
      local (if zero || x == can then cnt+1 else cnt-1) $ \ cnt' ->
        majority' xs can' cnt'

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

aMajority :: (P.Eq a, Typed a) => [Stream a] -> Stream a -> Stream Bool
aMajority [] _ = badUsage "aMajority: empty list not allowed"
aMajority xs can =
  let
    cnt = aMajority' 0 xs can
  in
    (cnt * 2) > fromIntegral (length xs)

aMajority' :: (P.Eq a, Typed a)
  => Stream Word32 -> [Stream a] -> Stream a -> Stream Word32
aMajority' cnt []     _   = cnt
aMajority' cnt (x:xs) can =
  local (if x == can then cnt+1 else cnt) $ \ cnt' ->
    aMajority' cnt' xs can