How would YOU implement it?

[Dan]

I am looking to implement a deck of cards, or more specifically a pile of cards (difference being a deck tends to be of a known starting size, this won't be)

I need to be able to:

[#]Look at the top X cards

[#]Remove the top card

[#]Shuffle the pile

[#]Add cards to the top of the pile

[#]Add cards to the bottom of the pile

[#]Search for a card

The pile needs to:

[#]Maintain its order between shuffles

[#]Be able to cope with ordered piles being added to it without being shuffled

Assume a card is defined as a class with no complex subtypes, and that no card IN the pile will need to know where in the pile it is.

What data structure would you base the pile on? I looked at arraylists but I can't see a clean way of keeping the indexing going when adding and removing arbitrarily. I also considered Queues but adding to the top and shuffling seems to be made overly complex. Stacks I can see having the same problems from the other end. I've just been looking at "List" rather than ArrayList and it seems hopeful. What do you guys think?

Edit: If it helps, I'm using C#WPFXAML.

[Nacey]

Use an ArrayList, calling .Remove() will shift everything to fill the gap (it's actually implemented as a Doubly Linked List so nothing really moves in memory).

[Dan]

Am I the only one that thinks linked lists of any kind are terrible? Though I can appreciate they do actually fit quite well here...

[Lagrosh]

Why do you think they're terrible? Vectors are also great. Depends on needs. Why do you need anything else though? Pretty much, do do everything with a "List" and then you can use whatever.

[Nacey]

Am I the only one that thinks linked lists of any kind are terrible?

Yes.

I don't even see why you care, you don't have to do anything related to it being a link list, you can just use it like a generic list, the implementation is irrelevant except if you try to do something that a linked list makes easy like adding or removing elements mid-list.  And even then the implementation is arguably still irrelevant.

[Omenos]

I used to think linked lists were terrible (as they seemed awkward to use at first) but seeing them being applied kinda made me realise they are actually pretty awesome but that's beside the point...

I've never used vectors and tbh my fallback generally is an Arraylist or a Hashmap depending on what I want, in this case as the order of the cards is key I would go for an Arraylist.

[Nacey]

Vector = Hashmap = Dictionary

[Omenos]

You sure about that?  I thought a Vector was closer to an Arraylist than a Hashmap given that a Vector is ordered and integer indexed as opposed to being pretty much unordered and indexed with a key which can be something other than an integer.

[Nacey]

Yeah sorry was getting Vector and Map confused, I never use C++ since it's a retarded language.

[Lagrosh]

It's a good language.

Yeah though, they're all different, but for most purposes they're basically the same.

[Dan]

Linked Lists then eh...

I'll see what I can dig up...

[Dan]

Actually thats pretty cool looking at what methods are avaliable on it, theres a c# "LinkedList" which you can provide a generic type on, top and bottom are easily obtainable and easy to put stuff on and I don't actually need to care how it looks on this inside (which is the bit that made me shy away from them).

Next up: How would you shuffle it?

I was thinking assign each card a random number (in a large range) and sort by that number, however, these linkedlists have no sort function. I could empty the collection into another data structure as at this point I don't need to maintain order and do the same thing and use its sort, then put them back, but that seems messy...

[Nacey]

I already told you, an ArrayList is a doubly linked list so just use that.

Inherit from ArrayList and have it implement the interface ISortable (I think, will check this at work.) you just need to provide a method which, when given two elements, returns the one which should be sorted higher. The actual sort loop is handled for you and it user Quick Sort as far as I remember. I can throw a quick demo for you together if needed.

[Dan]

They can't be typed ;_;

And you changed your first post on this thread since I read it, it just said use a Doubly Linked list...

And then your most recent post changed since I started typing this...

[Nacey]

Are you saying ArrayList<Type> doesn't work? Hmm, odd. Will look later from work.

[Dan]

For some reason, no. List<T> does, ArrayList doesn't seem to...

[Nacey]

Right you are.  Basically just use a List, it's the generics equivalent of an ArrayList.  For the number of elements you'll be using (guessing <1000 and more like <100), search/update time is trivial regardless of back-end implementation anyway.  See my previous post, the rest still stands regarding sorting a List.  There's a method List.Sort() which I didn't mention, you'll need to call that to sort the list (dur).

Edit: Actually forget that (for suffling at least), here is a much better way to implement a shuffle:

1. Have all your cards in whatever order in List<Type> myList.

2. Create a new temporary List<Type> tempList.

3. Generate a random number between 0 and myList.Count.

4. Add that element to tempList.

5. Remove that element from myList (remember this shifts everything down).

6. Goto 3 until myList is empty.

7. myList = tempList.

In case you haven't used random numbers before:

Random random = new Random(); //The default seed is based on the system clock
random.Next(0, myList.Count); //Random number between 0 (inclusive) and myList.Count (exclusive)

[Tim]

[#]Shuffle the pile

http://www.cplusplus.com/reference/algorithm/random_shuffle/

c++ FTW

[Nacey]

Hmm, I guess that works but at first thought that doesn't sound like it would produce an even random distribution.  Can anyone prove/disprove that?

[Mokajin]

There is no true random!

[Omenos]

/**
* This method returns a randomly generated integer.
* @return A random integer value
*/
public int randomNumber() {
    return 4;
}

(I think someone may have linked something like this here before )

EDIT: And something a little random which I saw in the Android 1.5 source code that made me chuckle...

/**
* Values returned by the accelerometer in various locations in the universe.
* all values are in SI units (m/s^2)
*/

#define GRAVITY_SUN             (275.0f)
#define GRAVITY_MERCURY         (3.70f)
#define GRAVITY_VENUS           (8.87f)
#define GRAVITY_EARTH           (9.80665f)
#define GRAVITY_MOON            (1.6f)
#define GRAVITY_MARS            (3.71f)
#define GRAVITY_JUPITER         (23.12f)
#define GRAVITY_SATURN          (8.96f)
#define GRAVITY_URANUS          (8.69f)
#define GRAVITY_NEPTUNE         (11.0f)
#define GRAVITY_PLUTO           (0.6f)
#define GRAVITY_DEATH_STAR_I    (0.000000353036145f)
#define GRAVITY_THE_ISLAND      (4.815162342f)

[Nacey]

(I think someone may have linked something like this here before )

XKCD did it:

RFC 1149.5 specifies 4 as the standard IEEE-vetted random number.

[Dan]

I still didn't implement this, I've been too busy making my cards individually work as my database of cards is still miles away.

Currently the concept of a hand, playing a card, and having cards in play are all on screen and displayed very nicely...

[Tiran]

There is no true random!

Radioactive decay.

[Nynia]

Thought this might have something to do with Race.

How are you going to work in the specials?

If it can automatically activate them that'd be quite nice.

(eg. Dealt extra cards when development phase, or after settle, etc.)