How to use associative arrays in Ada 2005?

[snoopysalive]

Hi!

Can anybody explain me how to use associative arrays in Ada 2005? I
mean hashes like in Perl. Some background: I'm a student of
Computational Linguistics and try to get away from Perl which I find
not efficient enough (at my university, Perl is the standard language
used by the professors). In my opinion, C++ is cool but Ada's syntax is
better to avoid dirty code.

So, when I say "hash", I mean something Perl-like like
"$hashname{key1}{key2} = 'something' ". Or something C++-like like "map
<string,int> hashname; hashname["key1"] = 42;".

Is there anything similar in Ada 2005, too? I bought the book
"Programming in Ada 2005" by John Barnes but I don't understand the
author's way of explaining a programming language (for me, the book is
more confusing than explaining).

Or does anybody know a good tutorial similar to the lots of C- and
Perl-tutorials? I found many Ada-tutorials but most of them just list
the contents of the built-in packages and don't explain how to use
them. As a beginner this is confusing.

Thanks for every answer!

CU,
Matthias

[Georg Bauhaus]

Post by snoopysalive
So, when I say "hash", I mean something Perl-like like
"$hashname{key1}{key2} = 'something' ". Or something C++-like like "map
<string,int> hashname; hashname["key1"] = 42;".

With Ada 2005, you have Ada.Containers.Hashed_Maps;

hashname.insert("key1", 42);

See
http://en.wikibooks.org/wiki/Ada_Programming/Containers#First_Example:_Maps
for an example.

The original Ada.Containers distribution at
http://charles.tigris.org/

has a Containers tutorial linked at the bottom of the page.

Post by snoopysalive
I found many Ada-tutorials but most of them just list
the contents of the built-in packages and don't explain how to use
them. As a beginner this is confusing.

Maybe try John English's
http://burks.bton.ac.uk/burks/language/ada/adacraft/contents.htm

It doesn't cover the Ada 2005 containers, though.

[Matthew Heaney]

Post by snoopysalive
Can anybody explain me how to use associative arrays in Ada 2005? I
mean hashes like in Perl.

There are actually two kinds of "associative arrays" in Ada05: ordered maps and
hashed maps. Each of these container types accept both a key and element as
generic formal types. (There are also sets, that accept just an element type.)

If both the key and element are "definite" types (types that don't require a
constraint to specify the size), then you can use:

ada.containers.hashed_maps
ada.containers.ordered_maps

If either the key or element is an "indefinite" type (such as String), then you
can use:

ada.containers.indefinite_hashed_maps
ada.containers.indefinite_ordered_maps

If you use the hashed version, you'll need a hash function for your key type.
The library comes with a hash function for type String (and Wide_String, etc);
see Ada.Strings.Hash.

If you use the ordered version, you'll need a relation operation ("<") for your
key type.

Post by snoopysalive
In my opinion, C++ is cool but Ada's syntax is
better to avoid dirty code.

If you're familiar with the STL, then you should have no trouble with the Ada
container library.

Post by snoopysalive
So, when I say "hash", I mean something Perl-like like
"$hashname{key1}{key2} = 'something' ". Or something C++-like like "map
<string,int> hashname; hashname["key1"] = 42;".

Right. People often say "hash" but in reality that's just one way of
implementing an associative container. In Ada05 you can use either the hashed
version or the ordered version.

Your example above would be:

package String_Integer_Maps is
new Ada.Containers.Indefinite_Hashed_Maps
(String,
Integer,
Ada.Strings.Hash,
Equivalent_Keys => "=");

Note that there's no index operator (operator[]()) in Ada, so you say:

procedure Op (M : in out String_Integer_Maps.Map) is
begin
M.Include ("key1", 42);
end;

Note that this is not exactly equivalent to the C++ operation, since in Ada the
key is replaced too (if it already exists). That's unnecessary here so a
slightly more efficient technique might be:

procedure Op (M : in out String_Integer_Maps.Map) is
C : Cursor;
B : Boolean;
begin
M.Insert ("key1", 42, C, B);
if not B then
M.Replace_Element (C, 42);
end if;
end Op;

Post by snoopysalive
Is there anything similar in Ada 2005, too? I bought the book
"Programming in Ada 2005" by John Barnes but I don't understand the
author's way of explaining a programming language (for me, the book is
more confusing than explaining).

