-------------
  
  Lists, sequences, list abstraction
  
  (a,b,c)  length 3, head a
  ()       length 0, null head, sometimes called 
  perhaps recursively:
  L = ((a,b) (c,d,f) e)  length 3, head (a,b)
  
  Lists have:
    length
    head (car)  a list element
    tail (cdr)  a list
  
  caar  the head of the head:  (caar L) is a, (caadr L) is c
  
  A sublist is a  sublist of consecutive members.
  a subsequence is made by removing 1 or more elements of original list.
  a prefix is a sublist starting at beginning
  a suffix is a sublist ending at end
  
  Q: how many sublists of list of length L?  (seems O(N^2), no?)
  Q: how many subsequences ditto?            (seems exponential?)
                                             (actually obvious, but why?)
  Q: prefixes and suffixes?                  ( O(N)? )
  
  List elements  have a *position*, and we have *precedes* and *follows*
  
  Lists can be *circular* (modular).
  
  Operations on lists:
  item = head(list)
  list = tail(list)
  item = position[i,list]
  item = next (list)
  item = previous (list)
  l3 = concatenate (l1, l2)  // append, splice
  insert(elt, pos, list)
  pos = lookup (elt, list)
  found = lookup(elt,list)
  delete(elt, list)
  sortedlist = sort(list)
  list = reverse(list)
  elt = pop(list)
  push(elt,list)
  elt = retrieve(i, list)
  elt =first(list)
  elt =last(list)
  n = length(list)
  bool = is_empty(list)
  int = sum(list), prod(list), ..
  eval(list)
  
  etc. ad inf.
  
  The Dictionary DataType
  
  ADT: Dictionary (phone book)  -- your job usually specified this level
  
  Operations:  Insert, Lookup, Delete (these would be public methods or
  the Interface, as Weiss calls it).
  
  Constraints:  elements not repeated -- Dictionary is a SET. 
  
  Abstract Implemention or Data Model: List -- your engineering decision
     about which type of data structure will work. . Hidden from user. In fact you should
     be able to change to a tree and user'd never know.
  
  Data Structure: Linked List, Array, Cursor -- ditto about how to
  implement your strategy of Abstract Implementation: technical
  tradeoffs for you, invisible to the user, hidden in private methods
  and structures.
  
  OK lists, but you know all that:
  Singly-linked list has cells, elements, pointers to ``next'' element.
  usually NULL pointer for last ``next'' pointer signals end.
  Many advantages to having a ``header'' node (so you  don't have to
  treat the empty list differently when inserting, deleting).
  
  
  Lists lend themselves to both iterative and recursive
  algorithms. pure LISP  is all recursive.
  Fig. 6.3. is recursive.  Iterative version goes something like
  (call Otto the Orkin man on this)
  
  int lookup (Etype x, List L) // return position found or 0, why not?
  // List is a pointer to a header cell 
  {
  int pos = 0;
  while(L->next != NULL)  // L never enters NULL, thanks to the header
    { L = L->next;
      pos++;
      if (L->element == x) return pos;
    }
  }
  
  This  iterative style is sometimes
  called ``cdr-ing'' down the list (following the cdr, or
  ``next'' pointer).
  
  See text:  running time for recurrence 
  T(0)  = O(1),
  T(n) = T(n-1) + O(1) 
  yields T(n) = O(n).
  
  The iteration can be implemented by the tail recursion in the
  Fig. 6.3, which a good compiler would actually turn into iteration(!).
  
  
  Deletion, insertion.
  
  Deleting an item from a linked list is usually your first exercise in
  pointers, so I won't insult you by going over it beyond noting that C
  makes it not so easy to write these simple routines since you need to
  affect things outside the scope of the function.  Hence the
  &((*pL)... locutions.  C++ makes it easier (see handout).
  
  Note insertion can be speeded up (to O(1)) if we just push new elt on
  front of list.  If this is a ``write only'' memory, like my list of
  jobs to do, may pay just to write it down first on the list every time
  my wife mentions a job, since I'm never going to read or remove
  anything from the list.
  
  
  Check out table 6.7 for running times for simple sequential search
  (cdr-ing) approach to  various sorts of list.
  
  
  Now note immediately that there's this ``Cursor'' implementation of
  linked lists, which is exactly a linked list implemented in a
  (parallel)  array A:
  
  index elt next
  0      x   5
  1      y   3
  ...
  
  so if a cell is at position i its element is A[i][0] and its
  ``next index'' is A[i][1].  
  
  This is simply a linked list on which you have to do your own storage
  management.  You need a ``free list'' for unusued cells, for instance.
  See Weiss.
  
  Note that worst case lookup is O(n), and average case is O(N/2) =
  O(N).  Not so good: there's faster ways. Think of actually using a
  dictionary: 1. thumb tabs, 2. binary search.  Phonebooks don't have
  the tabs.  These tricks assume though that the list is sorted.  Linear
  search with sorted list means we can quit early if we don't find it,
  but we save only factor of 2 that way.  So what's missing?  WE can't
  just jump into a linked list in the middle! We only point to the first
  one....there's no ``random access''...that is, you can't ``open it to
  the middle!''.
  
  So we're motivated for a more randomly accessible data structure...
  
  Array Implementation:
  
  Win a little, lose a little.  Implement list in an array.  Advantages:
  quickly do pos(i,list).  Dis: Finite length you need to stay aware of,
  and need to compress on delete, expand on insert.  If you are already
  pointing at the position where del or ins will take place those are
  O(1) in linked list, O(N) in array.
  
  Sentinels: 
  Basically put something at the end of an input stream
  or in this case an array so you know when you get to the end.  An
  example is the ``='' at the end of the calculator input stream.
  
  If you compare the code of 6.11 with 6.12, you see that actually
  inserting ``x'' (what you're looking for) at the end of the array
  allows the inner loop to be shorter, since it doesn't have to compare
  against ``length'' every time.
  
  As the box on 303 says, constant factors are important in the
  marketplace if not in the Complexity of Algorithms course.
  
  
  Binary Search:
  
   With array, you can get any elt in time O(1).  Binary
  search motivated by the question ``how many times can you cut
  something in half''?  With a *sorted* array (which takes you NlogN one
  time only) you can do searches in log N time by cutting unsearched
  list in half each time.  If you want to feel the difference between N
  and logN, imagine searching through the phonebook line by line, or
  imagine trying to find a name, given the phone number.  Bin. srch
  obvious: start 1/2 way through sorted array, ask if elt is <, >, or =
  middle element, and depending on answer you quit or (recursively, as
  it were) binary search the correct remaining half-sized array.  So
  logN.  Doesn't have to be recursive, of course! (ex. 6.5.8).
  
  ----------
  STACK ADT (LIFO list).
  
  Operations: push, pop, is-empty, (top), (clear or initialize)
  
  Nota Bene:  example 6.9.
  Infix, prefix (list), postfix (HP calculators, compilers).
  Handout.
  Example:
  
  (14 - 2) / ( 4 + 2) into postfix:
  
  stack            output     why
  (                           push operators
                    14        emit operands
  -                           push operators
  (
  
                    14 2      emit operands
  
                    14 2 -     ): pop down to  (, don't emit ()
  
  /                 14 2 -    push operator
  
  (
  /
                    14 2 - 4  as above...
  +
  (
  /
                    14 2 - 4 2  
  
  /                 14 2 - 4 2 +   ): pop to (,
  
                   14 2 - 4 2 + /   end of input, pop and emit
                                    everything
  
  
  Note: operands in original order (!).
  Note: think about prefix...
  Note: need to be careful about x - y - z and about a + b * c and
  u ^ v ^ w   ....... issues of precedence.
  
  evaluate 14 2 - 4 2 + /
  
  push operands.  When see operator, pop correct number of  operands for
  that operator (here always 2), do the op, push back the result.  Final
  result is on stack when no more input.
  
  input        top of stack V
  14                        14
  2                         2 14 
  -                         12   (notice you gotta get operands in right
                                  order!!)
  4                         4 12
  2                         2 4 12
  +                         6 12
  /                         2      (order important again).
  
  
  OR think about subroutine calls.  You (generally) always return to
  where you were called from (except for jumpouts or throws).  So if you
  keep the callers on a stack you'll always know where to go back
  to. This is  FCS 6.7.  Because so useful, most computers have stack
  commands in their machine language instruction sets.
  
  Stack for recursive calls...
  
        Preorder(Tree t)  // pointer to a tree node, each has info,
                          // a leftchild and rightchild
        {
  (1)     if (t != NULL)
  (2)        { cout << t->info;  //visit the node
  (3)          Preorder(t->leftchild) // ditto its left branch
  (4)          Preorder(t->rightchild) // ditto its right branch
            }
         }
  
  What do you need to know at run-time to be able to return to the right
  state in your program?  Keep a stack, each entry says what we need to
  know about the state of the Preorder() call: namely the value of t,
  which points to the root of the tree that the call is about.  Also we
  need to remember the statement we're executing, so we can return to
  the right spot (especially, return after (3) or return after (4).)
  
  Every time a new call is made at (3) or (4), push the new value of t
  onto the stack with  line number.
  
  When call returns, pop the stack, exposing the value of t and the
  current line number from previous call.
  
               a
             b   c
            d e
  
  not ignoring calls with null trees, get (stack top to right)
  
  (a 3)              a's left 
  (a 3) (b 3)        b's left
  (a 3) (b 3) (d 3)  d's left is NULL
  (a 3) (b 3) (d 4)  d's right is NULL
  (a 3) (b 4)        b's right
  (a 3) (b 4) (e 3)  e's left is NULL
  (a 3) (b 4) (e 4)  e's right is NULL
  (a 4)              a's right
  (a 4) (c 3)        c's left is NULL
  (a 4) (c 4)        c's right is NULL
  done
  
  Similar for all ``activation records''...
  
  
  How implement?  array is easiest...grows from one end.  Keep and
  update top index with ++ for push and -- for pop (or vice-versa).
  Watch not to over- or under-flow.
  
  Also good for linked list since only grows from front.  Top of stack
  is head of list, push
  links into head of list, pop delinks and returns first elt.
  
  ----------
  
  QUEUE  (First In First Out) list
  has enqueue, dequeue, is-empty, clear, is-full....
  
  Central to analysis of (and implementation of) anything involving job
  queues: turnpike gates, grocery check-out, flow of sub-jobs in an OS
  (disk requests, keyboard hits, print jobs, instruction streams,
  etc. etc.).  Queueing theory is a branch of mathematics.  Like to
  predict queue lengths and waiting times under various assumptions of
  service time, inter-arrival time and distribution.  See Weiss for an
  event-driven simulation using queues.  Lots of hardware queueing in
  things like ethernet receivers, network switches, anything having to
  do with message-passing between users or processes.
  
  Linked list implementation: front of queue is best at END of linked
  list.  keep a pointer there.  Easier to add there and delete off
  front, since in both cases have pointer to where the action is.  If
  you delete the end of the list even if you had a pointer to that,
  where is the new end?  Pointers are pointing wrong way.  Dequeue is
  then like a pop.
  
  Another good way is with a ``circular array'' (FCS 6.8.3).  Problem is
  that if you use an array, action at both ends (deleting from one end
  and adding to other) makes the beginning and end of the queue both
  move in some direction in the array (up or down).  The queue crawls
  thru the array, shrinking and growing, but both ends moving in same
  direction.  So obvious thing to do is let array wrap
  around...basically index modulo N where N is the length of the array.
  Keep track of length of queue to keep from wrapping, or check that
  front != rear.
  
  --------
  DEQUEUE
  double-ended queue, used for communications and message-passing
  applications...
  
  
  -----------
  
  Strings
  
  For many of us (who never do anything but edit text, or whose programs
  are only run once or twice and then either published or turned in
  (like researchers and students)), strings are the most common abstract
  data type we deal with.  We match them exactly with grep(1) or edit
  search commands, or approximately with spell-checkers and data-base
  enquiries (as in Yahoo! or Altavista) we insert into them, delete from
  them, translate them into upper case, whatever.  Strings are sequences
  and so we expect the data model list to be relevant.  The underlying
  implementation deserves our interest because chars are 8 bits and
  words are more, usually 32, because string operations need to be fast,
  and because there is actually a fairly limited set of operations that
  are relevant on strings.
  
  Future assigments in 172 might have to do with strings (certainly past
  ones have!).  Thus how we are going to represent them in a dynamic
  application is of interest.    Note that lots of programming languages
  have a string library to let you do these things: create, compare,
  find substrings, etc. tec.
  The text goes into several possibilities
  that don't take a rocket scientist to invent or criticise.  This
  section is good bedtime reading except that analyses like example 6.17
  are useful, if straightforward...make sure you get it.
  
  Topics in order: How to represent strings:
  e.g.
  arrays of chars with \0 at the end (NULL)
  fixed-length array: truncate long strings
  fixed-length array: \0 at end
  fixed-length array: separate length attribute
  linked-list, with several chars in each cell
  chunk of storage with strings stored (null delimited or length
     described),  pointers to each.
  
  Concordance example:  (we did a concordance last year).  Makes
  ref. to the Binary Search Tree we haven't seen yet.
  
  Linked lists, inefficient unless you start packing chars into
  fields. ugh. Point here is the nice little computation of  the
  expected number of bytes for string storage under different
  assumptions of probability of string length and number of chars you
  can put in a cell (if CPC is too  long, waste unused space: if too
  short, waste pointer space).
  
  The mass storage idea is something like a big random access memory for
  all the words you want to store.  Not bad, but have to do storage
  management perhaps (box) and it could be wasteful of space compared to
  trie.
  
  
  Example 6.18 is a kind of weird one in which we're building a
  concordance or dictionary or word bank of some sort out of text we are
  reading, and we have a big chunk of storage allocated to store words
  in.  The first time we see a word we copy its chars into the array and
  remember where we did it, say starting at X1458: in fact address or
  index X1458 becomes that word's unique identifier, and we use that to
  refer to it.  So suppose we see a new word and want to know if it is
  already in our storage?  We're stuck, all we have is addresses for
  existing words and unless we do something smart we'll have to compare
  the incoming word with all the words at all those addresses.  Sort of
  like trying to find someone's name by searching for his phone number
  in the phonebook.  So this motivates ways to organize data sets for
  fast search, which we'll get to when we do trees.
  
  Tries:
  
  However, a very common technique for storing words (used in compiler
  symbol tables, dictionaries, any number of places) is the trie, which
  is from reTRIEval.  The idea is simple..cf. p. 233 of FCS.  Represent
  your word set as a tree: on one level are all first letters of words
  you know.  On next level, under every first letter, are all the
  letters that appear as 2nd letters.  When you get to a word in the set
  you mark it.  To find if a word is in the set, just search down the
  tree for its letters in an obvious way.  Here is a trie for { boy ,
  bar, bat, bath, car}
  
                        start
                   /          \
                  b             c
                /   \             \
              a       o            a
            /  \       \           |
          t*     r*     y*         r*
          |
          h*
  
  
  ---------- Code Appendix, or why reference parameters are good for you
  
  /* this is a C program */
  
  #include 
  
  
  /* This  is code from FCS, page  296;  it is mainly designed to support
  a recursive proof of correctness, if you ask me.  It does more
  than one usually thinks of in a list implementation: it is really
  implementing a SET in which you can't have the same element twice.
  Also it fails in the elegance department because of all that descructive
  pointer-changing.  Most List ADTs only have insert defined to work
  at some "Current Position".
  */
  
  typedef struct ListNode *List;
  
  void printlist(List);
  
  struct ListNode
   {int element;
   List next;
  };
  
  
  void insert (int x, List *pl)
  {
  
    if ((*pl) == NULL)
        {
         (*pl) = (List) malloc(sizeof (struct ListNode));
         (*pl)->element = x;
         (*pl)->next = NULL;
         }
  else if (x != (*pl)->element)
       insert(x, &((*pl)->next));
  }
  
  void printlist(List l)
  {
  if (l == NULL) printf( "List Empty!\n");
  else 
    {
           while(l != NULL)
        { printf("%d \n", l->element);
        l = l->next;
        }
    }
  }
  
  void main()
  {
  List  L;
  
  L = NULL;
  
  insert ( 1,&L);
  insert ( 2,&L);
  insert ( 3,&L);
  insert ( 3,&L);
  insert ( 2,&L);
  
  printlist(L);
  
  /* prints
  1
  2
  3
  */
  
  }
  
  
  ------------
  
  /* this is a C++ program */
  
  #include 
  
  
  typedef struct ListNode * List;
  
  struct ListNode
   {int element;
   ListNode *next;
  };
  
  void printlist( List);
  
  void insert (const int x,  List & l)
  
  //straight translation of 
  // FCS Fig. 6.5 p. 296 into C++-ish  & (reference) style.  Nicer, eh?
  
  {
  ListNode  *tmp;
    if (l == NULL)
        {
          l  = new ListNode;  //puts at end
          l->element = x;
          l->next = NULL;
        }
     else  if (l->element  != x)
        insert(x,  l->next);
  }
  
  
  void printlist( List l)
  
  // here is an iterative approach
  // l is modified, call by value is what we want.
  
  {
  if (l == NULL) cout << "List Empty!\n";
  
  else 
   {
        while(l != NULL)
        { cout << l->element << '\n';
        l = l->next;                   // "cdr-ing" down the list
        }
    }
  }
  
  void main()
  {
    List L; 
  
  L = NULL;  // the null list
  
  insert ( 1,L);
  insert ( 2,L);
  insert ( 3,L);
  insert ( 3,L);
  insert ( 2,L);
  
  printlist(L);
  
  /* prints
  1
  2
  3
  */
  }
  
  /// now iterative binary search...
  
  #include 
  
  #define SIZE 512
  
  
  
  
  int binsrc(int *arr, int x, int N)
  {
  int low, mid, hi;
  low = 0;
  hi = N-1;
  printf("\n x: %d", x);
  
  while (low <= hi)    /*  strictly less than (<)  won't work! */
    { 
      mid = (int) (hi + low)/2;
      printf("\n    mid: %d", mid);
      
      if (x < arr[mid])
         hi = mid - 1;
      else if (x > arr[mid])
         low = mid +1;
      else 
        {printf("\n found it.");
        return;
        }
    }
  }
  	
  
  void main()
  {
  int sortedlist[SIZE];
  int i;
  int x, fnd;
  
  for(i = 0; i