Solidity – Is it Possible to Sort an Array of Structs? – UnimplementedFeatureError

solidity

I'm getting the following error trying to sort an array of Structs.

UnimplementedFeatureError: Copying of type struct
SortStruct.TestStruct memory[] memory to storage not yet supported.

Contract:

pragma solidity ^0.5;

contract SortStruct {


    struct TestStruct {
        address user;
        uint256 value;
    }
    TestStruct[] public testStructArray;
    TestStruct[] public sortedArray;

    function add(uint256 _value) public {


        TestStruct memory test;

        test.value = _value;
        testStructArray.push(test);

    }


    function sort() public {
        sortedArray = sort(testStructArray);
    }


    // 
    // sort
    // 
    function sort(TestStruct[] memory  data) internal returns (TestStruct[] memory) {
       quickSort(data, int(0), int(data.length - 1));
       return data;
    }

    function quickSort(TestStruct[] memory arr, int left, int right) internal {
        int i = left;
        int j = right;
        if(i==j) return;
        uint pivot = arr[uint(left + (right - left) / 2)].value;
        while (i <= j) {
            while (arr[uint(i)].value < pivot) i++;
            while (pivot < arr[uint(j)].value) j--;
            if (i <= j) {

                // swap
                TestStruct memory tempSortCandidate;
                tempSortCandidate = arr[uint(i)];
                arr[uint(i)] = arr[uint(j)];
                arr[uint(j)] = tempSortCandidate;

                i++;
                j--;
            }
        }
        if (left < j)
            quickSort(arr, left, j);
        if (i < right)
            quickSort(arr, i, right);
    }

}

Best Answer

This sorts Struct arrays for me. Obviously its not efficient (I didn't want to take the time to adapt your bubble sort, sry), but the construct should work. Let me know if this helped you :)

pragma solidity ^0.5;

contract SortStruct {

    struct TestStruct {
        address user;
        uint256 value;
    }

/** The left uint of the helper mapping is the items current index in testStructArray,
 ** the right uint is the destination index in sortedArray.*/
    mapping (uint => uint) helper;

    TestStruct[] public testStructArray;
    TestStruct[] public sortedArray;

    function add(uint256 _value) public {

        TestStruct memory test;

        test.value = _value;
        test.user = msg.sender;
        testStructArray.push(test);

    }

    function sort () public {

/** Loop through the original array to sort it*/
        for (uint i = 0; i < testStructArray.length; i++) {

/** Set the mapping to 0 initially. Later on all mapping entries will be the actual index +1.
 ** This is done, because an element larger than all compared elements will keep its 0 mapping
 ** throughout all comparisons and is assigned the new largest index in the end. If the acutal
 ** idexes were used, an element smaller than all others might falsely be assigned the largest
 ** index, because it got through the comparisons with mapping value 0.*/
            helper[i] = 0;

/** Compare the current element to all items that have already been sorted*/
            for (uint j = 0; j < i; j++){

/** If the item is smaller that the item it is compared against, sort it accordingly.*/
                if (testStructArray[i].value < testStructArray[j].value) {

/** The first time the new value is smaller than a sorted entry, set the mapping to that entry*/
                    if(helper[i] == 0){
                        helper[i] = helper[j];
                    }

/** Every time the new value is smaller than the (already sorted) value it is compared against,
 ** increment the index of the bigger item in the sorted array. */
                    helper[j] = helper[j] + 1;
                }
            }

/** Catch every entry that is larger than all previously sorted items*/
            if(helper[i] == 0) {
                helper[i] = i + 1;
            }
        }

/** Initialize the sortedArray to the same size as the testStructArray. Skip as many entries as
 ** the sortedArray already has, otherwise the sortedArray would double in size each time the
 ** function is called.*/
        var lengthSortedArray = sortedArray.length;
        for (uint i = 0; i < testStructArray.length; i++) {
            if (i < lengthSortedArray) continue;
            sortedArray.push(TestStruct(msg.sender, 0));
        }

/** Go over the testStructArray and copy the items to sortedArray to the positions specified in
 ** the helper mapping. At this point subtract the added 1, to get the real index */
        for (uint i = 0; i < testStructArray.length; i++) {
            sortedArray[helper[i]-1] = testStructArray[i];
        }
    }
}
Related Topic