Submission 5c162a81...
/**
* 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 {
//event E(uint);
/**
* @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.
*/
uint constant HASH_TABLE_SIZE = 733;
uint constant HASH_TABLE_MOD = HASH_TABLE_SIZE - 1;
uint constant RAND_OFFSET = 0x613c12789c3f663a544355053c9e1e25d50176d60796a155f553aa0f8445ee66;
function uniquify(uint[] input)
public
pure
returns(uint[] ret) {
uint inputLength = input.length;
if(inputLength == 0) return ret;
uint uniqueIndex;
uint[HASH_TABLE_SIZE] memory cache;
uint current;
uint quickHash;
uint currentCache;
uint i = 0;
for(;i < inputLength; ++i) {
current = input[i];
uint currentCacheOffset = current + RAND_OFFSET;
if((currentCache=cache[(quickHash = current % HASH_TABLE_SIZE)]) == 0) {
if(uniqueIndex != i) input[uniqueIndex] = current;
uniqueIndex++;
cache[quickHash] = 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] = currentCacheOffset;
break;
}
}
}
// Check if all unique
if(i == uniqueIndex) {
ret = input;
return;
}
// 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;
i = 0;
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;
}
}