<? 
/*
DemoChoice: Ranked Choice Web Polls
Instant Runoff with Self-Apportionment
Copyright (C) 2008 Dave Robinson
See DemoChoice-Readme.txt for license information
Incremental Tally script - updates a tally using old results + new vote
without recounting all of the ballots.  If this can't be done
(because there is a change in elimination or election order,
 or a winner becomes able to transfer more votons),
the C++ version that counts all the ballots is called.
The following should have been previously included:
 irsadefload.php (loads poll definition)
 incirsainclude.php (PHP versions of C++ methods for processing ballots)
The following inputs should be previously defined:
 NuBallot: a list of rankings for the ballot to be added
 ValidBallot: true if a valid NuBallot exists
 Expired: true if votes are not currently being accepted
The new ballot should have been written to ballot file so that C++ program finds it if necessary.
Exclusions are accounted for in full count by setting their first-round maxima to zero.
*/

$cfile="irsatally"; // path to the C++ version
// should be something like "irsatally" for windows and "./irsatally" for Unix

// equalize winners (reduction to ideal) or produce pile file
$DoEqualize=true;

// ------------------------------------MAIN

$DoIncTally=true;  // if false, do a full recount

if ($Expired or !$ValidBallot)
{ $DoIncTally=false; echo "<!-- expired or no ballot -->"; }
else
{
 // load previous tally output
 $BalCt=0;
 require("irsatallyload.php");
 if ($loaded) $BalCt=$result['Ballots'];
 else { $DoIncTally=false; echo "<!-- could not load previous tally -->"; }
}

