Assignment - ERC721

Ethereum Smart Contract Programming 201
#104

[quote=“AdamFortuna, post:1, topic:33588”]

  • What is the time complexity of creating new cats? (constant or linear w nr of cats).
    constant as information input is not growing

  • What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    linear as information grows with growing array size

  • How could the storage design be changed to make the getAllCats function constant?
    by implementing a mapping which points to an array of tokens owned by a specific address.
    see 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(address => uint256[]) public ownerKitties;

    

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

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

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

}

Discuss benefits:
much quicker / cheaper to retrieve all tokens of an owner

and drawbacks:
but this implementation complicates transfer of tokens to other owners as we are left with an empty position possibly in the midst of the array and I can’t think of a way to resolve this.

1 Like
#105

1. What is the time complexity of creating new cats?
O(1), which is constant.

2. What is the time complexity of the getAllCatsFor function?
O(n), which is linear.

3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
To reduce the complexity of getAllCats() to O(1), I’ve used the following mapping -

mapping(address => unit[]) mykitties;

for linking owner address with an array of token Ids of kitties he has.

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

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

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

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

    function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));
        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        cats = myKitties[_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 {
        myKitties[_to].push(_tokenId);
        kittyIndexToOwner[_tokenId] = _to;
        
        if (_from != address(0)) {
            uint [] storage kittyList = myKitties[_from];
            uint len = kittyList.length;
            uint rowToDelete = 0;
            for(uint i = 0 ; i < len ; i++){
                if(kittyList[i] == _tokenId){
                    rowToDelete = i;
                    break;
                }
            }
            kittyList[rowToDelete] = kittyList[len-1];
            kittyList.pop();
            
        }

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

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

}

Pros : getAllCatsFor() now has a complexity of O(1). Since this is a view function therefore considering gas won’t do any good.

Cons : New mapping has made the transfer function slightly complex.
An array corresponding to _from needs to be iterated to delete token Id which can take complexity between O(1) and O(n).
Eventually making the view function(getAllCatsFor) less expensive and non view (transfer) more expensive.

1 Like
#106

1 - The time complexity of creating a new kitten is LOW because it push pushes the new kitten at the end of the kittenarray and assigns the new kitten token id to new owner (address).

2 - the complexity of getAllCatsfor is HIGH O(N), because its looping through the entire kittenindextoOwner to find all token ids that correspond to owner address

3 -

My idea is to do something like this:

     struct Kitty {
        uint256 genes;
        uint64 birthTime;
        uint32 mumId;
        uint32 dadId;
        uint16 generation;
    }
    
    struct myKitties {
        uint16 TokenCount;
        uint16[] KittiesOwned;
    }

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => myKitties) ownershipTokens;

By adding myKitties struct and changing the second happing we now can look up the entire of list kitties tokens owned by each owner with mapping.

This will for sure increase the size of the storage size, but not by much because most people will own just a few kitties. Plus I’ve use uint16 for both TokenCount and KittiesOwned, as its unlikely someone will own anywhere close to 65k kitties. This will reduce storage size too.

Now once can find All cats owned by a particular address by looping through ownershipTokens[_owner].KittensOwned[]. This will be much faster than looping through all the cats.

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

_createKitty() has O(1) (linear) complexity

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

getAllCatsFor() complexity is dominated by the length of the kitties array so it’s o(n) (little “o”).

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

Most obvious solution is to use:

mapping (address => uint[]) ownershipTokens instead of ownershipTokenCount. The drawback is that this would cause a lot more data to be stored on the blockchain. You can save space by using a smaller id type than uint256.

1 Like
#108

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

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
getAllCats has to iterates through the kitties created which means the time complexity is linear .

3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
We could map the owner’s address to an array of kitties IDs he owns:

    Kitty[] kitties;
    mapping (uint256 => address) public kittyIndexToOwner;
 //   mapping (address => uint256) ownershipTokenCount;
    mapping (address => uint256[]) ownershipKities;

Benefits: That way the getAllCats function would require no iteration and the complexity would be constant and would save on gas fee.

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

        return ownershipKities[_owner];
    }

