Re: 5.2 work3 manual

["Juris Kalnins" <juris@...>]

On Tue, 25 May 2010 15:56:49 +0300, Tony Finch <dot@dotat.at> wrote:

> On Tue, 25 May 2010, Javier Guerra Giraldez wrote:
[..]
> > and a reverse linked list could keep it at O(1); but all these assume
> > maintaining extra structure and keep it current on every assignment.
>
> I don't see how you can get it to O(1) with something as simple as a  
> list.
> The hard part is dealing with splitting and joining contiguous sections  
> of
> non-nil array elements, where one assignment can change #t by a large
> number.

well, with the way it's currently made, you can

currently, array part is an array of TValue, which is big enough to be
a double-linked list node.
So make it:

union ANode {
  struct { ANode **prev; ANode *next; } l;
  TValues d;
};
struct Table {
...;
ANode *array;
ANode *firstNil;
...
};

When resizing array part, link all nil nodes into firstNil list;
then #t is:
*firstNil ? #t == array - firstNil : sizearray;

And you have O(1) #t, plus amortized O(1) cost of list upkeep.