On Thu, 3 Jun 2004, Bardur Arantsson wrote:
> On Wed, Jun 02, 2004 at 04:58:25PM -0500, Brian Hurt wrote:
>
> > On Wed, 2 Jun 2004, Bardur Arantsson wrote:
> >
> > > I just though of something else which might be useful both
> > > for internal use, but also for users of the library (well,
> > > me in any case ;)): What about introducing a
> > > "node-pointer" type (and "index" if you will) which could
> > > be used as a starting point/stopping point for iteration?
> > >
> > > Then one could do things like:
> > >
> > > let b = find_ix some_key1 map
> > > and e = find_ix some_key2 map
> > > in
> > > ExtMap.iter ~first:b ~last:e (fun ...) map
> >
> > Why not just make the first and last arguments keys? In other words:
> > ExtMap.iter ~first:some_key1 ~last:some_key2 (fun ...) map
>
> Well, the thing is that by using 'indexes' you can reuse
> the range 'boundary elements' in case you need to do two
> traversals with the same 'first' element, but a different
> 'last' element (or vice versa). The idea is that the
> actual key lookup happens when the 'index' is built, so
> you can avoid looking up the keys multiple times. Granted,
> lookup is only an O(logN) operation, but still...
I don't see what we could store in an index that'd make the traversal
faster than this code (assuming we have both a first and a last):
let iter_range first last f map =
let rec loop = function
| Empty -> ()
| R(k, d, l, r)
| B(k, d, l, r) ->
let rval1 = Ord.compare k first
and rval2 = Ord.compare k last
in
if rval1 >= 0 then
begin
loop l;
if rval2 <= 0 then
f k d
end;
if rval2 <= 0 then
loop r
in
loop map
;;
> > They wouldn't be that complicated, but I'd be inclined to
> > make them a different function rather than using optional
> > arguments.
>
> The good thing about using optional arguments for this is
> that you essentially get 4 functions from 1: You can
> support ranges of the types
>
> [...,b]
> [a,...]
> [a,...,b]
> [...]
The disadvantage is that it makes that one function way more complicated.
More than twice as complicated, easily, as each place we want to access
either argument, we have to deal with both the presence and abscence of
said argument.
--
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
- Gene Spafford
Brian
-------------------------------------------------------
This SF.Net email is sponsored by the new InstallShield X.
|