That book has a chapter (17?) on the container library. If you have a specific
question just post here or send me some email.

Post by snoopysalive
Or does anybody know a good tutorial similar to the lots of C- and
Perl-tutorials? I found many Ada-tutorials but most of them just list
the contents of the built-in packages and don't explain how to use
them. As a beginner this is confusing.

If just gave a tutorial on the Ada05 container library. I can give you the
power-point slides or send you a pdf version. Drop me a line if you're
interested.

But as a said above, the Ada standard container library is very similar to the
C++ STL, so if you already know the latter than the former shouldn't be much of
a stretch.

-Matt

[snoopysalive]

Hello!

With the help of both of you, I finally made my first steps with
Ada-containers. I really thank both of you very much.

@Matt: Yes, I'm really interested in the PowerPoint-slides you were
writing about. Would you be so kind and send them to me? I'd prefer the
pdf-version but I'd be also happy with the PowerPoint-version. I think,
you see my e-mail-address in the header of this message. Thank you!

Greetz,
Matthias

[snoopysalive]

Hi!

First: @Matt: Thank you for the pdf. It's really useful, but I couldn't
write you back because of the email filter.

And now, my next question: How to handle "hashes of hashes" in Ada?
Here's the code which should contain a package representing a hash of a
hash:

-- Here, the code begins
with Ada.Text_IO,
Ada.Strings.Hash,
Ada.Containers.Indefinite_Hashed_Maps;
use Ada.Text_IO,
Ada.Strings,
Ada.Containers;

procedure book is
package Str_Int_Maps is
new Ada.Containers.Indefinite_Hashed_Maps
(String,
Integer,
Ada.Strings.Hash,
"=");
use Str_Int_Maps;
package Str_Map_Maps is
new Ada.Containers.Indefinite_Hashed_Maps
(String,
Str_Int_Maps.Map,
Ada.Strings.Hash,
"=");

Ages : Str_Map_Maps.Map; -- That's the "hash of a hash"

begin
Ages.Insert("family name",Insert("name",23));
end book;
-- Here, the code ends


The statement "Ages.Insert("family name",Insert("name",23));" doesn't
work. So, how is it possible to do something like this in C++:
"...
map<string, map<string,int>> ages;
ages["family name"]["name"] = 23;
..."

Thank you and greetings,
Matthias

[Georg Bauhaus]

Post by snoopysalive
The statement "Ages.Insert("family name",Insert("name",23));" doesn't
work.

Think about what Insert returns, if anything.
Programs written in Ada are less frequently filled with
abbreviations :-)

Post by snoopysalive
"...
map<string, map<string,int>> ages;
ages["family name"]["name"] = 23;
..."

[Georg Bauhaus]

Post by snoopysalive
The statement "Ages.Insert("family name",Insert("name",23));" doesn't
"...
map<string, map<string,int>> ages;
ages["family name"]["name"] = 23;
..."

I think that in this case the Ada.Containers requirement
of being minimal building blocks applies. And probably also
the principle of query/command separation, which is not followed
by std::map::operator[]. [] does many things at the same time,
hence it is not minimal.

If I remember Matt's tutorial correctly, there is an example showing how
to manipulate items in containers in situ. Barnes' book has this, too.

If the elements in a map are containers themselves (or are
otherwise big), you may want to use Update_Element.

If you have +-----------+
+--> | ... |
+-------------+ | +-----------+
| ... | --+ | ... | +--> ...
+-------------+ +----------+ |
| family name | --> | ... | ---+
+-------------+ +----------+
| ... | | name | ------> 23
+----------+
| ... |

That is in order to manipulate one of the 2nd level maps,
you could either:

- Get the element at key "family name", which is a map.
This creates a copy of the map.
- Manipulate the copied map.
- Put the map back to where it had been (at key "family name"),
again copying.

Or,

- Get a cursor for the element at key "family name".
- Define a subprogram that manipulates the 2nd level map
(the one containing "name" as key).
- Call Update_Element with the cursor and the subprogram.

with Ada.Text_IO,
Ada.Strings.Hash,
Ada.Containers.Indefinite_Hashed_Maps;
use Ada.Text_IO,
Ada.Strings,
Ada.Containers;

