Assignment - ERC721

Ethereum Smart Contract Programming 201
#186

  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
    Creating a new cat is the same process which is constant.

  2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    Looping requires more effort for cats to be created therefore is linear.

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

Benefits of getALLCats function? It is a faster process since it doesn’t have to loop through the whole Kitty array.

Drawback - It makes the _transfer function complex to execute as it has to modify the owners array.

1 Like
#187

  1. It is constant (apart from negligible increases) as the new data being created is appended to the array without looking at the previous elements nor looping through them.

  2. The time needed to perform the function increases (roughly) linearly as the total supply grows, since the for loop needs to iterate its code as many times as the number of cats in the “kitties” array.

  3. Here is my code (I have commented the new/amended lines with 5 slashes):

Click here to expand 
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[]) kittiesOwned; ///// Store the array of kitten IDs of each owner
    mapping(uint256 => uint32) ownedId;  ///// Keep track of the element position within each owner's array

    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){  /////Just need to return an existing array
        return kittiesOwned[_owner]; ///// Replaced the whole function body with this line
    }

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

            kittiesOwned[_from][ownedId[_tokenId]] = kittiesOwned[_from][kittiesOwned[_from].length-1]; ///// Override sent token of previous owner's array with last element of the same array
            kittiesOwned[_from].pop(); ///// Remove last element of the previous owner's array
        }

        kittiesOwned[_to].push(_tokenId); ///// Append transferred token to new owner's array
        ownedId[_tokenId] = uint32(kittiesOwned[_to].length - 1);  ///// Store the token position within the new owner's array

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

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

}

My approach consists of introducing an array of IDs owned by each address (linked via mapping) which is constantly updated every time a kitten is created/transferred, so that we don’t need to loop through the kittens in order to gather such data. I am also creating a mapping to store the each token’s position within the array above, so that we can use it to update the ownership arrays each time a kitten is transferred.

The only drawbacks of this solution are:

  • I have introduced additional complexity to the code (slightly harder to read)
  • Additional storage will be used by the new variables I have introduced (although it should be negligible as they are uint arrays and mappings to uint)
1 Like
#188

1 What is the time complexity of creating new cats? (constant or linear w nr of cats).
It’s constant, at least for generating Gen0 Kitties. For further kitties code is not provided.

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
Complexity increase linearly w/ the n. of cats because getAllCatsFor loops through all of them. It’s still worth to say that that function is external view and this means that users still won’t pay for the complexity.

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

pragma solidity ^0.8.0;

library UInt256Array {
    function remove(uint256[] storage arrPtr, uint256 idx) internal
      returns(uint256 _ret)
      /*
        remove the element at index replacing the indexed element with the last element
        order of the array is NOT preserved
      */
    {
      require(idx < arrPtr.length, "IndexError");
      _ret = arrPtr[idx];
      arrPtr[idx] = arrPtr[arrPtr.length - 1];
      arrPtr.pop();
    }

    function find(uint256[] storage arrPtr, uint256 data) internal view
      returns(bool _found, uint256 _idx)
      /*
        find the first index for which data == arrPtr[index]
        the first returned element is meant to be "found"
        in case of not found the index will be the last index (arrPtr.length-1)
        call like:
        (bool found, uint index) = _findIn<T>Array(data, stateMember);
      */
    {
      for (_idx; _idx < arrPtr.length; _idx++){
        if(arrPtr[_idx] == data){
          _found = true;
          break;
        }
      }
    }
}

contract Kittycontract {

    using UInt256Array for uint256[];

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

    Kitty[] kitties;

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

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

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

    function ownerOf(uint256 _tokenId) external view returns (address)
    {
        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);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        cats = ownerToKittiesIndexes[_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),

            owner: _owner
        });
        
        kitties.push(_kitty);

        uint256 newKittenId = kitties.length - 1;

        ownerToKittiesIndexes[_owner].push(newKittenId);

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

        return newKittenId;
    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        (bool hasToken, uint256 arrIdx) = ownerToKittiesIndexes[_from].find(_tokenId);
        require(hasToken, "_tokenId doesn't belong to _from");
        
        kitties[_tokenId].owner = _to;
        ownerToKittiesIndexes[_from].remove(arrIdx);
        ownerToKittiesIndexes[_to].push(_tokenId);

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

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

}

