#2 Value deletion is broken

[Anonymous]

Consider the following code:

-----------------------------------------
jo = TlkJSONobject.Create;
jo.Add('a', 1);
jo.Add('b', 2);

jo.Delete(0);

someInt := jo.Field['b'].Value;
-----------------------------------------

The above code will produce a "List index out ouf bounds (1)" error, because after deleting the element with the index 0, which is 'a', the key belonging to the name 'b' is not updated from 1 to 0. Field['b'] still points to fList[1], which isn't there anymore.

[Nobody/Anonymous]

Here is a fix for the tree based path. There are two bugs.

The first is the 'flast' is declared globally instead of locally inside the 'del' function. When it is global, no nodes are ever deleted, because in the second 'if' statement (the one with 'if (t = flast) …') both 'if's never evaluate to true.

The second bug was that when you delete an object from fList, the indexes of those behind it decrease, but the tree still contains the old indexes. If you then execute 'IndexOfName', it returns the old index with is off by one. This i fixed by adding the 'UpdateKeys' procedure.

Here's the code:

---------------------------
function TlkBalTree.Delete(const ws: WideString): Boolean;

procedure UpdateKeys(t: PlkBalNode; idx: integer);
begin
if t <> fbottom then begin
if t.key > idx then
t.key := t.key - 1;
UpdateKeys(t.left, idx);
UpdateKeys(t.right, idx);
end;
end;

function del(var t: PlkBalNode): Boolean;
var
flast: PlkBalNode;
begin
result := false;
if t<>fbottom then begin
flast := t;
if ws<t.nm then
result := del(t.left)
else begin
fdeleted := t;
result := del(t.right);
end;
if (t = flast) and (fdeleted <> fbottom) and (ws = t.nm) then begin
fdeleted.key := t.key;
fdeleted.nm := t.nm;
t := t.right;
flast.nm := '';
dispose(flast);
UpdateKeys(froot, fdeleted.key);
result := true;
end
else if (t.left.level < (t.level - 1)) or (t.right.level < (t.level - 1)) then begin
t.level := t.level - 1;
if t.right.level > t.level then
t.right.level := t.level;
skew(t);
skew(t.right);
skew(t.right.right);
split(t);
split(t.right);
end;
end;
end;

begin
result := del(froot);
end;
-----------------------------------

Additionally, the declaration of 'flast' has to be removed from the definition of 'TlkBalTree'.

This seems to work as expected so far, although the tests i've done were not very thorough.

[Nobody/Anonymous]

Hello again,

the code i posted previously turned out to be buggy, but here is a corrected version that seems to work alright so far:

-----------------------------
function TlkBalTree.Delete(const ws: WideString): Boolean;

procedure UpdateKeys(t: PlkBalNode; idx: integer);
  begin
    if t <> fbottom then begin
      if t.key > idx then
        t.key := t.key - 1;
      UpdateKeys(t.left, idx);
      UpdateKeys(t.right, idx);
    end;
  end;

function del(var t: PlkBalNode): Boolean;
  begin
    result := false;
    if t<>fbottom then begin
      flast := t;
      if ws<t.nm then
        result := del(t.left)
      else begin
        fdeleted := t;
        result := del(t.right);
      end;
      if (t = flast) and (fdeleted <> fbottom) and (ws = fdeleted.nm) then begin
        UpdateKeys(froot, fdeleted.key);
        fdeleted.key := t.key;
        fdeleted.nm := t.nm;
        t := t.right;
        flast.nm := '';
        dispose(flast);
        result := true;
      end
      else if (t.left.level < (t.level - 1)) or (t.right.level < (t.level - 1)) then begin
        t.level := t.level - 1;
        if t.right.level > t.level then
          t.right.level := t.level;
        skew(t);
        skew(t.right);
        skew(t.right.right);
        split(t);
        split(t.right);
      end;
    end;
  end;

begin
  result := del(froot);
end;
-----------------------------

The differences are:
- flast *has* to be global, so i reverted this change i made previously
- the keys are updated before node deletion instead of afterwards when it doesn't make sense
- the original code had this line:

if (t = flast) and (fdeleted <> fbottom) and (ws = t.nm) then

which should have been

if (t = flast) and (fdeleted <> fbottom) and (ws = fdeleted.nm) then

I've got this line from the original paper describing this kind of binary tree (AA-tree).

So, this seems to work so far, but this would only fix the problems with node deletion and indexes pointing to wrong names after deletion for the tree based path. The hash based one still needs some kind of its own UpdateKeys function.

[Leonid Koninin]

thank you, i was fix this bug. also, thanks for the code.