Assignment - ERC721

[samartrade]

1. constant complexity for creating new cats; it creates a new entry in the array.

2. Linear complexity, complexity increases with the number of kitties, the function getAllCatsFor is looping through each cat defined in the array, which can be overkill when more tokens are available, which affects performance.

3. To solve the issue of performance, I added 2 mappings:
   one mapping from Owner Address to an array of token IDs.
   the other mapping is from TokenID to its index within the owner array above.

Pros for the solution:

1. eliminate the need to loop through the whole kitten struct array to get the list of tokens; instead, it available immediately.

Cons:

1. Complexity when performing transfer function to add token IDs to the array and update the index mapping.
2. Complexity of handling deletion from token IDs array.

Code below:

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 from owner address to an array containing all tokenIds
        mapping (address =>  uint256[]) ownedKittiesIds;
    
    // mapping from tokenId to the index within owned tokens list (in the ownedKittiesIds).
    mapping (uint256=> uint256) ownershipTokenPointer;
    

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

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

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

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

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        //uint[] memory result = new uint[](ownershipTokenCount[_owner]);
        //uint counter = 0;
        //for (uint i = 0; i < kitties.length; i++) {
          //  if (kittyIndexToOwner[i] == _owner) {
            //    result[counter] = i;
              //  counter++;
            //}
        //}
        //return result;
        return ownedKittiesIds[_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 {
        uint256 index;
        uint256 lastTokenID;
        
        //increase count of tokens for the to address
        ownershipTokenCount[_to]++;
        //update ownership address
        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {

            //get the index for the deleted token
            index=ownershipTokenPointer[_tokenId];
            //delete ownedKittiesIds[_from][index];
            //get tokenID for the last index
            lastTokenID=ownedKittiesIds[_from][ownedKittiesIds[_from].length-1];
            //move last index to deleted array position
            ownershipTokenPointer[lastTokenID]=index;
            ownedKittiesIds[_from][index]=lastTokenID;
            ownedKittiesIds[_from].pop();
            
            // add token ID to the ownedKittiesIds array
            ownedKittiesIds[_to].push(_tokenId);
            index=ownedKittiesIds[_to].length-1;
    
            //store index value for the new token.
            ownershipTokenPointer[_tokenId]=index;
        
        
            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;
  }

}```

[Charlene_Nicer]

1.) constant time, there is no need to iterate through the list to add a new kitty, it is simply being appended at the end of the list
2.) linear time, this function iterates through the list
3.) Have a mapping on owner address to an array of indexes of cats an owner has. Benefits include faster lookup, however, more memory is needed

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

    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 ownersKittyTable[_owner];
        // uint[] memory result = new uint[](ownershipTokenCount[_owner]);
        // uint counter = 0;
        // for (uint i = 0; i < kitties.length; i++) {
        //     if (kittyIndexToOwner[i] == _owner) {
        //         result[counter] = i;
        //         counter++;
        //     }
        // }
        // return result;
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

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

        uint256 newKittenId = kitties.length - 1;

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

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

        return newKittenId;

    }

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

        kittyIndexToOwner[_tokenId] = _to;

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

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

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

}```

[BrendanGolledge]

Everybody else before me has already come up with the same answers as me.

1. The time complexity of adding a kitty is 1. So far as I can tell, the create kitty function does nothing but assign the input variables to the variables in the kitty structure.
2. The time complexity for get all kitties is linear, since it has to iterate through an array.
3. As everyone else has also said, in order to make get all kitties linear, you could create a mapping where an owner’s ID points to an array of kitties he owns. This would require creating functions to add and remove kitties from an owner’s array, and the remove function would have to be linear since it would have to iterate through the array. There might also be some linearity involved in the add function if you have to check to see if the owner already owns a kitty. But this is much preferable to having the get all kitties function be linear. The number of kitties any particular owner has must be smaller than the total number of kitties, which means that the difficulty of adding or removing kitties from a particular owner’s array must be much much smaller (if there are many owners) than the complexity of checking every single kitty that has ever been created every time someone wants to see which kitties he owns.

[RoryPhilBTC]

1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
The time complexity is constant cause there is only one set of information being entered into the array at that given time.

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats). The array would need to be looped through and find all cats owned by the given address making the time complexity of the getAllCatsFor function linear.

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

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 => Kitty[]) catsOwned;

    

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

        kittyIndexToOwner[_tokenId] = _to;

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

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

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

}

You would need to create a new function and write to the mapping which in turn will result in way more gas fees. So the initial code is fine to implement.

[Neeraj_Nerlekar]

1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
   The creation of cats is constant as it will always take the same amount of time to create a new cat and does not depend on the Array size.

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
   To find a certain address for a given token id, we need to loop through the entire array. Thus, the time will increase as the size of the array increases and is a linear function.

3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
   One solution is to add a mapping function. The advantage is that it will be less time complex and will not depend on the array’s size, but it will add more functionality when transferring the kitty to a different owner.

[MrSeven]

1. The time complexity of creating new cats is constant. The function just creates the cat and adds to the next position in the array.

2. The time complexity of the getAllCatsFor function is linear with the number of cats. The coding for this function searches the entire array and increments +1 each time it finds the matching address. Therefore, the longer the size of the kitties array (or the number of cats in the array), the longer it will take the function to complete and provide the number of cats owned by the address owner.

3. Here is my design:

    function getAllCatsFor(address _owner) external view returns (uint)  {
        return ownershipTokenCount[_owner];
    }
    I would use the mapping ownershipTokenCount and search by the address.  This would make the time complexity of the getAllCatsFor function constant.  The benefit is obviously the time efficiency of the running the function.  If I only made the change to the getAllCatsFor function (as I showed above) and left the rest of the contract unchanged, I can't seem to identify a drawback.

[Bripeachy]

1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
constant. each cat created has the same time

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
linear, it changes based on how many cats are being created, and stored in the array.

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

function getAllCatsFor2(address _owner) external view returns (uint) {
        return ownershipTokenCount[_owner];
    }

The created tokens in my contract are unique, so counting the tokens will give you the number of cats this person owns. 
This way is easier because the design is not changed.

[cecilia]

Answer

1. The time complexity of creating new cats is constant because it just keeps getting pushed to the array.

2. The time complexity of the getAllCatsFor function is linear because it keeps looping through the array until it finds the address its looking for.

3. This design works better because its more efficient and also each token is unique and that means however many tokens they own is how many cats they own.

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

[camarosan]

What is the time complexity of creating new cats?
constant because every cat is added and took the same time create any of them
What is the time complexity of the getAllCatsFor function?
linear because we need to iterate every element
How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.

my code
I created getAllCats2 function and new mapping catsfor to make this

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(address => uint256[]) catsfor; // new mapping for Assigment
    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => uint256) ownershipTokenCount;

    

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

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

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

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

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

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

        uint256 newKittenId = kitties.length - 1;

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

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

        return newKittenId;

    }

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

        kittyIndexToOwner[_tokenId] = _to;
        catsfor[_to].push(_tokenId); // new for Assigment

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

}

I think my implementation is the best for the function getAllCatsFor for save time in every search, the function is smaller and simple, but the cost is an extra mapping with an array that push more work for transfer function.

[jokir]

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

Creating new cats is constant as there is no searching or sorting of existing cats.

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

Linear against the total number of cats created. It currently runs through the entire array of cats to check if the owner is the one calling getAllCatsFor().

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.

To remove the linear time complexity the quick fix would be to turn ownershipTokenCount mapping to an uint256 array of all the tokenIds owned. You can still access the number of tokens owned with ownershipTokenCount[address].length which is what the original variable tracked.