procedure book2 is
package Str_Int_Maps is
new Ada.Containers.Indefinite_Hashed_Maps
(String,
Integer,
Ada.Strings.Hash,
"=");
use Str_Int_Maps;
package Str_Map_Maps is
new Ada.Containers.Indefinite_Hashed_Maps
(String,
Str_Int_Maps.Map,
Ada.Strings.Hash,
"=");

Ages : Str_Map_Maps.Map; -- That's the "hash of a hash"
Named_Age: Str_Int_Maps.Map;


-- life by population statistics:

Average: constant Natural := 80;
function Grow_Older(Now: Integer) return Integer is separate;
-- used to compute a new `Age` from `Now`

Age: Integer := 0;

procedure Set_Age(name: String; value: in out Str_Int_Maps.Map) is
begin
Named_Age.Include("name", Age); -- Note how `Age` is used here
end Set_Age;

begin
Ages.Insert("family name", Named_Age);

while Age < Average loop
Age := Grow_Older(Age);

--
Ages.Update_Element(position => Ages.Find("family name"),
process => Set_Age'access); -- in situ
end loop;
end book2;

This might seem like a lot, but once you have your setup, you
can reuse it, or write []-style wrappers, if you need them
etc.. Scope is important in this example, because the `Age`
variable is visible to Set_Age, and need not be passed around.

[Matthew Heaney]

Post by Georg Bauhaus
I think that in this case the Ada.Containers requirement
of being minimal building blocks applies.

Right, the library is designed to be composable. Here's a case where a
container needs to contain another container.

Post by Georg Bauhaus
If the elements in a map are containers themselves (or are
otherwise big), you may want to use Update_Element.

Right. Use Insert to create the element in the outer container, and then use
Update_Element to manipulate the inner container.

Post by Georg Bauhaus
That is in order to manipulate one of the 2nd level maps,

Ouch! A lot of copying here...

Post by Georg Bauhaus
Or,
- Get a cursor for the element at key "family name".
- Define a subprogram that manipulates the 2nd level map
(the one containing "name" as key).
- Call Update_Element with the cursor and the subprogram.

Right, this is the correct approach.

Post by Georg Bauhaus
Ages : Str_Map_Maps.Map; -- That's the "hash of a hash"
Named_Age: Str_Int_Maps.Map;

You don't need the Named_Age map. There's a version of Insert that accepts
just a key (which is different from the other versions, which accept both key
and element).

Post by Georg Bauhaus
procedure Set_Age(name: String; value: in out Str_Int_Maps.Map) is
begin
Named_Age.Include("name", Age); -- Note how `Age` is used here

Here you can just say:
Value.Include ("name", Age);

Post by Georg Bauhaus
end Set_Age;
begin
Ages.Insert("family name", Named_Age);

It's probably better to use the insert that returns a cursor, and then reuse
that cursor value, since that will obviate the need for a separate Find.

You can also eliminate the Name_Age map object, if you use the Insert that
accepts a key only. (If the key doesn't already exists, then it inserts an
element with a default value. Here that would mean an empty map, which is just
what we want.)

Post by Georg Bauhaus
Ages.Update_Element(position => Ages.Find("family name"),
process => Set_Age'access); -- in situ

But note that Ages.Find duplicates the work of Ages.Insert (since Insert must
perform an internal search). If you use an Insert that returns a cursor, then
you can just reuse the cursor, instead of Find'ing it again. Your method works
but it's less efficient.

Post by Georg Bauhaus
end loop;
end book2;

[Dmitry A. Kazakov]

Post by snoopysalive
The statement "Ages.Insert("family name",Insert("name",23));" doesn't
"...
map<string, map<string,int>> ages;
ages["family name"]["name"] = 23;
..."

But this does not look like a hash of hashes. Rather it is a hash of
StringxString. If so, then you could make a record type with two string
fields and build a hash over it, or alternatively, pack two strings into
one using some delimiter character. To construct such keys you could write
a helper function:

type Key_Type is new String;
function Key (First_Name, Second_Name : String) return Key_Type;
...

[Matthew Heaney]

Post by Dmitry A. Kazakov
But this does not look like a hash of hashes.

A map of maps works great...

[snoopysalive]

Hi!

First, I want to thank all of you for your examples and ideas. But they
don't work, sorry! So, I took your ideas and am trying to implement an
own procedure creating "hashes" like I need them.

The problem is that I need maps of maps of maps ... It's logical that a
container is able to get another container as element and it's no
problem to instanciate these containers and then put them one into the
other.
In my example code I tried to create a table of family names, names
and their ages. Let's make it a little more complex and create another
first key called "nation":

Nation | Family Name | Name | Age*
----------|---------------|---------------------|------
German | Goethe | Johann Wolfgang | 60
| | Catharina Elisabeth | 80
| | Johann Caspar | 90
| Hesse | Hermann | 51
Japanese | Kusanagi | Motoko | 29
American | Ford | Henry | 45
| | Harrison | 41
Finnish | Torvalds | Linus | 35
----------|---------------|----------------------------
* All ages are fictional because I don't know the real
ages of these persons or they are dead or fictional

The problem: Every single key needs a separate container map. We need 1
first-level, 4 second-level and 5 third-level key maps.

First-level = 1x map of string-map
Second-level = 4x map of string-map
Third-level = 5x map of string-integer

It would be necessary to create every single map and to put them one
into the other all manually for transforming the given table into a
"hash". That's easy and possible but not flexible. When posting the
code of my impossible programme, I had the idea of "anonymous"
container maps contained in maps. Because of this I wrote
"Ages.Insert("family name", Insert("name", 23));".

Sadly, Matt's solution didn't work. The statement "Ages.Insert ("family
name", C, B);" brought a compilation error: "no selector 'Insert' for
private type "Ada.Containers.Indefinite_Hashed_Maps.Map" from instance
at line 16". I found out that no procedure "Insert(String, Cursor,
Boolean)" exists. But it exists a procedure "Insert(String,
Element_Type, Cursor, Boolean)".
So, I'm trying to combine Matt's and Georg's ideas now. I'll write a
line, if I'd be successfull. Otherwise, I'll also write a line. ;-)

Once more: Thank you all. I'm commencing to have an idea of Ada-syntax
and philosphy and that's more than my professors at universitiy could
give me.

Greetings,
Matthias

[Matthew Heaney]

Post by snoopysalive
Sadly, Matt's solution didn't work. The statement "Ages.Insert ("family
name", C, B);" brought a compilation error: "no selector 'Insert' for
private type "Ada.Containers.Indefinite_Hashed_Maps.Map" from instance
at line 16". I found out that no procedure "Insert(String, Cursor,
Boolean)" exists. But it exists a procedure "Insert(String,
Element_Type, Cursor, Boolean)".

Yes, you're right. I was thinking of the definite form of the hashed map. The
indefinite form doesn't include the operation I used in my example. Sorry for
the confusion.

Post by snoopysalive
So, I'm trying to combine Matt's and Georg's ideas now. I'll write a
line, if I'd be successfull. Otherwise, I'll also write a line. ;-)

