
NOTE: Most of this is now covered in the PicklingTools documentation
      in http://www.picklingtools.com:  This discussion below is
      correct, but out-of-date.  Refer to the web site instead.


  The OpenContainers philosophy is that the code is part of the
documentation.  So, it's very important that we describe the
implementations so you can understand what's happening behind the
scenes.

 Array:

  The array is just an extension of C-style arrays, but the OpenContainers
Array manages its own memory.  For Example:

  int length;  // Length of array

  int* c_array = (int*)malloc(sizeof(int)*length); // C-style allocate
  for (int ii=0; ii<length; ii++) 
    c_array[ii] = ii;                              // C-style initialize
  for (int ii=0; ii<length; ii++) 
    cout << c_array[ii] << " ";                    // C-style access
  free(c_array);                                   // C-style deallocate

  int* cc_array = new int[length];                 // C++-style allocate
  for (int ii=0; ii<length; ii++) 
    cc_array[ii] = ii;                             // C++-style access
  delete [] cc_array;                              // C++-style deallocate

  Array<int> oc_array;                             // OC style allocate
  for (int ii=0; ii<length; ii++) 
    cc_array[ii].append(ii);                       // OC style initialize
  // When oc_array out of scope, automatically freed: OC style deallocate



 HashTable:  

  A Hash table manages key-value pairs.  You insert data by key into
the table that you may delete by key or lookup by key at a later time.
The typical example of this is a phone book: the names are the "keys"
and the "values" are the phone numbers.  As you make new friends, you
insert new name/phone-number pairs into your phone book: "Hi Fred,
give me your number so I can call you".  You lookup phone-numbers by
name: "What was Fred's phone number again?".  And when people move,
you delete phone numbers.  "Fred's leaving town, I'll take him out of
the phone book".

   HashTable<int_u8> phonebook;
   phonebook.insertKeyAndValue("Fred", "505-298-8855");// Add Fred
   string key = phonebook["Fred"];                     // Lookup Fred's number
   phonebook.remove("Fred");                           // Fred's moving

  A Hash table works by turning a complicated key into a small integer
using something called a "HashFunction".  With the small integer
"representing" the value, we use that to index quickly into an array.
For example, "Fred" might be turned into:

   "F" (6th letter of the alphabet) =  6 +
   "r" (18th letter of the alphabet)  18 +
   "e" (5th letter of the alphabet)    5 +
   "d" (4th letter of the alphabet)    4 
                                     ----
                                      37

With that small integer, we look into an array to see if the 
item is there.

  Is "Fred" at array space 37?

  Array<int_u4> a;
  a[37].key == "Fred"?

 Well, most of the time, the array we have is very small (to save
memory), typically 8 elements.  How can we look at the 37th element
when the array is only 8 elements?  We use modulo arithmetic based on
the size of the array.  What does that remain?  We divide 37 by 8 and
use the remainder as the index.  37 / 8 = 4 with a remainder of 5.

  int_u4 hash_value = HashFunction("Fred");  
  // hash_value has a value of 37

  hash_value = hash_value % 8; // 8 is the size of the array  
  // Get a value between 0 and 7, the remainder of 37 % 8

  a[hash_value].key == "Fred"?


 So, if Fred is in the table, he'll be at array element 5.  That's
basically how all insertions work: Find the array space, and put it
there.  Deletions, find the array place and take it out.  Lookup, find
the array place and see if it's there.

 Problems with Hash Tables:

 As you probably guessed, there are problems if two people happen
to have the same value.  If, for instance, "Derf" comes along, he just
happens to "hash" to the same value.

   "D" (4th letter of the alphabet)    4 
   "e" (5th letter of the alphabet)    5 +
   "r" (18th letter of the alphabet)  18 +
   "f" (6th letter of the alphabet) =  6 +
                                     ----
                                      37 
[TODO: More here]
 

AVLTrees:

  A common complaint about the HashTables is that the iterator goes
