[M3devel] subrange value not constant?

[Martin Bishop]

Hmm, good point about count.  Originally I did initialize to 0, but in 
the process of trying to get it to work, I must have removed it.

As for min and max, yes the point of the Counting Sort 
(http://en.wikipedia.org/wiki/Counting_sort) is that min and max are known.

Thanks for the help :)

Mika Nystrom wrote:
> Martin, you have one bug: you don't initialize count.  Per 2.6.9 in the
> Green Book, NEW returns "an arbitrary value of its type"
>
> Also, for slightly more clarity, count can be a REF ARRAY OF CARDINAL.
>
> INC and DEC would make the code a bit easier to read, perhaps.
>
> Finally, you can dispense with min and max completely by just using
> min, initialized to a[0], and re-allocating the array whenever the
> new value is greater than min + NUMBER(count^) :-)  But maybe you
> already know what min and max are by some means that doesn't involve
> scanning the array.
>
>     Mika
>
>
>
>
> Martin Bishop writes:
>   
>> By the way, in case anyone cares, here's the proper code:
>>
>> PROCEDURE Sort(VAR a: ARRAY OF INTEGER; min, max: INTEGER) =
>>  VAR range := max - min + 1;
>>      count := NEW(REF ARRAY OF INTEGER, range);
>>      z := 0;
>>  BEGIN
>>    FOR i := FIRST(a) TO LAST(a) DO
>>      count[a[i] - min] := count[a[i] - min] + 1;
>>    END;
>>    FOR i := min TO max DO
>>      WHILE (count[i - min] > 0) DO
>>        a[z] := i;
>>        INC(z);
>>        count[i - min] := count[i - min] - 1;
>>      END;
>>    END;
>>  END Sort;
>>
>> Martin Bishop wrote:
>>     
>>> I've written this procedure (an implementation of counting sort):
>>>
>>> PROCEDURE Sort(VAR a: ARRAY OF INTEGER; min, max: INTEGER) =
>>>  VAR count := ARRAY [min..max] OF INTEGER {0, ..};
>>>      z := 0;
>>>  BEGIN
>>>    FOR i := FIRST(a) TO LAST(a) DO
>>>      count[i - min] := count[i - min] + 1;
>>>    END;
>>>    FOR i := min TO max DO
>>>      WHILE count[i - min] > 0 DO
>>>        a[z] := i;
>>>        INC(z);
>>>        count[i - min] := count[i - min] - 1;
>>>      END;
>>>    END;
>>>  END Sort;
>>>
>>> However, when I try to compile I get:
>>>
>>> "../Counting.m3", line 8: subrange lower bound is not constant
>>> "../Counting.m3", line 8: subrange upper bound is not constant
>>>
>>> Line 8 is:
>>>
>>> VAR count := ARRAY [min..max] OF INTEGER {0, ..};
>>>
>>> I don't see what's wrong?
>>>
>>>
>>>       
>
>