Right, all you need to do is change my example to say:

Ages.Insert
(Key => "family name",
New_Item => Str_Int_Maps.Empty_Map,
Position => C,
Inserted => B);

[Dmitry A. Kazakov]

Post by snoopysalive
The problem is that I need maps of maps of maps ... It's logical that a
container is able to get another container as element and it's no
problem to instanciate these containers and then put them one into the
other.
In my example code I tried to create a table of family names, names
and their ages. Let's make it a little more complex and create another
Nation | Family Name | Name | Age*
----------|---------------|---------------------|------
German | Goethe | Johann Wolfgang | 60
| | Catharina Elisabeth | 80
| | Johann Caspar | 90
| Hesse | Hermann | 51
Japanese | Kusanagi | Motoko | 29
American | Ford | Henry | 45
| | Harrison | 41
Finnish | Torvalds | Linus | 35
----------|---------------|----------------------------
* All ages are fictional because I don't know the real
ages of these persons or they are dead or fictional

No, this is still a 3D array of age. Mathematically it is always equivalent
to an array of arrays of arrays of age. Both are mappings which for a tuple
(Nation, Surname, Name) yield age.

Post by snoopysalive
The problem: Every single key needs a separate container map.

That depends on each concrete case. Arrays of arrays have advantages and
disadvantages. It is to expect a performance penalty in terms of both space
and time for an hash of hash of hash vs. simple hash. Clearly, instead of
one look-up you are doing three.

P.S. Arrays of arrays usually come in question only when you would like to
perform searches on subarrays. Like: find all Nation="German". And only
when there is a fixed order on the indices. For example, find all
Name="John" would work awfully.

