# SchellingCoin implementation
#
# Epoch length: 100 blocks
# Target savings depletion rate: 0.1% per epoch

data epoch
data hashes_submitted
data output
data quicksort_pairs
data accounts[2^160]
data submissions[2^80](hash, deposit, address, value)
extern any: [call]


def init():
    self.epoch = block.number / 100
    self.quicksort_pairs = create('quicksort_pairs.se')

def any():
    if block.number / 100 > epoch:
        # Sort all values submitted
        N = self.hashes_submitted
        o = array(N * 2)
        i = 0
        j = 0
        while i < N:
            v = self.submissions[i].value
            if v:
                o[j] = v
                o[j + 1] = i
                j += 2
            i += 1
        values = self.quicksort_pairs.call(data=o, datasz=j, outsz=j)

        # Calculate total deposit, refund non-submitters and
        # cleanup

        deposits = array(j / 2)
        addresses = array(j / 2)
        
        i = 0
        total_deposit = 0
        while i < j / 2:
            base_index = HASHES + values[i * 2 + 1] * 3
            deposits[i] = self.submissions[i].deposit
            addresses[i] = self.submissions[i].address
            if self.submissions[values[i * 2 + 1]].value:
                total_deposit += deposits[i]
            else:
                send(addresses[i], deposits[i] * 999 / 1000)
            i += 1

        inverse_profit_ratio = total_deposit / (contract.balance / 1000) + 1

        # Reward everyone
        i = 0
        running_deposit_sum = 0
        halfway_passed = 0
        while i < j / 2:
            new_deposit_sum = running_deposit_sum + deposits[i]
            if new_deposit_sum > total_deposit / 4 and running_deposit_sum < total_deposit * 3 / 4:
                send(addresses[i], deposits[i] + deposits[i] / inverse_profit_ratio * 2)
            else:
                send(addresses[i], deposits[i] - deposits[i] / inverse_profit_ratio)

            if not halfway_passed and new_deposit_sum > total_deposit / 2:
                self.output = self.submissions[i].value
                halfway_passed = 1
            self.submissions[i].value = 0
            running_deposit_sum = new_deposit_sum
            i += 1
        self.epoch = block.number / 100
        self.hashes_submitted = 0
        
def submit_hash(h):
    if block.number % 100 < 50:
        cur = self.hashes_submitted
        pos = HASHES + cur * 3
        self.submissions[cur].hash = h
        self.submissions[cur].deposit = msg.value
        self.submissions[cur].address = msg.sender
        self.hashes_submitted = cur + 1
        return(cur)

def submit_value(index, v):
    if sha3([msg.sender, v], 2) == self.submissions[index].hash:
            self.submissions[index].value = v
            return(1)

def request_balance():
    return(contract.balance)

def request_output():
    return(self.output)