use crate::host::{type_error, PyHost, PyObj};
use fusevm::{NumOp, Value};
pub fn entries(h: &mut PyHost) -> Vec<(String, Value)> {
[
"heappush",
"heappop",
"heapify",
"heappushpop",
"heapreplace",
"nlargest",
"nsmallest",
]
.iter()
.map(|name| {
(
(*name).to_string(),
h.alloc(PyObj::Builtin(format!("heapq.{name}"))),
)
})
.collect()
}
pub fn call(h: &mut PyHost, fname: &str, args: &[Value]) -> Option<Result<Value, String>> {
match fname {
"heappush" => Some(heappush(h, args)),
"heappop" => Some(heappop(h, args)),
"heapify" => Some(heapify(h, args)),
"heappushpop" => Some(heappushpop(h, args)),
"heapreplace" => Some(heapreplace(h, args)),
"nlargest" => Some(nlargest(h, args)),
"nsmallest" => Some(nsmallest(h, args)),
_ => None,
}
}
fn lt(h: &mut PyHost, a: &Value, b: &Value) -> Result<bool, String> {
let v = h.compare(NumOp::Lt, a, b)?;
Ok(h.truthy(&v))
}
fn snapshot(h: &PyHost, args: &[Value], idx: usize, fname: &str) -> Result<Vec<Value>, String> {
let v = args
.get(idx)
.ok_or_else(|| type_error(&format!("{fname} expected a heap argument")))?;
match h.get(v) {
Some(PyObj::List(l)) => Ok(l.clone()),
_ => Err(type_error(&format!(
"heap argument must be a list, not '{}'",
h.type_name(v)
))),
}
}
fn write_back(h: &mut PyHost, target: &Value, heap: Vec<Value>) {
if let Some(PyObj::List(l)) = h.get_mut(target) {
*l = heap;
}
}
fn siftdown(
h: &mut PyHost,
heap: &mut [Value],
startpos: usize,
mut pos: usize,
) -> Result<(), String> {
let newitem = heap[pos].clone();
while pos > startpos {
let parentpos = (pos - 1) >> 1;
if lt(h, &newitem, &heap[parentpos])? {
heap[pos] = heap[parentpos].clone();
pos = parentpos;
continue;
}
break;
}
heap[pos] = newitem;
Ok(())
}
fn siftup(h: &mut PyHost, heap: &mut [Value], mut pos: usize) -> Result<(), String> {
let endpos = heap.len();
let startpos = pos;
let newitem = heap[pos].clone();
let mut childpos = 2 * pos + 1;
while childpos < endpos {
let rightpos = childpos + 1;
if rightpos < endpos && !lt(h, &heap[childpos], &heap[rightpos])? {
childpos = rightpos;
}
heap[pos] = heap[childpos].clone();
pos = childpos;
childpos = 2 * pos + 1;
}
heap[pos] = newitem;
siftdown(h, heap, startpos, pos)
}
fn heappush(h: &mut PyHost, args: &[Value]) -> Result<Value, String> {
let target = args
.first()
.cloned()
.ok_or_else(|| type_error("heappush expected 2 arguments"))?;
let item = args
.get(1)
.cloned()
.ok_or_else(|| type_error("heappush expected 2 arguments"))?;
let mut heap = snapshot(h, args, 0, "heappush")?;
heap.push(item);
let last = heap.len() - 1;
siftdown(h, &mut heap, 0, last)?;
write_back(h, &target, heap);
Ok(Value::Undef)
}
fn heappop(h: &mut PyHost, args: &[Value]) -> Result<Value, String> {
let target = args
.first()
.cloned()
.ok_or_else(|| type_error("heappop expected 1 argument"))?;
let mut heap = snapshot(h, args, 0, "heappop")?;
let lastelt = match heap.pop() {
Some(v) => v,
None => return Err("IndexError: index out of range".into()),
};
let returnitem = if heap.is_empty() {
lastelt
} else {
let top = heap[0].clone();
heap[0] = lastelt;
siftup(h, &mut heap, 0)?;
top
};
write_back(h, &target, heap);
Ok(returnitem)
}
fn heapify(h: &mut PyHost, args: &[Value]) -> Result<Value, String> {
let target = args
.first()
.cloned()
.ok_or_else(|| type_error("heapify expected 1 argument"))?;
let mut heap = snapshot(h, args, 0, "heapify")?;
for i in (0..heap.len() / 2).rev() {
siftup(h, &mut heap, i)?;
}
write_back(h, &target, heap);
Ok(Value::Undef)
}
fn heapreplace(h: &mut PyHost, args: &[Value]) -> Result<Value, String> {
let target = args
.first()
.cloned()
.ok_or_else(|| type_error("heapreplace expected 2 arguments"))?;
let item = args
.get(1)
.cloned()
.ok_or_else(|| type_error("heapreplace expected 2 arguments"))?;
let mut heap = snapshot(h, args, 0, "heapreplace")?;
if heap.is_empty() {
return Err("IndexError: index out of range".into());
}
let returnitem = heap[0].clone();
heap[0] = item;
siftup(h, &mut heap, 0)?;
write_back(h, &target, heap);
Ok(returnitem)
}
fn heappushpop(h: &mut PyHost, args: &[Value]) -> Result<Value, String> {
let target = args
.first()
.cloned()
.ok_or_else(|| type_error("heappushpop expected 2 arguments"))?;
let mut item = args
.get(1)
.cloned()
.ok_or_else(|| type_error("heappushpop expected 2 arguments"))?;
let mut heap = snapshot(h, args, 0, "heappushpop")?;
if !heap.is_empty() && lt(h, &heap[0], &item)? {
std::mem::swap(&mut item, &mut heap[0]);
siftup(h, &mut heap, 0)?;
}
write_back(h, &target, heap);
Ok(item)
}
fn sort_ascending(h: &mut PyHost, items: &mut [Value]) -> Result<(), String> {
let mut err: Option<String> = None;
items.sort_by(|a, b| {
if err.is_some() {
return std::cmp::Ordering::Equal;
}
match h.compare(NumOp::Lt, a, b) {
Ok(v) => {
if h.truthy(&v) {
std::cmp::Ordering::Less
} else {
std::cmp::Ordering::Greater
}
}
Err(e) => {
err = Some(e);
std::cmp::Ordering::Equal
}
}
});
match err {
Some(e) => Err(e),
None => Ok(()),
}
}
fn nlargest(h: &mut PyHost, args: &[Value]) -> Result<Value, String> {
let (n, iterable) = split_n_iterable(h, args, "nlargest")?;
let mut items = h.iter_items(&iterable)?;
if n <= 0 {
return Ok(h.new_list(vec![]));
}
sort_ascending(h, &mut items)?;
items.reverse();
items.truncate(n as usize);
Ok(h.new_list(items))
}
fn nsmallest(h: &mut PyHost, args: &[Value]) -> Result<Value, String> {
let (n, iterable) = split_n_iterable(h, args, "nsmallest")?;
let mut items = h.iter_items(&iterable)?;
if n <= 0 {
return Ok(h.new_list(vec![]));
}
sort_ascending(h, &mut items)?;
items.truncate(n as usize);
Ok(h.new_list(items))
}
fn split_n_iterable(h: &PyHost, args: &[Value], fname: &str) -> Result<(i64, Value), String> {
let n = args
.first()
.and_then(|v| h.as_int(v))
.ok_or_else(|| type_error(&format!("{fname}() n must be an integer")))?;
let iterable = args
.get(1)
.cloned()
.ok_or_else(|| type_error(&format!("{fname} expected 2 arguments")))?;
Ok((n, iterable))
}