Assignment - ERC721

Ethereum Smart Contract Programming 201
#146

What is the time complexity of creating new cats? (constant or linear w nr of cats).

  • Constant as we just need to push to the end of the kitties array.

What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).

  • Linear since we need to loop through the list of kitties. The bigger the list the longer it will take.

How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.

  • We can create a mapping(address => uint[]) ownership where the address would map to a list of Kitten IDs owned by that address. The benefits would be that we could get the IDs of owned Kitties in constant time. The drawback would be we would need to update 2 values when transferring a Kitten. One to remove it from the _from address and another for the _to address.
1 Like
#147

The creation of new cats is constant because the new cat is only added to the array of existing cats.

The time complexity of the getAllCatsFor function is linear since one has to loop through the whole array of cats to count all cats of a specific owner.

The ids of all cats of an owner is stored in an uint array. This saves a lot of execution time since we don’t have to loop through the whole array of cats to find all the cats of a particular owner.
But the process of transferring a cat gets more complicated because we have to find and delete the according array element instead of just subtracting 1 from the number of cats an owner possesses. This is done by overwriting the id of the transfered cat by the last element of the array. After that we only need to remove the last element of the array and the removal is complete.

Overall this version saves execution time. The transfer function is not called too often compared to the other functions in the contract.

pragma solidity ^0.8.0;

contract Kittycontract {

    string public constant name = "TestKitties";
    string public constant symbol = "TK";
    
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    event Birth(
        address owner, 
        uint256 kittenId, 
        uint256 mumId, 
        uint256 dadId, 
        uint256 genes
    );

    struct Kitty {
        uint256 genes;
        uint64 birthTime;
        uint32 mumId;
        uint32 dadId;
        uint16 generation;
    }

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
	// Replacing the original mapping by a new one: address -> array of uint256
    mapping (address => uint256[]) public ownershipTokenArray;


    function balanceOf(address owner) external view returns (uint256 balance){
        return ownershipTokenArray[owner].length;
    }

    function totalSupply() public view returns (uint) {
        return kitties.length;
    }

    function ownerOf(uint256 _tokenId) external view returns (address)
    {
        return kittyIndexToOwner[_tokenId];
    }

    function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
		// Just getting back the array of uint as return value
        cats = ownershipTokenArray[_owner];
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) private returns (uint256) {
        Kitty memory _kitty = Kitty({
            genes: _genes,
            birthTime: uint64(block.timestamp),
            mumId: uint32(_mumId),
            dadId: uint32(_dadId),
            generation: uint16(_generation)
        });
        
        kitties.push(_kitty);

        uint256 newKittenId = kitties.length - 1;

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

        _transfer(address(0), _owner, newKittenId);

        return newKittenId;

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        
        // Map the cat to the new owner
        kittyIndexToOwner[_tokenId] = _to;
        
        // Push the id of the cat to the list if ids for the user
        ownershipTokenArray[_to].push(_tokenId);

        // Remove the id of the cat from the list of the previous order if it was not a newly generated cat
        if (_from != address(0)) {
            _removeCatFromOwner(_from, _tokenId);
        }

        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }
    
    // Removes the id of the cat from the previous owners list
    function _removeCatFromOwner(address _owner, uint256 _tokenId) internal {
        // Loop though the cats of the owner's given address
        for (uint i = 0; i < ownershipTokenArray[_owner].length; i++) {
            
            // If the cat was found
            if (ownershipTokenArray[_owner][i] == _tokenId) {
                // Replace the cat by copying the last cat to this position
                ownershipTokenArray[_owner][i] = ownershipTokenArray[_owner][ownershipTokenArray[_owner].length-1];
                
                // Remove the duplicate at the end of the array
                ownershipTokenArray[_owner].pop();
                
                return;
            }
        }
    }

    function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
      return kittyIndexToOwner[_tokenId] == _claimant;
  }

}
1 Like
#148

What is the time complexity of creating new cats? (constant or linear w nr of cats)

As there is no looping through of recursions or calls to other non-constant time functions (which no matter the size of the array, the time complexity takes a constant amount of time to run, independently of the size of the input data), it is a CONSTANT time complexity for creating new cats.

What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats)

As this function requires a for loop to recursively get all the cat id's which are owned by a particular owner address, this is a LINEAR time complexity.
Essentially, this method of time complexity means that this function will take proportionally longer to complete.

How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation

ERC-721 Assignment

pragma solidity ^0.7.5;

contract Kittycontract {

string public constant name = "TestKitties";
string public constant symbol = "TK";

event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

event Birth(
    address owner, 
    uint256 kittenId, 
    uint256 mumId, 
    uint256 dadId, 
    uint256 genes
);

struct Kitty {
    uint256 genes;
    uint64 birthTime;
    uint32 mumId;
    uint32 dadId;
    uint16 generation;
}

Kitty[] kitties;

mapping (uint256 => address) public kittyIndexToOwner;
mapping (address => uint256[]) ownershipTokenCount;



function balanceOf(address owner) external view returns (uint256 balance){
    return ownershipTokenCount[owner].length;
}

function totalSupply() public view returns (uint) {
    return kitties.length;
}

function ownerOf(uint256 _tokenId) external view returns (address)
{
    return kittyIndexToOwner[_tokenId];
}

function transfer(address _to,uint256 _tokenId) external
{
    require(_to != address(0));
    require(_to != address(this));
    require(_owns(msg.sender, _tokenId));

    _transfer(msg.sender, _to, _tokenId);
}

function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
    //NEW CODE - CONSTANT O(1) time complexity
    //mapping cats array to find the token id(s) for the owner address.
    cats = ownershipTokenCount[_owner];
    
    // OLD CODE - LINEAR O(n) time complexity
    
    // uint[] memory result = new uint[](ownershipTokenCount[_owner]);
    // uint counter = 0;
    // for (uint i = 0; i < kitties.length; i++) {
    //     if (kittyIndexToOwner[i] == _owner) {
    //         result[counter] = i;
    //         counter++;
    //     }
    // }
    // return result;
}

function createKittyGen0(uint256 _genes) public returns (uint256) {
    return _createKitty(0, 0, 0, _genes, msg.sender);
}

function _createKitty(
    uint256 _mumId,
    uint256 _dadId,
    uint256 _generation,
    uint256 _genes,
    address _owner
) private returns (uint256) {
    Kitty memory _kitty = Kitty({
        genes: _genes,
        birthTime: uint64(block.timestamp),
        mumId: uint32(_mumId),
        dadId: uint32(_dadId),
        generation: uint16(_generation)
    });
    
    kitties.push(_kitty);

    uint256 newKittenId = kitties.length - 1;

    emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

    _transfer(address(0), _owner, newKittenId);

    return newKittenId;

}