Drawbacks: The main drawback is the transfer function would need to iterate through that array to remove the transferred kitty and would become linear causing additional gas fee.

1 Like
#109

1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
Constant.
2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
Linear.
3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.

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 => uint[]) ownerToKitties; //New mapping


    function balanceOf(address owner) external view returns (uint256 balance){
        return ownerToKitties[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){
        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 {

        kittyIndexToOwner[_tokenId] = _to;
        ownerToKitties[_to].push(_tokenId); //Adding new kitty to array of ownership

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

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

    function _deleteOwnership(address _owner, uint256 _tokenId) internal {
      for(i = 0, i < ownerToKitties[_owner].length, i++) {
        uint lastId = ownerToKitties[_owner][ownerToKitties[_owner].length-1];
        if(_tokenId == ownerToKitties[_owner][i]) {
          //Looping through the ownerToKitties array until we find the tokenId we want to remove.
          ownerToKitties[_owner][i] = lastId; //Overwrite that tokenId with the last tokenId from the array.
          ownerToKitties[_owner].pop(); //Delete last tokenId from array.
        }
      }
    }

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

}

By creating a mapping that stores which address owns which cats.
The benefit of this implementation is that there’s no need anymore to loop through the whole kitties array to find which kittyIDs belong to which address, because each new kitty created will be added to the array in the ownerToKitties mapping.
The drawbacks are that by creating another mapping we store more in storage, which is expensive, and that we add more complexity to the transfer function because we need a way to delete the ownership of a cat from the array in our new mapping once it is transferred.

2 Likes
#110

The time complexity of creating new cats is constant,
since you only need to push a new cat to the array.

The time complexity of the getAllCatsFor function is linear,
as it requires iterating through the entire array.

getAllCatsFor could be made constant by using a mapping from
the owner to an array of the cat indexes he owns:

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

then getAllCatsFor(address _owner) would just return the
array of kitties owned from the mapping:

return ownersKitties[_owner];

Then you also know the # kitties owned by:

ownersKitties[_owner].length;

Transferring kitties, though, would require looking through
the list of owned kitties to find the one to transfer, (but this
should be a fairly small array), and removing that kitty from
the owner’s list will add some additional complexity.

2 Likes
#111

  1. The time complexity of creating new cats is constant because the new cat is simply pushed to the tail of the Kitties array

  2. The time complexity of getAllCatsFor is linear because the getAllCatsFor function does iterate the Kitties array.

  3. To implement a getAllCats function with linear time complexity we need to do the following:

  • add a mapping ownerToKitties to keep track of the array of token ids associated to each owner address. This require
  • in getAllCatsFor simply return the value of this mapping
  • in _transfer function remember to update the ownerToKitties mapping for the former and new owner addresses.

Here are the code changes required:

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

    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        return ownerToKitties[_owner];
    }
    
    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        ownershipTokenCount[_to]++;

        kittyIndexToOwner[_tokenId] = _to;

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

           // update the araays of tokenIds associated to the old and new owner addresses
           _removeKitty(_tokenId, ownerToKitties[_from]);
           _addKitty(_tokenId, ownerToKitties[_to]);
        }
        
        // Emit the transfer event.
        emit Transfer(_from, _to, _tokenId);
    }

    function _removeKitty(uint256 _tokenId, uint256[] storage _kitties) private {
        for (uint256 i=0; i<_kitties.length; i++) {
            if (_kitties[i] == _tokenId) {
                // if the token to be removed is found replace its value with the last element of the array and pop the array/
                _kitties[i] = _kitties[_kitties.length-1];
                _kitties.pop();
            }
        }
    }
    
    function _addKitty(uint256 _tokenId, uint256[] storage _kitties) private {
       _kitties.push(_tokenId);
    }
