Assignment - ERC721

[tutatenso]

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

Constant 0(1), its just a one-off exectution. the function gets called and executes without no loops etc.

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

Linear 0(n), you have to iterate through the array to find the values

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.

Its easier to get the tokenids when introducing a mapping, however, I think in general both implementations works but the mapping implementation would be more gas-efficient. if we’re looping through the array with getAllCats it would require more gas than looping through the array when we need to delete a cat.

One thing i was thinking about tho, why not just get the last kitty with:
ownedKittys[_from][i] = ownedKittys[_from].length -1

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

contract Kittycontract {

string public constant name = "TestKitties";
string public constant symbol = "TK";

event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

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

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

struct Owners {
    address owners;
    uint tokenId;
}

Kitty[] kitties;

mapping (uint256 => address) public kittyIndexToOwner;

mapping(address => uint256[]) ownedKittys;

function ownersKittys(address _addressOwner) external view returns (uint[] memory)
{
    return ownedKittys[_addressOwner];
}

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 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 {
    require(_to != address(this), "cant send to yourself");
    require(_to != address(0), "cant send to contract address");
   
    kittyIndexToOwner[_tokenId] = _to;
    ownedKittys[_to].push(_tokenId);

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

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

}

}

[empty_nutella]

1. constant, however i did notice that when i first made a new cat it cost more gas, then every other time it was the same amount.

2. linear, it increases by 3000 gas every time a new cat is added to the array.

3. this took me a while to figure out, my first solution was right on the nose, a mapping to list of uint, but gas still cost more as the list got bigger for both my version and the solution from github, so im not sure if i misunderstood the assignment because i thought it was about making the gas price consistent.

anyway i did made it the same way the solution video made, the drawbacks being that other function are now more complex and cost more gas.

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;

//make new storage for getallcats.

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

    

    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 ownerToTokenList[_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;
        ownerToTokenList[_to].push(_tokenId);

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

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


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

}

[Tony_Siu]

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? Implement your idea. Then discuss the benefits and drawbacks of your implementation and post everything in the forum.

use this instead mapping (address => uint[]) addressCatIds
It will make the insertion slower
but it will avoid iterating whole kitties array in getAllCats()

[KryptoS]

1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
   Constant time complexity. First call to add kitty to a new address has higher gas consumption. Subsequent additions to same address has constant gas consumption.

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
   Linear increase due to growth in number of cats in the owner’s array.

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.
   Use owner’s address to array of cats mapping to retrieve all cats for an address instead of searching the entire kitties array which consumes higher gas.

*Implemented the solution using mapping address to struct owners. Struct has owner’s cat count and array of cats.
*Benefits: Mapping can be used to retrieve all cats for an owner and eliminates kitties array search and thus reduces time complexity.
*Drawback of the solution: A new function is introduced to remove a catId from current owner’s array to transfer the cat to new owner.

My implementation:

// SPDX-License-Identifier: GPL-3.0

pragma solidity ^0.8.0;

contract Kittycontract {

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

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

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

    struct Owners {
        uint256 countCats;
        uint256[] ownedCats;
    }

    Kitty[] kitties;

    mapping (uint256 => address) public kittyIndexToOwner;
    mapping (address => Owners) public CatOwners;

   // mapping (address => uint256) ownershipTokenCount;

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

    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(_to != address(msg.sender));
        require(_owns(msg.sender, _tokenId));

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

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

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

        uint256 newKittenId = kitties.length - 1;

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

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

        return newKittenId;

    }

    function _transfer(address _from, address _to, uint256 _tokenId) internal {
        if (_from != address(0)) {
            //ownershipTokenCount[_from]--; 
            CatOwners[_from].countCats--; //reduce owner's token count
        }
        
        if (_from != address(0)) {
            _removeKittyCurrentOwner(_tokenId, _from); //remove tokenId from current owner's array
        }

        kittyIndexToOwner[_tokenId] = _to;
    
        //ownershipTokenCount[_to]++;
        CatOwners[_to].countCats++; //increase new owner's token count

        CatOwners[_to].ownedCats.push(_tokenId); //insert tokenId into new owner's array

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

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

    function _removeKittyCurrentOwner(uint256 _catId, address _currentOwner) internal returns (bool success){

        uint lastCatIndex = CatOwners[_currentOwner].ownedCats.length - 1;
         
        //find catId in the Owner's array
        for (uint i=0; i < CatOwners[_currentOwner].countCats; i++) {
            if (CatOwners[_currentOwner].ownedCats[i] == _catId) {
                //remove catId from array
                CatOwners[_currentOwner].ownedCats[i] = CatOwners[_currentOwner].ownedCats[lastCatIndex];
                CatOwners[_currentOwner].ownedCats.pop();
                return success;
            }
        }
    }
}

