Ada Components - GRACE Lists

Ada Components - GRACE Lists

[Marin David Condic]

Anything happening lately on the GRACE components (lists) that we were
discussing here? Has this withered on the vine? Or is there still some
interest in getting it done & posted somewhere semi-official? (AdaPower?)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/

Re: Ada Components - GRACE Lists

[Pat Rogers]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in message
news:a48p2k$nop$1@nh.pace.co.uk...
> Anything happening lately on the GRACE components (lists) that we were
> discussing here? Has this withered on the vine? Or is there still some
> interest in getting it done & posted somewhere semi-official? (AdaPower?)

Is this my cue to reiterate that we should settle on an existing library?  :-)
:-) :-)

Re: Ada Components - GRACE Lists

[Eric Merritt]

I was actually running this as well.

--- Pat Rogers <progers@classwide.com> wrote:
> "Marin David Condic"
> <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
> message
> news:a48p2k$nop$1@nh.pace.co.uk...
> > Anything happening lately on the GRACE components
> (lists) that we were
> > discussing here? Has this withered on the vine? Or
> is there still some
> > interest in getting it done & posted somewhere
> semi-official? (AdaPower?)
> 
> Is this my cue to reiterate that we should settle on
> an existing library?  :-)
> :-) :-)
> 
> 
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada.eu.org
> http://ada.eu.org/mailman/listinfo/comp.lang.ada


__________________________________________________
Do You Yahoo!?
Send FREE Valentine eCards with Yahoo! Greetings!
http://greetings.yahoo.com

Re: Ada Components - GRACE Lists

[Pat Rogers]

Not sure what you mean...



> I was actually running this as well.
> 
> --- Pat Rogers <progers@classwide.com> wrote:
> > "Marin David Condic"
> > <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
> > message
> > news:a48p2k$nop$1@nh.pace.co.uk...
> > > Anything happening lately on the GRACE components
> > (lists) that we were
> > > discussing here? Has this withered on the vine? Or
> > is there still some
> > > interest in getting it done & posted somewhere
> > semi-official? (AdaPower?)
> > 
> > Is this my cue to reiterate that we should settle on
> > an existing library?  :-)
> > :-) :-)
> > 
> > 
> > _______________________________________________
> > comp.lang.ada mailing list
> > comp.lang.ada@ada.eu.org
> > http://ada.eu.org/mailman/listinfo/comp.lang.ada
> 
> 
> __________________________________________________
> Do You Yahoo!?
> Send FREE Valentine eCards with Yahoo! Greetings!
> http://greetings.yahoo.com

Re: Ada Components - GRACE Lists

[Eric Merritt]

see below ->
--- Pat Rogers <progers@classwide.com> wrote:
> Not sure what you mean...
> 
> 
> 
> > I was actually running this as well.

Where did that come from? It should read -> I was
actually wondaring this myself.

> > 
> > --- Pat Rogers <progers@classwide.com> wrote:
> > > "Marin David Condic"
> > > <dont.bother.mcondic.auntie.spam@[acm.org> wrote
> in
> > > message
> > > news:a48p2k$nop$1@nh.pace.co.uk...
> > > > Anything happening lately on the GRACE
> components
> > > (lists) that we were
> > > > discussing here? Has this withered on the
> vine? Or
> > > is there still some
> > > > interest in getting it done & posted somewhere
> > > semi-official? (AdaPower?)
> > > 
> > > Is this my cue to reiterate that we should
> settle on
> > > an existing library?  :-)
> > > :-) :-)
> > > 
> > > 
> > > _______________________________________________
> > > comp.lang.ada mailing list
> > > comp.lang.ada@ada.eu.org
> > > http://ada.eu.org/mailman/listinfo/comp.lang.ada
> > 
> > 
> > __________________________________________________
> > Do You Yahoo!?
> > Send FREE Valentine eCards with Yahoo! Greetings!
> > http://greetings.yahoo.com
> 
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada.eu.org
> http://ada.eu.org/mailman/listinfo/comp.lang.ada


__________________________________________________
Do You Yahoo!?
Send FREE Valentine eCards with Yahoo! Greetings!
http://greetings.yahoo.com

Re: Ada Components - GRACE Lists

[Marin David Condic]

You know I've said before that I could get behind that - especially if there
was some agreement on a library forthcoming from the compiler vendors. I'd
hope that if a handful of them expressed an opinion on the subject that some
significant number of us would similarly fall in line.

