The new multiset implementation seems suitable for that when used without an ordering function. In that mode it takes O(log n) to insert and remove elements at each end but longer in the middle. With an ordering function it still takes O(log n) (assuming that function is O(1)) but with a higher constant. Stepping is O(1) on the average.
All the C level stuff already exists and appears to be stable, so what's needed is to make it available from Pike. If you aren't up to that, it could be an idea to use the C level functions in a specialized object; it'll still save you a lot of the gory details, such as handling resizing and gc interaction.
/ Martin Stjernholm, Roxen IS
Previous text:
2003-01-30 03:25: Subject: Re: hybrid of array & list
On Thu, Jan 30, 2003 at 02:05:03AM +0100, Martin Stjernholm, Roxen IS @ Pike developers forum wrote:
You mean: "ADT.Queue is using arrays to implement queues anyway, so I'll fix a better implementation." ;)
Well, I am slowly thinking about some hybride between lists and arrays, so I can use list->next(item)/list->prev(item) and indexes as well.
Actually, I need data type which will allow push/pop/shift (both FIFO & LIFO), destructive modification (by object reference, by index or index range) and access to the data by index. This data type should be quick enough when pushing/popping/shifting or iterating, and it should be possible to get an item which is next/previous to the specified.
Methods that I want at least (I hope purpose is obvious):
mixed push(mixed item, mixed|int|void pos) mixed pop(int|void count, int|void pos) mixed peek(int|void pos) void delete(mixed|int start, mixed|int|void end) mixed `[](mixed|int pos) mixed next(mixed pos) mixed prev(mixed pos)
There is no equivalent implemented already (in Pike), so I've no choice but to implement it myself (of course in C - Pike is soooo slow) :)
Regards, /Al
/ Brevbäraren