Assignment - ERC721

Ethereum Smart Contract Programming 201
#166

  1. Time complexity is constant

  2. It is linear as it loops through the kitties array. As the kitties array gets larger the time it takes for this function to run will grow exponentially.

  3. You can add mapping from an address owner to array of cat ID’s. In this sense though you would also need to manage/maintain the array of cat ID’s when one is transferred

1 Like
#167
  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
    The complexity is constant, or put differently it doesn’t change depending on how many cats have already been created.
  2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    The complexity is linear. We need to loop through the entire list of cats, so with each added cat we’ll have to perform the loop one additional time.
  3. We could map the index of each cat to their owners address like so mapping(address => uint256[]). This would allow us to retrieve the cats for a given address with constant complexity. Removing cats from a persons ownership would become more complex. But at least we don’t have to loop over the entire population of cats, just those owned by the given address.
1 Like
#168

  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
    It is a constant time to create new cats, as a new kitty is pushed to the end of the array and both mappings are updated.

  2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    There is at least a linear (could be exponential) time increase as nr of kitties increases. As the array is larger and the function loops through it.

  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.
    An additional mapping can be created to store the KittyIDs for each address:

    mapping (address => uint256[]) ownershipKittyList;

and update this in the transfer function

        ownershipKittyList[_to].push(_tokenId);

Benefits include a simple getAllCats function, which has a constant time.

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

The drawback is that more storage is required onchain and more logic is required i.e. a delete function would also need to be coded into the transfer function => costing more gas.

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

It is constant because the function only adds a new cat at the end of the array.

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

It is linear because the function has to go through the entire 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.

I would just link it to the existing mapping. (Note: Tbh, I was really hesitating this because it seemed too simple to be a correct answer, but I cant logically think why I should make the code more complicated if I can take the value from an already established mapping, and it would also make it constant because it gets the value directly from the mapping. The cost is 1586 gas and I cant think of any severe drawbacks with it.)

    function getAllCatsFor(address _owner) external view returns (uint256){
        return ownershipTokenCount[_owner];
    }
1 Like
#170
  1. creation takes always the same time regardless number of kitties already put in the array therefor is constant.
  2. linear based on number of kitties created.fx needs to iterate through the whole array to get number of cats by the caller of the caller.
  3. we could use mapping .
1 Like
#171

  1. Constant

  2. Linear

  3. A mapping from an address to a uint array can be used instead of an array alone. This will make the time complexity constant, but it would require more processing when transferring cats.

    mapping (address => uint[]) ownedCats;
    
    function getAllCats(address _owner) external view returns (uint[] memory cats){
        return ownedCats[_owner];
    }
1 Like
#172
  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
    Const. Every new creation the same time.
  2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    Linear. Depends how many cats is in the storage.
  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.
    With adding new mapping storage. Search in database with array to check every address is view function so does not consume gas also, but is slower.
mapping(address => uint[]) CatsBelonging;

function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
       return CatsBelonging[_owner];
    }
1 Like
#173

I feel lost in this assignment… what’s does he mean by time complexity? constant linear?

#174
  1. O(1)
  2. O(n)
  3. Map each address with an array of ids.
    mapping (address => uint[]) userOwnership;

The benefit is that we can get all cats for a users in O(1)
and the drawback is that we have to keep another mapping in the storage.

But because getAllCatFor is a “view” function at the first place, aka free, I believe that we don’t care that much to reduce the complexity here.

If we want to remove a token for someone, we need to update the userOwnership[address] table as well by coping the last element in the position of the id and using pop() to remove the last element. (as we saw in an older course).

This way we add a little more complexity and more gas in the transfer function.

In most cases it’s preferable to have the bigger complexity in view function which are cheaper. This way we reduce the storage (which is expensive) and the extra loop in the transfer operation.

1 Like
#175

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

It is constant because the time it takes to create new cats is the same every time we call the createKitty function.

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

It’s linear because we have to loop over the entire array, to get all the cats that a user has and it takes more time if many cats have been created.

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.

benefits:
It is now constant, it now gives the result of all the owned cats instantly no matter how many cats there are, because I am not looping through all the existing cats to get all my owned cats.

