pub(crate) use _heapq::module_def;
#[pymodule]
mod _heapq {
use crate::vm::{
Py, PyObjectRef, PyResult, VirtualMachine,
builtins::{PyList, PyListRef},
types::PyComparisonOp,
};
fn siftdown(
heap: &Py<PyList>,
startpos: usize,
mut pos: usize,
vm: &VirtualMachine,
) -> PyResult<()> {
let size = heap.__len__();
let newitem = match heap.borrow_vec().get(pos) {
Some(v) => v.clone(),
None => return Err(vm.new_index_error("index out of range")),
};
while pos > startpos {
let parentpos = (pos - 1) >> 1;
let parent = {
let vec = heap.borrow_vec();
vec[parentpos].clone()
};
let cmp = newitem.rich_compare_bool(&parent, PyComparisonOp::Lt, vm)?;
if size != heap.__len__() {
return Err(vm.new_runtime_error("list changed size during iteration"));
}
if !cmp {
break;
}
{
let mut vec = heap.borrow_vec_mut();
vec.swap(pos, parentpos);
}
pos = parentpos;
}
Ok(())
}
fn siftup(heap: &Py<PyList>, mut pos: usize, vm: &VirtualMachine) -> PyResult<()> {
let endpos = heap.__len__();
let startpos = pos;
if pos >= endpos {
return Err(vm.new_index_error("index out of range"));
};
let limit = endpos >> 1;
while pos < limit {
let mut childpos = 2 * pos + 1;
if childpos + 1 < endpos {
let (a, b) = {
let vec = heap.borrow_vec();
(vec[childpos].clone(), vec[childpos + 1].clone())
};
let cmp = a.rich_compare_bool(&b, PyComparisonOp::Lt, vm)?;
if endpos != heap.__len__() {
return Err(vm.new_runtime_error("list changed size during iteration"));
}
if !cmp {
childpos += 1;
}
}
{
let mut vec = heap.borrow_vec_mut();
vec.swap(pos, childpos);
}
pos = childpos;
}
siftdown(heap, startpos, pos, vm)
}
fn heappush_internal<F>(
heap: &Py<PyList>,
item: PyObjectRef,
siftdown_func: F,
vm: &VirtualMachine,
) -> PyResult<()>
where
F: Fn(&Py<PyList>, usize, usize, &VirtualMachine) -> PyResult<()>,
{
{
let mut vec = heap.borrow_vec_mut();
vec.push(item);
}
let size = heap.__len__();
siftdown_func(heap, 0, size - 1, vm)
}
#[pyfunction]
fn heappush(heap: PyListRef, item: PyObjectRef, vm: &VirtualMachine) -> PyResult<()> {
heappush_internal(&heap, item, siftdown, vm)
}
fn heappop_internal<F>(
heap: &Py<PyList>,
siftup_func: F,
vm: &VirtualMachine,
) -> PyResult<PyObjectRef>
where
F: Fn(&Py<PyList>, usize, &VirtualMachine) -> PyResult<()>,
{
let Some(lastelt) = heap.borrow_vec_mut().pop() else {
return Err(vm.new_index_error("index out of range"));
};
if heap.borrow_vec().is_empty() {
return Ok(lastelt);
};
let returnitem = {
let mut vec = heap.borrow_vec_mut();
let root = vec[0].clone();
vec[0] = lastelt;
root
};
siftup_func(heap, 0, vm)?;
Ok(returnitem)
}
#[pyfunction]
fn heappop(heap: PyListRef, vm: &VirtualMachine) -> PyResult<PyObjectRef> {
heappop_internal(&heap, siftup, vm)
}
fn heapreplace_internal<F>(
heap: &Py<PyList>,
item: PyObjectRef,
siftup_func: F,
vm: &VirtualMachine,
) -> PyResult<PyObjectRef>
where
F: Fn(&Py<PyList>, usize, &VirtualMachine) -> PyResult<()>,
{
let returnitem = {
let mut vec = heap.borrow_vec_mut();
let root = match vec.first() {
Some(v) => v.clone(),
None => return Err(vm.new_index_error("index out of range")),
};
vec[0] = item;
root
};
siftup_func(heap, 0, vm)?;
Ok(returnitem)
}
#[pyfunction]
fn heapreplace(
heap: PyListRef,
item: PyObjectRef,
vm: &VirtualMachine,
) -> PyResult<PyObjectRef> {
heapreplace_internal(&heap, item, siftup, vm)
}
#[pyfunction]
fn heappushpop(
heap: PyListRef,
item: PyObjectRef,
vm: &VirtualMachine,
) -> PyResult<PyObjectRef> {
let top = {
let vec = heap.borrow_vec();
match vec.first() {
Some(v) => v.clone(),
None => return Ok(item),
}
};
let cmp = top.rich_compare_bool(&item, PyComparisonOp::Lt, vm)?;
if !cmp {
return Ok(item);
}
let returnitem = {
let mut vec = heap.borrow_vec_mut();
let root = match vec.first() {
Some(v) => v.clone(),
None => return Err(vm.new_index_error("index out of range")),
};
vec[0] = item;
root
};
siftup(&heap, 0, vm)?;
Ok(returnitem)
}
const fn keep_top_bit(mut n: usize) -> usize {
let mut i = 0;
while n > 1 {
n >>= 1;
i += 1;
}
n << i
}
fn cache_friendly_heapify<F>(
heap: &Py<PyList>,
siftup_func: F,
vm: &VirtualMachine,
) -> PyResult<()>
where
F: Fn(&Py<PyList>, usize, &VirtualMachine) -> PyResult<()>,
{
let m = heap.__len__() >> 1; let leftmost = keep_top_bit(m + 1) - 1; let mhalf = m >> 1;
for i in (mhalf..leftmost).rev() {
let mut j = i;
loop {
siftup_func(heap, j, vm)?;
if j & 1 == 0 {
break;
}
j >>= 1;
}
}
for i in (leftmost..m).rev() {
let mut j = i;
loop {
siftup_func(heap, j, vm)?;
if j & 1 == 0 {
break;
}
j >>= 1;
}
}
Ok(())
}
fn heapify_internal<F>(heap: &Py<PyList>, siftup_func: F, vm: &VirtualMachine) -> PyResult<()>
where
F: Fn(&Py<PyList>, usize, &VirtualMachine) -> PyResult<()>,
{
let n = heap.__len__();
if n > 2500 {
return cache_friendly_heapify(heap, siftup_func, vm);
}
for i in (0..(n >> 1)).rev() {
siftup_func(heap, i, vm)?;
}
Ok(())
}
#[pyfunction]
fn heapify(heap: PyListRef, vm: &VirtualMachine) -> PyResult<()> {
heapify_internal(&heap, siftup, vm)
}
fn siftdown_max(
heap: &Py<PyList>,
startpos: usize,
mut pos: usize,
vm: &VirtualMachine,
) -> PyResult<()> {
let size = heap.__len__();
let newitem = match heap.borrow_vec().get(pos) {
Some(v) => v.clone(),
None => return Err(vm.new_index_error("index out of range")),
};
while pos > startpos {
let parentpos = (pos - 1) >> 1;
let parent = {
let vec = heap.borrow_vec();
vec[parentpos].clone()
};
let cmp = parent.rich_compare_bool(&newitem, PyComparisonOp::Lt, vm)?;
if size != heap.__len__() {
return Err(vm.new_runtime_error("list changed size during iteration"));
}
if !cmp {
break;
}
{
let mut vec = heap.borrow_vec_mut();
vec.swap(pos, parentpos);
}
pos = parentpos;
}
Ok(())
}
fn siftup_max(heap: &Py<PyList>, mut pos: usize, vm: &VirtualMachine) -> PyResult<()> {
let endpos = heap.__len__();
let startpos = pos;
if pos >= endpos {
return Err(vm.new_index_error("index out of range"));
};
let limit = endpos >> 1;
while pos < limit {
let mut childpos = 2 * pos + 1;
if childpos + 1 < endpos {
let (a, b) = {
let vec = heap.borrow_vec();
(vec[childpos + 1].clone(), vec[childpos].clone())
};
let cmp = a.rich_compare_bool(&b, PyComparisonOp::Lt, vm)?;
if endpos != heap.__len__() {
return Err(vm.new_runtime_error("list changed size during iteration"));
}
if !cmp {
childpos += 1;
}
}
{
let mut vec = heap.borrow_vec_mut();
vec.swap(pos, childpos);
}
pos = childpos;
}
siftdown_max(heap, startpos, pos, vm)
}
#[pyfunction]
fn heappush_max(heap: PyListRef, item: PyObjectRef, vm: &VirtualMachine) -> PyResult<()> {
heappush_internal(&heap, item, siftdown_max, vm)
}
#[pyfunction]
fn heappop_max(heap: PyListRef, vm: &VirtualMachine) -> PyResult<PyObjectRef> {
heappop_internal(&heap, siftup_max, vm)
}
#[pyfunction]
fn heapreplace_max(
heap: PyListRef,
item: PyObjectRef,
vm: &VirtualMachine,
) -> PyResult<PyObjectRef> {
heapreplace_internal(&heap, item, siftup_max, vm)
}
#[pyfunction]
fn heapify_max(heap: PyListRef, vm: &VirtualMachine) -> PyResult<()> {
heapify_internal(&heap, siftup_max, vm)
}
#[pyfunction]
fn heappushpop_max(
heap: PyListRef,
item: PyObjectRef,
vm: &VirtualMachine,
) -> PyResult<PyObjectRef> {
let top = {
let vec = heap.borrow_vec();
match vec.first() {
Some(v) => v.clone(),
None => return Ok(item),
}
};
let cmp = item.rich_compare_bool(&top, PyComparisonOp::Lt, vm)?;
if !cmp {
return Ok(item);
}
let returnitem = {
let mut vec = heap.borrow_vec_mut();
let root = match vec.first() {
Some(v) => v.clone(),
None => return Err(vm.new_index_error("index out of range")),
};
vec[0] = item;
root
};
siftup_max(&heap, 0, vm)?;
Ok(returnitem)
}
}