Re: [Ocaml-lib-devel] PSQueue news

[Brian H. <bri...@ql...>]

On Fri, 30 May 2003, Diego Olivier Fernandez Pons wrote:

> Why don't you try AVL balancing scheme ? As stated by Ralf Hinze, it
> does not have the property of a finite number of rebalancing
> operations in the delete process (logarithmic instead) but should be
> much more easy to implement. Ralf Hinze uses in his paper the
> weight-balanced scheme which is quite similar.

Because I have this dream of someday going through and changing the node 
definitions so that instead of:

type 'a node_t = Node of color_t * dominance_t * ... 

(i.e. use a word each for color and dominance) of instead doing:

type 'a node_t =
    RedLeft of ...  (* red color, left dominance *)
    | RedRight of ... (* red color, right dominance *)
    | BlackLeft of ...
    | BlackRight of ...

Color and dominance then become 1 bit values effectively.  The pattern 
matching, however, then becomes *ahem* interesting.  I can't simply throw 
in a _ in the proper place to ignore color or dominance.  I may at that 
point switch away from pattern matching to branching conditionals, I don't 
know.  But this is the sort of thing which a library can do.

Brian