Assignment - ERC721

[Mildo]

Hello Team:
What is the time complexity of creating new cats? (constant or linear w nr of cats).
Constant
What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
Linear as it loops over the amount of cats

// SPDX-License-Identifier: UNLICENSED
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[]) public ownershipTokenList;

    

    function balanceOf(address owner) external view returns (uint256 balance){
        uint countList = ownershipTokenList[owner].length-1;
        return countList;
    }

    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), "Destination should not be 0x");
        require(_to != address(this), "Destination should not be the same as contract owner");
        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[](ownershipTokenList[_owner].length);
        uint counter = 0;
        for (uint i = 0; i < kitties.length; i++) {
            if (kittyIndexToOwner[i] == _owner) {
                result[counter] = i;
                counter++;
            }
        }
        assert(result.length == ownershipTokenList[_owner].length);
        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 {
        ownershipTokenList[_to].push(_tokenId);
        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            uint previousSize = ownershipTokenList[_from].length;
            bool found = false;
            for (uint i=0 ; i < ownershipTokenList[_from].length; i++){
                if (ownershipTokenList[_from][i] == _tokenId){
                    ownershipTokenList[_from][i] = ownershipTokenList[_from][previousSize - 1];
                    found = true;
                }
            }
            if (found){
                ownershipTokenList[_from].pop();
            }
            assert(ownershipTokenList[_from].length == previousSize - 1);
        }

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

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

}

[EMarie1571]

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

The time complexity is constant(O(1)) because the function will execute the same no matter the input. Hence, if we exclude the first creation, the gas cost will be the same for all entries. There were 8 cats created.

What is the time complexity of the getAllCatsFor function?

The function’s execution time depends on the number of cats it has to fetch so the time complexity will be a linear one. The reason for this is the iteration inside the function because it has to look for all the NFTs belonging to that address so the time complexity will be O(n). The less NFT’s they have, the quicker it will take for the data to be fetched.

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’ve implemented a mapping function that would hold an array with all the cat id an owner has and return it into the external view instead of just looping through the entire temporary array as it was before. This will save up a lot of gas but still is not constant as now a second function has to be implemented to remove the index of the cat once the transfer is made which will be of linear complexity as it performs an iteration-bringing us to square one again. So, even if we eliminated a good portion of the gas cost, the constant complexity for the getAllCatsFor() function will still be a linear one.

Kittycontract.sol

pragma solidity ^0.8.0;

contract Kittycontract {

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

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

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

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
    mapping(address => uint[]) public ownerToKitties;
    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){
        return ownerToKitties[_owner];
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

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

        uint256 newKittenId = kitties.length - 1;
         
        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);

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

        return newKittenId;

    }

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

        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            ownershipTokenCount[_from]--;
            removeCat(_from, _tokenId);
           
        }
        ownerToKitties[_to].push(_tokenId);
        emit Transfer(_from, _to, _tokenId);
    }

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

}

[Hudsen]

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 since there is just a new struct being pushed into an array each time a cat is created.
2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats)
The time to run the function increases linearly with the number of cats since it has to cycle through the entire kitties array and the array increases in length as more cats are 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.
I’ve implemented a mapping of an address that points to an array. The array holds all the ids of the tokens that the address owns. This gets rid of the increasing time to find which cats you own as the supply goes up but it also increases the amount of storage in the contract. It also makes transfers more expensive since you have to delete the cat id out of the array that keeps track of which token IDs you hold.

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

    

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

        kittyIndexToOwner[_tokenId] = _to;

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

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

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

    function _removeCatId(address _removeFrom, uint256 _idToRemove) internal {
        for(uint i = 0; i <= ownedTokenIds[_removeFrom].length - 1; i++) {
            if(ownedTokenIds[_removeFrom][i] == _idToRemove) {
                ownedTokenIds[_removeFrom][i] = ownedTokenIds[_removeFrom][ownedTokenIds[_removeFrom].length - 1];
                ownedTokenIds[_removeFrom].pop();
            }
        }
    }

}

[A_Olson]

1. The _createKitty() function is constant since it simply adds to the array. The length of the array has no effect on the input size of this function. This allows _createKitty() to execute at a constant speed every time it is executed.

