Submission c55b63cd...
/**
* 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/
*/
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) {
uint inLen = input.length;
uint outLen;
if (inLen < 2) {
return input;
} else if (inLen == 2) {
outLen = input[0] == input[1] ? 1 : 2;
} else if (inLen <= 32) {
outLen = uniquifyFew(input);
} else {
outLen = uniquifyMuch(input, inLen / 8);
}
if (inLen == outLen) {
return input;
}
else {
assembly {
mstore(sub(input, 0x20), 0x20)
mstore(input, outLen)
return(sub(input, 0x20), add(mul(0x20, outLen), 0x40))
}
}
}
function uniquifyFew(uint[] input) internal pure returns(uint) {
uint filter;
uint outLen;
for (uint i = 0; i < input.length; i++) {
uint h = input[i] % 255;
uint y = (1 << h);
if (filter & y == 0) {
filter = filter | y;
input[outLen] = input[i];
outLen += 1;
}
}
return outLen;
}
function uniquifyMuch(uint[] input, uint filterSize) internal pure returns(uint) {
uint[] memory filter = new uint[] (filterSize);
uint outLen;
uint magic = filterSize * 256 - 1;
for (uint i = 0; i < input.length; i++) {
uint h = input[i] % magic;
uint x = h / 256;
uint y = (1 << (h % 256));
if (filter[x] & y == 0) {
filter[x] = filter[x] | y;
input[outLen] = input[i];
outLen += 1;
}
}
return outLen;
}
}