hashheap 0.2.2

//! A ***HashHeap*** is a data structure that merges a priority heap with
//! a hash table.  One of the drawbacks of priority queues implemented with
//! binary heaps is that searching requires O(n) time. Other operations
//! such as arbitrary removal or replacement of values thus also require O(n).
//!

//! In a HashHeap, however, values are paired with keys. The keys are
//! hashable (`:Hash+Eq`) and the values are comparable (`:Ord`).
//! Conceptually, an internal HashMap maps keys to *indices* of where
//! values are stored inside an internal vector. Heap operations that
//! require values to be swapped must keep the hashmap consistent.
//! While the actual implementation is a bit more complicated, as it avoids
//! all cloning, this arrangement allows search to run in
//! (avearge-case) O(1) time.  Removing or replacing a value, which will
//! also require values to be swapped up or down the heap, can be done in
//! O(log n) time.
//! <br>
//!

//! Consider the possibility that the priority of objects can *change.*
//! This would require finding the object then moving it up or down the
//! queue.  With most implementations of priority heaps this is only
//! possible by removing the previous value and inserting a new one.
//! A HashHeap can be used, for example, to effectively implement Dijkstra's
//! algorithm as the "open" or "tentative" queue.  When a lower-cost path
//! is found, its position in the queue must be updated.  This is possible
//! in O(log n) time with a HashHeap.
//!
//! Two versions of the data structure are provided.
//! **Their documentation are found under structs
//! [HashHeap] and [ConstHashHeap].**  The [consthashheap] module
//! was added in Version 0.2.
//!
//! Because the mutation of values will require them to be repositioned in
//! the heap, certain expected methods are not available, including `get_mut`
//! and `iter_mut`.  Instead, a [HashHeap::modify] function is provided that
//! allows the mutation of values with a closure, and will automatically
//! adjust their positions afterwards.
//!
//! Concerning the time complexity of operations, we consider looking up a
//! hash table to be an O(1) operation, although theoretically it can be
//! worst-case O(n) with concocted examples.  They rarely occur in practice.
//! Thus all complexities are given as average case, unless otherwise noted.
//! On the other hand, worst-case scenarios for binary heaps occur easily,
//! so we note both the average and worst-case complexities when there's a
//! difference.
//!
//! Examples
//! ```
//!    use hashheap::*;
//!    let mut priority_map = HashHeap::<&str,u32>::new_minheap();
//!    priority_map.insert("A", 4);   // O(1) average, O(log n) worst
//!    priority_map.insert("B", 2);
//!    priority_map.insert("C", 1);
//!    priority_map.insert("D", 3);
//!    priority_map.insert("E", 4);
//!    priority_map.insert("F", 5);
//!    priority_map.insert("A", 6);   // insert can also modify
//!    assert_eq!(priority_map.peek(), Some((&"C",&1))); // O(1)
//!    assert_eq!(priority_map.get(&"E"), Some(&4));     // O(1)
//!    assert_eq!(priority_map[&"F"], 5);                // O(1)
//!    priority_map.modify(&"F", |v|{*v=4;});            // O(log n)
//!    priority_map.remove(&"E");                        // O(log n)
//!    assert_eq!(priority_map.pop(), Some(("C",1)));    // O(log n)
//!    assert_eq!(priority_map.pop(), Some(("B",2)));
//!    assert_eq!(priority_map.pop(), Some(("D",3)));
//!    assert_eq!(priority_map.pop(), Some(("F",4)));    
//!    assert_eq!(priority_map.pop(), Some(("A",6)));    
//!    assert_eq!(priority_map.len(), 0);
//!
//!    // version of structure with const capacity 8:
//!    let mut points = ConstHashHeap::<&str,f32,8>::new(true); // true=maxheap
//!    points.insert("mary",3.0);
//!    points.insert("larz",2.0);
//!    points.insert("narx",2.5);
//!    points.insert("parv",3.4);
//!    let mut morepoints = points.resize::<16>();  //to larger capacity
//!    morepoints.insert("oarw",3.7);
//!    morepoints.insert("qaru",2.6);
//!    morepoints.insert("nev",0.2);
//!    morepoints = morepoints.refresh();
//!    morepoints.remove(&"narx");
//!    morepoints.modify(&"larz",|x|*x += 1.2);
//!    assert_eq!(morepoints.get(&"qaru"), Some(&2.6));
//!    assert_eq!(morepoints.get(&"larz"), Some(&3.2));
//!    assert!(morepoints.get(&"narx").is_none());
//!    assert_eq!(morepoints.pop(), Some(("oarw",3.7)));
//!    assert_eq!(morepoints.size(), 5);
//! ```    
/*
Theory stuff:

For heap of size n there are always (n+1)/2 leaves
So there are n-(n+1)/2 = non-leaves, not same as (n-1)/2, because of remainder
*/