Still, the GRACE stuff seemed very well thought out and Ted did a great job
of putting together the spec. We seemed to have a fair number of people's
input to it & some modicum of consensus that - if it wasn't exactly loved by
all - it would cause as little grief as possible for most. Maybe we could
declare victory on V0.1 (including only Lists), flesh it out and put it on a
website somewhere? Agree that it should be Public Domain? (GMGPL? Something
Else?) See if it might gain some use & acceptance? Press on with Maps?

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Pat Rogers" <progers@classwide.com> wrote in message
news:Dr%98.37987$wH3.1200447599@newssvr12.news.prodigy.com...
>
> Is this my cue to reiterate that we should settle on an existing library?
:-)
> :-) :-)
>
>

Re: Ada Components - GRACE Lists

[Eric Merritt]

Here, Here! This is exaclty what should happen. Please
dont let this effort die.
--- Marin David Condic
<dont.bother.mcondic.auntie.spam@[acm.org>]>,
MISSING_MAILBOX_TERMINATOR@.SYNTAX-ERROR. wrote:
> You know I've said before that I could get behind
> that - especially if there
> was some agreement on a library forthcoming from the
> compiler vendors. I'd
> hope that if a handful of them expressed an opinion
> on the subject that some
> significant number of us would similarly fall in
> line.
> 
> Still, the GRACE stuff seemed very well thought out
> and Ted did a great job
> of putting together the spec. We seemed to have a
> fair number of people's
> input to it & some modicum of consensus that - if it
> wasn't exactly loved by
> all - it would cause as little grief as possible for
> most. Maybe we could
> declare victory on V0.1 (including only Lists),
> flesh it out and put it on a
> website somewhere? Agree that it should be Public
> Domain? (GMGPL? Something
> Else?) See if it might gain some use & acceptance?
> Press on with Maps?
> 
> MDC
> --
> Marin David Condic
> Senior Software Engineer
> Pace Micro Technology Americas    www.pacemicro.com
> Enabling the digital revolution
> e-Mail:    marin.condic@pacemicro.com
> Web:      http://www.mcondic.com/
> 
> 
> "Pat Rogers" <progers@classwide.com> wrote in
> message
>
news:Dr%98.37987$wH3.1200447599@newssvr12.news.prodigy.com...
> >
> > Is this my cue to reiterate that we should settle
> on an existing library?
> :-)
> > :-) :-)
> >
> >
> 
> 
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada.eu.org
> http://ada.eu.org/mailman/listinfo/comp.lang.ada


__________________________________________________
Do You Yahoo!?
Send FREE Valentine eCards with Yahoo! Greetings!
http://greetings.yahoo.com

Re: Ada Components - GRACE Lists

[Pat Rogers]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in message
news:a4bl8h$6v7$1@nh.pace.co.uk...
> You know I've said before that I could get behind that - especially if there
> was some agreement on a library forthcoming from the compiler vendors. I'd
> hope that if a handful of them expressed an opinion on the subject that some
> significant number of us would similarly fall in line.

Two of them -- a significant number, really -- have said that they will meet
customer demand.  In effect, that we have to push it to them, not the other way
around.

> Still, the GRACE stuff seemed very well thought out and Ted did a great job
> of putting together the spec. We seemed to have a fair number of people's
> input to it & some modicum of consensus that - if it wasn't exactly loved by
> all - it would cause as little grief as possible for most. Maybe we could
> declare victory on V0.1 (including only Lists), flesh it out and put it on a
> website somewhere? Agree that it should be Public Domain? (GMGPL? Something
> Else?) See if it might gain some use & acceptance? Press on with Maps?

If it happens, great -- I'll support it, and I believe the vendors will too if
enough of us ask for it.  I certainly don't mean this as an "I told you so."
It's just that over the past 22 years I've seen similar efforts start but not
finish.

Re: Ada Components - GRACE Lists

[Nick Roberts]