2. getAllCatsFor() would be linear. Since this function runs a loop, the input size becomes dependent on the size of the array. As the smart contract grows, getAllCatsFor() will have to process more and more kitties, making it slower over time (and linear).

3. It works to store Uint newKittenId in mapping when a new kitten is created. The mapping will build an array for each [msg.sender], and every newKittenId will be stored in the Array. Then getAllCatsFor() will return that mapping when called, giving each user their array of ids.

mapping (address => uint256[]) ownersTokens;

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

One benefit is that getAllCatsFor() will no longer need a loop, making it more efficient to run (and constant).

The Downside is that while the function is now constant (since it doesn’t care about the size of the mapping), there is more additional storage required for the mapping than there was when using the array version of getAllCatsFor().

[eba]

What is the time complexity of creating new cats? (constant or linear w nr of cats)
It is O(1). Because, whenever a cat is created, operation uses internal information in the function and operation generates kitty’s features in constant time. By the way, I checked this function’s gas cost several times and it is always about 105007 gas consumption(Not the first one).

What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats)
As we know from “Analysis of Algorithms”, the only thing effects the algorithms time complexity is input size. In this situation, we have a range of kitties that will be outputted --> lets say “n”
“A for loop is iterate around the n size array” means we are executing the basic operation “n” times. So, time complexity will be O(n) --> It is linear.

How could the storage design be changed to make the getAllCats function constant?
If we are make getAllCats function complexity as “constant”, we should use mapping. Mappings are basically hash tables. It allows to reach values by keys with less effort(no linear gas cost with “for loops”)

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;
    
    // Remove the ownershipTokenCount mapping since we can calculate this number by the new mapping
    
    
    // map the owners address to the ids of the cats that he owns
    mapping (address => uint256[]) ownersCats;


    

    function balanceOf(address owner) external view returns (uint256 balance){
        return ownersCats[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);
    }
    
    // Part of the assignment
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        // Just return the cats in the mapping for the given caller
        cats = ownersCats[_owner];
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

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

        uint256 newKittenId = kitties.length - 1;

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

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

        return newKittenId;

    }

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

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

        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }
    
    // Removes the id of the cat from the previous owners list
    function _removeOwnership(address _owner, uint256 _tokenId) internal {
        // Loop though the owned cats of the given address
        for (uint i = 0; i < ownersCats[_owner].length; i++) {
            
            // If the cat was found
            if (ownersCats[_owner][i] == _tokenId) {
                // Replace the cat by copying the last cat to this position
                ownersCats[_owner][i] = ownersCats[_owner][ownersCats[_owner].length-1];
                
                // Remove the duplicate
                ownersCats[_owner].pop();
                
                // Return from the function to save gas since we have done all we should
                return;
            }
        }
    }

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

[Tommy121]

1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
The time complexity of creating Kitties is constant because being generation 0, we do not need to iterate or loop to source the DNA of the parents. To breed kitties I believe may be a linear process because we would need to potentially loop or iterate to find parent DNA.

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
This function and process is linear. Debugging the function I can see the opcodes and stack do a lot of work before this function completes. This for loop and if statement & the mappings take time.

I am very curious why the local results array length goes really big while I’m clicking through the opcodes and debugger. Any insights?

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.
I had a look at some of the other peoples ideas here in the forum.

[seybastiens]

1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
For every new cat, we only push it on the kitties array kitties.push(_kitty); so should be constant.

Execution costs for cats creation:
1st cat : 139207 gas : higher value because of the array creation
2nd cat : 105007 gas
3rd cat : 105007 gas
4th cat : 105019 gas
5ht cat : 105019 gas
We see that it’s constant with no increment.

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
For the getAllcatsFor function, we have a for loop that goes through each element of the kitties list -> the more cats we have the bigger the list -> the heavier the for loop. Therefore it’s won’t be constant for sure.
In order to test that, I assumed that whether an address is an owner or not, the execution cost won’t vary much relative to the impact of the kitties.length.
With 6 kitties all owned by one address, we need 44949 gas to retrieve them.
With 6 kitties none owned by the inputted address, we need 42017 gas.
Therefore, by neglecting this difference, we will add extra cats always from the same address and test the execution cost for getAllcatsFor function each time.

