Re: [chuck-users] implementing a set (was object / class hacking)

30 Sep 2009

      Hans:

To simultaneously stand my ground and display my ignorance:

I've written several flavors of hash tables in my life, but I'm not  
sure how the Stroustrup code sample helps in this case.  If you are  
suggesting that I hack the Chuck source code, you should know that I  
do entertain such ideas from time to time, but I usually come back to  
my senses within 25::samp -- it's just not on my list of priorities.

A "written entirely in ChucK" solution -- albeit non-optimal in  
execution speed -- is good enough for my needs.  I'm more into  
optimizing my days than my milliseconds.

Thanks, though.

- Rob

On 30 Sep 2009, at 14:01, Hans Aberg wrote:
...
On 30 Sep 2009, at 22:12, Robert Poor wrote:
...
To clarify: I'd like to implement a set for storing a collection of  
homogenous objects.  Specifically, I need to be able to test for  
the presence of an object in the set, add an object to the set (if  
not already present), delete a object from the set, and iterate  
over all the objects in the set.  This last requirements, sadly,  
eliminates Chuck's "associative arrays".
It's worth pointing out that:
arbitraryobject.toString()
will generate a string of the form "ClassName:hexLocation".   
Assuming that Chuck NEVER (ever) relocates a live object in memory  
(Chuck has a reference counting GC, not a copying GC, true?), that  
string could be useful as a unique ID.  But Chuck lacks the string  
operations to reduce a string into a hash key.
Bjarne Stroustrup, "The C++ Programming Language", 3.1.3, has a  
simple hash function:
name* look(const char* p, int ins=0);
name* insert(const char* s) { look(s, 1); }
struct name {
  char* string;
  name* next;
  double value;
}
const TBLSZ = 23;
name* table[TBLSZ];
name* look(const char* p, int ins=0) {
  int ii = 0;
  const char* pp = p;
  while (*pp) ii = ii<<1 ^ *pp++; // Hash function using eor: ii<<1;  
ii ^= *pp++;
if (ii < 0) ii = -ii; // Reduce to array range.
  ii %= TBLSZ;
for (name* n = table[ii]; n; n = n->next)  // Search
    if (strcmp(p, n->string) == 0)  return n;
if (ins == 0)  error("name not found");
name* nn = new name; // Insert
  nn->string = new char[strlen(p) + 1];
  strcpy(nn->string, p);
  nn->value = 1;
  nn->next = table[ii];
  table[ii] = nn;
  return nn;
}
Hans