Hash table

Hash table

[David Trudgett]

I'm looking for a Free Software Ada95 container library, or in
particular, a hash table (or associative list).

I noticed that Ada 2005 may include a standard Ada.Containers library,
but is there a working prototype of this available now?

A bit of searching found the ASL (Ada Structured Library --
http://sourceforge.net/projects/adasl), which hasn't had a new release
since 2001 (which means it must be perfect ;-)). Should I use ASL, and
if I do, will it be completely different from the proposed
Ada.Containers standard?

I'm using Gnat (3.15p) on Debian Linux.

Thanks.

David


-- 

David Trudgett
http://www.zeta.org.au/~wpower/

Most of the major ills of the world have been caused by well-meaning
people who ignored the principle of individual freedom, except as
applied to themselves, and who were obsessed with fanatical zeal to
improve the lot of mankind-in-the-mass through some pet formula of
their own. The harm done by ordinary criminals, murderers, gangsters,
and thieves is negligible in comparison with the agony inflicted upon
human beings by the professional do-gooders, who attempt to set
themselves up as gods on earth and who would ruthlessly force their
views on all others - with the abiding assurance that the end
justifies the means.

    -- Henry Grady Weaver (author), 
       (from The Mainspring of Human Progress) 

Re: Hash table

[Frank]

Hi!

Look around on http://www.adaworld.com/  (and http://www.adapower.com/)
in the Ada Projects->Ada Library, for more info

Frank 

Re: Hash table

[Ludovic Brenta]

David Trudgett <wpower@zeta.org.au.nospamplease> writes:
> I'm looking for a Free Software Ada95 container library, or in
> particular, a hash table (or associative list).
>
> I noticed that Ada 2005 may include a standard Ada.Containers library,
> but is there a working prototype of this available now?

Ada.Containers has not been finalised yet; what is known at this time
is that they require an Ada 200y compiler and thus will not work with
GNAT 3.15p.  If you feel like experimenting with bleeding-edge stuff,
off the top of my head I can think of four places where you can get
different versions of Ada.Containers:

- The home page on Tigris for both Charles and Ada.Containers[1]
- gnat-3.4 (in Debian sarge aka stable)
- gnat-4.0 (in Debian etch aka testing)
- and a port of Ada.Containers to Ada 95 by Martin Dowie[2].

But I recommend neither of them for now; see below.

> A bit of searching found the ASL (Ada Structured Library --
> http://sourceforge.net/projects/adasl), which hasn't had a new release
> since 2001 (which means it must be perfect ;-)). Should I use ASL, and
> if I do, will it be completely different from the proposed
> Ada.Containers standard?

Yes, ASL will be completely different from Ada.Containers.

> I'm using Gnat (3.15p) on Debian Linux.

You are in luck, as are all Debian users who program in Ada :)

apt-get install libcharles0-dev

will install Charles, the precursor container library to
Ada.Containers (in fact, Matt Heaney submitted Charles as his proposal
for the standard containers).  Its interface is similar to that of
Ada.Containers.  I recommend you use that for the time being.

HTH

[1] http://charles.tigris.org
[2] http://www.martin.dowie.btinternet.co.uk/

-- 
Ludovic Brenta.

Re: Hash table

[Matthew Heaney]

David Trudgett <wpower@zeta.org.au.nospamplease>  writes:

> I'm looking for a Free Software Ada95 container library, or in
> particular, a hash table (or associative list).

Ada 2005 will have both sets and maps.  You're asking specifically for a
hashed version, but keep in mind that an ordered container (having an
identical interface, but different time complexity) might satisfy your
needs just as well.

The hashed containers are:

ada.containers.hashed_sets
ada.containers.indefinite_hashed_sets
ada.containers.hashed_maps
ada.containers.indefinite_hashed_maps

The ordered forms are:

ada.containers.ordered_sets
ada.containers.indefinite_ordered_sets
ada.containers.ordered_maps
ada.containers.indefinite_ordered_maps


> I noticed that Ada 2005 may include a standard Ada.Containers library,
> but is there a working prototype of this available now?

Yes, there's a public reference implementation available here:

http://charles.tigris.org/

Follow the links to the CVS repository, to the ai302 subdirectory.  The
names use gnat run-time syntax, so you're looking for:

a-cohama.ad[sb]
a-cihama.ad[sb]
a-cohase.ad[sb]
a-cihase.ad[sb]

Note that these will only compile with an Ada 2005 compiler.  If you're
using the latest version of gnat, use the -gnat05 switch to compile them.

If you don't have an Ada 2005 compiler, then you can modify the sources
to your liking.  That will mean replacing an anonymous access subprogram
parameters with something else, typically a generic operation that
passes the subprogram as a generic formal.  For example, the procedure:

procedure Iterate
  (Container : in Map;
   Process   : not null access procedure (Position : Cursor));

should be re-written as:

generic
   with procedure Process (Position : Cursor);
procedure Generic_Iteration (Container : in Map);

(Note that replacing the anonymous access subprogram parameters with
named access parameters is probably not what you want, because of the
accessibility rules.  Hence the generic declaration above.)


> A bit of searching found the ASL (Ada Structured Library --
> http://sourceforge.net/projects/adasl), which hasn't had a new release
> since 2001 (which means it must be perfect ;-)). Should I use ASL, and
> if I do, will it be completely different from the proposed
> Ada.Containers standard?

I would try to use a reference implementation of the standard library,
modified as necessary to run under pure Ada 95.  I can help you make the
necessary modifications.

In general, we prefer that users use the standard library now, since
that helps us find bugs in the design of the library (early adopters
have been extremely helpful here), and in the actual implementation of
the library.


> I'm using Gnat (3.15p) on Debian Linux.

Do you have access to gcc 4.x?  The standard container library is
already bundled with the gcc 4 release.

-Matt

Re: Hash table

[David Trudgett]

Ludovic Brenta <ludovic.brenta@tiscali.be> writes:

>
>> I'm using Gnat (3.15p) on Debian Linux.
>
> You are in luck, as are all Debian users who program in Ada :)

I take it from one of your posts that you are the maintainer of the
Debian Ada stuff. I appreciate your work in making it as painless as
possible for newbies like me to get started! Good work! :-)


>
> apt-get install libcharles0-dev

Sounds like this is what I'm looking for. I'll give it a work out and
see how it goes!

>
> will install Charles, the precursor container library to
> Ada.Containers (in fact, Matt Heaney submitted Charles as his proposal
> for the standard containers).  Its interface is similar to that of
> Ada.Containers.  I recommend you use that for the time being.

Thanks for your advice.

David


-- 

David Trudgett
http://www.zeta.org.au/~wpower/

We come here upon what, in a large proportion of cases, forms the
source of the grossest errors of mankind. Men on a lower level of
understanding, when brought into contact with phenomena of a higher
order, instead of making efforts to understand them, to raise
themselves up to the point of view from which they must look at the
subject, judge it from their lower standpoint, and the less they
understand what they are talking about, the more confidently and
unhesitatingly they pass judgment on it.

    -- Leo Tolstoy, "The Kingdom of God is Within You"

Re: Hash table

[David Trudgett]

Hi Matthew,

Matthew Heaney <matthewjheaney@earthlink.net> writes:

> David Trudgett <wpower@zeta.org.au.nospamplease>  writes:
>
>> I'm looking for a Free Software Ada95 container library, or in
>> particular, a hash table (or associative list).
>
> Ada 2005 will have both sets and maps.  You're asking specifically for a
> hashed version, but keep in mind that an ordered container (having an

Yes, when I used those terms, I did so from the point of view of
someone with some experience in Perl and Common Lisp. 


> identical interface, but different time complexity) might satisfy your
> needs just as well.

Whether ordered or not is not really important for my current
immediate use, as you say. However, I knew that a container library
would generally provide various types for various uses.

While learning Ada, I am porting a simple Common Lisp program that I
wrote not long ago (partly based on a tutorial in a book) to play
computer vs human noughts and crosses.
(http://www.zeta.org.au/~wpower/dkt/programs/tictactoe.lisp) This
program makes use of simple associative lists for a couple of little
lookup jobs; hence the desire to find an Ada equivalent. I could just
use an array solution probably for something this simple, but it's a
learning exercise more than a practical application.


>
> If you don't have an Ada 2005 compiler, then you can modify the sources
> to your liking.  That will mean replacing an anonymous access subprogram
> parameters with something else, typically a generic operation that
> passes the subprogram as a generic formal.  For example, the procedure:
>
> procedure Iterate
>   (Container : in Map;
>    Process   : not null access procedure (Position : Cursor));
>
> should be re-written as:
>
> generic
>    with procedure Process (Position : Cursor);
> procedure Generic_Iteration (Container : in Map);
>
> (Note that replacing the anonymous access subprogram parameters with
> named access parameters is probably not what you want, because of the
> accessibility rules.  Hence the generic declaration above.)

As a newbie, all this is a bit over my head! ;-)


