Assignment - ERC721

Ethereum Smart Contract Programming 201
#206

  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
    The time complexity of creating new cats is constant. There is no looping involved.

  2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    The time complexity for getAllCatsFor is linear with the number of cats already in existence, because it requires looping through the kitties array every time it is run. The larger the array, the longer the process will take.

  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.
    I used a mapping from owner addresses to a uint array containing the tokenIds of kittens they own. This change made the getAllCatsFor function time complexity no longer dependent on the total number of cats in existence. However, to implement this solution, I had to make changes in the transfer function which required introducing a loop search through the array of cats owned by the transfer from address. Therefore, the larger the number of cats an individual owner has, the more costly it will be for that owner to transfer a cat to someone else. See code below.

Updated KittyContract1.sol 
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 of addresses to arrays containing owned kitties
    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));

        _transferV2(msg.sender, _to, _tokenId);
    }
    
   
    function getAllCatsForV2(address _owner) external view returns (uint[] memory cats){
       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);

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

        return newKittenId;

    }

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

        kittyIndexToOwner[_tokenId] = _to;

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

            //Remove _tokenId from ownedKitties[_from] array.
            uint lastTokenIdIndex = ownedKitties[_from].length - 1;
            uint transTokenIdIndex;
            //Find index of token to be removed.
            for (uint i = 0; i < ownedKitties[_from].length; i++) {
                if (_tokenId == ownedKitties[_from][i]) {
                    transTokenIdIndex = i;
                }
            }
            //Replace _tokenId to be removed with last tokenId then delete last index
            ownedKitties[_from][transTokenIdIndex] = ownedKitties[_from][lastTokenIdIndex];
            ownedKitties[_from].pop();

        }
        
        //update array of owned kitties in ownedKitties mapping.
        ownedKitties[_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;
  }

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

The time complexity of creating a new cat is constant. It doesn’t change based on the input or the number of cats.

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

The time complexity of getAllCatsFor is linear. The more cats there are in total, the longer it will take.

  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.

We could improve getAllCatsFor by adding a new mapping variable that stores all tokens for an address in an array. That would change the time complexity to constant. However, because we’re now dealing with an array of owned tokens, transferring a cat would have increased complexity because it needs to iterate through that array of owned tokens in order to find the one to delete. Even though we still have to iterate through an array at some point, I think it’s a good tradeoff because we’re working with a smaller dataset – array of owned tokens rather than the entire array of all tokens. Adding the break statement in there also saves time once the token is found. It’s also worth noting that we don’t need to iterate through the array when creating a cat since it’s transferred from the 0 address.

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[]) public ownerToKittyIndexes;

    function balanceOf(address owner) external view returns (uint256 balance){
        return ownerToKittyIndexes[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 ownerToKittyIndexes[_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 {
        require(_owns(_from, _tokenId), "From address doesn't own that token");
        kittyIndexToOwner[_tokenId] = _to;
        ownerToKittyIndexes[_to].push(_tokenId);
        if (_from != address(0)) {
            _deleteKittyFromOwner(_from, _tokenId);
        }

        emit Transfer(_from, _to, _tokenId);
    }

    /**
     * Delete the token from the array of owned tokens for an address.
     * Uses the technique to pop the last item off the array and move it to the index we want to delete.
     */
    function _deleteKittyFromOwner(address _owner, uint256 _tokenId) private {
        bool kittyFound = false;
        uint256 indexToReplace;
        for(uint256 i = 0; i < ownerToKittyIndexes[_owner].length; i++) {
            if (ownerToKittyIndexes[_owner][i] == _tokenId) {
                indexToReplace = i;
                kittyFound = true;
                break;
            }
        }
        // Since indexToReplace starts at 0, we need to make sure we actually found the token in the array
        require(kittyFound == true, "Token not found for owner");

        uint256 indexToMove = ownerToKittyIndexes[_owner].length - 1;
        ownerToKittyIndexes[_owner][indexToReplace] = ownerToKittyIndexes[_owner][indexToMove];
        ownerToKittyIndexes[_owner].pop();
    }

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

}
1 Like
#208

  1. constant complexity w. r. t. cat number

  2. linear complexity w. r. t. cat number

  3. (1) mapping the owner address to the owner’s kitty collection
    (2) record the collection index of owner’s kitty for efficient delete

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[]) ownershipCollection;
    mapping (uint256 => uint256) kittyCollectionIndex;


    function balanceOf(address owner) external view returns (uint256 balance){
        return ownershipCollection[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){
        uint[] memory result = ownershipCollection[_owner];
        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 {
        // _from address
        if (_from != address(0)) {
            uint kittyIndex = kittyCollectionIndex[_tokenId];
            uint endFromIndex = ownershipCollection[_from].length - 1;
            ownershipCollection[_from][kittyIndex] = ownershipCollection[_from][endFromIndex];
            ownershipCollection[_from].pop();
        }

        // _to address
        ownershipCollection[_to].push(_tokenId);
        uint endToIndex = ownershipCollection[_to].length - 1;
        kittyCollectionIndex[_tokenId] = endToIndex;

        // index to owner
        kittyIndexToOwner[_tokenId] = _to;
        
        // 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
#209

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

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

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.
Benefits: The time complexity of this solution is constant.
Drawbacks: The implementation is more complex and an additional mapping would need to be stored in the storage.

pragma solidity ^0.8.0;
import "./SafeMath.sol";

contract Kittycontract {

    using SafeMath for uint;

    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[]) ownershipOfTokens;

    mapping (uint256 => uint256) kittyIndexToOwnedIndex;

    function balanceOf(address owner) external view returns (uint256 balance){
        return ownershipOfTokens[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 ownershipOfTokens[_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.sub(1);

        ownershipOfTokens[address(0)].push(newKittenId);
        kittyIndexToOwnedIndex[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 {
        ownershipOfTokens[_to].push(_tokenId);

        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            uint rowToDelete = ownershipOfTokens[_from][kittyIndexToOwnedIndex[_tokenId]];
            uint keyToMove = ownershipOfTokens[_from].length.sub(1);
            uint tokenToMove = ownershipOfTokens[_from][keyToMove];

            ownershipOfTokens[_from][rowToDelete] = tokenToMove;
            ownershipOfTokens[_from].pop();

            kittyIndexToOwnedIndex[tokenToMove] = rowToDelete;
        }

        kittyIndexToOwnedIndex[_tokenId] = ownershipOfTokens[_to].length.sub(1);

        emit Transfer(_from, _to, _tokenId);
    }

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

}
1 Like
#210

so this is my code, but in the RemoveOwnership function i get an unreachable code error in the incremenet part of the for loop. Does anyone know why this happens?

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;
    }

    uint[] ListofCats;
    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;

        ownerOfCats[msg.sender].push(newKittenId);

        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)) {
           RemoveOwnership(_from, _tokenId);
            ownerOfCats[_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 RemoveOwnership(address _from, uint indexID) public returns(bool success) {
    //creates a local variable that represents the index on the array
    uint Id = indexID - 1;
    //loop through the cats _from address owns
    for( uint i = 0; i < ownerOfCats[_from].length; i++ ){
        //check if the address has a certain cat
        if(ownerOfCats[_from][i] == Id){
        // copy the data of the index to be deleted to the data of the last index of the array.
         ownerOfCats[_from][i] = ownerOfCats[_from][ownerOfCats[_from].length-1];
        //remove the last index from the array
         ownerOfCats[_from].pop();
        }

        return true;
    }

  }

}
1 Like
#211

1.Its always the same (constant)becuse its the same deterministic process over and over again.
2. Its not constant at all because we use a function that runs through an array till it finds the element we want so it will depend on the position of that alement in the array.
3.To make that function cheaper in terms of gas, and with a constant time complexity we should:

// this mapping only gives information about how many kitties someone, has, not which ones
 //mapping (address => uint256) ownershipTokenCount;
mapping(address =>uint256[]) ownerTokens;

//this option is much cheaper
function getAllCatsFor(address _owner) public view returns (uint[]){
    return ownerTokens[_owner];
        }
1 Like
#212

  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
    The time complexity of creating a cat is constant time, O (1), because when executing the createKittyGen0 function, you create the cats 1 by 1, or 1 at a time in this implementation.

  2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    To execute the getAllCatsFor function, there is a loop through an array. The parsing of this array makes the function operate from linear time complexity, 0 (n), therefore the processing required for the function grows linearly as the size of the array of cats grows.

  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.
    We could implement a version of the getAllCats function that uses a mapping rather than array. This is important because we found in the prior assignment that using mappings instead of arrays produces more efficient storage. Also, we notice that this type of implementation reduces the time complexity from linear to constant, reinforcing its’ improved efficiency.

    function getCatsMap(address _owner) external view returns (uint[] memory cats){
        return allKitties[_owner];
    }
1 Like
#213

Hi there, see below my answers:

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

It should be constant since we are just “pushing” a new entry, i.e. adding a new entry at the end of the array.

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

It will be linear, i.e it will take more time with the nr of cats increasing. This is because in its current implementation, we have to loop through the whole array of cats of ALL owners to find the cats belonging to a SPECIFIC owner

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

  • First create a new mapping mapping (address => uint256[]) ownedCats; which point to an ARRAY of cats owned by an address

  • Use this new mapping in the getAllCats function catsOfOwner = ownedCats[_owner];

1 Like
#214
  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.

Create a new mapping of owners => cats[]

mapping (address => uint256[]) ownersCats;

In function getAllCatsFor can just return ownersCats[_owner];

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

When transferring cats, the ownerCats mapping needs to be updated.

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

Constant, because it uses just array push method and direct assignments.

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

Linear because of the looping through the kitties array.

  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.

The idea is in creation the mapping:

mapping (address => uint[]) ownershipKitties;

With it we will get constant time complexity for getAllCatsFor but in same time we will increase the transfer time complexity because of removing cat increased complexity to O(n).

2 Likes
#216
  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
1st Answer:

The time is constant because we do not have to loop over the array length of kitties, simply push the new one onto the end of the array.

The transfer function which goes into the _transfer function simply adds to the (kittyIndexToOwner, ownershipTokenCount) mappings which does not add time complexity.

The gas costs required for each kitty creation increase linearly:

1st time creation: 139231 gas
2nd: 105031 gas
3rd: 105031 gas
4th: 105031 gas

The creation seems to initially go down but actually levels out and stays at a constant rate beyond the first time an account creates a kitty.

The very first kitty creation costs the most for other addresses but less than the very first kitty created:

1st: 122131 gas
2nd: 105031 gas
3rd: 105031 gas
4th: 105031 gas

This all depends on the _genes being equivalent length as in my testing using 123456… at 9 and 0 the cost ever so slightly increased:
105043 gas

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

The time complexity of the getAllCatsFor function is linearly increasing. As the kitties array increases the function has to do more loops to then check with the kittyIndexToOwner mapping.

The gas costs also increase linearly. This price varies by owner and how many cats they own.

If they own more not only do they get the extra cost everyone does with a larger array of cats, but also more calls inside of the for loop and if checking kitty ownership.

for (uint i = 0; i < kitties.length; i++) {
    if (kittyIndexToOwner[i] == _owner) {
        result[counter] = i;
        counter++;
    }
}

This results in having to increase the counter and more kitties in the returned array thus more operations for more owned kitties.

  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.
3rd Answer:

With a new mapping:
mapping (address => uint[]) kittiesForOwner;
This mapping allows for the time complexity of a lookup for cats owned by an owner to be constant.

The function getAllCatsFor can be changed although I make a new one here:

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

We no longer have to loop over the entire length of the kitties array and do an individual check on each kittyIndex on the kittyIndexToOwner mapping.

The gas cost does increase linearly, however it less than the previous implementation of the function which is a very important benefit.

It also does not increase if more cats are created by others, only by the amount of cats owned by the specific address.

This does not allow the deletion of the kittyIndexToOwner mapping as it is required to lookup which particular kitty is owned by whom.

There is another huge downside, the _transfer function must be reworked with more logic to remove ownership from the previous owner, since with this new method kitties are in an addresses mapping value array.
mapping (address => uint[]) kittiesForOwner;
Function rework:

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

    kittyIndexToOwner[_tokenId] = _to;

    // Adding newly transfered cat to the new owner's mapping
    kittiesForOwner[_to].push(_tokenId);

    // Huge downside of extra code here which is used to remove ownership
    // from previous kitty owner by moving the indexed cat to last in
    // the array then popped off.
    for(uint i = 0; i < kittiesForOwner[_from].length; i++) {
        if(kittiesForOwner[_from][i] == _tokenId) {
            kittiesForOwner[_from][_tokenId] = kittiesForOwner[_from].length - 1;
            kittiesForOwner[_from].pop();
            break;
        }
    }

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

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

I left the functionality of the kittyIndexToOwner and just added my required logic below comments. This method increases the gas cost of a kitty transfer.

#217

  1. Constant

  2. Linear

  3. Add another mapping (address => [Kitty]) ownerToKitties;
    This is what we can use in getAllCatsFor instead.
    Benefits: Constant time, simpler to read
    Drawbacks: we need to add a kitty to it everytime we create a kitty and modify it everytime we transfer the ownership, therefore more gas executed

1 Like
#218

Hi, here is my attempt to this erc-721 assignment

  1. the time complexity for creating a new cats is constant.
  2. the time complexity for getting all cats is linear w = nr because we have to loop trough the Kitties array and match cat ids
  3. as solution i had introduced a new struct called Owned kitties which contains an array and a mapping from cat ids to their index in the array within the struct
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 OwnedKitties{
      uint[] my_kitties;
      mapping(uint => uint) kittyToIndex; 
    }
    Kitty[] kitties;

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

    

    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 ownerToKitties[_owner].my_kitties;
    }
    
    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 storage _owned = ownerToKitties[_to];
          _owned.my_kitties.push(_tokenId);
          _owned.kittyToIndex[_tokenId] =  _owned.my_kitties.length -1;
          if(_from != address(0) ){
               ownershipTokenCount[_from] --;
                _removeFromOwned(_tokenId,_from);
          }
        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }

       function _removeFromOwned(uint _tokenId,address _owner) private returns(uint){
          OwnedKitties storage _owned = ownerToKitties[_owner];
          uint index_to_delete = _owned.kittyToIndex[_tokenId];
          uint kitty_to_delete_id = _owned.my_kitties[index_to_delete];
          uint last_kitty = _owned.my_kitties[_owned.my_kitties.length-1];
          _owned.my_kitties[index_to_delete] = last_kitty;
          _owned.kittyToIndex[last_kitty] = index_to_delete;
          _owned.my_kitties[_owned.my_kitties.length-1] = kitty_to_delete_id;
          _owned.my_kitties.pop();
           delete _owned.kittyToIndex[_tokenId];
          return _tokenId;
     }

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

}

Pros :
constant time complexity for getallcats methods
Cons:

  • More storage variable and writting leading to more gas consumption
  • have to re implement transfer method to update kitty pointer in each arrays
1 Like
#219
1

creating new cats is constant we push the kitty to array we do not need to iterate.

2

getAllCatsFor is linear w nr of cats because we need to iterate the array to get all the ids.

3

We could do mapping address => uint[], but now I have linear time complexity in transfer function so I think this is worse then before but now I get instant array of cats owned by someone we should think what is more important I think transaction so I would go back to original 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[]) 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){
        cats = 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]++;

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

        if (_from != address(0)) {
            ownershipTokenCount[_from]--;
            for(uint i=0; i<ownedKitties[_from].length; i++){
                if(ownedKitties[_from][i] == _tokenId){
                    ownedKitties[_from][i] = ownedKitties[_from][ownedKitties[_from].length-1];  
                    ownedKitties[_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
#220
  1. creating a new cat is constant. it has a very fast execution.

2.getAllCats is linear as it needs to loop through an array in order to return its result.

3.you can use a mapping(address => uint) ownedCats; and then return it in the getAllCats function.

Something that should be considered is that the functions purpose is to view the data rather than writing to storage. This is a free function so in terms of gas reduction its not worth it here. If you edit the getallcats function with a mapping it will cause other functions to require loops.

1 Like
#221

Hey guys, my solution to the assignment is the following:

  1. Constant, since it does not depend on any loop operation on the list of already existing kittens. All it takes is to push a new element to the array (O(1)), and transfer that Kitten to the respective user, which implies updating the ownershipToken count and kittyIndexToOwner mappings, which are also both O(1) operations.

  2. Linear, since the current implementation for this function relies on iterating through the existing Kitten Ids and verifying which belong to the given user.

  3. One solution for the time complexity optimization for the getAllCatsFor function is to replace the ownershipTokenCount storage pattern with another of the type (address => uint[]) ownedTokens. The benefits for this would be a time complexity of O(1) for the getAllCatsFor function. However, this solution does contain some drawbacks, namely the increase in gas consumption for storage and also the increase in complexity (and consequently gas consumption) for all functions that imply an update on ownership listing, mainly on transfer function, since updating this mapping requires looping the mapped list to remove the index of the transferred token.
    Here’s the updated code with the proposed changes:

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[]) ownedTokens;

    

    function balanceOf(address owner) external view returns (uint256 balance){
        return ownedTokens[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 ownedTokens[_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 {
        ownedTokens[_to].push(_tokenId);

        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            _removeKittenFromOwner(_from, _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 _removeKittenFromOwner(address _owner, uint256 _tokenId) internal {
      for (uint i = 0; i<=ownedTokens[_owner].length -1; i++) {
          if(ownedTokens[_owner][i] == _tokenId){
              ownedTokens[_owner][i] = ownedTokens[_owner][ownedTokens[_owner].length -1];
              ownedTokens[_owner].pop();
              break;
          }
      }
      
  }

}
1 Like
#222

yeah your orght. nice slution for the getAllCatsFor function

#223
  1. constant
  2. linear
  3. I will use
mapping (address => uint256[]) public ownersToken;

You can access directly to all tokens he owns. No need to loop all holders.

2 Likes
#224

Constant, linear. Mapping address to owned kitties index identifier is the best solution to O(n2) complexity by turning the getting owned kitties list to constant time.

Theory Study:
https://www.youtube.com/watch?v=Mo4vesaut8g&t=428s

Code Study:


pragma solidity ^0.8.0;

contract KittyFixed {

    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;
        //
        //uint256 listPointer;
    }

    //struct Owner {
    //    address owner;
    //    uint256[] hasKitties;
    //}

    Kitty[] kitties;
    //Owner[] owners; 

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

    mapping (address => uint256[]) public ownersLedger;

    
    // Model
    // "0x1" => ["1", "4", "6", "5"] // Ideal
    // [ ["0x1", ["1", "4", "6", "5"]], ["0x2", ["2", "7", "3"]] ] // wrong


    //mapping (address => Owner) public kittiesOf;
    //address[] public kittesOwned; 
    
    
    // 0x1 => (Kitty.listPointer => Kitty )
    // address => array
     

    //mapping (address => mapping (uint256 => Kitty)) public ownersLedger;



    //uint[] ownedKittiesArray;
    //mapping (address => ownedKittiesArray[]) public ownersLedger;

    //mapping (address => Kitty) public ownersLedger;

    

    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 (uint256[] 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 ownersLedger[_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)
            //listPointer: kitties.length
        });
        
        kitties.push(_kitty);


        // need a new temporary array definition to fill and empty everytime the creation runs
        

        // 
        //ownedKittiesArray.push(_kitty.listPointer);
        //ownersLedger[_owner] = ownedKittiesArray;
        
        
        
        
        //uint[] memory _ownedKittes = ownedKitties.push(_kitty);

        //uint[]
        
        //ownedKittiesArray[].push(_kitty.listPointer)
        //ownersLedger[_owner] = ownedKitties;





        //kittiesOf[_owner] = _ownedKittes;

        uint256 newKittenId = kitties.length - 1;

        ownersLedger[_owner].push(newKittenId);

        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;
  }

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

=> Constant: O(1)

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

=> Linear => O(n)

  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.

=> Use:

mapping (address => uint256[]) ownershipToKityIndexes;

Benefits: getAllCats has constant access time

Drawbacks: transfer is a little bit more complicated; also needs more storage for the uint array. Both means higher gas cost.

1 Like