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. This is because a new cat is simply just added to the end of the 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 due to the iteration over the entire kitty array.
3. How could the storage design be changed to make the getAllCats function constant?
We could add another mapping that would map the owner address to a uint[] of all the cats owned by the owner. This would require more memory and be a little more expensive to call _createKitty and to call _transfer cats, but would give us a constant time complexity to access all cats owned by a specific 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 => uint[]) ownerCat;
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[]){
return ownerCat[_owner];
}
}
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;
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;
}
}
