Range extraction: Difference between revisions

From Rosetta Code
Content added Content deleted
(Ada solution added)
Line 789: Line 789:


-> "0-2,4,6-8,11,12,14-25,27-33,35-39"</pre>
-> "0-2,4,6-8,11,12,14-25,27-33,35-39"</pre>

=={{header|PL/I}}==
<lang PL/I>
range_extraction:
procedure options (main);
declare c character (1);
declare (old, new, initial) fixed binary (31);
declare out file output;
open file (out) output title ('/out,type(text),recsize(70)');

c = ' ';
get list (old);
do forever;
initial = old;
on endfile (sysin) begin;
put file (out) edit (c, trim(old)) (a);
stop;
end;
get (new);
put edit (c) (a);
if new = old+1 then
do; /* we have a run. */
on endfile (sysin) begin;
put file (out) edit (c, trim(initial), '-', trim(old) ) (a);
stop;
end;
do while (new = old+1);
old = new;
get (new);
end;
/* At this point, old holds the last in a run; */
/* initial holds the first in a run. */
put file (out) edit (c, trim(initial), '-', trim(old) ) (a);
old = new;
end;
else /* we have an isolated value. */
do;
put file (out) edit (c, trim(old)) (a);
old = new;
end;
c = ',';
end;
end range_extraction;
</lang>
OUTPUT:
<lang>
0-2,4,6-8,11-12,14-25,27-33,35-39
</lang>
</lang>

=={{header|PureBasic}}==
=={{header|PureBasic}}==
Even though the example integer list only includes ascending ranges this code will also handles descending ranges.
Even though the example integer list only includes ascending ranges this code will also handles descending ranges.

Revision as of 15:33, 17 August 2010

Task
Range extraction
You are encouraged to solve this task according to the task description, using any language you may know.

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)
  • The range syntax is to be used only for, and for every range that expands to more than two values.

Example
The list of integers:

-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20

Is accurately expressed by the range expression:

-6,-3-1,3-5,7-11,14,15,17-20

(And vice-versa).

The task

  • Create a function that takes a list of integers in increasing order 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
  • Show the output of your program.

C.f. Range expansion

Ada

The provided implementation returns an empty string when the argument array is empty. Ranges with negative bounds are represented as -9--4, as the task requires. For real-life applications it is better to use the notation -9..-4: <lang Ada> with Ada.Text_IO; use Ada.Text_IO; with Ada.Strings.Unbounded; use Ada.Strings.Unbounded; with Ada.Strings.Fixed; use Ada.Strings.Fixed;

