[fpc-devel] Do we need a TFPGMap.IsSorted method?

[Amir]

Hi there,

   The other day, I wanted to write a code to memorize and search some 
values (something like the following):

     MyMap := TIntIntMap.Create;
     for  i := 1 to ABigNumber do
        MyMap.Insert(AnIncreasingFunction(i), 
ComputationallyExpensiveFunction(AnIncreasingFunction(i)));

To have fast lookup, I had to set myMap.Sorted := True. But then noticed 
that setting this property, in the worst case, requires O(ABigNumber^2) 
step:  TFPSMap.SetSorted is implemented as:
   if Value = FSorted then exit;
   FSorted := Value;
   if Value then Sort;

The keys are sorted and Sort is a quick sort (which sucks if the input 
data is already sorted).

Wondering if it makes sense to change the implementation to
   if Value = FSorted then exit;
   FSorted := Value;
   if Value and not IsSortedFunc then
      Sort;

The other option could be to add a new read-only MyMap.IsSorted where 
the getter is implemented as:

   if FSorted then
      Exit(True);
   FSorted := IsSortedFunc;
   Result := FSorted;

Thanks,
Amir