Interval class and extension

[Weedpacket]

'Bout time I posted something here again.
When you have a linear space on which you can identify specific points (any collection of things which have a specific order - numbers, dates, etc.) one of the first extensions of the concept is that you can have intervals - by picking out two points in the space you can specify the entire chunk of space that lies between them.
So here's a class or three for PHP5. interval is the base class, and also implements the space of real numbers. Subclassed from this is a date_interval class; and there is a class that implements sets of intervals.
I think I've pretty much covered the basic operations on general-purpose intervals: you can determine if two intervals overlap, or if one interval is contained within another; you can join two overlapping intervals into one, or excise one interval from another, and so on.
When subclassing, there are a few methods to override: lt: the "less than" operator which defines the ordering of points in the space (it takes two points as its arguments, not intervals) eq: tests the equality of two points length: the length of this interval widen: this is the basic function for moving the endpoints of an interval left or right. You may also wish to override widen_left and widen_right as well midpoint: returns the point that lies at the midpoint of the interval of course __toString() is used to return a human-readable string representation of the interval. (gt, ge, le, and ne are also available: these are all defined in terms of lt and eq, however, so explicit overriding is not necessary for them to work as expected).
Well, there's some ad-hoc commentary in the file. If I didn't welcome criticism I wouldn't be posting here. Someone will probably yell at me for the accessor methods. For an intro, part of the file is excerpted below, followed by some weedy examples of its use.


/*
An example extension of the interval class: intervals of days
(i.e., date ranges). Dates are passed in as associative arrays
('y'=>year, 'm'=>month, 'd'=>day) - all three use calendrical indexing (i.e,
1-indexed). So for example January 26, 1986 would be passed in as
array('y'=>1986, 'm'=>1, 'd'=>26).

Since intervals are closed, the range (2005,5,1) to (2005,5,7) is seven
days long - not the six as you might expect from simply subtracting the
two. Similarly, the range (1883,9,6) to (1883,9,6) is one day long.

For exemplary reasons, all date arithmetic is performed in-house,
rather than using native functions and storing dates as timestamps.
(It thus works outside the range of ordinary timestamps.)
Exercise for the reader: implement a date_interval class using that approach.
*/
class date_interval extends interval
{

public function __construct($left=null, $right=null)
{
if($left===null)
{
// The only place where a native date function is used.
// Warning: this means that if 32-bit signed arithmetic is still
// being used to store timestamps, then this code will break after
// 2038 and before 1900. Time travellers, you have been warned.
$now = getdate();
$left = array('y'=>$now['year'], 'm'=>$now['mon'], 'd'=>$now['mday']);
}
if($right===null) $right=$left;
self::fixdate($left);
self::fixdate($right);
if(self::lt($right,$left))
{
$t = $left;
$left = $right;
$right = $t;
}
$this->left = $left;
$this->right = $right;
}
public function __toString()
{
$left = $this->left['y']. '-'.$this->left['m']. '-'.$this->left['d'];
$right = $this->right['y'].'-'.$this->right['m'].'-'.$this->right['d'];
return '['.$left.', '.$right.']';
}

// Overriding the space-specific methods of the interval class.

public static function lt($a,$b)
{
if($a['y']<$b['y']) return true;
if($a['y']>$b['y']) return false;
if($a['m']<$b['m']) return true;
if($a['m']>$b['m']) return false;
if($a['d']<$b['d']) return true;
if($a['d']>$b['d']) return false;
return false;
}
public static function eq($a,$b)
{
return $a['y']==$b['y'] && $a['m']==$b['m'] && $a['d']==$b['d'];
}

// Number of days between two dates - measured in days
// Yes, I suppose I could have converted both to Julian
// Days and then subtracted - but naaah.
// Note that the number of days between a date and itself is 1
// (i.e. the interval from 1990-12-14 to 1990-12-14 is one day long).
public function length()
{
static $days = array(null,0,31,59,90,120,151,181,212,243,273,304,334);

$length = 1+$this->right['d']-$this->left['d'];
$length += $days[$this->right['m']]-$days[$this->left['m']];

if($this->left['m']>2 && self::leap($this->left['y']))
$length--;
if($this->right['m']>2 && self::leap($this->right['y']))
$length++;

for($year = $this->left['y']; $year<$this->right['y']; ++$year)
$length += self::leap($year) ? 366 : 365;

return $length;
}

public function midpoint()
{
$midpoint = $this->left;
$midpoint['d'] += $this->length()>>1;
self::fixdate($midpoint);
return $midpoint;
}

public function widen($v,$w=null)
{
if($w===null) $w = $v;

$this->left['d'] -= $v;
self::fixdate($this->left);
$this->right['d'] += $w;
self::fixdate($this->right);

// Since we can "widen" by negative amounts:
if(self::lt($this->right,$this->left))
{
$t = $this->left;
$this->left = $this->right;
$this->right = $t;
}
}

// Some private utility functions
protected static final function leap($year)
{
return !(($year&3 || !($year%100)) && $year%400);
}

protected static final function dinm($year, $month)
{
static $months = array(null,31,28,31,30,31,30,31,31,30,31,30,31);
if($month==2)
{
return self::leap($year) ? 29 : 28;
}
return $months[$month];
}

// 146th January is really 26th May
// (except in a leap year, when it's only the 25th).
// TODO:
// I'd like to speed this up by rolling back and forth
// by full years when possible.
// Anyone care to take a punt on writing this?
protected static final function fixdate(&$date)
{
while($date['d']<1)
{
--$date['m'];
if($date['m']==0)
{
$date['m'] = 12;
--$date['y'];
}
$date['d'] += self::dinm($date['y'], $date['m']);
}

while($date['d']>($dinm = self::dinm($date['y'], $date['m'])))
{
$date['d'] -= $dinm;
++$date['m'];
if($date['m']==13)
{
$date['m'] = 1;
++$date['y'];
}
}
}

}

// Examples:
$start_date = array('y'=>1993, 'm'=>9, 'd'=>1);
$September_that_never_ended = new date_interval(null, $start_date);
echo "September ".$September_that_never_ended->length().", 1993";

// Note that the resulting interval is 1000001 days long;
// today plus the million days following.
$one_million_days_from_now = new date_interval();
$one_million_days_from_now->widen_right(1000000);
echo join('-', $one_million_days_from_now->right());

$date1 = array('y'=>1973, 'm'=>5, 'd'=>14);
$date2 = array('y'=>1986, 'm'=>1, 'd'=>26);
$date3 = array('y'=>1980, 'm'=>8, 'd'=>31);
$date4 = array('y'=>2005, 'm'=>1, 'd'=>1);
$interval1 = new date_interval($date1, $date2);
$interval2 = new date_interval($date3, $date4);
echo date_interval::common_interval($interval1, $interval2);

[Weedpacket]

Hm. Attaching the file might help a bit.
Yeah, yeah. .txt extension.

[mrhappiness]

function leap_year($year) {
if ($year % 4)
return false;
if (($year % 100) or !($year % 400))
return true;
return false;
}

function my_fixdate(&$date) {
//array with days per month
static $dim = array(1 => 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31);
//days in year
static $diy = array(1 => 365, 334, 304, 273, 243, 212, 181, 151, 120, 90, 59, 31);
//check if current year is leap year
$leap = 1;
if (leap_year($date['y'])) {
//correct february
$dim[2] = 29;
//days in year
$diy = array(1 => 366, 335, 305, 274, 244, 213, 182, 152, 121, 91, 60, 31);
$leap = 4;
}
//check for valid date
if ($date['d'] <= $dim[$date['m']])
return;
//date is not valid, go correct it
//check if correct date is in current year
while ($date['d'] > $diy[$date['m']]) {
//no => increment year and check again
$date['y']++;
$date['d'] -= $diy[$date['m']];
$date['m'] = 1;
//check if current year is leap year
if (($leap-- % 4) and leap_year($date['y'])) {
//correct february
$dim[2] = 29;
//days in year
$diy = array(1 => 366, 335, 305, 274, 244, 213, 182, 152, 121, 91, 60, 31);
$leap = 4;
} else {
//correct february
$dim[2] = 28;
//days in year
$diy = array(1 => 365, 334, 304, 273, 243, 212, 181, 151, 120, 90, 59, 31);
}
}
//correct date is in current year
//find correct month and day
while ($date['d'] > $dim[$date['m']])
$date['d'] -= $dim[$date['m']++];
} it's a little bit faster if the correct date is within the year specified and it's faster if it's more than one year later (2003-12-578 = 2005-6-30)

if it's just one year later the speed is almost equal

[Weedpacket]

if ($date['d'] <= $dim[$date['m']])
return; $date['d'] might be negative. Your implementation also duplicates functionality that appears elsewhere; also, with your code, May 10 2005 plus 233 days is December 29 2005, but plus 234 days it's January 1 2006.

Blinding speed isn't as important as maintainability and correctness.

[planetsim]

weedpacket i havent had a chance to play around with it, but damn thats the best documented code ive seen in a long time :D

You may want to mention that you will require PHP 5 to run this.

[Weedpacket]

Originally posted by planetsim
weedpacket i havent had a chance to play around with it, but damn thats the best documented code ive seen in a long time :DSnow Crash (http://www.nealstephenson.com/)
All technical devices require documentation of a sort, but this stuff can only be written by the techies who are doing the actual product development, and they absolutely hate it, always put the dox question off to the very last minute. Then they type up some material on a word procesor, run it off on the laser printer, send the departmental secretary out for a cheap binder, and that's that.

You may want to mention that you will require PHP 5 to run this. Well, I kinda hoped that the line public function __construct($left=null, $right=null) was enough of a hint.

[Weedpacket]

Updated the file to fix an error; good thing no-one had downloaded it yet (despite it being commented on twice).

[bubblenut]

Cool, and damned handy as well. I can think of lots of uses for it ... and there's sooo much that it can do. Just as a side note, there seems to be no Interval PEAR package at the moment.

There seems to be a typo in the interval constructor. I'm guessing that
$t = $left;
$left = $right;
$right = $left;
should be$t = $left;
$left = $right;
$right = $t;

[Weedpacket]

Originally posted by bubblenut
There seems to be a typo in the interval constructor.Italian whiteware, that was the error I thought I fixed (everywhere except in the copy I prepped for upload, it seems)!

[Weedpacket]

Thought I'd revisit this. When fixing the date (so that, e.g., 1-1-1000000 was corrected to 2738-11-28; a quick nod to Frederick Pohl, there for "Day Million") the original code could only "wind the dials" back and forth by one month at a time. I wanted to do it in steps of full years when feasible.

I happened to have a use for this code, so I brought it up and saw the TODO. Saw how to do it, too. And did it. And saw that rolling by four centuries at a pop could save a bit of processing, too. (Why four? Because the Gregorian calendar has exactly 400*365+100-3 days in that period.)

With the Day One Million test above, the fixdate() method is now about a hundred times faster.



// 146th January is really 26th May
// (except in a leap year, when it's only the 25th).
//
// Note: this uses the so-called "proleptic" Gregorian calendar,
// i.e., it will use the Gregorian calendar even for dates prior
// to the calendar's adoption. The proleptic calendar also uses
// year 0 and negative years.
protected static final function fixdate(&$date)
{
// Rolling by steps of 400 Gregorian years
while($date['d']>146097)
{
$date['d']-=146097;
$date['y']+=400;
}
while($date['d']<-146097)
{
$date['d']+=146097;
$date['y']-=400;
}

// Rolling by steps of one year
while($date['d']<-364)
{
$date['d'] += self::leap(--$date['y'])?366:365;
}
while($date['d']>($diny = self::leap($date['y']+1)?366:365))
{
$date['d'] -= $diny;
++$date['y'];
}

// Rolling by month
while($date['d']<1)
{
if(--$date['m']==0)
{
$date['m'] = 12;
--$date['y'];
}
$date['d'] += self::dinm($date['y'], $date['m']);
}
while($date['d']>($dinm = self::dinm($date['y'], $date['m'])))
{
$date['d'] -= $dinm;
if(++$date['m']==13)
{
$date['m'] = 1;
++$date['y'];
}
}
}