pub(crate) use _bisect::module_def;
#[pymodule]
mod _bisect {
use crate::vm::{
PyObjectRef, PyResult, VirtualMachine, function::ArgIndex, types::PyComparisonOp,
};
#[derive(FromArgs)]
struct BisectArgs {
a: PyObjectRef,
x: PyObjectRef,
#[pyarg(any, default = 0)]
lo: ArgIndex,
#[pyarg(any, optional)]
hi: Option<ArgIndex>,
#[pyarg(named, optional)]
key: Option<PyObjectRef>,
}
#[inline]
fn handle_default(arg: ArgIndex, vm: &VirtualMachine) -> PyResult<isize> {
arg.into_int_ref().try_to_primitive(vm)
}
#[inline]
fn as_usize(
lo: ArgIndex,
hi: Option<ArgIndex>,
seq_len: usize,
vm: &VirtualMachine,
) -> PyResult<(usize, usize)> {
let lo = usize::try_from(handle_default(lo, vm)?)
.map_err(|_| vm.new_value_error("lo must be non-negative"))?;
let hi = match hi {
Some(value) => {
let value: isize = value.into_int_ref().try_to_primitive(vm)?;
usize::try_from(value).unwrap_or(0)
}
None => seq_len,
};
Ok((lo, hi))
}
#[inline]
#[pyfunction]
fn bisect_left(
BisectArgs { a, x, lo, hi, key }: BisectArgs,
vm: &VirtualMachine,
) -> PyResult<usize> {
let (mut lo, mut hi) = as_usize(lo, hi, a.length(vm)?, vm)?;
while lo < hi {
let mid = (lo + hi) / 2;
let a_mid = a.get_item(&mid, vm)?;
let comp = if let Some(ref key) = key {
key.call((a_mid,), vm)?
} else {
a_mid
};
if comp.rich_compare_bool(&x, PyComparisonOp::Lt, vm)? {
lo = mid + 1;
} else {
hi = mid;
}
}
Ok(lo)
}
#[inline]
#[pyfunction]
fn bisect_right(
BisectArgs { a, x, lo, hi, key }: BisectArgs,
vm: &VirtualMachine,
) -> PyResult<usize> {
let (mut lo, mut hi) = as_usize(lo, hi, a.length(vm)?, vm)?;
while lo < hi {
let mid = (lo + hi) / 2;
let a_mid = a.get_item(&mid, vm)?;
let comp = if let Some(ref key) = key {
key.call((a_mid,), vm)?
} else {
a_mid
};
if x.rich_compare_bool(&comp, PyComparisonOp::Lt, vm)? {
hi = mid;
} else {
lo = mid + 1;
}
}
Ok(lo)
}
#[pyfunction]
fn insort_left(BisectArgs { a, x, lo, hi, key }: BisectArgs, vm: &VirtualMachine) -> PyResult {
let needle = match key {
Some(ref key) => key.call((x.clone(),), vm)?,
None => x.clone(),
};
let index = bisect_left(
BisectArgs {
a: a.clone(),
x: needle,
lo,
hi,
key,
},
vm,
)?;
vm.call_method(&a, "insert", (index, x))
}
#[pyfunction]
fn insort_right(BisectArgs { a, x, lo, hi, key }: BisectArgs, vm: &VirtualMachine) -> PyResult {
let needle = match key {
Some(ref key) => key.call((x.clone(),), vm)?,
None => x.clone(),
};
let index = bisect_right(
BisectArgs {
a: a.clone(),
x: needle,
lo,
hi,
key,
},
vm,
)?;
vm.call_method(&a, "insert", (index, x))
}
}