2021-01-12 01:19:40 +01:00
|
|
|
use crate::city;
|
2021-02-11 12:00:55 +01:00
|
|
|
use crate::db::{SqliteLayoutDB, SavedLayout, MergeLowerBound, LayoutDB};
|
2021-02-15 22:59:13 +01:00
|
|
|
use crate::city::{City, House, HouseDistances};
|
2021-01-12 01:19:40 +01:00
|
|
|
use itertools::Itertools;
|
2021-01-13 00:56:28 +01:00
|
|
|
use itertools::iproduct;
|
2021-01-13 21:45:50 +01:00
|
|
|
use std::collections::{VecDeque, HashMap};
|
2021-01-13 00:03:09 +01:00
|
|
|
use std::collections::vec_deque::Iter;
|
2021-01-12 01:19:40 +01:00
|
|
|
|
2021-01-13 21:45:50 +01:00
|
|
|
struct LeftState<'a> {
|
|
|
|
layout: &'a SavedLayout,
|
|
|
|
sorted_houses: Vec<House>,
|
2021-02-11 11:26:37 +01:00
|
|
|
line: LeftLine<'a>
|
2021-01-13 21:45:50 +01:00
|
|
|
}
|
|
|
|
|
|
|
|
struct RightState<'a> {
|
|
|
|
layout: &'a SavedLayout,
|
2021-02-11 11:26:37 +01:00
|
|
|
line: RightLine<'a>
|
2021-01-13 21:45:50 +01:00
|
|
|
}
|
|
|
|
|
|
|
|
pub struct CompatibilityCache {
|
2021-01-13 22:32:02 +01:00
|
|
|
map: HashMap<(usize, usize, usize, usize, bool), bool>
|
2021-01-13 21:45:50 +01:00
|
|
|
}
|
|
|
|
|
|
|
|
impl CompatibilityCache {
|
|
|
|
pub fn new() -> CompatibilityCache {
|
|
|
|
CompatibilityCache {
|
|
|
|
map: HashMap::new()
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2021-01-13 22:32:02 +01:00
|
|
|
pub fn is_compatible(&self, left_layout: &SavedLayout, right_layout: &SavedLayout, left_update_index: usize, right_update_index: usize, y_axis: bool) -> Option<&bool> {
|
|
|
|
self.map.get(&(left_layout.id(), right_layout.id(), left_update_index, right_update_index, y_axis))
|
2021-01-13 21:45:50 +01:00
|
|
|
}
|
2021-01-13 04:11:33 +01:00
|
|
|
|
2021-01-13 22:32:02 +01:00
|
|
|
pub fn set_compatible(&mut self, left_layout: &SavedLayout, right_layout: &SavedLayout, left_update_index: usize, right_update_index: usize, y_axis: bool, compatible: bool) {
|
|
|
|
self.map.insert((left_layout.id(), right_layout.id(), left_update_index, right_update_index, y_axis), compatible);
|
2021-01-13 21:45:50 +01:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2021-02-15 17:29:43 +01:00
|
|
|
fn choose_layouts<TDB: LayoutDB>(db: &TDB, city: &City, top_layout_count: usize) -> Vec<SavedLayout> {
|
|
|
|
// We do a secondary sort by ID to make the result stable in case of ties
|
|
|
|
let top_deduplicated_layouts: Vec<SavedLayout> = db.layouts().iter()
|
|
|
|
.sorted_by_key(|x| (city::get_price(&city, x.houses()), x.id()))
|
|
|
|
.unique_by(|x| x.houses().iter().sorted_by_key(|x| (x.x, x.y)).collect::<Vec<_>>())
|
|
|
|
.map(|layout| (*layout).clone())
|
|
|
|
.take(top_layout_count)
|
|
|
|
.collect();
|
|
|
|
|
|
|
|
top_deduplicated_layouts
|
|
|
|
}
|
|
|
|
|
2021-02-12 04:01:28 +01:00
|
|
|
pub fn iterate_combines<TDB: LayoutDB>(mut db: &mut TDB, top_layout_count: usize, city: &City, mut cache: &mut CompatibilityCache, print_progress: bool) {
|
2021-02-21 00:00:42 +01:00
|
|
|
let mut no_improvements_in_a_row = 0;
|
2021-02-12 04:01:28 +01:00
|
|
|
if print_progress { eprintln!("Building a transposed city..."); }
|
|
|
|
let transposed_city = transpose_city(&city);
|
|
|
|
if print_progress { eprintln!("Finished building a transposed city"); }
|
|
|
|
|
|
|
|
loop {
|
2021-02-21 00:00:42 +01:00
|
|
|
if no_improvements_in_a_row == 2 { break; }
|
2021-02-12 04:01:28 +01:00
|
|
|
if print_progress { eprintln!("Starting to combine {} top houses DB; vertical cuts", top_layout_count); }
|
2021-02-15 17:29:43 +01:00
|
|
|
|
2021-02-21 00:00:42 +01:00
|
|
|
{
|
|
|
|
let chosen_layouts = choose_layouts(db, &city, top_layout_count);
|
|
|
|
if print_progress { eprintln!("Building right distances..."); }
|
|
|
|
let right_distances = city::build_distances_right(&city);
|
|
|
|
if print_progress { eprintln!("Finished building right distances"); }
|
|
|
|
if create_new_best_combination(&city, &chosen_layouts, &chosen_layouts, db, &mut cache, &right_distances, false, print_progress) {
|
|
|
|
no_improvements_in_a_row = 0;
|
|
|
|
} else {
|
|
|
|
no_improvements_in_a_row += 1;
|
|
|
|
}
|
|
|
|
if print_progress { eprintln!("Finished vertical cuts, improvement: {}", no_improvements_in_a_row == 0); }
|
2021-02-12 04:01:28 +01:00
|
|
|
}
|
|
|
|
|
2021-02-21 00:00:42 +01:00
|
|
|
if no_improvements_in_a_row == 2 { break; }
|
|
|
|
|
|
|
|
{
|
|
|
|
let chosen_layouts = choose_layouts(db, &city, top_layout_count);
|
|
|
|
let transposed_chosen_layouts: Vec<_> = chosen_layouts.iter().map(|x| transpose_saved_layout(x)).collect();
|
|
|
|
if print_progress { eprintln!("Building right distances (transposed)..."); }
|
|
|
|
let right_distances_transposed = city::build_distances_right(&transposed_city);
|
|
|
|
if print_progress { eprintln!("Finished building right distances"); }
|
|
|
|
|
|
|
|
if print_progress { eprintln!("Starting to combine {} top houses DB; horizontal cuts", top_layout_count); }
|
|
|
|
if create_new_best_combination(&transposed_city, &transposed_chosen_layouts, &transposed_chosen_layouts, db, &mut cache, &right_distances_transposed, true, print_progress) {
|
|
|
|
no_improvements_in_a_row = 0;
|
|
|
|
} else {
|
|
|
|
no_improvements_in_a_row += 1;
|
|
|
|
}
|
|
|
|
if print_progress { eprintln!("Finished horizontal cuts, improvement: {}", no_improvements_in_a_row == 0); }
|
2021-02-12 04:01:28 +01:00
|
|
|
}
|
|
|
|
|
2021-02-21 00:00:42 +01:00
|
|
|
if no_improvements_in_a_row == 2 { break; }
|
2021-02-12 04:01:28 +01:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
fn transpose_city(city: &City) -> City {
|
|
|
|
let mut transposed_prices = vec![0u16; city.width() * city.height()];
|
|
|
|
for y in 0..city.height() {
|
|
|
|
for x in 0..city.width() {
|
|
|
|
// Sorry, cache! Not worth optimizing with blocks,
|
|
|
|
// this is not going to be ran often.
|
|
|
|
transposed_prices[x * city.height() + y] = city.get_price_xy(x, y);
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
City::new(transposed_prices, city.height(), city.width())
|
|
|
|
}
|
|
|
|
|
|
|
|
fn transpose_saved_layout(layout: &SavedLayout) -> SavedLayout {
|
|
|
|
let mut transposed = Vec::new();
|
|
|
|
for house in layout.houses() {
|
|
|
|
transposed.push(House::new(house.y, house.x));
|
|
|
|
}
|
|
|
|
|
|
|
|
SavedLayout::new(layout.id(), transposed)
|
|
|
|
}
|
|
|
|
|
2021-02-15 22:59:13 +01:00
|
|
|
pub fn create_new_best_combination<TDB: LayoutDB>(city: &City, left_layouts: &Vec<SavedLayout>, right_layouts: &Vec<SavedLayout>, db: &mut TDB, cache: &mut CompatibilityCache, right_distances: &HouseDistances, transposed: bool, print_progress: bool) -> bool {
|
2021-01-17 20:27:42 +01:00
|
|
|
let mut best_price = left_layouts.iter().chain(right_layouts.iter())
|
|
|
|
.map(|layout| city::get_price(&city, layout.houses()))
|
|
|
|
.min();
|
|
|
|
|
2021-01-13 21:45:50 +01:00
|
|
|
let mut improved = false;
|
2021-01-13 00:03:09 +01:00
|
|
|
|
|
|
|
let mut lefts = Vec::new();
|
|
|
|
let mut rights = Vec::new();
|
|
|
|
|
2021-01-13 21:45:50 +01:00
|
|
|
for left_layout in left_layouts {
|
2021-01-17 20:27:42 +01:00
|
|
|
// We make sure that there is at least one other layout we want to compare this one with
|
|
|
|
// to avoid unnecessary house updates
|
|
|
|
let mut needed = false;
|
|
|
|
for right_layout in right_layouts {
|
|
|
|
if let Some(bound) = db.get_merge_lower_bound(left_layout, right_layout, transposed) {
|
|
|
|
if bound < best_price.expect("No best price set while lower bounds exist") {
|
|
|
|
needed = true;
|
|
|
|
break;
|
|
|
|
}
|
|
|
|
} else {
|
|
|
|
needed = true;
|
|
|
|
break;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
if !needed {
|
|
|
|
continue;
|
|
|
|
}
|
|
|
|
|
2021-01-13 21:45:50 +01:00
|
|
|
// Sorted in reverse so we can remove from the end
|
|
|
|
let sorted_houses: Vec<_> = left_layout.houses().iter().sorted_by(|h1, h2| h2.x.cmp(&h1.x)).map(|x| *x).collect();
|
|
|
|
|
|
|
|
lefts.push(LeftState {
|
|
|
|
layout: &left_layout,
|
|
|
|
sorted_houses,
|
2021-02-11 11:26:37 +01:00
|
|
|
line: LeftLine::new(&city)
|
2021-01-13 21:45:50 +01:00
|
|
|
});
|
2021-01-13 00:03:09 +01:00
|
|
|
}
|
2021-01-12 01:19:40 +01:00
|
|
|
|
2021-01-13 21:45:50 +01:00
|
|
|
for right_layout in right_layouts {
|
2021-01-17 20:27:42 +01:00
|
|
|
// We make sure that there is at least one other layout we want to compare this one with
|
|
|
|
// to avoid unnecessary house updates
|
|
|
|
let mut needed = false;
|
|
|
|
for left_layout in left_layouts {
|
|
|
|
if let Some(bound) = db.get_merge_lower_bound(left_layout, right_layout, transposed) {
|
|
|
|
if bound < best_price.expect("No best price set while lower bounds exist") {
|
|
|
|
needed = true;
|
|
|
|
}
|
|
|
|
} else {
|
|
|
|
needed = true;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
if !needed {
|
|
|
|
continue;
|
|
|
|
}
|
|
|
|
|
2021-01-13 21:45:50 +01:00
|
|
|
let mut sorted_houses: Vec<_> = right_layout.houses().iter().sorted_by(|h1, h2| h2.x.cmp(&h1.x)).map(|x| *x).collect();
|
|
|
|
|
2021-02-11 11:26:37 +01:00
|
|
|
let mut line = RightLine::new(&city);
|
2021-01-13 00:03:09 +01:00
|
|
|
// Make sure that we include all houses initially
|
2021-01-13 21:45:50 +01:00
|
|
|
while let Some(house) = sorted_houses.pop() {
|
|
|
|
line.add_house(house, &city);
|
2021-01-13 00:03:09 +01:00
|
|
|
}
|
2021-01-13 21:45:50 +01:00
|
|
|
rights.push(RightState {
|
|
|
|
layout: right_layout,
|
|
|
|
line
|
|
|
|
});
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
|
|
|
|
2021-01-13 04:11:33 +01:00
|
|
|
let axis = if transposed { "y" } else { "x" };
|
|
|
|
|
2021-02-15 17:29:43 +01:00
|
|
|
// We construct a quick lookup table for skipped pairs of layouts - these are kept the same
|
|
|
|
// the entire run. We also assume that the best price does not get worse throughout the run.
|
|
|
|
let checked_pair_table: Vec<Vec<bool>> = lefts.iter()
|
|
|
|
.map(|left| rights.iter().map(|right| {
|
|
|
|
if left.layout.id() == right.layout.id() {
|
|
|
|
// We do not want to combine a layout with itself, it would never improve the score.
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
if let Some(bound) = db.get_merge_lower_bound(left.layout, right.layout, transposed) {
|
|
|
|
if bound >= best_price.expect("No best price set while lower bounds exist") {
|
|
|
|
// This combination can never attain a price better than the current best.
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
return true;
|
|
|
|
}).collect()).collect();
|
|
|
|
|
|
|
|
if print_progress {
|
|
|
|
let total_pairs = checked_pair_table.iter().flatten().count();
|
|
|
|
let checked_pairs = checked_pair_table.iter().flatten().filter(|x| **x).count();
|
|
|
|
eprintln!("Checking {}/{} layout pairs", checked_pairs, total_pairs);
|
|
|
|
}
|
|
|
|
|
2021-01-12 01:19:40 +01:00
|
|
|
// x is the last left coordinate, x+1 is right
|
2021-02-11 11:26:37 +01:00
|
|
|
for x in 0..city.width() {
|
2021-02-12 04:01:28 +01:00
|
|
|
if print_progress { eprintln!("Starting {} {}", axis, x); }
|
2021-01-13 01:43:23 +01:00
|
|
|
|
2021-01-12 01:19:40 +01:00
|
|
|
// Update the lines
|
2021-01-13 21:45:50 +01:00
|
|
|
for left in lefts.iter_mut() {
|
|
|
|
while let Some(house) = left.sorted_houses.last() {
|
2021-01-13 00:03:09 +01:00
|
|
|
if house.x == x {
|
2021-01-13 21:45:50 +01:00
|
|
|
left.line.add_house(*house, &city);
|
|
|
|
left.sorted_houses.pop();
|
2021-01-13 00:03:09 +01:00
|
|
|
} else {
|
|
|
|
break;
|
|
|
|
}
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
|
|
|
}
|
2021-01-13 00:03:09 +01:00
|
|
|
|
2021-01-13 00:56:28 +01:00
|
|
|
for right_line in rights.iter_mut() {
|
2021-01-13 21:45:50 +01:00
|
|
|
right_line.line.remove_houses(x, &city);
|
2021-01-13 00:03:09 +01:00
|
|
|
}
|
2021-01-12 01:19:40 +01:00
|
|
|
|
|
|
|
// Check compatibility of lines
|
|
|
|
if x == 0 {
|
|
|
|
// Cannot check this due to limitations in the implementation of LeftLine,
|
|
|
|
// it wouldn't be very interesting anyway.
|
|
|
|
continue;
|
|
|
|
}
|
|
|
|
|
2021-01-13 21:45:50 +01:00
|
|
|
let pairs = iproduct!(lefts.iter().enumerate(), rights.iter().enumerate())
|
2021-02-15 17:29:43 +01:00
|
|
|
.filter(|((left_i, _), (right_i, _))| checked_pair_table[*left_i as usize][*right_i as usize])
|
2021-01-13 21:45:50 +01:00
|
|
|
.map(|((left_i, left), (right_i, right))| (left, right, left.line.price + right.line.price, left_i, right_i))
|
|
|
|
.sorted_by(|(_, _, price1, _, _), (_, _, price2, _, _)| price1.cmp(&price2));
|
2021-01-13 00:56:28 +01:00
|
|
|
|
2021-01-13 00:03:09 +01:00
|
|
|
let mut compatibles = 0;
|
|
|
|
let mut incompatibles = 0;
|
2021-01-13 21:45:50 +01:00
|
|
|
let mut cache_hits = 0;
|
2021-02-15 17:29:43 +01:00
|
|
|
let mut best_incompatible_price = best_price;
|
2021-01-13 00:56:28 +01:00
|
|
|
for (left, right, price, left_i, right_i) in pairs {
|
2021-01-13 21:45:50 +01:00
|
|
|
if let Some(min_price) = best_price {
|
|
|
|
if price >= min_price {
|
|
|
|
break;
|
|
|
|
}
|
|
|
|
}
|
2021-01-13 22:32:02 +01:00
|
|
|
let compatible = match cache.is_compatible(left.layout, right.layout, left.line.last_update_x, right.line.last_update_x, transposed) {
|
2021-01-13 21:45:50 +01:00
|
|
|
None => {
|
2021-02-15 22:59:13 +01:00
|
|
|
let compatible = is_compatible(city, right_distances, &left.line, &right.line);
|
2021-01-13 22:32:02 +01:00
|
|
|
cache.set_compatible(left.layout, right.layout, left.line.last_update_x, right.line.last_update_x, transposed, compatible);
|
2021-01-13 21:45:50 +01:00
|
|
|
compatible
|
|
|
|
}
|
|
|
|
Some(compatible) => {
|
|
|
|
cache_hits += 1;
|
|
|
|
*compatible
|
|
|
|
}
|
|
|
|
};
|
|
|
|
if compatible {
|
2021-01-13 00:56:28 +01:00
|
|
|
if best_price.is_none() || price < best_price.unwrap() {
|
|
|
|
best_price = Some(price);
|
2021-02-12 04:01:28 +01:00
|
|
|
if print_progress {
|
|
|
|
eprintln!("{} - new best score, cut on {} {}, left {} - right {}, printing", price, axis, x, left_i, right_i);
|
|
|
|
println!("{} - new best score, cut on {} {}, left {} - right {}", price, axis, x, left_i, right_i);
|
|
|
|
}
|
2021-01-13 21:45:50 +01:00
|
|
|
let mut new_houses: Vec<_> = left.line.houses().copied().chain(right.line.houses().copied()).collect();
|
2021-01-13 02:00:32 +01:00
|
|
|
if transposed {
|
|
|
|
new_houses = transpose_layout(&new_houses);
|
2021-01-13 00:03:09 +01:00
|
|
|
}
|
2021-02-12 04:01:28 +01:00
|
|
|
if print_progress {
|
|
|
|
println!("{}", new_houses.len());
|
|
|
|
for house in &new_houses {
|
|
|
|
println!("{} {}", house.y, house.x);
|
|
|
|
}
|
2021-01-13 02:00:32 +01:00
|
|
|
}
|
|
|
|
|
|
|
|
// We only add best results to avoid overfilling the database with similar layouts
|
2021-01-13 21:45:50 +01:00
|
|
|
db.add_layout(&new_houses, false);
|
2021-01-13 04:11:33 +01:00
|
|
|
improved = true;
|
2021-01-13 00:03:09 +01:00
|
|
|
}
|
2021-01-13 00:56:28 +01:00
|
|
|
compatibles += 1;
|
|
|
|
|
|
|
|
// All other pairs would be more expensive
|
|
|
|
break;
|
|
|
|
} else {
|
2021-02-15 17:29:43 +01:00
|
|
|
best_incompatible_price = Some(best_incompatible_price.unwrap_or(u32::MAX).min(price));
|
2021-01-13 00:56:28 +01:00
|
|
|
incompatibles += 1;
|
2021-01-13 00:03:09 +01:00
|
|
|
}
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
2021-01-13 00:03:09 +01:00
|
|
|
|
2021-02-15 17:29:43 +01:00
|
|
|
if print_progress { eprintln!("{} incompatibles checked before {} compatible ({} cache hits) [{}-{}]", incompatibles, compatibles, cache_hits, best_incompatible_price.unwrap_or(u32::MAX), best_price.unwrap_or(u32::MAX)); }
|
2021-01-17 20:27:42 +01:00
|
|
|
}
|
|
|
|
|
|
|
|
if let Some(lowest_price) = best_price {
|
|
|
|
let mut new_bounds = Vec::new();
|
|
|
|
|
2021-02-15 17:29:43 +01:00
|
|
|
for left in &lefts {
|
|
|
|
for right in &rights {
|
|
|
|
new_bounds.push(MergeLowerBound::new(left.layout.id(), right.layout.id(), transposed, lowest_price));
|
2021-01-17 20:27:42 +01:00
|
|
|
}
|
|
|
|
}
|
|
|
|
db.add_merge_lower_bounds(new_bounds);
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
2021-01-13 04:11:33 +01:00
|
|
|
|
|
|
|
improved
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
|
|
|
|
2021-02-15 22:59:13 +01:00
|
|
|
fn is_compatible(city: &City, right_distances: &HouseDistances, left: &LeftLine, right: &RightLine) -> bool {
|
2021-02-11 11:26:37 +01:00
|
|
|
for y in 0..city.height() {
|
2021-01-12 01:19:40 +01:00
|
|
|
let max_left_covered_x = left.get_max_covered_x(y);
|
|
|
|
let min_right_covered_x = right.get_min_covered_x(y);
|
|
|
|
|
2021-02-15 22:59:13 +01:00
|
|
|
if let Some(right_house) = right_distances.get_closest_house_xy(max_left_covered_x, y) {
|
|
|
|
if right_house.x < min_right_covered_x {
|
2021-01-12 01:19:40 +01:00
|
|
|
return false;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
true
|
|
|
|
}
|
|
|
|
|
2021-02-11 11:26:37 +01:00
|
|
|
struct LeftLine<'a> {
|
2021-01-13 00:03:09 +01:00
|
|
|
covers: Vec<usize>,
|
|
|
|
houses: Vec<House>,
|
2021-01-13 02:00:32 +01:00
|
|
|
price: u32,
|
2021-02-11 11:26:37 +01:00
|
|
|
last_update_x: usize,
|
|
|
|
city: &'a City
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
|
|
|
|
2021-02-11 11:26:37 +01:00
|
|
|
struct RightLine<'a> {
|
2021-01-12 01:19:40 +01:00
|
|
|
covers: Vec<usize>,
|
2021-01-13 00:03:09 +01:00
|
|
|
houses: VecDeque<House>,
|
2021-01-13 02:00:32 +01:00
|
|
|
price: u32,
|
2021-02-11 11:26:37 +01:00
|
|
|
last_update_x: usize,
|
|
|
|
city: &'a City
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
|
|
|
|
2021-02-11 11:26:37 +01:00
|
|
|
impl<'a> LeftLine<'a> {
|
|
|
|
pub fn new(city: &'a City) -> Self {
|
2021-01-12 01:19:40 +01:00
|
|
|
// XXX: Careful, default of 0 includes covering first vertical line
|
2021-02-11 11:26:37 +01:00
|
|
|
let covers = vec![0; city.height()];
|
2021-01-13 00:03:09 +01:00
|
|
|
let houses = Vec::new();
|
2021-02-11 11:26:37 +01:00
|
|
|
LeftLine { covers, houses, price: 0, last_update_x: 0, city }
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
|
|
|
|
2021-01-13 00:03:09 +01:00
|
|
|
pub fn add_house(&mut self, house: House, city: &City) {
|
2021-02-11 11:26:37 +01:00
|
|
|
let range_rect = house.range_rectangle(city);
|
2021-01-12 01:19:40 +01:00
|
|
|
for y in range_rect.top..=range_rect.bottom {
|
|
|
|
// Should always be the max variant
|
|
|
|
self.covers[y] = self.covers[y].max(range_rect.right);
|
|
|
|
}
|
2021-01-13 00:03:09 +01:00
|
|
|
self.price += city.get_price(house) as u32;
|
|
|
|
self.houses.push(house);
|
2021-01-13 22:32:02 +01:00
|
|
|
self.last_update_x = house.x;
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
|
|
|
|
|
|
|
pub fn get_max_covered_x(&self, y: usize) -> usize {
|
|
|
|
self.covers[y]
|
|
|
|
}
|
2021-01-13 00:03:09 +01:00
|
|
|
|
|
|
|
pub fn get_side_price(&self) -> u32 {
|
|
|
|
self.price
|
|
|
|
}
|
|
|
|
|
|
|
|
pub fn houses(&self) -> std::slice::Iter<'_, House> {
|
|
|
|
self.houses.iter()
|
|
|
|
}
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
|
|
|
|
2021-02-11 11:26:37 +01:00
|
|
|
impl<'a> RightLine<'a> {
|
|
|
|
pub fn new(city: &'a City) -> Self {
|
|
|
|
let covers = vec![usize::MAX; city.height()];
|
2021-01-12 01:19:40 +01:00
|
|
|
let houses = VecDeque::new();
|
2021-02-11 11:26:37 +01:00
|
|
|
RightLine { covers, houses, price: 0, last_update_x: 0, city }
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
|
|
|
|
2021-01-13 00:03:09 +01:00
|
|
|
pub fn add_house(&mut self, house: House, city: &City) {
|
2021-01-12 01:19:40 +01:00
|
|
|
// Added houses have to always be ordered by x
|
2021-02-11 11:26:37 +01:00
|
|
|
let range_rect = house.range_rectangle(city);
|
2021-01-12 01:19:40 +01:00
|
|
|
for y in range_rect.top..=range_rect.bottom {
|
|
|
|
self.covers[y] = self.covers[y].min(range_rect.left);
|
|
|
|
}
|
|
|
|
|
|
|
|
self.houses.push_back(house);
|
2021-01-13 22:32:02 +01:00
|
|
|
self.price += city.get_price(house) as u32;
|
|
|
|
self.last_update_x = house.x;
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
|
|
|
|
2021-01-13 00:03:09 +01:00
|
|
|
pub fn remove_houses(&mut self, x: usize, city: &City) {
|
2021-01-12 01:19:40 +01:00
|
|
|
// Has to be called with x, x+1, x+2...
|
|
|
|
while let Some(house) = self.houses.front() {
|
|
|
|
if house.x == x {
|
|
|
|
let removed_house = self.houses.pop_front().unwrap();
|
2021-02-11 11:26:37 +01:00
|
|
|
let removed_rect = removed_house.range_rectangle(city);
|
2021-01-12 01:19:40 +01:00
|
|
|
|
|
|
|
// Remove the now-outdated distances around the removed house
|
|
|
|
for y in removed_rect.top..=removed_rect.bottom {
|
|
|
|
self.covers[y] = usize::MAX;
|
|
|
|
}
|
|
|
|
|
|
|
|
// Update distances around the removed house if the area of any houses
|
|
|
|
// intersects the removed area
|
|
|
|
for house in &self.houses {
|
2021-02-11 11:26:37 +01:00
|
|
|
let house_rect = house.range_rectangle(city);
|
2021-01-12 01:19:40 +01:00
|
|
|
let y_intersection = if removed_house.y < house.y {
|
|
|
|
house_rect.top..=removed_rect.bottom
|
|
|
|
} else {
|
|
|
|
removed_rect.top..=house_rect.bottom
|
|
|
|
};
|
|
|
|
|
|
|
|
for y in y_intersection {
|
|
|
|
self.covers[y] = self.covers[y].min(house_rect.left);
|
|
|
|
}
|
|
|
|
}
|
2021-01-13 00:03:09 +01:00
|
|
|
|
|
|
|
self.price -= city.get_price(removed_house) as u32;
|
2021-01-13 22:32:02 +01:00
|
|
|
self.last_update_x = removed_house.x;
|
2021-01-12 01:19:40 +01:00
|
|
|
} else {
|
|
|
|
break;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
pub fn get_min_covered_x(&self, y: usize) -> usize {
|
2021-02-11 11:26:37 +01:00
|
|
|
self.covers[y].min(self.city.width())
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
2021-01-13 00:03:09 +01:00
|
|
|
|
|
|
|
pub fn get_side_price(&self) -> u32 {
|
|
|
|
self.price
|
|
|
|
}
|
|
|
|
|
|
|
|
pub fn houses(&self) -> Iter<'_, House> {
|
|
|
|
self.houses.iter()
|
|
|
|
}
|
2021-01-12 01:19:40 +01:00
|
|
|
}
|
2021-01-13 02:00:32 +01:00
|
|
|
|
|
|
|
pub fn transpose_layout(houses: &Vec<House>) -> Vec<House> {
|
|
|
|
let mut transposed = Vec::new();
|
|
|
|
for house in houses {
|
|
|
|
transposed.push(House::new(house.y, house.x));
|
|
|
|
}
|
|
|
|
|
|
|
|
transposed
|
|
|
|
}
|