Data-structure for dynamic disjoint-sets

Question

I have a collection of objects, with certain properties (let say 3 - zone, type, owner) only having a small predetermined possible set of values (like enum).

This is just a simple (javascript) array of gaming cards (think "magic the gathering"), that could be in different zones (deck, hand, grave, play), and they could be owned by different players at different stages of their lifecycle. Also, there is a type (spell, minion, weapon, enchantment) which is unchangeable, but still very important discriminator.

In order to process game, I need to often query my store to get "all spells in hand which cost less than current mana of current player", or "all enemy minions which had not attacked this turn".

Right now I simply use Array.filter and just filter the all universe with small predicate functions, but I have a feeling this could be made more efficient, if I can at least cut the size of whole collection in the beginning of query processing.

To speed up queries like where type = N, I considered using a pre-made number of Sets (e.g.: "cardsByType = MINIONS | SPELLS | WEAPONS" or cardsByZone = HAND | DECK | GRAVE). Also, during program life cycle - some of those properties could be updated - so I was updating those Sets together with object update.

Unfortunately in practice, I need the collection to be ordered, as insertions and removals need to happen in certain positions. This means that Sets only help me with queries like count where type=n. Also, during program life cycle - some of those properties could be updated - so I was updating those Sets together with each object's (card) update.

Also, maintaining the consistency between object itself, and two collection (old and new) is very error prone.

Am I missing some known obvious data-structure that could be helpful with such task ? OR no general-purpose data-structure like that exists ?

Answer 1

For Magic the Gathering, the number of cards is so small that the simplest data structure is probably the best. Just have a list of all cards (each card records its name, location, properties, etc.). Then to answer a query, scan through all cards and see which ones match the query. Since you'll probably have very few cards in the data structure at a time (like, at most a few hundred), all operations should be very fast.

There are more sophisticated schemes, but they probably aren't worth the implementation effort. You could think of this as a table in a relational database (one row per card, one column per attribute), and build an index for each column. In other words, you have an ordered list of cards. You also have a hashmap that maps from location to a list of all cards in that location. These lists are stored as balanced search trees, with links between them (i.e., given a card in one tree, you can follow pointers to find where that card is stored in each of the other trees). This will let you do queries quickly. Also to update the data structure, you can remove a card by finding it, then removing it from all of the linked trees; and you can insert a card similarly. But in your case it won't be worth the effort.