procedure Range_Extraction_Test is 

  type Sequence is array (Positive range <>) of Integer;
  function Image (S : Sequence) return String is
     Result : Unbounded_String;
     From   : Integer;
     procedure Flush (To : Integer) is
     begin
        if Length (Result) > 0 then
           Append (Result, ',');
        end if;
        Append (Result, Trim (Integer'Image (From), Ada.Strings.Left));
        if From < To then
           Append (Result, '-');
           Append (Result, Trim (Integer'Image (To), Ada.Strings.Left));
        end if;
     end Flush;
  begin      
     if S'Length > 0 then
        From := S (S'First);
        for I in S'First + 1..S'Last loop
           if S (I - 1) + 1 /= S (I) then
              Flush (S (I - 1));
              From := S (I);
           end if;
        end loop;
        Flush (S (S'Last));
     end if;
     return To_String (Result);
  end Image;

begin 

  Put_Line
  (  Image
     (  (  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
  )  )  );

end Range_Extraction_Test; </lang> Sample output: 

0-2,4,6-8,11-12,14-25,27-33,35-39

ALGOL 68

This example is incorrect. Please fix the code and remove this message.

Details: Range format is with a dash and no spaces, plus ranges must cover >2 integers, thanks.

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 68's strong type data security.

<lang algol68>MODE INTLIST = FLEX[0]INT;

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

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

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;
  1. OP REPR = (RANGE range)STRING: range repr(range); firmly related to RANGEINT #
  2. Declarations for manipulating lists containing pairs AND lone INTs #

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

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);

  1. 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);

  2. Task portion #

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;
 UNION(VOID, RANGE) prev range := EMPTY;

 PROC out range int list append = (RANGE value)VOID:
   out range int list[upb out range int list+:=1] :=
     IF lwb OF value = upb OF value THEN lwb OF value ELSE value FI;
  1. Note: Algol 68RS cannot handle LWB and UPB of a UNION in the following: #
 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;

   RANGE next range := CASE value IN
       (RANGE range): range,
       (INT value): RANGE(value, value)
     ESAC;

   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
             out range int list append(prev range)
           FI;
           next range
         FI
       OUT SKIP
     ESAC

 OD;

 CASE prev range IN 
   (RANGE last range): out range int list append(last range)
 ESAC;

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

);

  2. 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 #
  1. 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

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 following code a set of helper functions/generators that can be used to manipulate a lists of ranges. They can manipulate either arrays or iterator. And they can handle data of type int or range and both these types unioned.

These chained iterators do the following steps:

  1. Iterate through three different types of initial arrays - []int, []range and []rangeint with gen range, yielding range(lwb,upb)
  2. Iterate with gen range merge yielding merged range(lwb,upb)
  3. Iterate with gen range int merge, merging and yielding a union of int and range
  4. Finally iterate with range int list init exiting with an array of union of int and range.

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

  2. 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;
  1. OP REPR = (RANGE range)STRING: range repr(range); firmly related to RANGEINT #
  2. 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);

  1. 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);

  1. 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;
  1. FOR RANGE next range IN # gen range(range int list, # ) DO #
    1. (RANGE next range)VOID:
  2. 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
  1. 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: (

  1. 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
   )
  1. 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;
  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
  1. OD # );
 out range int list[:upb out range int list]

);

  2. 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 #
  1. 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)

C

Library: GLib

<lang c>#include <stdio.h>

  1. include <stdlib.h>
  2. include <string.h>
  3. include <stdbool.h>
  1. include <glib.h>
  1. ifndef ABS
  2. define ABS(X) (((X) > 0) ? (X) : -(X))
  3. endif

char *range_string_from_array(size_t n, const int *a) { 

 size_t i, p;
 char *r;
 const char *t;
 GString *s;
 bool inr;

 const char *ranget = "-%d,%d";
 const char *nranget = ",%d,%d";

 if ( n < 1 ) return NULL;

 s = g_string_new(NULL);
 if ( s == NULL ) return NULL;
 

 g_string_append_printf(s, "%d", a[0]);
 for(i = 1, inr = false, p=0; i < n; i++)
 {
   if ( ABS(a[i] - a[i-1]) == 1 ) { inr = true; p++; continue; }
   if ( inr ) {
     t = (p < 2) ? nranget : ranget;
     g_string_append_printf(s, t, a[i-1], a[i]);
     inr = false; p = 0;
   } else {
     g_string_append_printf(s, ",%d", a[i]);
   }
 }
 if ( inr ) g_string_append_printf(s, "-%d", a[i-1]);
 r = strdup(s->str);
 g_string_free(s, TRUE);
 return r;

}


int main() { 

 int i[] = { 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 }; 

 char *r = range_string_from_array(sizeof(i)/sizeof(int), i);
 puts(r);
 free(r);
 return 0;

}</lang>

Output: 

0-2,4,6-8,11,12,14-25,27-33,35-39

C++

<lang cpp>

  1. include <iostream>
  2. include <iterator>
  3. include <cstddef>

template<typename InIter> 

void extract_ranges(InIter begin, InIter end, std::ostream& os)

{ 

 if (begin == end)
   return;

 int current = *begin++;
 os << current;
 int count = 1;

 while (begin != end)
 {
   int next = *begin++;
   if (next == current+1)
     ++count;
   else
   {
     if (count > 2)
       os << '-';
     else
       os << ',';
     if (count > 1)
       os << current << ',';
     os << next;
     count = 1;
   }
   current = next;
 }

 if (count > 1)
   os << (count > 2? '-' : ',') << current;

}

template<typename T, std::size_t n> 

T* end(T (&array)[n])

{ 

 return array+n;

}

int main() { 

 int data[] = { 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 };

 extract_ranges(data, end(data), std::cout);
 std::cout << std::endl;

} </lang> Output: 

0-2,4,6-8,11,12,14-25,27-33,35-39

D

D v.2. <lang d>import std.stdio: writeln; import std.string: join, format;

string rangeExtract(int[] items) { 

   string[] ranges;

   for (int i = 0; i < items.length; i++) {
       auto low = items[i];
       while (i < (items.length-1) && (items[i]+1) == items[i+1])
           i++;
       auto hi = items[i];

       if (hi - low >= 2)
           ranges ~= format("%d-%d", low, hi);
       else if (hi - low == 1)
           ranges ~= format("%d,%d", low, hi);
       else
           ranges ~= format("%d", low);
   }

   return ranges.join(",");

}

void main() { 

   auto data = [ 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];
   writeln(rangeExtract(data));

}</lang> The output: 

0-2,4,6-8,11,12,14-25,27-33,35-39

E

This example is incorrect. Please fix the code and remove this message.

Details: 14-15 should be 14,15 according to the range format rules.

This example is incorrect. Please fix the code and remove this message.

Details: Wrong example list used.

Cheeky solution: relying on the standard library for finding ranges, and just formatting them ourselves.

<lang e>def rex(numbers :List[int]) { 

   var region := 0..!0
   for n in numbers { region |= n..n }
   var ranges := []
   for interval in region.getSimpleRegions() { 
       def a := interval.getOptStart()
       def b := interval.getOptBound() - 1
       ranges with= if (b > a + 1) {
                       `$a-$b`
                   } else if (b <=> a + 1) {
                       `$a,$b`
                   } else { # b <=> a
                       `$a`
                   }
   }
   return ",".rjoin(ranges)

}</lang>

<lang e>? rex([-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20])

  1. value: "-6,-3-1,3-5,7-11,14-15,17-20"</lang>

Haskell

<lang haskell>import Data.List (intercalate)

extractRange :: [Int] -> String extractRange = intercalate "," . f 

 where f :: [Int] -> [String]
       f (x1 : x2 : x3 : xs) | x1 + 1 == x2 && x2 + 1 == x3
            = (show x1 ++ '-' : show xn) : f xs'
         where (xn, xs') = g (x3 + 1) xs
               g a (n : ns) | a == n    = g (a + 1) ns
                            | otherwise = (a - 1, n : ns)
               g a []                   = (a - 1, [])
       f (x : xs)            = show x : f xs
       f []                  = []</lang>

<lang text>> extractRange $ [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"</lang>

Icon and Unicon

Icon

<lang Icon>procedure main() 

  R := [  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 ]

  write("Input list      := ",list2string(R))
  write("Extracted sting := ",s := range_extract(R)  | "FAILED")

end

procedure range_extract(R) #: return string/range representation of a list of unique integers local s,sep,low,high,x 

  every if integer(x:= !R) ~= x then fail                  # ensure all are integers, 
  R := sort(set(R))                                        # unique, and sorted

  s := sep := ""
  while s ||:= sep || ( low := high := get(R) ) do {       # lower bound of range
     sep := ","
     while high := ( R[1] = high + 1 ) do get(R)           # find the end of range
     if high > low+1 then s ||:= "-" || high               # - record range of 3+
     else if high = low+1 then push(R,high)                # - range of 2, high becomes new low
     }
  return s

end

procedure list2string(L) #: helper to convert list to string local s 

  every (s := "[ ") ||:= !L || " "
  return s || "]"

end</lang> Sample output: 

Input 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 ]
Extracted sting := 0-2,4,6-8,11,12,14-25,27-33,35-39


Unicon

This Icon solution works in Unicon.

J

<lang j>require 'strings' fmt=: [: ;@(8!:0) [`]`({. ; (',-' {~ 2 < #) ; {:)@.(2 <. #) group=: <@fmt;.1~ 1 ~: 0 , 2 -~/\ ] extractRange=: ',' joinstring group</lang>

Example use:

<lang j> extractRange 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 0-2,4,6-8,11,12,14-25,27-33,35-39</lang>

MUMPS

<lang MUMPS>RANGCONT(X) ;Integer range contraction 

NEW Y,I,CONT,NOTFIRST,CURR,PREV,NEXT,SEQ SET Y="",SEQ=0,PREV="",CONT=0
FOR I=1:1:$LENGTH(X,",") DO
.SET NOTFIRST=$LENGTH(Y),CURR=$PIECE(X,",",I),NEXT=$PIECE(X,",",I+1)
.FOR  Q:$EXTRACT(CURR)'=" "  S CURR=$EXTRACT(CURR,2,$LENGTH(CURR))  ;clean up leading spaces
.S SEQ=((CURR-1)=PREV)&((CURR+1)=NEXT)
.IF 'NOTFIRST SET Y=CURR
.IF NOTFIRST DO
..;Order matters due to flags
..IF CONT&SEQ ;Do nothing
..IF 'CONT&'SEQ SET Y=Y_","_CURR
..IF CONT&'SEQ SET Y=Y_CURR,CONT=0
..IF 'CONT&SEQ SET Y=Y_"-",CONT=1
.SET PREV=CURR
IF CONT SET Y=Y_PREV
K I,CONT,NOTFIRST,CURR,PREV,NEXT,SEQ
QUIT Y</lang>

Example: 

USER>SET S="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"
 
USER>W $$RANGCONT^ROSETTA(S)
0-2,4,6-8,11,12,14-25,27-33,35-39

OCaml

<lang ocaml>let range_extract = function 

 | [] -> []
 | x::xs ->
     let rec aux acc = function
       | (a,b), c::tail ->
           if (succ b) = c
           then aux acc ((a,c), tail)
           else aux ((a,b)::acc) ((c,c), tail)
       | v, [] ->
           List.rev (v::acc)
     in
     aux [] ((x,x), xs)

let string_of_range rng = 

 let rec aux acc = function
   | (a,b)::tl ->
       let this =

if (succ a) = b then (Printf.sprintf "%d,%d" a b) 

         else if a = b
         then (string_of_int a)
         else (Printf.sprintf "%d-%d" a b)
       in
       aux (this::acc) tl
   | [] ->
       String.concat "," (List.rev acc)
 in
 aux [] rng

let () = 

 let li =
   [ 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 ]
 in
 let rng = range_extract li in
 print_endline(string_of_range rng)</lang>

Output 

0-2,4,6-8,11,12,14-25,27-33,35-39

Oz

<lang oz>declare 

 fun {Extract Xs}
    {CommaSeparated
     {Map {ExtractRanges Xs} RangeToString}}
 end

 fun {ExtractRanges Xs}
    fun {Loop Ys Start End}
       case Ys
       of Y|Yr andthen Y == End+1 then {Loop Yr Start Y}
       [] Y|Yr                    then Start#End|{Loop Yr Y Y} 
       [] nil                     then [Start#End]
       end
    end
 in
    case Xs
    of X|Xr then {Loop Xr X X}
    [] nil then nil
    end
 end
 
 fun {RangeToString S#E}
    if E-S >= 2 then
       {VirtualString.toString S#"-"#E}
    else
       {CommaSeparated
        {Map {List.number S E 1} Int.toString}}
    end
 end

 fun {CommaSeparated Xs}
    {Flatten {Intersperse "," Xs}}
 end
  
 fun {Intersperse Sep Xs}
    case Xs of X|Y|Xr then
       X|Sep|{Intersperse Sep Y|Xr}
    else
       Xs
    end
 end

in 

 {System.showInfo
  {Extract [ 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 ]}}</lang>

Sample output: <lang oz>0-2,4,6-8,11,12,14-25,27-33,35-39</lang>

Perl

Using regexes. Also handles +/- and negative integer ranges.

<lang Perl>sub rangext { 

   my $str = join ' ', @_;
   1 while $str =~ s{([+-]?\d+) ([+-]?\d+)}
       {$1.(abs($2 - $1) == 1 ? '~' : ',').$2}eg; # abs for neg ranges
   $str =~ s/(\d+)~(?:[+-]?\d+~)+([+-]?\d+)/$1-$2/g;
   $str =~ tr/~/,/;
   return $str;

}

  1. Test and display

my @test = qw(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);

print rangext(@test), "\n";</lang>

Output: 

0-2,4,6-8,11,12,14-25,27-33,35-39

PicoLisp

<lang PicoLisp>(de rangeextract (Lst) 

  (glue ","
     (make
        (while Lst
           (let (N (pop 'Lst)  M N)
              (while (= (inc M) (car Lst))
                 (setq M (pop 'Lst)) )
              (cond
                 ((= N M) (link N))
                 ((= (inc N) M) (link N M))
                 (T (link (list N '- M))) ) ) ) ) ) )</lang>

Output: 

: (rangeextract
   (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 ) )

-> "0-2,4,6-8,11,12,14-25,27-33,35-39"

PL/I

<lang PL/I> range_extraction: 

  procedure options (main);
  declare c character (1);
  declare (old, new, initial) fixed binary (31);
  declare out file output;
  open file (out) output title ('/out,type(text),recsize(70)');

  c = ' ';
  get list (old);
  do forever;
     initial = old;
     on endfile (sysin) begin;
        put file (out) edit (c, trim(old)) (a);
        stop;
     end;
     get (new);
     put edit (c) (a);
     if new = old+1 then
        do; /* we have a run. */
           on endfile (sysin) begin;
              put file (out) edit (c, trim(initial), '-', trim(old) ) (a);
              stop;
           end;
           do while (new = old+1);
              old = new;
              get (new);
           end;
           /* At this point, old holds the last in a run; */
           /* initial holds the first in a run. */
           put file (out) edit (c, trim(initial), '-', trim(old) ) (a);
           old = new;
        end;
     else /* we have an isolated value. */
        do;
           put file (out) edit (c, trim(old)) (a);
           old = new;
        end;
     c = ',';
  end;

end range_extraction; </lang> OUTPUT: <lang> 

0-2,4,6-8,11-12,14-25,27-33,35-39

</lang> </lang>

PureBasic

Even though the example integer list only includes ascending ranges this code will also handles descending ranges. <lang PureBasic>DataSection 

 Data.i  33 ;count of elements to be read
 Data.i  0,  1,  2,  4,  6,  7,  8, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24
 Data.i  25, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39

EndDataSection

NewList values()

setup list

Define elementCount, i Read.i elementCount For i = 1 To elementCount 

 AddElement(values()): Read.i values()

Next

Procedure.s rangeExtract(List values()) 

 Protected listSize = ListSize(values()) - 1
 Protected rangeMarker, rangeStart, rangeIncrement, retraceSteps, rangeSize, endOfRange, output.s, sub.s
 
 ForEach values()
   rangeStart = values(): 
   sub = Str(rangeStart)
   If NextElement(values())
     retraceSteps = 1
     rangeIncrement = values() - rangeStart
     If rangeIncrement = 1 Or rangeIncrement = -1
       ;found start of possible range
       If ListIndex(values()) <> listSize
         retraceSteps = 2
         rangeSize = 2
         endOfRange = #False
         rangeMarker = values()
         While NextElement(values())
           If values() - rangeMarker <> rangeIncrement
             endOfRange = #True
             Break
           EndIf
           rangeSize + 1
           rangeMarker = values()
         Wend
         
         If rangeSize > 2
           sub = Str(rangeStart) + "-" + Str(rangeMarker)
           If Not endOfRange
             retraceSteps = 0 ;at end of list
           Else
             retraceSteps = 1
           EndIf 
         EndIf
       EndIf 
     EndIf
     
     ;return to the value before look-aheads
     While retraceSteps > 0
       PreviousElement(values()): retraceSteps - 1
     Wend 
   EndIf
   
   output + sub + "," 
 Next
 
 ProcedureReturn RTrim(output, ",")

EndProcedure

If OpenConsole() 

 PrintN(rangeExtract(values()))
 
 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
 Input()
 CloseConsole()

EndIf</lang> Sample output: 

0-2,4,6-8,11,12,14-25,27-33,35-39

Python

<lang python>#import random

def rangeextract(lst): 

   lenlst = len(lst)
   i, ranges = 0, []
   while i< lenlst:
       low = lst[i]
       while i <lenlst-1 and lst[i]+1 == lst[i+1]: i +=1
       hi = lst[i]
       ranges.append(
           '%i-%i'  % (low, hi) if hi - low >= 2 else
           ('%i,%i' % (low, hi) if hi - low == 1 else
            '%i' % low) )
       i += 1
   return ','.join(ranges)

lst = [ 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]

print(rangeextract(lst))</lang>

Sample output 

0-2,4,6-8,11,12,14-25,27-33,35-39

Ruby

<lang ruby>def range_extract(l) 

 sorted = l.sort
 range = []
 start = sorted.first
 # pad the list with a big value, so that the last loop iteration will 
 # appended something to the range
 sorted.concat([Float::MAX]).each_cons(2) do |prev,n|
   if prev.succ < n
     if start == prev
       range << start.to_s
     else
       range << "%d%s%d" % [start, (start.succ == prev ? "," : "-"), prev]
     end
     start = n
   end
 end
 range.join(',')

end

lst = [ 

   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

]

p rng = range_extract(lst)</lang>

output: 

"0-2,4,6-8,11,12,14-25,27-33,35-39"

SNOBOL4

Translation of: Perl
Works with: Macro Spitbol
Works with: CSnobol

Handles +/- and negative ranges.

<lang SNOBOL4>* # Absolute value 

       define('abs(n)') :(abs_end)

abs abs = ~(abs = lt(n,0) -n) n :(return) abs_end 

       define('rangext(str)d1,d2') :(rangext_end)

rangext num = ('+' | '-' | ) span('0123456789') rxt1 str ',' span(' ') = ' ' :s(rxt1) rxt2 str num . d1 ' ' num . d2 = + d1 ('~,' ? *eq(abs(d2 - d1),1) '~' | ',') d2 :s(rxt2) rxt3 str ('~' | '-') num '~' = '-' :s(rxt3) rxt4 str '~' = ',' :s(rxt4) 

       rangext = str :(return)

rangext_end

  • # Test and display
       test =  '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' 

       output = rangext(test)

end</lang>

Output: 

0-2,4,6-8,11,12,14-25,27-33,35-39

Tcl

<lang tcl>proc rangeExtract list { 

   set result [lindex $list 0]
   set first [set last [lindex $list 0]]
   foreach term [lrange $list 1 end] {

if {$term == $last+1} { set last $term continue } if {$last > $first} { append result [expr {$last == $first+1 ? "," : "-"}] $last } append result "," $term set first [set last $term] 

   }
   if {$last == $first+1} {

append result "," $last 

   } elseif {$last > $first} {

append result "-" $last 

   }
   return $result

}

  1. Commas already removed so it is a natural Tcl list

puts [rangeExtract { 

   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

}]</lang> Output: 

0-2,4,6-8,11,12,14-25,27-33,35-39
Retrieved from "https://rosettacode.org/wiki/Range_extraction?oldid=151931"