<commit_before>#!/usr/bin/env python
#
# Licensed to the Apache Software Foundation (ASF) under one
# or more contributor license agreements.  See the NOTICE file
# distributed with this work for additional information
# regarding copyright ownership.  The ASF licenses this file
# to you under the Apache License, Version 2.0 (the
# "License"); you may not use this file except in compliance
# with the License.  You may obtain a copy of the License at
#
#   http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing,
# software distributed under the License is distributed on an
# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
# KIND, either express or implied.  See the License for the
# specific language governing permissions and limitations
# under the License.
#

#
# The algorithms in this file are lifted from:
#   http://votesystem.cvs.sourceforge.net/viewvc/votesystem/votesystem/src/VoteMain.java?view=markup
#

import random

ELECTED = 1
HOPEFUL = 2
ELIMINATED = 4
ALMOST = 8

ERROR_MARGIN = 0.00001
BILLIONTH = 0.000000001


def load_votes(fname):
  lines = open(fname).readlines()
  names = [s.strip() for s in lines[1].strip().split(',')][1:]
  labels = [s.strip() for s in lines[2].strip().split(',')][1:]
  assert len(names) == len(labels)
  remap = dict(zip(labels, names))

  votes = { }
  for line in lines[3:]:
    parts = line.strip().split(',')
    votes[parts[0]] = [remap[l] for l in parts[1:]]
  return names, votes


def run_vote(names, votes, num_seats):
  num_cand = len(names)
  randset = generate_random(num_cand)

  remap = { }  # name -> Candidate
  candidates = [ ]
  for n, r in zip(names, randset):
    c = Candidate(n, r, num_cand-1)
    remap[n] = c
    candidates.append(c)

  for choices in votes.values():
    for i in range(len(choices)):
      choices[i] = remap[choices[i]]

  if count_state(candidates, ELECTED + HOPEFUL) <= num_seats:
    dbg('All candidates elected')
    change_state(candidates, HOPEFUL, ELECTED)
    return
  if num_seats <= 0:
    change_state(candidates, HOPEFUL, ELIMINATED)
    return

  quota = None  # not used on first pass
  iteration = 1
  while count_state(candidates, ELECTED) < num_seats:
    dbg('Iteration %d', iteration)
    iteration += 1
    quota = iterate_one(quota, votes, candidates, num_seats)
    reverse_random(candidates)

  dbg('All seats full')
  change_state(candidates, HOPEFUL, ELIMINATED)

  for c in candidates:
    print '%-40s%selected' % (c.name, c.status == ELECTED and ' ' or ' not ')

  
class Candidate(object):
  def __init__(self, name, rand, ahead):
    self.name = name
    self.rand = rand
    self.ahead = ahead
    self.status = HOPEFUL
    self.weight = 1.0
    self.vote = None  # calculated later

  def elect(self):
    self.status = ELECTED
    dbg('Elected: %s', self.name)

  def eliminate(self):
    self.status = ELIMINATED
    self.weight = 0.0
    dbg('Eliminated: %s', self.name)

  def adjust_weight(self, quota):
    assert quota is not None
    self.weight = (self.weight * quota) / self.vote


def iterate_one(quota, votes, candidates, num_seats):
  # assume that: count(ELECTED) < num_seats
  if count_state(candidates, ELECTED + HOPEFUL) <= num_seats:
    dbg('All remaining candidates elected')
    change_state(HOPEFUL, ELECTED)
    return None

  changed, new_quota, surplus = converge_one(quota, votes, candidates,
                                             num_seats)
  if not changed and surplus < ERROR_MARGIN:
    dbg('Remove Lowest (forced)')
    exclude_lowest(candidates)
  return new_quota


def converge_one(quota, votes, candidates, num_seats):
  for c in candidates:
    if c.status == ELECTED:
      c.adjust_weight(quota)
  return recalc(votes, candidates, num_seats)


def recalc(votes, candidates, num_seats):
  any_changed = False
  excess = calc_totals(votes, candidates)
  calc_aheads(candidates)
  ### if debug:
  display_tables(excess, candidates)
  quota = calc_quota(len(votes), excess, num_seats)
  elect(quota, candidates, num_seats)
  surplus = calc_surplus(quota, candidates)
  any_changed |= try_remove_lowest(surplus, candidates)
  return any_changed, quota, surplus


def calc_totals(votes, candidates):
  for c in candidates:
    c.vote = 0.0
  excess = 0.0
  for choices in votes.values():
    vote = 1.0
    for c in choices:
      if c.status == HOPEFUL:
        c.vote += vote
        vote = 0.0
        break
      if c.status != ELIMINATED:
        wv = c.weight * vote  # weighted vote
        c.vote += wv
        vote -= wv
        if vote == 0.0:  # nothing left to distribute
          break
    excess += vote
  return excess


def calc_aheads(candidates):
  def compare_candidates(c1, c2):
    if c1.ahead < c2.ahead:
      return -1
    if c1.ahead == c2.ahead:
      return cmp(c1.vote, c2.vote)
    return 1

  c_sorted = sorted(candidates, compare_candidates)
  last = 0
  for i in range(1, len(c_sorted)+1):
    if i == len(c_sorted) \
          or compare_candidates(c_sorted[last], c_sorted[i]) != 0:
      for c in c_sorted[last:i]:
        c.ahead = (i - 1) + last
      last = i<commit_msg>Use __cmp__ rather than a custom comparator function.<commit_after>#!/usr/bin/env python
