PossibleMajorityCandidate.hs

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ScopedTypeVariables #-}

module Data.Algorithm.PossibleMajorityCandidate where

import Data.Foldable

-- | Compute the possible majority candidate in t
--
-- The result is undefined if t is empty
--
-- Runtime is O(n)
possibleMajorityCandidate :: forall a t. (Eq a, Foldable t) => t a -> a
possibleMajorityCandidate = snd . foldl' loop (0, undefined)
  where
    loop :: (Int, a) -> a -> (Int, a)
    loop (!count,pmc) !a
      | count == 0  = (1, a)
      | a == pmc    = (count+1, pmc)
      | otherwise   = (count-1, pmc)
{-# INLINE possibleMajorityCandidate #-}