object / class hacking

Robert Poor

29 Sep 2009 29 Sep '09

8:13 p.m.

Chucksters: Three questions in one message (generally a bad idea, but they're short): [1] Accessing class name from an object I seem to recall seeing a way to get an object to yield its class name, if only for printing. But I haven't been able to locate the e- mail thread where that was discussed. Was I hallucinating? (I really only want this for debugging, but if it's a supported function, it may be useful for dispatching on class type.) [2] initializing an object Is there a subclassable method that is called when you instantiate an object? or do have to instantiate then initialize manually, as in: public class Foo { Controller @ c; fun void init(Controller c) { c @=> this.c } } Foo foo; foo.init(x); [3] "natural" sorting of objects Is there any attribute of an object that you can reliably use as a sort key? I ask because I want to speed up searching of an array of objects (e.g. to see if an object is already present). As I understand it, I can't use a hash array since there are no iterators. I guess the question should be: what's the fastest way to maintain a *set* of objects (i.e. a collection in which an object may only appear once) with the usual operations for insertion, deletion and iteration? TIA. - rob

Show replies by date

Kassen

29 Sep 29 Sep

8:39 p.m.

Robert;

...

[1] Accessing class name from an object

I seem to recall seeing a way to get an object to yield its class name, if only for printing. But I haven't been able to locate the e-mail thread where that was discussed. Was I hallucinating? (I really only want this for debugging, but if it's a supported function, it may be useful for dispatching on class type.)

Just try to "print the object", like this; Gain foo; //clearly a object <<< foo >>>;

...

[2] initializing an object

Is there a subclassable method that is called when you instantiate an object? or do have to instantiate then initialize manually, as in:

Not within ChucK as such, though the code that is in the body of the object itself (and outside of member functions) will run at instantiation, which seems to come down to a solution of your issue? This is provided we wrote the object ourselves, or extended it from a ready made one. Sadly UGens can't be extended in a working way.

...

[3] "natural" sorting of objects

Is there any attribute of an object that you can reliably use as a sort key? I ask because I want to speed up searching of an array of objects (e.g. to see if an object is already present). As I understand it, I can't use a hash array since there are no iterators.

Not within ChucK right now that I know of.

...

I guess the question should be: what's the fastest way to maintain a *set* of objects (i.e. a collection in which an object may only appear once) with the usual operations for insertion, deletion and iteration?

This sounds tricky, especially for the general case of sets that might include many different types of objects. You could keep them in a "set" by having a array of type Object and appending and assigning to that -I think- but I see no way to remove duplicates as I don't think the "==" operator covers objects in that general a way. I'm really not sure here. Erm.... good questions! ;-) Kas.

Hans Aberg

30 Sep 30 Sep

5:03 a.m.

On 30 Sep 2009, at 02:13, Robert Poor wrote:

...

I guess the question should be: what's the fastest way to maintain a *set* of objects (i.e. a collection in which an object may only appear once) with the usual operations for insertion, deletion and iteration?

For lookup tables, if you do not need to compare the keys, a hash map is fastest - time complexity O(1), otherwise a balanced tree (like C++ std::map) - complexity O(log n). There might be some C++ hash map classes at http://www.boost.org/. But if n is small and use not too intense, just about any container will do. Hans

Robert Poor

8:26 a.m.

Hans: Of course I'd love to use a hashmap. But how do you get one in Chuck? AFIK, the existing chuckain "hash array" lacks a means to iterate over its contents. - Rob On 30 Sep 2009, at 02:03, Hans Aberg wrote:

...

On 30 Sep 2009, at 02:13, Robert Poor wrote:

...
I guess the question should be: what's the fastest way to maintain a *set* of objects (i.e. a collection in which an object may only appear once) with the usual operations for insertion, deletion and iteration?

For lookup tables, if you do not need to compare the keys, a hash map is fastest - time complexity O(1), otherwise a balanced tree (like C++ std::map) - complexity O(log n). There might be some C++ hash map classes at http://www.boost.org/. But if n is small and use not too intense, just about any container will do.

Hans

Stefan Blixt

9:31 a.m.