#
# Licensed to the Apache Software Foundation (ASF) under one
# or more contributor license agreements.  See the NOTICE file
# distributed with this work for additional information
# regarding copyright ownership.  The ASF licenses this file
# to you under the Apache License, Version 2.0 (the
# "License"); you may not use this file except in compliance
# with the License.  You may obtain a copy of the License at
#
#   http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing,
# software distributed under the License is distributed on an
# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
# KIND, either express or implied.  See the License for the
# specific language governing permissions and limitations
# under the License.
#

#
# The algorithms in this file are lifted from:
#   http://votesystem.cvs.sourceforge.net/viewvc/votesystem/votesystem/src/VoteMain.java?view=markup
#

import random

ELECTED = 1
HOPEFUL = 2
ELIMINATED = 4
ALMOST = 8

ERROR_MARGIN = 0.00001
BILLIONTH = 0.000000001


def load_votes(fname):
  lines = open(fname).readlines()
  names = [s.strip() for s in lines[1].strip().split(',')][1:]
  labels = [s.strip() for s in lines[2].strip().split(',')][1:]
  assert len(names) == len(labels)
  remap = dict(zip(labels, names))

  votes = { }
  for line in lines[3:]:
    parts = line.strip().split(',')
    votes[parts[0]] = [remap[l] for l in parts[1:]]
  return names, votes


def run_vote(names, votes, num_seats):
  num_cand = len(names)
  randset = generate_random(num_cand)

  remap = { }  # name -> Candidate
  candidates = [ ]
  for n, r in zip(names, randset):
    c = Candidate(n, r, num_cand-1)
    remap[n] = c
    candidates.append(c)

  for choices in votes.values():
    for i in range(len(choices)):
      choices[i] = remap[choices[i]]

  if count_state(candidates, ELECTED + HOPEFUL) <= num_seats:
    dbg('All candidates elected')
    change_state(candidates, HOPEFUL, ELECTED)
    return
  if num_seats <= 0:
    change_state(candidates, HOPEFUL, ELIMINATED)
    return

  quota = None  # not used on first pass
  iteration = 1
  while count_state(candidates, ELECTED) < num_seats:
    dbg('Iteration %d', iteration)
    iteration += 1
    quota = iterate_one(quota, votes, candidates, num_seats)
    reverse_random(candidates)

  dbg('All seats full')
  change_state(candidates, HOPEFUL, ELIMINATED)

  for c in candidates:
    print '%-40s%selected' % (c.name, c.status == ELECTED and ' ' or ' not ')

  
class Candidate(object):
  def __init__(self, name, rand, ahead):
    self.name = name
    self.rand = rand
    self.ahead = ahead
    self.status = HOPEFUL
    self.weight = 1.0
    self.vote = None  # calculated later

  def elect(self):
    self.status = ELECTED
    dbg('Elected: %s', self.name)

  def eliminate(self):
    self.status = ELIMINATED
    self.weight = 0.0
    dbg('Eliminated: %s', self.name)

  def adjust_weight(self, quota):
    assert quota is not None
    self.weight = (self.weight * quota) / self.vote

  def __cmp__(self, other):
    if self.ahead < other.ahead:
      return -1
    if self.ahead == other.ahead:
      return cmp(self.vote, other.vote)
    return 1


def iterate_one(quota, votes, candidates, num_seats):
  # assume that: count(ELECTED) < num_seats
  if count_state(candidates, ELECTED + HOPEFUL) <= num_seats:
    dbg('All remaining candidates elected')
    change_state(HOPEFUL, ELECTED)
    return None

  changed, new_quota, surplus = converge_one(quota, votes, candidates,
                                             num_seats)
  if not changed and surplus < ERROR_MARGIN:
    dbg('Remove Lowest (forced)')
    exclude_lowest(candidates)
  return new_quota


def converge_one(quota, votes, candidates, num_seats):
  for c in candidates:
    if c.status == ELECTED:
      c.adjust_weight(quota)
  return recalc(votes, candidates, num_seats)


def recalc(votes, candidates, num_seats):
  any_changed = False
  excess = calc_totals(votes, candidates)
  calc_aheads(candidates)
  ### if debug:
  display_tables(excess, candidates)
  quota = calc_quota(len(votes), excess, num_seats)
  elect(quota, candidates, num_seats)
  surplus = calc_surplus(quota, candidates)
  any_changed |= try_remove_lowest(surplus, candidates)
  return any_changed, quota, surplus


def calc_totals(votes, candidates):
  for c in candidates:
    c.vote = 0.0
  excess = 0.0
  for choices in votes.values():
    vote = 1.0
    for c in choices:
      if c.status == HOPEFUL:
        c.vote += vote
        vote = 0.0
        break
      if c.status != ELIMINATED:
        wv = c.weight * vote  # weighted vote
        c.vote += wv
        vote -= wv
        if vote == 0.0:  # nothing left to distribute
          break
    excess += vote
  return excess


def calc_aheads(candidates):
  c_sorted = sorted(candidates)
  last = 0
  for i in range(1, len(c_sorted)+1):
    if i == len(c_sorted) or c_sorted[last] != c_sorted[i]:
      for c in c_sorted[last:i]:
        c.ahead = (i - 1) + last
      last = i
{'fraction_non_alphanumeric': 0.11046171829339567, 'fraction_numerical': 0.011981297486849795, 'mean_word_length': 3.2513457556935816, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3159838', 'n_tokens_mistral': 3636, 'n_tokens_neox': 3464, 'n_words': 1018}