Merge branch 'master' into history
[potlatch2.git] / net / systemeD / halcyon / connection / bboxes / FetchSet.as
1 package net.systemeD.halcyon.connection.bboxes {
2         
3         public class FetchSet {
4
5                 private var existing:Array;
6                 private static const MAX_PARTITION_TRIALS:uint = 100;
7
8                 function FetchSet():void {
9                         existing=[];
10                 }
11
12                 public function getBoxes(bbox:Box,maxBoxes:uint):Array {
13                         var bits:Array=Box.merge(bbox.subtractAll(existing));
14                         var toFetch:Array=optimalPart(maxBoxes,bits);
15                         return toFetch;
16                 }
17                 
18                 public function add(bbox:Box):void {
19                         existing.push(bbox);
20                         existing=existing.filter(function(item:Box,i:uint,arr:Array):Boolean {
21                                 return !bbox.encloses(item);
22                         });
23                 }
24
25                 public function get size():int {
26                         return existing.length;
27                 }
28
29                 private function rgString(prefix:Array, numSets:int, numElts:int, numTries:int):Array {
30                         if (numElts==0) return [prefix];
31                         var maxDigit:Number=Math.min(maxValue(prefix)+1,numSets-1);
32                         var result:Array=[];
33                         for (var digit:uint=0; digit<=maxDigit; digit++) {
34                                 if (numTries>0) {
35                                         var rv:Array=rgString(prefix.concat([digit]),numSets,numElts-1,numTries);
36                                         numTries-=rv.length;
37                                         result=result.concat(rv);
38                                 }
39                         }
40                         return result;
41                 }
42
43                 // select only the partitions of the set which have a certain size, or smaller
44
45                 private function partsOfSize(n:int,set:Array):Array {
46                         if (set.length==0) { return []; }
47                         return (rgString([0], n, set.length-1, MAX_PARTITION_TRIALS).map(
48                                 function(rgs:Array,index:uint,array:Array):* {
49                                         var ary:Array=[];
50                                         for (var j:uint=0; j<=maxValue(rgs); j++) ary.push([]);
51                                         for (var i:uint=0; i<rgs.length; i++) ary[rgs[i]].push(set[i]);
52                                         return ary;
53                                 }));
54                 }
55                 
56                 private function maxValue(a:Array):Number {
57                         var m:Number=Number.NEGATIVE_INFINITY;
58                         for each (var n:Number in a) m=Math.max(m,n);
59                         return m;
60                 }
61
62                 // find the optimal partition - the one which requests the smallest amount of extra space - 
63                 // given the set p of partitions
64
65                 private function optimalPart(n:int, set:Array):Array {
66                         var p:Array=partsOfSize(n,set);
67                         if (p.length==0) return [];
68                         var q:Array=p.sort(function(a:Array,b:Array):Number {
69                                 var aw:Number = wasteSize(a, set);
70                                 var bw:Number = wasteSize(b, set);
71                                 if (aw < bw) return -1;
72                                 else if (aw > bw) return 1;
73                                 else return 0;
74                         });
75                         return unionPartitions(q[0]);
76                 }
77
78                 private function wasteSize(boxes:Array, set:Array):Number {
79                         var waste:Number = 0;
80                         unionPartitions(boxes).forEach(function(b:Box,index:int,array:Array):void {
81                                 var included:Number = 0;
82                                 set.forEach(function(s:Box,index:int,array:Array):void {
83                                         s = s.intersection(b);
84                                         if (s.valid) included += s.size;
85                                 });
86                                 waste += b.size - included;
87                         });
88                         return waste;
89                 }
90
91                 private function unionPartitions(a:Array):Array {
92                         return a.map(function(bs:Array,index:int,array:Array):Box {
93                                 var box:Box = bs[0];
94                                 bs.forEach(function(b:Box,index:int,array:Array):void {
95                                         box=box.union(b);
96                                 });
97                                 return box;
98                         });
99                 }
100                 
101                 public function toString():String {
102                         return "["+existing.join(",")+"]";
103                 }
104
105         }
106 }