through the items in "odd" orders, i.e., seemingly random.  

  HashTableIterator it(phonebook);
  while (it()) {
     cout << it.key() << " ";  // Prints out "hank derf fred", HUH?
  }

Why DOESN'T it print out "derf" "fred" "hank" as expected?  They are
printed out in order of the buckets, which is based on the order
generated by the HashFunction ... and that's not necessarily ordered.
Basically, the HashTables have no "requirement" about data being
ordered: In fact, it would really slow down the hashtable to try to
implement this.  It simply isn't endemic to the implementation to be
ordered: it's the price we pay: we have fewer requirements on our
keys, we get great speed, but we don't get ordered data.

Since most data has a natural order (strings, ints, reals) [Note:
complex data is not inherently ordered, but many people order it by
magnitude: sqrt(real**2 + imag**2)], it's very useful to be able to
iterate through data in sorted order.

  The AVLTree is plug-in compatible with HashTables: they have the
exact same interface.  The difference: AVLTress doesn't require a
"HashFunction" but rather that the keys to be ordered.  For AVLTree,
the keys are strings, and they are ordered.  Using the phone example:

   AVLTree<string> phonebook;
   phonebook.insertKeyAndValue("Fred", "505-298-8855");// Add Fred
   string key = phonebook["Fred"];                     // Lookup Fred's number
   phonebook.remove("Fred");                           // Fred's moving


The difference now is that rather than calling "HashFunction" on keys,
we call "<" to compare keys (that's "less-than".) [NOTE: When
comparing strings, you get "lexographic" order, which is mostly how
you would put things in the Dictionary so that "a" < "aa", "derf" <
"fred", etc.  That ordering looks weird, though when applied to
numbers: "1" < "11" but "100" < "2" because, like in the dictionary,
the single digit "1" becomes before the single digit "2", so that "100"
comes before "2"].  This is a long winded way of saying:

  AVLTreeIterator<string> it(phonebook);
  while (it()) {
     cout << it.key() << " ";  // Prints out "derf fred hank" as expected
  }
  
Prints out as expected.

  But, what is an AVLTree?  An AVLTree is named after the Russians who 
discovered its structure: Adel'son-Velskii and Landis.


  AVLHash:

  The AVLHash is completely compatible with the HashTable: it has the
same restructions/requirement on keys and values.  The only
difference is how well it scales.

 The AVLHash is an answer to the main problem with HashTables
vs. AVLTrees: HashTables are fantastic for "the expected" amount of
data, but can degenerate into slow, linear searches if we are unlucky
or have too much data.  AVLTrees never degenerate into slow linear
searches, (and in fact bounded by 1.4*log(n)), but aren't as fast as
HashTables.

 What we want is extendible hashing: a hashtable that grows BUT
WITHOUT HAVING TO REHASH: If you want to "grow" a HashTable, typically
you have to reahash every single element in the old table to insert it
into the new table: thus, a single operation becomes linear: (every
item in the table has to be copied into the new table).  The main
problem, in my book, is that a rehash is potentially a very expensive
operation, and not bounded.

 The kernel for the solution comes from an idea from the Icon
Programming Language (a string based language from the University of
Arizona).  In Icon, the Hashtables store an extra field in buckets:
the full result of the HashFunction (recall that HashTables typically
chop the hash function to fit the number of buckets) so that rather
than do full string compares for collisions in the table, you do an
integer compare of hash values to see if you even NEED to do a string
compare.  

 Thus, the buckets of an AVLHash are formed by an AVLTree.  In a hash
table, it was easy to find your bucket: go to a particular element of
an array.  With an AVLHash, you have to "search" through a binary
search tree to get to your bucket.  It's not as fast, but it is very
fast for one reason: each compare to get to your bucket is an INTEGER
compare of hash values NOT compares of keys (which can be very
expensive). 

  If you look at the "timings" directory, you will see that AVLHash
keeps up with HashTable for small amounts of data, and really creams
it so large amounts of data.

 The general recommendation: use Hashtables if you know how much
data to expect, use AVLTrees if you want ordered iteration, and
use AVLHashes when you want



VAL/TAB/STR:

  If you want dictionaries like Python, or OpalValues like Midas 2k,
or tables/containers like Icon, the Val/Tab/Str triplet helps you
write code that looks like Python.

Vals are containers for any numeric type (int, real), tables (Tabs) or
strings.  Think of it as a union or a container for a single thing,
but it's also easy to get stuff out.

  Val v;              // empty
  cerr << v << endl;  // Prints as None (similar to Python)

  Val v1 = 1.0;       // Put a real value inside
  cerr << v1 << endl; // Prints it!
  real_8 v1_out = v1; // Get the value back out

  int_4 int_out = v1; // Get the value out, but convert to an int_4!

  cerr << v1.tag << endl; // Type tag: tells you what's inside
                          
  Val v2 = "hello";   // Put a string in
  
  Val vt = Tab();     // Put an empty tab in

Tabs allow you to contain multiple Vals, indexed by a key (a string
or Str).  Things are taken out by looking up via the key.

  Tab t;
  t["1"] = "hello";
  t["2"] = 1.0;
  t["3"] = 8;

  Val& v = t["1"];   // Get out by reference:  Don't HAVE to copy!
  Str s  = t["1"];   // Get out as a string
  int i  = t["1"];   // Probably get 0:"hello" doesn't convert well to an int

  int me = t["2"];   // Equivalent to: Val& vv = t["2"]; int me = vv;


Str are simply OCStrings (a subset of the STL string, but faster
in many contexts than the STL strings).  Everything in a Val
can always convert itself to a Str.

  Val vv = 1.0;
  Str ss = vv;

  Val vvv = 1024;
  Str sss vvv;


Of course, like Python dictionaries, the most useful feature
of Tabs is the ability to contain recursive Tabs.

  Tab t;
  t["1"] = "hello";
  t["2"] = 1.0;
  t["3"] = 8;

  Tab sub;
  sub["100"] = 100;
  
  t["subtable"] = sub; // make a copy and insert the table

  // Look up value in subtable
  Tab& the_sub_table = t["subtable"];  // Note: not a copy!  By reference!
  Val& v = the_sub_table["100"];
  int final = v;

  // Although the above works, you probably would prefer to do:
  int final = t["subtable"]["100"];    // Equivalent to above!

  // Most everything can convert to Strs and ints/reals,
  // Trying to convert a non-Tab to a Tab throws a logic_error
  try {
     Val vv = 1.0;
     Tab& t = vv;
  } catch (const logic_error& e) {
     // vv is a real_8!!! Can't be used a table!
     cerr << e.what() << endl;
  }

  // If you tried something similar in Python, you'd
  // get a "unsubscriptable object" exception

Iterating through the tables is VERY EASY:

  Tab t = ...;
  for (It ii(t); ii(); ) {
    const Str& key = ii.key();
          Val& value = ii.value();

    cerr << key << " " << value << endl;
  }

Notice that keys are given to you by const& (so you can't change them)
and values are given to you by & (so you can change them!).  The order
of iteration is indeterminate (unless you change Tab's implementation
to AVLTree instead of AVLHash: then you get the keys in sorted order).

If you want to pass Tabs between processes on your machine, you
can Serialize/Deserialize to/from a piece of memory.

  // Send end
  Tab t = ...;
  size_t bytes = BytesToSerialize(t);
  char* buff = new char[bytes];
  Serialize(t, buff);

  SENDBYTES_OVER_NETWORK(buff, bytes)

  // Receive end
  
  rcv_bytes = GETBYTES;
  RECEIVEBYTES_FROM_NETWORK(buff, rcv_bytes)

  Val v;
  Deserialize(v, buff);
  Tab& t = v;          // Will throw exception if not a Tab

  ... and do stuff with Tab! ....

