Login | Register
My pages Projects Community openCollabNet

Discussions > users > Re: Lower_Bound Upper_Bound

charles
Discussion topic

Back to topic list

Re: Lower_Bound Upper_Bound

Reply

Author Matthew Heaney <mheaney at on2 dot com>
Full name Matthew Heaney <mheaney at on2 dot com>
Date 2004-05-18 08:12:51 PDT
Message christoph dot grein at eurocopter dot com wrote:

>>Lower_Limit (S, K) < K (AKA "Ground", "Previous_Floor")
>>Floor (S, K) <= K
>>Ceiling (S, K) >= K (AKA Lower_Bound)
>>Upper_Limit (S, K) > K (AKA Upper_Bound, "Roof", "Next_Ceiling")
>
>
>>There seems to be agreement that this functionality is useful. One of
>>the issues is that several of the ARG reviewers were confused by the
>>names "Lower_Bound" and "Upper_Bound".
>
>
> Matt,
>
> and so am I (confused by the names).

The names "Lower_Bound" and "Upper_Bound" come from the STL. I
preserved those names, because I didn't have anything better.


> I do not wnat to fill the Ada-Comment list more than necessary, so I'm replying
> to you personally.

You can use the lists at tigris, too

users at charles dot tigris dot org
dev at charles dot tigris dot org
... -- there are others


> The names above on the left side seem intuitive to me, whereas Lower/Upper_Bound
> confuse me because they are both on the same side of S.
>
> In maths, when I have a set of numbers, a lower bound is any value that is
> smaller than or equal to any value from the set, the infimum is the greatest
> lower bound, the minimum the smallest element of the set (if it exists, it's
> equal to the infimum).

That's what Tucker was alluding to, the fact that there are already
terms from set theory that use a similar name.


> Upper bound, supremum, maximum are on the other side of the side.
>
> Here, Lower_Bound is the maximum of all elements of S:
>
> Ceiling (S, K) >= K (AKA Lower_Bound)
> Upper_Limit (S, K) > K (AKA Upper_Bound, "Roof", "Next_Ceiling")
>
> Why? This is very confusing. Intuitively Lower_Limit and Lower_Bound should at
> least be related, not reside on opposite sides of S.

The problem we're trying to solve is if you have a closed range
(includes both endpoints). For example, to iterate over the range [K1, K2]:

declare
    I : Cursor := Lower_Bound (S,K1);
    J : constant Cursor := Upper_Bound (S,K2);
begin
    while I /= J loop ...;
end;

Here, if K2 is in the set, then Upper_Bound returns its successor,
guaranteeing that cursor I will designate the node containing K2 on the
last iteration thru the loop.

On the other hand, if you want to iterate over the half-open range [K1,
K2), then you only need Lower_Bound:

declare
    I : Cursor := Lower_Bound (S,K1);
    J : constant Cursor := Lower_Bound (S,K2);
begin
    while I /= J loop ...;
end;

If K2 is in the set, then J will designate the node containing K2, and
the iteration will terminate when it reaches that node.

If you have Lower_Bound, then you rewrite the first loop like this:

declare
    I : Cursor := Lower_Bound (S,K1);
    J : Cursor := Lower_Bound (S,K2);
begin
    if not (K2 < Key (J)) then -- equals
       Next (J);
    end if;

    while I /= J loop ...;
end;

but that is slightly less efficient.

-Matt


--------------------​--------------------​--------------------​---------
To unsubscribe, e-mail: users-unsubscribe@ch​arles.tigris.org
For additional commands, e-mail: users-help at charles dot tigris dot org

« Previous message in topic | 1 of 1 | Next message in topic »

Messages

Show all messages in topic

Re: Lower_Bound Upper_Bound Matthew Heaney <mheaney at on2 dot com> Matthew Heaney <mheaney at on2 dot com> 2004-05-18 08:12:51 PDT
Messages per page: