package votorola.a.election; // Copyright 2007-2008, Michael Allan. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Votorola Software"), to deal in the Votorola Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicence, and/or sell copies of the Votorola Software, and to permit persons to whom the Votorola Software is furnished to do so, subject to the following conditions: The preceding copyright notice and this permission notice shall be included in all copies or substantial portions of the Votorola Software. THE VOTOROLA SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE VOTOROLA SOFTWARE OR THE USE OR OTHER DEALINGS IN THE VOTOROLA SOFTWARE. import java.io.*; import java.sql.*; import java.util.*; import votorola._.*; import votorola.a.manline.*; import votorola.g.lang.*; import votorola.g.sql.*; /** A node in a delegate cascade, it records the cumulative cast/count state for a single * voter/candidate. It is partly serializeable; when unserialized, it becomes detached * from the table, so that calling any of the table-dependent methods (such as commit, or * trace) will result in a runtime exception. */ public class CountNode implements Cloneable, java.io.Serializable { // Cf. a/register/ListNodeC private static final long serialVersionUID = 0L; /** Creates a CountNode with default values: all counts at zero, * no {@linkplain #getCandidateEmail() chosen candidate}, * and no {@linkplain #isCast() vote cast}. * * @param table per {@linkplain #table() table}() * @param voterEmail per {@linkplain #voterEmail() voterEmail}() */ CountNode( Table table, String voterEmail ) { if( table == null || voterEmail == null ) throw new NullPointerException(); // fail fast this.table = table; this.voterEmail = voterEmail; isChanged = true; } /** Constructs a CountNode. * * @param table per {@linkplain #table() table}() * @param voterEmail per {@linkplain #voterEmail() voterEmail}() * @param bar per {@linkplain #getBar() getBar}() * @param candidateEmail per {@linkplain #getCandidateEmail() getCandidateEmail}() * @param carryCount per {@linkplain #carryCount() carryCount}() * @param isCast per {@linkplain #isCast() isCast}() * @param receiveCount per {@linkplain #receiveCount() receiveCount}() */ CountNode( Table table, String voterEmail, String bar, String candidateEmail, long carryCount, boolean isCast, long rank, long rankIndex, long receiveCount ) { if( table == null || voterEmail == null ) throw new NullPointerException(); // fail fast this.table = table; this.voterEmail = voterEmail; // Adding fields here? Increment serialVersionUID and Count.serialVersionUID. this.bar = bar; this.candidateEmail = candidateEmail; this.carryCount = carryCount; this.isCast = isCast; this.rank = rank; this.rankIndex = rankIndex; this.receiveCount = receiveCount; } // ------------------------------------------------------------------------------------ /** The number of {@linkplain #receiveCount() received votes} that are * carried to the {@linkplain #getCandidateEmail() candidate} node * along with this node's {@linkplain #singleCastCount() single cast vote}. * The single cast vote is excluded from this count. * * @see #holdCount */ public final long carryCount() { return carryCount; } private long carryCount; /** Writes this node to the table, if it has uncommitted changes. */ final void commit() throws SQLException { if( table == null ) throw newReadOnlyException(); // fail fast if( !isChanged ) return; table.put( CountNode.this ); isChanged = false; } /** The number of votes held. This is simply * {@linkplain #receiveCount() receiveCount} - {@linkplain #carryCount() carryCount}. */ public final long holdCount() { return receiveCount - carryCount; } /** The bar against the voter, if any. A barred voter is ineligible to vote in this * election. The bar may be either an eligibility bar, or a list bar. An * eligibility bar is specific to an election. For example, the voter must reside in * the specific district of the election. *

