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 }