Number::Interval - Implement a representation of a numeric interval

  use Number::Interval;

  $i = new Number::Interval( Min => -4, Max => 20);
  $i = new Number::Interval( Min => 0 );

  $is = $i->contains( $value );
  $status = $i->intersection( $i2 );

  print "$i";

package Number::Interval;

use 5.006;
use strict;
use warnings;
use Carp;
use Data::Dumper;
use overload 
  '""' => "stringify",
  '==' => 'equate',
  'eq' => "equate",
  '!=' => "notequal",
  'ne' => "notequal";

# CVS ID: $Id$

use vars qw/ $VERSION /;
$VERSION = '0.05';

# hash of allowed lower-cased constructor keys with
# corresponding accessor method
my %ConstructAllowed = (
			min => 'min',
			max => 'max',
			incmax => 'inc_max',
			incmin => 'inc_min',
			posdef => 'pos_def',
		       );

sub new {
  my $proto = shift;
  my $class = ref($proto) || $proto;

  my %args = @_;

  my $r = {
	   Min => undef,
	   Max => undef,
	   IncMax => 0,
	   IncMin => 0,
	   PosDef => 0,
	  };

  # Create object
  my $obj = bless $r, $class;

  # Populate it
  for my $key (keys %args) {
    my $lc = lc( $key );
    if (exists $ConstructAllowed{$lc}) {
      my $method = $ConstructAllowed{$lc};
      $obj->$method( $args{$key} );
    }
  }

  return $obj;
}

sub copy {
  my $self = shift;
  my $new = $self->new();
  # simplistic hash copy since we know that we are a simple hash internally
  # subclasses might get in trouble if they have complexity.
  %$new = %$self;
  return $new;
}

sub max {
  my $self = shift;
  $self->{Max} = shift if @_;
  return $self->{Max};
}

sub min {
  my $self = shift;
  $self->{Min} = shift if @_;
  return $self->{Min};
}

sub inc_max {
  my $self = shift;
  $self->{IncMax} = shift if @_;
  return $self->{IncMax};
}

sub inc_min {
  my $self = shift;
  $self->{IncMin} = shift if @_;
  return $self->{IncMin};
}

sub pos_def {
  my $self = shift;
  if (@_) {
    $self->{PosDef} = shift;
    if ($self->{PosDef} && !defined $self->min) {
      $self->min( 0 );
    }
  }
  return $self->{PosDef};
}

sub minmax {
  my $self = shift;
  if (@_) {
    $self->min( $_[0] );
    $self->max( $_[1] );
  }
  my @minmax = ( $self->min, $self->max );
  return (wantarray ? @minmax : \@minmax);
}

sub minmax_hash {
  my $self = shift;
  if (@_) {
    my %args = @_;
    $self->min( $args{min} ) if exists $args{min};
    $self->max( $args{max} ) if exists $args{max};
  }

  # Populate the output hash
  my %minmax;
  $minmax{min} = $self->min if defined $self->min;
  $minmax{max} = $self->max if defined $self->max;

  return (wantarray ? %minmax : \%minmax);
}

sub sizeof {
  my $self = shift;
  if( ! defined( $self->min ) ||
      ! defined( $self->max ) ) {
    return undef;
  }

  return abs( $self->max - $self->min );
}

sub stringify {
  my $self = shift;

  my $min = $self->min;
  my $max = $self->max;

  # are we inclusive (for unbound ranges)
  my $inc_min_ub = ( $self->inc_min ? "=" : " " );
  my $inc_max_ub = ( $self->inc_max ? "=" : " " );

  if (defined $min && defined $max) {
    # Bound

    # use standard interval notation when using a bound range
    my $inc_min_b = ( $self->inc_min ? "[" : "(" );
    my $inc_max_b = ( $self->inc_max ? "]" : ")" );

    if ($min == $max) {
      # no range
      return "==$min";
    } elsif ($max < $min) {
      return "<$inc_max_ub$max and >$inc_min_ub$min";
    } else {
      if ($min <= 0 && $self->pos_def) {
	return "<$inc_max_ub$max";
      } else {
	return "$inc_min_b$min,$max$inc_max_b";
      }
    }
  } elsif (defined $min) {
    return ">$inc_min_ub$min";
  } elsif (defined $max) {
    return "<$inc_max_ub$max";
  } else {
    return "Inf";
  }

}

sub isinverted {
  my $self = shift;
  my $min = $self->min;
  my $max = $self->max;

  if (defined $min and defined $max) {
    return 1 if $min > $max;
  }
  return 0;
}

sub isbound {
  my $self = shift;
  my $min = $self->min;
  my $max = $self->max;
  if (defined $min and defined $max) {
    return 1;
  } else {
    return 0;
  }
}

sub equate {
  my $self = shift;
  my $comparison = shift;

  # Need to check that both are objects
  return 0 unless defined $comparison;
  return 0 unless UNIVERSAL::isa($comparison, "Number::Interval");

  # need to be explicit about undefs
  # return false immediately we find a difference
  for my $m (qw/ min max/) {
    # first values
    if ( defined $comparison->$m() ) {
      return 0 if !defined $self->$m();
      return 0 if $comparison->$m() != $self->$m();
    } else {
      return 0 if defined $self->$m();
    }

    # then boolean
    my $incm = 'inc_' . $m;

    # return false if state of one is NOT the other
    return 0 if ( ( $self->$incm() && !$comparison->$incm() ) ||
		  ( !$self->$incm() && $comparison->$incm() ) );
  }
  return 1;
}

sub notequal {
  my $self = shift;
  return !$self->equate( @_ );
}

sub contains {
  my $self = shift;
  my $value = shift;

  my $max = $self->max;
  my $min = $self->min;
  return 1 if (!defined $max && !defined $min);

  # Assume it doesnt match the interval
  my $contains = 0;
  if ($self->isinverted) {
    # Inverted interval. Both max and min must be defined
    if (defined $max and defined $min) {
      if ($self->inc_max && $self->inc_min) {
	if ($value <= $max || $value >= $min) {
	  $contains = 1;
	}
      } elsif ($self->inc_max) {
	if ($value <= $max || $value > $min) {
	  $contains = 1;
	}
      } elsif ($self->inc_min) {
	if ($value < $max || $value >= $min) {
	  $contains = 1;
	}
      } else {
	if ($value < $max || $value > $min) {
	  $contains = 1;
	}
      }

    } else {
      croak "An interval can not be inverted with only one defined value";
    }

  } else {
    # normal interval
    if (defined $max and defined $min) {
      if ($max == $min) {
	$contains = 1 if $value == $max;
      } elsif ($self->pos_def && $value < 0) {
	$contains = 0;
      } elsif ($self->inc_max && $self->inc_min) {
	if ($value <= $max && $value >= $min) {
	  $contains = 1;
	}
      } elsif ($self->inc_max) {
	if ($value <= $max && $value > $min) {
	  $contains = 1;
	}
      } elsif ($self->inc_min) {
	if ($value < $max && $value >= $min) {
	  $contains = 1;
	}
      } else {
	if ($value < $max && $value > $min) {
	  $contains = 1;
	}
      }
    } elsif (defined $max) {
      if ($self->inc_max) {
	$contains = 1 if $value <= $max;
      } else {
	$contains = 1 if $value <= $max;
      }
    } elsif (defined $min) {
      if ($self->inc_min) {
	$contains = 1 if $value >= $min;
      } else {
	$contains = 1 if $value > $min;
      }
    }
  }

  return $contains;
}

# There must be a neater way of implementing this method!
# There may be some edge cases that fail (when one of the
# interval boundaries is identical in both objects)

