Re: [Ocaml-lib-devel] Re: Dllist ? IndexTree ?

[Bardur A. <oca...@sc...>]

On Fri, Sep 10, 2004 at 05:39:22PM -0400, Jesse Guardiani wrote:

> Actually, I tried this before I submitted the current implementation and I
> couldn't get it to work. The problem seemed to be that Dllist has no
> concept of Empty, so the length function becomes really difficult to
> implement.
> 
> Brian, do you think it's possible to implement enums without the "valid"
> test? If everyone thinks it's possible then I'll give it another shot. I just
> didn't have much luck the first time around.
> 

On the subject of Dllist.enum... I noticed that the count ()
function always computes the length of the remaining nodes
by traversing the list. It would be more efficient to do
this, I think:

1) The first time count () is called, compute the length
and store it "in the enum".

2) Subsequent calls to count () just return the computed
length.

2) Every time next () is called, decrese the number of
remaining elements by 1 (if the number hasn't been set,
you don't need to do anything).

This would only incur minimal overhead for next () and for
any code the uses count () it basically reduces count ()
to O(1) averaged over all the elements.

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

- Be ot or bot ne ot, taht is the nestquoi.
                                   | Monty Python's Flying Circus