#![allow(dead_code)]
#![allow(unused_variables)]
#![allow(non_snake_case)]
#![allow(non_camel_case_types)]
#![allow(unused_parens)]
#![allow(unused_mut)]
#![allow(unused_assignments)]
#![allow(unused_doc_comments)]
#![allow(unused_imports)]
use std::cell::{Ref, RefCell, RefMut};
use std::cmp::Ord;
use std::collections::hash_map::RandomState;
use std::collections::{HashMap, HashSet};
use std::hash::{BuildHasher, Hash, Hasher};

pub mod consthashheap;
pub use consthashheap::*;

const DEFAULTCAP: usize = 16;

//// independent functions for heap indices:
fn left(i: usize) -> usize {
    2 * i + 1
}
fn right(i: usize) -> usize {
    2 * i + 2
}
fn parent(i: usize) -> usize {
    if i > 0 {
        (i - 1) / 2
    } else {
        0
    }
}

fn derive_hash<T: Hash + Eq>(rs: &RandomState, key: &T) -> usize {
    let mut bs = rs.build_hasher();
    key.hash(&mut bs);
    bs.finish() as usize
} // used by autohash


//#[cfg(feature="serde")]
//use serde::{Serialize, Deserialize};
//#[derive(Serialize, Deserialize)]
#[derive(Clone, Debug)]
pub struct HashHeap<KT, VT> {
    keys: Vec<Option<KT>>,  // None means once occupied
    vals: Vec<(VT, usize)>, // with inverse hash index (for map)
    userhash: Option<fn(&KT) -> usize>,
    rehash: fn(usize, usize) -> usize, // hashi,collisions -> newhashi
    kmap: HashMap<usize, (usize, usize)>, // hashindex to (ki,vi)
    lessthan: fn(&VT, &VT) -> bool,
    autostate: RandomState,
    minmax: bool, // record if it's min or max heap
}
impl<KT: Hash + Eq, VT: PartialOrd> HashHeap<KT, VT> {
    /// creates a HashHeap with given capacity.  If the capacity is less than 1,
    /// it defaults to 16.  If the second argument is true, a maxheap is
    /// created; otherwise a minheap is created.
    pub fn with_capacity(mut cap: usize, maxheap: bool) -> HashHeap<KT, VT> {
        if cap < 1 {
            cap = DEFAULTCAP;
        }
        let mut hh = HashHeap {
            keys: Vec::with_capacity(cap),
            vals: Vec::with_capacity(cap),
            kmap: HashMap::with_capacity(cap),
            userhash: None,
            rehash: |h, c| h + c,
            lessthan: |a, b| a < b,
            autostate: RandomState::new(),
            minmax: maxheap,
        };
        if !maxheap {
            hh.lessthan = |a, b| b < a;
        }
        hh
    } //with_capacity

    /// convenient way to create an empty min-hashheap with default capacity 16
    pub fn new_minheap() -> HashHeap<KT, VT> {
        Self::with_capacity(0, false)
    }
    /// convenient way to create an empty max-hashheap with default capacity 16  
    pub fn new_maxheap() -> HashHeap<KT, VT> {
        Self::with_capacity(0, true)
    }

    /// creates a min/max hashheap from a vector of key-value pairs.  This
    /// operation takes O(n) time, where n is the length of vector, as it uses
    /// the well-known *heapify* algorithm.  The second, bool argument determines
    /// if the heap portion of the structure is a maxheap (true) or minheap (false)
    pub fn from_pairs(kvpairs: Vec<(KT, VT)>, maxheap: bool) -> HashHeap<KT, VT> {
        let mut hh = Self::with_capacity(kvpairs.len() + 1, maxheap);
        hh.heapify(kvpairs);
        hh
    } //from_pairs

