#!/usr/bin/perl
# -*- CPerl -*-

use strict;
use warnings;

# sparse range structure:
#  array of arrayref/number
#   single integers represented as number
#   contigous ranges as arrayref [LOW,HIGH] inclusive

# given: string "A,B,C,X-Y,Z"
# return: sorted array [A, B, C, [X, Y], Z]
sub parse ($) {
  my @elements = split /,/, shift;

  foreach (@elements) {
    s/\s+//g;				# prune whitespace
    next unless m/\d+-\d+/;		# skip conversion if single integer
    $_ = [split /-/, $_];		# convert ranges to arrayrefs
  }

  # sort range set
  @elements = sort {(ref($a)?$a->[0]:$a) <=> (ref($b)?$b->[0]:$b)} @elements;

  # merge overlapping loose elements into preceding ranges
  for (my $i = 0; $i < $#elements; $i++) {
    next unless ref $elements[$i];	# skip single integers
    while ($i+1 <= $#elements and $elements[$i+1] <= $elements[$i][1])
      { splice @elements, $i+1, 1 }	# remove elements included in range
  }

  # coalesce contiguous integers into ranges
  for (my $i = 0; $i < $#elements; $i++) {
    next if ref $elements[$i];		# skip ranges
    if ($elements[$i]+1 == $elements[$i+1]) {
      my $j = 1+$i;
      $j++ while !ref($elements[$j]) && $elements[$j]+1 == $elements[$j+1];
      splice @elements, $i, 1+$j-$i, [$elements[$i], $elements[$j]];
    }
  }

  # merge adjacent loose elements into succeeding ranges
  for (my $i = 0; $i < $#elements; $i++) {
    next if ref $elements[$i];		# skip ranges
    next unless ref $elements[$i+1];	# but next element is a range
    # There can be at most one such element, since contiguous integers were
    # coalesced into ranges above.
    if ($elements[$i]+1 == $elements[$i+1][0])
      { splice @elements, $i, 2, [$elements[$i], $elements[$i+1][1]] }
  }

  # merge adjacent loose elements into preceding ranges
  for (my $i = 0; $i < $#elements; $i++) {
    next unless ref $elements[$i];	# skip single integers
    next if ref $elements[$i+1];	# but next element is a single integer
    # There can be at most one such element, since contiguous integers were
    # coalesced into ranges above.
    if ($elements[$i][1]+1 == $elements[$i+1])
      { splice @elements, $i, 2, [$elements[$i][0], $elements[$i+1]] }
  }

  # merge overlapping ranges
  for (my $i = 0; $i < $#elements; $i++) {
    next unless ref $elements[$i] and ref $elements[$i+1];
    splice @elements, $i, 2, [$elements[$i][0], $elements[$i+1][1]]
      if $elements[$i][1] >= $elements[$i+1][0];
  }

  # merge adjacent ranges
  for (my $i = 0; $i < $#elements; $i++) {
    next unless ref $elements[$i] and ref $elements[$i+1];
    splice @elements, $i, 2, [$elements[$i][0], $elements[$i+1][1]]
      if $elements[$i][1]+1 == $elements[$i+1][0];
  }

  return \@elements;
}

# given: sorted array from sub parse and integer
# return true if the integer is in the sorted array
sub search ($$) {
  my $set = shift;
  my $num = shift;

  my $left = 0; my $right = $#$set;
  my $i = $#$set >> 1;			# bitshift for integer /2
  while ($left < $right) {
    if (ref($set->[$i])) {		# evaluate a range
      return 1		# number within this range
	if $num >= $set->[$i][0] && $num <= $set->[$i][1];
      if ($num > $set->[$i][0])	{ $left  = $i+1 }
      else			{ $right = $i-1 }
    } else {				# evaluate a single integer
      return 1		# number matched
	if $num == $set->[$i];
      if ($num > $set->[$i])	{ $left  = $i+1 }
      else			{ $right = $i-1 }
    }
    $i = ($left + $right) >> 1;		# bitshift for integer /2
  }


  # last check
  if (ref($set->[$i])) {
    return $num >= $set->[$i][0] && $num <= $set->[$i][1]
  } else {
    return $num == $set->[$i]
  }
}

my $Set = parse shift;

use Data::Dumper;
print Data::Dumper->new([$Set],[qw(Set)])->Indent(0)->Dump,"\n";

foreach (@ARGV) {
  print $_, search($Set, $_) ? ' is' : ' is not', " in the set\n";
}