Constraint Error - Please Help

Constraint Error - Please Help

[Fanni Kolchina]

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;	 

Re: Constraint Error - Please Help

[Tom Moran]

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

Re: Constraint Error - Please Help

[Richard D Riehle]

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;	 

 

Re: Constraint Error - Please Help

[Jean-Pierre Rosen]

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

Re: Constraint Error - Please Help

[Jeff Carter]

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

Re: Constraint Error - Please Help

[Michael F Brenner]

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.