However this creates another linear complexity in the transfer function as you would need to search each owners array to find the one to remove. Adding the token to another user would be a simple .push(tokenId) to the new owner array.

To get solve this new linear complexity issue, I created a struct called OwnerIndex that has two variables, and ownerAddress and indexPosition. I then changed the kittyIndextoOwner mapping, to map to this new struct. This allows quick access to all relevant ownership variables from the tokenId number. We can now transfer ownership easily without having to search through any arrays.

Code below:

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 OwnerIndex {
        address ownerAddress;
        uint indexPosition;
    }

    Kitty[] kitties;

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

    

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

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

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

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

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

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

        uint256 newKittenId = kitties.length - 1;

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

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

        return newKittenId;

    }

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

        ownershipTokenCount[_to].push(_tokenId);
        kittyIndexToOwner[_tokenId].ownerAddress = _to;
        kittyIndexToOwner[_tokenId].indexPosition = ownershipTokenCount[_to].length - 1;

        //ownershipTokenCount[_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].ownerAddress == _claimant;
  }

}

[danielmain]

1. constant
2. linear w nr of cats
3. See diff:

diff --git a/kittycontract1.sol b/kittycontract1.sol
index 359a951..3986cc0 100644
--- a/kittycontract1.sol
+++ b/kittycontract1.sol
@@ -26,11 +26,11 @@ contract Kittycontract {
     Kitty[] kitties;
 
     mapping (uint256 => address) public kittyIndexToOwner;
-    mapping (address => uint256) ownershipTokenCount;
+    mapping (address => uint256[]) ownershipTokenCount;
 
     
 
-    function balanceOf(address owner) external view returns (uint256 balance){
+    function balanceOf(address owner) external view returns (uint256[] memory){
         return ownershipTokenCount[owner];
     }
 
@@ -52,16 +52,8 @@ contract Kittycontract {
         _transfer(msg.sender, _to, _tokenId);
     }
     
-    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
-        uint[] memory result = new uint[](ownershipTokenCount[_owner]);
-        uint counter = 0;
-        for (uint i = 0; i < kitties.length; i++) {
-            if (kittyIndexToOwner[i] == _owner) {
-                result[counter] = i;
-                counter++;
-            }
-        }
-        return result;
+    function getAllCatsFor(address _owner) external view returns (uint256[] memory){
+        return ownershipTokenCount[_owner];
     }
     
     function createKittyGen0(uint256 _genes) public returns (uint256) {
@@ -95,15 +87,17 @@ contract Kittycontract {
 
     }
 
-    function _transfer(address _from, address _to, uint256 _tokenId) internal {
-        ownershipTokenCount[_to]++;
+    function _removeKitty(address _owner, uint256 _tokenId) internal {
+        ownershipTokenCount[_owner][_tokenId] = ownershipTokenCount[_owner][ownershipTokenCount[_owner].length-1];
+        ownershipTokenCount[_owner].pop();
+    }
 
+    function _transfer(address _from, address _to, uint256 _tokenId) internal {
+        require(ownershipTokenCount[_from].length > 0);
+        _removeKitty(_from, _tokenId);
+        ownershipTokenCount[_to].push(_tokenId);
         kittyIndexToOwner[_tokenId] = _to;
 
-        if (_from != address(0)) {
-            ownershipTokenCount[_from]--;
-        }
-
         // Emit the transfer event.
         emit Transfer(_from, _to, _tokenId);
     }

[inzhagey]

• 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 because the kitties are added to an array and this process will not change.

• What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
  This function is linear because the size grows as the function iterates through the cats.

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

function getAllCatsFor(address _owner) external view returns (unit) {
           return getAllCatsFor[_owner];
}

This gets all the unique token address’s you own in an easier way to see the number of cats you own.

[Shawn_Wollenberg]

1. Constant
2. Linear (due to looping through array)
3. Add a mapping from address to array of uints (kitty IDs). the return function would then just take the address and return an array of kitties without looping. The transfer function would become more expensive as you’d have to loop through the array in the mapping for the “from” address to get the index so that you could switch with the last value in the array and then pop() for removal.

mapping(address => uint[]) public ownerKitties;

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

[karips]

1. Constant

2. Linear

3. We could create a storage mapping that maps each address to a list with all the kitties owned by the address. Then the address will return in constant time the list with all the kitties that match the address.
   Con: The obvious drawback is the space-time complexity trade-off, meaning that since we use more space to save this information to be available ad-hoc, which costs memory and increases the gas cost. The snippet of the function (not including the initialization of the state variable and the necessary amendments in the other functions) is the following:

    function getAllCatsFor(address _owner) external view returns (uint[] memory){
        // mapping (address => uint256 []) public OwnerToKitties;
         return  OwnerToKitties[_owner];
        
    }

[Cryptogirl]

Hey y’all,

This wasn’t so easy, and I have an error in my code and I don’t understand why, can someone pls look into it for me? I’d really appreciate it.

Here is my solution

pragma solidity 0.7.4;

contract CryptoCats{

    string public constant name = "myKitty";
    string public constant symbol ="MKT";
    
    event Transfer(address from, address _to, uint catID);
    
    event Birth (
        address owner,
        uint catID,
        uint momID,
        uint dadID,
        uint genes
);

    struct Cat {
        uint gene;
        uint birthDay;
        uint momID;
        uint dadID;
        uint generation;
        
        }
    
    Cat[] cats;
    
    mapping(uint => address) owner;
    mapping(address => uint) howManyCats;
    
   
    function balanceOf(address owner) public view returns(uint numberOfCats){
        
        return howManyCats[owner];
        
    }
    
    function totalSupply() public view returns(uint allCats){
        return cats.length;
    }
    
    
    function ownerOf(uint catID) public view returns(address catOwner){
        
    return owner[catID];
    }
    
    function transfer(address _to, uint _catID) external returns(bool success){
        
        require(_to != address(0));
        require(_to!= address(this));
        require(_owns(msg.sender,_catID));
        
       
        _transfer(msg.sender,_to,_catID);
        
        return true;
        
        
    }
    
    function getAllCatsForAddress( address _owner) external view returns(uint allCatsOwned){
      
     // uint[] memory allCatsOwned = new uint[] (howManyCats[_owner]);        
      
     // uint counter = 0;

//        for( uint i = 0 ; i < cats.length;i++){
           // if(howManyCats[i] == _owner){
                
              //  allCatsOwned[counter] = i ;
               // counter ++;
               
          //  }
          //   return allCatsOwned;
       // }
       
       // mapping storage design down below
       
       return howManyCats[_owner];
    }
    
    function createCatGenZero(uint _genes,address _owner) public view returns(uint generation){
        
        _createCat(0, 0, 0,0,msg.sender,_genes); // here I'm getting an error : Invalid type for argument in function call.
                                                 // Invalid implicit conversion from address payable to uint256 requested. HELP :)
        
        return generation;
    }
    
    
    function _createCat(uint _gene, uint _birthDay, uint _momID, uint _dadID,uint _generation,address _owner) private returns (uint newCatID){
        
        Cat memory newCat =  Cat ({
        gene: _gene,
        birthDay:block.timestamp,
        momID:_momID,
        dadID:_dadID,
        generation:_generation
        
        });
        
        cats.push(newCat);
       
       uint _newCatID = cats.length -1;
    
    emit Birth(_owner,newCatID,_momID,_dadID, _gene);
    
    _transfer(address(0),_owner,newCatID);
    
    return newCatID;
        
    }
    
    function _transfer(address _from, address _to, uint _catID) internal returns (bool success){
        
        owner[_to]++;
        howManyCats[_catID]= _to;
        
          if (_from != address(0)) {
            howManyCats[_from]--;
        }
         emit Transfer(_from,_to,_catID);
         
        return true;
    }
    
      function _owns(address _buyer, uint256 _catID) internal view returns (bool success) {
      howManyCats[_catID] == _buyer;
      
      return true;
  }
    
}

and my answers

1. Constant I believe, because we just instantly create a cat sturct and just add it to the array.

2. In the getAllCats function it’s linear because we are using a loop to go through the whole array one by one.

3. We can change the loop to a mapping that simply points us to the amount of cats the owner has but in this case we cannot see the actual kitties owned by the person by ID. It is cheaper to execute it tho.

[dan-i]

Hey @Cryptogirl

You are sending the parameter in the wrong order.

 _createCat(0, 0, 0,0,msg.sender,_genes);
    
function _createCat(uint _gene, uint _birthDay, uint _momID, uint _dadID,uint _generation,address _owner)

The 5th argument should be a uint but you are sending an address (msg.sender).

Cheers,
Dani

[Cryptogirl]

I see, it makes sense.
Thanks a lot!

[jrdefideveloper]

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

It’s O(1) to create a new cat

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

It’s O(N) since it has a for loop

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.

Include a mapping of owner to array of cats

mapping (address => uint[]) ownerToCats; 

function getCatsAddressOwns(address owner) external view returns(uint[] memory cats) { 
    return ownerToCats[owner]; 
}

// Also removal we need to do that singly linked list chop off thingy. Put the item you want to delete to the end of the list and pop it off. 

Now we get an instant lookup but of course storage is the most expensive so I’d not go this route unless I expect a lot of these kind of lookups.

[Duende]

1The time is constant
2.The time is linear.

[CryptoXyz]

1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
The time complexity for creating new cats is constant since it does not depend on the size of the array (size of the storage).

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
The time complexity for the getAllCatsFor function is linear because it depends on the size of the array, and it loops through every Kitty in the array to find the cats the owner has. (Loops through enumerable storage and the bigger the array, the more gas it costs to call this function).

3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
Initially, I tried to implement this by using a mapping-only solution, like the previous assignment on Data Storage Patterns, to allow the time complexity of these functions to be constant. For this I needed to add arguments in the Kitty struct, which I think would cause more harm than good since the more kitties there are, that extra argument will consume a lot of space, so I tried using an array solution which is my final solution in the contract.

pragma solidity ^0.8.0;

contract Kittycontract {

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

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

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

    Kitty[] kitties;

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

    function balanceOf(address _owner) external view returns (uint256 balance){
        return catsOwned[_owner].length; //to know where his cats are located in the catsOwned mapping
    }

    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 catsOwned[_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); // used address(0) because it's created from nothing

        return newKittenId;

    }

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

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

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

        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }
    
/*  This requires additional argument (catPointer) in Kitty Struct - try an array solution instead 
    function removeCat(address _owner, uint256 _tokenId, uint _catPointer) internal returns(bool success)
        require(catsOwned[owner]._catPointer == true);
        uint256 catToRemove = catsOwned[_owner]._tokenId; // owner's cat to delete
        uint256 catToMove   = catsOwned[catsOwned[_owner].length-1]; // cat of the owner at the end of the list
        
    // place the cat to be removed at the end of owner's list, switch the last cat's place with previous place of cat to remove
        catsOwned[catToRemove] = catToMove;
        catsOwned[_owner]._tokenId = catToRemove; 
        catsOwned[_owner].pop(); // remove owner's last cat
        return true;
    }
*/

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

}

For this solution, the getAllCatsFor function is now constant and which is the goal of the assignment. It is constant because the Cats’ ID’s are now stored in an array for every owner, which is based on a mapping from address to the owner array. This makes the time complexity of calling the function constant.

To allow this to happen, another function is created removeCat which has a linear time complexity, although this uses less storage than the previous linear getAllCatsFor function. This is the downside to the solution.