function _transfer(address _from, address _to, uint256 _tokenId) internal {
    // ownershipTokenCount[_to]++;

    kittyIndexToOwner[_tokenId] = _to;
    ownershipTokenCount[_to].push(_tokenId);

    if (_from != address(0)) {
        for (uint256 i = 0; i < ownershipTokenCount[_from].length; i++) { //loop through the array of the owner
            if (ownershipTokenCount[_from][i] == _tokenId) { //if the token id in the array matches the one provided
                ownershipTokenCount[_from][i] = ownershipTokenCount[_from][ownershipTokenCount[_from].length - 1]; // Set the array member at that index equal to the member of the array
                ownershipTokenCount[_from].pop(); // delete the last member of the array
                break;
            }
        }
    }

    // Emit the transfer event.
    emit Transfer(_from, _to, _tokenId);
}

function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
  return kittyIndexToOwner[_tokenId] == _claimant;

}

}

The getAllCatsFor function could be made into a constant time complexity by taking out the for loop and changing to a mapped list instead.
Unfortunately, the drawback is that we would still require a linear time complexity for removing the cat id's from the owner address. This makes the contract slower for searching the index for the particular id's, but a necessary one for a constant O(1) execution.
The benefits would be less gas fees overall and a faster execution time compared to a fully linear time complexity.

:upside_down_face:

1 Like
#149
  1. The time complexity of creating new cats is constant.
  2. The time complexity of the getAllCatsFor function is linear as it needs to run through a loop of the Kitty array, thus taking up more time
  3. `pragma solidity ^0.8.0;

contract Kittycontract {

string public constant name = "TestKitties";
string public constant symbol = "TK";

event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

event Birth(
    address owner, 
    uint256 kittenId, 
    uint256 mumId, 
    uint256 dadId, 
    uint256 genes
);

struct Kitty {
    uint256 genes;
    uint64 birthTime;
    uint32 mumId;
    uint32 dadId;
    uint16 generation;
}

Kitty[] kitties;

mapping (uint256 => address) public kittyIndexToOwner;
mapping (address => uint256) ownershipTokenCount;
mapping (address => uint256[]) ownedCats;



function balanceOf(address owner) external view returns (uint256 balance){
    return ownershipTokenCount[owner];
}

function totalSupply() public view returns (uint) {
    return kitties.length;
}

function ownerOf(uint256 _tokenId) external view returns (address)
{
    return kittyIndexToOwner[_tokenId];
}

function transfer(address _to,uint256 _tokenId) external
{
    require(_to != address(0));
    require(_to != address(this));
    require(_owns(msg.sender, _tokenId));

    _transfer(msg.sender, _to, _tokenId);
}

function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
    return ownedCats [_owner];
}

function createKittyGen0(uint256 _genes) public returns (uint256) {
    return _createKitty(0, 0, 0, _genes, msg.sender);
}

function _createKitty(
    uint256 _mumId,
    uint256 _dadId,
    uint256 _generation,
    uint256 _genes,
    address _owner
) private returns (uint256) {
    Kitty memory _kitty = Kitty({
        genes: _genes,
        birthTime: uint64(block.timestamp),
        mumId: uint32(_mumId),
        dadId: uint32(_dadId),
        generation: uint16(_generation)
    });
    
    kitties.push(_kitty);

    uint256 newKittenId = kitties.length - 1;

    emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

    _transfer(address(0), _owner, newKittenId);

    return newKittenId;

}

function _transfer(address _from, address _to, uint256 _tokenId) internal {

    kittyIndexToOwner[_tokenId] = _to;

    if (_from != address(0)) {
        ownershipTokenCount[_from]--;
    }

    // Emit the transfer event.
    emit Transfer(_from, _to, _tokenId);
}

function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
  return kittyIndexToOwner[_tokenId] == _claimant;

}

function deleteCatOwnership(address _owner, uint256 _tokenId) internal {
    uint previousOwner = ownedCats[_owner][ownedCats[_owner].length-1];
    
    for(uint i = 0;i < ownedCats [_owner].length; i++){
        if (ownedCats[_owner] [i] == _tokenId) {
            ownedCats[_owner][i] = previousOwner;
            ownedCats[_owner].pop(); 
        }
    }
}

}`

With this implementation, the gas cost is cheaper and the contract runs faster, however we had to put in another loop in the deleteCatOwnership function, making the time complexity for this function linear.

1 Like
#150

1. What is the time complexity of creating new cats?

Constant, due to same steps needed each time a kitty is created.

2. What is the time complexity of the getAllCatsFor function?

Linear, since it loops through the array which grows in size as more kitties are added.

3. How could the storage design be changed to make the getAllCats function constant?

Use a mapping to map the address to an array of kitty IDs, update the function, and add a new function to account for deleting a cat from the owner’s owned cat array.

pragma solidity ^0.8.0;

contract KittyTwo {

    string public constant name = "TestKitties";
    string public constant symbol = "TK";
    
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    event Birth(
        address owner, 
        uint256 kittenId, 
        uint256 mumId, 
        uint256 dadId, 
        uint256 genes
    );

    struct Kitty {
        uint256 genes;
        uint64 birthTime;
        uint32 mumId;
        uint32 dadId;
        uint16 generation;
    }

    Kitty[] kitties;
    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => uint256[]) public ownedCats;


    function balanceOf(address owner) external view returns (uint256 balance){
        return ownedCats[owner].length;
    }

    function totalSupply() public view returns (uint) {
        return kitties.length;
    }

    function ownerOf(uint256 _tokenId) external view returns (address)
    {
        return kittyIndexToOwner[_tokenId];
    }

    function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getCatsfor(address _owner) external view returns (uint[] memory cats) {
        cats = ownedCats[_owner];
    }

    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) private returns (uint256) {
        Kitty memory _kitty = Kitty({
            genes: _genes,
            birthTime: uint64(block.timestamp),
            mumId: uint32(_mumId),
            dadId: uint32(_dadId),
            generation: uint16(_generation)
        });
        
        kitties.push(_kitty);

        uint256 newKittenId = kitties.length - 1;

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

        _transfer(address(0), _owner, newKittenId);

        return newKittenId;

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        kittyIndexToOwner[_tokenId] = _to;
        ownedCats[_to].push(_tokenId);

        if (_from != address(0)) {
            _removeOwnership(_from, _tokenId);
        }

        emit Transfer(_from, _to, _tokenId);
    }
    
    function _removeOwnership(address _owner, uint256 _tokenId) internal {

        for (uint i = 0; i < ownedCats[_owner].length; i++) {
            if (ownedCats[_owner][i] == _tokenId) {
                ownedCats[_owner][i] = ownedCats[_owner][ownedCats[_owner].length-1];
                ownedCats[_owner].pop();
                return;
            }
        }
    }    
    
    function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
      return kittyIndexToOwner[_tokenId] == _claimant;
  }

}

