use crate::grid::BoolGrid;

    let mut comparator = CompareContext::new(&db, &mut stderr)?;

    let mut comparator = CompareContext::new(&db, &mut stderr).await?;

        let mut stack: Vec<(*mut (String, i64), *mut (String, i64))> = vec![(&mut shortlist[0], &mut shortlist[len - 1])];

        let mut stack: Vec<(*mut (String, i64), *mut (String, i64))> =
            vec![(&mut shortlist[0], &mut shortlist[len - 1])];

    std::mem::drop(comparator);

    needs_newline: bool,

    cache: BoolGrid,

    fn new(db: &'a AsyncConnection, out: &'a mut W) -> DynResult<Self> {

    async fn new(
        db: &'a AsyncConnection,
        out: &'a mut W,
    ) -> DynResult<CompareContext<'a, W>> {
        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);
        }

            needs_newline: false,

            cache,

        mut pivot: *mut (String, i64),

        pivot: *mut (String, i64),

        use std::cmp::Ordering::*;

        let pivot = (&*pivot).clone();

            loop {

            'l: loop {

                match self.compare(&*i, &*pivot).await? {
                    std::cmp::Ordering::Greater => (),
                    _ => break,

                if self.compare(&*i, &pivot).await? != Greater {
                    break 'l;

            loop {

            'r: loop {

                match self.compare(&*j, &*pivot).await? {
                    std::cmp::Ordering::Less => (),
                    _ => break,

                if self.compare(&*j, &pivot).await? != Less {
                    break 'r;

                if pivot == i {
                    pivot = j;
                } else if pivot == j {
                    pivot = i;
                }

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

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

                if self.needs_newline {
                    self.out.queue(cursor::MoveToNextLine(1))?;
                } else {
                    self.needs_newline = true;
                }

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

                self.out.queue(style::Print('\n'))?;
                self.out.execute(cursor::MoveToColumn(0))?;
                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
                    });
                }

    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??)
    }

    //  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??)
    //  }

    pub async fn insert_preference(
        &self,
        better: i64,
        worse: i64,
    ) -> DynResult<()> {
        self.insert_one_preference(better, worse).await?;
        self.make_transitive().await

    pub async fn list_preferences(&self) -> DynResult<Vec<(i64, i64)>> {
        self.post(|conn| {
            let mut stmnt =
                conn.prepare("SELECT better, worse FROM preferences")?;
            let mut rows = Vec::new();
            while let sqlite::State::Row = stmnt.next()? {
                rows.push((stmnt.read::<i64>(0)?, stmnt.read::<i64>(1)?));
            }
            Ok(rows)
        })
        .await?

    async fn insert_one_preference(

    pub async fn insert_preference(

    }
    pub async fn make_transitive(&self) -> DynResult<()> {
        loop {
            let todo = self
                .post(|db| -> DynResult<_> {
                    let mut stmnt = db.prepare(
                        "SELECT a.better, b.worse
                FROM preferences AS a
                INNER JOIN preferences as b ON a.worse = b.better
                WHERE NOT EXISTS (
                  SELECT rowid FROM preferences AS x
                  WHERE x.better = a.better
                  AND x.worse = b.worse
                )
                ",
                    )?;
                    let mut rows = Vec::new();
                    while let sqlite::State::Row = stmnt.next()? {
                        rows.push((
                            stmnt.read::<i64>(0)?,
                            stmnt.read::<i64>(1)?,
                        ));
                    }
                    Ok(rows)
                })
                .await??;
            if todo.is_empty() {
                return Ok(());
            } else {
                let handles: Vec<_> = todo
                    .into_iter()
                    .map(|(better, worse)| {
                        let target = self.clone();
                        tokio::spawn(async move {
                            target.insert_one_preference(better, worse).await
                        })
                    })
                    .collect();
                for handle in handles {
                    handle.await??;
                }
            }
        }

mod grid;

#[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<'a>(&'a self, x: usize) -> BoolColumn<'a> {
        BoolColumn::new(self, x)
    }
    pub fn row<'a>(&'a self, y: usize) -> BoolRow<'a> {
        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::replace(&mut self.content, Vec::new()),
                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))
    }
}