My solution re-design the smart contract in such a way that we only need a single mapping to store the kittens Ids as value paired with the owner address.
I’m still not really convinced because even if the getAllCatsFor call is very cheap, transfer will be more costly (althought increasing linearly to loop inside the owned kitties). And users will have to pay for trasfer since it obviously change the state of the contract. I feel like I have a cheaper external view function at the expense of a external and it doesn’t seems that smart…

1 Like
#189

Hoping someone can explain something about this contract. Its a very basic question so i am probs missing something quite obvious but…

When we use the createKitty function it returns us a newKittenId by uisng the following logic…
uint256 newKittenId = kitties.length - 1;

The above makes sense to me, but how do we arrive at uint tokenId? Don’t we need to assign newKittenId = tokenId?

#190
  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 because no matter the amount of cats, the procedure will always be the same and have the same time complexity

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

The time complexity of the getAllCatsFor is going to be linear, because it has to loop through the array depending upon how many cats are in the array.

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

The design could be easily improved by utilizing a mapping that maps an address to an array of the cats owned. This will use less gas and it is executed in constant time. However, in this case, because out getAllCats function is a view function, gas is irrelevant. Using this strategy would actually make our contract use more gas, because we would have to use more gas in our transfer function which is not a view function. This is because we are writing more to storage with our new mapping.

1 Like
#191

Hi, these are my answers:

  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
    It is linear w nr of cats
  1. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    It is linear w nr of cats
  1. How could the storage design be changed to make the getAllCatsFor function constant? Implement your idea. Then discuss the benefits and drawbacks of your implementation and post everything in the forum.
    This is how I change the storage design to make the function constant:

Create a state variable to map the address of the owner to an array of all kitties’ indices

// my solution
    mapping(address => uint[]) ownerToKittiesIndices;

In the private function _transfer, add one more line of code to push new _tokenId to the array of the mapping

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

        kittyIndexToOwner[_tokenId] = _to;
        // my solution
        ownerToKittiesIndices[_to].push(_tokenId);

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

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

Now, regardless of the amount of kitties an owner has, the time complexity of getting all kitties’ indices will be constant

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

The benefit:

As the amount of kitties of an owner increases, the old design will spend more gas, but the mapping design requires the same amount of gas every time no matter how many kitties there are.

The drawbacks:

  • Creating a new kitty with the mapping design requires more gas (15% more than the old design) because of pushing new kitty index to the mapping ownerToKittiesIndices.
  • In addition, getAllCatsFor function is a view function, I see that the execution cost only applies when called by a contract, so the benefit only counts if this function is called by other external contracts, otherwise, the old design will save people money when creating new cats.
1 Like
#192

Question. With the the getAllCatsFunction why is it… uint[] memory cats? I have never seen it written out like this with uint. Normally when there is struct array I’d use Kitty[] memory. Is that okay too or is their a particular reason we have to use uint[] memory cats instead.

To further illustrate. This is the code we have…

function getAllCatsFor(address _owner) public 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;
           }
       }

But I generally would use “Kitty[] memory” in place of “uint[] memory cats” like so…

function getAllCatsFor(address _owner) public view returns (Kitty[] memory) {
           Kitty[] 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;
           }   
       }

Is the my alternative okay or is there a reason we are specify “uint[] memory cats” ?

1 Like
#193

Your solution is OK. :ok_hand:

uint[] memory cats is the same has uint[] memory result, just a array of unsigned integers to store the cat Id, the array will be returned filled with the Id of each cat the address _owner owns.

Carlos Z

#194

Thanks for the response Carlos. The comparison in question was not unit[] memory cats vs. units[] memory result. It was….

unit[] memory cats vs. Kitty[] memory.

