Help me choose appropriate data structure
 

Hi all,
I'm trying to implement some game logic. First i would like to give an
example.
We have 3 different colors of cards. In each color there are 504 cards
(numbered from 0 to 503).
Now each player is given some cards. The cards given to each player
shall be represented by a combination of following
a). Individual card number
b). Range of card numbers.
c) Note: each player will have cards belonging to only one color. one
player cannot have same color cards as another player.
eg. player 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
player 2 has : green cards (1-100, 301-305, 499)

I want to implement a structure which can represent the cards each
player has.

typedef struct
{
T_COLOR color;
int length; /*length of absolute card numbers */
int *num; /* array of standalone numbers, ie not represented by
ranges */
int num of range; /*length of number of ranges */
int *start; /* indicate start of each range */
int *end; /* indicate end of each range */
}

For example:player 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
This is represented in the above structure like,
{
color = YELLOW
length = 3;
num = [1,3,99]
num_of_range = 2
start = [20,200]
end = [30,310]
}


Adding some complexity on top of this is, i should be able to
dyanmically add and remove number of cards to each player. Again this
dynamic input is represented by
eg: Add the following cards for player 1 : Yellow cards (320, 401-419)
remove the following cards for player 2: green cards (40-50, 301)


I thought of implementing this in bitmaps. But memory is of concern
here (sometimes a player can have only one card, so pre-allocating a
bitmap of size 504 seemed overkill). Can someone comment on the
structure ? Is there a better way to implement these ?


Thanks

Re: Help me choose appropriate data structure
 

bigbang <bigbangbingo@gmail.com> wrote:

> We have 3 different colors of cards. In each color there are 504 cards
> (numbered from 0 to 503).

> eg. player 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
> player 2 has : green cards (1-100, 301-305, 499)
> Adding some complexity on top of this is, i should be able to
> dyanmically add and remove number of cards to each player. Again this

> I thought of implementing this in bitmaps. But memory is of concern
> here (sometimes a player can have only one card, so pre-allocating a
> bitmap of size 504 seemed overkill). Can someone comment on the
> structure ? Is there a better way to implement these ?

If you have reason to believe that this can change to virtual cards of
thousands of colours, with thousands of values for each, maybe use a
linked list of struct range {int start; int end;} for each player. If
keeping the hands sorted is important, and you expect tens of thousands
of cards per colour, use a tree of some kind.
If, OTOH, you know that you will at most have a reasonable dozen of
colours, of less than a thousand cards each, a bitmap simply is not as
much overkill as it seems. Remember that it will probably keep the code
simpler, and therefore smaller.

Richard

Re: Help me choose appropriate data structure
 

"bigbang" <bigbangbingo@gmail.com> wrote in message
news:72421e30-b076-411c-b55d-60dd6d60508f@u3g2000prl.googlegroups.com...

> We have 3 different colors of cards. In each color there are 504 cards
> (numbered from 0 to 503).
> Now each player is given some cards. The cards given to each player
> shall be represented by a combination of following
> a). Individual card number
> b). Range of card numbers.
> c) Note: each player will have cards belonging to only one color. one
> player cannot have same color cards as another player.
> eg. player 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
> player 2 has : green cards (1-100, 301-305, 499)

> typedef struct
> {
> T_COLOR color;
> int length; /*length of absolute card numbers */
> int *num; /* array of standalone numbers, ie not represented by
> ranges */
> int num of range; /*length of number of ranges */
> int *start; /* indicate start of each range */
> int *end; /* indicate end of each range */
> }
>
> For example:player 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
> This is represented in the above structure like,
> {
> color = YELLOW
> length = 3;
> num = [1,3,99]
> num_of_range = 2
> start = [20,200]
> end = [30,310]
> }
>
>
> Adding some complexity on top of this is, i should be able to
> dyanmically add and remove number of cards to each player. Again this
> dynamic input is represented by
> eg: Add the following cards for player 1 : Yellow cards (320, 401-419)
> remove the following cards for player 2: green cards (40-50, 301)
>
>
> I thought of implementing this in bitmaps. But memory is of concern
> here (sometimes a player can have only one card, so pre-allocating a
> bitmap of size 504 seemed overkill). Can someone comment on the
> structure ? Is there a better way to implement these ?

Having separate representations for individual cards, and ranges, seems
overcomplex. For example if you have card 17, and add card 18, suddenly you
have a range. And vice versa.

There are any number of ways of representing an abitrary collection of the
numbers from 0 to 503. If I didn't need to use C, I would choose a language
that implemented Pascal-type sets:

type cards: 0..503; (or whatever the syntax happens to be);

cards a,b,c;
a=[1,3,20..30,50,99,200..310];

Now adding extra cards is easy:

a = a+[4..10,17..19,100] //assuming no duplicates allowed

Now a will be [1,3..10,17..30,50,99..100,200..310]

I don't think it's that hard to implement something similar in C

Personally I would just go with a bytemap of 504 bytes (char a[504]); the
0.5KB memory is of no consequence on most processors. Any anyway your data
structure, in the worst case, could use a lot more (eg. the set
[0,2,4,8,.... 502]).

--
Bartc

Re: Help me choose appropriate data structure
 

On 01/06/10 11:41, bigbang wrote:

> For example:player 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
> This is represented in the above structure like,
> {
> color = YELLOW
> length = 3;
> num = [1,3,99]
> num_of_range = 2
> start = [20,200]
> end = [30,310]
> }

so an array of 3 ints, and 2 arrays of 2 ints, plus 2 ints. And 1 int
for the colour.

That's 10 ints. 4 bytes per int? 40 bytes.

Add a few more cards and ranges, and you're soon over 64 bytes.

