Another try of algorithm implbackend-3

Signed-off-by: Matthias Beyer <mail@beyermatthias.de>

1 files changed, 108 insertions, 80 deletions

diff --git a/src/backend.rs b/src/backend.rs
index be2edf3..7487c9e 100644
--- a/src/backend.rs
+++ b/src/backend.rs
@@ -43,107 +43,135 @@ impl LandscapeElement {
     fn increase_height(&mut self, h: f32) {
         self.water_level += h;
     }
+
+    fn decrease_height(&mut self, h: f32) {
+        self.water_level -= h;
+    }
+
+    // subtract enough from own water level to balance with other, returning what needs to be added
+    // to other
+    fn balance(&mut self, other_height: f32) -> f32 {
+        if other_height - self.current_height() > 1.0 {
+            self.water_level -= 1.0;
+            1.0
+        } else {
+            let diff = (other_height - self.current_height()) / 2.0;
+            self.water_level -= diff;
+            diff
+        }
+    }
 }
 
 fn rearrange(land: &mut [LandscapeElement]) {
     use float_cmp::*;
     log::trace!("Rearrange: {:?}", land);
 
-    if land.len() > 1 {
-        let max_idx = land.iter()
-            .enumerate()
-            .max_by(|(_i, a), (_j, b)| {
-                use std::cmp::Ordering;
-
-                if approx_eq!(f32, a.current_height(), b.current_height(), F32Margin::default()) {
-                    Ordering::Equal
+    let max_idx = land.iter()
+        .enumerate()
+        .max_by(|(_i, a), (_j, b)| {
+            use float_cmp::*;
+            use std::cmp::Ordering;
+
+            if approx_eq!(f32, a.current_height(), b.current_height(), F32Margin::default()) {
+                Ordering::Equal
+            } else {
+                if a.current_height() > b.current_height() {
+                    Ordering::Greater
                 } else {
-                    if a.current_height() > b.current_height() {
-                        Ordering::Greater
-                    } else {
-                        Ordering::Less
-                    }
+                    Ordering::Less
                 }
-            })
-            .map(|(idx, _)| idx);
-
-        let max_idx = match max_idx {
-            None => return, // no maximum, we're ready
-            Some(m) => m,
-        };
-        log::trace!("Maximum at index {}", max_idx);
+            }
+        })
+        .map(|(idx, _)| idx);
+
+    let max_idx = match max_idx {
+        None => return, // no maximum, we're ready
+        Some(m) => m,
+    };
+    log::trace!("maximum at index {}", max_idx);
+
+    if land.iter().all(|elem| approx_eq!(f32, elem.current_height(), land[max_idx].current_height(), F32Margin::default())) {
+        log::trace!("All elements equal high, returning");
+        return;
+    }
 
-        if land.iter().all(|elem| approx_eq!(f32, elem.current_height(), land[max_idx].current_height(), F32Margin::default())) {
+    let land_len = land.len();
+
+    let has_left_neighbor = max_idx != 0;
+    let has_right_neighbor = max_idx != land_len - 1;
+
+    match (has_left_neighbor, has_right_neighbor) {
+        (true, true) => {
+            log::trace!("Having both neighbors to recalculate");
+            recalc_left(max_idx, land, 0.5);
+            recalc_right(max_idx, land, 0.5);
+            land[max_idx].decrease_height(1.0);
+        },
+
+        (false, true) => {
+            log::trace!("Having right neighbor to recalculate");
+            recalc_right(max_idx, land, 1.0);
+            land[max_idx].decrease_height(1.0);
+        },
+
+        (true, false) => {
+            log::trace!("Having left neighbor to recalculate");
+            recalc_left(max_idx, land, 1.0);
+            land[max_idx].decrease_height(1.0);
+        },
+
+        (false, false) => {
+            // nothing to do
+            log::trace!("No neighbor to recalculate");
             return;
-        }
+        },
+    }
+    log::trace!("After rearrange step: {:?}", land);
 
-        {
-            let mut idx = max_idx as usize;
-            while idx >= 0 {
-                if idx == 0 {
-                    // no left element, cannot subtract 1
-                    log::trace!("No element on the left of 0, increasing at 0");
-                    land[idx].increase_height(0.5);
-                    break;
-                }
+    let land_len = land.len();
+    rearrange(&mut land[0..max_idx]);
+    rearrange(&mut land[max_idx..land_len]);
+}
 
-                match land.get(idx - 1) {
-                    None => {
-                        // no element on my left, I am the last element
-                        log::trace!("No element on the left of {}, increasing at {}", idx, idx);
-                        land[idx].increase_height(0.5);
-                        break;
-                    }
-
-                    Some(one_to_left) => if one_to_left.current_height() > land[idx].current_height() {
-                        // left to me is higher than I am, water stays with me
-                        log::trace!("Element on the left of {} is higher, increasing {}", idx, idx);
-                        land[idx].increase_height(0.5);
-                    } else {
-                        log::trace!("Element on the left of {} is lower, continue", idx);
-                        // continue iterating
-                    }
-                }
+fn recalc_left(max_idx: usize, land: &mut [LandscapeElement], inc: f32) {
+    let mut idx = max_idx;
+    let mut iter_height = land[idx].current_height();
+    loop {
+        if idx == 0 {
+            break;
+        }
 
-                if idx == 0 {
-                    break;
-                } else {
-                    idx -= 1;
-                }
-            }
+        if land[idx - 1].current_height() < iter_height {
+            iter_height = land[idx - 1].current_height();
+            idx -= 1;
+        } else {
+            break;
         }
+    }
 
-        {
-            let mut idx = max_idx as usize;
-            while idx < land.len() {
-                match land.get(idx + 1) {
-                    None => {
-                        // no element on my right, I am the last element
-                        log::trace!("No element on the right of {}, increasing at {}", idx, idx);
-                        land[idx].increase_height(0.5);
-                        break;
-                    }
-
-                    Some(one_to_right) => if one_to_right.current_height() > land[idx].current_height() {
-                        // right to me is higher than I am, water stays with me
-                        log::trace!("Element on the right of {} is higher, increasing {}", idx, idx + 1);
-                        land[idx].increase_height(0.5);
-                    } else {
-                        log::trace!("Element on the right of {} is lower, continue", idx);
-                        // continue iterating
-                    }
-                }
+    land[idx].increase_height(inc);
+}
 
-                idx += 1;
-            }
+fn recalc_right(max_idx: usize, land: &mut [LandscapeElement], inc: f32) {
+    let mut idx = max_idx;
+    let mut iter_height = land[idx].current_height();
+    loop {
+        if idx == land.len() - 1 {
+            break;
         }
 
-        let land_len = land.len();
-        rearrange(&mut land[0..max_idx]);
-        rearrange(&mut land[(max_idx)..(land_len - 1)]);
+        if land[idx + 1].current_height() < iter_height {
+            iter_height = land[idx + 1].current_height();
+            idx += 1;
+        } else {
+            break;
+        }
     }
+
+    land[idx].increase_height(inc);
 }
 
+
 #[cfg(test)]
 mod tests {
     use super::LandscapeElement as LE;