    /// This function allows the user to override the default hasher
    /// provided by the Hash trait with an arbitrary function.  The
    /// operation is only allowed while the HashHeap is empty.  Returns
    /// true on success.
    pub fn set_hash(&mut self, h: fn(&KT) -> usize) -> bool {
        if self.keys.len() > 0 {
            return false;
        }
        self.userhash = Some(h);
        true
    }

    /// Override the default rehash method, which implements linear probing.
    /// The given function take the original hash value as the first
    /// argument and the number of collisions as the second argument.  The
    /// internal representation uses the hasher from the Hash trait to compute
    /// an index, which becomes the key to a hashmap from *indices* to locations
    /// of keys and values.  Collisions are therefore resolved by a rehashing.
    /// Example for setting a quadratic probing rehash function:
    /// ```
    /// # use hashheap::*;
    ///   let mut table = HashHeap::<&str,i32>::new_minheap();
    ///   table.set_rehash(|h,c|h+c*c/2 + c/2);
    /// ```
    /// The calculated hash value does not index a vector but a rust HashMap with
    /// indices as keys, so there's no issue with out-of-bounds hash values.
    pub fn set_rehash(&mut self, rh: fn(usize, usize) -> usize) -> bool {
        if self.keys.len() > 0 {
            return false;
        }
        self.rehash = rh;
        true
    }

    /// Override the internal comparison function with a function cmp such
    /// that `cmp(a,b)` is true means a is "less than" b.  This operation
    /// is only allowed when the size of the HashHeap is no more than one.
    /// Returns true on success.
    pub fn set_cmp(&mut self, cmp: fn(&VT, &VT) -> bool) -> bool {
        if self.keys.len() > 1 {
            false
        } else {
            self.lessthan = cmp;
            true
        }
    } //set_cmp

    fn autohash(&self, key: &KT) -> usize {
        self.userhash
            .map_or(derive_hash(&self.autostate, key),
                    |f| { f(key) }
             )
    } //autohash

    // must return index of where key is found, or of an empty slot,
    // must rehash on collision
    fn findslot(&self, key: &KT) -> (usize, bool) {
        let mut h = self.autohash(key);
        let h0 = h;
        let mut collisions = 0;
        let mut reuse = None;
        while let Some((ki, vi)) = self.kmap.get(&h) {
            match &self.keys[*ki] {
                Some(key2) if key2 == key => {
                    return (h, true);
                }
                None => {
                    // rehash, set reuse
                    if let None = reuse {
                        reuse = Some(h);
                    }
                    collisions += 1;
                    //self.tc+=1;
                    h = (self.rehash)(h0, collisions);
                }
                Some(_) => {
                    //rehash, includes case where key entry is None
                    collisions += 1;
                    //self.tc+=1;
                    h = (self.rehash)(h0, collisions);
                }
            } //match
        } //while let
        reuse.map_or((h, false), |g| (g, false))
    } //findslot returns index for insert, and bool indicating exact key match
      //Here, index refers to index of kmap, not of heap vector

    /// Add or change a key-value pair, returning the replaced pair, if
    /// it exists.  This operation runs in **average-case O(1) time and
    /// worst-case O(log n) time**.
    /// Insertion into a heap is known to be average-case O(1) because the
    /// number of values on each higher level decreases geometrically, so that
    /// the average is bounded by a convergent infinite series.
    pub fn insert(&mut self, key: KT, val: VT) -> Option<(KT, VT)> {
        let (h, exists) = self.findslot(&key);
        if exists {
            let (ki, vi) = *self.kmap.get(&h).unwrap();
            let mut newkey = Some(key);
            let mut newval = (val, h);
            core::mem::swap(&mut newkey, &mut self.keys[ki]);
            core::mem::swap(&mut newval, &mut self.vals[vi]);
            self.reposition(vi);
            Some((newkey.unwrap(), newval.0))
        }
        //replace
        else {
            // assuming key is new
            let kn = self.keys.len();
            let vn = self.vals.len();
            self.keys.push(Some(key));
            self.vals.push((val, h));
            self.kmap.insert(h, (kn, vn));
            self.swapup(vn);
            None
        } //else
    } //insert

    /// Version of insert that does not replace existing key.
    /// Instead, it returns false if an equivalent key already exists.
    pub fn push(&mut self, key: KT, val: VT) -> bool {
        let (h, exists) = self.findslot(&key);
        if exists {
            false
        } else {
            // assuming key is new
            let kn = self.keys.len();
            let vn = self.vals.len();
            self.keys.push(Some(key));
            self.vals.push((val, h));
            self.kmap.insert(h, (kn, vn));
            self.swapup(vn);
            true
        } //else
    } //push

    /// This operation replaces the top (highest priority) entry
    /// with given key and value, and returns the previous top entry.
    /// However, if the given key already exists, it replaces the existing
    /// key-value with the new ones before removing the top entry.  This
    /// operation runs in O(log n) time.
    pub fn top_swap(&mut self, key: KT, val: VT) -> Option<(KT, VT)> {
        if self.vals.len() == 0 {
            self.push(key, val);
            return None;
        }
        let (h, exists) = self.findslot(&key);
        if exists {
            // replace key,val then pop
            let (ki, vi) = *self.kmap.get(&h).unwrap();
            self.keys[ki] = Some(key);
            self.vals[vi] = (val, h);
            self.reposition(vi);
            return self.pop();
        }
        // get info about top value
        let (_, it) = &self.vals[0];
        let (tki, tvi) = *self.kmap.get(it).unwrap();
        assert!(tvi == 0);
        let mut newkey = Some(key);
        let mut newval = (val, h);
        core::mem::swap(&mut newkey, &mut self.keys[tki]);
        core::mem::swap(&mut newval, &mut self.vals[0]);
        self.kmap.insert(h, (tki, 0));
        self.swapdown(0);
        Some((newkey.unwrap(), newval.0))
    } //swap

    /// Returns the key-value pair with the highest priority value (smallest
    /// or largest depending on minheap or maxheap).  This operation runs in
    /// O(1) time
    pub fn peek(&self) -> Option<(&KT, &VT)> {
        if self.vals.len() == 0 {
            return None;
        }
        let (v, hv) = &self.vals[0];
        let k = self.kmap.get(hv).unwrap().0;
        Some((self.keys[k].as_ref().unwrap(), v))
    } //peek

    /// Removes and returns the key-value pair with highest priority value
    /// (smallest or largest depending on minheap or maxheap).  This operation
    /// runs in O(log n) time
    pub fn pop(&mut self) -> Option<(KT, VT)> {
        let vn = self.vals.len();
        if vn == 0 {
            return None;
        }
        self.heapswap(0, vn - 1);
        let mut Kopt = None;
        let (V, iv) = self.vals.pop().unwrap();
        let (ki, vi) = *self.kmap.get(&iv).unwrap();
        core::mem::swap(&mut self.keys[ki], &mut Kopt);
        // entry persist in kmap for rehashing
        self.swapdown(0);
        Some((Kopt.unwrap(), V))
    } //pop

    /// returns the value associated with the given key, if it exists.  
    /// Indexed access is also available, but will panic if the key is not found.
    /// This operation runs in O(1) time.
    ///
    /// Note that **there is no `get_mut` operation** as mutations will
    /// require values to be repositioned in the heap.  Call instead the
    /// [HashHeap::modify] operation.
    pub fn get(&self, key: &KT) -> Option<&VT> {
        //O(1)
        if let (h, true) = self.findslot(key) {
            let (_, vi) = self.kmap[&h];
            Some(&self.vals[vi].0)
        } else {
            None
        }
    } //get

    /// This operation applies the mutating closure to the value associated
    /// with the key, if it exists.  It then adjusts the position of the
    /// value inside the heap.  It returns true on success and false if
    /// the key was not found. This operation runs in O(log n) time in addition
    /// to the cost of calling the closure.
    pub fn modify<F>(&mut self, key: &KT, mapfun: F) -> bool
    where
        F: FnOnce(&mut VT),
    {
        if let (h, true) = self.findslot(key) {
            let (_, vi) = self.kmap[&h];
            mapfun(&mut self.vals[vi].0);
            self.reposition(vi);
            true
        } else {
            false
        }
    } //modify

    /// Removes and returns the key-value pair with the given key reference, if it
    /// exists.  This operation runs in O(log n) time.
    pub fn remove(&mut self, key: &KT) -> Option<(KT, VT)> {
        if let (h, true) = self.findslot(key) {
            let (ki, vi) = self.kmap[&h];
            self.heapswap(vi, self.vals.len() - 1);
            let (V, _) = self.vals.pop().unwrap();
            //if vi < self.vals.len() {self.reposition(vi);}  //vi was not popped
            self.reposition(vi);
            let mut K = None;
            core::mem::swap(&mut K, &mut self.keys[ki]);
            Some((K.unwrap(), V))
        } else {
            None
        }
    } //remove