* The bar may also be a {@linkplain votorola.a.register.ListNode#getBar() list * bar}. A list bar applies to all elections. *

* * @return description of bar, or null if there is no bar * * @see #setBar(String) */ public final String getBar() { return bar; } private String bar; /** Sets an eligibility bar against the voter. * * @see #getBar() */ final void setBar( String newBar ) { if( ObjectX.nullEquals( newBar, bar )) return; bar = newBar; isChanged = true; } /** Returns the rank assigned to this node, with respect to {@linkplain * #receiveCount() votes received}. The numerical minimum is a rank of 1 (top rank), * assigned to the node(s) receiving the most votes. Rank progresses incrementally, * with no gaps. All nodes receiving the same number of votes are assigned the same * rank. *
* 1, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4 *
*

* In the example above, two candidates are tied for second place (rank 2). * The bottom rank of 4 is shared by 7 voters who are probably non-candidates * (receiving no votes). *

* * @return rank of 1 or larger; or 0, if no rank has been assigned, * because the count is still in progress * * @see #setRank(long) */ public final long getRank() { return rank; } private long rank; /** Assigns a rank to this node. * * @see #getRank() */ final void setRank( long newRank ) { if( newRank == rank ) return; rank = newRank; isChanged = true; } /** Returns the unique index assigned to this node, by order of {@linkplain #getRank() * rank}, and (secondarily) {@linkplain #voterEmail() email address}. * This index serves for constructing predictable paged views of the rankings. * * @return rank index of 0 or larger * * @see #setRankIndex(long) */ public final long getRankIndex() { return rankIndex; } private long rankIndex; /** Assigns a rank index to this node. * * @see #getRankIndex() */ final void setRankIndex( long newRankIndex ) { if( newRankIndex == rankIndex ) return; rankIndex = newRankIndex; isChanged = true; } /** Returns true if a vote was successfully cast * for the {@linkplain #getCandidateEmail() candidate}; false otherwise. * * @see #cast(boolean) * @see #uncast(boolean) */ public final boolean isCast() { return isCast; } private boolean isCast; /** Attempts to cast a vote for the {@linkplain #getCandidateEmail() chosen candidate}. * If the voter {@linkplain #getBar() is barred}, the vote will go nowhere. * Otherwise, it may cascade, affecting counts on other nodes. * * @param toCarry Set to true to carry the {@linkplain #receiveCount() received votes} * along with the cast vote. Set to false to transfer the single vote * of this voter, alone. * @return {@linkplain #trace() trace} * * @throws IllegalStateException if the vote is already cast, * @see #uncast(boolean) */ final CountNode[] cast( boolean toCarry ) throws SQLException { if( isCast ) throw new IllegalStateException( "attempt to cast a vote twice" ); assert !toCarry || carryCount == 0L : "carry votes once only"; final CountNode[] trace = trace(); if( trace.length > 1 ) { if( toCarry && voterEmail().equals( trace[trace.length-1].getCandidateEmail() )) { castCarryCyclic( trace ); } else castStraight( toCarry, trace ); } return trace; } /** Withdraws a vote for the {@linkplain #getCandidateEmail() candidate}, * if one was cast. * * @param toCarry Set to true to withdraw any {@linkplain #carryCount() carried votes} * along with the cast vote. Set to false to withdraw the single vote * of this voter, alone. * @return {@linkplain #trace() trace} * * @see #cast(boolean) */ final CountNode[] uncast( boolean toCarry ) throws SQLException { final CountNode[] trace = trace(); if( isCast ) { if( trace.length <= 1 ) throw new IllegalStateException( "lost trace of cast vote" ); if( toCarry && voterEmail().equals( trace[trace.length-1].getCandidateEmail() )) { uncastCarryCyclic( trace ); } else uncastStraight( toCarry, trace ); } return trace; } /** The number of votes received from other nodes. * * @see #carryCount * @see #holdCount */ public final long receiveCount() { return receiveCount; } private long receiveCount; /** The number of votes cast for the {@linkplain #getCandidateEmail() candidate}; * either 0 or 1. * * @see #carryCount() * @see #cast(boolean) * @see #isCast() */ public final long singleCastCount() { return isCast? 1L:0L; } /** The table in which this node is stored. * * @return table, or null if this is a deserialized, read-only node */ public final Table table() { return table; } private final transient Table table; /** Traces the route a vote would follow if it a cast were attempted * from this node to the {@linkplain #getCandidateEmail() candidate node}, * and carried onward to the terminal node. * * @return array of nodes from the casting node (index 0) * to the terminal node (length-1) */ final CountNode[] trace() throws SQLException { if( table == null ) throw newReadOnlyException(); // fail fast final ArrayList nodeList = new ArrayList(); trace: for( CountNode node = CountNode.this;; ) { nodeList.add( node ); if( node.getBar() != null ) break trace; String candidateEmail = node.getCandidateEmail(); if( candidateEmail == null ) break trace; for( CountNode listNode: nodeList ) { if( candidateEmail.equals( listNode.voterEmail() )) break trace; // prevent cycle } node = table.getOrCreate( candidateEmail ); } return nodeList.toArray( new CountNode[nodeList.size()] ); } // ` V o t e `````````````````````````````````````````````````````````````````````````` /** Identifies the candidate for whom the voter will be voting, * once the vote is {@linkplain #cast(boolean) actually cast}. * * @return canonical email address (having no personal part); * or null, if the voter has not attempted to cast a vote * * @see #setCandidateEmail(String) */ public final String getCandidateEmail() { return candidateEmail; } private String candidateEmail; /** Changes the candidate for whom the voter will be voting. * In order for the change to affect the election state, * you would normally call {@linkplain #uncast(boolean) uncast}(true) beforehand, * then {@linkplain #cast(boolean) cast}(true) afterwards. * * @see #getCandidateEmail() */ final void setCandidateEmail( String newCandidateEmail ) { if( ObjectX.nullEquals( newCandidateEmail, candidateEmail )) return; candidateEmail = newCandidateEmail; isChanged = true; } /** Identifies the voter. * * @return canonical email address (having no personal part) */ public final String voterEmail() { return voterEmail; } private final String voterEmail; // - O b j e c t ---------------------------------------------------------------------- public final @Override CountNode clone() { try { return (CountNode)super.clone(); } catch( CloneNotSupportedException x ) { throw new RuntimeException( x ); } // never occurs } /** Returns the {@linkplain #voterEmail() voter email address}. */ public final @Override String toString() { return voterEmail(); } // ==================================================================================== /** The relational store of count nodes that (in part) backs * a {@linkplain Count election count}. */ public static @ThreadSafe class Table { // Cf. a/register/ListNodeC.Table /** Constructs a Table. * * @param readyDirectory per {@linkplain #readyDirectory() readyDirectory}() * @param database per {@linkplain #database() database}() */ Table( final ReadyDirectory readyDirectory, final Database database ) throws IOException { this.readyDirectory = readyDirectory; this.database = database; final String snapDateSuffix = VOSnap.dateSuffix( readyDirectory.snapDirectory().getName() ); if( !VOSnap.isDateSuffix( snapDateSuffix )) throw new VotorolaRuntimeException( "improperly date-suffixed snap directory parent of ready directory: " + readyDirectory ); tableName = snapDateSuffix.substring(1) + VOSnap.dateSuffixDelimiter + "count_node" + VOSnap.dateSuffix(readyDirectory.getCanonicalFile().getName()); statementKeyBase = getClass().getName() + ":" + schemaName() + "/" + tableName + "."; } private String schemaName() { return readyDirectory.name(); } private final String statementKeyBase; private final String tableName; // -------------------------------------------------------------------------------- /** Creates this table in the database. */ final void create() throws SQLException { final String key = statementKeyBase + "create"; synchronized( database ) { PreparedStatement s = database.statementCache().get( key ); if( s == null ) { s = database.connection().prepareStatement( "CREATE TABLE \"" + schemaName() + "\".\"" + tableName + "\"" + " (voterEmail character varying PRIMARY KEY," + " bar character varying," + " candidateEmail character varying," + " carryCount bigint NOT NULL," + " isCast boolean NOT NULL," + " rank bigint NOT NULL," + " rankIndex bigint NOT NULL," // UNIQUE, but not till count completes + " receiveCount bigint NOT NULL)" ); // Changing table structure? Then also increment Count.serialVersionUID. database.statementCache().put( key, s ); } s.execute(); } } /** Returns the database in which this table is stored. */ final Database database() { return database; } private final Database database; /** Drops this table from the database. */ final void drop() throws SQLException { final String key = statementKeyBase + "drop"; synchronized( database ) { PreparedStatement s = database.statementCache().get( key ); if( s == null ) { s = database.connection().prepareStatement( "DROP TABLE \"" + schemaName() + "\".\"" + tableName + "\"" ); database.statementCache().put( key, s ); } s.execute(); } } /** Returns true if this table exists in the database; false otherwise. */ final boolean exists() throws SQLException { final String key = statementKeyBase + "exists"; synchronized( database ) { PreparedStatement s = database.statementCache().get( key ); if( s == null ) { s = database.connection().prepareStatement( "SELECT * FROM \"" + schemaName() + "\".\"" + tableName + "\"" ); s.setMaxRows( 1 ); database.statementCache().put( key, s ); } try { s.execute(); } catch( SQLException x ) { if( "42P01".equals( x.getSQLState() )) return false; // UNDEFINED TABLE throw x; } } return true; } /** Retrieves a node from this table. * * @return node as stored in the table; or null, if none is stored */ CountNode get( final String voterEmail ) throws SQLException { if( voterEmail == null ) throw new NullPointerException(); // fail fast final String key = statementKeyBase + "get"; synchronized( database ) { PreparedStatement s = database.statementCache().get( key ); if( s == null ) { s = database.connection().prepareStatement( "SELECT bar, candidateEmail, carryCount, isCast, rank, rankIndex, receiveCount" + " FROM \"" + schemaName() + "\".\"" + tableName + "\"" + " WHERE voterEmail = ?" ); database.statementCache().put( key, s ); } s.setString( 1, voterEmail ); final ResultSet r = s.executeQuery(); try { if( !r.next() ) return null; return new CountNode( Table.this, voterEmail, r.getString(1), r.getString(2), r.getLong(3), r.getBoolean(4), r.getLong(5), r.getLong(6), r.getLong(7) ); } finally{ r.close(); } } } /** Retrieves a list of nodes by rank indeces. The list includes all nodes from first * index (inclusive) to lastBound (exclusive). It is pre-sorted, from low to high. */ List getByRankIndeces( final int first, final int lastBound ) throws SQLException { final String key = statementKeyBase + "getByRankIndeces"; synchronized( database ) { PreparedStatement s = database.statementCache().get( key ); if( s == null ) { s = database.connection().prepareStatement( "SELECT * FROM \"" + schemaName() + "\".\"" + tableName + "\"" + " WHERE rankIndex >= ? AND rankIndex < ? ORDER BY rankIndex" ); database.statementCache().put( key, s ); } s.setLong( 1, first ); s.setLong( 2, lastBound ); final ResultSet r = s.executeQuery(); final ArrayList nodeList = new ArrayList( /*initial capacity*/lastBound - first ); try { while( r.next() ) { nodeList.add( new CountNode( Table.this, r.getString(1), r.getString(2), r.getString(3), r.getLong(4), r.getBoolean(5), r.getLong(6), r.getLong(7), r.getLong(8) )); } } finally{ r.close(); } return nodeList; } } /** Retrieves a list of nodes that are successfully casting for a particular * candidate. The list is pre-sorted by carry count, from high to low. * * @param minimumCarryCount the minimum carry count that a node must have, * for inclusion in the list; all others are excluded */ public List getCastersByCandidate( final String candidateEmail, final long minimumCarryCount ) throws SQLException { final String key = statementKeyBase + "getCastersByCandidate"; synchronized( database ) { PreparedStatement s = database.statementCache().get( key ); if( s == null ) { s = database.connection().prepareStatement( "SELECT voterEmail, bar, carryCount, rank, rankIndex, receiveCount" + " FROM \"" + schemaName() + "\".\"" + tableName + "\"" + " WHERE isCast AND carryCount >= ? AND candidateEmail = ?" + " ORDER BY carryCount DESC" ); database.statementCache().put( key, s ); } s.setLong( 1, minimumCarryCount ); s.setString( 2, candidateEmail ); final ResultSet r = s.executeQuery(); final ArrayList nodeList = new ArrayList( /*initial capacity, guess*/50 ); // 100 is max, if client is a.voter.WP_Voter, per receiveCutoffPercent try { while( r.next() ) { nodeList.add( new CountNode( Table.this, r.getString(1), r.getString(2), candidateEmail, r.getLong(3), /*isCast*/true, r.getLong(4), r.getLong(5), r.getLong(6) )); } } finally{ r.close(); } return nodeList; } } /** Retrieves a node from this table; or, if none is stored, a default node. * * @return CountNode as stored in the table; or, if none is stored, * a {@linkplain CountNodeIC CountNodeIC} with default values */ public CountNode getOrCreate( final String voterEmail ) throws SQLException { CountNode node = get( voterEmail ); if( node == null ) node = new CountNodeIC( Table.this, voterEmail ); return node; } /** Stores a node. */ public final void put( final CountNode node ) throws SQLException { synchronized( database ) { { final String key = statementKeyBase + "putU"; PreparedStatement s = database.statementCache().get( key ); if( s == null ) { s = database.connection().prepareStatement( "UPDATE \"" + schemaName() + "\".\"" + tableName + "\"" + " SET bar = ?," + " candidateEmail = ?," + " carryCount = ?," + " isCast = ?," + " rank = ?," + " rankIndex = ?," + " receiveCount = ?" + " WHERE voterEmail = ?" ); database.statementCache().put( key, s ); } s.setString( 1, node.getBar() ); s.setString( 2, node.getCandidateEmail() ); s.setLong( 3, node.carryCount() ); s.setBoolean( 4, node.isCast() ); s.setLong( 5, node.getRank() ); s.setLong( 6, node.getRankIndex() ); s.setLong( 7, node.receiveCount() ); s.setString( 8, node.voterEmail() ); final int updatedRows = s.executeUpdate(); if( updatedRows > 0 ) { assert updatedRows == 1; return; } } { final String key = statementKeyBase + "putI"; PreparedStatement s = database.statementCache().get( key ); if( s == null ) { s = database.connection().prepareStatement( "INSERT INTO \"" + schemaName() + "\".\"" + tableName + "\"" + " (voterEmail, bar, candidateEmail, carryCount," + " isCast, rank, rankIndex, receiveCount)" + " VALUES (?, ?, ?, ?, ?, ?, ?, ?)" ); database.statementCache().put( key, s ); } s.setString( 1, node.voterEmail() ); s.setString( 2, node.getBar() ); s.setString( 3, node.getCandidateEmail() ); s.setLong( 4, node.carryCount() ); s.setBoolean( 5, node.isCast() ); s.setLong( 6, node.getRank() ); s.setLong( 7, node.getRankIndex() ); s.setLong( 8, node.receiveCount() ); s.executeUpdate(); } } } /** Sorts all rows by the columns that determine {@linkplain CountNode#getRank() * rank}; stores the resulting rank and rank-index for each row; and returns the * cumulative count of votes cast, and so forth. */ RankedCumulate rank() throws SQLException { final String key = statementKeyBase + "rank"; synchronized( database ) { PreparedStatement s = database.statementCache().get( key ); if( s == null ) { s = database.connection().prepareStatement( "SELECT voterEmail, bar, candidateEmail, carryCount, isCast, receiveCount" + " FROM \"" + schemaName() + "\".\"" + tableName + "\"" + " ORDER BY receiveCount DESC, voterEmail" ); database.statementCache().put( key, s ); } final ResultSet r = s.executeQuery(); try { final RankedCumulate c = new RankedCumulate(); long receiveCountLast = Long.MAX_VALUE; while( r.next() ) { final CountNode node = new CountNode( Table.this, r.getString(1), r.getString(2), r.getString(3), r.getLong(4), r.getBoolean(5), 0L, 0L, r.getLong(6) ); c.singleCastCount += node.singleCastCount(); c.holdCount += node.holdCount(); if( node.receiveCount() < receiveCountLast ) { ++c.rankCount; assert !(c.nodeCount == 0L && c.rankCount > 1L): "top rank is 1"; receiveCountLast = node.receiveCount(); } else assert node.receiveCount() == receiveCountLast: "nodes are sorted"; node.setRank( c.rankCount ); node.setRankIndex( c.nodeCount ); node.commit(); ++c.nodeCount; if( node.receiveCount() > 0 ) ++c.candidateCount; } return c; } finally{ r.close(); } } } /** The file-based counterpart to this table. */ final ReadyDirectory readyDirectory() { return readyDirectory; } private final ReadyDirectory readyDirectory; // final after init // ================================================================================ /** @see #rank() */ static final class RankedCumulate { /** @see Count#candidateCount() */ long candidateCount; /** @see CountNode#holdCount() */ long holdCount; /** @see Count#nodeCount() */ long nodeCount; /** @see Count#rankCount() */ long rankCount; /** @see CountNode#singleCastCount() */ long singleCastCount; } } //// P r i v a t e /////////////////////////////////////////////////////////////////////// /** Does a cyclic cast-and-carry. This is more complicated than * {@linkplain #castStraight(boolean,CountNode[]) castStraight}(toCarry,trace) * because there is no single, terminal node at which the carried votes are held, * rather they are deposited here and there, depending on where they entered the cycle. *

* Let the following denote a series of nodes in two states B and C: *

* 
      *          -> B[0]    B[1] -> B[2] -> ... -> B[n-1] --
      *         |                                           |
      *          - - - - - - - - - - - - - - - - - - - - - -
      *
      *
      *          -> C[0] -> C[1] -> C[2] -> ... -> C[n-1] --
      *         |                                           |
      *          - - - - - - - - - - - - - - - - - - - - - -
      *
*

* where: *

* 
      *         -> is the route of votes within the series (other votes
      *         may merge into the series from other nodes, but are not shown)
      *
      *         B[i] is the state of N[i] when N[0] has withheld its vote
      *
      *         C[i] is the state of N[i] when N[0] has cast for N[1],
      *         thus causing a cyclic cascade
      *
      *         n is the number of nodes in the trace
      *
*

* Given vote counts for B, calculate those for C. *

* 
 (1)
      *         C[0].receive  =  B[0].receive
      *
*

* Votes received by N[0] remain constant. * No vote can cycle, so the input to N[0] cannot increase with its output. *

* 
 (2)
      *         C[i].receive  =  C[j].receive ,   for all i, j
      *
*

* Equation 2 is the flood rule. It states that all nodes in the cycle * will receive the same number of votes. This follows from the fact that * a vote carried into the cycle will travel until just before it encounters * the same node twice, so it will be received by all nodes. * Likewise, single casts originating within the cycle are evenly distributed. *

*

* From 1 and 2: *

* 
 (3)
      *         C[i].receive  =  B[0].receive ,   for all i
      *
*

* Also: *

* 
 (4)
      *         C[i].hold  =  B[i+1].receive  -  B[i].receive ,   for i = 1...n-1
      *
*

* Equation 4 states: except N[0], each node will come to hold * whatever its following node had received, less whatever it itself had received. * In other words, a node will hold whatever its successor had introduced to the cycle. * This is guaranteed, because a cycling vote must stop before it actually cycles. *

*

* Known are C[i].receive (3) and C[i].hold (4), for i = 1...n-1. * So C[i].carry may be calculated: *

* 
 (5)
      *         N.hold  =  N.receive  -  N.carry
      *
      *         C[i].carry  =  C[i].receive  -  C[i].hold
      *
*

* Equation 5 states that votes are conserved. * Votes that are held are those received, minus those carried to another node. *

*

* It only remains to solve for C[0] *

* 
 (6)
      *         C[0].hold  =  B[1].receive  +  1
      *
*

* Equation 6 is another instance of the rule (4) that a node holds whatever * its successor had introduced into the cycle. *

*

* Known are C[0].hold (6) and C[0].receive (1). So C[0].carry may be calculated (5). *

*/ private void castCarryCyclic( final CountNode[] trace ) { final long hold0 = trace[1].receiveCount + 1; // (6) assert trace.length > 1; for( int i = 1; i < trace.length; ++i ) { final CountNode node = trace[i]; final CountNode sucessor; if( i == trace.length - 1 ) sucessor = trace[0]; else sucessor = trace[i+1]; final long hold = sucessor.receiveCount - node.receiveCount; // (4) node.receiveCount = trace[0].receiveCount; // (3) node.carryCount = node.receiveCount - hold; // (5) node.isChanged = true; } isCast = true; carryCount = receiveCount - hold0; // (5), and receiveCount unchanged (1) isChanged = true; } /** Does either a simple cast (single vote) or an acyclic cast-and-carry. * * @see #uncastStraight(boolean,CountNode[]) * @see #castCarryCyclic(CountNode[]) */ private void castStraight( final boolean toCarry, final CountNode[] trace ) { isCast = true; isChanged = true; final long sendCount; if( toCarry ) { sendCount = receiveCount + 1L; // send them all out carryCount = receiveCount; // holding no more } else sendCount = 1L; assert trace.length > 1; for( int i = 1;; ) { final CountNode node = trace[i]; node.receiveCount += sendCount; node.isChanged = true; ++i; if( i >= trace.length ) break; node.carryCount += sendCount; // carry them onward, to the end } } private boolean isChanged; private static VotorolaRuntimeException newReadOnlyException() { return new VotorolaRuntimeException( "write attempt on deserialized (read only) node" ); } /** Does a cyclic uncast-and-carry. This the more complicated case * of {@linkplain #uncastStraight(boolean,CountNode[]) uncastStraight}(toCarry,trace), * and the opposite of castCarryCyclic(trace), * ({@linkplain #castCarryCyclic(CountNode[]) q.v.} * for equations and other details). *

* Again, let the following denote a series of nodes * in two states C and B. *

* 
      *          -> C[0] -> C[1] -> C[2] -> ... -> C[n-1] --
      *         |                                           |
      *          - - - - - - - - - - - - - - - - - - - - - -
      *
      *
      *          -> B[0]    B[1] -> B[2] -> ... -> B[n-1] --
      *         |                                           |
      *          - - - - - - - - - - - - - - - - - - - - - -
      *
*

* Given vote counts for C, calculate those for B (cast and carry withdrawn). *

* 
 (7)
      *         B[i].hold  =  0 ,   for i = 1...n-1
      *
*

* Equation 7 is true because all votes cascade to B[0]. * The B series has no cycle, so no other node holds votes. *

* 
 (8)
      *         C[i].carry  -  B[i].carry  =  sum( C[j].hold ) ,  or
      *
      *         B[i].carry  =  C[i].carry - sum( C[j].hold ) ,
      *
      *         for i = 1...n-1 ,   j = i+1...n-1
      *
*

* When N[0] is originally cast, the increase in carriage it caused * at each node had to be balanced by an increase in holds * among that node's successors. And there could have been * no increase in carriage at N[n-1] (1). So equation 8 must hold. *

*

* Known are B[i].hold (7) and B[i].carry (8), for i = 1...n-1. * So B[i].receive may be calculated (5). *

*

* It only remains to solve for B[0]. But its vote is witheld, * so there is no carriage to other nodes: *

* 
 (9)
      *         B[0].carry  =  0
      *
*

* Known are B[0].carry (9) and B[0].receive (1). So B[0].hold may be calculated (5). *

*/ private void uncastCarryCyclic( final CountNode[] trace ) { long successorHoldSum = 0L; // so far assert trace.length > 1; for( int i = trace.length - 1; i >= 1; --i ) { final CountNode node = trace[i]; final long wasHeld = node.holdCount(); node.carryCount -= successorHoldSum; // (8) node.receiveCount = node.carryCount; // so now holding 0 (7) node.isChanged = true; successorHoldSum += wasHeld; } isCast = false; carryCount = 0L; // (9), and receiveCount unchanged (1) isChanged = true; } /** Does either a simple withdrawal (single vote) * or an acyclic withdrawal-and-carry. * * @see #castStraight(boolean,CountNode[]) * @see #castCarryCyclic(CountNode[]) */ private void uncastStraight( final boolean toCarry, final CountNode[] trace ) { isCast = false; isChanged = true; final long withdrawCount; if( toCarry ) { withdrawCount = receiveCount + 1L; // withdraw them all carryCount = 0L; // hold them } else withdrawCount = 1L; assert trace.length > 1; for( int i = 1;; ) { final CountNode node = trace[i]; node.receiveCount -= withdrawCount; node.isChanged = true; ++i; if( i >= trace.length ) break; node.carryCount -= withdrawCount; // withdraw them onward, to the end } } }