You are given a list of n ascending, unique numbers which are to form limits
for n+1 bins which count how many of a large set of input numbers fall in the
range of each bin.

(Assuming zero-based indexing)

   bin[0] counts how many inputs are < limit[0]
   bin[1] counts how many inputs are >= limit[0] and < limit[1]
   ..
   bin[n-1] counts how many inputs are >= limit[n-2] and < limit[n-1]
   bin[n] counts how many inputs are >= limit[n-1]

Task

The task is to create a function that given the ascending limits and a stream/
list of numbers, will return the bins; together with another function that
given the same list of limits and the binning will print the limit of each bin
together with the count of items that fell in the range.

Assume the numbers to bin are too large to practically sort.

Task examples

Part 1: Bin using the following limits the given input data

   limits  = [23, 37, 43, 53, 67, 83]
   data = [95,21,94,12,99,4,70,75,83,93,52,80,57,5,53,86,65,17,92,83,71,61,54,58,47,
           16, 8, 9,32,84,7,87,46,19,30,37,96,6,98,40,79,97,45,64,60,29,49,36,43,55]

Part 2: Bin using the following limits the given input data

   limits = [14, 18, 249, 312, 389, 392, 513, 591, 634, 720]
   data = [445,814,519,697,700,130,255,889,481,122,932, 77,323,525,570,219,367,523,442,933,
           416,589,930,373,202,253,775, 47,731,685,293,126,133,450,545,100,741,583,763,306,
           655,267,248,477,549,238, 62,678, 98,534,622,907,406,714,184,391,913, 42,560,247,
           346,860, 56,138,546, 38,985,948, 58,213,799,319,390,634,458,945,733,507,916,123,
           345,110,720,917,313,845,426,  9,457,628,410,723,354,895,881,953,677,137,397, 97,
           854,740, 83,216,421, 94,517,479,292,963,376,981,480, 39,257,272,157,  5,316,395,
           787,942,456,242,759,898,576, 67,298,425,894,435,831,241,989,614,987,770,384,692,
           698,765,331,487,251,600,879,342,982,527,736,795,585, 40, 54,901,408,359,577,237,
           605,847,353,968,832,205,838,427,876,959,686,646,835,127,621,892,443,198,988,791,
           466, 23,707,467, 33,670,921,180,991,396,160,436,717,918,  8,374,101,684,727,749]

Show output here, on this page.

% Bin the given data, return an array of counts.
% CLU allows arrays to start at any index; the result array
% will have the same lower bound as the limit array.
 
% The datatype for the limits and data may be any type
% that allows the < comparator.
bin_count = proc [T: type] (limits, data: array[T]) returns (array[int])
            where T has lt: proctype (T,T) returns (bool)
    ad = array[T]       % abbreviations for array types
    ai = array[int] 
 
    lowbin: int := ad$low(limits)
    bins: ai := ai$fill(lowbin, ad$size(limits)+1, 0)
 
    for item: T in ad$elements(data) do
        bin: int := lowbin
        while bin <= ad$high(limits) do
            if item < limits[bin] then break end
            bin := bin + 1
        end
        bins[bin] := bins[bin] + 1
    end
 
    return(bins)
end bin_count
 
% Display the bins and the amount of items in each bin.
% This imposes the further restriction on the datatype
% that it allows `unparse' (may be turned into a string).
display_bins = proc [T: type] (limits, data: array[T])
               where T has unparse: proctype (T) returns (string),
                     T has lt: proctype (T,T) returns (bool)
    ad = array[T]
    ai = array[int]
 
    po: stream := stream$primary_output()
    bins: ai := bin_count[T](limits, data)
 
    for i: int in int$from_to(ad$low(limits), ad$high(limits)+1) do
        lo, hi: string
        if i-1 < ad$low(limits) 
            then lo := "-inf"
            else lo := T$unparse(limits[i-1])
        end 
        if i > ad$high(limits)
            then hi := "inf"
            else hi := T$unparse(limits[i])
        end
 
        stream$putright(po, lo, 5)
        stream$puts(po, " - ")
        stream$putright(po, hi, 5)
        stream$puts(po, " : ")
        stream$putright(po, int$unparse(bins[i]), 5)
        stream$putl(po, "")
    end
 
    stream$putl(po, "------------------------------------------\n")
end display_bins
 
% Try both example inputs
start_up = proc () 
    ai = array[int]
 
    limits1: ai := ai$[23, 37, 43, 53, 67, 83]
    data1: ai := ai$
     [95,21,94,12,99,4,70,75,83,93,52,80,57,5,53,86,65,17,92,83,71,61,54,58,47,
      16, 8, 9,32,84,7,87,46,19,30,37,96,6,98,40,79,97,45,64,60,29,49,36,43,55]
 
    limits2: ai := ai$[14, 18, 249, 312, 389, 392, 513, 591, 634, 720]
    data2: ai := ai$
     [445,814,519,697,700,130,255,889,481,122,932, 77,323,525,570,219,367,523,442,933,
      416,589,930,373,202,253,775, 47,731,685,293,126,133,450,545,100,741,583,763,306,
      655,267,248,477,549,238, 62,678, 98,534,622,907,406,714,184,391,913, 42,560,247,
      346,860, 56,138,546, 38,985,948, 58,213,799,319,390,634,458,945,733,507,916,123,
      345,110,720,917,313,845,426,  9,457,628,410,723,354,895,881,953,677,137,397, 97,
      854,740, 83,216,421, 94,517,479,292,963,376,981,480, 39,257,272,157,  5,316,395,
      787,942,456,242,759,898,576, 67,298,425,894,435,831,241,989,614,987,770,384,692,
      698,765,331,487,251,600,879,342,982,527,736,795,585, 40, 54,901,408,359,577,237,
      605,847,353,968,832,205,838,427,876,959,686,646,835,127,621,892,443,198,988,791,
      466, 23,707,467, 33,670,921,180,991,396,160,436,717,918,  8,374,101,684,727,749]   
 
    display_bins[int](limits1, data1)
    display_bins[int](limits2, data2)
end start_up