How to use associative arrays in Ada 2005?

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

Re: How to use associative arrays in Ada 2005?

[Georg Bauhaus]

On Tue, 2006-11-21 at 02:11 -0800, snoopysalive wrote:

> 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.


>  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.

Re: How to use associative arrays in Ada 2005?

[Matthew Heaney]

"snoopysalive" <matthias.kistler@gmx.de> writes:

> 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.


> 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.


> 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;


> 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.


> 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

Re: How to use associative arrays in Ada 2005?

[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

Re: How to use associative arrays in Ada 2005?

[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

Re: How to use associative arrays in Ada 2005?

[Georg Bauhaus]

On Thu, 2006-11-23 at 11:27 -0800, snoopysalive wrote:

> 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 :-)

>  So, how is it possible to do something like this in C++:
> "...
> map<string, map<string,int>> ages;
> ages["family name"]["name"] = 23;
> ..."

Re: How to use associative arrays in Ada 2005?

[Georg Bauhaus]

On Thu, 2006-11-23 at 11:27 -0800, snoopysalive wrote:

> 
> 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;
> ..."

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.

Re: How to use associative arrays in Ada 2005?

[Dmitry A. Kazakov]

On 23 Nov 2006 11:27:31 -0800, snoopysalive wrote:

> 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;
> ..."

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;
...

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: How to use associative arrays in Ada 2005?

[Matthew Heaney]

"snoopysalive" <matthias.kistler@gmx.de> writes:

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

You have to make two distinct instantiations.


> 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;
   

> 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;
> ..."

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

Re: How to use associative arrays in Ada 2005?

[Matthew Heaney]

Georg Bauhaus <bauhaus@futureapps.de> writes:

> 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.


> 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.


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

Ouch!  A lot of copying here...

> 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.


>     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).  


>     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);

>     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.)


>         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.


>     end loop;
> end book2;

Re: How to use associative arrays in Ada 2005?

[Matthew Heaney]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> But this does not look like a hash of hashes. 

A map of maps works great...

Re: How to use associative arrays in Ada 2005?

[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

Re: How to use associative arrays in Ada 2005?

[Matthew Heaney]

"snoopysalive" <matthias.kistler@gmx.de> writes:

> 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.


>   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);

Re: How to use associative arrays in Ada 2005?

[Dmitry A. Kazakov]

On 26 Nov 2006 11:05:54 -0800, snoopysalive wrote:

> 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

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.

> 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.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: How to use associative arrays in Ada 2005?

[Matthew Heaney]

Dmitry A. Kazakov wrote:
>
> 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...

Re: How to use associative arrays in Ada 2005?

[Simon Wright]

"snoopysalive" <matthias.kistler@gmx.de> writes:

> 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.

Re: How to use associative arrays in Ada 2005?

[Dmitry A. Kazakov]

On 27 Nov 2006 11:53:43 -0800, Matthew Heaney wrote:

> Dmitry A. Kazakov wrote:
>>
>> 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.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: How to use associative arrays in Ada 2005?

[Matthew Heaney]

Dmitry A. Kazakov wrote:
> 
> ... 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...


> 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...


> 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.

Re: How to use associative arrays in Ada 2005?

[Matthew Heaney]

Simon Wright wrote:
> 
> 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.


> 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.)


 > 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.

Re: How to use associative arrays in Ada 2005?

[Simon Wright]

Matthew Heaney <mheaney@on2.com> writes:

> Simon Wright wrote:
>>
>> 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.

>> 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). 
>
> 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."

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

> 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.

Re: How to use associative arrays in Ada 2005?

[Matthew Heaney]

Simon Wright <simon@pushface.org> writes:

> 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.


> 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.


> > 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.  

Re: How to use associative arrays in Ada 2005?

[Alex R. Mosteo]

Matthew Heaney wrote:

> Dmitry A. Kazakov wrote:
>> 
>> ... 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.

Re: How to use associative arrays in Ada 2005?

[Dmitry A. Kazakov]

On Mon, 27 Nov 2006 16:52:03 -0500, Matthew Heaney wrote:

> Dmitry A. Kazakov wrote:

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

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: How to use associative arrays in Ada 2005?

[Matthew Heaney]

"Alex R. Mosteo" <devnull@mailinator.com> writes:

> 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.

Re: How to use associative arrays in Ada 2005?

[Matthew Heaney]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> 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!