On Mon, 11 Feb 2002 10:47:30 -0500, "Marin David Condic"
<dont.bother.mcondic.auntie.spam@[acm.org> strongly typed:

>Anything happening lately on the GRACE components (lists) that we were
>discussing here? Has this withered on the vine? Or is there still some
>interest in getting it done & posted somewhere semi-official? (AdaPower?)

I am still working on Tenet, which I estimate will be ready in two or three
months from now. I'll publish it wherever it'll be had. It's not going to
be a 'standard', but may be a handy toolkit for those who like it.

-- 
Nick Roberts

Re: Ada Components - GRACE Lists

[Jeffrey Carter]

GRACE was the name of the Ada-83 components from EVB (Generic Reusable
Ada Components for Engineering). Here you seem to be using it to refer
to the list component that we fought about here, ending up with
something nobody liked but many of us could live with. Did someone name
that GRACE while I wasn't looking?

-- 
Jeff Carter
"Your mother was a hamster and your father smelt of elderberries."
Monty Python & the Holy Grail

Re: Ada Components - GRACE Lists

[Marin David Condic]

Well, maybe "nobody liked" is a little strong - I thought it was pretty good
and quite servicable. :-)

Ted Dennison seemed to like the moniker "GRACE" and had an acronym worked
out for it. Also in honor of Grace Hopper. Try looking up the old posts on
this subject - lots of names were kicked around.

Me? I'm not married to the name. Assuming this effort moves forward, I could
go with just about anything that consumes five or fewer characters. (I liked
"ACE" - short and leading to lots of card-game spinoff names - but feel free
to suggest ones of your own.)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Jeffrey Carter" <jrcarter@acm.org> wrote in message
news:3C6B134B.9114B686@acm.org...
> GRACE was the name of the Ada-83 components from EVB (Generic Reusable
> Ada Components for Engineering). Here you seem to be using it to refer
> to the list component that we fought about here, ending up with
> something nobody liked but many of us could live with. Did someone name
> that GRACE while I wasn't looking?
>

Re: Ada Components - GRACE Lists

[Ted Dennison]

Marin David Condic wrote:

> Anything happening lately on the GRACE components (lists) that we were
> discussing here? Has this withered on the vine? Or is there still some
> interest in getting it done & posted somewhere semi-official? (AdaPower?)


I just got back from my 2 week Olympic vacation and came across this.

The current status as near as I can tell is the following:

1  We have a spec for unbounded lists.
2  I have an implementation, which is mostly tested.
3  I have a request in about the name, but only got a response that the 
request was being forwarded. Its tough going because I can't find any 
contact information for the folks who made the old Ada83 "GRACE" 
components. I think they may be essentially dead and gone. Given that, 
and the fact that they trademarked "GRACE" and not "Grace", I think we 
may be OK using the name (at least tenatively during the beta stages), 
but I'm sure some will disagree.

4  Before releasing what I have, I'm beginning to think the effort 
requires something considerably more formal that what we have been 
working for. In particular, I'd like to see a full-blown CVS-controlled 
project, perhaps hosted on Savannah or AdaPower. This would also allow 
us to take some of the discussion traffic off of the newsgroup, which I 
think some here would be very appreciative of.

Mostly what has been sidetracking progress is that I'd like to do 4, but 
to do it we need some kind of resolution of 3 (I'd imagine changing the 
name of a hosted project would be a real pain).

---
T.E.D.

(I survived the 2002 winter olympics)

Re: Ada Components - GRACE Lists

[Nick Roberts]

On Sat, 23 Feb 2002 01:26:29 GMT, Ted Dennison <dennison@telepath.com>
strongly typed:

>3  I have a request in about the name, but only got a response that the 
>request was being forwarded. Its tough going because I can't find any 
>contact information for the folks who made the old Ada83 "GRACE" 
>components. I think they may be essentially dead and gone. Given that, 
>and the fact that they trademarked "GRACE" and not "Grace", I think we 
>may be OK using the name (at least tenatively during the beta stages), 
>but I'm sure some will disagree.

Might it be possible for you to contact the US trademarking authority to
see if you can get a confirmation that it was never trademarked, or that it
has officially lapsed, or maybe contact information?

I have a suspicion that "Grace" would not be trademarkable, since it is an
English (dictionary) word. I'm really not sure about "GRACE".

>4  Before releasing what I have, I'm beginning to think the effort 
>requires something considerably more formal that what we have been 
>working for. In particular, I'd like to see a full-blown CVS-controlled 
>project, perhaps hosted on Savannah or AdaPower. 

You will have to ask David Botton, but I myself have no objection to you
using the ASCL 'slot' on AdaPower.net, should you wish. (I never uploaded
anything to AdaPower.net/ASCL.) It may be an idea to consult Michael
Erdmann also.

>This would also allow 
>us to take some of the discussion traffic off of the newsgroup, which I 
>think some here would be very appreciative of.

I personally have no objection (to the discussion being on comp.lang.ada).

>Mostly what has been sidetracking progress is that I'd like to do 4, but 
>to do it we need some kind of resolution of 3 (I'd imagine changing the 
>name of a hosted project would be a real pain).

Surely you could host it under a 'working name' that wouldn't confuse
anyone ("Ada Container Library" or indeed "ASCL") and release it under its
proper name when the time comes?

>I just got back from my 2 week Olympic vacation and came across this.
>(I survived the 2002 winter olympics)

Gosh, did you actually compete in something? (Pardon my ignorance.)

All the best,
-- 
Nick Roberts

Re: Ada Components - GRACE Lists

[Richard Riehle]

Ted Dennison wrote:

> Marin David Condic wrote:
>
>
>  Its tough going because I can't find any
> contact information for the folks who made the old Ada83 "GRACE"
> components. I think they may be essentially dead and gone. Given that,
> and the fact that they trademarked "GRACE" and not "Grace", I think we
> may be OK using the name (at least tenatively during the beta stages),
> but I'm sure some will disagree.

EVB Software Engineering, the company that had the trademark for GRACE
is dormant, probably moribund.    However, I know how to contact the last
CEO of EVB and will send her a message to ask about this.

Perhaps she would be willing to post an answer to comp.lang.ada.

Richard Riehle

Re: Ada Components - GRACE Lists

[Ted Dennison]

Richard Riehle wrote:

>> Its tough going because I can't find any
>>contact information for the folks who made the old Ada83 "GRACE"
>>components. I think they may be essentially dead and gone. Given that,
> 
> EVB Software Engineering, the company that had the trademark for GRACE
> is dormant, probably moribund.    However, I know how to contact the last
> CEO of EVB and will send her a message to ask about this.

I'd appreciate that. I got hold of someone who I think also tried to get 
hold of her a month or so ago, with no effect. But perhaps you have 
better contact info for her than he did.

--
T.E.D.

Re: Ada Components - GRACE Lists

[Marin David Condic]

Ted:

If you could e-mail me a copy of what you have, I'd appreciate it. Or post
it somehwere & pass along the URL. Thanks.

As for the name? If this is going to be at all problematic, I suggest just
using a new name. Plenty of names are available without a) risking any
infringement on anyone's trademark and b) confusing any potential users with
a name similar to something else. Maybe its best to avoid this one and pick
something else.

As for #4? Until there's something more substantial, I'd think worrying
about configuration management is unnecessary. Plenty of these sorts of
packages are just posted to a website with somebody volunteering to be the
Keeper Of The Eternal Flame & managing the changes locally. (It ought to be
something that gets pretty stable pretty quickly, don't you think?) If it
gets anywhere & starts expanding, worrying about CVS, etc, might make some
sense down the line.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:3C76EE71.40506@telepath.com...
> Marin David Condic wrote:
>
> > Anything happening lately on the GRACE components (lists) that we were
> > discussing here? Has this withered on the vine? Or is there still some
> > interest in getting it done & posted somewhere semi-official?
(AdaPower?)
>
>
> I just got back from my 2 week Olympic vacation and came across this.
>
> The current status as near as I can tell is the following:
>
> 1  We have a spec for unbounded lists.
> 2  I have an implementation, which is mostly tested.
> 3  I have a request in about the name, but only got a response that the
> request was being forwarded. Its tough going because I can't find any
> contact information for the folks who made the old Ada83 "GRACE"
> components. I think they may be essentially dead and gone. Given that,
> and the fact that they trademarked "GRACE" and not "Grace", I think we
> may be OK using the name (at least tenatively during the beta stages),
> but I'm sure some will disagree.
>
> 4  Before releasing what I have, I'm beginning to think the effort
> requires something considerably more formal that what we have been
> working for. In particular, I'd like to see a full-blown CVS-controlled
> project, perhaps hosted on Savannah or AdaPower. This would also allow
> us to take some of the discussion traffic off of the newsgroup, which I
> think some here would be very appreciative of.
>
> Mostly what has been sidetracking progress is that I'd like to do 4, but
> to do it we need some kind of resolution of 3 (I'd imagine changing the
> name of a hosted project would be a real pain).
>
> ---
> T.E.D.
>
> (I survived the 2002 winter olympics)
>
>
>

Re: Ada Components - GRACE Lists

[Ted Dennison]

nickroberts@ukf.net (Nick Roberts) wrote in message news:<3c77bfff.325065109@news.cis.dfn.de>...
> On Sat, 23 Feb 2002 01:26:29 GMT, Ted Dennison <dennison@telepath.com>
> strongly typed:
> >and the fact that they trademarked "GRACE" and not "Grace", I think we 
> >may be OK using the name (at least tenatively during the beta stages), 
> >but I'm sure some will disagree.
> 
> Might it be possible for you to contact the US trademarking authority to
> see if you can get a confirmation that it was never trademarked, or that it
> has officially lapsed, or maybe contact information?

I suppose that could be looked into. If the company is truly defunct
though, I don't think it matters much if the trademark has another
year or so to go.

> I have a suspicion that "Grace" would not be trademarkable, since it is an
> English (dictionary) word. I'm really not sure about "GRACE".

Good point. They'd probably have to stick an "i", "e", or "m" in front
of it to do that. :-)

