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

[Hans Aberg]

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