2 Likes
#112

  1. The time complexity for createKitty function is constant, that is O(1) in terms of Big-O notation. This is because regardless of the input size the number of basic operations remains the same.

  2. The time complexity of getAllCatsFor function is linear, making the Big-O notation O(n). It is because the number of basic operations grows as the size of the array increases.

  3. To make the time complexity of the getAllCats function constant, we need to store the index of each kitty object in an array that is mapped to the address of an individual. By knowing the indexes of each kitty object, there would be no requirement for a for loop, and as a result, the time complexity becomes constant. The drawback of this implementation is that we introduce a for loop in the _transfer function. The loop iterates through the array of indexes until it finds the index of the kitty object that is being transferred. Therefore, the time complexity of the transfer function becomes linear. However, this drawback can be addressed by applying the same approach as before.

    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 => uint256[]) OwnedTokens; 

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

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

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

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

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
        cats = OwnedTokens[_owner];
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

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

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

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

        return newKittenId;

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        OwnedTokens[_to].push(_tokenId);

        kittyIndexToOwner[_tokenId] = _to;

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

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

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

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

Its constant because it just adds the kitties to the array. So it doesnt have to loop through any array, it would be the same for any number of new cats added.

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

It is linear because it would need to loop trough the kittyIndexToOwner array to match each kitty to the owner address. So it would take more time the more cats there are in the array.

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

By creating a mapping that points an address to a cat id array.

2 Likes
#115

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 as it only requires instantiating structs and adding them to an array.

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
The time complexity of the getAllCatsFor function is linear as it requires iterating overe the kitties array. The greater the numbere of elements in this array, the greater the complexity of the function.

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

Storage solution:

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[]) catsByOwnerAddress; // Add tokenId (Kitty index) to array

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

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

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

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

        _transfer(msg.sender, _to, _tokenId);
    }
    
    function getAllCatsFor(address _owner) external view returns (uint[] memory cats) {
        cats = catsByOwnerAddress[_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 {
        catsByOwnerAddress[_to].push(_tokenId);

        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            // remove tokenId_ from previous owner
            for (uint i = 0; i < catsByOwnerAddress[_from].length; i++) {
                if (catsByOwnerAddress[_from][i] == _tokenId) {
                    catsByOwnerAddress[_from][i] = catsByOwnerAddress[_from][catsByOwnerAddress[_from].length - 1];
                    catsByOwnerAddress[_from].pop();
                    return;
                }
            }
        }

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

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

}

Benefits: getAllCatsFor is now constant.

Drawbacks: _transfer function now becomes linear as we need to loop through array to remove thr transferd kitty token.

So, we have essemtially made a liner function constant and a constant function linear by replacing the ownershipTokenCount mapping. The next question to ask is which of these two functions will be called more often. It can be argued that this starage solution is more efficient since it is likely that, over time, the kitties array will be bigger than the newly created catsByOwnerAddress array.

1 Like
#116

1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
Constant, Creating new Cats is adding to the end of an Array so you don’t need to loop through the array to create a new cat.
2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
Linear with the numbers of cats. The more cats, the more data has to be retrieved.
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.

First i make a mapping from address => uint array to store all the kitties from one user in mapping.
Then when we call the function getAllCats we don’t have to loop through the array which makes this function constant in price and speed.
Ownershiptokencount is not needed anymore for this contract.
Now i’m not sure how the contract adds the kitties to this uint256[]array.
Please explain, am i missing something?

pragma solidity ^0.8.0;

contract Kittycontract {

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

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

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

    Kitty[] kitties;

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

    

    function balanceOf(address owner) external view returns (uint256 balance){
        return ownerCats[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 ownerCats[_owner];
    }
    
    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

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

        uint256 newKittenId = kitties.length - 1;

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

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

        return newKittenId;

    }

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

        kittyIndexToOwner[_tokenId] = _to;

    

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

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

}
//© 2021 GitHub, Inc.
//Terms
//Privacy
//S
1 Like
#117

:one: 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. As the number of cats increases in the kitties array, the creating of each new cat remains the same, and each new cat is simply pushed onto the end of the array.

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

Considering the getAllCatsFor function needs to loop through the entire kitties array, the time complexity for the function grows linearly with each new cat created.

In an alternative world If each address was able to own only one Kitty, we could map the owners’ addresses to the Kitty ID and in this sense the time complexity would be constant.
But because the function requires us to loop through the full array, it will be more arduous with each Kitty created.

:three: 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.

There is another way to get around this by adding an array for each owners kitties.
So therefore for every inbound transaction of kitties, we push this kitty to the owners ownersKitties array.
We can then have a mapping of an address to this uint catID array, which will greatly reduce the time spent through looping to find the owners kitties; particularly if there are a vast amount of kitties in circulation.

So the following actions need to be taken:

Add the ownersKitties mapping for the address to an array of kitty ID’s.

    mapping (address => uint[]) ownersKitties;

Update the transfer function to push the _tokenId to the owners array:

   function transfer(address _to,uint256 _tokenId) external
    {
        require(_to != address(0));
        require(_to != address(this));
        require(_owns(msg.sender, _tokenId));
        
        // Remove from old owners array
        uint256 lastId = ownersKitties[msg.sender].length-1;
        for (uint i = 0; i < ownersKitties[msg.sender].length; i++) {
            if (ownersKitties[msg.sender][i] == _tokenId) {
                ownersKitties[msg.sender][i] = lastId;
                ownersKitties[msg.sender].pop();
            }
        }
        _transfer(msg.sender, _to, _tokenId);
        // Add this push instruction
        ownersKitties[_to].push(_tokenId);
    }

And do the same for the _transfer function:

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

        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            ownershipTokenCount[_from]--;
        }
        
        // Remove from old owners array
        uint256 lastId = ownersKitties[_from].length-1;
        for (uint i = 0; i < ownersKitties[_from].length; i++) {
            if (ownersKitties[_from][i] == _tokenId) {
                ownersKitties[_from][i] = lastId;
                ownersKitties[_from].pop();
            }
        }
        
        // Push Kitty to new owner
        ownersKitties[_to].push(_tokenId);

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

Add Gen0 kitties to the creators address:

(I get a warning here saying Unreachable Code… Think is has something to do with msg.sender, but would love some feedback here! :slightly_smiling_face:)

    function createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
        // Push Gen0 kitty to creator
        ownersKitties[msg.sender].push(0);
    }

For the createKitty function, we have to push the new kitty to the owners address too:

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;
        
        // Push the new kitten to the owner.
        ownersKitties[_owner].push(newKittenId);

        emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);
        _transfer(address(0), _owner, newKittenId);
        return newKittenId;

    }

And now the Main Event; the getAllCatsFor function could be as simple as:

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

This would significantly reduce the time complexity of the getAllCatsFor function. Mapping is far more efficient than looping through an array, and it would make the time complexity for the getCatsForAll functionconstant.
It does have huge downsides however, particularly in storage.

This addition would mean that each address requires storage for their own array of each kitty they own. This storage is expensive on the VM.

So in effect, this alternative solution is arguably more expensive and less efficient in aggregate than the original contract.

1 Like
#118

Greetings and I wish you a fantastic day !

Answers:

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

I’m guessing constant because the _CreateKitty function does not change over time, it may only be executed more frequently as time goes on ?

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

Linear with number of cats. The more cats there are, the longer it takes to iterate through them ?

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.

Ooof, store it off-chain ? Since it says “implement your idea” I guess there is another method and I need to study storage some more :smiley:

1 Like
#119

  1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
    The time complexity of creating new cats seems to be constant. The first transaction might take longer due to the initialization of the array, however, every transaction thereafter is just pushing the new cat to the existing array and should therefore consist of the same time complexity.

  2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
    The time complexity of the getAllCatsFor function should be linear, due to the fact that for every new cat generated, the longer it takes to cycle through the array to find cats matching the owner.

  3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
    The storage design could be changed to where whenever a new cat is added, the ownership is declared via a mapping(uint catID => address owner ). When the mapping is updated, it should trigger the update of a separate mapping (address owner, uint[] catIDs). The benefit of this is to conserve time/gas when searching for the catIDs a single address owns by having a direct lookup, however, the downside is that it introduces a separate mapping that requires a lot of code to upkeep after each transfer of cat or generation of new cat.

1 Like
#120

  1. It’s constant time O(1) because the function to create a new cat does not have to loop or iterate over a dataset.

  2. It’s linear time O(N) because the amount of time to get all of the cats is dependent on the number of cats within the kitties[ ].

  3. Create a mapping that has an address as a key and an array of kitties that the address owns as the mapping’s value to replace the mapping(address => uint) ownershipTokenCount. The benefit is that the number of cats is still accessible from that mapping while being able to retrieve all of the cats that the address owns. The downside is that it will cost more storage as the address owns more cats.