> >I just got back from my 2 week Olympic vacation and came across this.
> >(I survived the 2002 winter olympics)
> 
> Gosh, did you actually compete in something? (Pardon my ignorance.)

Heck no (unless you count driving through blizzards). I'm not exactly
a 22 year-old speed demon any more. However, judging from the US
curling team, I'd have quite a ways to go before I'm too old and out
of shape for that sport. :-)

---
T.E.D.

Re: Ada Components - GRACE Lists

[Matthew Heaney]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:3C76EE71.40506@telepath.com...
> The current status as near as I can tell is the following:
>
> 1  We have a spec for unbounded lists.
> 2  I have an implementation, which is mostly tested.

If anyone is interested, the data structure library "charles" also comes
with list types:

http://home.earthlink.net/~matthewjheaney/charles/charles-unbounded_lists__a
ds.htm
http://home.earthlink.net/~matthewjheaney/charles/charles-bounded_lists__ads
.htm
http://home.earthlink.net/~matthewjheaney/charles/charles-limited_unbounded_
lists__ads.htm
http://home.earthlink.net/~matthewjheaney/charles/charles-limited_bounded_li
sts__ads.htm
http://home.earthlink.net/~matthewjheaney/charles/charles-double_lists__ads.
htm
http://home.earthlink.net/~matthewjheaney/charles-20020213.zip

Re: Ada Components - GRACE Lists

[Nick Roberts]

On 25 Feb 2002 07:42:02 -0800, dennison@telepath.com (Ted Dennison)
strongly typed:

>nickroberts@ukf.net (Nick Roberts) wrote:
>> Gosh, did you actually compete in something? (Pardon my ignorance.)
>
>Heck no (unless you count driving through blizzards). I'm not exactly
>a 22 year-old speed demon any more. However, judging from the US
>curling team, I'd have quite a ways to go before I'm too old and out
>of shape for that sport. :-)

Well, you just might be able to get 'blizzard driving' entered as an
Olympic sport in four years time. ;-)

I'd like to express my congratulations to the US winter Olympic team, whom
I gather won a welter of medals this year. Well done!

-- 
Nick Roberts

Re: Ada Components - GRACE Lists (Sorting them)

[Chad R. Meiners]

I remembering that there was a discussion about using quicksort for these
list components.  There was naturally concern about the O(n^2) worst case
performance.  If people are still worried about this issue, I have a
solution that guarantees that quicksort worst case is O(n*log n).  Before
any of you spill your coffee ;-) there is a hefty constant involved that
makes this modified quicksort slower on average than heapsort (maybe
mergesort sort also but it doesn't take more space that mergesort).  Anyway
the idea is to choose the median of each list (sublist) in linear time.
There happens to be a 'well known algorithm' for this.  The only drawback is
a hit on the constant.  I figure it might not be too bad of a price to pay,
though.

Comments?

-CRM

Re: Ada Components - GRACE Lists (Sorting them)

[Thomas Wolf]

crmeiners@hotmail.com wrote:
> I remembering that there was a discussion about using quicksort for these
> list components.  There was naturally concern about the O(n^2) worst case
> performance.  If people are still worried about this issue, I have a
> solution that guarantees that quicksort worst case is O(n*log n).  Before
> any of you spill your coffee ;-) there is a hefty constant involved that
> makes this modified quicksort slower on average than heapsort (maybe
> mergesort sort also but it doesn't take more space that mergesort).  Anyway
> the idea is to choose the median of each list (sublist) in linear time.
> There happens to be a 'well known algorithm' for this.  The only drawback is
> a hit on the constant.  I figure it might not be too bad of a price to pay,
> though.

For lists, mergesort is not a bad choice: worst-case O(n*log n), and
the constant factor compared to a quicksort on arrays is not that bad.

If you want a quicksort with worst-case O(n*log n), check out 
introspective sort. Performs just as well as quicksort, but
avoids the quadratic worst case. Basically it counts the nesting
depth and switches to heapsort if that count gets significantly
greater than log n, assuming that in this case, it has hit a worst-
case input for quicksort. Because it counts the nesting depth, it
can get by with a standard median-of-three pivot selection; no need
for fancy things like choosing the true median.

-- 
-----------------------------------------------------------------
Thomas Wolf                          e-mail: t_wolf@angelfire.com

Re: Ada Components - GRACE Lists (Sorting them)

[Ted Dennison]

"Chad R. Meiners" <crmeiners@hotmail.com> wrote in message news:<a5fs6c$2cir$1@msunews.cl.msu.edu>...
> list components.  There was naturally concern about the O(n^2) worst case
> performance.  If people are still worried about this issue, I have a
> solution that guarantees that quicksort worst case is O(n*log n).  Before
> any of you spill your coffee ;-) there is a hefty constant involved that
...
> There happens to be a 'well known algorithm' for this.  The only drawback is
> a hit on the constant.  I figure it might not be too bad of a price to pay,
> though.

