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'?

Name · Answer 1 · 2011-02-18T11:41:22.700

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;

Linas · Accepted Answer · 2011-02-21T14:22:17.803

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;

edited Feb 21 '11 at 14:22

answered Feb 18 '11 at 11:45

Linas

5,485
1
25
35

Thanks. I like the syntax. But 2 problems: it stays indefinitely on the same item and a call of SetToKey is missing. I have added a corrected version of the function in your post, but it will visible only after it is peer reviewed. – Name Feb 18 '11 at 13:19
@Name: You should just post the corrected version as a separate answer :) – jalf Feb 18 '11 at 13:52
The edited version (the one using locate) doesn't work properly. I'm testing with a map containing followings values: 'aaa' => 0, 'def' => 1,, 'abc' => 2, 'abc' => 3, 'def' => 4, 'abc' => 5, 'def' => 6 and I get 2, 3, 5, 1, 4, 6. (But I must say that my corrected version didn't work properly either. I'll try to correct it and post it as a new answer) – Name Feb 21 '11 at 08:34

score 1 · Answer 3 · answered Feb 21 '11 at 09:00

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;

This version is OK. My test case was bas previously :) One thing: you dont need to call getContainer(iter) in findin, because you have map as a parameter. — Linas, Feb 21 '11 at 14:03

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

3 Answers3