sub intersection {
  my $self = shift;
  my $new = shift;

  # Check input
  return 0 unless defined $new;
  return 0 unless UNIVERSAL::isa($new,"Number::Interval");

  # Get the values
  my $max1 = $self->max;
  my $min1 = $self->min;
  my $max2 = $new->max;
  my $min2 = $new->min;

  my $inverted1 = $self->isinverted;
  my $inverted2 = $new->isinverted;
  my $inverted = $inverted1 || $inverted2;

  my $bound1 = $self->isbound;
  my $bound2 = $new->isbound;
  my $bound  = $bound1 || $bound2;

  my $outmax;
  my $outmin;

  # There are six possible combinations of Bound interval,
  # inverted interval and unbound interval.

  if ($bound) {
    # Support BB, BU and BI and II

    if ($inverted) {
      # Any inverted: II or BI or IB or UI or IU
      #print "*********** INVERTED *********\n";

      if ($inverted1 && $inverted2) {
	# II
	# This is fairly easy.
	# Always take the smallest max and largest min
	$outmin = ( $min1 > $min2 ? $min1 : $min2);
	$outmax = ( $max1 < $max2 ? $max1 : $max2);

      } else {
	# IB, IU (BI and UI)
	# swap if needed, to have everything as IX
	my $nowbound;
	if ($inverted2) {
	  ($max1,$min1,$max2,$min2) = ($max2,$min2,$max1,$min1);
	  # determine bound state of #1 before losing order information
	  $nowbound = $bound1;
	} else {
	  # #1 is inverted so we need the bound state of #1
	  $nowbound = $bound2;
	}

	if ($nowbound) {
	  # IB
	  # We know that max2 and min2 are defined
	  # We always end up with at least one bound interval
	  if ($min2 < $max1) {
	    $outmin = $min2;

	    # If max2 is too high we get two intervals.
	    croak "This intersection results in two output intervals. Currently not supported" if $max2 > $min1;

	    # Upper limit of interval must be the min of the two maxes
	    $outmax = ( $max1 < $max2 ? $max1 : $max2 );

	  } elsif ($min2 < $min1) {

	    # Make sure we intersect a little
	    # If the bound interval lies outside the inverted interval
	    # return undef
	    if ($max2 >= $min1) {
	      $outmin = $min1;
	      $outmax = $max2;
	    }

	  } elsif ($min2 > $min1) {

	    # This is just the bound interval
	    $outmin = $min2;
	    $outmax = $max2;


	  } else {
	    croak "Oops Bug in interval intersection [6]\n".
	      _formaterr( $min1, $max1, $min2, $max2);
	  }


	} else {
	  # IU
	  if (defined $max2) {

	    # The upper bound must be below the inverted "min"
	    # else we get intersection of two intervals
	    if ($max2 > $min1) {
	      croak "This intersection results in two output intervals. Currently not supported";
	    } elsif ($max2 > $max1) {
	      # Just use the inverted interval
	      $outmax = $max1;
	      $outmin = $min1;
	    } else {
	      # max must be decreased to include min2
	      $outmax = $max2;
	      $outmin = $min1;
	    }


	  } elsif (defined $min2) {

	    # The lower bound must be above the "max"
	    # else we get an intersection of two intervals
	    if ($min2 < $max1) {
	      croak "This intersection results in two output intervals. Currently not supported";
	    } elsif ($min2 < $min1) {
	      # Just use the inverted interval
	      $outmax = $max1;
	      $outmin = $min1;
	    } else {
	      # min must be increased to include min2
	      $outmax = $max1;
	      $outmin = $min2;
	    }

	  } else {
              # both undefined
              $outmax = $max1;
              $outmin = $min1;
	  }

	}

      }



    } else {
      # BB, BU or UB
      #print "*********** BOUND NON INVERTED ************\n";
      if ($bound1 and $bound2) {
	# BB
	#print "---------- BB -----------\n";
	$outmin = ( $min1 > $min2 ? $min1 : $min2 );
	$outmax = ( $max1 < $max2 ? $max1 : $max2 );

	# Check that we really are overlapping
	if ($outmax < $outmin) {
	  # oops - intervals did not intersect. Reset
	  $outmin = $outmax = undef;
	}
	

      } else {
	# BU and UB
	#print "---------- BU/UB -----------\n";
	# swap if needed, to have everything as BU
	if ($bound2) {
	  ($max1,$min1,$max2,$min2) = ($max2,$min2,$max1,$min1);
	}

	# unbound is now guaranteed to be (2)
	# Check that unbound max is in interval
	if (defined $max2) {
	  if ($max2 <= $max1 && $max2 >= $min1) {
	    # inside interval
	    $outmax = $max2;
	    $outmin = $min1;
	  } elsif ($max2 <= $min1) {
	    # outside interval. No intersection
	  } elsif ($max2 >= $max1) {
	    # below interval. irrelevant
	    $outmax = $max1;
	    $outmin = $min1;
	  } else {
	    croak "Number::Interval - This should not happen[2]\n".
	      _formaterr( $min1, $max1, $min2, $max2);
	  }

	} elsif (defined $min2) {
	  if ($min2 <= $max1 && $min2 >= $min1) {
	    # inside interval
	    $outmax = $max1;
	    $outmin = $min2;
	  } elsif ($min2 >= $max1) {
	    # outside interval. No intersection
	  } elsif ($min2 <= $min1) {
	    # below interval. irrelevant
	    $outmax = $max1;
	    $outmin = $min1;
	  } else {
	    croak "Number::Interval - This should not happen[3]:\n" .
	      _formaterr( $min1, $max1, $min2, $max2);
	  }

	} else {
          # The second interval is unbounded at both ends
          $outmax = $max1;
          $outmin = $min1;
	}


      }

    }


  } else {
    # Unbound+Unbound only
    # Four options here. 
    # 1. A max and a max =>  max (same for min and min)
    # 2. max and a min with no overlap => no intersection
    # 3. max and min with overlap => bounded interval
    # 4. all undefined
    if (defined $max1 && defined $max2) {
      $outmax = ( $max1 < $max2 ? $max1 : $max2 );
    } elsif (defined $min2 && defined $min1) {
      $outmin = ( $min1 > $min2 ? $min1 : $min2 );
    } else {
      # max and a min - one must be defined for both
      my $refmax = (defined $max1 ? $max1 : $max2);
      my $refmin = (defined $min1 ? $min1 : $min2);

      if (!defined $refmax && !defined $refmin) {
	# infinite bound
	return 1;
      } elsif (!defined $refmax) {
	# just a min
	$outmin = $refmin;
      } elsif (!defined $refmin) {
	# just a max
	$outmax = $refmax;
      } elsif ($refmax > $refmin) {
	# normal bound interval
	$outmax = $refmax;
	$outmin = $refmin;
      } else {
	# unbound interval. No intersection
      }


    }

  }


  # Modify object if we have new values
  if (defined $outmax or defined $outmin) {
    $self->max($outmax);
    $self->min($outmin);
    return 1;
  } else {
    return 0;
  }

}

sub _formaterr {
  my ($min1, $max1, $min2, $max2) = @_;
  return "Comparing : (".
    (defined $min1 ? $min1 : "<undef>" ).
      "," . 
	(defined $max1 ? $max1 : "<undef>" ).
	  ") with (".
	    (defined $min2 ? $min2 : "<undef>" ).
	      "," . (defined $max2 ? $max2 : "<undef>" ).
		")";
}

1;