You see Kitty[] memory I am using the struct array name (our struct is called Kitty) which I thought was necessary here. It appears it’s not necessary but I’m confused why it’s not ? I guess you are saying we can create any variable name for the array to store the values we return but I thought it was necessary to use our struct name (Kitty[] memory) for some reason.

#195
  1. The creation of new cats will be constant. The size of the array doesn’t impact the time to create a new cat.
  2. The getAllCatsFor function would have a linear time complexity because it’s related to the size of the array it has to iterate through. The longer the array the longer it will to take to complete the function call.
  3. Using Mapping instead of using an array would create a constant time complexity which would be good for owners with a lot of cats. Save gas as well with it being But mapping will not allow me to loop through an array anymore so one could only get the amount in the array but not all of them individually at once.
function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        return ownershipTokenCount[_owner];
    }
#196
  1. constant, procedure is the same regardless of cat
  2. linear, since the function has to iterate through the list of cats
  3. could create a map of addresses to lists of cats belonging to that address. Downside would be that removing would be rather cumbersome and tedious, being both linear and not the most nicest of code. It would make the transfer of tokens rather slow and most tokens in this category does get flipped.
1 Like
#197

1- complexity is constant because, it always requires the same resources to the blockchain.

2- in this case , the complexity more every element put in the array, because this add new loops for complete the find.

/* I think by pushing in a mapping array the owner's kitten ID.
    Make a constant function, or at least less expensive of search 
    in all the array. */
    mapping (address => uint256[]) listIndexKitty;


 function getAllCatsFor(address _owner) external view returns (uint[] memory){
        return listIndexKitty[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;
// ---------------------------------------------------------------
        listIndexKitty[msg.sender].push(newKittenId);
// ---------------------------------------------------------------
        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

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

        return newKittenId;

    }

I think by pushing in a mapping array the owner’s kitten ID. Make a constant function, or at least less expensive of search in all the array.

N.B. miss implementation in transfer the Token, but i think need in this exercise

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

The time complexity for creating a new cat is constant because when the function is called the new kitty is simply
added tothe end of the kitties array.

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

The time complexity for getAllCatsFor function is linear, this is because to get all the cat for the address it has
to loop through the array of kitties to get all the cats owned by the address ie. it has to repete the instruction till it gets all the
cats the address ownes.

//My implementation for question 3 


mapping (address => uint256[]) kittyOwned;

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

    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;

        kittyOwned[msg.sender].push(newKittenId);  // here we push the id of the newly created kitty to the uint256[] in the kittyOwned mapping.

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

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

        return newKittenId;

    }

Advantage:
The getAllCatsFor function consumes less gas and is constant.

Disadvantage:
it will add more complexity to the transfer function because we will have to remove the transferred cat from the array in the kittyOwned mapping.

