Submission c6833ddb...

ChallengeRemove duplicate elements
Submitterricmoo.firefly.eth
Submitted at2018-45-25
Gas used881457
/**
 * 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 {
    /**
     * @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 length = input.length;
        if (length <= 1) { return input; }

        uint256 filter = 0;

        uint256 bloomFilter = 0;
        uint256 smallFilter = 0;

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

            if (v <= 0xff) {
                filter = 2 ** v;
                if ((smallFilter & filter) != 0) { continue; }
                smallFilter |= filter;

            } else {
                filter = 2 ** ((v * 211) & 0xff);
                if ((bloomFilter & filter) == 0) {
                } else {
                    for (uint j = 0; j < ptr; j++) {
                        if (input[j] == v) {
                            filter = 0;
                            break;
                        }
                    }
                    if (filter == 0) { continue; }
                }
                bloomFilter |= filter;
            }

            input[ptr++] = v;
        }

        assembly {
            mstore(input, ptr)
        }

        return input;
    }
}