So I thought I would try making my Heap code generic. This is the result. The part that is a bit messy is converting U (which will typically be instantiated as either u32 or usize) to usize and vice-versa, I have functions z and u to do this, which I have to use a lot... I was wondering if there was a cooler way to do this ( I don't think so... but there is so much I don't know ). Doc for this code is here: GHeap in rustdb::pstore - Rust

```
#[derive(Default)]
/// Heap Node.
pub struct HeapNode<K, T, U> {
/// Index of node from heap position.
pub x: U,
/// Heap position of this node.
pub pos: U,
/// Node id.
pub id: T,
/// Node key.
pub key: K,
}
/// Heap for tracking least used page.
pub struct GHeap<K, T, U> {
/// Number of heap nodes, not including free nodes.
pub n: usize,
/// 1 + Index of start of free list.
pub free: usize,
/// Vector of heap nodes.
pub v: Vec<HeapNode<K, T, U>>,
}
impl<K, T, U> Default for GHeap<K, T, U>
where
K: Default,
T: Default,
{
fn default() -> Self {
Self {
v: Vec::new(),
n: 0,
free: 0,
}
}
}
impl<K, T, U> GHeap<K, T, U>
where
K: Default + Ord + Copy,
T: Default + Copy,
U: Copy + Default + TryFrom<usize>,
usize: TryFrom<U>,
{
/// Insert id into heap with specified key (usage). Result is index of heap node.
pub fn insert(&mut self, id: T, key: K) -> U {
let pos = self.n;
self.n += 1;
let x = self.alloc(pos);
self.v[x].id = id;
self.v[x].key = key;
self.move_up(pos, x, key);
Self::z(x)
}
/// Modify key of specified heap node.
pub fn modify(&mut self, x: U, newkey: K) {
let x = Self::u(x);
let pos = Self::u(self.v[x].pos);
let oldkey = self.v[x].key;
self.v[x].key = newkey;
match newkey.cmp(&oldkey) {
Ordering::Greater => self.move_down(pos, x, newkey),
Ordering::Less => self.move_up(pos, x, newkey),
Ordering::Equal => (),
}
}
/// Remove heap node with smallest key, returning the associated id.
/// Note: index of heap node is no longer valid.
pub fn pop(&mut self) -> T {
assert!(self.n > 0);
self.n -= 1;
let xmin = Self::u(self.v[0].x); // Node with smallest key.
let xlast = Self::u(self.v[self.n].x); // Last node in heap.
self.v[xlast].pos = Self::z(0); // Make last node first.
self.v[0].x = Self::z(xlast);
self.move_down(0, xlast, self.v[xlast].key);
// De-allocate popped node
self.v[xmin].pos = Self::z(self.free);
self.free = xmin + 1;
self.v[xmin].id
}
fn move_up(&mut self, mut c: usize, cx: usize, ck: K) {
while c > 0 {
let p = (c - 1) / 2;
let px = Self::u(self.v[p].x);
if ck >= self.v[px].key {
return;
}
// Swap parent(p) and child(c).
self.v[p].x = Self::z(cx);
self.v[c].x = Self::z(px);
self.v[px].pos = Self::z(c);
self.v[cx].pos = Self::z(p);
c = p;
}
}
fn move_down(&mut self, mut p: usize, px: usize, pk: K) {
loop {
let mut c = p * 2 + 1;
if c >= self.n {
return;
}
let mut cx = Self::u(self.v[c].x);
let mut ck = self.v[cx].key;
let c2 = c + 1;
if c2 < self.n {
let cx2 = Self::u(self.v[c2].x);
let ck2 = self.v[cx2].key;
if ck2 < ck {
c = c2;
cx = cx2;
ck = ck2;
}
}
if ck >= pk {
return;
}
// Swap parent(p) and child(c).
self.v[p].x = Self::z(cx);
self.v[c].x = Self::z(px);
self.v[px].pos = Self::z(c);
self.v[cx].pos = Self::z(p);
p = c;
}
}
fn alloc(&mut self, pos: usize) -> usize {
let x = if self.free == 0 {
self.v.push(HeapNode::default());
self.v.len() - 1
} else {
let x = self.free - 1;
self.free = Self::u(self.v[x].pos);
x
};
self.v[pos].x = Self::z(pos);
self.v[x].pos = Self::z(x);
x
}
fn z(x: usize) -> U {
match U::try_from(x) {
Ok(y) => y,
Err(_) => panic!(),
}
}
fn u(x: U) -> usize {
match usize::try_from(x) {
Ok(y) => y,
Err(_) => panic!(),
}
}
}
```