This increases the efficiency of the function getting all cats for an owner, but at the expense of more complexity with transfers of cats (new linear function).

1 Like
#151
  1. The time complexity is constant for all cats created.
  2. The time complexity goes up as the length of the array goes up.
  3. `pragma solidity ^0.8.0;

contract Kittycontract {

string public constant name = "TestKitties";
string public constant symbol = "TK";

event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

event Birth(
    address owner, 
    uint256 kittenId, 
    uint256 mumId, 
    uint256 dadId, 
    uint256 genes
);

struct Kitty {
    uint256 genes;
    uint64 birthTime;
    uint32 mumId;
    uint32 dadId;
    uint16 generation;
}

Kitty[] kitties;

mapping (uint256 => address) public kittyIndexToOwner;

mapping (address => uint256) ownershipTokenCount;

mapping (address => uint[]) ownerOfCats;




function balanceOf(address owner) external view returns (uint256 balance){
    return ownershipTokenCount[owner];
}

function totalSupply() public view returns (uint) {
    return kitties.length;
}

function ownerOf(uint256 _tokenId) external view returns (address)
{
    return kittyIndexToOwner[_tokenId];
}

function transfer(address _to,uint256 _tokenId) external
{
    require(_to != address(0));
    require(_to != address(this));
    require(_owns(msg.sender, _tokenId));

    _transfer(msg.sender, _to, _tokenId);
}

function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
    return ownerOfCats[_owner];
}

function createKittyGen0(uint256 _genes) public returns (uint256) {
    return _createKitty(0, 0, 0, _genes, msg.sender);
}

function _createKitty(
    uint256 _mumId,
    uint256 _dadId,
    uint256 _generation,
    uint256 _genes,
    address _owner
) private returns (uint256) {
    Kitty memory _kitty = Kitty({
        genes: _genes,
        birthTime: uint64(block.timestamp),
        mumId: uint32(_mumId),
        dadId: uint32(_dadId),
        generation: uint16(_generation)
    });
    
    kitties.push(_kitty);

    uint256 newKittenId = kitties.length - 1;

    emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

    _transfer(address(0), _owner, newKittenId);

    return newKittenId;

}

function _transfer(address _from, address _to, uint256 _tokenId) internal {
    ownershipTokenCount[_to]++;

    kittyIndexToOwner[_tokenId] = _to;
    ownerOfCats[_to].push(_tokenId);

    if (_from != address(0)) {
        ownershipTokenCount[_from]--;
    }

    // Emit the transfer event.
    emit Transfer(_from, _to, _tokenId);
}

function _removeTokenIdFromOwner(address _owner, uint _tokenId) internal {
    uint256 lastId = ownerOfCats[_owner][ownerOfCats[_owner].length-1];
    for (uint i = 0; i < ownerOfCats[_owner][i] == _tokenId) {
        ownerOfCats[_owner][i] = lastId;
        ownerOfCats[_owner].pop();
    }
    }
}


function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
  return kittyIndexToOwner[_tokenId] == _claimant;

}

}`

This is my final solution. It seems like a lot of code and extra functions for an internal function.

1 Like
#152

  1. Its constant since its the same procedure every time.

  2. Linear since we are working with newer and newer information every time.

  3. Store the info in a mapping and make the searching process easier and constant.

Code:

pragma solidity ^0.8.0;

contract Kittycontract {

    string public constant name = "TestKitties";
    string public constant symbol = "TK";
    
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    event Birth(
        address owner, 
        uint256 kittenId, 
        uint256 mumId, 
        uint256 dadId, 
        uint256 genes
    );

    struct Kitty {
        uint256 genes;
        uint64 birthTime;
        uint32 mumId;
        uint32 dadId;
        uint16 generation;
    }

    Kitty[] kitties;
    
    mapping (uint256 => address) public kittyIndexToOwner;
    
    mapping (address => uint256) ownershipTokenCount;
    
    mapping (address => uint256[]) ownerToCats;

    function balanceOf(address owner) external view returns (uint256 balance){
        return ownershipTokenCount[owner];
    }

    function totalSupply() public view returns (uint) {
        return kitties.length;
    }

    function ownerOf(uint256 _tokenId) external view returns (address)
    {
        return kittyIndexToOwner[_tokenId];
    }

    function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
       return ownerToCats[_owner];
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) private returns (uint256) {
        Kitty memory _kitty = Kitty({
            genes: _genes,
            birthTime: uint64(block.timestamp),
            mumId: uint32(_mumId),
            dadId: uint32(_dadId),
            generation: uint16(_generation)
        });
        
        kitties.push(_kitty);

        uint256 newKittenId = kitties.length - 1;

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

        _transfer(address(0), _owner, newKittenId);

        return newKittenId;

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        ownershipTokenCount[_to]++;

        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            ownershipTokenCount[_from]--;
        }

        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }

    function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
      return kittyIndexToOwner[_tokenId] == _claimant;
  }

}

It is more efficient for the function we want to improve but it makes other functions more gas costly, which makes the change itself not really worth it unless we make further changes.

1 Like
#153

1.Constant; pushing into an array is constant after first element, and assigning to mapping is as well.
2. Linear with length, as the for loop’s needs to go through all items
3. I implemented a linked list for the kitties. This means, that there is a mapping (uint => uint) kittyIndexToNext, for all kitties pointing at a next kitty in a chain. All addresses point have an ownerToHead mapping, pointing at the head of their kittychain. All chains end at kitty 0. Zero Kitty can’t be transfered, whoever created him has him FOREVER. This could be avoided if I implemented another mapping for each address pointing at the tail of each chain, but that would increase complexity and this seemed like a reasonable tradeoff.
Here are the gas cost results:
image
The cost of creating new cats and the making transfers is now 1.5-2x more expensive due to the added logic. However, the query time is now constant vs the total number of kitties, therefore the app can now scale.

