0

I am programming a card game in java, and unsure what data structure I should use for the player's hand.

I considered using an array, with one integer to traverse the array and another integer to increment and decrement the size of the player's hand. However, if a player removes a card from the middle of the array, then the array will have a hole in it.

I could shift the position of every subsequent card towards the 1 element of the array and decrement the integer that keeps track of the players hand -- but this seems insufficient. I also considered a linked list.

Does anyone have a better suggestion for a data structure or insight about the two ideas that I have?

  • 2
    What language are you using? Most languages other than C and assembly have containers that can handle dynamic size changes easily. It's unlikely you need a custom structure, so using one of the simpler containers your language (hopefully) provides for you is likely the best move for now. – Ixrec May 16 '15 at 23:59
  • 2
    How many cards all-in-all? 4*13? Then consider a 64bit-integer used as a bitset. Anyway, even if the cards have identity (and why should they), using a linked-list is about the worst idea you could pursue. – Deduplicator May 16 '15 at 23:59
  • 1
    This seems like it's already well-traveled territory. – Robert Harvey May 17 '15 at 0:22
  • Are you primarily asking for performance reasons (as the answers here seem to have assumed), or for understandability (i.e. teaching/learning Java, etc)? – Tersosauros Feb 28 '16 at 5:43
5

There are a couple things to think about here - the structure of a card and the structure of the collection of cards... and all the while keeping in mind that this is Java and should be written with proper attention to object oriented principles.

A card is a thing. Representing it entirely as a bit in a BitSet, or worse... doing your own bit manipulation and passing around a long really takes you away from those object oriented principles. You're instead dealing with "I've got bit 23 thats a jack of hearts" makes for some ugly coding. Iterating over a bitset or bits set in a long isn't at all fun either. So, lets put that to rest - a bit isn't a card isn't a thing.

There are approaches based on this that aren't wrong for Java. It is not unreasonable to stick all of the cards in an enum:

public enum Card {
  ACE_OF_HEARTS,
  TWO_OF_HEARTS,
  ...
  KING_OF_SPADES
}

You could then use an EnumSet as the collection. Yes, its backed by a BitSet when you dig into it, but it's a nice collection to deal with. It's actually a Collection (a BitSet isn't) and so you get the iterators and contains and the like. A BitSet, you're doing your iteration by hand calling nextSetBit(5) to find out what the index of the next set bit.

I won't say that the enum with all the cards in it is wrong, but it isn't right either. If you read the tutorial on enums from Oracle, you even find...

import java.util.*;

public class Card {
    public enum Rank { DEUCE, THREE, FOUR, FIVE, SIX,
        SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, ACE }

    public enum Suit { CLUBS, DIAMONDS, HEARTS, SPADES }

    private final Rank rank;
    private final Suit suit;
    private Card(Rank rank, Suit suit) {
        this.rank = rank;
        this.suit = suit;
    }

    public Rank rank() { return rank; }
    public Suit suit() { return suit; }
    public String toString() { return rank + " of " + suit; }

    private static final List<Card> protoDeck = new ArrayList<Card>();

    // Initialize prototype deck
    static {
        for (Suit suit : Suit.values())
            for (Rank rank : Rank.values())
                protoDeck.add(new Card(rank, suit));
    }

    public static ArrayList<Card> newDeck() {
        return new ArrayList<Card>(protoDeck); // Return copy of prototype deck
    }
}

And you've got a deck backed by the ArrayList.

Here's a thing to think about though. You can't have two jack of hearts in your hand... well, some games you might, but most games you don't. This means a collection of cards is a Set. This gives you a few options for how to implement the hand in such a way that doesn't mean juggling arrays.

I'd start with a LinkedHashSet as that maintains dealt order, or you might prefer either the TreeSet or ConcurrentSkipListSet if you want the cards to be in sorted order. Note that this isn't as useful for dealing the cards from a deck as you would want that to be in a List because Collections.shuffle takes a list as arguments. You also don't have to worry about pulling cards out of the middle of the deck when dealing. So the LinkedList would work very nicely for the deck itself when dealing cards (see pollFirst if you want to do it that way).

Some games though, you may find that you need to keep it in a deque (such as a LinkedList - so you get the poll first and last). Others you want to keep the cards in a sorted structure, or others you may want something else. It all depends on what you want to do and finding the correct Collection (or not) to do it.

However, the data structure for a card should be that of the card presented by Oracle in the enum tutorial. And then you use the Collection that maps to how you want to hold the cards.

  • You're hating on bit manipulation way too much. A BitSet or equivalent wouldn't force you to go super-low-level and worry about whether bit 23 is set. Want to find out whether it's the jack of hearts? Intersect the Jacks and Hearts sets (giving a set that contains only the jack of hearts) and then intersect that with the hand (or deck or card) you're interested in, and if it's not empty, then that hand/deck/card had the jack of hearts. – Michael Shaw May 17 '15 at 16:52
  • @MichaelShaw I personally really like bit sets and the like, and your suggestion greatly simplifies a sheepshead montecarlo program I've been thinking of (bonus: sheepshead deck only has 32 cards in it). But for idiomatic Java code, working with a deck of 52 Card objects and the appropriate collection would lead to more maintainable code that more clearly shows its intention... Especially in the situation where the OP is not completely comfortable with all of the collections in the first place, a bitset or masking a long may be confusing. – user40980 May 17 '15 at 17:02
  • I see your point about the importance of collections, although I think the intentions would be perfectly clear if the bit manipulations were wrapped in a reasonable class. It would be really simple to implement a filter method and then do things like hand.filter(Hearts & FaceCards), for example. I've never played sheepshead, so I don't know if this will be useful, but I did a montecarlo simulation for figuring out the odds of poker hands once, and when I switched from montecarlo to an exact calculation (generating all possible hands and counting the straights) it sped up a lot. – Michael Shaw May 17 '15 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.