#2 Value deletion is broken

closed-fixed
nobody
None
5
2009-01-26
2008-11-06
Anonymous
No

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.

Discussion

  • 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

    Leonid Koninin - 2009-01-26
    • status: open --> closed-fixed
     
  • Leonid Koninin

    Leonid Koninin - 2009-01-26

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

     

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks