Range extraction: Difference between revisions

Content added Content deleted

Inline

Revision as of 08:57, 16 July 2010

A format for expressing an ordered list of integers is to use a comma separated list of either

individual integers
Or a range of integers denoted by the starting integer separated from the end integer in the range by a dash, '-'. (The range includes all integers in the interval including both endpoints)

So the list of integers: 1, 2, 3, 6, 7, 9 could be written as: 1-3,6-7,9 or as 1-3,6,7,9 or as ...

We add a further rule:

The range syntax is to be used only for, and for every range that expands to more than two values.

This means that the above example could only become: 1-3,6,7,9

The task is to create a function that takes a list of integers and returns a correctly formatted string in the range format. Use the function to compute and print the range formatted version of the following ordered list of integers:

    0,  1,  2,  4,  6,  7,  8, 11, 12, 14,
   15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
   25, 27, 28, 29, 30, 31, 32, 33, 35, 36,
   37, 38, 39

C.f. Range expansion

ALGOL 68

Note: The following Iterative code specimen is the "unrolled" version of the Generative code specimen below. Together they provided as a comparison of the two different methods.

Iterative

Works with: ALGOL 68 version Revision 1 - no extensions to language used

Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

The closest concept that Algol 68 has to duck typing is the tagged union. This is used to define mode rangeint = union(int, struct(int lwb, upb)). If duck typing was available it could reduced the size of the code specimen, but would have lost some of Algol 68s strong type data security.

<lang algol68>MODE INTLIST = FLEX[0]INT; MODE YIELDINT = PROC(INT)VOID;

Declarations for manipulating lists of range pairs [lwb:upb] #

MODE RANGE = STRUCT(INT lwb, upb); MODE RANGELIST = FLEX[0]RANGE; MODE YIELDRANGE = PROC(RANGE)VOID;

PROC range repr = (RANGE range)STRING:

 whole(lwb OF range,0)+
   IF lwb OF range = upb OF range THEN "" ELSE ":"+whole(upb OF range,0) FI;

OP REPR = (RANGE range)STRING: range repr(range); firmly related to RANGEINT #

Declarations for manipulating lists containing pairs AND lone INTs #

MODE RANGEINT = UNION(INT, RANGE); MODE RANGEINTLIST = FLEX[0]RANGEINT; MODE YIELDRANGEINT = PROC(RANGEINT)VOID;

PROC range int repr = (RANGEINT range int)STRING:

 CASE range int IN
   (RANGE range): range repr(range),
   (INT int): whole(int,0)
 ESAC;

OP REPR = (RANGEINT range int)STRING: range int repr(range int);

The closest thing ALGOL 68 has to inheritance is the union #

MODE RANGEINTLISTINIT = UNION(RANGEINTLIST, RANGELIST, INTLIST);

PROC range int list repr = (RANGEINTLIST range int list)STRING: (

 STRING out := "(", sep := "";
 FOR key FROM LWB range int list TO UPB range int list DO
   out +:= sep + REPR range int list[key];
   sep := ", "
 OD;
 out+")"

);

OP REPR = (RANGEINTLIST range int list)STRING: range int list repr(range int list);

Note: Algol 68RS cannot handle LWB and UPB of a UNION in the following: #

PROC gen range = (RANGEINTLISTINIT range int list, YIELDRANGE yield range)VOID:

 FOR key FROM LWB range int list TO UPB range int list DO
   RANGEINT value = CASE range int list IN 
                      (INTLIST list):list[key],
                      (RANGELIST list):list[key],
                      (RANGEINTLIST list):list[key]
                    ESAC;
   yield range(
     CASE value IN
       (RANGE range): range,
       (INT value): (value, value)
     ESAC
   )
 OD;

PROC gen range merge = (RANGEINTLISTINIT range int list, YIELDRANGE yield range)VOID: (

 UNION(VOID, RANGE) prev range := EMPTY;

FOR RANGE next range IN # gen range(range int list, # ) DO #
1. (RANGE next range)VOID:
if the ranges cannot be merge, then yield 1st, and return 2nd #

   prev range := 
     CASE prev range IN
       (VOID): next range,
       (RANGE prev range): 
         IF upb OF prev range + 1 = lwb OF next range THEN
           RANGE(lwb OF prev range, upb OF next range) # merge the range #
         ELSE
           IF lwb OF prev range <= upb OF prev range THEN
             yield range(prev range)
           FI;
           next range
         FI
       OUT SKIP
     ESAC

OD # );

 CASE prev range IN (RANGE last range): yield range(last range) ESAC

);

PROC gen range int merge = (RANGEINTLISTINIT range int list, YIELDRANGEINT yield range int)VOID: (

FOR RANGE range IN # gen range merge(range int list, # ) DO #
1. (RANGE range)VOID:

   yield range int(
     IF lwb OF range = upb OF range THEN lwb OF range ELSE range FI
   )

OD # )

);

PROC range int list init = (RANGEINTLISTINIT range int list)RANGEINTLIST: (

 [LWB range int list: UPB range int list]RANGEINT out range int list;
 INT upb out range int list := LWB out range int list - 1;

FOR RANGEINT range int IN # gen range int merge(range int list, # ) DO #
1. (RANGEINT range int)VOID:

   out range int list[upb out range int list+:=1] := range int

OD # );

 out range int list[:upb out range int list]

);

do some simple test cases: #

test: BEGIN

 []INT int list = (
   0,  1,  2,  4,  6,  7,  8, 11, 12, 14,
   15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
   25, 27, 28, 29, 30, 31, 32, 33, 35, 36,
   37, 38, 39);
 
 []RANGE range list = ( # unnormalised #
   (0,0),  (1,1),  (2,2),  (4,4),  (6,6),  (7,7),  (8,8), (11,11), (12,12), (14,14),
   (15,15), (16,16), (17,17), (18,18), (19,19), (20,20), (21,21), (22,22), (23,23), (24,24),
   (25,25), (27,27), (28,28), (29,29), (30,30), (31,31), (32,32), (33,33), (35,35), (36,36),
   (37,37), (38,38), (39,39));
 
 []RANGEINT list a = (RANGE(0,2), 4, RANGE(6,8), RANGE(11,12), RANGE(14,25), RANGE(27,33), RANGE(35,39));

 []RANGEINT list b = ( # unnormalised #
   0,  1,  2,  4,  6,  7,  8, 11, 12, 14,
   15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
   25, 27, 28, 29, 30, 31, 32, 33, 35, 36,
   37, 38, 39);

 FLEX[0]RANGEINT list c := range int list init(list b); # normalised #

compare manipulation of various types of argument lists #

 print((REPR range int list init(int list), new line));
 print((REPR range int list init(range list), new line));
 print((REPR list a, new line));
 print((REPR(range int list init(list b)), new line));
 print((REPR list c, new line))

END</lang> Output:

(0:2, 4, 6:8, 11:12, 14:25, 27:33, 35:39)
(0:2, 4, 6:8, 11:12, 14:25, 27:33, 35:39)
(0:2, 4, 6:8, 11:12, 14:25, 27:33, 35:39)
(0:2, 4, 6:8, 11:12, 14:25, 27:33, 35:39)
(0:2, 4, 6:8, 11:12, 14:25, 27:33, 35:39)

Generative