A way to make queryable more efficient

[nidhhoggr]

Right now queryable is O(maxSupply) and I'm proposing a way to make it O(largestTokenId - smallestTokenId)

setAux reserves a space for 64 bits having the largest unsigned integer of 18446744073709551615.

If we reserve aux strictly for this lookup index we can store both the largestTokenId and the smallestTokenId in this integer.

The way to store and retrieve two integers into one is as follows:

Dual Packer

You can store both A and B in one variable, say D, by doing where C = max(A, B) + 1
D = A * C + B

Now, when needing to extract A and B, you can do,

A’ = D / C = A (Note: It is integer division)

B’ = D % C = B

The square root of 18446744073709551615 makes 4294967296 + 1 the largest possible number for the maxSupply

No collections come anywhere near a max supply of 4294967296 so this is more that practical for this purpose. For that reason we can even reserve a smaller space 2^32 within aux for this purpose which allows for the largest maxSupply of 65536, still practical for the majority of collections. Now we can still use 32 bits in aux for whatever else we need.

1. First we store the first minted index as both the largestTokenId and smallestTokenId.
2. Upon transfers we unpack the index and check that the tokenIndex is between A' and B'
3. If the tokenId isn't between A' and B' we re-compute the index and store the tokenId as A' if its smaller thanB' or vise versa.
4. Now we always call tokensOfOwnerIn(owner, A', B') in place of tokensOfOwner

[Vectorized]

Queryable is not intended to be used for on-chain querying.

[nidhhoggr]

Makes sense. I'll close it.