Skip to content

Instantly share code, notes, and snippets.

@seresistvanandras
Last active June 13, 2018 20:43
Show Gist options
  • Save seresistvanandras/7c0a5a2370f031f65c1b80130efd5c35 to your computer and use it in GitHub Desktop.
Save seresistvanandras/7c0a5a2370f031f65c1b80130efd5c35 to your computer and use it in GitHub Desktop.
function uniquify(uint[] input) public pure returns(uint[] ret) {
       if(input.length < 2) {
           return input;
       }

       uint lengthOfKeySpace = input.length*2;

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

       for(uint i = 0; i < input.length; i++) {
           uint hash = uint(sha3(input[i]))%lengthOfKeySpace;

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

           if(hashTable[hash]==0 && input[i] != 0) {
               hashTable[hash] = input[i];
               index[counter] = input[i];
               counter++;
           }
           else if(!nullValue && input[i] == 0){
               nullValue = true;
               hashTable[hash] = 0;
               index[counter] = 0;
               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