Heres my code:

pragma solidity ^0.8.6;

contract Kittycontract_mod {

    string public constant name = "TestKitties";
    string public constant symbol = "TK";
    
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    event Birth(
        address owner, 
        uint256 kittenId, 
        uint256 mumId, 
        uint256 dadId, 
        uint256 genes
    );

    struct Kitty {
        uint256 genes;
        uint64 birthTime;
        uint32 mumId;
        uint32 dadId;
        uint16 generation;
    }

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => uint256) ownershipTokenCount;
    mapping (uint256 => uint256) kittyIndexToNext;
    mapping (uint256 => uint256) kittyIndexToPrev;
    mapping (address => uint256) ownerToHead;

    

    function balanceOf(address owner) external view returns (uint256 balance){
        return ownershipTokenCount[owner];
    }

    function totalSupply() public view returns (uint) {
        return kitties.length;
    }

    function ownerOf(uint256 _tokenId) external view returns (address)
    {
        return kittyIndexToOwner[_tokenId];
    }

    function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        /*uint[] memory result = new uint[](ownershipTokenCount[_owner]);
        uint counter = 0;
        for (uint i = 0; i < kitties.length; i++) {
            if (kittyIndexToOwner[i] == _owner) {
                result[counter] = i;
                counter++;
            }
        }
        */
        uint[] memory result = new uint[](ownershipTokenCount[_owner]);
        uint counter = 0;
        uint headkitty = ownerToHead[_owner];
        if (headkitty != 0) {
            result[counter] = headkitty;
            counter++;
        }
        uint next = kittyIndexToNext[headkitty];
        while (next != 0){
            result[counter] = next;
            next = kittyIndexToNext[next];
            counter++;
        }
        // If the caller has Kitty Zero, add it to his list.
        if (_owner == kittyIndexToOwner[0]){
            result[counter] = 0;
            counter++;
        }
        //this should be changed to the assert line, but I want to see the message
        require(ownershipTokenCount[_owner] == counter,"Something went very, very wrong with our chain!");
        //assert(ownershipTokenCount[_owner] == counter);
        return result;
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) private returns (uint256) {
        Kitty memory _kitty = Kitty({
            genes: _genes,
            birthTime: uint64(block.timestamp),
            mumId: uint32(_mumId),
            dadId: uint32(_dadId),
            generation: uint16(_generation)
        });
        
        kitties.push(_kitty);

        uint256 newKittenId = kitties.length - 1;
        // New kitties have 0 as next first (by default);
        //kittyIndexToNext[newKittenId] = 0;

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

        _transfer(address(0), _owner, newKittenId);

        return newKittenId;

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        ownershipTokenCount[_to]++;

        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            ownershipTokenCount[_from]--;
            require(_tokenId != 0,"Kitty Zero is Not for Sale! Don't ask!");
            // Patch up the previous chainblock 
            // If this wasn't the headkitty for the chain
            if(ownerToHead[_from] != _tokenId) {
                kittyIndexToNext[kittyIndexToPrev[_tokenId]] = kittyIndexToNext[_tokenId];
                kittyIndexToPrev[kittyIndexToNext[_tokenId]] = kittyIndexToPrev[_tokenId];
            }
            // If this was the headkitty for previous owner make next in line the head
            else {
                ownerToHead[_from] = kittyIndexToNext[_tokenId];
            }
        }
        //Add to the head of the new chainblock
        kittyIndexToPrev[ownerToHead[_to]] = _tokenId;
        //Make new head
        kittyIndexToNext[_tokenId] = ownerToHead[_to];
        ownerToHead[_to] = _tokenId;
        
        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }

    function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
      return kittyIndexToOwner[_tokenId] == _claimant;
  }

}
1 Like
#154

Assignment - ERC721

  1. time complexity of creating new cats is a constant.
  2. time complexity of the getAllCatsFor function is linear. as the number of cats are increasing, the looping through the increasing sized array kittyIndexToOwner takes more ressources to compute.

I deleted the mapping (address => uint256) ownershipTokenCount; in the solution below…looks like it s working…can anyone please confirm it s Ok ? :slight_smile:

pragma solidity ^0.8.0;

contract Kittycontract {

    string public constant name = "TestKitties";
    string public constant symbol = "TK";
    
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    event Birth(
        address owner, 
        uint256 kittenId, 
        uint256 mumId, 
        uint256 dadId, 
        uint256 genes
    );

    struct Kitty {
        uint256 genes;
        uint64 birthTime;
        uint32 mumId;
        uint32 dadId;
        uint16 generation;
    }

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => uint[]) ownershipTokens; 
    
    

    function balanceOf(address owner) external view returns (uint256 balance){
        return ownershipTokens[owner].length;
    }

    function totalSupply() public view returns (uint) {
        return kitties.length;
    }

    function ownerOf(uint256 _tokenId) external view returns (address)
    {
        return kittyIndexToOwner[_tokenId];
    }

    function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsIndexesFor(address _owner) external view returns (uint[] memory cats){
        return ownershipTokens[_owner];
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) private returns (uint256) {
        Kitty memory _kitty = Kitty({
            genes: _genes,
            birthTime: uint64(block.timestamp),
            mumId: uint32(_mumId),
            dadId: uint32(_dadId),
            generation: uint16(_generation)
        });
        
        kitties.push(_kitty);

        uint256 newKittenId = kitties.length - 1;

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

        _transfer(address(0), _owner, newKittenId);

        return newKittenId;

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        ownershipTokens[_to].push(_tokenId);

        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            _removeTokenIdFromOwner (_from,_tokenId); 
           
        }

        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }

    function _removeTokenIdFromOwner(address _from, uint256 _tokenId) internal {
        uint lastIndex_TokenId = ownershipTokens[_from][(ownershipTokens[_from].length-1)];
        for (uint i=0;i<ownershipTokens[_from].length;i++){
            if (ownershipTokens[_from][i] == _tokenId) {
                ownershipTokens[_from][i] = lastIndex_TokenId;
                ownershipTokens[_from].pop();
            }
        }
    }



    function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
      return kittyIndexToOwner[_tokenId] == _claimant;
  }

}
1 Like
#155
  1. Constant
  2. Linear
  3. Have a smaller lookup array of kitty ids to an address mapping(address => uint256[]) ownedCats;
    We can loop this much smaller array increasing efficiency for the function getAllCatsFor(), while slightly reducing the efficiency of a kitty transfer by needing to loop the ownedCats array for then _from address.
    In the end this solution is not good for the end user as the original getAllCatsFor() may be inefficient, but it has no gas cost associated as a view function. Adding more storage and storage changes to transfers will increase the cost to the end user for a gain not seen by them.
