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 <rdpoor@gmail.com>

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!