    /// Determines if the given key exists in the HashHeap. This is an
    /// O(1) operation.
    pub fn contains_key(&self, key: &KT) -> bool {
        // O(1)
        self.findslot(key).1
    }

    /// Determines if the given value exists in the table.  This operation
    /// **runs in O(n) time**.
    pub fn contains_val(&self, val: &VT) -> bool {
        // O(n)
        self.valsearch(0, val)
    }
    fn valsearch(&self, root: usize, val: &VT) -> bool {
        if root >= self.vals.len() {
            false
        } else if &self.vals[root].0 == val {
            true
        } else if (self.lessthan)(&self.vals[root].0, val) {
            false
        } else {
            self.valsearch(left(root), val) || self.valsearch(right(root), val)
        }
    }

    // treat as maxheap
    fn swapup(&mut self, mut i: usize) -> usize {
        if i >= self.vals.len() {
            return i;
        }
        let mut p = parent(i);
        while i > 0 && (self.lessthan)(&self.vals[p].0, &self.vals[i].0) {
            self.heapswap(i, p);
            i = p;
            p = parent(i);
        } //while
        i
    } //swapup returns final position of ith val

    fn swapdown(&mut self, mut i: usize) -> usize {
        let size = self.vals.len();
        let nonleaves = size - ((size + 1) / 2);
        let mut sc = 0;
        while (i < nonleaves && sc != usize::MAX) {
            // refine
            sc = usize::MAX;
            let li = left(i);
            let ri = right(i);
            if li < size && (self.lessthan)(&self.vals[i].0, &self.vals[li].0) {
                sc = li;
            }
            if ri < size
                && (self.lessthan)(&self.vals[i].0, &self.vals[ri].0)
                && (self.lessthan)(&self.vals[li].0, &self.vals[ri].0)
            {
                sc = ri;
            }
            if (sc != usize::MAX) {
                //swap
                self.heapswap(i, sc);
                i = sc;
            }
        } //while
        i
    } //swapdown

    fn reposition(&mut self, i: usize) -> usize {
        let mut ni = self.swapup(i);
        if ni == i {
            ni = self.swapdown(i);
        }
        ni
    } //reposition

    // swap values at indices i, j in vals, re-associate
    fn heapswap(&mut self, i: usize, j: usize) {
        if i == j {
            return;
        }
        let ih = self.vals[i].1; //hash-index of corresponding key
        let jh = self.vals[j].1;
        self.vals.swap(i, j);
        self.kmap.get_mut(&ih).map(|(_, vi)| {
            *vi = j;
        });
        self.kmap.get_mut(&jh).map(|(_, vj)| {
            *vj = i;
        });
        // hash-index does not change- need for future lookup
    } // swap values in vals, re-associate

    fn heapify(&mut self, vkv: Vec<(KT, VT)>) {
        if self.keys.len() > 0 {
            self.keys.clear();
            self.vals.clear();
            self.kmap.clear();
        }
        let vn = vkv.len();
        let nonleafs = vn - (vn + 1) / 2;
        let mut vi = 0;
        for (k, v) in vkv {
            let (kh, _) = self.findslot(&k);
            self.keys.push(Some(k));
            self.vals.push((v, kh));
            self.kmap.insert(kh, (vi, vi));
            vi += 1;
        } //for
        vi = nonleafs;
        while vi > 0 {
            // heapify loop
            self.swapdown(vi - 1);
            vi -= 1;
        } //while
    } //heapify

    /// returns the number of key-value pairs in the HashHeap in constant time.
    pub fn len(&self) -> usize {
        self.vals.len()
    }

    /// reserves additional capacity
    pub fn reserve(&mut self, additional: usize) {
        self.kmap.reserve(additional);
        self.vals.reserve(additional);
        self.keys.reserve(additional);
    } //reserve

    /// clears HashHeap without changing capacity.  Also resets [RandomState]
    /// for hasher.
    pub fn clear(&mut self) {
        self.vals.clear();
        self.keys.clear();
        self.kmap.clear();
        self.autostate = RandomState::new();
    } //clear

    /// returns true if the structure is a max-hashheap and false if it's a
    /// min-hashheap.
    pub fn is_max_hashheap(&self) -> bool {
        self.minmax
    }

    /*
    pub fn diagnostic(&self) {
      if self.tc>0 {println!("total collisions: {}",self.tc);}
    }
    */
} // impl HashHeap

//default
impl<KT: Hash + Eq, VT: PartialOrd> Default for HashHeap<KT, VT> {
    fn default() -> Self {
        Self::new_maxheap()
    }
} // impl default

/*
use core::fmt::Debug;
impl<KT: Hash + Eq + Debug, VT: PartialOrd + Debug> Debug for HashHeap<KT, VT> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        let mut fp = f.pad("HashHeap: [\n");
        let width = 14;
        for (key, val) in self.iter() {
            fp = f.pad(&format!("  key {:?}  :  value {:?}\n", key, val));
        }
        fp = f.pad("]\n");
        fp
    }
} // impl default

impl<KT: Hash + Eq + Clone, VT: PartialOrd + Clone> Clone for HashHeap<KT, VT> {
    fn clone(&self) -> Self {
        HashHeap {
            keys: self.keys.clone(),
            vals: self.vals.clone(),
            userhash: self.userhash.clone(),
            rehash: self.rehash.clone(),
            kmap: self.kmap.clone(),
            lessthan: self.lessthan.clone(),
            autostate: self.autostate.clone(),
            minmax: self.minmax,
        }
    } //clone
} // impl clone
*/

/// indexed get
impl<KT: Hash + Eq, VT: PartialOrd> core::ops::Index<&KT> for HashHeap<KT, VT> {
    type Output = VT;
    fn index(&self, index: &KT) -> &Self::Output {
        self.get(index).expect("key not found")
    }
} //impl Index

/// The implementation of this `From` trait always returns a max-hashheap.
/// For a min-hashheap, call instead [HashHeap::from_pairs]
impl<KT: Hash + Eq, VT: PartialOrd> From<Vec<(KT, VT)>> for HashHeap<KT, VT> {
    fn from(v: Vec<(KT, VT)>) -> HashHeap<KT, VT> {
        HashHeap::from_pairs(v, true)
    }
}

/// The implementation of this `From` trait always returns a min-hashheap.
/// For a max-hashheap, call [Iterator::collect] followed by [HashHeap::from_pairs]
impl<KT: Hash + Eq, VT: PartialOrd> FromIterator<(KT, VT)> for HashHeap<KT, VT> {
    fn from_iter<T: IntoIterator<Item = (KT, VT)>>(iter: T) -> HashHeap<KT, VT> {
        HashHeap::from_pairs(iter.into_iter().collect(), false)
    }
}

////// iterator implementations

/// This iterator is returned by the [HashHeap::keys] function
pub struct KeyIter<'a, KT> {
    keys: &'a [Option<KT>],
    index: usize,
}
impl<'a, KT> Iterator for KeyIter<'a, KT> {
    type Item = &'a KT;
    fn next(&mut self) -> Option<Self::Item> {
        let kn = self.keys.len();
        while self.index < kn && self.keys[self.index].is_none() {
            self.index += 1;
        }
        if self.index >= kn {
            None
        } else {
            self.index += 1;
            self.keys[self.index - 1].as_ref()
        }
    } //next
} // keys iterator

/// This iterator is returned by the [HashHeap::values] function
pub struct ValIter<'a, VT> {
    vals: &'a [(VT, usize)],
    index: usize,
}
impl<'a, VT> Iterator for ValIter<'a, VT> {
    type Item = &'a VT;
    fn next(&mut self) -> Option<Self::Item> {
        let vn = self.vals.len();
        if self.index >= vn {
            None
        } else {
            self.index += 1;
            Some(&self.vals[self.index - 1].0)
        }
    } //next
} // vals iterator

/// This iterator is returned by the [HashHeap::iter] function
pub struct KeyValIter<'a, KT, VT> {
    hh: &'a HashHeap<KT, VT>,
    index: usize,
}
impl<'a, KT: Hash + Eq, VT: PartialOrd> Iterator for KeyValIter<'a, KT, VT> {
    type Item = (&'a KT, &'a VT);
    fn next(&mut self) -> Option<Self::Item> {
        let vn = self.hh.vals.len();
        while self.index < vn {
            let (v, iv) = &self.hh.vals[self.index];
            self.index += 1;
            let (ki, _) = self.hh.kmap[iv];
            if let Some(k) = &self.hh.keys[ki] {
                return Some((k, v));
            }
        }
        None
    } //next
} // key-val iterator

impl<'a, KT: Hash + Eq, VT: PartialOrd> HashHeap<KT, VT> {
    /// returns an iterator over the keys of the structure in no particular
    /// order
    pub fn keys(&'a self) -> KeyIter<'a, KT> {
        KeyIter {
            keys: &self.keys,
            index: 0,
        }
    } //keys

    /// returns an iterator over the values of the structure in no particular
    /// order
    pub fn values(&'a self) -> ValIter<'a, VT> {
        ValIter {
            vals: &self.vals,
            index: 0,
        }
    } //values

    /// returns an iterator over `(key,value)` pairs of the structure
    /// in no particular order.
    ///
    /// Note that, because of the need to swap values up or down the
    /// heap after a mutation, there is no `iter_mut` available.  Use the
    /// [HashHeap::modify] operation to mutate single values instead.
    pub fn iter(&'a self) -> KeyValIter<'a, KT, VT> {
        KeyValIter { hh: self, index: 0 }
    }

    /// returns a consuming iterator over `(key,value)` in order of
    /// priority (via [Self::pop]).  The hashheap will be emptied by
    /// the iterator
    pub fn priority_stream(&'a mut self) -> PriorityQueue<'a,KT,VT> {
       PriorityQueue(self)
    }
} // impl iterators

/// The IntoIterator for references is the same as calling [HashHeap::iter],
/// and will therefore return references in **arbitrary order**.
impl<'t, KT: Hash + Eq, VT: PartialOrd> IntoIterator for &'t HashHeap<KT, VT> {
    type Item = (&'t KT, &'t VT);
    type IntoIter = KeyValIter<'t, KT, VT>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
} //IntoIter for references

/// Consuming iterator, type for [IntoIterator].  This iterator will
/// call [HashHeap::pop] for the next (key,value) pair, and will thus
/// return the values in **sorted order** (increasing for min-hashheap,
/// decreasing for max-hashheap). The cost of any for-loop over this
/// iterator is thus at least O(n*log n).
/// In constrast, the non-consuming iterators all enumerate references
/// in arbitrary order.
pub struct IntoIter<KT, VT>(HashHeap<KT, VT>);
impl<KT: Hash + Eq, VT: PartialOrd> Iterator for IntoIter<KT, VT> {
    type Item = (KT, VT);
    fn next(&mut self) -> Option<(KT, VT)> {
        self.0.pop()
    }
} //impl IntoIter

/// The consuming iterator is implemented by [IntoIter] and will return
/// the owned values in **sorted order**
impl<KT: Hash + Eq, VT: PartialOrd> IntoIterator for HashHeap<KT, VT> {
    type Item = (KT, VT);
    type IntoIter = IntoIter<KT, VT>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter(self)
    }
} // consuming iterator

/// Non-consuming iterator, but will empty the heap via pop()
pub struct PriorityQueue<'a,KT,VT>(&'a mut HashHeap<KT,VT>);
impl<'a,KT: Hash + Eq, VT: PartialOrd> Iterator
for PriorityQueue<'a,KT,VT>
{
  type Item = (KT,VT);
  fn next(&mut self) -> Option<Self::Item> {
    self.0.pop()
  }
}

//////////testing
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn it_works() {
        let mut priority_map = HashHeap::<&str, u32>::new_minheap();
        priority_map.insert("A", 4); // O(1) average, O(log n) worst
        priority_map.insert("B", 2);
        priority_map.insert("C", 1);
        priority_map.insert("D", 3);
        priority_map.insert("E", 4);
        priority_map.insert("F", 5);
        priority_map.insert("A", 6); // insert can also modify
                                     // iterator tests:
        let mut total = 0;
        for (key, val) in &priority_map {
            println!("iterator key {} : val {}", key, val);
            total += val;
        }
        assert_eq!(total, 21);

        for (key, val) in priority_map {
            println!("consuming iterator key {} : val {}", key, val);
        }
    } //it_works
} //tests module