"Arthur A. Gleckler" <xxxxxx@speechcode.com> writes:

> I'm implementing Hopcroft's algorithm for DFA minimization, and a new
> hash table operation occurred to me:
>
> (choose-and-remove! hash-table) => key, value
>
> The idea is that it picks a key-value pair at random, removes it, and
> returns it. To implement that with the current proposals, one must get
> the list of keys, pick one element from it, look up the associated
> value, remove the key and value, and return them. Constructing the
> list of keys when one is only going to use a single element is
> wasteful.
>
> I'm using a simple implementation of sets built on top of hash tables,
> so I'm actually implementing remove-an-element for sets, not for hash
> tables, but picking an element at random from a set is a common
> operation and worth optimizing, and supporting it at the hash table
> level seems likely to be fruitful, too.

Obviously the better (best?) name for this is hash-table-pop!.  It's
unfortunate that this conflicts with Gauche, but shouldn't one use

    (pop! (hash-table-ref ht k) x)

for popping from a generic place, obviating the need for any *-pop!
operations specialized for different data structures?

OK, that's less efficient.  I would question how often that difference
in efficiency is relevant though.  If we absolutely want the efficient
push/pop then maybe we should name them hash-table-update/pop! and such.
Or let users define that when they want it and leave it out of the spec.

Taylan