treemap.rs

// https://www.win.tue.nl/~vanwijk/stm.pdf
use treemap::TreeMap;
mod treemap {
	use serde::Serialize;
	use super::AnalyzedAddon;

	#[derive(Debug, Clone, Serialize)]
	pub(super) struct MappedGMAFile {
		#[serde(flatten)]
		pub(super) inner: AnalyzedAddon,
		x: f64,
		y: f64,
		w: f64,
		h: f64
	}

	#[derive(Debug, Clone)]
	pub(super) struct TreeMap {
		pub(super) squares: Vec<MappedGMAFile>,
		gmas: Vec<Option<AnalyzedAddon>>,
		x: f64,
		y: f64,
		w: f64,
		h: f64
	}
	impl TreeMap {
		pub(super) fn new(gmas: Vec<Option<AnalyzedAddon>>, w: f64, h: f64, total_size: f64) -> Self {
			let mut treemap = Self {
				gmas,
				squares: Vec::new(),
				x: 0.,
				y: 0.,
				w,
				h,
			};

			let mut scaled: Vec<f64> = treemap.gmas.iter().map(|x| ((x.as_ref().unwrap().gma.size as f64) * h * w) / total_size).collect();
			treemap.squarify(&mut scaled, &mut Vec::new(), treemap.min_width().0);
			treemap
		}

		fn squarify(&mut self, squares: &mut Vec<f64>, row: &mut Vec<f64>, w: f64) {
			if squares.len() == 1 {
				return self.layout_last_row(squares, row, w);
			}

			let mut row_with_child: Vec<f64> = row.clone();
			row_with_child.push(squares[0]);

			if row.is_empty() || self.worst_ratio(row, w) >= self.worst_ratio(&row_with_child, w) {
				squares.remove(0);
				return self.squarify(squares, &mut row_with_child, w);
			}

			self.layout_row(row, w, self.min_width().1);
			return self.squarify(squares, &mut Vec::new(), self.min_width().0);
		}

		fn worst_ratio(&self, row: &Vec<f64>, w: f64) -> f64 {
			let mut sum: f64 = 0.;
			let mut max: f64 = 0.;
			let mut min: f64 = f64::MAX;
			for row in row {
				sum = sum + *row;
				max = max.max(*row);
				min = min.min(*row);
			}

			let sumsum = sum.powi(2);
			let ww = w.powi(2);

			f64::max(
				(ww * max) / sumsum,
				sumsum / (ww * min)
			)
		}

		fn min_width(&self) -> (f64, bool) {
			if self.h.powi(2) > self.w.powi(2) {
				(self.w, false)
			} else {
				(self.h, true)
			}
		}

		fn layout_row(&mut self, row: &mut Vec<f64>, w: f64, vertical: bool) {
			let row_height = row.iter().sum::<f64>() / w;

			for row in row {
				let row_width = *row / row_height;
				self.squares.push(if vertical {
					let data = MappedGMAFile {
						x: self.x,
						y: self.y,
						w: row_height,
						h: row_width,
						inner: self.gmas[self.squares.len()].take().unwrap(),
					};
					self.y = self.y + row_width;
					data
				} else {
					let data = MappedGMAFile {
						x: self.x,
						y: self.y,
						w: row_width,
						h: row_height,
						inner: self.gmas[self.squares.len()].take().unwrap(),
					};
					self.x = self.x + row_width;
					data
				});
			}

			if vertical {
				self.x = self.x + row_height;
				self.y = self.y - w;
				self.w = self.w - row_height;
			} else {
				self.x = self.x - w;
				self.y = self.y + row_height;
				self.h = self.h - row_height;
			}
		}

		fn layout_last_row(&mut self, squares: &mut Vec<f64>, row: &mut Vec<f64>, w: f64) {
			let vertical = self.min_width().1;
			self.layout_row(row, w, vertical);
			self.layout_row(squares, w, vertical);
		}
	}
}