Execution costs for getAllcatsFor function:
With 1 kitty : 29854 gas
With 2 kitties : 32873 gas (+3019 gas)
With 3 kitties : 35892 gas (+3019 gas)
With 4 kitties : 38911 gas (+3019 gas)
With 5 kitties : 41930 gas (+3019 gas)
With 6 kitties : 44949 gas (+3019 gas)
With 7 kitties : 47968 gas (47488 gas when 1 owned by another address…shows that it’s negligible)
With 8 kitties : 50988 gas (+3020 gas)

So we see that the increment is constant and of +3019 gas therefore it’s a linear increase.

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.
I suggest having a mapping with all cats (= array) for each address and when we call that function we simply check the mapping for the desired address -> no loops and it becomes constant.

Here are the modifications done:

mapping (address => uint[]) catsList;

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

we add the following just before emitting the Birth event in the function _createKitty
catsList[_owner].push (newKittenId);

The internal _transfer function is modified as follow:

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

        kittyIndexToOwner[_tokenId] = _to;

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

        //removal of transferred cat _tokenID from the catsList[_from] and replacement to catsList[_to]
        if (_from != address(0)) {
            uint index;
            for (uint i = 0; i < catsList[_from].length; i++) {
                if (catsList[_from][i] == _tokenId){
                    index = i ;
                }
            }
            for (uint i = index; i < catsList[_from].length-1; i++) {
                catsList[_from][i] = catsList[_from][i+1];
            }
            catsList[_from].pop();


            catsList[_to].push (_tokenId);
        }

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

Benefits :

Lighter getAllCats function + it’s “constant”. The only reason the execution cost still grows is if a specific address owns more cats, but not if there are more cats total among all adresses.
No loops through allCats

Drawback :
Complexity of the _transfer function, it adds a loop (actually 2, but it’s like 1 loop split in 2). But this loop only goes through all the cats owned by a specific address which will always be much less than through allCats.

We compare the execution cost of the getAllcats function with 10 cats total splitted among 3 addresses
Before : 59725 gas / 58765 gas / 58765 gas
After : 36883 gas / 32043 gas / 32043 gas

With 21 cats total:
Before : 86556 gas / 85595 gas / 86075 gas
After : 44144 gas / 39303 gas / 41723 gas

Comparison with Filip solution:

The main difference is that when a transfer occur:

• Filip takes the LastID to replace the ID that got transferred

• I transfer the ID and then move all the ones that follow -1 in the array

[Ptodoroff]

1. The complexity of creating new cats is constant. Although we are interacting with an array, we are only pushing a value to it. Push () only appends an element to the array without the need to loop over the contract. It is an instant operation

2. The complexity of the GetAllCatsFor function is linear , because it requires longer time to execute as the array grows. It is also pretty expensive, since looping and writing are the most resource-consuming operations.

3. Here is my solution:

function getAllCatsFor(address _owner) external view returns (uint[] memory cats){ //Gets all Cats for given Address
     //New Solution:
     cats = catsOwned[_owner];

[olif14]

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

   • We already have access to all variables when creating a cat, so only O(1).

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

   • We are just looping through an array of all cats and grabbing the ones that match. So O(n) and O(1) from all the previous information. Thus, the result is O(n).

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

   • We would have to implement a 2D array with each uint mapped to an address for the index displaying the individual’s array of cats. This would allow us to grab the index with a mapping from the address, thus not needing a loop, therefore, resulting in the function being only O(1) time complexity.

[K_P]

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

It is constant, because each new cat is contained in a struct and the function pushes it to the array in the same way regardless of the amount of kitties in array.

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

The function is linear, because the more kitties added to the array, the longer amount of time it takes to loop through each kitty in the array.

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

Mapping the address in the getAllCats function to an array - mapping (address => uint256[]) catsOwned; - would make the time complexity constant. It would decrease the return time, but increase the storage demand and subsequent transaction cost.

[PsiMach]

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

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

It will increase linearly

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

In the following code, I added a mapping of owner address to an array of uint (the cats they own). The benefit is there will be no need to iterate through the entire kitty array however extra storage and the functionally to maintain it is required

pragma solidity ^0.8.13;

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=>uint[]) public ownerToKitties;
    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){
        return ownerToKitties[_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;
        ownerToKitties[_to].push(_tokenId);

        if (_from != address(0)) {
            ownerToKitties[_from][_tokenId] = ownerToKitties[_from][ownerToKitties[_from].length-1];
            ownerToKitties[_from].pop();
           // [ownerToKitties][_from].length--;
            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;
  }
}

[simfin94]

The create cats fucntion is constant, since all it i does is creat a new cat and push it to the end of the array.
The getAllCatsFor function is on the other hand is linear, since it iterates through an array, that just gets bigger and bigger

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

    

    function balanceOf(address owner) external view returns (uint256 balance){
        return ownersKitties[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;*/
        cats = ownersKitties[_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;

        ownersKitties[_to].push(_tokenId);

        if (_from != address(0)) {
            //ownersKitties[_from]--;
            removeKitty(_from, _tokenId);
        }

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

    function removeKitty(address _owner, uint _tokenId) internal returns (bool _success) {
        for(uint i = 0; i < ownersKitties[_owner].length; i++) {
            if(ownersKitties[_owner][i] == _tokenId) {
                ownersKitties[_owner][i] = ownersKitties[_owner][ownersKitties[_owner].length-1];
                ownersKitties[_owner].pop();
                return true;
            }
        }
    }

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

Here I’ve implemented the code to make getAllCatFor constant, but then had to introduce a new linear function, removeKittties. But it’s not as linear as getAllCatsFor was previously. It still gotta iterate through an array, but it depends on the if condition if the for loop goes fully through, and it only has to do it once.

[cyl2chan]

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

Total = t(line 72 + … + line 94)

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

Total = t(line 56 + line 57 + line 64) + kitties.length[Math.max[t(line 60)+t(line 61)]]

Total = t(uint[] memory result = new uint;

• uint counter = 0;

• return result;) + kitties.length[Math.max[t(result[counter] = i;)+t(counter++;)]]

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.

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

Pro:

Save gas

Cons:

Can’t use any blockchain data, because constants are defined at compiled time

[spoonage]

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

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

3. How could the storage design be changed to make the getAllCats function constant?
   Change it to use a mapped array.

Code:

pragma solidity ^0.8.0;

contract Kittycontract {

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

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

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

    Kitty[] kitties;

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

    mapping (address => uint[]) ownedCats;  //maps an owners address to an array of cat index values

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

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

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

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

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        return ownedCats[_owner]; //returns the ownedCats array for the given 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;
        ownedCats[_to].push(_tokenId);  //adds cat tokenID to the mapped array

        if (_from != address(0)) {
            ownershipTokenCount[_from]--;
            deleteKitty(_from, _tokenId); //call the delete function
        }

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

    function deleteKitty (address _from, uint _tokenId) internal returns(bool success){
        uint strayCat = ownedCats[_from][ownedCats[_from].length-1]; //saving last entry in ownedcats array for given owner
        for (uint i = 0; i < ownedCats[_from].length; i++) { //search through the array
            if (ownedCats[_from][i] == _tokenId) { //find matching tokenID
                ownedCats[_from][i] = strayCat; //overwrite tokenID with last entry in array
                ownedCats[_from].pop(); //delete last entry in array
            }
        }
        return true;    
    }

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

}

Cons
Shifts the linear complexity to the transfer process.

Pros
Greatly simplifies the get all function to simply returning an array.
Simple to add IDs to the array.
Diminishes the scale of linear complexity.

[tome]

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

    function removeCatFromOwner(uint _catID, address _owner) public {
        for(uint i=0; i<ownersCatsDetailedList[_owner].length; i++){
            if(ownersCatsDetailedList[_owner][i]==_catID){
                ownersCatsDetailedList[_owner][i]=ownersCatsDetailedList[_owner][ownersCatsDetailedList[_owner].length-1];
                ownersCatsDetailedList[_owner].pop();
            }
        }
    }
    function addCatToOwner(uint _catID, address _owner) public {
        ownersCatsDetailedList[_owner].push(_catID);
    }

    

    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);
        addCatToOwner(_tokenId, _to);
        removeCatFromOwner(_tokenId, msg.sender);
    }
    
    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 getAllCats(address _owner) public view returns(uint[] memory cats){
        cats=ownersCatsDetailedList[_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);

        ownersCatsDetailedList[_owner].push(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;
  }

}

[mcgrane5]

wow super anwser man. this is one of the most detailed that ive seen. you really did a great analysisi here. theres actually a video that pooped into my head when reading your post that i though tyou might like. its still around the “gas optimisation” topic, the guy shows some clever ways where you can save on gas so its worth the watch
https://www.youtube.com/watch?v=4r20M9Fr8lY
keep it up my man

[seybastiens]

amazing video thanks man. I love optimization inn general.

[JoriDev]

1. What is the time complexity of creating new cats? (constant or linear w nr of cats)
Indepently of the existing cats, you can create a new unique Kitty. Also the new kitten ID is always the end position of the array. Therefore the time complexity for creating a new cat is the same every time. It is constant.

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats)
The getAllCatsFor function is lineair, because the time of executing depends on the size of the kitties array. For every Kitty in the array you have to determine if it’s owned by the input address. Thus the bigger the array, the longer it takes to perform this process over and over again.

3. How could the storage design be changed to make the getAllCats function constant? Discuss the benefits and drawbacks of your implementation.
By putting all cats of the same owner to an array and connecting this array to the owners’ address using a mapping, we can simply search this mapping with a key (the owners’ address) and get all the cats the owner owns directly in return. Since we don’t have to loop through the kitties array but just search directly in a mapping, the time complexity of this function is now constant.

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;
    //each owner address points to an array of all the cat tokenId's this owner owns
    mapping (address => uint256[]) catsCollectionOwner;

    

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

        //add the transfered Kitty to the collection of the new owner
        catsCollectionOwner[_to].push(_tokenId);

        if (_from != address(0)) {
            ownershipTokenCount[_from]--;
            //correct the cats collection array from the previous owner
            _removeKittyFromOldOwner(_from, _tokenId);
        }

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

    function _removeKittyFromOldOwner(address _owner, uint256 _tokenId) internal {
        //get the last cat tokenId of the cat collection array of the previous owner
        uint lastTokenId = catsCollectionOwner[_owner] [catsCollectionOwner[_owner].length-1];
        for (uint i = 0; i < catsCollectionOwner[_owner].length; i++) {
            //if the transferred tokenId to be removed is found
            if (catsCollectionOwner[_owner][i] == _tokenId) {

                //replace this cat tokenId with a copy of the last TokenId of the owner's catscollection array
                catsCollectionOwner[_owner][i] = lastTokenId;
                //remove the original lastTokenId at the end of the catscollection array to avoid duplicates 
                catsCollectionOwner[_owner].pop();
            }
        }
    }

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

}

