Submission 50f37cfc...

ChallengeRemove duplicate elements
Submitterricmoo.firefly.eth
Submitted at2018-08-24
Gas used958472
/**
 * This file is part of the 1st Solidity Gas Golfing Contest.
 *
 * This work is licensed under Creative Commons Attribution ShareAlike 3.0.
 * https://creativecommons.org/licenses/by-sa/3.0/
 *
 *  Author: Richard Moore <[email protected]>
 *  Date:   May 24, 2018
 */

pragma solidity 0.4.24;

contract Unique {

    function isUnique(uint[] input, uint length, uint value) private pure returns(uint256) {
        for (uint i = 0; i < length; i++) {
            if (input[i] == value) { return 0; }
        }
        return 1;
    }

    /**
     * @dev Removes all but the first occurrence of each element from a list of
     *      integers, preserving the order of original elements, and returns the list.
     *
     * The input list may be of any length.
     *
     * @param input The list of integers to uniquify.
     * @return The input list, with any duplicate elements removed.
     */
    function uniquify(uint[] input) public pure returns(uint[] ret) {

        uint256 filter = 0;

        uint256 bloomFilter = 0;
        uint256 smallFilter = 0;

        uint256 ptr = 0;
        for (uint256 i = 0; i < input.length; i++) {
            uint256 v = input[i];

            if (v & 0xff == v) {
                filter = (uint256(1) << v);
                if (smallFilter & filter != 0) {
                    continue;
                }
                smallFilter |= filter;
            } else {
                filter = (uint256(1) << ((v * 211) & 0xff));
                if ((bloomFilter & filter) == 0) {
                } else if (isUnique(input, i, v) == 0) {
                    continue;
                }
                bloomFilter |= filter;
            }

            input[ptr++] = v;
        }

        ret = new uint[](ptr);
        for(i = 0; i < ret.length; i++) {
            ret[i] = input[i];
        }

        return ret;
    }

}