/*
DemoChoice: Ranked Choice Web Polls
Instant Runoff with Self-Apportionment
Copyright (C) 2008 Dave Robinson
See DemoChoice-Readme.txt for license information

Compiling instructions: use the GCC compiler and use the command
 g++ irsatally.c -o irsatally -O2 -s
GCC is built into Unix-like operating systems, including Mac OS X if you've enabled the developer package
For Windows, use MinGW (http://www.mingw.org).  The cygwin version is less desirable.
Feel free to use other compilers if that works better for you.
Be sure to check DEFAULT_PATH below.

For use instructions, enter irsatally -h at the command line

Uses char for candidate indices, allowing 255 candidates (and one exhausted).
Uses unsigned long for tallies, allowing 4 billion voters for a one-seat election,
or 65,000 for a 255-seat election.  The software could be modified easily
to use int for candidate indices and long long for tallies.
MinGW's long and int are identical, but this may not be true on other compilers.
Generally:
scales with candidates: char
scales with rounds: int
scales with ballots: unsigned long
scales with Votons: unsigned int
presumably char is unsigned on all compilers
xferreport::matrix scales with ballots and allows negative values, so it uses long long.
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#define DEFAULT_PATH "./data/"
// should be "./data/" for unix or "data\\" for windows
// if it's neither of these, update help text accordingly

#define DEFAULT_FILE "DC"
// that is, look in ./data/DC_ballots.txt
// save to DC_result.txt and optionally DC_piles.txt

#define THISFILE "irsatally.c"
using namespace std;

enum Actenum { NO_ACTION, ELIM, ELECTED, ENOUGH_1ST, ENOUGH, IDEAL_1ST, IDEAL };

// these can be toggled or changed by command-line -e -c <num> -s <num>
bool DoEqualize=1;      // Equalize number of votes of remaining candidates (must also recycle)
char Cands=2;           // number of candidates
char Seats=1;           // number of seats
unsigned int Votons=2;  // number of votons into which ballots can be subdivided = Seats*(Seats+1)

int RndNum=1;           // number of the current round, starting from 1
unsigned long BalCt=0;  // number of ballots
unsigned long Enough=1; // Enough (Droop) threshold
unsigned long Ideal=1;  // Ideal (Hare) threshold

// This program relies heavily on the vector template from the C++ standard
// template library, allowing it to handle memory allocation for arrays.
// Beyond that and the use of simple objects, the program doesn't use fancy 
// C++ features and could have been written in C.

vector<int> WonInRound;       // round in which a candidate won 
vector<int> EnoughInRound;    // round in which a candidate first reduced max toward enough
vector<int> IdealInRound;     // round in which a candidate first reduced max toward ideal
vector<int> ElimInRound;      // round in which a candidate was eliminated
// if round is zero, candidate is not in that category (winner, eliminated, etc.)

vector<unsigned long> Slices; // Number of ballots that counted for a given number of winners 
vector<unsigned long> RankCt; // Number of ballots that ranked a given number of candidates
vector<unsigned long> Tally;  // array used to sum changes in votes between rounds
vector<char> SortKey;         // Sorted tally keys, used for eliminations
vector<char> SortKey1;        // Sorted first-round tally keys, presented in output file
vector<unsigned int> Maxima;  // maximum number of votons per ballot countable toward a candidate
vector<unsigned long> Depth;  // Sum of votons from ballots that counted for a winner in each ballot position
vector<Actenum> CandsToProcess; // Type of recount (if any) needed for each candidate
// Last element in [Cands+1] arrays holds the number of exhausted ballots.
 
class whofor
// an array element associated with a ballot describing who it counts for
{
 public:
 char who;            // which candidate it counts for
 unsigned int weight; // fraction of this vote counted toward the candidate

 whofor::whofor()
 // set default values
 {
  whofor::who=0;
  whofor::weight=Votons;
 }
} tempwho;

class Ballot
{
 public:
 vector<char> ranklist; // ranked candidates as described in input file, split into array
 vector<whofor> wt;     // array describing who ballot counts for, and how much for each

Ballot::Ballot()
// initialize a ballot
{
 Ballot::ranklist.clear();
 Ballot::wt.clear();
}

int load(char *inbuf)
// loads a line (string) from the input file into the ranklist array
// for speed, doesn't flag invalid ballots but just crops between 0 and Cands
{
 char r;
 char* rankstr;

 Ballot::ranklist.clear();
 rankstr = strtok(inbuf,","); // standard C function that pulls off first ranking
 while (rankstr != NULL)
 {
  r=(char)abs(atoi(rankstr));       // convert to char and eliminate sign
  if (r<Cands)                // skip if weird number (too high)
  Ballot::ranklist.push_back(r); // convert to char and add to list
  rankstr = strtok (NULL,","); // get next ranking
 }
 Ballot::wt.clear();
 return Ballot::ranklist.size();
}

 char GetPos(char whichcand)
 // finds the position of a candidate in a ballot's list
 // returns the number of candidates if not found
 // (a valid result is less than this)
 {
  char ThePos=0;
   while (ThePos<Ballot::ranklist.size() && 
   Ballot::ranklist[ThePos]!=whichcand)
    ThePos++;
  if (ThePos==Ballot::ranklist.size()) ThePos=Cands;
  return ThePos;
 }

 char GetWho(char whichcand)
 // finds the position in the whofor array of a given candidate
 // returns the size of the array if not found
 // (a valid result is less than this)
 {
  char ThePos=0;
  while (ThePos<Ballot::wt.size() &&
  Ballot::wt[ThePos].who!=whichcand)
   ThePos++;
  return ThePos;
 }

 void addweight(char whichcand, int thewt)
 // adds votons to an element of a ballot's wt array.
 // after finding the candidate in the ballot's who-for array
 // if the candidate is not there, a new who-for entry is created.
 // If an entry is set to zero weight and is at the end of the array,
 // it is deleted.
 {
  int index=Ballot::GetWho(whichcand);
  if (index==Ballot::wt.size())
  {
   tempwho.who=whichcand;
   tempwho.weight=thewt;
   Ballot::wt.push_back(tempwho);
  }
  else
  {
   Ballot::wt[index].weight+=thewt;
   if (index==Ballot::wt.size()-1 && ElimInRound[Ballot::wt[index].who]>0)
    Ballot::wt.pop_back();
  }
 }
 
 void update()
 // Determine who a ballot counts for, given current maxima and woninround.
 // The ballot's contribution to histograms should be taken care of separately.
 // Ballot counts for highest-ranked candidate, except:
 // number of votons counting for candidate must not exceed maximum
 // Votons can't count for a winner unless elected later than any higher-ranked winners
 // if votons can't count for anyone under these constraints, they go back to highest-ranked winner
 // if that is impossible, they count for "none of these"
 {
  Ballot::wt.clear();
  char Recycleto=Cands;
  unsigned int VotonsLeft=Votons;
  int LastWonInRound=0;
  int CandsRanked=Ballot::ranklist.size();  
  int i=0;
  int j=0;

  while (i<CandsRanked && VotonsLeft>0)
  {
   j=Ballot::ranklist[i];
   if (WonInRound[j]==0)
   {
    if (Maxima[j]==0) { i++; continue; }
    else 
    {
     Ballot::addweight(j,VotonsLeft); VotonsLeft=0;
    } 
   }
   else if (LastWonInRound<WonInRound[j])
   {
    if (VotonsLeft>Maxima[j])
    {
     Ballot::addweight(j,Maxima[j]); VotonsLeft-=Maxima[j];
    } 
    else
    {
     Ballot::addweight(j,VotonsLeft); VotonsLeft=0;
    } 
    if (Recycleto==Cands) Recycleto=j; 
    LastWonInRound=WonInRound[j];  
   }
   i++;
  }
  if (VotonsLeft>0)
  {
   Ballot::addweight(Recycleto,VotonsLeft);
  }
 } 
} tempbal;
vector<Ballot> Ballots;

class Bin
// Element of a histogram, storing a number of votons per ballot and the
// number of ballots counting that many votons toward a candidate.
{
 public:
 int Votons;
 int NumOfBallots;

 Bin::Bin()
 {
  Bin::Votons=0;
  Bin::NumOfBallots=0;
 }

 void reset()
 {
  Bin::Votons=0;
  Bin::NumOfBallots=0;
 }
} tempbin;

class Histo
// Histograms are used to determine the maximum number of votons countable to a candidate.
// The maximum is adjusted so that winners don't tie up too many votes, and their constituents
// can help elect other candidates.  This approach makes it less likely that a ballot will be 
// split between more than two candidates.
{
 public:
 vector<Bin> bin;
 unsigned int Max;         // convenient place to store a newly calculated maximum
 unsigned int WantMax;     // a newly calculated maximum goes here, and copied to Max later
 Bin AboveMax;     // stores number of ballots counting above maximum (AboveMax.Votons=0)

 void reset()
 {
  Histo::bin.clear();
  Histo::Max=Votons;
  Histo::WantMax=Votons;
  Histo::AboveMax.reset();
 }

 Histo::Histo()
 // set initial values
 {
  Histo::reset();
 }

 void accept()
 // Accept a calculated maximum as the real thing
 // call if it has been determined that the transfer can be made
 {
  Histo::Max=Histo::WantMax;
 }

 void bindrop(unsigned int weight)
 // remove a ballot's contribution to a histogram
 // empty bins are deleted during sort of histogram
 {
  bool foundit=false;
  for (int hr=0; hr<Histo::bin.size(); hr++)
  {
   if (Histo::bin[hr].Votons==weight)
   {
    foundit=true;
    Histo::bin[hr].NumOfBallots--;
    break;
   }   
  }
  if (!foundit) { Histo::AboveMax.NumOfBallots--; }
 }

 void binadd(unsigned int weight)
 // add a ballot's contribution to a histogram
 // adds a new element if no ballots previously contribute a number of votons
 {
  bool foundit=false;
  if (weight>Histo::Max)
   Histo::AboveMax.NumOfBallots++;
   else
   {
    for (int hr=0; hr<Histo::bin.size(); hr++)
    {
     if (Histo::bin[hr].Votons==weight)
     {
      foundit=true;
      Histo::bin[hr].NumOfBallots++;
      break;
     }
    }
    if (!foundit)
    {
     tempbin.Votons=weight;
     tempbin.NumOfBallots=1;
     Histo::bin.push_back(tempbin);
    }
   }
 }

 int newmax(unsigned long Surplus)
 // Using this histogram and a known number of votons that must be transferred elsewhere (surplus),
 // compute a new maximum that will come as close as possible to eliminating the surplus
 // without making it negative.
 // The maximum is set to the number of votons in successive bins until at least enough would be transferred.
 // If too many would be transferred, an interpolation is made, and the maximum rounded up.
 // This will malfunction if histogram is not sorted!
 {
  unsigned long votonsincluded=0;
  unsigned long ballotsincluded=0;
  unsigned long remain=0;
  unsigned int tempmax=Votons;
  unsigned int prevmax=Votons;
  unsigned int i;

  for (i=0; i<Histo::bin.size(); i++)
  {
   tempmax=Histo::bin[i].Votons;
   if (prevmax<tempmax) break;
   votonsincluded+=ballotsincluded*(prevmax-tempmax);
   if (votonsincluded>Surplus) break;
   ballotsincluded+=Histo::bin[i].NumOfBallots;
   prevmax=tempmax;
  } 
  if (votonsincluded<Surplus)
  {
   tempmax=0;
   votonsincluded+=ballotsincluded*prevmax;
  }
  if (votonsincluded>Surplus)
  {
   // interpolate
   if (ballotsincluded!=0) // can be if surplus<0
   {
    tempmax+=(votonsincluded-Surplus)/ballotsincluded;
    remain=(votonsincluded-Surplus)%ballotsincluded;
    if (remain!=0) tempmax++;
   }
  }
  Histo::WantMax=tempmax;
 }

 void sort()
 {
  unsigned int i0,i1;

  if (Histo::bin.size()==0) return;

  // sort bins by number of ballots
  for (i0=1; i0<Histo::bin.size(); i0++)
  {
   tempbin=Histo::bin[i0];
   i1=i0;
   while (Histo::bin[i1-1].NumOfBallots < tempbin.NumOfBallots)
   {
    Histo::bin[i1] = Histo::bin[i1-1];
    i1--;
    if (i1==0) break;
   }
   Histo::bin[i1] = tempbin;
  }

  // purge zero ballots from end
  for (i0=Histo::bin.size()-1; i0>0; i0--)
   if (Histo::bin[i0].NumOfBallots==0)
    Histo::bin.pop_back();
   else break;

  if (Histo::bin.size()==1 && Histo::bin[0].NumOfBallots==0)
  {
   Histo::bin.pop_back();
   return;
  }

  // sort bins by number of votons per ballot  
  for (i0=1; i0<Histo::bin.size(); i0++)
  {
   tempbin=Histo::bin[i0];
   i1=i0;
   while (Histo::bin[i1-1].Votons < tempbin.Votons)
   {
    Histo::bin[i1] = Histo::bin[i1-1];
    i1--;
    if (i1==0) break;
   }
   Histo::bin[i1] = tempbin;
  }

  // purge bins with zero votons
  for (i0=Histo::bin.size()-1; i0>0; i0--)
   if (Histo::bin[i0].Votons==0)
    Histo::bin.pop_back();
   else break;

  if (Histo::bin.size()==1 && Histo::bin[0].Votons==0)
  {
   Histo::bin.pop_back();
   return;
  }
 }
} temphisto;

vector<Histo> Histogram;

class roundreport
// record data about a round that will go in output file
// Enough and Ideal thresholds depend on number of none-of-these ballots,
// so must be recorded for each round
// (or at least after every round with eliminations, which can change that number).
{
 public:
 vector<unsigned long> Tally;
 vector<unsigned int> Maxima;
 unsigned long Enough;
 unsigned long Ideal;

 void reset()
 {
  roundreport::Tally.clear();
  roundreport::Maxima.clear();
  roundreport::Enough=1;
  roundreport::Ideal=1;
 }

 roundreport::roundreport()
 // set initial values
 {
  roundreport::reset();
 }
} tallytemp;
vector<roundreport> roundata; 

class xferreport
// record data about a transfer that will go in output file
// Reports are recorded for elected candidates in every round to record their histograms
// even if there is no maximum change, so it can be understood why no change occurs,
// and to check for maximum changes if a ballot is added to the tally without a full recount.
{
 public:
 int Rnd;             // transfer reports are appended to an array as they occur;
                      // this field indicates when they occurred
 char who;            // candidate from which votons are transferred
 Actenum action;      // why a candidate is transferred from 
 vector<long long> Matrix; // records who votons get transferred to
                      // This is approximate when several are transferred from in the same round
                      // Because it can be negative, it must be larger than unsigned long
 vector<Bin> Histo;   // record the histogram
 Bin Above;           // record the abovemax bin
 bool tie;            // note if tie requiring random break occurred in elimination calculation

 void reset()
 // reset internal values
 {
  xferreport::Rnd=1;
  xferreport::who=Cands;
  xferreport::action=ELIM;
  xferreport::Matrix.assign(Cands+1,0);
  xferreport::Histo.clear();
  xferreport::Above.reset();
  xferreport::tie=false;
 }

 xferreport::xferreport()
 // set initial values
 {
  xferreport::reset();
 }
} xfertemp;
vector<xferreport> Xfer;

//------------------------------------------------------------------MAIN
int main(int argc, char *argv[])
{
 srand(time(NULL));    // seed random number generator with timestamp
 char inbuf[1024];     // used when loading ballots
 char exclstr[1024];   // command-line list of excluded candidates
 char* exclchar;
 bool DoExclude=0;     // true if exclusions are requested on command line
 int IdealZero;        // nonzero if a candidate above ideal has max of zero
 bool Verbose=1;       // sends more info to stdout if true
 int h,i,j;            // various loop indices
 unsigned int ui;      // unsigned int loop index (for histogram bin loops)
 unsigned long k;      // long loop index (for ballot loops)
 long ElimSum;         // sum of votes to determine who to eliminate
 int ElimGap;          // candidate below which multiple candidates can be eliminated 

 //-------- parse command line to get filename, number of candidates and seats, etc.
 int argtype=0;
 char label[80];
 char fname[80];
 strcpy(label,DEFAULT_FILE);
 if (Verbose) cout << THISFILE << endl;
 for (int i=1; i<argc; i++)
 {
  switch (argtype)
  {
   case 1: // -s <num>: set number of seats to elect (between 1 and 255)
    Seats=atoi(argv[i]);
    Seats=Seats<1?1:Seats;
    Votons=Seats*(Seats+1);
    argtype=0; break;
   case 2: // -f <label: set file prefix (1-20 chars)
    if (strlen(argv[i])>0 && strlen(argv[i])<20)
    { strcpy(label,argv[i]); }
    argtype=0; break;
   case 3: // -c <num>: set number of candidates (between 1 and 255)
    Cands=atoi(argv[i]);
    Cands=Cands<1?1:Cands;
    argtype=0; break;
   case 4: // -x <list>: candidates to exclude, comma-delimited
    strcpy(exclstr,argv[i]);
    DoExclude=1;
   argtype=0; break;
   default:
   if (strcmp(argv[i],"-s")==0) argtype=1;
   if (strcmp(argv[i],"-f")==0) argtype=2;
   if (strcmp(argv[i],"-c")==0) argtype=3;
   if (strcmp(argv[i],"-x")==0) argtype=4;
   if (strcmp(argv[i],"-q")==0) Verbose=0;
   if (strcmp(argv[i],"-e")==0) DoEqualize=0;
   if (strcmp(argv[i],"-h")==0)
   {
    cout << "DemoChoice tally software - http://www.demochoice.org" << endl;
    cout << "Instant Runoff with Self-Apportionment, April 2008" << endl;
    cout << "inputs from command line:" << endl;
    cout << " -f <name> filename prefix" << endl;
    cout << "  if <name>=DC, this corresponds to DC_ballots.txt and DC_result.txt" << endl;
    cout << "  files should be in subdirectory called data" << endl;
    cout << " -s <num> seats to be elected, up to 255" << endl;
    cout << " -c <num> number of candidates, up to 255" << endl;
    cout << " -x 0,1,2 candidates to exclude (0,1, and 2 in this case)" << endl;
    cout << " -q turn off display of most results to stdout (screen)" << endl;
    cout << "input file: filename_ballots.txt" << endl;
    cout << " each line contains one ballot, listing choices in order (1st, 2nd, ...) separated by commas" << endl;
    cout << " candidates are numbered 0,1,2,... in the order listed in a separate file not directly used" << endl;
    cout << " by this program." << endl;
    cout << "output file: filename_result.txt" << endl;
    cout << " dumps the final values of most of the variables used in the count, " << endl;
    cout << " as documented in DemoChoice-Readme.txt." << endl;
    return 0;
   }
  }
 }

 // if more seats than candidates, default to 1 seat
 Seats=Seats<=Cands?Seats:1;
 
 // Determine number of votons per ballot
 Votons=Seats*(Seats+1);

 //----------------------- initialize arrays
 // Cands arrays are set to Cands+1 for consistency even though some logically only need Cands 
 
 WonInRound.assign(Cands+1,0);
 EnoughInRound.assign(Cands+1,0);
 IdealInRound.assign(Cands+1,0);
 ElimInRound.assign(Cands+1,0);
 Slices.assign(Cands+1,0);
 RankCt.assign(Cands+1,0); 
 Tally.assign(Cands+1,0);
 SortKey.assign(Cands+1,0);
 SortKey1.assign(Cands+1,0);
 Maxima.assign(Cands+1,Votons);
 Depth.assign(Cands+1,0);
 CandsToProcess.assign(Cands+1,1);
 for (i=0; i<=Cands; i++)
 { SortKey[i]=i; SortKey1[i]=i; }

 int Remaining=Cands;         // number of remaining candidates
 int Elected=0;               // number of elected candidates
 int NumCandsToProcess=Cands; // candidates whose maximum can be reduced in next round
 bool CanReduce=false;        // set by any rule that can override a maximum reduction
 int Ties=0;                  // number of ties for last place
 int Lot=0;                   // random number used to break tie
 int xferfrom=0;              // These are used to determine who to credit for transfers
 int minxfer=0;               // in the transfer report
 bool Showhisto,              // These switch display of data in output file,
      Showelim,Showcount;     // depending on context


 // eliminate excluded candidates
 // parse in the same way as ballot::load
 if (DoExclude)
 {
  exclchar = strtok(exclstr,",");
  while (exclchar != NULL)
  {
   h=abs(atoi(exclchar));
   h=h>Cands?Cands:h;
   ElimInRound[h]=1;
   Maxima[h]=0;
   Remaining--;
   if (Verbose) cout << h << " excluded" << endl;
   exclchar = strtok (NULL,",");
  }
 }


//-------------------------------- load ballots

 strcpy(fname,DEFAULT_PATH);
 strcat(fname,label);
 ifstream infile(strcat(fname,"_ballots.txt"),ios::in);
 if (infile)
 { if (Verbose) cout << "opened " << fname << endl; }
 else { cout << "failed to open " << fname << endl; }
 long start_time=clock();
 
 // longest possible line: numbers 0-255+commas+crlf=912 bytes
 while (infile)
 {
  infile.getline(inbuf,1024);
  if (infile && tempbal.load(inbuf)>0) Ballots.push_back(tempbal);
 }
 infile.close();
 BalCt=Ballots.size();

 // build histograms of ballots for first-choice candidate
 // create a single bin with a ballot's worth of votons but no ballots
 temphisto.reset();
 tempbin.reset();
 tempbin.Votons=Votons;
 for (i=0; i<=Cands; i++)
 {
  Histogram.push_back(temphisto);
  Histogram[i].bin.push_back(tempbin);
  if (ElimInRound[i]>0) // excluded candidate
  {
   Histogram[i].Max=0;
   Histogram[i].WantMax=0;
  }
 }

 // Count ballots for highest-ranked non-excluded candidate
 // - populate wt, bin, tally
 for (k=0; k<BalCt; k++)
 {
  Ballots[k].update();
  j=Ballots[k].wt[0].who;
  Histogram[j].bin[0].NumOfBallots++;
  Tally[j]+=Votons;
 }
 
 RndNum=0;

 // skip main loop if no votes in ballot file
 if (BalCt==0) NumCandsToProcess=0;

 if (Verbose)
 {
  cout << clock()-start_time << " ms: ballots loaded" << endl;
 } // if verbose

 //------------------------------------------ main loop
 while (NumCandsToProcess>0)
 {
  RndNum++;

  // transfer votes from candidates identified in the previous round
  // It's supposed to be a shortcut to just count ballots in piles affected by max changes.
  // In some cases, the same ballot may be recounted several times if it is in several affected piles,
  // or is in one and then moved to another.  This should be innocuous.  A last_updated_in_round stamp
  // could be recorded if it turns out not to be.
  if (RndNum>1)
  {
   // update global maxima and prepare transfer report from previous round's determinations
   for (i=0; i<Cands; i++)
   {
    Maxima[i]=Histogram[i].Max;
    if (CandsToProcess[i]==NO_ACTION) continue;
    xfertemp.reset();
    xfertemp.who=i;
    xfertemp.Rnd=RndNum;
    xfertemp.action=CandsToProcess[i];
    xfertemp.Histo=Histogram[i].bin;
    xfertemp.Above=Histogram[i].AboveMax;
    if (CandsToProcess[i]==ELIM && Ties>0) xfertemp.tie=true;
    Xfer.push_back(xfertemp);
   }

   // Update ballots, histograms, and tally with new maxima, woninround
   for (k=0; k<BalCt; k++)
   {
    // check ballot's wt array for a candidate subject to transfer
    // and weight above max, and skip if none
    // - could also skip if above previous round's max, but not implemented
    j=0;
    for (h=0;h<Ballots[k].wt.size();h++)
    {
     if ((CandsToProcess[Ballots[k].wt[h].who]>ELECTED ||
          CandsToProcess[Ballots[k].wt[h].who]==ELIM) &&
         Ballots[k].wt[h].weight>Maxima[Ballots[k].wt[h].who]) j++;
    }
    if (j==0) continue;

    // remove whole ballot from tally and all histograms and xfer reports
    for (h=0;h<Ballots[k].wt.size();h++)
    {
     if (Ballots[k].wt[h].weight>0) Histogram[Ballots[k].wt[h].who].bindrop(Ballots[k].wt[h].weight);
     Tally[Ballots[k].wt[h].who]-=Ballots[k].wt[h].weight;
     xfertemp.Matrix[Ballots[k].wt[h].who]-=Ballots[k].wt[h].weight;
    }

    // compute new weights given this round's constraints
    Ballots[k].update();

    // add each wt element back to a histogram, tally, and xfer report
    for (h=0;h<Ballots[k].wt.size();h++)
    {
     Histogram[Ballots[k].wt[h].who].binadd(Ballots[k].wt[h].weight);
     Tally[Ballots[k].wt[h].who]+=Ballots[k].wt[h].weight;
     xfertemp.Matrix[Ballots[k].wt[h].who]+=Ballots[k].wt[h].weight;
    }

    // Determine a candidate to credit transfer of the ballot
    minxfer=0;
    xferfrom=0;

    // find the candidate who is lowest (most negative) on this ballot
    for (i=0; i<Cands; i++)
     if (xfertemp.Matrix[i]<xfertemp.Matrix[minxfer]) minxfer=i;

    // figure out where that candidate is in Xfer array
    for (i=Xfer.size()-1; i>=0; i--)
     if (Xfer[i].Rnd==RndNum && Xfer[i].who==minxfer) { xferfrom=i; break; }

    // add the ballot's transfer info to the Xfer matrix
    for (i=0; i<=Cands; i++)
    {
     Xfer[xferfrom].Matrix[i]+=xfertemp.Matrix[i];
     xfertemp.Matrix[i]=0;
    }
   } // k
  } // RndNum

  // recompute thresholds 
  Enough=(BalCt-Tally[Cands]/Votons)*Seats+1;
  Ideal=(BalCt-Tally[Cands]/Votons)*(Seats+1); 

  // record main data for round
  tallytemp.Tally=Tally;
  tallytemp.Maxima=Maxima;
  tallytemp.Enough=Enough;
  tallytemp.Ideal=Ideal;
  roundata.push_back(tallytemp);

  // update number of winners and remaining candidates
  Remaining=Cands;
  Elected=0;
  for (i=0; i<Cands; i++)
  {
   CandsToProcess[i]=NO_ACTION;
   if (ElimInRound[i]>0) Remaining--;
   if (Tally[i]>=Enough)
   {
    Elected++;
    CandsToProcess[i]=ELECTED;
    if (WonInRound[i]==0) WonInRound[i]=RndNum;
   } // if tally
  } // for i

  // elect remaining candidates below threshold if no extra candidates
  if (Remaining==Seats && Elected < Seats)
  {
   Elected=0;
   for (i=0; i<Cands; i++)
    if (ElimInRound[i]==0)
    {
     Elected++;
     CandsToProcess[i]=ELECTED;
     if (WonInRound[i]==0) WonInRound[i]=RndNum;
    } // if elim   
  } // if remain

  // sort histograms
  int i0,i1;
  for (h=0; h<Cands; h++) Histogram[h].sort();

  // update sorted tally
  for (i0=1; i0<Cands; i0++)
  {
   h=SortKey[i0];
   i1=i0;
   while (Tally[SortKey[i1-1]]<Tally[h])
   {
    SortKey[i1]=SortKey[i1-1];
    i1--;
    if (i1<=0) break; 
   }
   SortKey[i1]=h;
  }
  if (RndNum==1) SortKey1=SortKey;

  // ------------------------------------------------------------------
  // check for possible maximum reductions to correct surplus to Enough
  if (Elected<Seats)
  {
   CanReduce=false;
   for (h=0; h<Cands; h++)
   {
    // skip unelected candidates, but check for eliminations in previous round
    // -  these enable transfers even if no new winners
    if (WonInRound[h]==0)
    {
     if (RndNum>1 && ElimInRound[h]==RndNum-1)
     {
      CanReduce=true;
     }
     continue;
    } // if WIR

    // compute new maximum
    if (Tally[h]<=Enough) continue;
    Histogram[h].newmax(Tally[h]-Enough);

    // enable reduction if it's someone's first time
    // otherwise flag for reduction but wait for someone else to enable 
    if (Histogram[h].WantMax!=Histogram[h].Max)
    {
     if (EnoughInRound[h]==0)
     {
      EnoughInRound[h]=RndNum;
      CandsToProcess[h]=ENOUGH_1ST;
      CanReduce=true;
     } // if EnIR
     else CandsToProcess[h]=ENOUGH;
    } // if eq max
   } // for h

   // someone has enabled transfer, but make sure someone actually can transfer
   // and then change the maxima
   if (CanReduce)
   {
    CanReduce=false;
    for (h=0; h<Cands; h++)
    {
     if (CandsToProcess[h]==ENOUGH || CandsToProcess[h]==ENOUGH_1ST)
     {
      CanReduce=true;
      Histogram[h].accept();
     }
    } // for h
   } // if canreduce
  } // if elected

  // check for possible maximum reductions to correct surplus to Ideal
  // skip if DoEqualize command line parameter is false
  IdealZero=0;
  if (DoEqualize && Remaining<=Seats)
  {
   CanReduce=true;
   for (h=0; h<Cands; h++)
   {
    // skip any candidates who aren't above ideal
    // stop if candidate above ideal has zero maximum
    if (WonInRound[h]==0) continue;
    if (Tally[h]<=Ideal) continue;
    else if (Maxima[h]==0)
    {
     CanReduce=false;
     IdealZero=RndNum+1;
    }

    // compute new maximum
    Histogram[h].newmax(Tally[h]-Ideal);

    // if change in max, mark for transfer
    // IdealInRound isn't used in the procedure, but could be in a variation
    // or could just be added to output if someone cares
    if (Histogram[h].WantMax!=Histogram[h].Max)
    {
     if (IdealInRound[h]==0)
     {
      IdealInRound[h]=RndNum;
      CandsToProcess[h]=IDEAL_1ST;
     } // if IIR
     else
     {
      CandsToProcess[h]=IDEAL;
     }
    } // if eq max
   } // for h

   // make sure IdealZero wasn't triggered, and then change the maxima
   if (CanReduce)
   {
    CanReduce=false;
    for (h=0; h<Cands; h++)
    {
     if (CandsToProcess[h]==IDEAL || CandsToProcess[h]==IDEAL_1ST)
     {
      CanReduce=true;
      Histogram[h].accept();
     }
    } // for h
   } // if canreduce
  } // if remaining


  // review to see if any winners can reduce maxima
  // - if not, demote status to ELECTED and prepare to eliminate
  NumCandsToProcess=0;
  for (i=0; i<Cands; i++)
  {
   // this relies on the order in Actenum
   if (CandsToProcess[i]>ELECTED)
   {
    if (CanReduce) NumCandsToProcess++;
    else CandsToProcess[i]=ELECTED;
   }
  }

  // Eliminate losers if no winners reduce maxima and there are extra candidates
  if (NumCandsToProcess==0 && Remaining>Seats)
  {
   // Sum candidates from smallest to largest
   // omit Seats-1 candidates to avoid eliminating too many
   // identify highest point at which the sum of lower candidates is less than the next candidate
   ElimSum=0;
   ElimGap=0;
   for (i=Cands-1; i>=Seats-1; i--)
   {
    if (Tally[SortKey[i]]>ElimSum) ElimGap=i;
    ElimSum+=Tally[SortKey[i]];
   } // for i

   // Determine just the sum of those lower candidates
   ElimSum=0;
   for (i=Cands-1; i>ElimGap; i--) ElimSum+=Tally[SortKey[i]];

   // Identify ties for last place
   // Other ties don't need resolution (can eliminate someone else, or all)
   // ElimGap snags on first tier if there is a tie
   // check to see if ElimGap snags on last place or last nonzero place
   Ties=0;
   if (ElimGap>=Cands-1 || (Tally[SortKey[ElimGap+1]]==0 && ElimGap>Seats-1))
   {
    // count number of last place ties
    // first condition prevents infinite loop if something goes wrong
    while (ElimGap-Ties>1 && Tally[SortKey[ElimGap-Ties]]==Tally[SortKey[ElimGap-Ties-1]])
     Ties++;
   }

   if (Ties>0)
   {
   // If tied, choose reproducibly random candidate
   // seed by number of votons in tie
    srand(Tally[SortKey[ElimGap]]); // presumably this can cast as necessary
    Lot=(int)floor(((double)Ties+1.0)*
             ((double)(rand()%RAND_MAX)/(double)RAND_MAX));

    // Eliminate the chosen candidate
    ElimInRound[SortKey[ElimGap-Lot]]=RndNum;
    Histogram[SortKey[ElimGap-Lot]].Max=0;    
    CandsToProcess[SortKey[ElimGap-Lot]]=ELIM;
    NumCandsToProcess++;

    // make sure that zero-vote candidates are eliminated
    for (i=Cands-1; i>ElimGap-Lot; i--)
    {
     if (ElimInRound[SortKey[i]]==0 && Tally[SortKey[i]]==0)
     {
      ElimInRound[SortKey[i]]=RndNum;
      CandsToProcess[SortKey[i]]=ELIM;
      Histogram[SortKey[i]].Max=0;
      NumCandsToProcess++;
     } // if EIR
    } // for i
   } // if tie
   else
   {
    // eliminate everyone below ElimGap
    for (i=Cands-1; i>ElimGap; i--)
    {
     if (ElimInRound[SortKey[i]]==0)
     {
      ElimInRound[SortKey[i]]=RndNum;
      CandsToProcess[SortKey[i]]=ELIM;
      Histogram[SortKey[i]].Max=0;
      NumCandsToProcess++;
     } // if EIR
    } // for i
   } // else 
  } // elim
 } // main while loop

 // record final histograms
 if (DoEqualize && IdealZero==0)
 {
  for (i=0; i<Cands; i++)
  {
   if (WonInRound[i]==0) continue;
   xfertemp.reset();
   xfertemp.who=i;
   xfertemp.Rnd=RndNum+1;
   xfertemp.action=ELECTED;
   xfertemp.Histo=Histogram[i].bin;
   xfertemp.Above=Histogram[i].AboveMax;
   Xfer.push_back(xfertemp);
  }
 }
 
 int Rnds=RndNum;

 if (Verbose)
 {
  cout << clock()-start_time << " ms: tally" << endl;
 } // if verbose

 // Go through ballots and compute some statistics (Depth, Slices, RankCt)

 if (BalCt>0)
 {
  int sli; // number of nonzero entries in whofor array (for slices)
  for (i=0; i<=Cands; i++) Depth[i]=0;
  for (k=0; k<BalCt; k++)
  {
   sli=0;

   // compile distribution of number of rankings listed on a ballot
   RankCt[(Ballots[k].ranklist.size()-1)>Cands?Cands:(Ballots[k].ranklist.size()-1)]++;

   for (i=0; i<Ballots[k].wt.size(); i++)
   {
    // count number of candidates a ballot counts for
    if (Ballots[k].wt[i].weight>0 && Ballots[k].wt[i].who!=Cands) sli++;

    // compile distribution of positions in ranking list that ballot uses
    h=Ballots[k].GetPos(Ballots[k].wt[i].who);
    if (h!=Cands && WonInRound[Ballots[k].wt[i].who]>0)
     Depth[h]+=Ballots[k].wt[i].weight;
    else Depth[Cands]+=Ballots[k].wt[i].weight;
   } // for i
   if (sli>0 && sli<=Cands) Slices[sli-1]++;
  } // for k
  Slices[Cands]=Tally[Cands]/Votons;
 } // if balct

 if (Verbose)
 {
  cout << clock()-start_time << " ms: depth calc" << endl;
 } // if verbose

 //---------------------------------Write Result File
 // This uses the JSON format, which is human-readable if done properly,
 // and can be read easily by PHP and other languages. 
 // There are more modular and flexible ways to produce the output,
 // but the overhead is higher, and this works.
 
 int xferctr;
 char q=34;
 if (BalCt>0)
 {
  xferctr=0;
  strcpy(fname,DEFAULT_PATH);
  strcat(fname,label);
  ofstream outfile(strcat(fname,"_result.txt"));
  if (outfile) { if (Verbose) cout << "opened " << fname << endl; }
  else cout << "failed to open " << fname << endl;
  outfile << "{" << endl;
  outfile << " " << q << "Datatype" << q << ": " << q << "DemoChoice Results" << q << "," << endl;
  outfile << " " << q << "Pollname" << q << ": " << q << label << q << "," << endl;
  outfile << " " << q << "Incremental" << q << ": " << 0 << "," << endl;
  outfile << " " << q << "Ballots" << q << ": " << BalCt << "," << endl;
  outfile << " " << q << "VotonsPerBallot" << q << ": " << Votons << "," << endl;
  outfile << " " << q << "Votons" << q << ": " << Votons*BalCt << "," << endl;
  outfile << " " << q << "Candidates" << q << ": " << (int)Cands << "," << endl;
  outfile << " " << q << "Seats" << q << ": " << (int)Seats << "," << endl;
  outfile << " " << q << "Round" << q << ":" << endl;
  outfile << " [" << endl;

  for (j=0; j<Rnds; j++)
  {
   outfile << "  { " << endl;
   outfile << "   " << q << "RndNum" << q << ": " << j+1 << "," << endl;
   outfile << "   " << q << "Enough" << q << ": " << roundata[j].Enough << "," << endl;
   outfile << "   " << q << "Ideal" << q << ": " << roundata[j].Ideal << "," << endl;
   outfile << "   " << q << "Tally" << q << ": [";
   for (i=0; i<Cands; i++)
    outfile << roundata[j].Tally[i] << ",";
   outfile << roundata[j].Tally[Cands] << "]," << endl;
   outfile << "   " << q << "Maxima" << q << ": [";
   for (i=0; i<Cands-1; i++)
    outfile << roundata[j].Maxima[i] << ",";
   outfile << roundata[j].Maxima[Cands-1] << "]," << endl;

   // don't show final-round transfers if count ends because of an IdealZero
   // or because user wants count to stop as soon as elected candidates are determined
   // - final-round histograms are used to determine if count should continue when ballots are added
   if ((DoEqualize && IdealZero==0) || j<Rnds-1)
   {
    outfile << "   " << q << "Transfer" << q << ":" << endl;
    outfile << "   [" << endl;
    while (xferctr<Xfer.size() && Xfer[xferctr].Rnd==j+2)
    {
     outfile << "    {" << endl;
     outfile << "     " << q << "Candidate" << q << ": " << (int)Xfer[xferctr].who << "," << endl;
     outfile << "     " << q << "Action" << q << ": " << q;
     Showhisto=true;
     Showelim=false;
     Showcount=true;
     switch (Xfer[xferctr].action)
     {
      case ELIM : outfile << "ELIM";
       // no need for histogram info, but show if there was a tie
       Showelim=true;
       Showhisto=false;
      break;
      case ELECTED : outfile << "ELECTED";
       // Zero transfers in this case, so don't show
       Showcount=false;
      break;
      case ENOUGH_1ST : outfile << "ENOUGH_1ST"; break;
      case ENOUGH : outfile << "ENOUGH"; break;
      case IDEAL_1ST : outfile << "IDEAL_1ST"; break;
      case IDEAL : outfile << "IDEAL"; break;
      default: outfile << "NO_ACTION"; break;
     }
     outfile << q ;
     if (Showcount)
     {
      outfile << "," << endl << "     " << q << "Count" << q << ": [";
      for (i=0; i<Cands; i++)
       outfile << Xfer[xferctr].Matrix[i] << ",";
      outfile << Xfer[xferctr].Matrix[Cands] << "]";
     }
     if (Showhisto)
     {
      outfile << "," << endl << "     " << q << "Histogram" << q << ": [";
      for (ui=0; ui<Xfer[xferctr].Histo.size(); ui++)
       outfile << "[" << Xfer[xferctr].Histo[ui].Votons << "," 
               << Xfer[xferctr].Histo[ui].NumOfBallots << "],";
      outfile << "[" << Xfer[xferctr].Above.Votons << ","
              << Xfer[xferctr].Above.NumOfBallots << "]]";
     }
     if (Showelim)
     {
      outfile << "," << endl << "     " << q << "Tie" << q << ": ";
      if (Xfer[xferctr].tie)
       outfile << "true";
      else outfile << "false";
     }
     outfile << endl;
     outfile << "    }";    
     xferctr++;
     if (xferctr<Xfer.size() && Xfer[xferctr].Rnd==j+2) outfile << ",";
     outfile << endl; // xfer element
    } // while
    outfile << "   ]" << endl; // transfer array
   } // if not last round
   else
    outfile << "   " << q << "Transfer" << q << ": null" << endl;
   outfile << "  }";

   if (j < Rnds-1) outfile << ",";
   outfile << endl; // round element 
  } 
  outfile << " ]," << endl; // round array

  outfile << " " << q << "SortKey" << q << ": [";
  for (i=0; i<Cands-1; i++)
   outfile << (int)SortKey1[i] << ","; 
  outfile << (int)SortKey1[Cands-1] << "]," << endl; 

  outfile << " " << q << "WonInRound" << q << ": [";
  for (i=0; i<Cands-1; i++)
   outfile << WonInRound[i] << ","; 
  outfile << WonInRound[Cands-1] << "]," << endl; 

  outfile << " " << q << "Depth" << q << ": [";
  for (i=0; i<Cands; i++)
   outfile << Depth[i] << ","; 
  outfile << Depth[Cands] << "]," << endl; 

  outfile << " " << q << "Slices" << q << ": [";
  for (i=0; i<Cands; i++)
   outfile << Slices[i] << ","; 
  outfile << Slices[Cands] << "]," << endl; 

  outfile << " " << q << "RankCt" << q << ": [";
  for (i=0; i<Cands-1; i++)
   outfile << RankCt[i] << ","; 
  outfile << RankCt[Cands-1] << "]" << endl; 
  outfile << "}" << endl;
  outfile.close();

  if (Verbose)
  {
   cout << clock()-start_time << " ms: finished" << endl;
  } // if verbose
 } // balct > 0
 else
 {
  cout << "No ballots in file" << endl;
 }

 return 0;
} // main