2 Likes
#199
  1. Constant
  2. Linear
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;

    //A mapping from a kitty index to where that kitty index is stored in the uint256[]
    //within the ownershipOfTokens mapping
    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){
        /*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 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;//ownershipOfTokens[address(0)].length.sub(1);

        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 the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }

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

}

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.

2 Likes
#200

  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
    Time complexity of creating new cats is constant because number of steps involved in creating new cats is fixed , their complexity is not increased with creation of more cats. The time taken in creating first cat and nth cat will be same.

  2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    Time complexity of getAllCatsFor() function will be linear which means that with increase in number of cats the time complexity will also increase linearly. As this function is iterating through all array , its time for full iteration will increase with increase in number of cats in array.
    Time complexity

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

I will declare a mapping of address to array of uint
mapping (address => uint256[]) ownershipToken;
instead of
mapping (address => uint256) ownershipTokenCount;
After declaring this we can getAllCats by simply returning the array

function getAllCatsFor(address _owner) external view returns (uint[] memory cats){

     return ownershipToken[_owner];

 }

In this way we will make the time complexity of the above function constant.

But after doing this time complexity of create new kitty function will increase slightly. I have to just make some change in transfer function which create new kitty function calls. The changes i will do are

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

    kittyIndexToOwner[_tokenId] = _to;

    ownershipToken[_to].push(_tokenId);

    if (_from != address(0)) {

        for(uint i=0;i<ownershipToken[_from].length;i++){

            if(ownershipToken[_from][i]==_tokenId){

                ownershipToken[_from][i]=ownershipToken[_from[ownershipToken[_from].length-1];

                ownershipToken[_from].pop();

            }

        }

       

    }

    // Emit the transfer event.

    emit Transfer(_from, _to, _tokenId);

 }
1 Like
#201

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. We are always pushing to the last spot in an array and therefore, the time complexity does not change.

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
The time complexity of the getAllCatsFor function is linear. The time will increase as more cats are added. This is because we need to loop through the entire array of cats in order to find all cats owned by a particular address.

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

To make the getAllCats function constant, we can create a mapping:
mapping (address => uint[]) kittiesOwned;

To return all cats owned by an address we would need a function like the following:
function getAllCatsFor(address _owner) external view returns(uint[] memory cats){
return kittiesOwned[_owner];
}

We would save some time in getting the cats owned by a specific address, but we create complexity and added cost when transferring a cat. We now need to go through the array of cats owned, grab the id of the cat being transferred, and update the array. This is time consuming and expensive.

1 Like
#202
  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
    It is constant at it takes the same time to create each cat.
  2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    It is linear, it increase with each cat added to the array.
  3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
    I would make a mapping of the owners with an array of the cats that they posses:
    mapping(owners=> uint256[]) catOwned
    The cons are thatt it add complexity to the code and even a linear function to remove the ownership of the cats but it will bring the benefit to do not to loop the array any time anyone want to know their cats.
1 Like
#203
  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
    O(1), there is only push at the end of the array, no looping.
  2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    O(n) - linear, the farthest kitty is located in array, the longer.
  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.
mapping(address => uint[]) ownedCats;

function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
       return ownedCats[_owner];
    }
#204
  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).

Creating a cats Time complexity is Constant 0(1), which means it is a constant time, even with different input. take less storage space, less gas usage and iteration.

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

getAllCatsFor function is a Linear Time Complexity 0(n), this indicate the function will take longer amount of time if the input is larger, so the larger the array , the larger the input the larger amount of time it will take.

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

From all indication, we need to change the Mapping to this format `mapping (address => uint[]) ownedKitties; we also need to delate and replace the delated owner from the array list which am sure with take less gas compared to the previous function.

#205

Hi everyone, these are my thoughts on the ERC721 assignment:

  1. Time complexity for creating a new cat is constant. Doesn’t really matter how long the kitties array is since we’re pushing to it, and the new id is derived by kitties.length-1.

  2. getAllCatsFor() function is linear since it depends on the size of the kitties array due to the for loop.

This is my code to make the getAllCatsFor() constant.

// SPDX-License-Identifier: MIT
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[]) catsForOwner; 

    

    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 = catsForOwner[_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;

        catsForOwner[_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;

        catsForOwner[_to].push(_tokenId);

        if (_from != address(0)) {
            ownershipTokenCount[_from]--;
            for (uint i=0; i<catsForOwner[_from].length; i++) {
                uint idToRemove = _tokenId;
                uint lastId = catsForOwner[_from][catsForOwner[_from].length -1];
                if (catsForOwner[_from][i] == idToRemove){
                    catsForOwner[_from][i] = lastId;
                    catsForOwner[_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;
  }

}

I made a new mapping to map an address to an array of owned kitties. By doing so, the getAllCatsFor() function only needs the owner address to retrieve the corresponding array with the kitties.

The _createKitty() function pushes the new Id to the corresponding array catsForOwner[_owner].push(newKittenId).

The problem is that now the _transfer() function has to loop through the array of an address in order to find and eliminate the ID of the kitty that’s been transferred.

Some feedback would be super welcomed since I have no idea if this is a good solution, it’s the first idea I had. Also, I’m not sure if the _transfer() function has been updated correctly.

Another question I had is on the Kitty object that’s gets created from the struct in the _createKitty() function. What is the reason behind it, as opposed to just using the Kitty struct?

This is a long answer I guess, so thanks in advance :grinning: :grinning:

1 Like