function [plain,ssd] = condorcet(election)

% [plain,ssd] = condorcet(election): Plain and SSD Condorcet winners
%     $election$: pairwise matrix or string matrix whose rows are ballots
%                 -- same conventions as $tallies$, below
%     $plain$:   winners (as letters) from Plain Condorcet voting
%     $ssd$:     winners (as letters) from SSD Condorcet voting (BONUS)
%     note: when there are ties, *all* possible answers are returned

    pwm = tallies(election);
    numCandidates = length(pwm);
    [i,j,v] = alldefeats(pwm);

    if diagnostic
        I = sprintf('%2d ', i); II = sprintf(' %c ', char(i + 'A' - 1));
        J = sprintf('%2d ', j); JJ = sprintf(' %c ', char(j + 'A' - 1));
        V = [sprintf('%2d ', v) ' magnitude'];
        disp(str2mat('defeats:', '', [I ' win'],II, '', [J ' lose'],JJ, '', V))
    end

    ssd = char(SSD(pwm) + 'A' - 1); % SSD Condorcet winners

    % find Plain Condorcet winners by using $alldefeats$
        v = [v ; inf]; % extra, different value to avoid falling off the end
        % fast version of $defeats = hist(j,1: numCandidates);$
            defeats = full(sparse(1,j,1)); % number of defeats per candidate
        k = 1;
        % drop all defeats of minimum magnitude until have a winner
        % inv: already dropped $k-1$ smallest defeats
        while min(defeats) > 0
            kk = k;
            % drop all defeats with magnitude $v(k)$
            % inv: already dropped $k:kk-1$
            while v(kk) == v(k)
                defeats(j(k)) = defeats(j(k)) - 1;
                k = k+1;
            end
        end
        plain = char('A' - 1 + find(defeats == 0));

    % find Plain Condorcet winners, bypassing $alldefeats$
        pwm2 = pwm;
        pwm2(pwm <= pwm') = inf; % mark non-defeat entries with $inf$
        % drop all defeats of minimum magnitude until have a winner
        % inv: winners for $pwm2$ = correct answer
        while all(~isinf(min(pwm2)))
            pwm2(pwm2 == min(min(pwm2))) = inf;
        end
        plain2 = char('A' - 1 + find(isinf(min(pwm2))));

    % verify both Plain Condorcet solutions agree
        if ~strcmp(plain, plain2)
            plain, plain2, error('Plain Condorcet solutions disagree');
        end

function t = diagnostic
% t = diagnostic: "print diagnostic output?"  (1 = yes; 0 = no)
    t = logical(1);

function [i,j,v] = alldefeats(pwm)
% [i,j,v] = alldefeats(pwm): defeats in ascending order in pairwise matrix 
%     $pwm$:   pairwise matrix
%     $i,j,v$: $k$-th defeat is $i(k)$ over $j(k)$ with magnitude $v(k)$;
%              $v$ is sorted in ascending order

    pwm(pwm <= pwm') = 0; % eliminate entries that aren't magnitudes of defeats
    [i,j,v] = find(pwm); % find defeats
    % sort defeats in ascending order of magnitude
        [v,order] = sort(v);
        i = i(order);
        j = j(order);

function t = issubset(a,b)
% t = issubset(a,b): "$a$ is a subset of $b$?"

    t = isempty(setdiff(a,b));                                  % solution 1
    t2 = length(setdiff(a,b)) == 0;                             % solution 2
    t3 = all(ismember(a,b));                                    % solution 3
    t4 = logical(1); for i = a, t4 = t4 & any(i == b); end      % solution 4
    if ~isequal(t,t2) | ~isequal(t2,t3) | ~isequal(t3,t4)
        t, t2, t3, t4, error('solutions to $issubset$ disagree');
    end

function pwm = tallies(election)
% pwm = tallies(election): pairwise matrix specified by election$
%     $election$: pairwise matrix or string matrix whose rows are ballots
%
%     the format of a single ballot is the same as for $tally$, below;
%     each ballot is assumed to have the same number of candidates

    pwm = election; % assume $election$ is pairwise matrix
    if ischar(election)
        % concise solution
            pwm = zeros((size(election,2)+1)/2);
            for ballot = election'
                pwm = pwm + tally(ballot');
            end
        % slightly less concise solution
            numCandidates = sum(isletter(election(1,:))); % count #letters
            pwm2 = zeros(numCandidates, numCandidates);
            for i = 1:size(election,1)
                pwm2 = pwm2 + tally(election(i,:));
            end
        % verify both solutions give same answer
            if ~isequal(pwm,pwm2)
                pwm, pwm2, error('solutions to $tallies$ disagree');
            end
    end

function pwm = tally(ballot)
% pwm = tally(ballot): pairwise matrix for single ballot $ballot$
%     $ballot$: a string vector of holding an ordered sequence of candidates
%     + candidates are represented by consecutive letters of the alphabet,
%       starting at $'a'$, and ignoring case ($'a'$ and $'A'$ are the same)
%     + $ballot(1:2:end)$ is the list of candidates
%     $ $ballot(2:2:end)$ holds comparisons $'>'$ and/or $'='$
%
% example: $tally('d>c=e=b>a')$

    % fairly direct, unvectorized solution: look for $'>'$s between candidates
        b = upper(ballot);
        for i = 1:2:length(b)
            for j = 1:2:length(b)
                pwm(b(i)-'A'+1, b(j)-'A'+1) = any(b(i:j) == '>');
            end
        end
    % slightly indirect, vectorized solution using rank idea from lecture
        ballot = upper(ballot);
        candidates = ballot(1:2:end) - 'A' + 1;
        rank = cumsum([1 ballot(2:2:end) == '>']); % smaller rank = more votes
        rank(candidates) = rank;
        rank = repmat(rank, length(candidates), 1);
        pwm2 = rank' < rank;
    % verify both solutions give same answer
        if ~isequal(pwm,pwm2)
            pwm, pwm2, error('solutions to $tally$ disagree');
        end

function top = topmost(pwm)
% top = topmost(pwm): innermost unbeaten sets for pairwise matrix $pwm$
    % find smallest unbeaten set containing each candidate
    % (note: inefficient since each call to $unbeaten$ recomputes $alldefeats$)
        for i = length(pwm):-1:1
            top{i} = unbeaten(pwm,i);
        end
    % throw away redundant sets, i.e. sets that are supersets of other sets
        i = 1;
        % inv: $top{1:i-1}$ is a distinct list of innermost unbeaten sets
        while i ~= 1+length(top)
            j = 1; redundant = 0; 
            % inv: $redundant$ = "$top{i}$ is a superset of a set $top{k}$ for
            %      some $k, i ~= k < j$?"
            while j ~= 1+length(top) & ~redundant
                redundant = i ~= j & issubset(top{j}, top{i});
                j = j+1;
            end
            if redundant
                top(i) = [];
            else
                i = i+1;
            end
        end

function list = unbeaten(pwm,list)
% list = unbeaten(pwm,list): smallest unbeaten set containing $list$
%     $pwm$: pairwise matrix
%     note: $list$ is both a return variable and a parameter

    list = unique(list); % sort and remove duplicates
    [winners,losers,v] = alldefeats(pwm);
    old = [];
    % inv: smallest unbeaten set containing current value of $list$
    %      = smallest unbeaten set containing original value of $list$
    while ~isequal(old,list)
        old = list;
        % include everyone who beats anyone in $list$
            list = union(list,winners(ismember(losers,list))); 
    end

function winners = SSD(pwm)
% winners = SSD(pwm): SSD Condorcet winners for given pairwise matrix
%     $pwm: pairwise matrix
%     $winners:  winners (as integers) from SSD Condorcet voting (BONUS)
%     note: when there are ties, *all* possible answers are returned

    winners = [];
    tops = topmost(pwm);
    for i = 1:length(tops)
        top = tops{i};
        if length(top) == 1
            winners = [winners top];
        else
            n = length(top);
            minipwm = pwm(top,top); % look at only $n$ candidates in $top$
            % drop minimum magnitude defeats
                [i,j,v] = alldefeats(minipwm);
                keep = find(v > min(v)); 
                minipwm = full(sparse(i(keep), j(keep), v(keep), n, n));
            miniwinners = SSD(minipwm);
            % rename miniwinners to use same integers as our election
                winners = [winners top(miniwinners)];
        end
    end