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


-- | Boyer-Moore Majority Vote Algorithm
--   
--   The Boyer-Moore Majority Vote Algorithm determines if there in a list
--   of votes is a candidate that holds more than half of the majority, and
--   if so, finds this candidate. It does so in time linear in the length
--   of the input list and constant memory. For a detailed description of
--   the algorithm, see these papers:
--   
--   <ul>
--   <li>Wim H. Hesselink, "<i>The Boyer-Moore Majority Vote
--   Algorithm</i>", 2005;</li>
--   <li>Robert S. Boyer and J. Strother Moore, "<i>MJRTY - A Fast Majority
--   Vote Algorithm</i>", 1982.</li>
--   </ul>
@package majority
@version 1.1


module Algorithms.Majority

-- | <i>O(length xs)</i>, Determines if there in a list of votes <i>xs</i>
--   is a candidate that has more than half of the votes, and if so,
--   returns that canditate.
--   
--   E.g. applying <tt>majority</tt> on the string <tt>"AAACCBBCCCBCC"</tt>
--   yields <tt>Just 'C'</tt>, since <tt>'C'</tt> has 7 out of 13 votes.
majority :: Eq a => [a] -> Maybe a