Submission 33d05573...

ChallengeRemove duplicate elements
Submitterhyszeth.eth
Submitted at2018-54-28
Gas used328211
/**
 * 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: Greg Hysen (@hysz)
 * Date: June 2018
 * Description of Algorithm: Uses a hash table to perform lookups.
 */

pragma solidity 0.4.24;

contract Unique {
    uint constant HASH_TABLE_SIZE = 313;
    uint constant HASH_TABLE_MOD = HASH_TABLE_SIZE - 1;
    uint constant RAND_OFFSET = 0x613c12789c3f663a544355053c9e1e25d50176d60796a155f553aa0f8445ee66;

    /**
     * @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) {
        uint inputLength = input.length;
        if(inputLength == 0 || inputLength == 1) return input;
        ret = uniquifyPrivate(input, inputLength);
        return ret;
    }

    function uniquifyPrivate(uint[] input, uint inputLength)
    private
    pure
    returns(uint[]) {
        uint uniqueIndex;
        uint[HASH_TABLE_SIZE] memory cache;
        uint current;
        uint quickHash;
        uint currentCache;
        uint i;
        uint currentCacheOffset;
        uint lastUnique;
        for(;i != inputLength;) {
            current = input[i];
            if((currentCacheOffset = current + RAND_OFFSET) == lastUnique) {
                ++i;
                continue;
            }
            if((currentCache=cache[(quickHash = current % HASH_TABLE_SIZE)]) == 0) {
                if(uniqueIndex != i++) input[uniqueIndex] = current;
                uniqueIndex++;
                cache[quickHash] = lastUnique = currentCacheOffset;
                continue;
            }

            // Scan unique list for duplicates
            while(currentCache != currentCacheOffset) {
                // Look for next spot
                if(++quickHash == HASH_TABLE_SIZE) quickHash = 1;
                if((currentCache = cache[quickHash]) == 0) {
                    if(uniqueIndex != i) input[uniqueIndex] = current;
                    uniqueIndex++;
                    cache[quickHash] = lastUnique = currentCacheOffset;
                    break;
                }
            }
            ++i;
        }

        // Check if all unique
        if(i == uniqueIndex) return input;
        return createUniqueList(input, uniqueIndex);
    }

    // Separate into its own function to avoid compiler optimizations
    // creeating an array before we need it. Saved ~4k gas in tests.
    function createUniqueList(uint[] input, uint uniqueIndex)
        private
        pure
        returns(uint[] ret)
    {
        // Copy unique elements from `input` to `ret`
        // Grouping together in this case saved about 10k gas.
        ret = new uint[](uniqueIndex);
        uint max = uniqueIndex/10 * 10;
        uint i;
        while(i != max) {
            ret[i++] = input[i];
            ret[i++] = input[i];
            ret[i++] = input[i];
            ret[i++] = input[i];
            ret[i++] = input[i];
            ret[i++] = input[i];
            ret[i++] = input[i];
            ret[i++] = input[i];
            ret[i++] = input[i];
            ret[i++] = input[i];
        }
        while(i != uniqueIndex) ret[i++] = input[i];
        return ret;
    }
}