// "SPDX-License-Identifier: AGPL-3.0"
pragma solidity ^0.8.0;

contract Kittycontract {

    string public constant name = "TestKitties";
    string public constant symbol = "TK";
    
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    event Birth(
        address owner, 
        uint256 kittenId, 
        uint256 mumId, 
        uint256 dadId, 
        uint256 genes
    );

    struct Kitty {
        uint256 genes;
        uint64 birthTime;
        uint32 mumId;
        uint32 dadId;
        uint16 generation;
    }

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => uint256) ownershipTokenCount;
    mapping (address => uint256[]) ownedCats;

    function balanceOf(address owner) external view returns (uint256 balance){
        return ownershipTokenCount[owner];
    }

    function totalSupply() public view returns (uint) {
        return kitties.length;
    }

    function ownerOf(uint256 _tokenId) external view returns (address)
    {
        return kittyIndexToOwner[_tokenId];
    }

    function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        return ownedCats[_owner];
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) private returns (uint256) {
        Kitty memory _kitty = Kitty({
            genes: _genes,
            birthTime: uint64(block.timestamp),
            mumId: uint32(_mumId),
            dadId: uint32(_dadId),
            generation: uint16(_generation)
        });
        
        kitties.push(_kitty);

        uint256 newKittenId = kitties.length - 1;

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

        _transfer(address(0), _owner, newKittenId);

        return newKittenId;

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        ownershipTokenCount[_to]++;

        kittyIndexToOwner[_tokenId] = _to;

        _updateOwnedCats(_from, _to, _tokenId);

        if (_from != address(0)) {
            ownershipTokenCount[_from]--;
        }

        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }

    function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
      return kittyIndexToOwner[_tokenId] == _claimant;
    }

    function _updateOwnedCats(address _from, address _to, uint256 _tokenId) internal {
        // to remove an id we need to locate the position of the tokenid to be removed and copy over it with the last token id
        // then we pop the last item off the array
        for (uint i = 0; i < ownedCats[_from].length; i++) {
            uint lastPosition = ownedCats[_from].length -1;

            if (ownedCats[_from][i] == _tokenId) {
                ownedCats[_from][i] = ownedCats[_from][lastPosition]; // Copy the id in the last position to the position of the id to be removed
                ownedCats[_from].pop(); // Remove the last item in the array

                i = ownedCats[_from].length; // Stop looping
            }
        }
        
        ownedCats[_to].push(_tokenId);
    }
}
1 Like
#156

  • What is the time complexity of creating new cats? (constant or linear w nr of cats).
    Constant - just a simple push.

  • What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    Linear because of the for loop iterating through the kitties array.

  • How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.

For my solution, I changed the second mapping (ownershipTokenCount) to point from an array rather than a single uint. The benefit is that we can get rid of the for loop in the getAllCatsFor function, and simply return the array. However, in order to get it to work, I had to ADD a for loop to the transfer function, so not sure if this is actually better.
Anyways, here’s the code:

pragma solidity ^0.8.0;

contract Kittycontract {

    string public constant name = "TestKitties";
    string public constant symbol = "TK";
    
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    event Birth(
        address owner, 
        uint256 kittenId, 
        uint256 mumId, 
        uint256 dadId, 
        uint256 genes
    );

    struct Kitty {
        uint256 genes;
        uint64 birthTime;
        uint32 mumId;
        uint32 dadId;
        uint16 generation;
    }

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => uint256[]) tokensOwnedBy;

    

    function balanceOf(address owner) external view returns (uint256 balance){
        return tokensOwnedBy[owner].length;
    }

    function totalSupply() public view returns (uint) {
        return kitties.length;
    }

    function ownerOf(uint256 _tokenId) external view returns (address)
    {
        return kittyIndexToOwner[_tokenId];
    }

    function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        return tokensOwnedBy[_owner];
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) private returns (uint256) {
        Kitty memory _kitty = Kitty({
            genes: _genes,
            birthTime: uint64(block.timestamp),
            mumId: uint32(_mumId),
            dadId: uint32(_dadId),
            generation: uint16(_generation)
        });
        
        kitties.push(_kitty);

        uint256 newKittenId = kitties.length - 1;

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

        _transfer(address(0), _owner, newKittenId);

        return newKittenId;

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        tokensOwnedBy[_to].push(_tokenId);

        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            for(uint i = 0; i < tokensOwnedBy[_from].length; i++){
                if(tokensOwnedBy[_from][i] == _tokenId){
                    tokensOwnedBy[_from][i] = tokensOwnedBy[_from][tokensOwnedBy[_from].length - 1];
                    tokensOwnedBy[_from].pop();
                }
            }
            
        }

        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }

    function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
      return kittyIndexToOwner[_tokenId] == _claimant;
  }

}
1 Like
#157

  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
    The time complexity should be constant. Every cat needs the same execution time, no matter if there are already existing cats in the Array.

  2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    Its linear, because we have to loop through the hole array to get all cats. The longer the array gets the longer it takes to execute this function.

  3. How could the storage design be changed to make the getAllCats function constant? Implement your idea. Then discuss the benefits and drawbacks of your implementation and post everything in the forum.
    The Benefit of this solution is, that we can create a constant getAllCat function, because no matter how many cats we have the function will only perform one and the same operation: owendKittis[_owner]…

The drawback is, that we now have an other linear function.

pragma solidity ^0.8.0;

