BidBasedCrowdSale.sol

contract Token {

    /// @return total amount of tokens
    function totalSupply() constant returns (uint256 supply) {}

    /// @param _owner The address from which the balance will be retrieved
    /// @return The balance
    function balanceOf(address _owner) constant returns (uint256 balance) {}

    /// @notice send `_value` token to `_to` from `msg.sender`
    /// @param _to The address of the recipient
    /// @param _value The amount of token to be transferred
    /// @return Whether the transfer was successful or not
    function transfer(address _to, uint256 _value) returns (bool success) {}

    /// @notice send `_value` token to `_to` from `_from` on the condition it is approved by `_from`
    /// @param _from The address of the sender
    /// @param _to The address of the recipient
    /// @param _value The amount of token to be transferred
    /// @return Whether the transfer was successful or not
    function transferFrom(address _from, address _to, uint256 _value) returns (bool success) {}

    /// @notice `msg.sender` approves `_addr` to spend `_value` tokens
    /// @param _spender The address of the account able to transfer the tokens
    /// @param _value The amount of wei to be approved for transfer
    /// @return Whether the approval was successful or not
    function approve(address _spender, uint256 _value) returns (bool success) {}

    /// @param _owner The address of the account owning tokens
    /// @param _spender The address of the account able to transfer the tokens
    /// @return Amount of remaining tokens allowed to spent
    function allowance(address _owner, address _spender) constant returns (uint256 remaining) {}

    event Transfer(address indexed _from, address indexed _to, uint256 _value);
    event Approval(address indexed _owner, address indexed _spender, uint256 _value);
}

library Heap {
    function siftDown(uint[] storage entries, uint[] storage priorities, uint count, uint idx) internal {
        uint entry;
        uint priority;
        while (idx < count) {
            uint c1 = idx * 2 + 1;
            uint c2 = c1 + 1;
            if (c1 < count && priorities[c1] < priorities[idx]) {
                // Sift down to left child
                entry = entries[c1];
                priority = priorities[c1];
                entries[c1] = entries[idx];
                priorities[c1] = priorities[idx];
                entries[idx] = entry;
                priorities[idx] = priority;
                idx = c1;
            } else if (c2 < count && priorities[c2] < priorities[idx]) {
                // Sift down to right child
                entry = entries[c2];
                priority = priorities[c2];
                entries[c2] = entries[idx];
                priorities[c2] = priorities[idx];
                entries[idx] = entry;
                priorities[idx] = priority;
                idx = c2;
            } else {
                return;
            }
        }
    }

    function bubbleUp(uint[] storage entries, uint[] storage priorities, uint idx) internal {
        uint maxIdx = entries.length - 1;
        uint entry;
        uint priority;
        while (idx > 0) {
            uint p = (idx - 1) / 2;
            if (priorities[p] >= priorities[idx]) {
                // Bubble up to the parent
                entry = entries[p];
                priority = priorities[p];
                entries[p] = entries[idx];
                priorities[p] = priorities[idx];
                entries[idx] = entry;
                priorities[idx] = priority;
                idx = p;
            } else {
                return;
            }
        }
    }
}

contract BidBasedCrowdSale {
    uint public totalUnits;
    uint public unitsSold;
    uint public lotSize;
    uint public minimumPrice;
    uint public priceIncrement;
    uint public deadline;
    Token public currency;
    Token public reward;

    struct Bid {
        address bidder;
        uint unitsBid;
        uint priceBid;
        uint unitsAllocated;
        bool redeemed;
    }

    Bid[] public bids;
    uint[] public bidHeap;
    uint[] public bidHeapPriorities;
    uint public bidHeapCount;

    function getBidCount() returns (uint) {
        return bids.length;
    }

    function BidBasedCrowdSale(Token _reward, Token _currency, uint _totalUnits, uint _lotSize, uint _minimumPrice, uint _priceIncrement, uint _deadline) {
        reward = _reward;
        currency = _currency;
        totalUnits = _totalUnits;
        lotSize = _lotSize;
        minimumPrice = _minimumPrice;
        priceIncrement = _priceIncrement;
        unitsSold = 0;
        deadline = _deadline;
    }

    modifier beforeDeadline() {
        if (now < deadline) _;
    }

    modifier afterDeadline() {
        if (now >= deadline) _;
    }

    event BidAccepted(uint, address, uint, uint);
    event BidExceeded(uint, address, uint);
    function bid(uint128 amount, uint128 price) beforeDeadline returns (uint) {
        if ((amount < lotSize) || (amount % lotSize != 0)) {
            throw;
        }

        /*
        if (amount > totalUnits) {
            throw;
        }
        */

        if ((price < minimumPrice) || (price % priceIncrement != 0)) {
            throw;
        }

        if (!currency.transferFrom(msg.sender, this, amount * price)) {
            throw;
        }

        uint freeUnits = totalUnits - unitsSold;
        if (freeUnits > amount) {
            freeUnits = amount;
        }
        unitsSold += freeUnits;

        uint priority = (((uint) (price)) * 18446744073709551616) + ((uint64) (deadline - now));
        while (amount > freeUnits && bidHeapCount > 0 && bidHeapPriorities[0] < priority) {
            uint available = bids[bidHeap[0]].unitsAllocated;
            uint returnAmount;
            if (freeUnits + available > amount) {
                // Remove the amount required from this bid, leaves a non-zero amount
                returnAmount = amount - freeUnits;
                bids[bidHeap[0]].unitsAllocated -= returnAmount;
                BidExceeded(bidHeap[0], bids[bidHeap[0]].bidder, bids[bidHeap[0]].unitsAllocated);
                currency.transfer(bids[bidHeap[0]].bidder, (amount - freeUnits) * bids[bidHeap[0]].priceBid);
                freeUnits = amount;
            } else {
                // This bid must be removed to make way for the new one
                returnAmount = bids[bidHeap[0]].unitsAllocated;
                BidExceeded(bidHeap[0], bids[bidHeap[0]].bidder, 0);
                currency.transfer(bids[bidHeap[0]].bidder, (amount - freeUnits) * bids[bidHeap[0]].priceBid);
                bids[bidHeap[0]].unitsAllocated = 0;

                // Remove the current minimum bid
                bidHeapCount--;
                bidHeap[0] = bidHeap[bidHeapCount];
                bidHeapPriorities[0] = bidHeapPriorities[bidHeapCount];
                Heap.siftDown(bidHeap, bidHeapPriorities, bidHeapCount, 0);

                freeUnits += available;
            }
        }

        if (freeUnits > 0) {
            // Insert the new bid
            uint bidId = bids.length;
            bids.push(Bid(msg.sender, amount, price, freeUnits, false));
            if (bidHeap.length <= bidHeapCount) {
                bidHeap.push(bidId);
                bidHeapPriorities.push(priority);
            } else {
                bidHeap[bidHeapCount] = bidId;
                bidHeapPriorities[bidHeapCount] = priority;
            }
            Heap.bubbleUp(bidHeap, bidHeapPriorities, bidHeapCount);
            bidHeapCount++;

            BidAccepted(bidId, msg.sender, freeUnits, price);
        }

        uint unallocated = amount - freeUnits;
        if (unallocated > 0) {
            currency.transfer(msg.sender, unallocated * price);
        }
    }

    function recoverUnits(uint bidId) afterDeadline {
        if (bidId >= bids.length) {
            throw;
        }

        Bid storage bid = bids[bidId];
        if (bid.unitsAllocated > 0 && !bid.redeemed) {
            bid.redeemed = true;
            reward.transfer(bid.bidder, bid.unitsAllocated);
        }
    }
}