How to iterate properly over the search results of a DMultiMap (DeCAL) in Delphi?

Question

I am using the DMultiMap container from DeCAL with Delphi 6 to store data. The key is a string which can appears several time in the map.

I wonder how to iterate properly over all objects with a given key.

Will this code:

function IterateOverObjects(map: DMultimap);
var iter: DIterator;
begin
  iter := map.locate(['abc']);
  while IterateOver(iter) do
  begin
    // do something with the value...
  end;
end;

returns all the objects of with 'abc' as key? Or will it returns all the objects of the map starting from the first object with 'abc' as key?

Edit: Just tested. It returns all the objects of the map starting from the first object with 'abc' as key. What is then the best way to iterate over 'abc'?

Answer 1

EDIT: tested version (I've changed previously used findif, because I investigated that it doesn't use fast locate, it just loops through all the items):

EDIT2: because my previous test was bad, I've edited function to make it work properly. it looks almost the same as Name's answer, but I changed it to not confuse anyone with incorrect function.

    function IterateOverFound(Map: DMultiMap; var iter: DIterator; const obj: array of const): Boolean;
begin
  if diIteration in iter.flags then
  begin
    advance(iter);
    SetToKey(iter);
    iter := findIn(iter, Map.finish, obj);
  end
  else
  begin
    iter := Map.locate(obj);
    Include(iter.flags, diIteration);
  end;

  Result := not atEnd(iter);
  if not result then
    Exclude(iter.flags, diIteration);
end;

Example usage:

var
  iter: DIterator;

  iter := map.start; 
  while IterateOverFound(map, iter, ['abc']) do
  begin
    SetToValue(iter);
    // get value
  end;

Answer 2

In the meanwhile I made some researches and found one solution. As DMultiMap is an ordered map (based on a black tree and not on an hash value), all items with the same key are grouped so that following code works:

function IterateOverObjects(map: DMultimap);
var iter1, iter2: DIterator;
begin
  iter1 := map.locate(['abc']);
  if not AtEnd(iter1) then
  begin
    iter2 := map.upper_bound(['abc']);
    repeat
      // do something with the value...
      Advance(iter1);
    until equals(iter1, iter2);
  end;
end;

Another possibility would be:

function IterateOverObjects(map: DMultimap);
var iter: DIterator;
begin
  iter := map.locate(['abc']);
  while IterateOver(iter) do
  begin
    SetToKey(iter);
    if (getString(iter) <> 'abc') then break;
    SetToValue(iter);
    // do something with the value...
  end;
end;

Answer 3

I like the syntax of the usage example proposed by Linas, but as the function doesn't work properly, here is a corrected version. The fact that FindIn doesn't use a fast locate isn't a problem, as it is only used to iterate (A DMultiMap is an ordered map, so that all items with the same key are together):

function IterateOverFound(Map: DMultiMap; var iter: DIterator; const obj: array of const): Boolean;
var bWasToKey: boolean;
begin
  if diIteration in iter.flags then
  begin
    advance(iter);
    bWasToKey := diKey in iter.flags;
    SetToKey(iter);
    iter := DeCAL.findIn(iter, DeCAL.getContainer(iter).finish, obj);
    if not bWasToKey then
      SetToValue(iter);
  end else
  begin
    iter := Map.locate(obj);
    Include(iter.flags, diIteration);
  end;
  result := not atEnd(iter);
  if not result then
    Exclude(iter.flags, diIteration);
end;

Example usage:

var
  map: DMultiMap;
  iter: DIterator;

map := DMultiMap.Create;
map.putPair(['aaa', 0]);
map.putPair(['def', 1]);
map.putPair(['abc', 2]);
map.putPair(['abc', 3]);
map.putPair(['def', 4]);
map.putPair(['abc', 5]);
map.putPair(['def', 6]);
iter := map.start;
while IterateOverFound(map, iter, ['abc']) do
begin
  // do something with the value...
end;