More importantly, how do you get a nice hash key? You can iterator over contents on a simple array, store the keys there like: string hashKeys[]; That's what you usually use to iterate over when doing hashmaps anyway (if you want to iterate over contents what do you need the hash for?) Here's a pseudocode attempt at a hashset (I keep forgetting the subtleties of @ and the autogrowing array syntax is missing from the annoying manual): class HashElement { fun int hashCode(); } class HashSet { HashElement elements[][]; fun int contains(HashElement @ element) { elements[element.hashCode()] @=> HashElement @ hashedList[]; for (0 => int i; i < hashedList.cap(); i++) { if (hashedList[i] == element) { return 1; } } return 0; } fun void insert(HashElement @ element) { elements[element.hashCode()] @=> HashElement @ hashedList[]; if (hashedList == null) { HashElement[1] @=> hashedList; hashedList @=> elements[element.hashCode()]; } element +=> hashedList[]; // keep forgetting the syntax for autogrowing the array } } The elements you want to put in the hash set need to extend HashElement. /Stefan 2009/9/30 Robert Poor

...

Hans: Of course I'd love to use a hashmap. But how do you get one in Chuck? AFIK, the existing chuckain "hash array" lacks a means to iterate over its contents.

- Rob

On 30 Sep 2009, at 02:03, Hans Aberg wrote:

On 30 Sep 2009, at 02:13, Robert Poor wrote:

I guess the question should be: what's the fastest way to maintain a *set* of objects (i.e. a collection in which an object may only appear once) with the usual operations for insertion, deletion and iteration?

For lookup tables, if you do not need to compare the keys, a hash map is fastest - time complexity O(1), otherwise a balanced tree (like C++ std::map) - complexity O(log n). There might be some C++ hash map classes at http://www.boost.org/. But if n is small and use not too intense, just about any container will do.

Hans

_______________________________________________ chuck-users mailing list chuck-users@lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/chuck-users

-- Release me, insect, or I will destroy the Cosmos!

Andrew C. Smith

9:49 a.m.

it would be hashedList << element; and you have to declare hashedList as hashedList[0] (not []) or else you get a null pointer. For reference, it's in the release notes, and I believe the examples (under examples/array/array_dynamic.ck or something). -Andrew 2009/9/30 Stefan Blixt :

...

More importantly, how do you get a nice hash key?

You can iterator over contents on a simple array, store the keys there like:

string hashKeys[];

That's what you usually use to iterate over when doing hashmaps anyway (if you want to iterate over contents what do you need the hash for?)

Here's a pseudocode attempt at a hashset (I keep forgetting the subtleties of @ and the autogrowing array syntax is missing from the annoying manual):

class HashElement {     fun int hashCode(); }

class HashSet {     HashElement elements[][];

    fun int contains(HashElement @ element) {         elements[element.hashCode()] @=> HashElement @ hashedList[];         for (0 => int i; i < hashedList.cap(); i++) {             if (hashedList[i] == element) {                 return 1;             }         }         return 0;     }

    fun void insert(HashElement @ element) {         elements[element.hashCode()] @=> HashElement @ hashedList[];         if (hashedList == null) {             HashElement[1] @=> hashedList;             hashedList @=> elements[element.hashCode()];         }         element +=> hashedList[]; // keep forgetting the syntax for autogrowing the array     } }

The elements you want to put in the hash set need to extend HashElement.

/Stefan

2009/9/30 Robert Poor

...
Hans: Of course I'd love to use a hashmap. But how do you get one in Chuck? AFIK, the existing chuckain "hash array" lacks a means to iterate over its contents. - Rob On 30 Sep 2009, at 02:03, Hans Aberg wrote:

On 30 Sep 2009, at 02:13, Robert Poor wrote:

I guess the question should be: what's the fastest way to maintain a *set* of objects (i.e. a collection in which an object may only appear once) with the usual operations for insertion, deletion and iteration?

For lookup tables, if you do not need to compare the keys, a hash map is fastest - time complexity O(1), otherwise a balanced tree (like C++ std::map) - complexity O(log n). There might be some C++ hash map classes at http://www.boost.org/. But if n is small and use not too intense, just about any container will do.

Hans

_______________________________________________ chuck-users mailing list chuck-users@lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/chuck-users

-- Release me, insect, or I will destroy the Cosmos!

_______________________________________________ chuck-users mailing list chuck-users@lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/chuck-users

Hans Aberg

9:52 a.m.

On 30 Sep 2009, at 14:26, Robert Poor wrote:

...

Of course I'd love to use a hashmap. But how do you get one in Chuck? AFIK, the existing chuckain "hash array" lacks a means to iterate over its contents.

You want something like std::set, right? ONe can use the chuck associative arrays as follows: int set[0]; 1 => set["hello"]; 1 => set["world"]; if (set["this"] == 1) <<< "ok" >>>; else <<< "nope" >>>; if (set["hello"] == 1) <<< "ok" >>>; else <<< "nope" >>>; I got the printout: $ chuck set.ck "nope" : (string) "ok" : (string) It means that chuck treats an empty index as returning the int 0. So by setting the other entries to a non-zero value, one can make use of that implementation. Insertion and deletion is easy. For deletion, just set the value to 0 - it will remain there, but checks will say it is empty. I couldn't find iterators for these associative arrays. I think they are implemented using std::map, though. Hans

Stefan Blixt

10:08 a.m.

I don't think there are iterators for associative arrays, and cap() keeps returning zero even though you've added stuff. /Stefan On Wed, Sep 30, 2009 at 3:52 PM, Hans Aberg wrote:

...

On 30 Sep 2009, at 14:26, Robert Poor wrote:

Of course I'd love to use a hashmap. But how do you get one in Chuck?

...
AFIK, the existing chuckain "hash array" lacks a means to iterate over its contents.

You want something like std::set, right? ONe can use the chuck associative arrays as follows:

int set[0];

1 => set["hello"]; 1 => set["world"];

if (set["this"] == 1) <<< "ok" >>>; else <<< "nope" >>>;

if (set["hello"] == 1) <<< "ok" >>>; else <<< "nope" >>>;

I got the printout: $ chuck set.ck "nope" : (string) "ok" : (string)

It means that chuck treats an empty index as returning the int 0. So by setting the other entries to a non-zero value, one can make use of that implementation.

Insertion and deletion is easy. For deletion, just set the value to 0 - it will remain there, but checks will say it is empty.

I couldn't find iterators for these associative arrays. I think they are implemented using std::map, though.

Hans

_______________________________________________ chuck-users mailing list chuck-users@lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/chuck-users

-- Release me, insect, or I will destroy the Cosmos!

Andrew C. Smith

10:16 a.m.

But with this, you can't easily return the contents (which in this case is the list of names, not the "contents" in the normal sense) of the associative arrays. If you can iterate, deleting is pretty easy. The problem there is just that everything has to be re-sorted. Without easy pointers, it's much more difficult to insert something into a sorted list, but luckily an array is basically just a series of pointers (right?). If you had a sortable list (like note numbers of a chord or something) then you could drop the search function into the middle and get to your destination quite a bit faster. If you wanted to hack the array class to create .insert() and .remove() methods (where .remove() keeps the order without any null pointers) then please, do share. It could probably be done in ChucK sans-hacking, but where's the fun in that? What is the difference exactly between .cap() and .size() ? Andrew On Wed, Sep 30, 2009 at 9:52 AM, Hans Aberg wrote:

...

On 30 Sep 2009, at 14:26, Robert Poor wrote:

...
Of course I'd love to use a hashmap. But how do you get one in Chuck? AFIK, the existing chuckain "hash array" lacks a means to iterate over its contents.

You want something like std::set, right? ONe can use the chuck associative arrays as follows:

int set[0];

1 => set["hello"]; 1 => set["world"];

if (set["this"] == 1) <<< "ok" >>>; else <<< "nope" >>>;

if (set["hello"] == 1) <<< "ok" >>>; else <<< "nope" >>>;

I got the printout: $ chuck set.ck "nope" : (string) "ok" : (string)

It means that chuck treats an empty index as returning the int 0. So by setting the other entries to a non-zero value, one can make use of that implementation.

Insertion and deletion is easy. For deletion, just set the value to 0 - it will remain there, but checks will say it is empty.

I couldn't find iterators for these associative arrays. I think they are implemented using std::map, though.

Hans

_______________________________________________ chuck-users mailing list chuck-users@lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/chuck-users

Hans Aberg

2:02 p.m.

On 30 Sep 2009, at 16:16, Andrew C. Smith wrote:

...

But with this, you can't easily return the contents (which in this case is the list of names, not the "contents" in the normal sense) of the associative arrays.

Robert did not tell if he wanted lookup table or something like C++ std::set, which just stores the elements.

...

If you can iterate, deleting is pretty easy. The problem there is just that everything has to be re-sorted. Without easy pointers, it's much more difficult to insert something into a sorted list, but luckily an array is basically just a series of pointers (right?).

An array in C is a contiguous memory chunk, at least address wise. In C ++, std::vector is such a chunk which can dynamically reallocated. A hash map typically has such an array, where each entry is a singly linked list. It average speed is proportional to the average depth of the lists.

...

If you had a sortable list (like note numbers of a chord or something) then you could drop the search function into the middle and get to your destination quite a bit faster. If you wanted to hack the array class to create .insert() and .remove() methods (where .remove() keeps the order without any null pointers) then please, do share. It could probably be done in ChucK sans-hacking, but where's the fun in that?

A check check in the source codes suggested chuck is using std::map for the associative array part. Then it is just to export to the chuck language iterator type and functions begin(), end(). The syntax might be something like: int m[0]; 1 => m["a"]; 2 => m["b"]; ... for (m.begin => iterator i; i < m.end(); i++) <<< m[i] >>>; One problem here is the type qualification of i: in C++, one would have to give it as a type belonging to the class, like std::map::iterator.

...

What is the difference exactly between .cap() and .size() ?

Don't know. I just needed array size, and started using size() :-). Hans

Kassen

2:52 p.m.

Hans; What is the difference exactly between .cap() and .size() ?

...

...
Don't know. I just needed array size, and started using size() :-).

Working from memory; In previous versions of ChucK .cap() could be used to get the length of the array, it could also (undocumentedly) be used to (re)set the length though at the expense of re-initialising all elements. In 1.2.1.2 .size() was added which can be used exactly like .cap() to get the size of the array. It is overloaded to set the size, which should not re-initialise the existing elements (this works as far as I'm aware) and which should initialise any new ones added (this does not always happen in practice). In the meantime .cap() is no longer overloaded to set array length. Why this is like it is I don't know, in theory it might have broken some code, like how we could set all array elements of a array of type int to 0 while maintaining the same length using this; foo.cap( foo.cap() ); more generally; using that we could re-initialise all elements without being aware of the type of the array. In practice I never heard about this resulting in any complaints. The current situation, however, *is* a bit unclear (if much preferable to the old one). I can see how potentially breaking code would be preferable to dramatically changing it's functionality without warning but I'm not sure that is the reasoning that led to the choices made. Personally I use .cap() to get lengths and .size( int) to set them, purely for readability reasons. Yours, Kas.

Andrew C. Smith

3:30 p.m.

...

A check check in the source codes suggested chuck is using std::map for the associative array part. Then it is just to export to the chuck language iterator type and functions begin(), end().

Right, but as I understand it Robert wanted to use an array of Objects. It seems that the associative array only works to associate strings with values, so (for example) you couldn't do: int foo[0]; 1 => foo[Bar bar]; because the associations can't take an Object. You'd be left with creating a symbolic string for every created Object, rather than having an array of Objects that you could search through. Iterating over the array seems so fast (especially if they're sortable) that throwing a bunch of strings into the mix would be tough. Side thought: class ObjectString { Object foo; string bar; ...(set, get, whatever)... } ObjectString hello; Object @ null; Object m[0]; SinOsc sine => hello.foo; hello.foo @=> m[hello.bar]; ... null @=> m[hello.bar]; // removes object So that then if you want to know if you have your object (hello), you can just ask if m[hello.bar] != null. I'm not sure whether this code will work or not, though, and all calls would have to be explicit (not iterative--so you couldn't set all m[] Objects to a particular parameter, I believe). Also, the array doesn't seem to be a contiguous block of memory now that we have operators << and popBack() and other dynamic array types. I remembered, .size() is a get method pretty much like .cap(), but .size(int) is a set method. Maybe .cap() is vestigial? Andrew (thanks, Hans, for catching how I only sent this to you) 2009/9/30 Kassen :

...

Hans;

...
...
What is the difference exactly between .cap() and .size() ?

Don't know. I just needed array size, and started using size() :-).

Working from memory;

In previous versions of ChucK .cap() could be used to get the length of the array, it could also (undocumentedly) be used to (re)set the length though at the expense of re-initialising all elements.

In 1.2.1.2 .size() was added which can be used exactly like .cap() to get the size of the array. It is overloaded to set the size, which should not re-initialise the existing elements (this works as far as I'm aware) and which should initialise any new ones added (this does not always happen in practice). In the meantime .cap() is no longer overloaded to set array length.

Why this is like it is I don't know, in theory it might have broken some code, like how we could set all array elements of a array of type int to 0 while maintaining the same length using this; foo.cap( foo.cap() );

more generally; using that we could re-initialise all elements without being aware of the type of the array. In practice I never heard about this resulting in any complaints.

The current situation, however, *is* a bit unclear (if much preferable to the old one). I can see how potentially breaking code would be preferable to dramatically changing it's functionality without warning but I'm not sure that is the reasoning that led to the choices made.

Personally I use .cap() to get lengths and .size( int) to set them, purely for readability reasons.

Yours, Kas.

_______________________________________________ chuck-users mailing list chuck-users@lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/chuck-users

Hans Aberg

4:11 p.m.

On 30 Sep 2009, at 21:30, Andrew C. Smith wrote:

...

...
A check check in the source codes suggested chuck is using std::map for the associative array part. Then it is just to export to the chuck language iterator type and functions begin(), end().

Right, but as I understand it Robert wanted to use an array of Objects.

I was going he would clarify.

...

It seems that the associative array only works to associate strings with values, so (for example) you couldn't do:

int foo[0]; 1 => foo[Bar bar];

because the associations can't take an Object. You'd be left with creating a symbolic string for every created Object, rather than having an array of Objects that you could search through. Iterating over the array seems so fast (especially if they're sortable) that throwing a bunch of strings into the mix would be tough. Side thought:

class ObjectString { Object foo; string bar; ...(set, get, whatever)... }

Yes, that is what though to. Otherwise, one would have to require objects to have equality comparisons for hash maps, and inequalities (total order) for maps (balanced trees). It might be called: class ObjectKey { Object object_; string key_; }

...

Andrew (thanks, Hans, for catching how I only sent this to you)

This mailing list server sets a reply-to field, which can play tricks on you, as there is no standard on how it should behave, I think. So different mail programs may handle it differently. Hans

Robert Poor

4:12 p.m.

New subject: implementing a set (was object / class hacking)

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. So what I'll probably end up doing is to create a unique ID for each of my objects (either via toString() or some other construction-time device), and keeping the objects sorted in an array using the ID for a binary search function. It's not as fast as a hashmap, but it's faster than linear search. - rob On 30 Sep 2009, at 12:30, Andrew C. Smith wrote:

...

...
A check check in the source codes suggested chuck is using std::map for the associative array part. Then it is just to export to the chuck language iterator type and functions begin(), end().

Right, but as I understand it Robert wanted to use an array of Objects. It seems that the associative array only works to associate strings with values, so (for example) you couldn't do:

int foo[0]; 1 => foo[Bar bar];

because the associations can't take an Object. You'd be left with creating a symbolic string for every created Object, rather than having an array of Objects that you could search through. Iterating over the array seems so fast (especially if they're sortable) that throwing a bunch of strings into the mix would be tough. Side thought:

class ObjectString { Object foo; string bar; ...(set, get, whatever)... }

ObjectString hello; Object @ null; Object m[0];

SinOsc sine => hello.foo;

hello.foo @=> m[hello.bar];

...

null @=> m[hello.bar]; // removes object

So that then if you want to know if you have your object (hello), you can just ask if m[hello.bar] != null. I'm not sure whether this code will work or not, though, and all calls would have to be explicit (not iterative--so you couldn't set all m[] Objects to a particular parameter, I believe).

Also, the array doesn't seem to be a contiguous block of memory now that we have operators << and popBack() and other dynamic array types.

I remembered, .size() is a get method pretty much like .cap(), but .size(int) is a set method. Maybe .cap() is vestigial?

Andrew (thanks, Hans, for catching how I only sent this to you)

...
_______________________________________________ chuck-users mailing list chuck-users@lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/chuck-users

_______________________________________________ chuck-users mailing list chuck-users@lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/chuck-users

Michael Heuer

4:40 p.m.

New subject: implementing a set (was object / class hacking)

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.

So what I'll probably end up doing is to create a unique ID for each of my objects (either via toString() or some other construction-time device), and keeping the objects sorted in an array using the ID for a binary search function. It's not as fast as a hashmap, but it's faster than linear search.

ChucK desperately needs int hashCode() and Object (or Class) getClass() made available on its top-level Object. Any takers? I'm willing to write java-style HashMap, ArraySet, and HashSet classes in LiCK, if you are ok with that style. There would be first class iterators and inner iterator methods (e.g. forEach) similar to the List and ArrayList classes. michael

Kassen

4:42 p.m.

New subject: implementing a set (was object / class hacking)

I would like to momentarily return to a previous issue. Before I said that the "==" operator doesn't cover identity in this sense; I was wrong and it does partially. consider; ======== Gain foo; foo @=> Gain bar; //should be true if (foo == foo) <<<"true">>>; else <<<"false">>>; //also true if (foo == bar) <<<"true">>>; else <<<"false">>>; ============ As compared to; ========= baz foo; foo @=> baz bar; //will lead to a error as "==" isn't overloaded to extend to this if (foo == foo) <<<"true">>>; else <<<"false">>>; class baz { int member; } ========== Now let's get tricky and try to write around the lack of overloading as at the testing stage we don't actually need the type; ========== baz foo; foo @=> baz bar; //this will yield a error at the casting if (( foo $ Object) == ( bar $ Object)) <<<"true">>>; else <<<"false">>>; class baz { int member; } ================= I believe this error to be another bug or omission in the type system. As a "baz" is clearly a object we should be able to cast it to Object. Because of this we won't -currently- be able to test for identity in trying to clean our array/set of identical objects. Of course we might still give a custom class a unique "id-tag" and test based on that. Unless somebody explains why and how I'm wrong in expecting the cast operator to extend to this usage I'm going to file this as a bug to the wiki. Personally I also feel that "(foo == bar)" should return true iff "(( foo $ Object) == ( bar $ Object)) " returns true and that the "==" operator should be overloaded to cover that. There might be implications to that that but currently that seems to me like the way to go; casting is fun but not *that* much fun. Yours, Kas.

Hans Aberg

5:01 p.m.

New subject: implementing a set (was object / class hacking)

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

Stefan Blixt

1 Oct 1 Oct

2:52 a.m.

New subject: implementing a set (was object / class hacking)

On Wed, Sep 30, 2009 at 10:12 PM, Robert Poor wrote:

...

So what I'll probably end up doing is to create a unique ID for each of my objects (either via toString() or some other construction-time device), and keeping the objects sorted in an array using the ID for a binary search function. It's not as fast as a hashmap, but it's faster than linear search.

- rob

Hmm, toString() (giving the memory pointer thingie) won't work if you want to be able to create two equal objects and use them like: A x1; "x" => x1.id; hashset.put(x1); A y; "y" => y.id; hashset.put(y); A x2; "x" => x2.id; // same as x1 if (hashset.contains(x2)) { // You want this code to run here } -- Release me, insect, or I will destroy the Cosmos!

Stefan Blixt

2:03 a.m.

Yeah, that's like what I did with my hash set example earlier (bar = hashcode). It's how the hash collections in Java works, it requires a hashcode function to be present. http://java.sun.com/javase/6/docs/api/java/util/HashSet.html Two problems with your ObjectString solution: 1: bar needs to contain a string that uniquely identifies the object it's in - no two objects may have the same bar string. There are a lot of tricky stuff involved with this (how do you generate an object and the another object equal to the first? How do you make sure that two different objects never get the same bar string?) Note that a hashcode doesn't need to be unique, all it does is generate some string that sorts the object into a group used for fast retrieval. 2: There is no way to iterate over associative arrays! Try this code: int a[0]; <<< "Size: ", a.size() >>>; 7 => a["hello"]; <<< "Size: ", a.size() >>>; The size() result (which is crucial for a for loops that wants to iterate over this array) keeps returning zero even though you added an element. Also, you don't know what to index the array with, even if you got the for loop going. What ChucK needs is some way of getting hold of all associative keys used in an array. Something like this: a.keys() => string keys[]; for( 0 => int i; i < keys.size(); i++) { a[keys[i]] => Object value; [...] } ...which I think is a thing that already has been touched upon in this thread. /Stefan On Wed, Sep 30, 2009 at 9:30 PM, Andrew C. Smith wrote:

...

...
A check check in the source codes suggested chuck is using std::map for the associative array part. Then it is just to export to the chuck language iterator type and functions begin(), end().

Right, but as I understand it Robert wanted to use an array of Objects. It seems that the associative array only works to associate strings with values, so (for example) you couldn't do:

int foo[0]; 1 => foo[Bar bar];

because the associations can't take an Object. You'd be left with creating a symbolic string for every created Object, rather than having an array of Objects that you could search through. Iterating over the array seems so fast (especially if they're sortable) that throwing a bunch of strings into the mix would be tough. Side thought:

class ObjectString { Object foo; string bar; ...(set, get, whatever)... }

ObjectString hello; Object @ null; Object m[0];

SinOsc sine => hello.foo;

hello.foo @=> m[hello.bar];

...

null @=> m[hello.bar]; // removes object

So that then if you want to know if you have your object (hello), you can just ask if m[hello.bar] != null. I'm not sure whether this code will work or not, though, and all calls would have to be explicit (not iterative--so you couldn't set all m[] Objects to a particular parameter, I believe).

Also, the array doesn't seem to be a contiguous block of memory now that we have operators << and popBack() and other dynamic array types.

I remembered, .size() is a get method pretty much like .cap(), but .size(int) is a set method. Maybe .cap() is vestigial?

Andrew (thanks, Hans, for catching how I only sent this to you)

...
Hans;

...
...
What is the difference exactly between .cap() and .size() ?

Don't know. I just needed array size, and started using size() :-).

Working from memory;

In previous versions of ChucK .cap() could be used to get the length of

...
array, it could also (undocumentedly) be used to (re)set the length

...
at the expense of re-initialising all elements.

In 1.2.1.2 .size() was added which can be used exactly like .cap() to get the size of the array. It is overloaded to set the size, which should not re-initialise the existing elements (this works as far as I'm aware) and which should initialise any new ones added (this does not always happen in practice). In the meantime .cap() is no longer overloaded to set array length.

Why this is like it is I don't know, in theory it might have broken some code, like how we could set all array elements of a array of type int to 0 while maintaining the same length using this; foo.cap( foo.cap() );

more generally; using that we could re-initialise all elements without being aware of the type of the array. In practice I never heard about this resulting in any complaints.

The current situation, however, *is* a bit unclear (if much preferable to the old one). I can see how potentially breaking code would be preferable to dramatically changing it's functionality without warning but I'm not sure that is the reasoning that led to the choices made.

Personally I use .cap() to get lengths and .size( int) to set them,

2009/9/30 Kassen : the though purely

...
for readability reasons.

Yours, Kas.

_______________________________________________ chuck-users mailing list chuck-users@lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/chuck-users

_______________________________________________ chuck-users mailing list chuck-users@lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/chuck-users

-- Release me, insect, or I will destroy the Cosmos!

5524

Age (days ago)

5525

Last active (days ago)

List overview

Download

18 comments

6 participants

participants (6)

Andrew C. Smith
Hans Aberg
Kassen
Michael Heuer
Robert Poor
Stefan Blixt