Ben Knoble Ben Knoble - 3 months ago 10
C# Question

Adding Cards to the bottom of an immutable Deck

Background: I created a custom

Card
struct with
Suit
and
Value
properties represented by enums to model a playing card. I created a
Deck
class which contains cards and has several options for manipulating them. It stores cards as a
Queue<Card>
because that made the most logical sense and made most implementations easy.

To practice coding, I decided I wanted to build an
ImmutableDeck
that couldn't be modified. It's methods return new
ImmutableDeck
s and use
out
parameters to return drawn
Card
s. I modeled it on Eric Lippert's
ImmutableStack
, creating an
Empty
Deck, making constructors private, and having two members: the "Top Card", and a "pointer" to the next
ImmutableDeck
.

public class ImmutableDeck
{
static readonly EmptyDeck Empty = new EmptyDeck ();
readonly Card top;
readonly ImmutableDeck next;

ImmutableDeck ()
{
}

ImmutableDeck (Card top, ImmutableDeck next)
{
this.top = top;
this.next = next;
}

public int Count => 1 + next.Count;
public bool IsEmpty => this == Empty;
public Card Top => top;

public Card Bottom ()
{
var temp = next;
while (!temp.next.IsEmpty)
{
temp = temp.next;
}
return temp.Top;
}

public ImmutableDeck DrawCard (out Card c)
{
c = top;
return next;
}

public ImmutableDeck PutCardOnTop (Card c)
{
return new ImmutableDeck (c, this);
}

public ImmutableDeck PutCardOnBottom (Card c)
{
throw new NotImplementedException ("PutCardOnBottom");
}



public class EmptyDeck : ImmutableDeck
{
public new int Count
{
get;
} = 0;

public new bool IsEmpty
{
get;
} = true;

public new Card Top
{
get
{
throw new Deck.DeckEmptyException ();
}
}

public new Card Bottom ()
{
throw new Deck.DeckEmptyException ();
}

public new ImmutableDeck DrawCard (out Card c)
{
throw new Deck.DeckEmptyException ();
}

public new ImmutableDeck PutCardOnTop (Card c)
{
return new ImmutableDeck (c, this);
}

public new ImmutableDeck PutCardOnBottom (Card c)
{
return new ImmutableDeck (c, this);
}
}
}


Problem: Clearly, these decks can be constructed by building cards on top of cards on top of empty decks. It's fairly powerful. But I'm struggling to implement a way to allow a
Card
to be added to the bottom. So far, all I've come up with is that I need to follow the
next
pointers through the chain until I reach the end (Empty), but I'm not sure what the next steps are.

A good solution will provide working code that correctly returns a new
ImmutableDeck
instance where the passed in
Card
is now the last card in the deck as well as an explanation of how the solution works.

Answer

As Leandro said, there are multiple ways to do this. Here is mine (using the same class you already have). The only problem I can see is that it requires that you assign a value to the next field, which is read-only in your implementation. I understand why it is so (you can't modify what's under another card before taking that card out), but in this case I'm sure it'd be possible to do it without changing the this field.

Public ImmutableDeck PutCardOnBottom (Card c)
{
    if (!this.next.IsEmpty)
        this.next.PutCardOnBottom(c);
    else
        this.next = new ImmutableDeck(c, ImmutableDeck.Empty);

    return this;
}

Note : I'm not 100% sure about return the instance of the 1st call, but I think that's what makes sense since the top of the deck didn't change.

Other Note : Only issue I can see with this (apart from what I noted before) is that if you have a really big deck, you'll encounter a StackOverflowException. I could have done it in a similar fashion to your implementation of the Bottom method, but I figured a 52 card deck would not be an issue, and I love recursive functions :)

Comments