if ($DoIncTally && $BalCt>0 && $ValidBallot)
{
 // slightly more convenient forms of common variables
 $Cands=$result['Candidates'];
 $Votons=$result['VotonsPerBallot'];
 $WonInRound=$result['WonInRound'];
 $Rnds=count($result['Round']);
 $SortKey1=$result['SortKey'];

 // set up data structure for new ballot
 $Ballot['Ranklist']=explode(",",$NuBallot);
 for ($i=0; $i<=$Cands; $i++)
 {
  $Ballot['wt'][$i]=0; // number of votons counting for each candidate
  $wtdiff[$i]=0;       // difference from last round, used to compute transfers
 }

 // add to ballot count 
 $result['Ballots']++;
 $result['Votons']+=$result['VotonsPerBallot'];

 for ($RndNum=0; $RndNum<$Rnds; $RndNum++)
 {
  // fetch new maxima and update ballot
  $Maxima=$result['Round'][$RndNum]['Maxima'];
  $PrevWt=$Ballot['wt'];
  update($Ballot);
  for($i=0;$i<=$Cands;$i++)
  {
   $result['Round'][$RndNum]['Tally'][$i]+=$Ballot['wt'][$i];
  }

  // update thresholds
  if ($Ballot['wt'][$result['Candidates']]==0)
  {
   $result['Round'][$RndNum]['Enough']+=$result['Seats'];
   $result['Round'][$RndNum]['Ideal']+=($result['Seats']+1);
  }

  // Determine whether we are eliminating or correcting to enough or ideal
  // Ideal if remaining=seats
  // eliminating if there is a transfer marked as elim
  // elimflag records current and previous eliminations
  // - used to determine change in elimination order, which would trigger recount
  $Remaining=0;
  $DoIdeal=false;
  $haselim=false;
  for ($i=0; $i<$Cands; $i++)
   if ($result['Round'][$RndNum]['Tally'][$i]>0) $Remaining++;
  if ($Remaining<=$result['Seats']) $DoIdeal=true;

  for ($i=0; $i<$Cands; $i++)
  {
   if ($result['Round'][$RndNum]['Tally'][$i]>0) $ElimFlag[$i]=0;
   else $ElimFlag[$i]=1;
  }
  for ($i=0; $i<count($result['Round'][$RndNum]['Transfer']); $i++)
   if ($result['Round'][$RndNum]['Transfer'][$i]['Action']=="ELIM")
   {
    $ElimFlag[$result['Round'][$RndNum]['Transfer'][$i]['Candidate']]=1;
    $haselim=true;
   }

  // determine who gets credit for transfer 
  // - find difference between new ballot's weights in this and previous round
  // If several maxima are reduced, the ballot may have more than one negative entry.
  // Credit transfer to the candidate who contributes most weight to other candidates.
  if ($RndNum>0)
  {
   $minwtdiff=$Cands;
   for ($i=0; $i<=$Cands; $i++)
   {
    $wtdiff[$i]=$Ballot['wt'][$i]-$PrevWt[$i];
    if ($i<$Cands && $wtdiff[$i]<$wtdiff[$minwtdiff]) $minwtdiff=$i;
   }
   for ($i=0; $i<count($result['Round'][$RndNum-1]['Transfer']); $i++)
   {
    // add to transfer count
    if ($result['Round'][$RndNum-1]['Transfer'][$i]['Candidate']==$minwtdiff)
    for ($j=0; $j<=$Cands; $j++)
     $result['Round'][$RndNum-1]['Transfer'][$i]['Count'][$j]+=$wtdiff[$j];
   }
  } // RndNum>0

  $CanReduce=false;
  for ($i=0; $i<count($result['Round'][$RndNum]['Transfer']); $i++)
  {
   // a more convenient name:
   $who=$result['Round'][$RndNum]['Transfer'][$i]['Candidate'];

   // Make note of whether a winner max reduction occurred, for future reference
   if ($result['Round'][$RndNum]['Transfer'][$i]['Action']=="ENOUGH" ||
       $result['Round'][$RndNum]['Transfer'][$i]['Action']=="ENOUGH_1ST" ||
       $result['Round'][$RndNum]['Transfer'][$i]['Action']=="IDEAL" ||
       $result['Round'][$RndNum]['Transfer'][$i]['Action']=="IDEAL_1ST")
    $CanReduce=true;

   // add new ballot to histogram
   // Element 0 corresponds to Bin::Votons; 1 is Bin::NumOfBallots
   // last element in array is the AboveMax bin (element 0 is not used for that)
   if ($Ballot['wt'][$who]>0
       && count($result['Round'][$RndNum]['Transfer'][$i]['Histogram'])>0)
   {
    $foundit=false;
    $zz=count($result['Round'][$RndNum]['Transfer'][$i]['Histogram'])-1;

    // look for existing bin and add to it if found
    for ($j=0; $j<$zz; $j++)
     if ($result['Round'][$RndNum]['Transfer'][$i]['Histogram'][$j][0]==
          $Ballot['wt'][$who])
     {
      $foundit=true;
      $result['Round'][$RndNum]['Transfer'][$i]['Histogram'][$j][1]++;
      break;
     }

    // create new bin and add to it if not found
    // but if the ballot is above maximum, add to the AboveMax bin
    if (!$foundit)
    {
     if ($Ballot['wt'][$who]>$result['Round'][$RndNum]['Maxima'][$who])
      $result['Round'][$RndNum]['Transfer'][$i]['Histogram'][$zz][1]++;
     else // add new bin
     {
      $result['Round'][$RndNum]['Transfer'][$i]['Histogram'][$zz+1][0]=$Ballot['wt'][$who];
      $result['Round'][$RndNum]['Transfer'][$i]['Histogram'][$zz+1][1]=1;
      $zz++;

      // Sort histogram
      // The newmax function requires a sorted histogram
      // zero-voton or zero-ballot bins should not occur in an incremental count
      // (the C++ version purges these)
      for ($i0=1; $i0<$zz+1; $i0++)
      {
       if ($zz==0) continue;
       $Sortme[0]=$result['Round'][$RndNum-1]['Transfer'][$i]['Histogram'][$i0][0];
       $Sortme[1]=$result['Round'][$RndNum-1]['Transfer'][$i]['Histogram'][$i0][1];
       $i1=$i0;
       while($result['Round'][$RndNum-1]['Transfer'][$i]['Histogram'][$i1-1][0]<$Sortme[0])
       {
        $result['Round'][$RndNum-1]['Transfer'][$i]['Histogram'][$i1][0]=
         $result['Round'][$RndNum-1]['Transfer'][$i]['Histogram'][$i1-1][0];
        $result['Round'][$RndNum-1]['Transfer'][$i]['Histogram'][$i1][1]=
         $result['Round'][$RndNum-1]['Transfer'][$i]['Histogram'][$i1-1][1];
        $i1=$i1-1;
        if ($i1<=0) {break;} 
       }
       $result['Round'][$RndNum-1]['Transfer'][$i]['Histogram'][$i1][0]=$Sortme[0];
       $result['Round'][$RndNum-1]['Transfer'][$i]['Histogram'][$i1][1]=$Sortme[1];
      } // sort for
     } // else add new bin
    } // not found bin
   } // add to histogram

   // Check for changed maximum, and trigger full recount if so
   // First, make sure histogram doesn't correspond to elimination,
   // or the current candidate has a zero maximum (and has only an AboveMax bin),
   // or that candidate is still above threshold (if not, deal with separately).
   // $Rnd1 logic allows final round to be checked for max change
   // (changes in maxima determined in round N are recorded in round N+1)

   $Rnd1=(($RndNum<$Rnds-1)?($RndNum+1):$RndNum);
   $thresh=$DoIdeal?$result['Round'][$RndNum]['Ideal']:$result['Round'][$RndNum]['Enough'];

   if (!$haselim && count($result['Round'][$RndNum]['Transfer'][$i]['Histogram'])>1 &&
       $result['Round'][$RndNum]['Tally'][$who]-$thresh>0 && 
       $result['Round'][$Rnd1]['Maxima'][$who]!=
       newmax($result['Round'][$RndNum]['Tally'][$who]-$thresh,
              $result['Round'][$RndNum]['Transfer'][$i]['Histogram']))
   {
    $DoIncTally=false;
    echo "<!-- max change round ".$RndNum." cand ".$who." -->";   
   }
  } // for each transfer

  // check for change in when a candidate is elected
  // (an elected candidate has gone below threshold, or unelected candidate has gone above)
  for ($i=0;$i<$Cands;$i++)
   if ((($WonInRound[$i]>$RndNum+1 || $WonInRound[$i]==0)
        && $result['Round'][$RndNum]['Tally'][$i]>=$result['Round'][$RndNum]['Enough'])
       || (($result['Round'][$RndNum]['Transfer'][$i]['Action']=="ELECTED" ||
            $result['Round'][$RndNum]['Transfer'][$i]['Action']=="ENOUGH" ||
            $result['Round'][$RndNum]['Transfer'][$i]['Action']=="ENOUGH_1ST")
        && $result['Round'][$RndNum]['Tally'][$i]<$result['Round'][$RndNum]['Enough'])
       || (($result['Round'][$RndNum]['Transfer'][$i]['Action']=="IDEAL" ||
           $result['Round'][$RndNum]['Transfer'][$i]['Action']=="IDEAL_1ST")
        && $result['Round'][$RndNum]['Tally'][$i]<$result['Round'][$RndNum]['Ideal']))
    {
     $DoIncTally=false;
     echo "<!-- Round ".$RndNum." election order change -->";
    }

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

  // check for change in elimination order
  // should only do if no ideal or enough
  // This is identical to the more thoroughly commented C++ code
  if ($DoIncTally && !$CanReduce)
  {
   $ElimSum=0;
   $ElimGap=0;
   for ($i=$Cands-1; $i>=$Seats-1; $i--)
   {
    if ($result['Round'][$RndNum]['Tally'][$result['SortKey'][$i]]>$ElimSum) $ElimGap=$i;
    $ElimSum+=$result['Round'][$RndNum]['Tally'][$result['SortKey'][$i]];
   } // for i
   $ElimSum=0;
   for ($i=$Cands-1; $i>$ElimGap; $i--)
    $ElimSum+=$result['Round'][$RndNum]['Tally'][$result['SortKey'][$i]]; 

   // If tied, trigger recount
   // ElimGap snags on first tier if there is a tie
   // Ties only need resolution if the tiers have the fewest nonzero votes
   // otherwise there is someone else to eliminate, or all can be eliminated
   $Ties=0;
   if ($ElimGap>=$Cands-1 ||
    ($result['Round'][$RndNum]['Tally'][$result['SortKey'][$ElimGap+1]]==0 &&
     $ElimGap>$result['Seats']-1))
   {
    while ($ElimGap-$Ties>1 && 
      $result['Round'][$RndNum]['Tally'][$result['SortKey'][$ElimGap-$Ties]]==
      $result['Round'][$RndNum]['Tally'][$result['SortKey'][$ElimGap-$Ties-1]])
     $Ties++;
   }

   // trigger recount if tie
   if (Ties>0)
   {
    $DoIncTally=false; echo "<!-- tie -->";
   } // if tie
   else
   // check for change in elimination order; trigger recount if so
   // ElimFlag should be 0 if not eliminated or 2 if eliminated regardless of the new ballot
   // if it is 1, the new ballot changed a candidate's status, requiring a recount
   {
    for ($i=$Cands-1; $i>$ElimGap; $i--)
    {
     $ElimFlag[$result['SortKey'][$i]]++;
    }
    for ($i=0; $i<$Cands; $i++)
     if ($ElimFlag[$i]==1)
     { $DoIncTally=false; echo "<!-- Round ".$RndNum.": ".$i." changes elimination order -->"; }
   } // else no ties 
  } // not canreduce 

 if (!$DoIncTally) break;
 } // for each round

 $result['SortKey']=$SortKey1;

 // add to depth, rankct, slices
 $MySlice=0;
 for ($i=0; $i<=$Cands; $i++)
 {
  if ($Ballot['wt'][$i]>0)
  {
   $result['Depth'][GetPos($Ballot,$i)]+=$Ballot['wt'][$i];
   if ($i!=$Cands) $MySlice++;
  }
 } // depth loop
 if ($MySlice==0) $MySlice=$Cands+1;
 $result['Slices'][$MySlice-1]++;
 $result['RankCt'][count($Ballot['Ranklist'])-1]++;
} // if valid ballot and doinctally and balct>0
else
{ $DoIncTally=false; echo "<!-- no valid ballot or no ballots -->"; }