The main reason I was inclined to stick with Quicksort is that it is
on *average* the fastest sort available. If "average case" is truly
the average (a big "if", I'll grant you), then we'll be saving
everyone a lot of CPU time in the aggregate by using a fast Quicksort.
If we blow that, in my book we might as well use something else and
keep the code simple.

When I do finally manage to find a suitable forum to publish the
implmentation I have, we should certianly encourage folks to play with
the algorithm, modify it, analayze the results, and report their
findings for discussion. But again, I don't think we should waste a
huge amount of effort on it, because this isn't the sort that will
really matter. That one will be in the "Maps" package, and will
probably have to be some kind of tree-based sort.

-- 
T.E.D.
Home     -  mailto:dennison@telepath.com (Yahoo: Ted_Dennison)
Homepage -  http://www.telepath.com/dennison/Ted/TED.html

Re: Ada Components - GRACE Lists (Sorting them)

[Darren New]

Ted Dennison wrote:
> The main reason I was inclined to stick with Quicksort is that it is
> on *average* the fastest sort available. If "average case" is truly
> the average (a big "if", I'll grant you),

The only problem with quicksort's worst-case behavior is that it occurs
when the list is already mostly sorted. The distribution of worst-case
cases isn't random, and it's easy to code in a way that hits the worst
case on a regular basis.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
  To the user, everything works just as expected,
    assuming the user's expectations are correct.

Re: Ada Components - GRACE Lists (Sorting them)

[Ted Dennison]

Darren New <dnew@san.rr.com> wrote in message news:<3C7BC3CD.3B7A46DC@san.rr.com>...
> Ted Dennison wrote:
> > The main reason I was inclined to stick with Quicksort is that it is
> > on *average* the fastest sort available. If "average case" is truly
> > the average (a big "if", I'll grant you),
> 
> The only problem with quicksort's worst-case behavior is that it occurs
> when the list is already mostly sorted. The distribution of worst-case
> cases isn't random, and it's easy to code in a way that hits the worst
> case on a regular basis.

Right. But if you are aware of this issue, its also fairly easy to
code in a way that it *doesn't* hit the worst case.

Also (and this is the part I don't think a lot of folks realise), the
constants on quicksort vs. other sorts are such that "n" often has to
be damn large before Quicksort's n**2 is worse than other algorithms'
nlogn. I'd argue that anyone sorting that large an amount of stuff
should be using the Maps package anyway.

-- 
T.E.D.
Home     -  mailto:dennison@telepath.com (Yahoo: Ted_Dennison)
Homepage -  http://www.telepath.com/dennison/Ted/TED.html

Re: Ada Components - GRACE Lists (Sorting them)

[Matthew Heaney]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:4519e058.0202260859.4ecde69f@posting.google.com...
> When I do finally manage to find a suitable forum to publish the
> implmentation I have, we should certianly encourage folks to play with
> the algorithm, modify it, analayze the results, and report their
> findings for discussion. But again, I don't think we should waste a
> huge amount of effort on it, because this isn't the sort that will
> really matter. That one will be in the "Maps" package, and will
> probably have to be some kind of tree-based sort.

In the Charles data structure and algorithm library, I included a quicksort
to sort arrays (using the median-of-3 technique), and another to do a stable
sort of a list.  I haven't tried to do any other optimizations or anything.

http://home.earthlink.net/~matthewjheaney/charles/charles-generic_quicksort_
_ads.htm

http://home.earthlink.net/~matthewjheaney/charles/charles-unbounded_lists-ge
neric_quicksort__ads.htm

http://home.earthlink.net/~matthewjheaney/charles/

http://home.earthlink.net/~matthewjheaney/charles-20020228.zip

http://home.earthlink.net/~matthewjheaney/

Note that in Charles, the map and set types are implemented using a
red-black tree, so they're already sorted.

gnat-3.14p, libaddr2line and IRIX 6.5

[Dirk Baerts]

After gnat.com released 3.14p, at Jan 31 2002, I'm now finally have the time
to build it starting from 3.12p, under IRIX 6.5.
To my surprise the Makefile asks for libaddr2line, that was nowhere in sight.
And it really seems to be necessary : convert_addresses : unresolved.symbol
Found the gnu binutils addr2line, but no libaddr2line on the web. Just
discussions, on what to do about this.

Q's :
What is my best option ?
make a stub ? apply one of the patches ( and if yes, which one ) ? remove any
target from the makefile that includes libaddr2line ? Is libaddr2line
available in the foreseeable future ? is rebuilding addr2line as library a
solution ? and so on, and so

BTW :
What is the point of distributing free software if its dependencies are not
freely available ?

Cheers,
Dirk

Re: gnat-3.14p, libaddr2line and IRIX 6.5

[David C. Hoos]

----- Original Message -----
From: "Dirk Baerts" <d.baerts@xs4all.nl>
Newsgroups: comp.lang.ada
To: <comp.lang.ada@ada.eu.org>
Sent: Tuesday, March 05, 2002 1:55 PM
Subject: gnat-3.14p, libaddr2line and IRIX 6.5


> After gnat.com released 3.14p, at Jan 31 2002, I'm now finally have the
time
> to build it starting from 3.12p, under IRIX 6.5.
> To my surprise the Makefile asks for libaddr2line, that was nowhere in
sight.
> And it really seems to be necessary : convert_addresses :
unresolved.symbol
> Found the gnu binutils addr2line, but no libaddr2line on the web. Just
> discussions, on what to do about this.
>
FWIW, the Linux version of gnat-3.14p contains a static library
libaddr2line.a
which is compiled from the following files:
addr2line.c, bucomm.c, version.c, and filemode.c

I imagine this library is used to support symbolic tracebacks, and that it
would be
simple to create such a library on any platform for which the source code
for
addr2line is available.

> Q's :
> What is my best option ?
> make a stub ? apply one of the patches ( and if yes, which one ) ? remove
any
> target from the makefile that includes libaddr2line ? Is libaddr2line
> available in the foreseeable future ? is rebuilding addr2line as library a
> solution ? and so on, and so
>
> BTW :
> What is the point of distributing free software if its dependencies are
not
> freely available ?
>
As we all should know by now, there's no such thing as a non-trivial program
without some bug, and one like this can easily happen unless an attempt was
made to build a distribution for each platform on a "clean" machine -- i.e.,
on which has no non-standard libraries, etc., something that is not always
possible to do with finite resources.

And, as I imaagined above, I think we'll find that the dependencies _are_
freely available.  It sometimes just takes a little digging.

> Cheers,
> Dirk
>
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada.eu.org
> http://ada.eu.org/mailman/listinfo/comp.lang.ada
>

Re: gnat-3.14p, libaddr2line and IRIX 6.5

[Stephen Leake]

"David C. Hoos" <david.c.hoos.sr@ada95.com> writes:

> ----- Original Message -----
> From: "Dirk Baerts" <d.baerts@xs4all.nl>
> Newsgroups: comp.lang.ada
> To: <comp.lang.ada@ada.eu.org>
> Sent: Tuesday, March 05, 2002 1:55 PM
> Subject: gnat-3.14p, libaddr2line and IRIX 6.5
> 
> 
> > After gnat.com released 3.14p, at Jan 31 2002, I'm now finally have the
> time
> > to build it starting from 3.12p, under IRIX 6.5.
> > To my surprise the Makefile asks for libaddr2line, that was nowhere in
> sight.
> > And it really seems to be necessary : convert_addresses :
> unresolved.symbol
> > Found the gnu binutils addr2line, but no libaddr2line on the web. Just
> > discussions, on what to do about this.

Just comment out the build of 'convert_addresses' in the makefile;
you'll probably never miss it.


-- 
-- Stephe

Re: gnat-3.14p, libaddr2line and IRIX 6.5 : solved !

[Dirk Baerts]

Thanks for your push in the right direction. Managed to build libaddr2line and
gnat-3.14p.
The latter does compile serious sources, but appears to have the same bug (?) as
I encountered in 3.13p : does not accept MCL_CURRENT as an argument for the
c-sytemcall mlockall, that is called via an if.ads file. 3.12p had no trouble
with that.
I might get back on this point.

Thanks again,
Dirk

"David C. Hoos" wrote:

> ----- Original Message -----
> From: "Dirk Baerts" <d.baerts@xs4all.nl>
> Newsgroups: comp.lang.ada
> To: <comp.lang.ada@ada.eu.org>
> Sent: Tuesday, March 05, 2002 1:55 PM
> Subject: gnat-3.14p, libaddr2line and IRIX 6.5
>
> > After gnat.com released 3.14p, at Jan 31 2002, I'm now finally have the
> time
> > to build it starting from 3.12p, under IRIX 6.5.
> > To my surprise the Makefile asks for libaddr2line, that was nowhere in
> sight.
> > And it really seems to be necessary : convert_addresses :
> unresolved.symbol
> > Found the gnu binutils addr2line, but no libaddr2line on the web. Just
> > discussions, on what to do about this.
> >
> FWIW, the Linux version of gnat-3.14p contains a static library
> libaddr2line.a
> which is compiled from the following files:
> addr2line.c, bucomm.c, version.c, and filemode.c
>
> I imagine this library is used to support symbolic tracebacks, and that it
> would be
> simple to create such a library on any platform for which the source code
> for
> addr2line is available.
>
> > Q's :
> > What is my best option ?
> > make a stub ? apply one of the patches ( and if yes, which one ) ? remove
> any
> > target from the makefile that includes libaddr2line ? Is libaddr2line
> > available in the foreseeable future ? is rebuilding addr2line as library a
> > solution ? and so on, and so
> >
> > BTW :
> > What is the point of distributing free software if its dependencies are
> not
> > freely available ?
> >
> As we all should know by now, there's no such thing as a non-trivial program
> without some bug, and one like this can easily happen unless an attempt was
> made to build a distribution for each platform on a "clean" machine -- i.e.,
> on which has no non-standard libraries, etc., something that is not always
> possible to do with finite resources.
>
> And, as I imaagined above, I think we'll find that the dependencies _are_
> freely available.  It sometimes just takes a little digging.
>
> > Cheers,
> > Dirk
> >
> > _______________________________________________
> > comp.lang.ada mailing list
> > comp.lang.ada@ada.eu.org
> > http://ada.eu.org/mailman/listinfo/comp.lang.ada
> >

Re: gnat-3.14p, libaddr2line and IRIX 6.5

[Dirk Baerts]

Deep down, namely in binutils/addr2line.c, lies the solution. It�s there,
undocumented & hardly traceable
Credits to David C. Hoos.

Cheers,
Dirk

Stephen Leake wrote:

> "David C. Hoos" <david.c.hoos.sr@ada95.com> writes:
>
> > ----- Original Message -----
> > From: "Dirk Baerts" <d.baerts@xs4all.nl>
> > Newsgroups: comp.lang.ada
> > To: <comp.lang.ada@ada.eu.org>
> > Sent: Tuesday, March 05, 2002 1:55 PM
> > Subject: gnat-3.14p, libaddr2line and IRIX 6.5
> >
> >
> > > After gnat.com released 3.14p, at Jan 31 2002, I'm now finally have the
> > time
> > > to build it starting from 3.12p, under IRIX 6.5.
> > > To my surprise the Makefile asks for libaddr2line, that was nowhere in
> > sight.
> > > And it really seems to be necessary : convert_addresses :
> > unresolved.symbol
> > > Found the gnu binutils addr2line, but no libaddr2line on the web. Just
> > > discussions, on what to do about this.
>
> Just comment out the build of 'convert_addresses' in the makefile;
> you'll probably never miss it.
>
> --
> -- Stephe