Struct U64RadixAddressableHeap 

pub struct U64RadixAddressableHeap<V> { /* private fields */ }

An addressable monotone radix heap for u64 keys.

Handles are checked for foreign and stale use. As with every radix heap in this module, fallible insertion and key-update methods enforce range and monotonicity restrictions.

Examples

use rheaps::monotone::U64RadixAddressableHeap;

let mut heap = U64RadixAddressableHeap::new(0, 100).unwrap();
let task = heap.try_insert(30, "compile report").unwrap();
heap.try_insert(10, "answer mail").unwrap();

heap.decrease_key(task, 20).unwrap();
assert_eq!(heap.peek().map(|(_, key, _)| *key), Some(10));
assert_eq!(heap.delete(task), Ok((20, "compile report")));

Implementations

impl<V> U64RadixAddressableHeap<V>

pub fn new(minimum_key: u64, maximum_key: u64) -> Result<Self, RadixHeapError>

Creates an empty addressable radix heap with inclusive bounds.

pub fn with_bounds( minimum_key: u64, maximum_key: u64, ) -> Result<Self, RadixHeapError>

Alias for Self::new.

pub fn minimum_key(&self) -> &u64

Returns the inclusive lower key bound.

pub fn maximum_key(&self) -> &u64

Returns the inclusive upper key bound.

pub fn last_deleted_key(&self) -> &u64

Returns the most recently removed key, or the lower bound if no key has yet been removed or the heap was cleared.

pub fn bucket_count(&self) -> usize

Returns the fixed number of radix buckets.

pub fn try_insert( &mut self, key: u64, value: V, ) -> Result<RadixHandle, RadixHeapError>

Inserts a key-value entry and returns its handle.

pub fn peek(&self) -> Option<(RadixHandle, &u64, &V)>

Returns the handle, key, and value of the minimum entry.

pub fn pop(&mut self) -> Option<(u64, V)>

Removes and returns the minimum entry.

pub fn key(&self, handle: RadixHandle) -> Result<&u64, InvalidHandle>

Returns the key addressed by handle.

pub fn value(&self, handle: RadixHandle) -> Result<&V, InvalidHandle>

Returns the value addressed by handle.

pub fn value_mut( &mut self, handle: RadixHandle, ) -> Result<&mut V, InvalidHandle>

Returns mutable access to the value addressed by handle.

pub fn decrease_key( &mut self, handle: RadixHandle, key: u64, ) -> Result<(), RadixDecreaseKeyError>

Decreases an entry’s key while preserving the monotonicity restriction.

pub fn delete(&mut self, handle: RadixHandle) -> Result<(u64, V), InvalidHandle>

Removes and returns the entry addressed by handle.

pub fn len(&self) -> usize

Returns the number of live entries.

pub fn is_empty(&self) -> bool

Returns whether the heap contains no entries.

pub fn clear(&mut self)

Removes all entries, invalidates their handles, and resets the monotonicity constraint.

Trait Implementations

impl<V> TryAddressableHeap<u64, V> for U64RadixAddressableHeap<V>

type Handle = RadixHandle

Opaque type that identifies a live entry in this heap.

type InsertError = RadixHeapError

Error returned when an entry cannot be inserted.

fn try_insert( &mut self, key: u64, value: V, ) -> Result<Self::Handle, Self::InsertError>

Attempts to insert an entry and returns its handle.

fn peek(&self) -> Option<(Self::Handle, &u64, &V)>

Returns the handle, key, and value of a minimum entry, if present.

fn pop(&mut self) -> Option<(u64, V)>

Removes and returns a minimum entry, if present.

fn key(&self, handle: Self::Handle) -> Result<&u64, InvalidHandle>

Returns the key identified by handle.

fn value(&self, handle: Self::Handle) -> Result<&V, InvalidHandle>

Returns the value identified by handle.

fn value_mut(&mut self, handle: Self::Handle) -> Result<&mut V, InvalidHandle>

Returns mutable access to the value identified by handle.

fn delete(&mut self, handle: Self::Handle) -> Result<(u64, V), InvalidHandle>

Removes and returns the entry identified by handle.

fn len(&self) -> usize

Returns the number of live entries.

fn clear(&mut self)

Removes all entries and invalidates every outstanding handle.

fn is_empty(&self) -> bool

Returns whether the heap contains no entries.

impl<V> TryDecreaseKeyHeap<u64, V> for U64RadixAddressableHeap<V>

type DecreaseKeyError = RadixDecreaseKeyError

Error returned when a key decrease cannot be performed.

fn decrease_key( &mut self, handle: Self::Handle, key: u64, ) -> Result<(), Self::DecreaseKeyError>

Decreases the key identified by handle.