mORMot Open Source

zed

Member

From: Belarus

Registered: 2015-02-26

Posts: 105

TDynArray and insert info sorted array

If I need insert item into sorted array, I can do it like this:

  VDynArr.Add(I);
  VDynArr.Sort;

but I think that it's not a very optimized and I suggest to do it differently:

 if not VDynArr.FastLocateSorted(I, VNewIndex) then begin
      VDynArr.Insert(VNewIndex, I);
 end;

After this Insert operation, array will still be sorted.

Implementation of FastLocateSorted is (tested on Delphi 2007):

type
  TDynArrayExt = object(TDynArray)
  public
    function FastLocateSorted(const Elem; out Index: Integer): boolean;
  end;

function TDynArrayExt.FastLocateSorted(const Elem; out Index: Integer): boolean;
var n, L, i, cmp: integer;
    P: PAnsiChar;
begin
  result := False;
  Index := -1; // return -1 if not Sorted
  if fSorted and (@fCompare<>nil) then begin
    P := fValue^;
    L := 0;
    n := Count - 1;
    while L <= n do begin
      i := (L+n) shr 1;
      cmp := fCompare(P[cardinal(i)*ElemSize],Elem);
      if cmp=0 then begin
        L := i;
        result := True;
        Break;
      end else
        if cmp<0 then
          L := i+1 else
          n := i-1;
    end;
    // if result is True - return the index of existing Elem
    // if result is False - return the index where to insert
    Index := L;
  end;
end;

...and small test:

procedure Test;
var
  I, VIndex, VNewIndex, VCount: Integer;
  VIntArr: TIntegerDynArray;
  VDynArr: TDynArrayExt;
begin
  VDynArr.InitSpecific(TypeInfo(TIntegerDynArray), VIntArr, djInteger, @VCount);

  for I := 1 to 6 do begin
    VDynArr.Add(I);
  end;
  VDynArr.Sorted := True;

  I := 3;
  VIndex := VDynArr.Find(I);

  if VIndex >= 0 then begin
    VDynArr.Delete(VIndex);
    VDynArr.Sorted := True;

    if not VDynArr.FastLocateSorted(I, VNewIndex) then begin
      Assert(VNewIndex >= 0);
      Assert(VNewIndex = VIndex);

      VDynArr.Insert(VNewIndex, I);
      VDynArr.Sorted := True;
    end;
  end;
end;

I think it will be useful to see this functional in TDynArray. Or maybe you know other way to do it?

ab

Administrator

From: France

Registered: 2010-06-21

Posts: 14,660

Website

Re: TDynArray and insert info sorted array

Good idea!

Please see http://synopse.info/fossil/info/8df20014e7

Thanks for the idea & patch!