Skip to content

Instantly share code, notes, and snippets.

@seresistvanandras
Last active June 13, 2018 14:35
Show Gist options
  • Save seresistvanandras/c89574dbece7a71bddf9b0f847a21334 to your computer and use it in GitHub Desktop.
Save seresistvanandras/c89574dbece7a71bddf9b0f847a21334 to your computer and use it in GitHub Desktop.
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) {
       if(input.length < 2) {
           return input;
       }

       uint lengthOfKeySpace = 256;

       uint[] memory hashToNumber = new uint[](lengthOfKeySpace);
       uint[] memory index = new uint[](input.length);
       uint counter = 0;
       bool nullValue;

       for(uint i; i < input.length; i++) {
           uint hash = input[i]&255;

           while(hashToNumber[hash]!=0 && hashToNumber[hash]!=input[i]) {
               hash=(hash+1)%lengthOfKeySpace;
           }


           if(hashToNumber[hash]==0 && input[i] != 0) {
               hashToNumber[hash] = input[i];
               index[counter] = input[i];
               counter++;
           }
           else if(!nullValue && input[i] == 0){
               nullValue = true;
               counter++;
           }
       }

       ret = new uint[](counter);
       for(i=0; i < counter; i++) {
           ret[i] = index[i];
       }
   }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment