Merge branch 'master' of github.com:systemed/potlatch2
[potlatch2.git] / net / systemeD / halcyon / connection / bboxes / Interval.as
1 package net.systemeD.halcyon.connection.bboxes {
2         
3         public class Interval {
4
5                 public var _min:Number;
6                 public var _max:Number;
7                 
8                 function Interval(min:Number,max:Number):void {
9                         _min=min;
10                         _max=max;
11                 }
12
13                 public function contains(x:Number):Boolean { return (x>=_min && x<_max); }
14                 public function get valid():Boolean { return (_max>_min); }
15                 public function get size():Number { return (_max-_min); }
16
17                 public function intersects(other:Interval):Boolean { return (_max>other._min && _min<other._max); }
18                 public function equals(other:Interval):Boolean { return (_min==other._min && _max==other._max); }
19                 public function union(other:Interval):Interval { return new Interval(Math.min(_min,other._min), Math.max(_max,other._max)); }
20                 public function intersection(other:Interval):Interval { return new Interval(Math.max(_min,other._min), Math.min(_max,other._max)); }
21                 
22                 public function toString():String { return ("Interval["+_min+","+_max+"]"); }
23
24                 // Merge an array of possibly overlapping intervals into a set of disjoint intervals.
25                 public static function merge(intervals:Array):Array {
26                         intervals.sort(compareMinimum);
27                         var memo:Array=[];
28                         for each (var elem:Interval in intervals) {
29                                 var last:Interval=memo.pop();
30                                 if (!last) { 
31                                         memo=[elem];
32                                 } else if (last.intersects(elem)) {
33                                         memo.push(last.union(elem));
34                                 } else {
35                                         memo.push(last);
36                                         memo.push(elem);
37                                 }
38                         }
39                         return memo;
40                 }
41
42                 // Returns the largest empty interval in the given set of intervals.
43                 
44                 public static function largestEmpty(intervals:Array):Interval {
45                         var gaps:Array=[];
46                         intervals=merge(intervals);
47                         for (var i:uint=0; i<=intervals.length-2; i++) {
48                                 gaps.push(new Interval(intervals[i]._max, intervals[i+1]._min));
49                         }
50                         gaps.sort(compareSize);
51                         return gaps[gaps.length-1];
52                 }
53
54                 // Comparison methods for sorting
55
56                 private static function compareMinimum(a:Interval, b:Interval):int {
57                         if (a._min>b._min) { return 1; }
58                         if (a._min<b._min) { return -1; }
59                         return 0;
60                 }
61
62                 private static function compareSize(a:Interval, b:Interval):int {
63                         if (a.size>b.size) { return 1; }
64                         if (a.size<b.size) { return -1; }
65                         return 0;
66                 }
67         }
68 }