/**
 * A quick and dirty implementation of the Moore's Linear Time Majority Vote 
 * Algorithm.  Described here:
 *     http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html
 *
 * Essentially, you use this algorithm if you know one element in a list appears
 * more often then all others combined and you want to know what that element 
 * is.
 * 
 * The upside of this algorithm is that you do a single pass, and you only need 
 * to store a single reference and a counter.  The downside is you have no way 
 * of knowing whether there was in fact a majority.  
 *
 */ 
#include <iostream>
#include <vector>

int main( int argc, char* argv[] ) {

    typedef char VOTE_TYPE;

    // These are the "votes"
    std::string voteStr( "AAACCBBCCCBCC" );
    std::vector<VOTE_TYPE> votes( voteStr.begin(), voteStr.end() );

    VOTE_TYPE currentLeader = 0;
    unsigned int leadCount = 0;

    for ( int i = 0; i < votes.size(); i++ ) {
        if ( leadCount == 0 ) {
            currentLeader = votes[ i ];
            leadCount++;
        } else if ( votes[ i ] == currentLeader ) {
            leadCount++;
        } else {
            leadCount--;
        }
    }

    std::cout << "If there is a total majority, then majority is: " 
              << currentLeader << std::endl;

    return 0;
}