diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Cargo.lock | 7 | ||||
| -rw-r--r-- | Cargo.toml | 8 | ||||
| -rw-r--r-- | src/main.rs | 439 |
4 files changed, 455 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..ea8c4bf --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +/target diff --git a/Cargo.lock b/Cargo.lock new file mode 100644 index 0000000..63411b1 --- /dev/null +++ b/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "drone_db" +version = "0.1.0" diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..a8a6c04 --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,8 @@ +[package] +name = "drone_db" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 0000000..272366b --- /dev/null +++ b/src/main.rs @@ -0,0 +1,439 @@ +//! # Drone Database Exercise +//! +//! Implement the [Database] struct and methods to: +//! - Process incoming Radar Tracking Events. +//! - Query the state of Tracks at any given time. +//! - Persist via save/load methods so the state of DB can be restored. +//! +//! The `TESTING` environment variable controls what methods are tested +//! - `cargo test` : only tests [Database::process] and [Database::query] +//! - `env TESTING=iterator cargo test` : also tests [Database::query_iterator] +//! - `env TESTING=save_load cargo test` : also tests [Database::save] and [Database::load] +//! - `env TESTING=iterator,save_load cargo test` : tests everything +//! +//! You may only use what is provided by the [std]. +//! You may use unstable features if you wish. +//! +//! Usage characteristics for performance considerations: +//! - [Database::process] is called frequently. +//! - [Database::query] and [Database::query_iterator] methods called vary rarely. +//! +//! Hints: +//! - Some methods restrict the data representation more than others. +//! - `&'static str` implements `Into<Box<dyn std::error::Error>>>` +//! - `<Database as Default>::default` should by an empty Database. +//! +//! Bonus: Define and implement behaviour such that the current error +//! conditions for [Database::process] are no longer erroneous. + +use std::{ + cmp::Reverse, + collections::{BTreeMap, HashMap}, +}; + +type Res<T> = Result<T, Box<dyn std::error::Error>>; + +/// Timestamp +type UTC = u64; + +#[derive(Clone, Copy, Debug, Hash, Eq, PartialEq)] +pub struct TrackID(pub u32); + +#[derive(Clone, Debug, Eq, PartialEq)] +pub enum TrackEvent { + Ping { + id: TrackID, + time: UTC, + position: (i32, i32), + }, + Lost { + id: TrackID, + time: UTC, + }, +} + +#[derive(Default)] +struct TrackState { + lost: Option<UTC>, + positions: Vec<(UTC, (i32, i32))>, +} + +#[derive(Default)] +pub struct Database { + track_events: HashMap<TrackID, TrackState>, +} + +impl Database { + /// Errors Conditions (returns Err(...) when): + /// - Event with `time` before already processed event for the same track. + /// - Lost Event without first receiving a Ping for the same track. + /// - Multiple Lost Events for the same track. + /// - Ping Event after Lost already processed for the same track. + pub fn process(&mut self, event: TrackEvent) -> Res<()> { + match event { + TrackEvent::Ping { id, time, position } => { + self.track_events + .entry(id) + .and_modify(|state| { + state.positions.push((time, position)); + }) + .or_insert(TrackState { + positions: vec![(time, position)], + ..Default::default() + }); + } + TrackEvent::Lost { id, time } => { + self.track_events.entry(id).and_modify(|state| { + state.lost = Some(time); + }); + } + }; + + Ok(()) + } + + /// Considers only events occouring before or at `time`. Returns: + /// - The tracks not Lost before or at `time` + /// - The 5 most recent positions before or at `time` + /// - Most recent positions towards end of Vec. + pub fn query(&self, time: UTC) -> HashMap<TrackID, Vec<(i32, i32)>> { + println!("{time:?}"); + self.track_events + .iter() + .filter(|(_, state)| !state.lost.is_some_and(|t| t <= time)) + .filter(|(_, state)| state.positions.last().is_some_and(|(t, _)| t <= &time)) + .map(|(id, state)| { + ( + *id, + state + .positions + .iter() + .skip_while(|(t, _)| t > &time) + .take(5) + .map(|(_, pos)| pos) + .copied() + .collect(), + ) + }) + .collect() + } + + /// Same as [Self::query] except without allocation. + pub fn query_iterator(&self, time: UTC) -> impl Iterator<Item = (TrackID, &[(i32, i32)])> + '_ { + let _ = time; + if false { + return std::iter::empty(); // Provide concrete type to allow compile. + } + todo!("Implement Database::query_iterator") + } + + pub fn save(&self) -> Vec<u8> { + todo!("Implement Database::save") + } + + /// Assumes `saved` is output of `Self::save`. + /// Does not perform validation to ensure any invariants. + pub fn load(saved: &[u8]) -> Res<Database> { + let _ = saved; + todo!("Implement Database::load") + } +} + +fn main() {} + +#[cfg(test)] +mod test { + use super::*; + use TrackEvent::*; + + #[test] + fn empty_db() { + let mut db = DatabaseTester::default(); + db.extend(&[]); + db.expect_query(0, &[]) + } + + #[test] + fn ping() { + let mut db = DatabaseTester::default(); + db.extend(&[ + Ping { + id: TrackID(11), + time: 0, + position: (1, 1), + }, + Ping { + id: TrackID(22), + time: 1, + position: (2, 2), + }, + Ping { + id: TrackID(33), + time: 2, + position: (3, 3), + }, + Ping { + id: TrackID(44), + time: 3, + position: (4, 4), + }, + Ping { + id: TrackID(55), + time: 4, + position: (5, 5), + }, + Ping { + id: TrackID(66), + time: 6, + position: (6, 6), + }, + ]); + db.expect_query( + 8, + &[ + (TrackID(11), &[(1, 1)]), + (TrackID(22), &[(2, 2)]), + (TrackID(33), &[(3, 3)]), + (TrackID(44), &[(4, 4)]), + (TrackID(55), &[(5, 5)]), + (TrackID(66), &[(6, 6)]), + ], + ) + } + + #[test] + fn lost() { + let mut db = DatabaseTester::default(); + db.extend(&[ + Ping { + id: TrackID(11), + time: 0, + position: (1, 1), + }, + Lost { + id: TrackID(11), + time: 1, + }, + ]); + db.expect_query(2, &[]) + } + + #[test] + fn query_limit() { + let mut db = DatabaseTester::default(); + db.extend(&[ + Ping { + id: TrackID(1), + time: 0, + position: (0, 0), + }, + Ping { + id: TrackID(1), + time: 1, + position: (1, 1), + }, + ]); + db.expect_query(8, &[(TrackID(1), &[(0, 0), (1, 1)])]); + db.extend(&[ + Ping { + id: TrackID(1), + time: 2, + position: (2, 2), + }, + Ping { + id: TrackID(1), + time: 3, + position: (3, 3), + }, + Ping { + id: TrackID(1), + time: 4, + position: (4, 4), + }, + Ping { + id: TrackID(1), + time: 5, + position: (5, 5), + }, + Ping { + id: TrackID(1), + time: 6, + position: (6, 6), + }, + ]); + db.expect_query( + 8, + &[(TrackID(1), &[(2, 2), (3, 3), (4, 4), (5, 5), (6, 6)])], + ); + } + + #[test] + fn scenario1() { + let mut db = DatabaseTester::default(); + db.extend(&[ + Ping { + id: TrackID(1), + time: 2, + position: (1, 0), + }, + Ping { + id: TrackID(1), + time: 3, + position: (1, 1), + }, + Ping { + id: TrackID(2), + time: 3, + position: (2, 0), + }, + Ping { + id: TrackID(1), + time: 4, + position: (1, 2), + }, + ]); + db.expect_query(0, &[]); + db.expect_query(1, &[]); + db.expect_query( + 3, + &[(TrackID(1), &[(1, 0), (1, 1)]), (TrackID(2), &[(2, 0)])], + ); + + db.extend(&[ + Lost { + id: TrackID(2), + time: 4, + }, + Ping { + id: TrackID(1), + time: 4, + position: (1, 3), + }, + Ping { + id: TrackID(3), + time: 4, + position: (1, 2), + }, + ]); + db.expect_query( + 3, + &[(TrackID(1), &[(1, 0), (1, 1)]), (TrackID(2), &[(2, 0)])], + ); + db.expect_query( + 4, + &[ + (TrackID(1), &[(1, 0), (1, 1), (1, 2), (1, 3)]), + (TrackID(3), &[(1, 2)]), + ], + ); + + db.extend(&[ + Ping { + id: TrackID(1), + time: 5, + position: (1, 4), + }, + Ping { + id: TrackID(1), + time: 6, + position: (1, 5), + }, + Ping { + id: TrackID(1), + time: 7, + position: (1, 6), + }, + Lost { + id: TrackID(1), + time: 9, + }, + ]); + db.expect_query( + 4, + &[ + (TrackID(1), &[(1, 0), (1, 1), (1, 2), (1, 3)]), + (TrackID(3), &[(1, 2)]), + ], + ); + db.expect_query( + 8, + &[ + (TrackID(1), &[(1, 2), (1, 3), (1, 4), (1, 5), (1, 6)]), + (TrackID(3), &[(1, 2)]), + ], + ); + db.expect_query(9, &[(TrackID(3), &[(1, 2)])]); + + db.extend(&[Lost { + id: TrackID(3), + time: 40, + }]); + db.expect_query(100, &[]); + } + + pub struct DatabaseTester { + inner: Database, + save_load: bool, + iterator: bool, + } + + impl Default for DatabaseTester { + fn default() -> Self { + let tests = std::env::var("TESTING").unwrap_or_default(); + Self { + inner: Default::default(), + save_load: tests.contains("save_load"), + iterator: tests.contains("iterator"), + } + } + } + + impl DatabaseTester { + #[track_caller] + fn extend(&mut self, events: &[TrackEvent]) { + for event in events { + self.inner.process(event.clone()).unwrap() + } + } + + #[track_caller] + fn expect_query_map(&self, time: UTC, expect: &[(TrackID, &[(i32, i32)])]) { + let mut got = self.inner.query(time); + for (id, expected) in expect { + let Some(got) = got.remove(&id) else { + panic!("No positions with {id:?} found, expected to have {expected:?}"); + }; + assert_eq!(got, *expected, "{id:?} @ time={time}"); + } + assert!(got.is_empty(), "More results than expected, extra: {got:?}"); + } + + #[track_caller] + fn expect_query_iterator(&self, time: UTC, expect: &[(TrackID, &[(i32, i32)])]) { + let mut expected: HashMap<_, _> = expect.iter().copied().collect(); + for (id, got) in self.inner.query_iterator(time) { + let Some(expected) = expected.remove(&id) else { + panic!("Got track {id:?} with {got:?} but expected not to"); + }; + assert_eq!(got, expected, "{id:?}"); + } + assert!(expected.is_empty(), "Missing query results: {expected:?}"); + } + + #[track_caller] + fn expect_query(&mut self, time: UTC, expect: &[(TrackID, &[(i32, i32)])]) { + self.expect_query_map(time, expect); + if self.iterator { + self.expect_query_iterator(time, expect); + } + if self.save_load { + let save = self.inner.save(); + self.inner = Database::load(&save).expect("Database to load from save"); + if self.iterator { + self.expect_query_iterator(time, expect); + } + self.expect_query_map(time, expect); + } + } + } +} |