ERC721 - Assignment (Answers)
mapping (address => uint256[]) ownerKitties;
function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
return ownerKitties[_owner];
I think it is constant as it adds (push) the entry at the end of the array.
Linear w nr of cats. The more the cats, the more elements to iterate.
We should redesign so as the iteration on the array is not needed. We can add a mapping of each address (key) to an additional array containing the cats that each address ownes.
Then we return directly that array on the mapping on the getAllCats using the address (key). However we need to maintain that array, so we need to change the corresponding entry of the array every time a kitty is created or transferred.
This is how I would fix the issue regarding time complexity in getAllCats function:
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[]) kittiesOfOwner; // new mapping.
function balanceOf(address owner) external view returns (uint256 balance){
return kittiesOfOwner[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);
}
// FIXED //
function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
return kittiesOfOwner[_owner];
/* uint[] memory result = new uint[](ownershipTokenCount[_owner]);
uint counter = 0;
for (uint i = 0; i < kitties.length; i++) {
if (kittyIndexToOwner[i] == _owner) {
result[counter] = i;
counter++;
}
}
return result;
*/
}
function createKittyGen0(uint256 _genes) public returns (uint256) {
return _createKitty(0, 0, 0, _genes, msg.sender);
}
function _createKitty(
uint256 _mumId,
uint256 _dadId,
uint256 _generation,
uint256 _genes,
address _owner
) private returns (uint256) {
Kitty memory _kitty = Kitty({
genes: _genes,
birthTime: uint64(block.timestamp),
mumId: uint32(_mumId),
dadId: uint32(_dadId),
generation: uint16(_generation)
});
kitties.push(_kitty);
uint256 newKittenId = kitties.length - 1;
emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);
_transfer(address(0), _owner, newKittenId);
return newKittenId;
}
function _transfer(address _from, address _to, uint256 _tokenId) internal {
//ownershipTokenCount[_to]++;
kittyIndexToOwner[_tokenId] = _to;
kittiesOfOwner[_to].push(_tokenId);
if (_from != address(0)) {
// ownershipTokenCount[_from]--;
uint[] memory tokensFrom = kittiesOfOwner[_from];
delete kittiesOfOwner[_from];
for(uint8 l=0; l<tokensFrom.length; l++){
if(tokensFrom[l] != _tokenId){
kittiesOfOwner[_from].push(tokensFrom[l]);
}
}
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
mapping (address => uint256[]) addressToIDs;
Added the following line to the _transfer function to add to the array when a new kitty is created
addressToIDs[_to].push(_tokenId);
Here is the function to retrieve the Kitty IDs for an address
function getCatsForAddress(address _address) public view returns (uint[] memory) {
return addressToIDs[_address];
}
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[]) 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 transferKitty(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 ownerCats[_owner];
}
function getCatIndexOwnerArray(address _owner, uint256 _tokenId) internal returns(uint256 index){
for (uint i = 0; i < ownerCats[_owner].length; i++){
if (ownerCats[_owner][i] == _tokenId) {
return i;
}
}
}
function deleteFromOwnerArray(address _owner, uint _tokenId) internal {
uint toRemove = getCatIndexOwnerArray(_owner, _tokenId);
ownerCats[_owner][toRemove] = ownerCats[_owner][ownerCats[_owner].length - 1];
delete ownerCats[_owner][ownerCats[_owner].length - 1];
}
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 {
ownerCats[_to].push(_tokenId);
kittyIndexToOwner[_tokenId] = _to;
if (_from != address(0)) {
deleteFromOwnerArray(_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;
}
}
Pros: faster look up
Cons: transfer function more complex and expensive in my implementation for removing kitty from old owner array.
What is the time complexity of creating new cats? (constant or linear w nr of cats).
constant - no looping required to create a cat, just push on to the end of the array.
What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
linear (or worse) with number of cats - the looping through will take longer as the array of cats gets larger - more cats to loop through to get to the right result.
How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
Here is my 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) ownershipTokenCount;
mapping (address => uint[]) public kittyCollections;
mapping (uint => uint) public positionInArray;
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 kittyCollections[_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]++;
kittyCollections[_to].push(_tokenId);
kittyIndexToOwner[_tokenId] = _to;
if (_from != address(0)) {
ownershipTokenCount[_from]--;
removeKitty(_from, positionInArray[_tokenId]);
}
positionInArray[_tokenId] = kittyCollections[_to].length-1; //reset the position of the kitty in the collection
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function removeKitty(address _from, uint256 _position) internal {
kittyCollections[_from][_position] = kittyCollections[_from][kittyCollections[_from].length-1]; //swap in cat from end of positionInArray
//delete kittyCollections[_from][kittyCollections[_from].length-1]; //delete the entry at end of array
kittyCollections[_from].pop(); //remove last element of array and decrease length of array by 1
positionInArray[kittyCollections[_from][_position]] = _position; //update the moved cat's index
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
Iâve added two extra mappings, one which maps from any given ownerâs address to the array of cats that he owns (an array of cat IDâs), and the other mapping from any given cat ID, to the position that that cat occupies in their ownerâs array of cats. This means we can return any owners array of cats without using a for loop, thus saving considerable gas and making that function constant.
The drawback here is that by creating two additional mappings we are taking up additional storage space. I have not yet calculated how much additional gas.
My solution is to create a new global mapping with an adress pointing to an array of cat id:s.
mapping (address => uint256[]) kittyOwnership;
Then the getAllCatsFor function gets a lot simpler (it just returns the array in the mapping) and the complexity is constant O(1):
function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
return kittyOwnership[_owner];
}
And then a new cat needs to be added to the array in the mapping when created. The downside with this solution is that we have to create another global variable in storage, which is costly (but constant complexity). The good thing is that we donât have to iterate through an array to find all kittens belonging to an owner, which is of linear complexity.
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;
//Add new kitten to mapping.
kittyOwnership[_owner].push(newKittenId);
emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);
_transfer(address(0), _owner, newKittenId);
return newKittenId;
}
My first attempt was wrong. I totally didnât think about the transfer function. So hereâs my updated version:
These are good:
mapping (address => uint256[]) kittyOwnership;
function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
return kittyOwnership[_owner];
}
Then the _transfer function to which I moved the push to the ownership array. But I think the push to the ownership array should come after the removal. Otherwise, after the push, but before removal, the system will be in a state where the same kitten has two owners. The _transfer function calls _removeTokenFromOwner to handle the removal.
However, the complexity now is back to square one, since we also introduce a new for loop.
function _removeTokenFromOwner(address _owner, uint256 _catID) internal {
uint256 index = kittyOwnership[_owner].length;
uint256 lastId = kittyOwnership[_owner][index -1];
for(uint256 i = 0; i < index; i++) {
if(kittyOwnership[_owner][i] == _catID) {
kittyOwnership[_owner][i] = lastId;
kittyOwnership[_owner].pop();
}
}
}
function _transfer(address _from, address _to, uint256 _tokenId) internal {
ownershipTokenCount[_to]++;
kittyIndexToOwner[_tokenId] = _to;
if (_from != address(0)) {
ownershipTokenCount[_from]--;
_removeTokenFromOwner(_from, _tokenId);
}
kittyOwnership[_to].push(_tokenId);
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
What is the time complexity of creating new cats? (constant or linear w nr of cats).
This would be constant as the method of creating cats doesnt really change.
What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
This would be linear as the number of cats created increases, so does the array to store the cats.
How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
Implement a mapping array that holds all cats owned by an address. You would still need a loop because when you transfer you need to remove the cat from the old address and add it to the new one. The loop however would be over a much smaller array so it would be faster.
Benefit is faster execution time as the entire project grows. Drawback is that you add more complexity to the contract and you add complexity to items that cost gas such as storage and functions that write to the blockchain. Whereas the original contract put all the heavy computation into the view function which doesnt cost any gas (assuming not called by an external contract).
Here is my code, organized with modified functions first, followed by original functions commented out, and then the miscellaneous functions. There is no way to test this code in its current form, so this may or may not work:
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
);
//Added the tokenId uint to each Kitty;
struct Kitty {
uint256 genes;
uint64 birthTime;
uint32 mumId;
uint32 dadId;
uint16 generation;
uint256 tokenId;
}
Kitty[] kitties;
mapping (uint256 => address) public kittyIndexToOwner;
mapping (address => uint256) ownershipTokenCount;
//Mapping for each address's array of owned cats;
mapping(address => Kitty[]) allCatsOwnedBy;
//Simplified function for returning list of owned cats:
function getAllCatsFor(address _owner) external view returns (Kitty[] memory cats) {
return allCatsOwnedBy[_owner];
}
//This is where things get messy.
function _transfer(address _from, address _to, uint256 _tokenId) internal {
require (_from != address(0));
ownershipTokenCount[_to]++;
ownershipTokenCount[_from]--;
kittyIndexToOwner[_tokenId] = _to;
//Add Kitty to new owner's list of owned Kittys:
allCatsOwnedBy[_to].push(kitties[_tokenId]);
//Delete Kitty from previous owner's list of owned Kittys:
for(uint i = 0; i < allCatsOwnedBy[_from].length; i++) {
allCatsOwnedBy[_from][i];
if (allCatsOwnedBy[_from][i].tokenId == _tokenId) {
Kitty memory kittyToMove = allCatsOwnedBy[_from][allCatsOwnedBy[_from].length - 1];
allCatsOwnedBy[_from][i] = kittyToMove;
allCatsOwnedBy[_from].pop();
}
}
emit Transfer(_from, _to, _tokenId);
}
//Updated to include tokenId as a property of the new Kitty struct;
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),
tokenId: uint256(kitties.length - 1)
});
kitties.push(_kitty);
uint256 newKittenId = kitties.length - 1;
emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);
_transfer(address(0), _owner, newKittenId);
return newKittenId;
}
//Original _transfer function;
/*
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);
}
*/
//Oirignal getAllCatsFar function;
/*
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 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 createKittyGen0(uint256 _genes) public returns (uint256) {
return _createKitty(0, 0, 0, _genes, msg.sender);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
kitties.push(_kitty);
_transfer(address(0), _owner, newKittenId);
for (uint i = 0; i < kitties.length; i++) {
if (kittyIndexToOwner[i] == _owner) {
result[counter] = i;
counter++;
}
}
In order to make time complexity of getAllCats function constant, ownershipTokenCount should store the id of tokens that the owner owns, not the amount of token.
Benefit:
Drawback:
Code:
pragma solidity 0.8.3;
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[]) ownerToKittyIndexes;
function balanceOf(address owner) external view returns (uint256 balance){
return ownerToKittyIndexes[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 = ownerToKittyIndexes[_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 {
ownerToKittyIndexes[_to].push(_tokenId);
kittyIndexToOwner[_tokenId] = _to;
if (_from != address(0)) {
uint n = ownerToKittyIndexes[_from].length;
for(uint i=0;i<n;i++){
if(ownerToKittyIndexes[_from][i]==_tokenId){
uint tmp = ownerToKittyIndexes[_from][n-1];
ownerToKittyIndexes[_from][i] = tmp;
ownerToKittyIndexes[_from].pop();
break;
}
}
}
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
First of all I just want to say that this was kinda hard man, it really took some studying and the real issue I had was trying to grasp a concept on my own that you guys havnt specifically mentioned before but I guess that was to make sure we go back and do actual research. Going back to the data structure section I see that basically time complexity is associated with gas price because unless the function is constant the operations will be repeated as the algorithm carries out its operation.
1,The create cat function is constant because all its doing is creating 1 cat each time you call it. O(1)
2, Getting all the cats is linear because depending on the length of the array it will have to repeat itself. O(N)
Hello Everyone!
Creating new cats is constant with the number of cats.
As we are looping through to the cats it is going to be linear with the growing of the number of cats.
Here is what I have changed.
pragma solidity ^0.8.0;
pragma abicoder v2;
contract Kittycontract {
string public constant name = "TestKitties";
string public constant symbol = "TK";
event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);
event Birth(
address owner,
uint256 kittenId,
uint256 mumId,
uint256 dadId,
uint256 genes
);
struct Kitty {
uint256 genes;
uint64 birthTime;
uint32 mumId;
uint32 dadId;
uint16 generation;
}
Kitty[] kitties;
mapping (address => uint256[]) ownershipTokenbyKitty;
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 kittenIDs){
return ownershipTokenbyKitty[_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]++; //This add +1 to the address which owns the catID, because it's adding the kitty id's together(how many we have all in all), not listing them one by one
kittyIndexToOwner[_tokenId] = _to; // This means the token ID for the kitty has transferred to the _to address
ownershipTokenbyKitty[_to].push(_tokenId); // It seems we can use more mapping in a row
if (_from != address(0)) {
ownershipTokenCount[_from]--; //
deleteToken(_from, _tokenId);
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function deleteToken(address owner, uint256 tokenToDelete) internal {
uint lastId = ownershipTokenbyKitty[owner][ownershipTokenbyKitty[owner].length-1]; // we access to the last member of the array here,
for ( uint i = 0; i < ownershipTokenbyKitty[owner].length; i++){
if(ownershipTokenbyKitty[owner][i] == tokenToDelete){
ownershipTokenbyKitty[owner][i] = lastId;
ownershipTokenbyKitty[owner].pop;
}
}
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
So I have created a new mapping as the following: mapping (address => uint[]). This has solved the issue for the time complexity in getAllCatsFor function as it is now constant due to the mapping, but it is also created some new issues, such as we had to create a new function (deleteToken) where I also created a for loop. Of course the new array does not contain that much element than the last one, but also when the transfer function is called, we also need to call the deleToken function again everytime, which is more Gas consuming.
Hi All 
_createKitty() function is of constant complexity because it implies just one array push and setting one mapping element.
getAllCatsFor() function contains a for loop that iterates through the whole kitty population to scan the owner. Complexity therefore increases with the total kitty supply.
Instead of scanning the whole kitty population for every call to getAllCatsFor(), it is possible to pre-build an array of owned kitties for each owner and update it whenever a kitty is transferred.
Added a new mapping kittyOwnerToIndex that associates an owner with its array of owned kitties.
This array has to be kept up-to-date with the _transfer() function.
It is easy to update ownedKitties for the recipient with a simple push().
However updating the array for the sender of the kitty is a bit more tricky because an element has to be deleted from ownedKitties. This is made possible with an additional mapping kittiesIndex that keeps track of the index of a given kitty id in ownedKitties array.
Measurements:
The table below shows getAllCatsFor() execution costs (gas).
| Total population 3 cats | Total population 10 cats | |
|---|---|---|
| Before modification | 10060, 8568 | 26994, 22141 |
| After modification | 6139, 2708 | 13980, 2708 |
The new code shows a clear improvement in performance. Calling getAllCatsFor() for an address owning zero cats is constant no matter the size of the kitty population (2708 gas for 3 and 10 cats).
Although independent of total kitty supply, getAllCatsFor() execution cost increases with the size of the kitty array being returned (unfortunately it is returned by copy, which is expensive).
Pros: better performance of getAllCatsFor(), independent of the total kitty population.
Cons: _transfer() code is more complex and a bit harder to read, additional array and mappings take more storage space,
// 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;
}
Kitty[] kitties;
struct OwnedKitties{
uint256[] ownedKitties;
mapping(uint256 => KittiesIndex) kittiesIndex;
}
struct KittiesIndex{
uint256 index;
bool exists;
}
mapping (uint256 => address) public kittyIndexToOwner;
mapping (address => OwnedKitties) kittyOwnerToIndex;
function balanceOf(address owner) external view returns (uint256 balance){
return kittyOwnerToIndex[owner].ownedKitties.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), "You do not own this token");
_transfer(msg.sender, _to, _tokenId);
}
function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
return kittyOwnerToIndex[_owner].ownedKitties;
}
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;
kittyOwnerToIndex[_to].ownedKitties.push(_tokenId);
uint256 addedTokenIndex = kittyOwnerToIndex[_to].ownedKitties.length-1;
kittyOwnerToIndex[_to].kittiesIndex[_tokenId].exists = true;
kittyOwnerToIndex[_to].kittiesIndex[_tokenId].index = addedTokenIndex;
if (_from != address(0)) {
assert(kittyOwnerToIndex[_from].kittiesIndex[_tokenId].exists == true);
//Update the kitties array
uint256 deletedTokenIndex = kittyOwnerToIndex[_from].kittiesIndex[_tokenId].index;
uint256 length = kittyOwnerToIndex[_from].ownedKitties.length;
assert(length > 0);
// Replace entry to delete with the last entry and pop the last entry off the array
kittyOwnerToIndex[_from].ownedKitties[deletedTokenIndex] = kittyOwnerToIndex[_from].ownedKitties[length-1];
kittyOwnerToIndex[_from].ownedKitties.pop();
assert(length > kittyOwnerToIndex[_from].ownedKitties.length);
kittyOwnerToIndex[_from].kittiesIndex[_tokenId].exists = false;
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
What is the time complexity of creating new cats? (constant or linear w nr of cats).
The time complexity for creating new cats is constant.
What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
The time complexity for getAllCatsFor-function is linear due to the for-loop that is needing more time to iterate longer the bigger the array gets that it needs to check.
How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
pragma solidity ^0.8.0;
contract Kittycontract {
string public constant name = "TestKitties";
string public constant symbol = "TK";
event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);
event Birth(
address owner,
uint256 kittenId,
uint256 mumId,
uint256 dadId,
uint256 genes
);
struct Kitty {
uint256 genes;
uint64 birthTime;
uint32 mumId;
uint32 dadId;
uint16 generation;
}
//Created this struct in order to keep track of what array placement it has on the owner address
struct KittyOwnerData {
address owner;
uint256 arrayPlacement;
}
Kitty[] kitties;
//Added KittyOwnerData struct to the mapping
mapping (uint256 => KittyOwnerData) public kittyIndexToOwner;
//Maps an address to an array in order to store all the owned tokens
mapping (address => uint256[]) ownerOfTokens;
//Returns the length of the array in the ownerOfTokens mapping to present how many tokens an owner has
function balanceOf(address _owner) external view returns (uint256 balance){
return ownerOfTokens[_owner].length;
}
function totalSupply() public view returns (uint) {
return kitties.length;
}
function ownerOf(uint256 _tokenId) external view returns (address){
return kittyIndexToOwner[_tokenId].owner;
}
function transfer(address _to, uint256 _tokenId) external {
require(_to != address(0));
require(_to != address(this));
require(_owns(msg.sender, _tokenId));
_transfer(msg.sender, _to, _tokenId);
}
function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
return ownerOfTokens[_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 {
if (_from != address(0)) {
//Stores the token that is in the end of the array placement of the _from address
uint256 tokenToSave = ownerOfTokens[_from][ownerOfTokens[_from].length - 1];
//The token in the actual array row gets replaced with the token that was in the end of the array (tokenToSave)
ownerOfTokens[_from][kittyIndexToOwner[_tokenId].arrayPlacement] = tokenToSave;
//Deletes the last row of the array in the mapping
ownerOfTokens[_from].pop();
//Updates the token mapping so that the new array placement gets updated
kittyIndexToOwner[tokenToSave].arrayPlacement = kittyIndexToOwner[_tokenId].arrayPlacement;
}
//Maps the _to address to the token which gets pushed in to an array
ownerOfTokens[_to].push(_tokenId);
//Updates the token owner
kittyIndexToOwner[_tokenId].owner = _to;
//Updates the token's array placement of the owner
kittyIndexToOwner[_tokenId].arrayPlacement = ownerOfTokens[_to].length - 1;
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId].owner == _claimant;
}
}
Pros:
The time complexity of the getAllCatsFor function is now constant and also costs less gas than the original solution.
Cons:
The gas cost of creating kittens is higher because of the added array in the mapping ownerOfTokens and also the struct in the kittyIndexToOwner.
Creating is constant time.
getAllCatsFor() is linear time w.r.t. number of cats.
The constant time solution is similar to the hybrid mapping-list solution from the Storage Design Patterns section of the course. My idea is to create a mapping of owner address to array of tokenIDs, and add an ownerPointer variable on each Kitty that will be the index in that array for whichever address currently owns the kitty. The benefit is that we can efficiently query which cats are owned by any address. The tradeoff is extra complexity in the _transfer() function to keep track of the ownership lists. Also this requires storing an extra ownerPointer variable on each Kitty, which will 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;
uint ownerPointer;
}
Kitty[] kitties;
mapping (uint256 => address) public kittyIndexToOwner;
mapping (address => uint256) ownershipTokenCount;
mapping (address => uint[]) kittyOwnerToIndices;
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 kittyOwnerToIndices[_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),
ownerPointer: 0
});
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]--;
// Update the _from ownership mapping
uint rowToDelete = kitties[_tokenId].ownerPointer;
uint keyToMove = kittyOwnerToIndices[_from][kittyOwnerToIndices[_from].length - 1];
kittyOwnerToIndices[_from][rowToDelete] = keyToMove;
kittyOwnerToIndices[_from].pop();
}
// Update the _to ownership mapping
kittyOwnerToIndices[_to].push(_tokenId);
kitties[_tokenId].ownerPointer = kittyOwnerToIndices[_to].length - 1;
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
Hello, I need please a clarification on the line 57 of the code. I do not understand what is going on there. Looks like defining a variable on both sides of the â=â. Can somebody elaborate what is going on there?
Thanks in advance.
1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
Constant, because we just add struct.
2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
Linear, because we have to loop through all array. With increasing nr of cats in array the time will also increase.
3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
I used two mappings:
Then it is simple to execute getAllCats, because we just return the array of kitties that are owned by address from mapping.
PROS: with increasing number of kitties we save a lot of gas and time should be constant, because we donât have to loop for array. We just return the array from mapping. With such a project as CryptoKitties we expect that âdatabaseâ of values will be huge and therefore it brings a big advantage in terms of gas and time
CONS: with low number of kitties this solution takes more gas and possibly also more time. Solution is much more complex because of transfer function (which is complicated). However for this project it shuld be worth of it.
EDIT: First I made a solution with only one mapping so in transfer function I looped through an array. However I wanted to remove any loop from the contract, so I came up with double mapping.
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; // we can remove this mapping because we can count the length of kittiesOwned
mapping (address => uint256[]) public kittiesOwned;
mapping (address => mapping(uint256 => uint256)) public kittiesListPointer;
function balanceOf(address owner) external view returns (uint256 balance){
return kittiesOwned[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 (uint256[] memory){
return kittiesOwned[_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 {
kittiesOwned[_to].push(_tokenId); //push into array
kittiesListPointer[_to][_tokenId] = kittiesOwned[_to].length-1; //add listPointer
kittyIndexToOwner[_tokenId] = _to;
if (_from != address(0)) {
//switch inside of array
uint256 indexToDelete = kittiesListPointer[_from][_tokenId]; //listpointer of id we want to delete (place in kittiesOwned mapping array)
uint256 valueToMove = kittiesOwned[_from][(kittiesOwned[_from].length-1)]; //last id in kittiesOwned mapping array
kittiesOwned[_from][indexToDelete] = valueToMove; //replace id we want to delete with last id in array
kittiesListPointer[_from][valueToMove] = indexToDelete; // replace listpointer of value we switched
kittiesOwned[_from].pop(); // remove last id in storagy array
//delete double mapping listpointer of last id ??? Not possible, only set to default value 0, but is it really needed?
//No, because it is not being used until it is overwritten again.
//It would only consume gas with no additional value.
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
O(1) time complexity.
2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
O(n) time complexity.
3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
My changes would be the following:
pragma solidity ^0.8.0;
contract Kittycontract {
string public constant name = "TestKitties";
string public constant symbol = "TK";
event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);
event Birth(
address owner,
uint256 kittenId,
uint256 mumId,
uint256 dadId,
uint256 genes
);
struct Kitty {
uint256 genes;
uint64 birthTime;
uint32 mumId;
uint32 dadId;
uint16 generation;
}
Kitty[] kitties;
mapping(address => uint256[]) kittyIndexToOwner;
mapping (uint256 => address) tokenOwnership;
function balanceOf(address owner) external view returns (uint256 balance){
return kittyIndexToOwner[owner].length;
}
function totalSupply() public view returns (uint) {
return kitties.length;
}
function ownerOf(uint256 _tokenId) external view returns (address)
{
return tokenOwnership[_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 cats = kittyIndexToOwner[_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]++;
tokenOwnership[_tokenId] = _to;
// kittyIndexToOwner[_tokenId] = _to;
kittyIndexToOwner[_to].push(_tokenId);
if (_from != address(0)) {
// ownershipTokenCount[_from]--;
for(uint i=0; i< kittyIndexToOwner[_from].length; i++){
if(kittyIndexToOwner[_from][i] == _tokenId){
delete kittyIndexToOwner[_from][i];
kittyIndexToOwner[_from][i] = kittyIndexToOwner[_from][kittyIndexToOwner[_from].length-1];
kittyIndexToOwner[_from].pop();
}
}
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return tokenOwnership[_tokenId] == _claimant;
}
}
I decided it would be best to change kittyIndexToOwner mapping from mapping (uint256 => address) to mapping(address => uint256[]). This would enable us to retrieve a list of all tokenIds an owner has in O(1) time complexity as we no longer have to loop through an array.
The benefits of this implementation is itâs quicker to get the list of cats an owner owns.
The drawback is we must modify our _transfer function to introduce a loop for mapping(address => uint256[]) kittyIndexToOwner in order to find and delete the tokenId we are transferring ownership from. Then take the last element of the array to overwrite the deleted position before using pop() to remove the final item and decrease the size of the array.
Thus the trade-off here is a _transfer that uses more gas while getAllCatsFor leads to faster retrieval times for data querying.
Hi @MyName
You are creating an array âresultâ of type uint having length ownershipTokenCount[_owner]
Cheers,
Dani