[paradox]

1. constant
2. linear with no. of cats
3. If the contract had a mapping from owner address to array of catIDs then the function could simply look up the address and return the array. The disadvantage would be that it would take up more permanent storage

[decrypter]

1. Constant
2. linear w nr of cats
3. By using a mapping to an array that stores all kittens of per owner. The drawback is that the array must be maintained by the _transfer function and the extra storage required.

[lawyer]

Questions:

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

If only pushing/appending new NFTs into ‘kitties’ array (plus triggering _transfer function and Birth event) as this code shows, then constant. This also assumes the _createKitty function inputs are mainly user-supplied, rather than having other (not shown) functions loop through the ‘kitties’ array to identify/supply them.

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

Linear w nr of cats, as in this code it is looping through the entire kittyIndexToOwner mapping to find all instances of the supplied owner’s address.

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.

A possibility is to add two new mappings: 1) a double mapping (kittiesList) to list all NFTs owned by a single address; 2) a new counter (litterSize) to support the double mapping (see following code for their implementation.)

Benefits: more efficient querying/identification of all NFTs owned by a single address.
Drawbacks: greater storage requirements (two additional mappings, one of them a double) and slightly more complicated code.

Code:

pragma solidity 0.8.0;
//addition: import SafeMath
import "./safemath.sol";

contract Kittycontract {

//addition: SafeMath declaration
    using SafeMath for uint256;

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

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

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

    Kitty[] kitties;

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

//addition: double mapping that lists all kitties associated with an address
    mapping (address =>mapping(uint256 => uint256)) internal kittiesList;
//addition: new count mapping that supports list double mapping in edited functions below, see getAllCatsFor() and _transfer()
    mapping (address => uint256) internal litterSize;

//addition: new functions to query kittiesList and litterSize mapping values for testing purposes
    function viewCat(uint256 _catId) public view returns (Kitty[] memory cat){
        Kitty[] memory catDetails = new Kitty[](1);
        catDetails[0] = kitties[_catId];
        return catDetails;
    }
    function getLitterSize(address _owner) external view returns (uint256 cats){
        return litterSize[_owner];
    }

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

//addition: new function that queries list double mapping to output all kitties associated with an address; in front-end code, zero values could be ignored and the remaining tokenIds with associated data from main NTF Struct array 'kitties' passed on for display
    function getAllCatsFor(address _owner) external view returns (uint[] memory litterIndexValues){
    	uint[] memory result = new uint[](litterSize[_owner]);
    	for (uint i = 0; i < litterSize[_owner]; i++) {
            result[i] = kittiesList[_owner][i];
    	}
        return result;
    }
    
    //previous function code commented out
    //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 createKittyGen0(uint256 _genes) public returns (uint256) {
        return _createKitty(0, 0, 0, _genes, msg.sender);
    }

//addition: changed to public for testing purposes
    function _createKitty(
        uint256 _mumId,
        uint256 _dadId,
        uint256 _generation,
        uint256 _genes,
        address _owner
    ) public 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;

    }

//addition: changed from "internal" to "public" and to payable for testing purposes
    function _transfer(address _from, address _to, uint256 _tokenId) public payable {
        ownershipTokenCount[_to]++;

        kittyIndexToOwner[_tokenId] = _to;
        
//addition: populate new double mapping with kitty transfer data and increase litterSize mapping count by one
        kittiesList[_to][litterSize[_to]] = _tokenId;
        litterSize[_to] = litterSize[_to].add(1);

        if (_from != address(0)) {
            ownershipTokenCount[_from]--;
//addition: a for loop with if/else that deletes the transferred kitty from the owner's list in the new 'kittiesList' double mapping
            for (uint256 i = 0; i < litterSize[_from]; i++) {
            	if(kittiesList[_from][i] == _tokenId){
			        kittiesList[_from][i] = 0;
		        }
		        else{}
            }
        }

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

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

}

[nqb]

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

litties.push(_kitty) -> new cat created, and added to the kitties Array. Constant time independed on number of cats.

 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;

    }

2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
   since kitties is an array, the more kitties, more bigger and larger array, more time and more gas need to be consume to go through index 0 until index.length! it’s Linnear time consuming.

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

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.

we can create an addition mapping where one address will be having the opportunities to have info of several ids:

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

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