* Constraint Error - Please Help
@ 1998-12-02 0:00 Fanni Kolchina
1998-12-02 0:00 ` Tom Moran
` (3 more replies)
0 siblings, 4 replies; 6+ messages in thread
From: Fanni Kolchina @ 1998-12-02 0:00 UTC (permalink / raw)
Hi, All:
I am writing a generic sorting program in Ada using heap sort. I am
new to Ada, and have no experience with this. When I run my program, I
get a Constraint Error: range error. I have spent lots of time
thinking what is wrong, but I just cannot comprehend it.
If someone could help me, I will greatly appreciate it. Below is my
code, and the line where the exception is thrown is marked by comment
lines above and below it. Thanks a lot!
with ada.text_io; use ada.text_io;
with ada.integer_text_io; use ada.integer_text_io;
with ada.float_text_io; use ada.float_text_io;
procedure test_sort is
generic
type ITEM is private;
type SORT_ARRAY is array(Positive range <>) of ITEM;
with function "<" (u,v: ITEM) return boolean is <>;
function sort_generic (x: SORT_ARRAY) return SORT_ARRAY;
subtype index is positive range 1..10;
type floatArray is array (positive range <>) of float;
fa, hfa, shfa: floatArray(index);
procedure printFloatArray (fa: floatArray) is
begin
for count in fa'first..fa'last loop
put(fa(count), fore=>3, aft=>1, exp =>0);
end loop;
new_line;
end;
function sort_generic (x: SORT_ARRAY) return SORT_ARRAY is
copy: SORT_ARRAY(x'range);
last, left, right, max_l_r, current, this, parent: integer;
end_node, contents : ITEM;
begin
for i in x'first..x'last loop
copy(i):=x(i);
end loop;
for i in x'first+1..x'last loop
this:=i;
parent:= (i-1)/2;
contents:=copy(this);
----------------------------------------------------------------
-- here's the line with the exception ---
while this /= x'first and then copy(parent)<contents loop
----------------------------------------------------------------
copy(this):= copy(parent);
this:= parent;
parent:=(parent-1)/2;
end loop;
copy(this):=contents;
end loop;
for last in reverse x'first+1..x'last loop
--swap first position with last
--end_node needs to be filtered down into heap
end_node:= copy(last);
copy(last):=copy(x'first);
--start at the root node
current:=x'first;
--traverse the heap
loop
--look left
left:=2*current+1;
--if no left node, you've found the right slot
exit when left>last-1;
-- if there is a left node then find whether left or
-- right node (if any) is max_l_r
right:=left+1;
if right>last-1 or copy(right)<copy(left) then
max_l_r:= left;
else
max_l_r:= right;
end if;
-- if end_node is bigger than
both left and right children, then it
-- must go here, so stop traversing
exit when copy(max_l_r) < end_node;
-- otherwise, move down
copy(current):=copy(max_l_r);
current:=max_l_r;
end loop;
-- after the loop, current points to the insertion spot
copy(current):= end_node;
end loop;
return copy;
end;
function sortFloat is new sort_generic (float, floatArray, "<");
begin
fa:=(7.2, 8.4, 3.5, 0.3, -5.4, 9.9, -0.5, 8.0, 1.1, 3.8);
new_line;
put("Testing sort for float vectors");
new_line;
put("Before: ");
new_line;
printFloatArray (fa);
shfa:=sortFloat(fa);
put("After: ");
new_line;
printFloatArray(fa);
new_line;
end;
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: Constraint Error - Please Help
1998-12-02 0:00 Constraint Error - Please Help Fanni Kolchina
@ 1998-12-02 0:00 ` Tom Moran
1998-12-02 0:00 ` Richard D Riehle
` (2 subsequent siblings)
3 siblings, 0 replies; 6+ messages in thread
From: Tom Moran @ 1998-12-02 0:00 UTC (permalink / raw)
> for i in x'first+1..x'last loop
> this:=i;
> parent:= (i-1)/2;
> contents:=copy(this);
>----------------------------------------------------------------
>-- here's the line with the exception ---
> while this /= x'first and then copy(parent)<contents loop
this is surely never equal to x'first since it starts at x'first+1 and
increments. The first time through the loop i=x'first+1 so
parent=x'first/2 and if x'first=1 then parent = 0 which is out of
copy'range.
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: Constraint Error - Please Help
1998-12-02 0:00 Constraint Error - Please Help Fanni Kolchina
1998-12-02 0:00 ` Tom Moran
@ 1998-12-02 0:00 ` Richard D Riehle
1998-12-03 0:00 ` Jean-Pierre Rosen
1998-12-03 0:00 ` Jeff Carter
3 siblings, 0 replies; 6+ messages in thread
From: Richard D Riehle @ 1998-12-02 0:00 UTC (permalink / raw)
In article <7445iv$gog$1@news.nyu.edu>,
kolc7797@PROBLEM_WITH_YOUR_MAIL_GATEWAY_FILE.nyu.edu (Fanni Kolchina)
wrote:
>Hi, All:
>
>I am writing a generic sorting program in Ada using heap sort. I am
>new to Ada, and have no experience with this. When I run my program, I
>get a Constraint Error: range error. I have spent lots of time
>thinking what is wrong, but I just cannot comprehend it.
>If someone could help me, I will greatly appreciate it. Below is my
>code, and the line where the exception is thrown is marked by comment
>lines above and below it. Thanks a lot!
You have an error in your algorithm. The first four iterations work
fine and the index will be incremented as 2, 3, 4, 5. Then, because
of the way you compute parent and later assign it to this, the whole
algorithm wobbles out of phase and the variable, this, returns to
the value 2. This is inconsistent with the rest of the behavior
expected of the while loop.
If you handle and raise exceptions for the while loop and put in a
line at the end of the for loop to print the successive values of
your variables you will see at once the problem associated with
your calculation on the variable parent and its subsequent assignment
to the variable this.
>
>with ada.text_io; use ada.text_io;
>with ada.integer_text_io; use ada.integer_text_io;
>with ada.float_text_io; use ada.float_text_io;
>
>procedure test_sort is
>
> generic
> type ITEM is private;
> type SORT_ARRAY is array(Positive range <>) of ITEM;
> with function "<" (u,v: ITEM) return boolean is <>;
>
> function sort_generic (x: SORT_ARRAY) return SORT_ARRAY;
>
> subtype index is positive range 1..10;
> type floatArray is array (positive range <>) of float;
> fa, hfa, shfa: floatArray(index);
>
> procedure printFloatArray (fa: floatArray) is
> begin
> for count in fa'first..fa'last loop
> put(fa(count), fore=>3, aft=>1, exp =>0);
> end loop;
> new_line;
> end;
>
> function sort_generic (x: SORT_ARRAY) return SORT_ARRAY is
> copy: SORT_ARRAY(x'range);
> last, left, right, max_l_r, current, this, parent: integer;
> end_node, contents : ITEM;
> begin
>
> for i in x'first..x'last loop
> copy(i):=x(i);
> end loop;
>
> for i in x'first+1..x'last loop
> this:=i;
> parent:= (i-1)/2;
> contents:=copy(this);
>----------------------------------------------------------------
>-- here's the line with the exception ---
> while this /= x'first and then copy(parent)<contents loop
>----------------------------------------------------------------
> copy(this):= copy(parent);
> this:= parent;
> parent:=(parent-1)/2;
> end loop;
> copy(this):=contents;
> end loop;
>
> for last in reverse x'first+1..x'last loop
> --swap first position with last
> --end_node needs to be filtered down into heap
> end_node:= copy(last);
> copy(last):=copy(x'first);
>
> --start at the root node
> current:=x'first;
> --traverse the heap
> loop
> --look left
> left:=2*current+1;
> --if no left node, you've found the right slot
> exit when left>last-1;
> -- if there is a left node then find whether left or
> -- right node (if any) is max_l_r
> right:=left+1;
> if right>last-1 or copy(right)<copy(left) then
> max_l_r:= left;
> else
> max_l_r:= right;
> end if;
> -- if end_node is bigger than
> both left and right children, then it
> -- must go here, so stop traversing
> exit when copy(max_l_r) < end_node;
> -- otherwise, move down
> copy(current):=copy(max_l_r);
> current:=max_l_r;
> end loop;
> -- after the loop, current points to the insertion spot
> copy(current):= end_node;
> end loop;
> return copy;
>end;
>
>function sortFloat is new sort_generic (float, floatArray, "<");
>
>begin
> fa:=(7.2, 8.4, 3.5, 0.3, -5.4, 9.9, -0.5, 8.0, 1.1, 3.8);
> new_line;
> put("Testing sort for float vectors");
> new_line;
> put("Before: ");
> new_line;
> printFloatArray (fa);
>
> shfa:=sortFloat(fa);
> put("After: ");
> new_line;
> printFloatArray(fa);
> new_line;
>end;
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: Constraint Error - Please Help
1998-12-02 0:00 Constraint Error - Please Help Fanni Kolchina
1998-12-02 0:00 ` Tom Moran
1998-12-02 0:00 ` Richard D Riehle
@ 1998-12-03 0:00 ` Jean-Pierre Rosen
1998-12-03 0:00 ` Jeff Carter
3 siblings, 0 replies; 6+ messages in thread
From: Jean-Pierre Rosen @ 1998-12-03 0:00 UTC (permalink / raw)
Not the initial question, but I can't resist:
Fanni Kolchina a �crit dans le message <7445iv$gog$1@news.nyu.edu>...
> [...]
> function sort_generic (x: SORT_ARRAY) return SORT_ARRAY is
> copy: SORT_ARRAY(x'range);
> last, left, right, max_l_r, current, this, parent: integer;
> end_node, contents : ITEM;
> begin
>
> for i in x'first..x'last loop
> copy(i):=x(i);
> end loop;
>
You should rather simply write:
function sort_generic (x: SORT_ARRAY) return SORT_ARRAY is
copy: SORT_ARRAY := x;
One of the nice things with Ada is that you can very often deal with
structrured variables globally, and that you are not forced to always
go to basic loop.
---------------------------------------------------------
J-P. Rosen (Rosen.Adalog@wanadoo.fr)
Visit Adalog's web site at http://perso.wanadoo.fr/adalog
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: Constraint Error - Please Help
1998-12-02 0:00 Constraint Error - Please Help Fanni Kolchina
` (2 preceding siblings ...)
1998-12-03 0:00 ` Jean-Pierre Rosen
@ 1998-12-03 0:00 ` Jeff Carter
1998-12-04 0:00 ` Michael F Brenner
3 siblings, 1 reply; 6+ messages in thread
From: Jeff Carter @ 1998-12-03 0:00 UTC (permalink / raw)
Fanni Kolchina wrote:
>
> Hi, All:
>
> I am writing a generic sorting program in Ada using heap sort. I am
> new to Ada, and have no experience with this. When I run my program, I
> get a Constraint Error: range error. I have spent lots of time
> thinking what is wrong, but I just cannot comprehend it.
> If someone could help me, I will greatly appreciate it. Below is my
> code, and the line where the exception is thrown is marked by comment
> lines above and below it. Thanks a lot!
>
> with ada.text_io; use ada.text_io;
> with ada.integer_text_io; use ada.integer_text_io;
> with ada.float_text_io; use ada.float_text_io;
>
> procedure test_sort is
>
> generic
> type ITEM is private;
> type SORT_ARRAY is array(Positive range <>) of ITEM;
> with function "<" (u,v: ITEM) return boolean is <>;
>
> function sort_generic (x: SORT_ARRAY) return SORT_ARRAY;
>
> subtype index is positive range 1..10;
> type floatArray is array (positive range <>) of float;
> fa, hfa, shfa: floatArray(index);
>
> procedure printFloatArray (fa: floatArray) is
> begin
> for count in fa'first..fa'last loop
This is a good place to use 'range:
for Count in Fa'range loop
> put(fa(count), fore=>3, aft=>1, exp =>0);
> end loop;
> new_line;
> end;
>
> function sort_generic (x: SORT_ARRAY) return SORT_ARRAY is
> copy: SORT_ARRAY(x'range);
This is a good place to initialize Copy:
Copy : Sort_Array := X;
> last, left, right, max_l_r, current, this, parent: integer;
> end_node, contents : ITEM;
> begin
>
> for i in x'first..x'last loop
> copy(i):=x(i);
> end loop;
If you initialized Copy in its declaration, as I suggested above, then
this loop may be deleted.
>
> for i in x'first+1..x'last loop
> this:=i;
> parent:= (i-1)/2;
> contents:=copy(this);
> ----------------------------------------------------------------
> -- here's the line with the exception ---
> while this /= x'first and then copy(parent)<contents loop
> ----------------------------------------------------------------
> ...
We see later in your code that this is called with X'First = 1. So the
first time through this loop, I = 2, which means Parent = (2 - 1) / 2 =
1 / 2 = 0 (integer division truncates towards zero). So the condition of
the while loop is
2 /= 1 and then Copy (0) < Contents
Obviously, 2 is never equal to 1, so the comparison of Copy (0) to
Contents is performed. Zero is not a valid index for Copy, and a
run-time check detects this constraint violation and raises
Constraint_Error.
--
Jeff Carter
E-mail: carter commercial-at innocon [period | full stop] com
"Perfidious English mouse-dropping hoarders."
Monty Python & the Holy Grail
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: Constraint Error - Please Help
1998-12-03 0:00 ` Jeff Carter
@ 1998-12-04 0:00 ` Michael F Brenner
0 siblings, 0 replies; 6+ messages in thread
From: Michael F Brenner @ 1998-12-04 0:00 UTC (permalink / raw)
As an additional note to the helpful posts which identified improvements
and errors in the code, most Ada compilers will help you identify
the reason for the overflow. Some even print out the offending values
on the dump, although some require you to run an external debugger,
retain certain symbol table files, compile using certain debugging
options, and/or link using certain debugging options. It may be helpful
to compile and link the code with all the debugging options turned on,
and retain all the extra debugging files, and do not STRIP away any
debugging information from the executable.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~1998-12-04 0:00 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1998-12-02 0:00 Constraint Error - Please Help Fanni Kolchina
1998-12-02 0:00 ` Tom Moran
1998-12-02 0:00 ` Richard D Riehle
1998-12-03 0:00 ` Jean-Pierre Rosen
1998-12-03 0:00 ` Jeff Carter
1998-12-04 0:00 ` Michael F Brenner
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox