quickdudley/namepick - Change VBDR24U4NU2GWBHQE5B3BMJPWOCAXK5Y2WURM5EFZSN77Y6T54HQC

Switch from in memory grid to recursive CTE

Created by quickdudley on August 21, 2023

VBDR24U4NU2GWBHQE5B3BMJPWOCAXK5Y2WURM5EFZSN77Y6T54HQC

Dependencies

In channels

main

Change contents

File deletion: grid.rs

BF:BFD[3.15] → [4.3286:3317]

BF:BFD[4.3317] → [4.3318:3318]

B:BD[4.3318] → [4.3319:3533]

B:BD[4.3533] → [5.1558:1613]

∅:D[5.1613] → [4.3595:3635]

B:BD[4.3595] → [4.3595:3635]

B:BD[4.3635] → [5.1614:1663]

∅:D[5.1663] → [4.3691:10515]

B:BD[4.3691] → [4.3691:10515]

B:BD[4.10515] → [5.1664:1715]

∅:D[5.1715] → [4.10581:12449]

B:BD[4.10581] → [4.10581:12449]

#[derive(Debug)]
pub struct BoolGrid {
    width: usize,
    content: Vec<bool>,
}
impl BoolGrid {
    pub fn new() -> Self {
        Self {
            width: 0,
            content: Vec::new(),
        }
    }
    pub fn column(&self, x: usize) -> BoolColumn<'_> {
        BoolColumn::new(self, x)
    }
    pub fn row(&self, y: usize) -> BoolRow<'_> {
        BoolRow::new(self, y)
    }
    pub fn set_transitive(
        &mut self,
        x: usize,
        y: usize,
    ) -> Vec<(usize, usize)> {
        use std::collections::VecDeque;
        let mut q = VecDeque::new();
        q.push_back((x, y));
        let mut result = Vec::new();
        while let Some((x, y)) = q.pop_front() {
            let t = &mut self[(x, y)];
            if !*t {
                *t = true;
                result.push((x, y));
                for (c, v) in self.row(x).enumerate() {
                    if v {
                        q.push_back((c, y));
                    }
                }
                for (c, v) in self.column(y).enumerate() {
                    if v {
                        q.push_back((x, c));
                    }
                }
            }
        }
        result
    }
    pub fn compare(&self, x: usize, y: usize) -> Option<std::cmp::Ordering> {
        use std::cmp::Ordering::*;
        if x == y {
            Some(Equal)
        } else {
            match (self[(x, y)], self[(y, x)]) {
                (true, true) => Some(Equal),
                (true, false) => Some(Greater),
                (false, true) => Some(Less),
                (false, false) => None,
            }
        }
    }
}
#[test]
fn transitive_works() {
    let mut grid = BoolGrid::new();
    grid.set_transitive(1, 2);
    grid.set_transitive(14, 15);
    grid.set_transitive(2, 3);
    grid.set_transitive(10, 11);
    grid.set_transitive(4, 5);
    grid.set_transitive(12, 13);
    grid.set_transitive(15, 16);
    grid.set_transitive(6, 7);
    grid.set_transitive(13, 14);
    grid.set_transitive(5, 6);
    grid.set_transitive(9, 10);
    grid.set_transitive(11, 12);
    grid.set_transitive(8, 9);
    for x in 0..=16 {
        for y in 0..=16 {
            assert_eq!(
                x < y
                    && [1..=3, 4..=7, 8..=16]
                        .into_iter()
                        .any(|i| i.contains(&x) && i.contains(&y)),
                grid[(x, y)]
            );
        }
    }
}
#[test]
fn row_iterator() {
    let mut grid = BoolGrid::new();
    grid[(5, 4)] = true;
    let row: Vec<_> = grid.row(4).collect();
    assert_eq!(&row[..], &[false, false, false, false, false, true]);
    assert!(grid.row(5).all(|v| !v));
}
#[test]
fn col_iterator() {
    let mut grid = BoolGrid::new();
    grid[(5, 4)] = true;
    let row: Vec<_> = grid.column(5).collect();
    assert_eq!(&row[..], &[false, false, false, false, true]);
    assert!(grid.column(6).all(|v| !v));
}
#[test]
fn test_compare() {
    use std::cmp::Ordering::*;
    let mut grid = BoolGrid::new();
    let mut set = Vec::new();
    set.extend(grid.set_transitive(1, 2).into_iter());
    set.extend(grid.set_transitive(2, 3).into_iter());
    assert_eq!(grid.compare(3, 4), None);
    assert_eq!(grid.compare(1, 3), Some(Greater));
    assert_eq!(grid.compare(3, 1), Some(Less));
    assert_eq!(grid.compare(2, 2), Some(Equal));
    assert!(set.iter().all(|(a, b)| a < b));
}
#[test]
fn test_transitive_bug() {
    let mut grid = BoolGrid::new();
    let mut set = Vec::new();
    for (a, b) in [(1, 4), (4, 2), (8, 4), (3, 4), (4, 7), (4, 6), (4, 12)] {
        set.extend(grid.set_transitive(a, b));
    }
    for (a, b) in set {
        assert!(a != 11);
        assert!(b != 11);
    }
    for x in 1..=12 {
        assert!(!grid[(11, x)]);
        assert!(!grid[(x, 11)]);
    }
}
#[test]
fn test_rows_cols_bug() {
    use std::collections::HashSet;
    let mut grid = BoolGrid::new();
    let mut set = HashSet::new();
    grid.set_transitive(1, 4);
    set.insert((1, 4));
    for x in 0..=5 {
        for y in 0..=5 {
            assert_eq!(grid[(x, y)], (x, y) == (1, 4));
        }
    }
    let c: Vec<_> = grid.column(3).collect();
    println!("column 3: {:?}", c);
    for x in 0..12 {
        for (y, v) in grid.column(x).enumerate() {
            if v != set.contains(&(x, y)) {
                panic!("x: {}, y: {}, v: {}", x, y, v);
            }
        }
    }
}
static OFF_GRID: bool = false;
impl std::ops::Index<(usize, usize)> for BoolGrid {
    type Output = bool;
    fn index(&self, (x, y): (usize, usize)) -> &bool {
        if x >= self.width {
            return &OFF_GRID;
        }
        let ix = self.width * y + x;
        if ix >= self.content.len() {
            return &OFF_GRID;
        }
        <Vec<bool> as std::ops::Index<usize>>::index(&self.content, ix)
    }
}
impl std::ops::IndexMut<(usize, usize)> for BoolGrid {
    fn index_mut(&mut self, (x, y): (usize, usize)) -> &mut bool {
        let height = self.content.len() / self.width.max(1);
        let rq_width = self.width.max(x + 1);
        let rq_height = (y + 1).max(height);
        if (self.width, height) != (rq_width, rq_height) {
            struct Resize {
                old_content: Vec<bool>,
                old_width: usize,
                new_width: usize,
                new_height: usize,
                x: usize,
                y: usize,
            }
            impl Resize {
                fn new(
                    content: Vec<bool>,
                    old_width: usize,
                    new_width: usize,
                    new_height: usize,
                ) -> Self {
                    Self {
                        old_content: content,
                        old_width,
                        new_width,
                        new_height,
                        x: 0,
                        y: 0,
                    }
                }
            }
            impl Iterator for Resize {
                type Item = bool;
                fn next(&mut self) -> Option<bool> {
                    if self.y >= self.new_height {
                        return None;
                    }
                    let result = if self.x >= self.old_width {
                        Some(false)
                    } else {
                        let ix = self.y * self.old_width + self.x;
                        if ix >= self.old_content.len() {
                            Some(false)
                        } else {
                            Some(self.old_content[ix])
                        }
                    };
                    let z = if self.x < self.new_width - 1 {
                        (self.x + 1, self.y)
                    } else {
                        (0, self.y + 1)
                    };
                    self.x = z.0;
                    self.y = z.1;
                    result
                }
                fn size_hint(&self) -> (usize, Option<usize>) {
                    let r =
                        self.new_width * (self.new_height - self.y) - self.x;
                    (r, Some(r))
                }
            }
            self.content = Resize::new(
                std::mem::take(&mut self.content),
                self.width,
                rq_width,
                rq_height,
            )
            .collect();
            self.width = rq_width;
        }
        <Vec<bool> as std::ops::IndexMut<usize>>::index_mut(
            &mut self.content,
            self.width * y + x,
        )
    }
}
pub struct BoolColumn<'a> {
    grid: &'a BoolGrid,
    ix: usize,
}
impl<'a> BoolColumn<'a> {
    fn new(grid: &'a BoolGrid, x: usize) -> Self {
        if x < grid.width {
            Self { grid, ix: x }
        } else {
            Self {
                grid,
                ix: usize::MAX,
            }
        }
    }
}
impl<'a> Iterator for BoolColumn<'a> {
    type Item = bool;
    fn next(&mut self) -> Option<bool> {
        if self.ix < self.grid.content.len() {
            let result = self.grid.content[self.ix];
            self.ix += self.grid.width;
            Some(result)
        } else {
            None
        }
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.grid.content.len();
        let result = (len - self.ix) / len;
        (result, Some(result))
    }
}
pub struct BoolRow<'a> {
    grid: &'a BoolGrid,
    ix: usize,
    end: usize,
}
impl<'a> BoolRow<'a> {
    fn new(grid: &'a BoolGrid, y: usize) -> Self {
        Self {
            grid,
            ix: y * grid.width,
            end: (y + 1) * grid.width,
        }
    }
}
impl<'a> Iterator for BoolRow<'a> {
    type Item = bool;
    fn next(&mut self) -> Option<bool> {
        if self.ix < self.end && self.ix < self.grid.content.len() {
            let result = self.grid.content[self.ix];
            self.ix += 1;
            Some(result)
        } else {
            None
        }
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        let result = self.end - self.ix;
        (result, Some(result))
    }
}

