Solidity Puzzle! How to get position in a list without looping over unbounded mapping?

Question

Consider I mint 10 CryptoDoggy NFTs, each with an incrementing ID, starting at 0. I also have a uint => uint mapping, which records the position of the NFT using its ID as a key. Initially, its position will be equal to its ID. So the 5th CryptoDoggy I mint will have ID 4 and position 4.

Now, say that I wish to burn the CryptoDoggy with ID 5. The CryptoDoggy with ID 6 is now in position 5, and likewise with all IDs above 5.

But, updating the positions by looping over the whole mapping is not an option if CryptoDoggy creation is unbounded.

So how, for example, would I get the position of the CryptoDoggy with ID 8, without looping over anything unbounded?

Answer 1

You have to separate concerns:

1. Confirming existence.
2. Random access.
3. Counting.
4. Iterating.
5. Deleting.
6. Sorting.

This is not a database system, so hidden assumptions about data organization will mislead you. You're 100% responsible for working it out appropriately. A rookie mistake is overloading the contracts with external concerns.

Deleting from an unordered list without iteration is accomplished by moving the last item into the row to delete and then shortening the list. That can be combined with unique IDs (enforced) and random access to arbitrary structs.

• The method is explained here: https://medium.com/robhitchens/solidity-crud-part-1-824ffa69509a

• There is a library for using the method in simplified, readable contracts, here: https://github.com/rob-Hitchens/UnorderedKeySet

Sorting is a separate concern. Before you make the mistake of implementing it when it isn't needed, have a look at this: https://medium.com/solidified/the-joy-of-minimalism-in-smart-contract-design-b67fb4073422. It will, hopefully, challenge assumptions about what you need.

If you still want a sorted list, consider:

• a self-balancing b-tree like: https://hackernoon.com/binary-search-trees-and-order-statistics-for-ethereum-db47e2dd2c36.
• linked lists with hints: https://bitbucket.org/rhitchens2/soliditystoragepatterns/src/master/LinkedList.sol

It's important to understand how the patterns scale and the strategies they use control gas cost. Chose wisely.

Hope it helps.

Answer 2

Let's say you need to store uint value and string name for each item in your data-base:

contract MyContract {
    uint[] public list;

    struct Item {
        bool valid;
        uint index;
        uint value; // example
        string name; // example
    }

    mapping(uint => Item) public table;

    /* Update or insert an item */
    function upsert(uint ID, uint value, string name) external {
        Item storage item = table[ID];
        if (!item.valid) {
            item.valid = true;
            item.index = list.length;
            list.push(ID);
        }
        item.value = value; // example
        item.name = name; // example
    }

    /* Remove an item */
    function remove(uint ID) external {
        Item storage item = table[ID];
        require(item.index < list.length);
        require(ID == list[item.index]);
        uint lastItem = list[list.length - 1];
        table[lastItem].index = item.index;
        list[item.index] = lastItem;
        list.length -= 1;
        delete table[ID];
    }

    /* Get the total number of items */
    function count() external view returns (uint) {
        return list.length;
    }
}

As you can see, there is no looping in this code.