P.P.S. Hashes aren't equivalent to associative arrays. Hash is one of many
possible implementations of. It again has advantages and disadvantages. For
example, hashes are unsuitable for searching for the best match (like:
Nation="...", Name="..." etc). Here things like kd-trees are used.

[Matthew Heaney]

Post by Dmitry A. Kazakov
That depends on each concrete case. Arrays of arrays have advantages and
disadvantages. It is to expect a performance penalty in terms of both space
and time for an hash of hash of hash vs. simple hash. Clearly, instead of
one look-up you are doing three.

Yawn. A hash-table look-up is O(1). It's like trying to argue that
you'll lose weight by only eating 1 pea instead of 3 peas for dinner...

[Dmitry A. Kazakov]

Post by Matthew Heaney

Post by Dmitry A. Kazakov
That depends on each concrete case. Arrays of arrays have advantages and
disadvantages. It is to expect a performance penalty in terms of both space
and time for an hash of hash of hash vs. simple hash. Clearly, instead of
one look-up you are doing three.

Yawn. A hash-table look-up is O(1). It's like trying to argue that
you'll lose weight by only eating 1 pea instead of 3 peas for dinner...

... asymptotically under certain conditions, which might be or not met in a
real case.

Also:

1. Insertion and deletion in sparse 3D arrays organized in hashes of hashes
might lead to an eager allocation and deallocation of subordinated hashes.
Shuffling memory is not a pea. In some cases it is a disaster.

2. Finding an optimal set of hash functions (and that is 1+n+n*m
functions!) might turn quite difficult, depending on how items are
distributed in 3D space. You might have a relatively evenly distributed
items in 3D, which awfully distributed in 2D and 1D planes.

3. You don't mention memory, for a good reason. Hashes are known space
eaters. And you have n**2 of them!

The bottom line is - I think a good advice to a student learning Ada, and
the Ada's way (tm) is to factor out a clean interface to his 3D array
first, and hide the implementation (be it a hash of hashes or anything
else). This might be obvious for Ada programmers, but people coming with
the background in other languages tend to think in terms of implementation.

[Matthew Heaney]

Post by Dmitry A. Kazakov
... asymptotically under certain conditions, which might be or not met in a
real case.

Now you're just moving the goalposts. Again.

The only issue at hand is whether the standard container library can
solve the OP's problem. The answer is emphatically yes.

Tangential discussions of relative efficiency of maps compared to arrays
are little more than a Chewbacca Defense...

Post by Dmitry A. Kazakov
3. You don't mention memory, for a good reason. Hashes are known space
eaters. And you have n**2 of them!

Yes, Dimitry. And cars consume more gasoline than bicycles...

Post by Dmitry A. Kazakov
This might be obvious for Ada programmers, but people coming with
the background in other languages tend to think in terms of implementation.

The Ada 2005 standard container library is not substantively different
from the C++ standard container library.

[Alex R. Mosteo]

Post by Matthew Heaney

Post by Dmitry A. Kazakov
... asymptotically under certain conditions, which might be or not met in
a real case.

Now you're just moving the goalposts. Again.
The only issue at hand is whether the standard container library can
solve the OP's problem. The answer is emphatically yes.
Tangential discussions of relative efficiency of maps compared to arrays
are little more than a Chewbacca Defense...

I don't think this is completely fair. Yes, hashes are said to be O(1) but
also they always carry the warning that this is not absolute. I'd feel
dishonest if presenting an algorithm saying it's O(1) if it uses hash maps.
I'd probably prefer to use trees and give O(log n) as a real upper bound.

[Matthew Heaney]

Post by Alex R. Mosteo
I don't think this is completely fair. Yes, hashes are said to be O(1) but
also they always carry the warning that this is not absolute. I'd feel
dishonest if presenting an algorithm saying it's O(1) if it uses hash maps.
I'd probably prefer to use trees and give O(log n) as a real upper bound.

Agree with all of the above. If you need an upper-bound guarantee, then an
ordered form (which is tree-based) is preferred.

[Dmitry A. Kazakov]

Post by Matthew Heaney

Post by Dmitry A. Kazakov
3. You don't mention memory, for a good reason. Hashes are known space
eaters. And you have n**2 of them!

Yes, Dimitry. And cars consume more gasoline than bicycles...

Sorry, but I fail to see how a hash of hashes is more "car" than a simple
hash (over the tuple). Maybe your point is that a car carrier truck is a
better family car than Ford Mondeo?

[Matthew Heaney]

Post by Dmitry A. Kazakov
Sorry, but I fail to see how a hash of hashes is more "car" than a simple
hash (over the tuple).

I was trying to make the point that yes of course hash-tables consume more
resources than an array, but if you don't have a discrete index type then
you have to use a hash table!

[Simon Wright]

Post by snoopysalive
Nation | Family Name | Name | Age*
----------|---------------|---------------------|------
German | Goethe | Johann Wolfgang | 60
| | Catharina Elisabeth | 80
| | Johann Caspar | 90
| Hesse | Hermann | 51
Japanese | Kusanagi | Motoko | 29
American | Ford | Henry | 45
| | Harrison | 41
Finnish | Torvalds | Linus | 35
----------|---------------|----------------------------

There's no reason I can see to use maps of maps *for this problem*. I
would use a hash function (Nation x Family_Name x Name) => Hash_Type
in a single map.

Matt, I see (A.18.4(5)) that Ada.Containers doesn't allow hash
collisions (which, if true, is demanding a lot of hash function
designers). If collisions aren't allowed we could go for an ordered
map based on

Left.Nation < Right.Nation
and then Left.Family_name < Right.Family_Name
and then Left.Name < Right.Name

or some likely-to-be-more-efficient order.

[Matthew Heaney]

Post by Simon Wright
There's no reason I can see to use maps of maps *for this problem*. I
would use a hash function (Nation x Family_Name x Name) => Hash_Type
in a single map.

Yes, that's right, you could do it either way.

I prefer that OP's approach of using a map of maps of maps, since that
allows you to perform queries like "give me all the entries for this
nation", etc.

Post by Simon Wright
Matt, I see (A.18.4(5)) that Ada.Containers doesn't allow hash
collisions (which, if true, is demanding a lot of hash function
designers).

A.18.4 (5) says:

5/2{AI95-00302-03} {node (of a map)} A map contains pairs of keys and
elements, called nodes. Map cursors designate nodes, but also can be
thought of as designating an element (the element contained in the node)
for consistency with the other containers. There exists an equivalence
relation on keys, whose definition is different for hashed maps and
ordered maps. A map never contains two or more nodes with equivalent
keys. The length of a map is the number of nodes it contains.{length (of
a map)}

The RM is here:

http://www.adaic.com/standards/05aarm/html/AA-A-18-4.html


You're misreading that paragraph. It does say that:

"A map never contains two or more nodes with equivalent keys."

but that's very different from saying "hash collisions aren't allowed."

That sentence is simply saying that this is a (unique-key) map, not a
multi-map.

Hash functions can map key values to the same hash value (that can
happen easily if your hash function is poor). That's not good if there
are many such collisions, but it's certainly allowed by the standard.

But the hash value is only one aspect of a key used to determine its
uniqueness: the other is equivalence. The hash value of a key
determines its bucket, and the equivalence relation is then used to
compare the key to keys already in that bucket.

So it doesn't matter whether multiple keys hash to the same value (it
would just mean they all get put in the same bucket), since the success
of an insertion (say) is ultimately decided by equivalence.

Take a look at the generic formal region of the hashed map:

generic
type Key_Type is private;

type Element_Type is private;

with function Hash (Key : Key_Type) return Hash_Type;

with function Equivalent_Keys (Left, Right : Key_Type)
return Boolean;

with function "=" (Left, Right : Element_Type)
return Boolean is <>;

package Ada.Containers.Hashed_Maps is

You have to supply both a hash function and an equivalence function.
Typically you pass "=" as the generic actual for Equivalent_Keys, but
not always. (The reason why the general formal is declared that way is
because equivalence is orthogonal to equality.)

Post by Simon Wright
If collisions aren't allowed we could go for an ordered
map based on ... or some likely-to-be-more-efficient order.

If you have as your key a record comprising the 3 strings (nation,
family name, given name), then "=" would be adequate for Equivalent_Keys.

[Simon Wright]

Post by Matthew Heaney

Post by Simon Wright
There's no reason I can see to use maps of maps *for this problem*. I
would use a hash function (Nation x Family_Name x Name) => Hash_Type
in a single map.

Yes, that's right, you could do it either way.
I prefer that OP's approach of using a map of maps of maps, since that
allows you to perform queries like "give me all the entries for this
nation", etc.

But that only works for the first map. You couldn't find all the
Smiths that way.

If that's what you're after, you need (in database terms) a second
independent index.

Post by Matthew Heaney

Post by Simon Wright
Matt, I see (A.18.4(5)) that Ada.Containers doesn't allow hash
collisions (which, if true, is demanding a lot of hash function
designers).

"A map never contains two or more nodes with equivalent keys."
but that's very different from saying "hash collisions aren't allowed."

I've just read (and re-read, and re-read) A.18.5(43) and I see what
you mean. Perhaps it's a bit late. I had read 'same hash =>
equivalent' whereas it's actually 'equivalent => same hash'.

Post by Matthew Heaney
If you have as your key a record comprising the 3 strings (nation,
family name, given name), then "=" would be adequate for
Equivalent_Keys.

I would have a record with (nation, family_name, given_name, age) --
if you have filtered out a container with just the Smiths you'd want
to know the other facts for each of them, too.

[Matthew Heaney]

Post by Simon Wright
But that only works for the first map. You couldn't find all the
Smiths that way.
If that's what you're after, you need (in database terms) a second
independent index.

Right. In the GNAT distribution there's an examples directory that includes
some container examples. The library example does what you suggest, using
multiple containers to provide the necessary query support.

Post by Simon Wright
I've just read (and re-read, and re-read) A.18.5(43) and I see what
you mean. Perhaps it's a bit late. I had read 'same hash =>
equivalent' whereas it's actually 'equivalent => same hash'.

Right.

Post by Simon Wright

Post by Matthew Heaney
If you have as your key a record comprising the 3 strings (nation,
family name, given name), then "=" would be adequate for
Equivalent_Keys.

I would have a record with (nation, family_name, given_name, age) --
if you have filtered out a container with just the Smiths you'd want
to know the other facts for each of them, too.

You could have the map of maps of maps (as in the OP), and use another
container (an ordered multiset, say) whose elements are cursors designating a
family-name/(given-name/age) map. (Using cursors means you never have to
duplicate data.) The cursors would be ordered according to family-name (that
is, by the key that the cursor points to).

Actually, there are probably many ways to do it. During the design of the
container library, both the container and cursor types were declared as
definite and non-limited specifically to facilitate the kinds of composition as
in your example.

[Matthew Heaney]

Post by snoopysalive
And now, my next question: How to handle "hashes of hashes" in Ada?

You have to make two distinct instantiations.

Post by snoopysalive
procedure book is
package Str_Int_Maps is
new Ada.Containers.Indefinite_Hashed_Maps
(String,
Integer,
Ada.Strings.Hash,
"=");
use Str_Int_Maps;
package Str_Map_Maps is
new Ada.Containers.Indefinite_Hashed_Maps
(String,
Str_Int_Maps.Map,
Ada.Strings.Hash,
"=");
Ages : Str_Map_Maps.Map; -- That's the "hash of a hash"
begin
Ages.Insert("family name",Insert("name",23));
end book;
-- Here, the code ends

You have to make two distinct insertions. The first uses the form of Insert
that inserts a key and a default element value (the element here is itself
another map), and the second uses an in-place update to insert a key/elem pair
into the secondary map. Something like:

declare
C : Str_Map_Maps.Cursor;
B : Boolean;
begin
-- this is the insert that inserts an element with its
-- "default value" into the map:
Ages.Insert ("family name", C, B); -- first insert

-- C now designates the map we care about (note that
-- it doesn't matter what value B has)

declare
procedure Update
(S : String; -- the family name
M : in out Str_Int_Maps.Map) is
begin
M.Insert ("name", 23); -- second insert
end;
begin
Ages.Update_Element (C, Update'Access);
end;
end;

Post by snoopysalive
The statement "Ages.Insert("family name",Insert("name",23));" doesn't
"...
map<string, map<string,int>> ages;
ages["family name"]["name"] = 23;
..."

Ada doesn't have an index operator, so it's not going to be as concise as the
C++. If you're doing this a lot then you can always refactor the code above
into its own stand-alone operation. Something like:

procedure Insert
(M : in out Str_Map_Maps.Map;
Family_Name : String;
Name : String;
Age : Integer) is ... -- as above