CS 61B: Lecture 23
                               Monday, March 18

DICTIONARIES (continued)
============

Resizing Hash Tables
--------------------
Sometimes we can't predict in advance how many items we'll need to store.  If
the load factor n/N (items per bucket) gets too large, we are in danger of
losing constant-time performance.

One option is to enlarge the hash table when the load factor becomes too large
(typically larger than 0.75).  Allocate a new table (typically at least twice
as long as the old), then walk through all the items in the old table and
_rehash_ them into the new.

Take note:  you CANNOT just copy the linked lists to the same buckets in the
new table, because the hash functions of the two tables will certainly be
incompatible.  You have to rehash each item individually.

You can also shrink hash tables (e.g., when n/N < 0.25) if you think the
freed-up memory will benefit something else.  (Practical examples of this being
worth the effort are rare.)

Obviously, an operation that causes a hash table to resize itself will take
more than O(1) time; nevertheless, the _average_ over the long run is still
O(1) time per operation.

Transposition Tables:  Using a Dictionary to Speed Game Trees
-------------------------------------------------------------
An inefficiency of unadorned game tree search is that some grids can be reached
through many different sequences of moves, and so the same grid might be
evaluated many times.  To reduce this expense, maintain a hash table that
records previously encountered grids.  This dictionary is called a
"transposition table."  Each time you compute a grid's score, insert into the
dictionary an item whose key is the grid and whose element is the grid's score.
Each time the minimax algorithm considers a grid, it should first check whether
the grid is in the transposition table; if so, its score is returned
immediately.  Otherwise, its score is evaluated recursively and stored in the
transposition table.

Transposition tables will probably not help you with your project, because they
only become useful when you can search to a depth of at least four ply, which
you won't be able to do in five seconds.

After each move is taken, the transposition table should be emptied, because
you will want to search grids to a greater depth than you did during the
previous move.

STACKS
======
A stack is a crippled list.  You may manipulate only the item at the top of the
stack.  The main operations:  you may "push" a new item onto the top of the
stack; you may "pop" the top item off the stack; you may examine the "top" item
of the stack.  A stack can grow arbitrarily large.

 | |          | |            | | -size()-> 2 |d| -top()-> d     | |
 |b| -pop()-> | | -push(c)-> |c|             |c|                | | -top()--
 |a|    |     |a|            |a| -push(d)--> |a| --pop() x 3--> | |        |
 ---    v     ---            ---             ---                ---        v
        b                                                   StackEmptyException

public interface Stack {
  public int size();
  public boolean isEmpty();
  public void push(Object element);
  public Object pop() throws StackEmptyException;
  public Object top() throws StackEmptyException;
}

In any reasonable implementation, all these methods run in O(1) time.  A Stack
is easily implemented as a List, using just the front(), insertFront(), and
removeFront() methods.

Why talk about Stacks when we already have Lists?  Mainly so you can carry on
discussions with other computer programmers.  If somebody tells you that
an algorithm uses a stack, the limitations of a stack give you a hint how
the algorithm works.

Sample application:  Verifying matched parentheses in a String like
"{[(){[]}]()}".  Scan through the string character-by-character.  When you
encounter a lefty - '{', '[', or '(' - push it onto the stack.  When you
encounter a righty, pop its counterpart from atop the stack, and check that
they match.  If there's a mismatch or exception, or if the stack is not empty
when you reach the end of the string, the parentheses are not properly matched.

QUEUES
======
A queue is also a crippled list.  You may read or remove only the item at the
front of the queue, and you may add an item only to the back of the queue.  The
main operations:  you may "enqueue" an item at the back of the queue; you may
"dequeue" the item at the front; you may examine the front item ("front").
Don't be fooled by the diagram; a queue can grow arbitrarily long.

 ===              ===               ===               === -front()-> b
 ab. -dequeue()-> b.. -enqueue(c)-> bc. -enqueue(d)-> bcd
 ===     |        ===               ===               === -dequeue() x 3--> ===
         v                                                                  ...
         a                                  QueueEmptyException <-front()-- ===

Sample Application:  Printer queues.  When you submit a job to be printed at
a selected printer, your job goes into a queue.  When the printer finishes
printing a job, it dequeues the next job and prints it.

public interface Queue {
  public int size();
  public boolean isEmpty();
  public void enqueue(Object element);
  public Object dequeue() throws QueueEmptyException;
  public Object front() throws QueueEmptyException;
}

In any reasonable implementation, all these methods run in O(1) time.  A Queue
is easily implemented as a List with a tail pointer.

DEQUES
======
A deque (pronounced "deck") is a Double-Ended QUEue.  You can insert and remove
items at both ends.  You can easily build a deque out of any of the lists we've
studied this semester.  You just have to add removeFront() and removeBack()
methods (Goodrich and Tamassia call them removeFirst() and removeLast() ), and
deny applications direct access to list nodes.  Obviously, deques are less
powerful than lists whose list nodes are accessible.