drawbacks:
I can not loop through all the cats anymore and get all of my cats one by one, but only the total amount of my owned cats.

function getAllCatsFor(address _owner) external view returns (uint256 cats) {
      return ownershipTokenCount[_owner];
}
1 Like
#176

Constant because doesn’t matter how many kitties still there are, during the creation there isn’t for loop or stuff like that that require more time based of where we are in the kitties array

This one, in the other hand, has a constant rise of complexity because ore kitties there are, more time will be required, and “effort” or the smart contract for finding all the kitties owned by the _owner and sign it on the result array

Well, how I can see I have done quite the same stuff of people before me… The concept is that using the system before, with an array, is all more minimal because with only a function I can track what an address own, without need to write other code in other function, but it is a costly method because you need more gas based on how much kitties are created.
With this other method, using mapping, for checking witch kitty an address own there is a constant cost, independently of the kitties created number. There is a little more cost in the creation and transfer function because everytime there is the need to update the whitch kitties an address own, but this in a little array, based on how many kitties the address own.

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

    

    function balanceOf(address owner) external view returns (uint256 balance){
        return KittiesOwnership[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)
    {
        cats = KittiesOwnership[_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);
        KittiesOwnership[_owner].push(newKittenId);

        return newKittenId;

    }

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

        kittyIndexToOwner[_tokenId] = _to;

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

        KittiesOwnership[_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;
  }

}
2 Likes
#177

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

The first cat takes the longest to create (139185 gas), while every cat creation afterwords is less and stays at a constant (104985 gas).

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

This is a complex function that needs to loop through all cats in order to find the cats that belong to the address; where the more number of cats increases the time and gas in a linear fashion.

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

If we add another mapping for mapping(address => uint256[]), we could easily get all owned ID’s without increasing time complexity for higher kitties.length. However, this does have drawbacks of storing more data, adding more complexity to the code (especially to _transfer()), and increasing the gas costs for _transfer() (since we increased the complexity there).

Adding this new mapping does make gas consumption consistent when new cats get created, but if the owner’s owned cats change at all, this does effect the gas consumed (which makes sense, because removing the owned cats would make it less complex, while owning more cats will make it more complex).

Here's my updated Kittycontract 
pragma solidity 0.8.7;

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

    function balanceOf(address _owner) external view returns (uint256 balance){
        return ownerIndexToKitties[_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)); // a fake address (often used for "burning" tokens)
        require(_to != address(this)); // the contracts address
        require(_owns(msg.sender, _tokenId));

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        // OLD gas costs (before ownerIndexToKitties change):
        // NOTE: whether the owner owns more or less cats, newly birthed cats
        // will continue to increase the gas consumed.
        // - 14 cats: 65261
        // - 34 cats: 117962
        // - 44 cats: 144312
        //
        // NEW gas costs (after ownerIndexToKitties change):
        // NOTE: if the owner gets or removes owned cats, the gas will change
        // but if more cats are birthed without changing the owners owned cats
        // then the gas will be the same each call.
        // - 14 cats: 58709
        // - 34 cats: 68390
        // - 44 cats: 73231
        return ownerIndexToKitties[_owner];
    }

    // massCreateKitties is an easy way to create a lot of cats for multiple
    // owners in order to test the changes in gas consumption compared to
    // more cats being created/owned.
    // ["0x5B38Da6a701c568545dCfcB03FcB875f56beddC4", "0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2", "0x4B20993Bc481177ec7E8f571ceCaE8A9e22C02db", "0x78731D3Ca6b7E34aC0F824c42a7cC18A495cabaB", "0x617F2E2fD72FD9D5503197092aC168c91465E7f2"]
    function massCreateKitties(uint8 _loopAmount, address[] memory _randomOwners) public returns (uint256) {
        uint8 addressIndex = 0;
        for (uint8 i = 0; i < _loopAmount; i++) {
            _createKitty(0, 0, 0, i, _randomOwners[addressIndex]);
            addressIndex++;
            if (addressIndex > _randomOwners.length-1) {
                addressIndex = 0;
            }
        }

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

    // OLD gas costs (before ownerIndexToKitties change):
    // -  1st cat: 139185
    // -  2nd cat: 104985
    // -  3rd cat: 104985
    // - 14th cat: 104985
    //
    // NEW gas costs (after ownerIndexToKitties change):
    // -  1st cat: 119103
    // -  2nd cat: 104803
    // -  3rd cat: 104803
    // - 14th cat: 104803
    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;
    }

    // _transfer performs the cat transfer without doing any checks.
    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        // if this isn't a new cat
        if (_from != address(0)) {
            // remove catID from previous owner
            uint256 lastOwnedID = ownerIndexToKitties[_from][ownerIndexToKitties[_from].length-1];
            for (uint256 i = 0; i < ownerIndexToKitties[_from].length; i++) {
                if (ownerIndexToKitties[_from][i] == _tokenId) {
                    ownerIndexToKitties[_from][i] = lastOwnedID;
                    break;
                }
                ownerIndexToKitties[_from].pop();
            }
        }
        // add catID to new owner
        ownerIndexToKitties[_to].push(_tokenId);

        emit Transfer(_from, _to, _tokenId);
    }

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

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