Deletion in src/pick.rs at line 3 [7.32]
B:BD[6.19] → [4.0:27]
```
use crate::grid::BoolGrid;
```
Deletion in src/pick.rs at line 162 [7.32]
B:BD[6.2908] → [4.269:290]
```
    cache: BoolGrid,
```

Deletion in src/pick.rs at line 176 [7.32]

B:BD[4.410] → [4.410:610]

        let mut cache = BoolGrid::new();
        for (x, y) in db.list_preferences().await.unwrap_or_else(|_| Vec::new())
        {
            cache.set_transitive(x as usize, y as usize);
        }

Deletion in src/pick.rs at line 182 [7.32]
B:BD[8.605] → [4.611:630]
```
            cache,
```

Replacement in src/pick.rs at line 221 [7.32]

∅:D[2.606] → [4.980:1043]

B:BD[6.4141] → [4.980:1043]

        match self.cache.compare(a.1 as usize, b.1 as usize) {

[2.606]

[6.4219]

        match self.db.compare(a.1, b.1).await? {

Replacement in src/pick.rs at line 265 [7.32]

B:BD[4.1157] → [4.1157:1467]

                self.cache.set_transitive(better as usize, worse as usize);
                {
                    let tdb = self.db.clone();
                    tokio::spawn(async move {
                        tdb.insert_preference(better as i64, worse as i64).await
                    });
                }

[4.1157]

[4.1467]

                self.db.insert_preference(better as i64, worse as i64).await?;

Replacement in src/names_database.rs at line 78 [10.42]

B:BD[9.968] → [4.1469:2801]

    //  pub async fn compare(
    //      &self,
    //      a: i64,
    //      b: i64,
    //  ) -> DynResult<Option<std::cmp::Ordering>> {
    //      if a == b {
    //          return Ok(Some(std::cmp::Ordering::Equal));
    //      }
    //      Ok(self.post(move |conn| -> DynResult<Option<std::cmp::Ordering>> {
    //          let mut stmnt = conn.prepare("SELECT better, worse FROM preferences WHERE (better = ? AND worse = ?) OR (better = ? AND worse = ?)")?;
    //          stmnt.bind::<i64>(1,a)?;
    //          stmnt.bind::<i64>(2,b)?;
    //          stmnt.bind::<i64>(3,b)?;
    //          stmnt.bind::<i64>(4,a)?;
    //          match stmnt.next()? {
    //              sqlite::State::Done => Ok(None),
    //              sqlite::State::Row => {
    //                  let better = stmnt.read::<i64>(0)?;
    //                  let worse = stmnt.read::<i64>(1)?;
    //                  if better == a && worse == b {
    //                      Ok(Some(std::cmp::Ordering::Greater))
    //                  } else if better == b && worse == a {
    //                      Ok(Some(std::cmp::Ordering::Less))
    //                  } else {
    //                      Ok(Some(std::cmp::Ordering::Equal))
    //                  }
    //              }
    //          }
    //      }).await??)
    //  }

[9.968]

[9.2180]

    pub async fn compare(
        &self,
        a: i64,
        b: i64,
    ) -> DynResult<Option<std::cmp::Ordering>> {
        if a == b {
            return Ok(Some(std::cmp::Ordering::Equal));
        }
        Ok(self.post(move |conn| -> DynResult<Option<std::cmp::Ordering>> {
            let mut stmnt = conn.prepare("WITH RECURSIVE t(better,worse) AS (SELECT better, worse FROM preferences WHERE preferences.worse IN (?,?) UNION SELECT preferences.better, t.worse FROM preferences INNER JOIN t ON preferences.worse = t.better) SELECT t.better, t.worse FROM t WHERE t.better IN (?,?) LIMIT 1")?;
            stmnt.bind::<i64>(1,a)?;
            stmnt.bind::<i64>(2,b)?;
            stmnt.bind::<i64>(3,a)?;
            stmnt.bind::<i64>(4,b)?;
            match stmnt.next()? {
                sqlite::State::Done => Ok(None),
                sqlite::State::Row => {
                    let better = stmnt.read::<i64>(0)?;
                    let worse = stmnt.read::<i64>(1)?;
                    if better == a && worse == b {
                        Ok(Some(std::cmp::Ordering::Greater))
                    } else if better == b && worse == a {
                        Ok(Some(std::cmp::Ordering::Less))
                    } else {
                        Ok(Some(std::cmp::Ordering::Equal))
                    }
                }
            }
        }).await??)
    }

Deletion in src/main.rs at line 5 [3.49]
B:BD[11.222] → [4.3275:3285]
```
mod grid;
```

Switch from in memory grid to recursive CTE

Dependencies

In channels

Change contents

File deletion: grid.rs

Deletion in src/pick.rs at line 3 [7.32]

Deletion in src/pick.rs at line 162 [7.32]

Deletion in src/pick.rs at line 176 [7.32]

Deletion in src/pick.rs at line 182 [7.32]

Replacement in src/pick.rs at line 221 [7.32]

Replacement in src/pick.rs at line 265 [7.32]

Replacement in src/names_database.rs at line 78 [10.42]

Deletion in src/main.rs at line 5 [3.49]