>
>
>> A bit of searching found the ASL (Ada Structured Library --
>> http://sourceforge.net/projects/adasl), which hasn't had a new release
>> since 2001 (which means it must be perfect ;-)). Should I use ASL, and
>> if I do, will it be completely different from the proposed
>> Ada.Containers standard?
>
> I would try to use a reference implementation of the standard library,
> modified as necessary to run under pure Ada 95.  I can help you make the
> necessary modifications.

Thanks for the offer of help. I was going to have a look at Charles
first and see how I go.


>
> In general, we prefer that users use the standard library now, since
> that helps us find bugs in the design of the library (early adopters
> have been extremely helpful here), and in the actual implementation of
> the library.

Well, I would like to be helpful if I can, and it would be good to get
some hands-on experience with the new container library (reference). I
may save it for when I know a bit more than I do now, though!


>
>
>> I'm using Gnat (3.15p) on Debian Linux.
>
> Do you have access to gcc 4.x?  The standard container library is
> already bundled with the gcc 4 release.

Yes, it's probably just an apt-get away, but one step at a time! ;-)
I'm also now in the midst of some system housekeeping work that
could'nt wait, so it might be a day or three before I get some more
time to work on this...  

Thanks for taking time to reply to my query.

David


-- 

David Trudgett
http://www.zeta.org.au/~wpower/

As for those who profit by the privileges gained by previous acts of
violence, they often forget and like to forget how these privileges
were obtained. But one need only recall the facts of history, not the
history of the exploits of different dynasties of rulers, but real
history, the history of the oppression of the majority by a small
number of men, to see that all the advantages the rich have over the
poor are based on nothing but flogging, imprisonment, and murder.

    -- Leo Tolstoy, "The Kingdom of God is Within You"

Re: Hash table

[Martin Dowie]

David Trudgett wrote:
>>will install Charles, the precursor container library to
>>Ada.Containers (in fact, Matt Heaney submitted Charles as his proposal
>>for the standard containers).  Its interface is similar to that of
>>Ada.Containers.  I recommend you use that for the time being.

The Charles API is nothing like the Ada.Containers API IMHO but if
you are happy to use it rather than the new standard API it doesn't
really matter! :-)

Matt and I don't agree on exactly what to use if you want to use
something that will be like the Ada200Y API - he like generics as
you can use them in an Ada200Y fashion, I think that if you are
using Ada95 an Ada95 access type fashion is good enough (is this
accurate Matt?). But with the 'standard' now sooooo close to being
accepted (at least by the ARG) all the compiler vendors will pull
the finger out on this one at least and start supporting the
extentions needed.

Cheers

-- Martin
(http://www.martin.dowie.btinternet.co.uk/ home of the now slightly
out of date Ada95 version of the the Ada200Y container library.
Really must get that updated someday... ;-)

Re: Hash table

[Martin Dowie]

Martin Dowie wrote:
> Matt and I don't agree on exactly what to use if you want to use
> something that will be like the Ada200Y API - he like generics as
> you can use them in an Ada200Y fashion, I think that if you are
> using Ada95 an Ada95 access type fashion is good enough (is this
> accurate Matt?). But with the 'standard' now sooooo close to being
> accepted (at least by the ARG)

Should have been an "I would hope" here... :-)

> all the compiler vendors will pull
> the finger out on this one at least and start supporting the
> extentions needed.

Re: Hash table

[Matthew Heaney]

Martin Dowie wrote:
> > Matt and I don't agree on exactly what to use if you want to use
> > something that will be like the Ada200Y API - he like generics as
> > you can use them in an Ada200Y fashion, I think that if you are
> > using Ada95 an Ada95 access type fashion is good enough (is this
> > accurate Matt?).

No, the named access type approach is *not* good enough, because it's
impossible to use a locally-declared subprogram (the only thing that
makes any sense) as the iterator parameter.

Re: Hash table

[Martin Dowie]

Matthew Heaney wrote:
> Martin Dowie wrote:
>>> Matt and I don't agree on exactly what to use if you want to use
>>> something that will be like the Ada200Y API - he like generics as
>>> you can use them in an Ada200Y fashion, I think that if you are
>>> using Ada95 an Ada95 access type fashion is good enough (is this
>>> accurate Matt?).
>
> No, the named access type approach is *not* good enough, because it's
> impossible to use a locally-declared subprogram (the only thing that
> makes any sense) as the iterator parameter.

Well, I have written some programs that do this using package level and
while it isn't as nice as Ada200Y will be, it does work and it has the
benefit of not needing to be changed when I can move to an Ada200Y
compiler. That's a bigger hurdle for me than using the generic solution,
which would have to change.

Cheers

-- Martin