Upside
The greatest benefit of the new getAllCatsFor function is that this function on it’s own saves time and gas.

Downside
However this comes with a drawback. In order to keep the mapping, which stores the cat collection of each owner, up to date, we need extra lines of code to properly add or remove the transferred cats. But still this seems a better solution, because the additional lineair Remove Kitty function loops through an array of a single cats collection. This is less complex than looping through an array of all cats in the original getAllCatsFor function.

[ARK]

What is the time complexity of creating new cats? (constant or linear w nr of cats)It is constant, and does not change when there are more cats. Since the cat is pushed to the end of the arry, there is not an increase (or at lest not an important increase) in the amount of time used, as the list becomes longer.

What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
For this the length of the array matters (with more cats to check as the list becomes longer). Also the number of cats that are owned by 1address might affect the amount of time required.

How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
You can make an array for every address in the system, wand in the array put the id numbers. Each array object could have an owner address as a key in a mapping. This would add an object for each address, and would require additional storage.

[CipherGrind]

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

What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
linear, because it needs to search through the array for all of the cats the address would own.

How could the storage design be changed to make the getAllCats function constant?
Discuss benefits and drawbacks with your implementation.
mapping the owner address to an array of catsOwned based on gene IDs.
It would cut down time on retreiving the catsOwned by address (constant), but would search through the catsOwned array for retreiving the specific cat ID (linear).

change:
mapping (address => uint256) ownershipTokenCount;
to:
mapping (address => uint256 [ ] ) catsOwned;

change:
function getAllCatsFor()...
to:

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