1 Like
#122

If you return before the action then that action is not reachable / executed… so this is better:

 function createKittyGen0(uint256 _genes) public returns (uint256) {
        // Push Gen0 kitty to creator
        ownersKitties[msg.sender].push(0);

        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

And in your transfer() the block:

       // Remove from old owners array
        uint256 lastId = ownersKitties[msg.sender].length-1;
        for (uint i = 0; i < ownersKitties[msg.sender].length; i++) {
            if (ownersKitties[msg.sender][i] == _tokenId) {
                ownersKitties[msg.sender][i] = lastId;
                ownersKitties[msg.sender].pop();
            }
        }

is also done in the _transfer() which is called from fransfer(), so seems to be done twice and no sense in the _transfer() anymore … :wink: . So you can remove it from the transfer() function.

Same for:

 ownersKitties[_to].push(_tokenId);

in combination with _transfer() execution the _tokenId is added twice to the array, so only necessary in the _transfer() function.

#123

My solutions:

.1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
=> Constant: Via _createKitty() => Just fill the struct and add it to the array of kitties. Then transfer (assign) kittenId to owner, all without looping through an array.

.2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
=> Linear: it loops through the kitties array, which is equal to nr of kitties known, increasing when a kitty is added.

.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
=>

pragma solidity ^0.8.0;

contract Kittycontract {

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

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

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

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => uint256[]) public kittiesOfOwner; // address to array of kittyIds

    function balanceOf(address owner) external view returns (uint256 balance){
        return kittiesOfOwner[owner].length; // each item is 1 kitty, so nr of items is nr of kitties
    }

    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 kittiesOfOwner[_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 {
        kittiesOfOwner[_to].push(_tokenId); // add tokenId to new owner array

        kittyIndexToOwner[_tokenId] = _to;

        if (_from != address(0)) {
            _removeKitty(_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 _removeKitty(address _owner, uint256 _tokenId) internal {
        for(uint256 n = 0; n < kittyIndexToOwner[_owner].length; ++n){
            if(kittyIndexToOwner[_owner][n] == _tokenId){
                kittyIndexToOwner[_owner][n] = kittyIndexToOwner[_owner][kittyIndexToOwner[_owner].length-1]; // move last to item to be removed
                kittyIndexToOwner[_owner].pop(); // remove last (copied) item
                return;
            }
        }
    }
}
2 Likes
#124

  1. The time complexity of creating new cats is constant. This is because the function always carries out the same operations, creating a new instance of the Kitty struct and adding it to the kitties array, it doesn’t matter how many elements are already in the array.

  2. The time complexity of the getAllCatsFor function is linear with the number of cats. This is because the function loops through the entire kitties array, checking the owner address of every element. Therefore if there are more cats in the array, looping through it will require more operations and take longer.

  3. We could make the getAllCats function constant by using a mapping that maps an address to an array of Kitty IDs owned by that address

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

In the _createKitty function, we need to push the ID into the owner’s array in the kittiesOwned mapping

kittiesOwned[_owner].push(newKittenId);

Then the getAllCats function can be made very simple and will be time constant, no matter how many kitties there are

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

The drawback of this method however is that we will often have to delete elements from the middle of an array if someone sells a cat. This will involve replacing the cat being sold with the last cat in the array and deleting the last element, making the transfer function more complicated and costly to execute.

1 Like
#125

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

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

This increases linearly. the more cats get added the loner the list the needs to be searched for to get the number of cats owned.

  1. My solution is simply to create a mapping that points to the an array where all the indexes is stored for a specific address:

like this :

  mapping (address => uint[]) KittiesOwned;

The in the _transfer function we change like this :

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

        kittyIndexToOwner[_tokenId] = _to;
        
   // here we add the index to the array of token indexes  that is mapped to this address
  KittiesOwned[_to].push(_tokenId); 
                                                            
  
        
        

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

}

finally we change the getAllCats Function :

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