1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

extern crate num_cpus;

use data::{Point, Region, Square};
use std::thread;



static mut THREAD_LIMIT: i64 = 0;
fn find_thread_limit(bucket_size:i64) -> i64{
	let thread = num_cpus::get() as i64;
	let limit = bucket_size / (thread * 10);
	limit
}

pub fn use_bucket(square:&mut Square, mother_bucket: Vec<Point>) -> (Vec<Point>, Vec<Point>){
	let mut inside = vec![];
	let mut outside = vec![];
	for p in mother_bucket{
		if square.is_inside(&p) {
			inside.push(p);
		}else{
			outside.push(p);
		}
	}
	(inside , outside)
}

pub fn split_region(square :&Square) -> (Square, Square, Square, Square) {
	let nw = Square::new(square.x, square.y + square.lenght / 2, square.lenght / 2);
	let ne = Square::new(square.x + square.lenght / 2, square.y + square.lenght / 2, square.lenght / 2);
	let se = Square::new(square.x + square.lenght / 2, square.y, square.lenght / 2);
	let sw = Square::new(square.x, square.y, square.lenght / 2);
	(nw, ne , sw, se)
}

fn assign(mut current_square :Square, point:Option<Point>, region:Option<Region>) -> Square {
	if region.is_some() {
		current_square.region = Some(Box::new(region.unwrap()));
	}else{
		current_square.point = point;
	}
	current_square
}

fn compute_assign(square:Square, bucket :Vec<Point>) -> Square {
	let (square, nw_point, nw_region) = compute(square, bucket);
	let square = assign(square, nw_point, nw_region);
	square
}

fn create_region_no_thread(nw:Square,nw_bucket:Vec<Point>, ne:Square,ne_bucket:Vec<Point>, sw:Square,sw_bucket:Vec<Point>, se:Square,se_bucket:Vec<Point>) -> Region {
	let nw = compute_assign(nw, nw_bucket);
	let ne = compute_assign(ne, ne_bucket);
	let sw = compute_assign(sw, sw_bucket);
	let se = compute_assign(se, se_bucket);
	
	Region::new(nw, ne, sw, se)
}

fn create_region_thread(nw:Square,nw_bucket:Vec<Point>, ne:Square,ne_bucket:Vec<Point>, sw:Square,sw_bucket:Vec<Point>, se:Square,se_bucket:Vec<Point>) -> Region {
	
	let nw_t = thread::spawn(move || {
	    compute_assign(nw, nw_bucket)
	});
	let ne_t = thread::spawn(move || {
	    compute_assign(ne, ne_bucket)
	});
	let sw_t = thread::spawn(move || {
	    compute_assign(sw, sw_bucket)
	});
	let se_t = thread::spawn(move || {
	    compute_assign(se, se_bucket)
	});
	
	Region::new(nw_t.join().unwrap(),
		 ne_t.join().unwrap(),
		 sw_t.join().unwrap(),
		 se_t.join().unwrap())
}



fn create_region(self_square :&Square, bucket :Vec<Point>) -> Region {
	let size = bucket.len() as i64;
	
	let (mut nw, mut ne, mut sw, mut se) = split_region(&self_square);
	let (nw_bucket, current_bucket) = use_bucket(&mut nw, bucket);
	let (ne_bucket, current_bucket) = use_bucket(&mut ne, current_bucket);
	let (sw_bucket, current_bucket) = use_bucket(&mut sw, current_bucket);
	let (se_bucket, _) = use_bucket(&mut se, current_bucket);
	
	if size > unsafe{THREAD_LIMIT} {
		create_region_thread(nw,nw_bucket, ne,ne_bucket, sw,sw_bucket, se,se_bucket)
	}else{
		create_region_no_thread(nw,nw_bucket, ne,ne_bucket, sw,sw_bucket, se,se_bucket)
	}
}


fn compute(mut self_square :Square, mut bucket:Vec<Point>) -> (Square, Option<Point>, Option<Region>){
	self_square.weight = bucket.len() as i64;
	if bucket.len() == 0 {
		return (self_square, None, None)
	}
	if bucket.len() == 1 {
		let point = bucket.pop().unwrap();
		return (self_square, Some(point), None)
	}
	
	let region = create_region(&mut self_square, bucket);
	self_square.region = Some(Box::new(region));

	(self_square, None, None)
}


pub struct Tree;
impl Tree{
	
	pub fn compute_root(&self, mut square: Square, root_bucket :Vec<Point>) -> Square {
		let bucket_size = root_bucket.len() as i64;
		square.weight = bucket_size;
		unsafe {
			THREAD_LIMIT = find_thread_limit(bucket_size)
			}
		let (square, _, _) = compute(square, root_bucket);
		square
	}
}