"dlist" -- beta is ready

[dmost at magna.com.au]

This is a very interesting concept. It might be worthwhile exploring
the possibility of adding some heuristic which would detect whether the
list is being added to at the front or back, and adjusting the realloc
behaviour accordingly.

e.g. you'd start your list with a small constant overallocation at
either end. The overallocation at each end would be recorded
separately, with independant doubling behaviour as the list grows in
that direction. In this way, a list used only to add elements at the
start of the list wouldnt have its trailing overallocation increased.

In article <393B4144.4C1DC04C at san.rr.com>,
  Courageous <jkraska1 at san.rr.com> wrote:
>
> I have a functioning implementation of my "dlist":
> an ADT which is a vector similar to python's list,
> with the addition of a buffer zone on the front as
> well as the back. This gives the vector O(1)+k
> performance on add/remove from both the head and
> the tail, while maintaining constant time for random
> access (with a small additional constant cost of
> tracking a virtual index).
>
> The implementation seems stable, and is passing
> a small test suite I've written, so I think it works.
>
> There are three items which I will finish soon
> (perhaps sooner if someone asks for them):
>
> 1. sorting; probably shouldn't be too hard to add
>    in Guido's/Tim's binarysort/sample sort code.
>
> 2. reversing.
>
> 3. invariant structures, in conjunction with 1.
>
> This is a VC98 project, intended to compile/run
> on windows platforms, although it could with some
> small mods work on unix platforms with equal ease.
>
> Simply request the source, and I'll send you a
> copy of the whole project dir, including the small
> test suite I have.
>
> C/
>


Sent via Deja.com http://www.deja.com/
Before you buy.