You are not logged in.
- Topics: Active | Unanswered
Pages: 1
#1 Re: mORMot 1 » Bug in TDynArray.Find ? » 2015-03-17 10:58:11
Yes, it does. 
Thank you.
#2 Re: mORMot 1 » Bug in TDynArray.Find ? » 2015-03-17 08:13:48
Hello,
I'm talking about TDynArray.Find(const Elem; const aIndex: TIntegerDynArray; aCompare: TDynArraySortCompare): integer;
According to the comments above the declaration in SynCommon.pas Find should return the index of Elem.
/// search for an element value inside the dynamic array, from an external
// indexed lookup table
// - return the index found (0..Count-1), or -1 if Elem was not found
// - this method will use a custom comparison function, with an external
// integer table, as created by the CreateOrderedIndex() method: it allows
// multiple search orders in the same dynamic array content
// - if an indexed lookup is supplied, it must already be sorted:
// this function will then use fast binary search
// - if an indexed lookup is not supplied (i.e aIndex=nil),
// this function will use slower but accurate iterating search
// - warning; the lookup index should be synchronized if array content
// is modified (in case of adding or deletion)The array is sorted on one way. An external lookup table is sorted on otherway with CreateOrderdIndex() method. I manually set to 0 the length of the external lookup table before each CreateOrderedIndex() call to be sure that external index is correctly synchronized with array content.
Then, when I use the indexed lookup table, 2 cases occur : 
- If DynArray.Count <= 11, Find(Elem, aIndex, aCompare) uses iterating search (because of the n>10 condition), the result is the index found as described in comments.
function TDynArray.Find(const Elem; const aIndex: TIntegerDynArray;
aCompare: TDynArraySortCompare): integer;
var n, L, cmp: integer;
P: PAnsiChar;
begin
n := Count;
if (@aCompare<>nil) and (n>0) then begin
dec(n);
P := fValue^;
if (n>10) and (length(aIndex)>n) then begin
// array should be sorted -> use fast binary search
.../...
end else
// array is not sorted -> use iterating search
.../...
end;
result := -1;
end;- If DynArray.Count > 11, Find(Elem, aIndex, aCompare) uses binary search over aIndex and te result is the index IN the external lookup table which is not consistent with comments nor documentation.
function TDynArray.Find(const Elem; const aIndex: TIntegerDynArray;
aCompare: TDynArraySortCompare): integer;
.../...
result := (L+n) shr 1;
cmp := aCompare(P[cardinal(aIndex[result])*ElemSize],Elem);
if cmp=0 then
exit;
.../...
end;IMHO, result should be aIndex[result] in the last case to be consistent with comments and documentation.
Did I miss something ?
#3 mORMot 1 » Bug in TDynArray.Find ? » 2015-03-16 13:24:22
- sc78310
- Replies: 4
Hello,
It seems there is a bug in the Find function when supplying an index and a compare function.
If Count > 11, the result is the position in the supplied index array (aIndex).
If Count <= 11, the result is the position in the wrapped array (fValue).
The result is inconsistent whereas parameters are the same modulo the lenght of the wrapped array.
function TDynArray.Find(const Elem; const aIndex: TIntegerDynArray;
aCompare: TDynArraySortCompare): integer;
var n, L, cmp: integer;
P: PAnsiChar;
begin
n := Count;
if (@aCompare<>nil) and (n>0) then begin
dec(n);
P := fValue^;
if (n>10) and (length(aIndex)>n) then begin
// array should be sorted -> use fast binary search
L := 0;
repeat
result := (L+n) shr 1;
cmp := aCompare(P[cardinal(aIndex[result])*ElemSize],Elem);
if cmp=0 then
exit;
if cmp<0 then
L := result+1 else
n := result-1;
until L>n;
end else
// array is not sorted -> use iterating search
for result := 0 to n do
if aCompare(P^,Elem)=0 then
exit else
inc(P,ElemSize);
end;
result := -1;
end;Considering all the FindAnd*** functions, I'm not sure about what should be the value returned by the function.
As far as I'm concerned, in some cases, I also need a function that gives the position in the index array.
By the way, thank you for your great job.
Pages: 1