- introduce friend classes
- review queues
- review breadth-first-search
- say something about arrays of strings (char **)
- go over some common problems in assignment 1 (if there is time)
----------------
admin:
	will handout old quiz on tuesday

Friends:
--------
	allow access to private members
	a whole class can be made a friend then that class can access
	any private methods.  Useful for helper classes so other parts
	of the program don't screw up the helper class.

e.g.,

class CharLink
{
  char data;
  CharLink* next;
  CharLink(char, CharLink*);
  ~CharLink();
  friend class CharStack;
};

class CharStack {
  CharLink* top;
  char pop();
  void push(char);
  CharStack();
  ~CharStack();
}

	If you want to go over the proper implementation of ~CharStack
	(recursively delete all elements via delete) and ~CharLink
	that wouldn't be a bad idea.

For queues:
	how would you implement them?  head and tail.
	What should head and tail point to if we want to avoid
	doubly linked lists.

	Keep this general enough that you don't have to write any code?

For BFS:
	main point: how does the marking work so that one can retrace
	the path.

The maze:
	

       +-------+-------+
       | 0   1 | 2   3 | 
       |   +   +---+   +
start 4  5 | 6   7 | 8   9  goal <|
       |   +   +---+   +
       | 10  11  12  13|
       +---------------+


Note: hwk assignment is to do something very much like this, except
"maze" isn't a 2-D maze like this: instead it's a conceptual maze
defined by a list of words and a rule that tells you when two words
are adjacent.

Data Structures:
----------------

class IntMaze {
	// returns # of neigbors of a node
	int getNumNeighbors();
	// returns the 'num'th neigbor of 'node'.
	int getNeighbor(int node, int num);
	// sets all nodes to unmarked
	void unMarkAll();
	// marks node 'to' with node 'from'
	int setMark(int from, int to);
	// gets the mark for 'node'
	int getMark(int node);
};

note: this make can only have unique integers as nodes.
better data structure uses a Node class.

Algorithm recap:
----------------
1. Initialize nodes in all to NOT_VISITED, except start -> start.

2. Queue, insert start.   {4}

3. While (queue is not empty) {

     current = remove(queue)

     if current is goal, then done: read off path from came_from.

     otherwise, for each neighbor X of current that's not been visited yet
                insert X into queue.
                mark X as coming from current
   }


                                 QUEUE
                            tail       head
insert 4.                         <4>                             DIST 0
Remove 4, insert 5                <5>                             DIST 1
Remove 5, insert 10,0           <0, 10>                           DIST 2
Remove 10,insert 11       ask   <11, 0>       (why not 5 too?)
Remove 0, insert 1              <1, 11>                           DIST 3
Remove 11,(ASK)insert 6,12     <12, 6, 1>
Remove 1.   (ASK)               <12, 6>                           DIST 4
Remove 6, insert 7              <7, 12>
Remove 12,insert 13             <13, 7>                           DIST 5
Remove 7.                        <13>
Remove 13,insert 8                <8>                             DIST 6
Remove 8, insert 9,3            <3, 9>                            DIST 7
Remove 9, and done.
--> read off path.

Let's think about why this works.  First, easier: look at running
time. note: only put onto queue if haven't been there before.
So, each spot only put onto queue once, so time is LINEAR in
#spots * #nbrs_per_spot. 

  General principal: Using right ALGORITHM is MUCH more important that 
  issues like: is an array faster than a linked list, etc.

Now ask questions about inductive proof of correctness.  Below is
similar to the proof offered in class.

Shortest paths -- how to PROVE it's shortest.

INDUCTION:  <induction is  VERY important to this course>
how to use here:

INDUCTIVE ASSUMPTION:
  Assume at some point found shortest to all of distance i or less,
    and at this point all of distance i are on queue. Haven't reached
    any of dist i+1 or greater.

BASE CASE:
  i = 0. Found shortest to start.  start on queue. 

PROVE FOR i+1:
  In next sequence of steps, once flush all of distance i from queue,
  will have all of distance i+1 on queue (since these are nbrs
  of nodes of distance i (by defn) and not yet reached (by assumption)
  and all other nbrs HAVE been reached (by assumption)).  [[part 2]]
  Also, will have found shortest path to them: why? (because we got
  them in one more step than nodes of dist i). [[part 1]]. And, haven't
  reached any of dist i+2 or greater (since those aren't nbrs of dist i)
  [[part 3]].

	don't use the array, but instead do an ADT for the maze.  Have
	mark insert a pointer from the node being marked to the node
	doing the marking.

Arrays of strings:
	remember you need to allocate space for the array of pointers AND
	for each string itself.

Common errors:
	These came from previous years recitation nodes
	Can discuss these or some of your favorites after grading.

BUG 1

Description:  Using a while loop in a recursive call.
Behavior:  Infinite loop printing the last word in the list.
Misconception:  Not understanding that the recursion implements the loop.
Code:

void print_in_reverse(list_t l)
{
  while (l->next != NULL)
    print_in_reverse(l->next);
  cout << l->word << " ";
}

Correct (I hope!) Code:

void print_in_reverse(list_t l)
{
  if (l == NULL) return;
  print_in_reverse(l->next);
  cout << l->word << " ";
}

BUG 2

Description:  Misusing strings/pointers.  The bug was that a pointer was
a) being dereferenced when its value was NULL, or
b) being used as a scratch variable when it was pointing to data that
   shouldn't be destroyed (the data in the list).

Also, when the student was debugging this, the student modified
find_replacement to return a constant string instead of NULL (e.g. 'return
"not found"').  This seemed reasonable, and the student modified the test
for null to strcmp(replacement, "not found").  However, this masked the
real bug because the code didn't crash anymore, but rather modified the
memory used to store "not found".

It seemed like the created list doesn't contain what it was created
with.  All the patterns seemed to match the first pattern input by the
user.  When find_replacement returned NULL, we ended up with a
segfault (or bus error, I forget which).  However, when
find_replacement was returning "not found", what really happened was
that the first time find_replacement was called, it returned a pointer
to the constant string "not found".  This was then erroneously used as
the destination for the user's input replacement.  Thus, for example,
"not found" was overwritten with "Danny".  Then whenever
find_replacement was called again, it tried to return "not found", but
"not found" was now "Danny", which doesn't match (a different
instantiation of the constant string) "not found" which is what it was
being tested against.  Thus, "Danny" was used as the replacement for
every pattern.  (Surely the worst possible behavior for a Madlibs program!)


Behavior:  All patterns get replaced by first user input.
Misconception:  Assigning a semantics to a variable without paying
                attention to what is really happening.  Not understanding
                how constant strings are treated internally.
Code:

int main(void){
...
  char *replacement;
  word_t new_word;
...
  while(the_text_file >> new_word) {
    if (new_word[0] != '*') {
      lis = insert_word(lis, new_word);
    } else {
      replacement = find_replacement(pl, new_word);
      if (replacement != NULL) {
        lis = insert_word(lis, replacement);
      } else {
        cout << "Enter a " << (new_word + 1) << ":" << endl;
        cin >> replacement;
        lis = insert_word(lis, replacement);
        pl = insert_word_pair(pl, new_word, replacement);
      }
    }
  }
...