contract Kittycontract {

    string public constant name = "TestKitties";
    string public constant symbol = "TK";
    
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    event Birth(
        address owner, 
        uint256 kittenId, 
        uint256 mumId, 
        uint256 dadId, 
        uint256 genes
    );

    struct Kitty {
        uint256 genes;
        uint64 birthTime;
        uint32 mumId;
        uint32 dadId;
        uint16 generation;
    }

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => uint256) ownershipTokenCount;
    mapping (address => uint256[])OwendKittis;
    

    function balanceOf(address owner) external view returns (uint256 balance){
        return ownershipTokenCount[owner];
    }

    function totalSupply() public view returns (uint) {
        return kitties.length;
    }

    function ownerOf(uint256 _tokenId) external view returns (address)
    {
        return kittyIndexToOwner[_tokenId];
    }

    function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        //uint[] memory result = new uint[](ownershipTokenCount[_owner]);
        //uint counter = 0;
        //for (uint i = 0; i < kitties.length; i++) {
           // if (kittyIndexToOwner[i] == _owner) {
                //result[counter] = i;
               // counter++;
           // }
        //}
        //return result;
        cats=OwendKittis[_owner];
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) private returns (uint256) {
        Kitty memory _kitty = Kitty({
            genes: _genes,
            birthTime: uint64(block.timestamp),
            mumId: uint32(_mumId),
            dadId: uint32(_dadId),
            generation: uint16(_generation)
        });
        
        kitties.push(_kitty);

        uint256 newKittenId = kitties.length - 1;

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

        _transfer(address(0), _owner, newKittenId);

        return newKittenId;

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        //ownershipTokenCount[_to]++;
        OwendKittis[_to].push(_tokenId); //new 

        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            ownershipTokenCount[_from]--;
        }

        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }
    
    function removeCats(address _owner, uint256 _tokenId)internal {
        for (uint i =0; i < OwendKittis[_owner].length; i++){
           if (OwendKittis[_owner][i]==_tokenId){
               OwendKittis[_owner][i]=OwendKittis[_owner][OwendKittis[_owner].length -1];
               OwendKittis[_owner].pop();
           } 
        }
    }

    function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
      return kittyIndexToOwner[_tokenId] == _claimant;
  }
}
1 Like
#158

  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).

    Constant

  2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).

    Linear

  3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.

    Store all the Kitties` Ids on an array instead of only keeping the count variable.
    That will change the time complexity of getAllCats to constant time.

    Advantages:
    a) This should improve the experience of the user when checking all his Kitties.

    Drawbacks:
    a) Will need to keep one array for each owner with the Kitties Ids. This is linear to the size of the Kitties Ids.
    b) Transferring Kitties will be linear to the list of Kitties owned by the owner, which isn’t totally bad.
    c) Gas increased since the improvement was to a view function which doesn’t cost anything to users but the transfer function had a considerable gas increase

Old implementation:
Transfer cost: 57366 gas
getAllCatsFor costs:44949 gas (Cost only applies when called by a contract)

New implementation
Transfer cost: 72110 gas
getAllCatsFor costs: 32065 gas (Cost only applies when called by a contract)

pragma solidity ^0.8.0;

contract Kittycontract {

    string public constant name = "TestKitties";
    string public constant symbol = "TK";
    
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    event Birth(
        address owner, 
        uint256 kittenId, 
        uint256 mumId, 
        uint256 dadId, 
        uint256 genes
    );

    struct Kitty {
        uint256 genes;
        uint64 birthTime;
        uint32 mumId;
        uint32 dadId;
        uint16 generation;
    }

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => uint256[]) ownershipTokenCount;

    

    function balanceOf(address owner) external view returns (uint256 balance){
        return ownershipTokenCount[owner].length;
    }

    function totalSupply() public view returns (uint) {
        return kitties.length;
    }

    function ownerOf(uint256 _tokenId) external view returns (address)
    {
        return kittyIndexToOwner[_tokenId];
    }

    function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint256[] memory){
        return ownershipTokenCount[_owner];
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) private returns (uint256) {
        Kitty memory _kitty = Kitty({
            genes: _genes,
            birthTime: uint64(block.timestamp),
            mumId: uint32(_mumId),
            dadId: uint32(_dadId),
            generation: uint16(_generation)
        });
        
        kitties.push(_kitty);

        uint256 newKittenId = kitties.length - 1;

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

        _transfer(address(0), _owner, newKittenId);

        return newKittenId;

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        ownershipTokenCount[_to].push(_tokenId);

        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            for(uint i = 0; i < ownershipTokenCount[_from].length; i++) {
                if(ownershipTokenCount[_from][i] == _tokenId) {
                    delete ownershipTokenCount[_from][i];
                    ownershipTokenCount[_from][i] = ownershipTokenCount[_from][ownershipTokenCount[_from].length - 1];
                    break;
                }
            }
            ownershipTokenCount[_from].pop();
        }

        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }

    function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
      return kittyIndexToOwner[_tokenId] == _claimant;
  }

}
1 Like
#159
  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).

A. Constant

  1. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).

A. Linear

  1. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.

A. We can change value of ownershipTokenCount mapping to array of unassigned integers, so that way we can just call array of kitties without looping through all kitties array by using owner address.

pragma solidity ^0.8.0;

contract Kittycontract {

    string public constant name = "TestKitties";
    string public constant symbol = "TK";
    
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    event Birth(
        address owner, 
        uint256 kittenId, 
        uint256 mumId, 
        uint256 dadId, 
        uint256 genes
    );

    struct Kitty {
        uint256 genes;
        uint64 birthTime;
        uint32 mumId;
        uint32 dadId;
        uint16 generation;
    }
    
    struct Owner {
        address ownerAddress;
        uint index;
    }

    Kitty[] kitties;

    mapping (uint256 => Owner) public kittyIndexToOwner;
    mapping (address => uint[]) ownershipTokenCount;
    

    function balanceOf(address owner) external view returns (uint balance){
        return ownershipTokenCount[owner].length;
    }

    function totalSupply() public view returns (uint) {
        return kitties.length;
    }

    function ownerOf(uint256 _tokenId) external view returns (address)
    {
        return kittyIndexToOwner[_tokenId].ownerAddress;
    }

    function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint cats){
        // uint[] memory result = new uint[](ownershipTokenCount[_owner]);
        // uint counter = 0;
        // for (uint i = 0; i < kitties.length; i++) {
        //     if (kittyIndexToOwner[i] == _owner) {
        //         result[counter] = i;
        //         counter++;
        //     }
        // }
        return ownershipTokenCount[_owner].length;
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) private returns (uint256) {
        Kitty memory _kitty = Kitty({
            genes: _genes,
            birthTime: uint64(block.timestamp),
            mumId: uint32(_mumId),
            dadId: uint32(_dadId),
            generation: uint16(_generation)
        });
        
        kitties.push(_kitty);

        uint256 newKittenId = kitties.length - 1;

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

        _transfer(address(0), _owner, newKittenId);

        return newKittenId;

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        if (_from != address(0)) {
            ownershipTokenCount[_from][kittyIndexToOwner[_tokenId].index] = ownershipTokenCount[_from][ownershipTokenCount[_from].length - 1];
            ownershipTokenCount[_from].pop();
        }
        
        ownershipTokenCount[_to].push(_tokenId);
        kittyIndexToOwner[_tokenId].ownerAddress = _to;
        kittyIndexToOwner[_tokenId].index = ownershipTokenCount[_to].length - 1;

        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }

    function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
      return kittyIndexToOwner[_tokenId].ownerAddress == _claimant;
  }

}
1 Like
#160

  1. Constant - every cat should require the same execution time.

  2. Linear - we loop through all cats in a given owner’s array. The longer the array, the longer it will take to loop through and retrieve the result.

  3. We can include an array for owned kittens for each address (owner):

pragma solidity ^0.8.0;

contract Kittycontract {

    string public constant name = "TestKitties";
    string public constant symbol = "TK";
    
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    event Birth(
        address owner, 
        uint256 kittenId, 
        uint256 mumId, 
        uint256 dadId, 
        uint256 genes
    );

    struct Kitty {
        uint256 genes;
        uint64 birthTime;
        uint32 mumId;
        uint32 dadId;
        uint16 generation;
    }

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => uint256) ownershipTokenCount;
    mapping (address => uint256[]) ownedKitties;

    

    function balanceOf(address owner) external view returns (uint256 balance){
        return ownershipTokenCount[owner];
    }

    function totalSupply() public view returns (uint) {
        return kitties.length;
    }

    function ownerOf(uint256 _tokenId) external view returns (address)
    {
        return kittyIndexToOwner[_tokenId];
    }

    function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        // uint[] memory result = new uint[](ownershipTokenCount[_owner]);
        // uint counter = 0;
        // for (uint i = 0; i < kitties.length; i++) {
        //     if (kittyIndexToOwner[i] == _owner) {
        //         result[counter] = i;
        //         counter++;
        //     }
        // }
        // return result;
        
        return ownedKitties(_owner);
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) private returns (uint256) {
        Kitty memory _kitty = Kitty({
            genes: _genes,
            birthTime: uint64(block.timestamp),
            mumId: uint32(_mumId),
            dadId: uint32(_dadId),
            generation: uint16(_generation)
        });
        
        kitties.push(_kitty);

        uint256 newKittenId = kitties.length - 1;

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

        _transfer(address(0), _owner, newKittenId);

        return newKittenId;

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        ownershipTokenCount[_to]++;

        kittyIndexToOwner[_tokenId] = _to;
        ownedKitties[_to].push(_tokenId);

        if (_from != address(0)) {
            ownershipTokenCount[_from]--;
            _removeOwnedKitty(_from, _tokenId);
        }

        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }

    function _removeOwnedKitty(address _from, uint256 _tokenId) internal {
        uint256 toDelete = ownedKitties[_from][ownedKitties[_from].length-1];
        
        for(uint i = 0, i < ownedKitties[_from].length, i++) {
            if (ownedKitties[_from][i] == _tokenId) {
                ownedKitties[_from][i] = ownedKitties[_from][toDelete];
                ownedKitties[from].pop();
            }
        }
    }

    function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
      return kittyIndexToOwner[_tokenId] == _claimant;
  }

}

The solution makes the ‘getAllCatsFor’ function much simpler but it adds a lot of complexity to the transfer function and new removal function. Creating a new storage variable means more costs for regular transactions, whereas the original contract had a ‘view’ function meaning there aren’t any associated gas fees.

1 Like
#161

1. What is the time complexity of creating new cats? (constant or linear w nr of cats).

  • Constant, no need to loop through an array.

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).

  • Linear, as it’s currently looping through all cats and has scaling issues.

3. How could the storage design be changed to make the getAllCats function constant? Implement your idea. Then discuss the benefits and drawbacks of your implementation and post everything in the forum.

  • getAllCatsFor function requires to be a constant which brings a benefit for fetching cats, however, the disadvantage is the transfer function will be linear instead of constant which ends up costing more gas.
contract Kittycontract {

   string public constant name = "TestKitties";
   string public constant symbol = "TK";
   
   event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

   event Birth(
       address owner, 
       uint256 kittenId, 
       uint256 mumId, 
       uint256 dadId, 
       uint256 genes
   );

   struct Kitty {
       uint256 genes;
       uint64 birthTime;
       uint32 mumId;
       uint32 dadId;
       uint16 generation;
   }

   Kitty[] kitties;

   mapping (uint256 => address) public kittyIndexToOwner;
   mapping (address => uint256 []) ownedCats;

   

   function balanceOf(address _owner) external view returns (uint256){
       return ownedCats [_owner].length;
   }

   function totalSupply() public view returns (uint) {
       return kitties.length;
   }

   function ownerOf(uint256 _tokenId) external view returns (address)
   {
       return kittyIndexToOwner[_tokenId];
   }

   function transfer(address _to,uint256 _tokenId) external
   {
       require(_to != address(0));
       require(_to != address(this));
       require(_owns(msg.sender, _tokenId));

       _transfer(msg.sender, _to, _tokenId);
   }
   
   function getAllCatsFor(address _owner) external view returns (uint[] memory cats){

       return ownedCats [_owner];
   }
   
   function createKittyGen0(uint256 _genes) public returns (uint256) {
       return _createKitty(0, 0, 0, _genes, msg.sender);
   }

   function _createKitty(
       uint256 _mumId,
       uint256 _dadId,
       uint256 _generation,
       uint256 _genes,
       address _owner
   ) private returns (uint256) {
       Kitty memory _kitty = Kitty({
           genes: _genes,
           birthTime: uint64(block.timestamp),
           mumId: uint32(_mumId),
           dadId: uint32(_dadId),
           generation: uint16(_generation)
       });
       
       kitties.push(_kitty);

       uint256 newKittenId = kitties.length - 1;

       emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

       _transfer(address(0), _owner, newKittenId);

       return newKittenId;

   }

   function _transfer(address _from, address _to, uint256 _tokenId) internal {
       
       kittyIndexToOwner[_tokenId] = _to;

       if (_from != address(0)) {
          // Deletes the cat from the owner
          _deleteKittyOwnership (_from, _tokenId);
       }
       
       // Add the token to the new owner
       ownedCats [_to].push (_tokenId);

       // Emit the transfer event.
       emit Transfer(_from, _to, _tokenId);
   }

   function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
     return kittyIndexToOwner[_tokenId] == _claimant;
 }
 
 function _deleteKittyOwnership (address _owner, uint _tokenId) internal {
     for (uint i = 0; i < ownedCats [_owner].length; i ++) {
         
         if (ownedCats [_owner] [i] == _tokenId) {
             ownedCats [_owner] [i] = ownedCats [_owner] [ownedCats [_owner].length-1];
             ownedCats [_owner].pop ();
             return;
         }
     }
 }

}
1 Like
#162
  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
  • Constant
  1. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
  • Linear
  1. How could the storage design be changed to make the getAllCats function constant? Implement your idea. Then discuss the benefits and drawbacks of your implementation and post everything in the forum.
  • By creating a mapping between an address and a corresponding uint array containing the index of each owned Kitty.
...

// Owner-Kitties Mapping
mapping (address => uint[]) public OwnerToKitty;

...

function getAllCatsForOwnerMapping(address _owner) external view returns (uint[] memory cats){
    return OwnerToKitty[_owner];
}

...

function _transfer(address _from, address _to, uint256 _tokenId) internal {
    ownershipTokenCount[_to]++;

    kittyIndexToOwner[_tokenId] = _to;
    
    // Update Owner-Kitties Mapping
    OwnerToKitty[_to].push(_tokenId);
    
...
  • With this mapping, you don’t have to loop through the array of Kitty structs
  • Drawbacks will be:
    • you need to add logic in modifying an array if there will be changes (i.e. an owner transferring a Kitty to someone else)
    • additional storage consideration especially as more owners get to have a Kitty
1 Like
#163

  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).

    Constant

  2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).

    Linear

  3. Improvement using a KittenListItem and creating an array of them (a collection of cats is called a clowder apparently) - then removing kittens from the list when transferred.

pragma solidity ^0.8.0;
pragma abicoder v2;

contract Kittycontract {

    string public constant name = "TestKitties";
    string public constant symbol = "TK";
    
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    event Birth(
        address owner, 
        uint256 kittenId, 
        uint256 mumId, 
        uint256 dadId, 
        uint256 genes
    );

    struct Kitty {
        uint256 genes;
        uint64 birthTime;
        uint32 mumId;
        uint32 dadId;
        uint16 generation;
    }
    
    struct KittyListItem {
        uint kittenId;
        uint listPointer;
    }
    
    mapping (address => KittyListItem[]) clowder;

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => uint256) ownershipTokenCount;


    function balanceOf(address owner) external view returns (uint256 balance){
        return ownershipTokenCount[owner];
    }

    function totalSupply() public view returns (uint) {
        return kitties.length;
    }

    function ownerOf(uint256 _tokenId) external view returns (address)
    {
        return kittyIndexToOwner[_tokenId];
    }

    function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        uint[] memory result = new uint[](ownershipTokenCount[_owner]);
        uint counter = 0;
        for (uint i = 0; i < kitties.length; i++) {
            if (kittyIndexToOwner[i] == _owner) {
                result[counter] = i;
                counter++;
            }
        }
        return result;
    }
    
    function getClowderFor(address _owner) external view returns (uint[] memory cats){
        KittyListItem[] memory _clowder = clowder[_owner];
        uint[] memory result = new uint[](ownershipTokenCount[_owner]);
        for(uint i = 0; i < _clowder.length; i++){
            KittyListItem memory kittyListItem = _clowder[i];
            result[i] = kittyListItem.kittenId;
        }
        
        return result;
    }
    
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) private returns (uint256) {
        Kitty memory _kitty = Kitty({
            genes: _genes,
            birthTime: uint64(block.timestamp),
            mumId: uint32(_mumId),
            dadId: uint32(_dadId),
            generation: uint16(_generation)
        });
        
        kitties.push(_kitty);

        uint256 newKittenId = kitties.length - 1;

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

        _transfer(address(0), _owner, newKittenId);

        return newKittenId;

    }
    
    function addKittenToClowder(address _owner, uint kittenId) public{
        KittyListItem[] storage currentClowder = clowder[_owner];
        
        KittyListItem memory listItem = KittyListItem({
            kittenId: kittenId,
            listPointer: currentClowder.length
        });
        
        currentClowder.push(listItem);

    }
    
    function removeKittenFromClowder(address _owner, uint kittenId) public {
        
        KittyListItem[] storage _clowder = clowder[_owner];
        bool found = false;
        uint indexOfKittenToRemove = 0;
        for(uint i = 0; i < _clowder.length; i++){
            KittyListItem memory kittyListItem = _clowder[i];
            if (kittyListItem.kittenId == kittenId){
                indexOfKittenToRemove = i;
                found=true;
                break;
            }
        }
        
        if(found){
            _clowder[indexOfKittenToRemove] = _clowder[_clowder.length-1];
            _clowder.pop();
        }

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        ownershipTokenCount[_to]++;

        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            ownershipTokenCount[_from]--;
        }
        
        removeKittenFromClowder(_from, _tokenId);
        addKittenToClowder(_to, _tokenId);
        
        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }

    function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
      return kittyIndexToOwner[_tokenId] == _claimant;
  }

}
1 Like
#164
  1. It is constant; adding a cat into the array isn’t timely whatsoever, and in comparison to a call to sort through an array, it would be much smaller (depending on the size of the array.
  2. It is linear; the looping function will go through each cat within the array until call is complete. The larger the array, the more time and cost associated with the call.
  3. The easiest way is to set getAllCats as a mapping that has the address point to an integer associated to the address; the upside is the constant time in creation but 2 calls are made in the create function so it just displaces gather cost in a way.
1 Like
#165

  1. Well the new cats are stored in an array. With storage assignment adding first few elements to the array I noticed the gas consumption was going up. But then it went down and stayed constant within some threshold. So I think the time complexity is constant.

  2. To get all the cat’s you have to loop though all the kitties array. So I guess the time complexity is at least linear.

  3. If I add this:

mapping (address => Kitty[]) public ownerToKitties;

Then in _createKitty()

    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) private returns (uint256) {
        Kitty memory _kitty = Kitty({
            genes: _genes,
            birthTime: uint64(block.timestamp),
            mumId: uint32(_mumId),
            dadId: uint32(_dadId),
            generation: uint16(_generation)
        });
        
        ownerToKitties[_owner].push(_kitty);

        uint256 newKittenId = ownerToKitties[_owner].length - 1;

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

        _transfer(address(0), _owner, newKittenId);

        return newKittenId;

    }

And now I can getAllCatsFor() instantly

    function getAllCatsFor(address _owner) external view returns (Kitty[] memory cats){
        cats = ownerToKitties[_owner];
    }

But instead of returning uint[] it returns Kitty[]. So…

1 Like