In addition, adding or removing a card has to check for any effect on
existing ranges, for example if taking a card out in the middle of
range, or creating of new ones. If you take a card out of a range, you
may break it into a card + range, or range + range. Adding a card might
extend a range, just be a new card, join two ranges, or fit between a
single card and a range (eg if you have 21, 23 - 27 and add 22). You
have to detect all of this and update data structures accordingly.

> I thought of implementing this in bitmaps. But memory is of concern
> here (sometimes a player can have only one card, so pre-allocating a
> bitmap of size 504 seemed overkill). Can someone comment on the
> structure ? Is there a better way to implement these ?

64 (8 bit) bytes = 512 bits gives you 504 card indicators and 8 bits for
colour, which could be 1 of 256 colours. And adding and removing a card
is as simple as setting or clearing a bit. 512 bits is, in most
architectures, likely to be an easily defined block using eg "unsigned
char * cards[16];" for an 8 bit char architecture.

I think it will be better in terms of both data size and code size in
the long run to use bitfields, any saving in data storage for small
numbers of cards is probably going to be offset by the increase in code
size to handle the additional complexity of managing the more complex
structures.

Rgds

Denis McMahon

Re: Help me choose appropriate data structure
 

On Jun 1, 8:08*pm, Denis McMahon <denis.m.f.mcma...@googlemail.co.uk>
wrote:
> I think it will be better in terms of both data size and code size in
> the long run to use bitfields ...

Perhaps. I suppose you meant "bitmap" when you wrote "bitfield."

There are some other alternatives for various size/simplicity
tradeoffs. A general bitmap codec (probably overkill for OP's
needs) is available at
http://fabpedigree.com/james/sofa.c
(License would be needed for commercial use.)

James

Re: Help me choose appropriate data structure
 

bigbang <bigbangbingo@gmail.com> writes:
> I'm trying to implement some game logic. First i would like to give an
> example.
> We have 3 different colors of cards. In each color there are 504 cards
> (numbered from 0 to 503).
> Now each player is given some cards. The cards given to each player
> shall be represented by a combination of following
> a). Individual card number
> b). Range of card numbers.
> c) Note: each player will have cards belonging to only one color. one
> player cannot have same color cards as another player.
> eg. player 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
> player 2 has : green cards (1-100, 301-305, 499)
[snip]

Is this homework?

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Re: Help me choose appropriate data structure
 

In article <lnfx16ixqx.fsf@nuthaus.mib.org>,
Keith Thompson <kst-u@mib.org> wrote:
>bigbang <bigbangbingo@gmail.com> writes:
>> I'm trying to implement some game logic. First i would like to give an
>> example.
>> We have 3 different colors of cards. In each color there are 504 cards
>> (numbered from 0 to 503).
>> Now each player is given some cards. The cards given to each player
>> shall be represented by a combination of following
>> a). Individual card number
>> b). Range of card numbers.
>> c) Note: each player will have cards belonging to only one color. one
>> player cannot have same color cards as another player.
>> eg. player 1 has : yellow cards (1,3, 20-30,50, 99, 200-310)
>> player 2 has : green cards (1-100, 301-305, 499)
>[snip]
>
>Is this homework?

Suppose it is. Please explain why that is a problem (if, as I gather
from your tone, you think that it is).

If you work it through, you will see that homework is precisely what we
*should* be answering here in this newsgroup. I just don't see it as a
problem.

--
> No, I haven't, that's why I'm asking questions. If you won't help me,
> why don't you just go find your lost manhood elsewhere.

CLC in a nutshell.

Re: Help me choose appropriate data structure
 

On Jun 1, 1:41*pm, bigbang <bigbangbi...@gmail.com> wrote:
> Hi all,
> Can someone comment on the
> structure ? Is there a better way to implement these ?
>
You have about 1500 cards. On a modern machine, memory efficiency
isn't a concern. The window manager will use far more memory
displaying results to the user than you use in storing the cards,
whatever sane representation you use.
The obvious structure to use is a flat list of cards, then dynamic
lists of indices giving the cards held by each player, in discard
heaps, and so on. This is because such a data structure is reasonably
fast, and intuitive.

However if you need extra space / storage efficiency then you need to
analyse how you index the cards. There are always tradeoffs between
ease of implementation, speed, and memory usage. For instance if space
is the only constraint, you can have a flat list of cards, compressed
in memory, and traverse the list each time you need to pull out a
card, decompressing on the fly. A non-compressed but compact flat list
is the next stage up, giving considerable improvements in ease of
implementation and access speed, but still potentially O(N) each time
you need to check whether a player has a card. However if N is only
1500, O(N) isn't too bad.

Re: Help me choose appropriate data structure
 

On Jun 1, 11:28*am, gaze...@shell.xmission.com (Kenny McCormack)
wrote:
> Suppose it is. *Please explain why that is a problem (if, as I gather
> from your tone, you think that it is).
>
> If you work it through, you will see that homework is precisely what we
> *should* be answering here in this newsgroup. *I just don't see it as a
> problem.

People should be working out their own homework that's the point. I
think most people would be ok if people tried to work out a solution
and THEN asked for advice. The OP seems [to me] to be borderline
homework answer seeking and legitimate question. Thing is the OP
really hasn't shown their code yet, just some small useless fragment
and then asking if there is a better way.

Thing is people like Keith or Richard have likely seen all forms of
homework questions float around here, which is why they're quick to
sniff it out.

Let me ask you something, what service do you suppose you're providing
if you do peoples homework and they don't ever learn anything?

Tom

Re: Help me choose appropriate data structure
 

On Jun 1, 6:56*pm, Tom St Denis <t...@iahu.ca> wrote:
>
> Let me ask you something, what service do you suppose you're providing
> if you do peoples homework and they don't ever learn anything?
>
There's a difference, admittedly sometimes a fine one, between doing
the homework and telling them how to do it.