The Gen 0 Kitty cost 139207 gas. All others afterwards cost 105007 gas. Therefore the gas cost stays the same.

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

Without any cats the function cost 26783 gas. With just one Cat the gas consumption went up to 29854. At the fifth cat the gas cost is 41930. As you can see the cas consumption rises with each cat, suggesting, that the time complexity rises with each new cat.

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

The current function loops through the whole array. Therefore it gets more complex the more cats there are. A mapping for the adress pointing towards the owned cats seems to be the solution most of us used here.

1 Like
#179

answer: The time complexity of creating a new cat is constant. No matter the number of new cats created. The only thing that’ll change is the property of the kitty along with the token id of the kitty. Which, both has a time complexity of O(1).

answer: The time complexity of getAllCatsFor function is linear w/ the number of cats stored/created. The execution time of the function increases along with the number of cats.

answer:

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

    

    function balanceOf(address owner) external view returns (uint256 balance){
        return catsOwnedByAddress[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){
        cats = catsOwnedByAddress[_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)) {
            revokeTokenIdOwner(_from, _tokenId);

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

}

Here, since the mapping of tokenIds through owner address is created. getAllCatsFor function will be constant.
Benefit: Conservation of gas cost as the function is now constant instead of linear (previous implementation).
Drawbacks: A linear function is called in the loop which has a function to remove the transferred tokenId. Thus, increasing the gas cost again.

1 Like
#180

  1. Constant. No looping through arrays of varying length. All done via mappings.

  2. Linear. Getting all of a user’s cats involves looping through the full array of every cat in existence, therefore it will take longer the more cats there are in the array.

  3. My solution still has linear elements but is more time efficient (however, considerably less storage-efficient). With this approach, the full array of all cats is never searched, rather, every user gets their own array of all the cats they own mapped to their address. The getAllCatsFor function just returns the owner’s mapped array of owned cats.
    The _transfer function then needed some re-working to update the sender and receiver’s mapped arrays when a cat is sent and now uses a for loop.

Benefits: The getAllCatsFor function is now constant as it just returns an array using a mapping.

Drawbacks: Though the getAllCatsFor function is now constant, the _transfer function is now linear. Still it’s much less time-intensive than looping through every cat that exists since each owner’s array of cats will be much shorter than the full list of cats. The big drawback is the storage cost though. This approach doubles the number of Kitty objects that will be stored in storage.

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;
        uint kittyId; //had to add this to the struct for new owner-specific arrays
    }

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => Kitty[]) kittiesOwned; //new array mapped to each address that only contains their kitties, replacing the 'ownershipTokenCount' mapping.

    

    function balanceOf(address owner) external view returns (uint256 balance){
        return kittiesOwned[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 (Kitty[] memory){
        return kittiesOwned[_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),
            kittyId: uint256 (kitties.length)
        });
        
        kitties.push(_kitty);
        kittiesOwned[_owner].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)){
            //finds the queried kitty from the array mapped to the _from address 
            //sets the new owner in the mapping and updates the arrays mapped to the _from and _to addresses
            for (uint i = 0; i < kittiesOwned[_from].length; i++){
                if (kittiesOwned[_from][i].kittyId == _tokenId){
                    kittyIndexToOwner[_tokenId] = _to;
                    kittiesOwned[_to].push(kittiesOwned[_from][i]);
                    kittiesOwned[_from][i] = kittiesOwned[_from][kittiesOwned[_from].length - 1];
                    kittiesOwned[_from].pop();          
                }
            }
        }
        else (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
#181

Hello everybody,

Especially the last question was hard to think about
Here are my answers

  1. Creating new cats with the Genesis function is constant. I saw that the first mint was more expensive than the other mintings, but I guess that’s pure because it’s the first => creating the database costs more than adding data to the database

  2. For me it was obvious that it’s linear. I didn’t even had to test it out to come to that solution. Why? because it’s using a loop. More KittieNFT’s, more data to check…

  3. Having a loop in a function costs a lot of gas. especially if there are more and more kitties being minted. My solution to this problem is having an array in a mapping with only one integer that saves the ID of the NFT. Ofcourse there are some drawbacks to this solution, but isn’t this the best solution for this function?

I’m really curious about everyone’s opinion about this.

1 Like
#182

Why not put the owner address into the NFT struct? Then you don’t need the mapping(id => address).

#183

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

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

How could the storage design be changed to make the getAllCats function constant?
I did that below. Make the mapping Owners(address => uintp[), that is, have the Owner mapping map the owner address to an array of all his cats. Then you can just return the array when asked. It makes the transfer function more complex because you have to remove the kitty from the _from sender, by using the pop() trick but I am infering that getAllCatsFor is called more often than _transfer so it lessens the gas burden on users in general.


pragma solidity ^0.8.0;

// SPDX-License-Identifier: MIT

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;
        address owner; // don't need separate id => owner mapping, just use the kitty itself to hold owner 
    }

    Kitty[] Kitties;

    mapping (address => uint[]) Owners; // (address => array of kittie ids)

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

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

    function ownerOf(uint256 _tokenId) external view returns (address) // should be private (nobody's business who owns it)
    {
        return Kitties[_tokenId].owner;
    }

    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);
    }
    
    // complexity O(1)
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        return Owners[_owner];
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, address(this));
    }

    // complexity O(1)
    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),
            owner: address(this) // just use this contract address as the temporary owner during creation
        });
        
        Kitties.push(_kitty);

        uint256 newKittenId = Kitties.length - 1;

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

        _transfer(address(0), _owner, newKittenId); // gen0 kitties are owned by the contract itself address

        return newKittenId;
    }

    // complexity O(n), tradeoff for getAllCatsFor O(1) because getAllCatsFor probably called more often than transfer
    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        Owners[_to].push(_tokenId);
 
        // do the pop trick to delete the kittie from the _from Owner O(n)
        for (uint i = 0; i < Owners[_from].length; ++i) {
           if (Owners[_from][i] == _tokenId) {
               uint len = Owners[_from].length;
               Owners[_from][i] = Owners[_from][len-1];
               Owners[_from].pop(); 
           }
        }
        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }

    // complexity O(1)
    function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
      return Kitties[_tokenId].owner == _claimant;
  }
}

P.S. More trick questions! You got me on that one.

1 Like
#184

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

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

  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.

Every Option needs a Loop. So we have to iterate somewhere over all Data to get all IDs. If we use an array we have to iterate over the array if User A wants to send a NFT to User B to delete it from his array.

1 Like
#185

1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
Constant, each new cat will be added to the end of kitties array.

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
Linear, the function have to iterate through the kitties to get all cats owned by a user.

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

Could be through a mapping from address to an integer array where we could storage the ID of the cats the user owns.

mapping (address => uint256[]) ownedKitties;

Then we could just return the array from the mapping like this:

    function getAllCatsFor(address _owner) external view returns (uint[] memory){
        return ownedKitties[_owner];
    }
1 Like