Testing the Game ADT

testing each of the Game ADT interface functions
to make sure they’re doing what they should be doing.

how? “simulate” a game:
make moves, check game state is correct.

how?
you specify the deck,
you decide the moves,
so you know the resulting game state

see Testing the Game ADT

Implementing the Game ADT

first: design

what do you need to keep track of game state?
what will you put in your struct _game?
how will you store hands, deck, discard pile?

tip: sit down with your group and discuss this before coding

Implementing the Game ADT

then: implement

function at a time…
add tests as you go!

Playing the Game

write an AI to play the game…
more details coming soon

Submission

open for testGame.c and Game.c!
player.c coming later in week 12

submit as usual
give, through WebCMS3, etc.

submit early … submit often

submit a compiling stub version now
(more on this later)

Submitting Code

submit partial (but compiling) code

submit often

Test + Competition rounds

Sundays, Wednesdays, Fridays
at 8:30pm

Failed Tests

figuring out what’s wrong with your code

disputing incorrect tests

Disputed Tests

refuting claims that your test was wrong

Writing + Fixing Tests

Previously on COMP1511…

printf(“Hello, world!\n”);

conditionals (if/else), functions, loops

memory, arrays, strings, pointers

structs, typedef, dynamic memory allocation

testing, problem solving & abstraction, ADTs

ADTs

separating the interface from the implementation

Stacks

Last In, First Out (LIFO)

we can only
add, see, or remove
(“push”, “peek”, or “pop”)
the top-most element

Continuity

arrays: a fixed size, contiguous block of memory
(a continuous series of boxes in memory)

each item has a known location –
it’s right after the previous item

int array[7] = { 3, 1, 4, 1, 5, 9, 2 };

gives us a sequence of elements in memory:

┄─┬────┬────┬────┬────┬────┬────┬────┬─┄
  │  3 │  1 │  4 │  1 │  5 │  9 │  2 │  
┄─┴────┴────┴────┴────┴────┴────┴────┴─┄

Varying the Length

what if stacks aren’t of known-maximum length?

what if we need arrays of dynamic length?

in C, we have dynamic allocation…
but that’s still (effectively) fixed in length

we need a new way to represent
collections of things

Discontinuity

we could allocate memory for a new value as needed

int *a = calloc (1, sizeof (int));
*a = 3;
int *b = calloc (1, sizeof (int));
*b = 1;
int *c = calloc (1, sizeof (int));
*c = 4;
// ... and so on

we’d have to hold on to all those pointers…
and we don’t have a nice way to do that.

┄┬────┬┄    ┄┬────┬┄    ┄┬────┬┄    ┄┬────┬┄
 │  3 │      │  9 │      │  5 │      │  2 │ 
┄┴────┴┄    ┄┴────┴┄    ┄┴────┴┄    ┄┴────┴┄
      ┄┬────┬┄    ┄┬────┬┄    ┄┬────┬┄      
       │  1 │      │  4 │      │  1 │       
      ┄┴────┴┄    ┄┴────┴┄    ┄┴────┴┄      

Continual Discontinuity

 ╭───╮   ╭───╮   ╭───╮   ╭───╮ 
 │ 3 ├─╮ │ 5 ├───│ 9 ├───│ 2 ├╳
 ╰───╯ │ ╰───╯   ╰───╯   ╰───╯ 
       │   ╰───────────────╮   
     ╭───╮   ╭───╮   ╭───╮ │   
     │ 1 ├───│ 4 ├───│ 1 ├─╯   
     ╰───╯   ╰───╯   ╰───╯     

Continual Discontinuity

a sequence of nodes,
each with a value and a next

╭───╮  
│ 3 ├─*
╰───╯  

Discontinuity

typedef struct _node *Node;
typedef struct _list {
    Node head;
} list;
typedef struct _node {
    int value;
    Node next;
} node;

… pointers!

╭───╮    ╭───╮    ╭───╮  
│ 3 ├────│ 1 ├────│ 4 ├─╳
╰───╯    ╰───╯    ╰───╯  
  a        b        c    

node a = { 3 };
node b = { 1 };
node c = { 4 };
a.next = &b;
a.next->next = &c;
a.next->next->next = &d;

In context: Final Card-Down

a player has a hand of cards

possible actions:
draw card (add card to hand)
play card (remove from middle?)

how could we implement this?

Arrays vs Linked Lists

… an array of Cards?

remove from middle?
shuffle all array elements down…

add card to hand?
add onto the end?
… what if we run out of space?

Array of Cards

Card hand[SOME_BIG_NUMBER];
int upto = 0;
Card first = getCard(???);
hand[upto] = first;
upto++;
Card second = getCard(???);
hand[upto] = second;
upto++;

Arrays vs Linked Lists

… a list of Cards?

remove from middle?
easy! just remove a Card + adjust pointers

add card to hand?
easy! just add to the start/end of list
… no size limit!

List of Cards

typedef struct _node *Node;
typedef struct _node {
    // int value;
    Card card;
    Node next;
} node;

…

Node hand;
Card first = getCard(???);
hand->card = first;

Card second = getCard(???);
hand->next = newNode();
hand->next->card = second;

Traversing… an Array

void fillArray (int array[ARRAY_SIZE], int value) {
    int i = 0;
    while (i < ARRAY_SIZE) {
        array[i] = value;  // set the value
        i++;               // move to next element
    }
}

Traversing… a Linked List

void fillList (List list, int value) {
    Node curr = list->head;
    while (curr != NULL) {
        curr->value = value; // set the value
        curr = curr->next;   // move to next node
    }
}

What can we do with linked lists?

insert into list

remove from list

create a new node

print out list

What can we do with linked lists?

insert into list

remove from list

create a new node

print out list

What can we do with linked lists?

insert into list

remove from list

create a new node

print out list

What can we do with linked lists?

insert into list

remove from list

create a new node

print out list