//---------------------------------Rewrite Result File

if (!$Expired && $DoIncTally)
{
 $endl=chr(13).chr(10);
 $q=chr(34);

 $fp=fopen($FilePath.$Pollname."_result.txt","w+");

  fputs($fp,"{".$endl);
  fputs($fp, " ".$q."Datatype".$q.": ".$q."DemoChoice Results".$q.",".$endl);
  fputs($fp, " ".$q."Pollname".$q.": ".$q.$Pollname.$q.",".$endl);
  fputs($fp, " ".$q."Incremental".$q.": ".$q.($result["Incremental"]+1).$q.",".$endl);
  fputs($fp, " ".$q."Ballots".$q.": ".$result["Ballots"].",".$endl);
  fputs($fp, " ".$q."VotonsPerBallot".$q.": ".$result["VotonsPerBallot"].",".$endl);
  fputs($fp, " ".$q."Votons".$q.": ".$result["VotonsPerBallot"]*$result["Ballots"].",".$endl);
  fputs($fp, " ".$q."Candidates".$q.": ".$result["Candidates"].",".$endl);
  fputs($fp, " ".$q."Seats".$q.": ".$result["Seats"].",".$endl);

  fputs($fp, " ".$q."Round".$q.":".$endl);
  fputs($fp, " [".$endl);

  for ($j=0; $j<count($result["Round"]); $j++)
  {
   fputs($fp, "  { ".$endl);
   fputs($fp, "   ".$q."RndNum".$q.": ".($j+1).",".$endl);
   fputs($fp, "   ".$q."Enough".$q.": ".$result["Round"][$j]["Enough"].",".$endl);
   fputs($fp, "   ".$q."Ideal".$q.": ".$result["Round"][$j]["Ideal"].",".$endl);
   fputs($fp, "   ".$q."Tally".$q.": [");
   for ($i=0; $i<$result["Candidates"]; $i++)
    fputs($fp, $result["Round"][$j]["Tally"][$i].",");
   fputs($fp, $result["Round"][$j]["Tally"][$result["Candidates"]]."],".$endl);
   fputs($fp, "   ".$q."Maxima".$q.": [");
   for ($i=0; $i<$result["Candidates"]-1; $i++)
    fputs($fp, $result["Round"][$j]["Maxima"][$i].",");
   fputs($fp, $result["Round"][$j]["Maxima"][$result["Candidates"]-1]."],".$endl);

   if (($DoEqualize && $IdealZero==0) || $j<count($result["Round"])-1)
   {
    fputs($fp, "   ".$q."Transfer".$q.":".$endl);
    fputs($fp, "   [".$endl);
    for ($x=0; $x<count($result["Round"][$j]["Transfer"]); $x++)
    {
     fputs($fp, "    {".$endl);
     fputs($fp, "     ".$q."Candidate".$q.": ".$result["Round"][$j]["Transfer"][$x]["Candidate"].",".$endl);
     fputs($fp, "     ".$q."Action".$q.": ".$q.$result["Round"][$j]["Transfer"][$x]["Action"].$q);
     if (count($result["Round"][$j]["Transfer"][$x]["Count"])==$result["Candidates"]+1)
     {
      fputs($fp, ",".$endl."     ".$q."Count".$q.": [");
      for ($i=0; $i<$result["Candidates"]; $i++)
       fputs($fp, $result["Round"][$j]["Transfer"][$x]["Count"][$i].",");
      fputs($fp, $result["Round"][$j]["Transfer"][$x]["Count"][$result["Candidates"]]."]");
     }
     $zz=count($result["Round"][$j]["Transfer"][$x]["Histogram"]);
     if ($zz>0)
     {
      fputs($fp, ",".$endl."     ".$q."Histogram".$q.": [");
      for ($i=0; $i<$zz-1; $i++)
       fputs($fp, "[".$result["Round"][$j]["Transfer"][$x]["Histogram"][$i][0]."," 
             .$result["Round"][$j]["Transfer"][$x]["Histogram"][$i][1]."],");
      fputs($fp, "[".$result["Round"][$j]["Transfer"][$x]["Histogram"][$zz-1][0].","
             .$result["Round"][$j]["Transfer"][$x]["Histogram"][$zz-1][1]."]]");
     }
     if (array_key_exists("Tie",$result["Round"][$j]["Transfer"][$x]))
     {
      fputs($fp,",".$endl."     ".$q."Tie".$q.": ");
      if ($result["Round"][$j]["Transfer"][$x]["Tie"])
       fputs($fp, "true");
      else fputs($fp, "false");
     }
     fputs($fp, $endl);
     fputs($fp, "    }");    
     if ($x<count($result["Round"][$j]["Transfer"])-1) fputs($fp, ",");
     fputs($fp, $endl); // xfer element
    } // for x
    fputs($fp, "   ]".$endl); // transfer array
   } // if not last round
   else
    fputs($fp, "   ".$q."Transfer".$q.": null".$endl);
   fputs($fp, "  }");
   if ($j < count($result["Round"])-1) fputs($fp, ",");
   fputs($fp, $endl); // round element 
  } 
  fputs($fp, " ],".$endl); // round array

  fputs($fp, " ".$q."SortKey".$q.": [");
  for ($i=0; $i<$result["Candidates"]-1; $i++)
   fputs($fp, $result["SortKey"][$i].","); 
  fputs($fp, $result["SortKey"][$result["Candidates"]-1]."],".$endl); 

  fputs($fp, " ".$q."WonInRound".$q.": [");
  for ($i=0; $i<$result["Candidates"]-1; $i++)
   fputs($fp, $result["WonInRound"][$i].","); 
  fputs($fp, $result["WonInRound"][$result["Candidates"]-1]."],".$endl); 

  fputs($fp, " ".$q."Depth".$q.": [");
  for ($i=0; $i<$result["Candidates"]; $i++)
   fputs($fp, $result["Depth"][$i].","); 
  fputs($fp, $result["Depth"][$result["Candidates"]]."],".$endl); 

  fputs($fp, " ".$q."Slices".$q.": [");
  for ($i=0; $i<$result["Candidates"]; $i++)
   fputs($fp, $result["Slices"][$i].","); 
  fputs($fp, $result["Slices"][$result["Candidates"]]."],".$endl); 

  fputs($fp, " ".$q."RankCt".$q.": [");
  for ($i=0; $i<$result["Candidates"]-1; $i++)
   fputs($fp, $result["RankCt"][$i].","); 
  fputs($fp, $result["RankCt"][$result["Candidates"]-1]."]".$endl); 
  fputs($fp, "}".$endl);
  fclose($fp);
} // if not (expired and doinctally)

// Perform full recount if incremental tally was not possible,
// or there has not been a full recount since the poll expired
if ((!$DoIncTally && !($Expired && $result["Incremental"]==0)) || !$ValidBallot)
{
 echo "<!-- ";
 $CCall=$cfile." -q -f ".$Pollfile." -c ".$Cands." -s ".$Seats;
 if ($ExclCt>0) $CCall.=" -x ".$ExclStr;
 if (!$DoEqualize) $CCall.=" -e ";
 echo $CCall." ";
 unset($Cout);
 exec($CCall,$Cout);
 echo $Cout[0];
 echo " -->";
}
?>
