/*  custom "hashheap"
*/
use std::collections::HashMap;
use std::hash::Hash;
use std::cmp::Ord;

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} }


pub trait HashHeapValue<KT> {
  fn getkey(&self) -> &KT;
}// trait HashHeapValue

//must assume that key passed to push is consistent with val.getkey()

pub struct HashHeap<KT:Hash, VT:Ord>
{
   heap: Vec<VT>,
   hash: HashMap<KT,usize>, // from keys to value indices
   cmp: fn(&VT,&VT) -> bool, // less than
}
impl<KT:Hash+Eq, VT:Ord+HashHeapValue<KT>> HashHeap<KT,VT>
{
   pub fn minheap(mut cap:usize) -> Self {
     if cap<1 {cap=DEFAULTCAP;}
     HashHeap {
       heap: Vec::with_capacity(cap),
       hash: HashMap::with_capacity(cap),
       cmp: |x,y|{x<y},
     }
   }//minheap new

   pub fn maxheap(mut cap:usize) -> Self {
     if cap<1 {cap=DEFAULTCAP;}
     HashHeap {
       heap: Vec::with_capacity(cap),
       hash: HashMap::with_capacity(cap),
       cmp: |x,y|{y<x},
     }
   }//maxheap new

   pub fn len(&self) -> usize { self.heap.len() }

   pub fn insert(&mut self, key:KT, val:VT) -> bool {
      if val.getkey() != &key {return false;}
      let size = self.heap.len();
      if size==self.heap.capacity() {self.resize();}
      self.heap.push(val);
      self.hash.insert(key,size);      
      self.swapup(size);
      true
   }//push, returns true if key matches val.getkey(),

   pub fn peek(&mut self) -> Option<&VT> { self.heap.get(0) }

   pub fn pop(&mut self) -> Option<VT> {
    if self.heap.len()==0 {return None;}
    let k0 = self.heap[0].getkey();
    self.hash.remove(k0);        
    if self.heap.len()==1 {      return self.heap.pop();    }
    let answer = Some(self.heap.swap_remove(0));
    self.associate(0);
    self.swapdown(0);    
    answer
   }//pop

   pub fn get(&self, key:&KT) -> Option<&VT> {
     self.hash.get(key).map(|i|self.heap.get(*i)).flatten()
   }// get

   pub fn get_mut(&mut self, key:&KT) -> Option<&mut VT> {
     self.hash.get(key).map(|i|self.heap.get_mut(*i)).flatten()
   }//get_mut

   ///in-place modification of value, followed by requeue
   pub fn modify<F>(&mut self, key:&KT, f:F) -> bool
      where F:FnOnce(&mut VT)
   {
      let moded = self.get_mut(key).map(|val|f(val));
      if moded.is_some() { self.requeue(key) }
      else {false}
   }//modify

   pub fn requeue(&mut self, key:&KT) -> bool {
      let opti = self.hash.get(key);
      if opti.is_none() {return false;}
      let i = *opti.unwrap();
      let ni = self.swapup(i);
      if ni==i {self.swapdown(i);}
      true
   }//requeue
   pub fn reposition(&mut self, val:&VT) -> bool {
      self.requeue(val.getkey())
   }

   pub fn contains_key(&self, key:&KT) -> bool {
     self.check_key(key)
   }// contains

   pub fn contains_value(&self, val:&VT) -> bool {
     self.check_key(val.getkey())
   }// contains

   pub fn take(&mut self, key:&KT) -> Option<VT> {
     let opti = self.hash.get(key);
     if opti.is_none() {return None;}
     let i = *opti.unwrap(); //make copy, safe to mut later
     self.hash.remove(key);
     if self.heap.len()+1==i {return self.heap.pop();}
     let answer = Some(self.heap.swap_remove(i));
     self.associate(i);
     self.swapdown(i);
     answer
   }//take

   fn associate(&mut self, i:usize) {
      let ik = self.heap[i].getkey();
      self.hash.get_mut(ik).map(|j|{*j=i;});
   }//associate

   fn check_key(&self, key:&KT) -> bool {
      self.hash.get(key)
      .map(|ki|self.heap[*ki].getkey() == key)
      .unwrap_or(false)
   }//check_key

   fn check_index(&self, i:usize) -> bool {
     self.heap.get(i)
     .map(|val|{
       self.hash.get(val.getkey())
       .map(|k|k==&i)
      })
     .flatten()
     .unwrap_or(false)
   }//check_index


   fn swapup(&mut self, mut i:usize) -> usize {
      let size = self.heap.len();
      if i>=size {return i;} // not possible
      let mut pi = parent(i);
      while i>0 && (self.cmp)(&self.heap[i], &self.heap[pi]) {
        self.heap.swap(i,pi);
        self.associate(i);
        self.associate(pi);
	i = pi;  pi = parent(i);
      }
      return i;
   }//swapup

   fn swapdown(&mut self, mut i:usize) -> usize {
      let size = self.heap.len();
      if i>=size {return i;}
      let mut sc = 0; //swap candidate
      while sc<size {
        sc = size;
        let li = left(i);
	let ri = right(i);
	if li<size && (self.cmp)(&self.heap[li],&self.heap[i]) {sc=li;}
	if ri<size && (self.cmp)(&self.heap[ri],&self.heap[i])
                   && (self.cmp)(&self.heap[ri],&self.heap[li]) {
	  sc = ri;
	}
	if sc<size {
	  self.heap.swap(i,sc);
          self.associate(i);
          self.associate(sc);
	  i = sc;
	} //swap
      }//while
      return i;
   }//swapdown

   fn resize(&mut self) {
      let n = self.heap.len();
      self.heap.reserve(n);
      self.hash.reserve(n);
   }//double capacities
}//impl HashHeap


impl<KT:Hash+Eq+Clone, VT:Ord+HashHeapValue<KT>> HashHeap<KT,VT> {
   pub fn push(&mut self, val:VT) {
     let key = val.getkey().clone();
     self.insert(key,val);
   }

   pub fn heapify(&mut self, v:Vec<VT>) {
     self.heap = v;
     self.hash.clear();
     for i in 0..self.heap.len() {
        self.hash.insert(self.heap[i].getkey().clone(), i);
     }
     let size = self.heap.len();
     let mut i = size - ((size+1)/2);  //number of non-leave nodes
     while i > 0 {
       i -= 1;
       self.swapdown(i);
     }//swapdowns
   }//heapify
}//impl HashHeap, assuming keys can be copied

/*
fn main() {

  let mut mh = MinHeap::<Node>::new();
  for i in [4,8,1,2,5,9,3,2,8,12] {
    println!("index {} for {}",mh.push(Node::new(i)),i);
  }
  mh.peek().map(|node|{println!("node with id {}",&node.id);});  
  let n = Node::new(7);
  let ni = mh.push(n);
  mh.peek_at(ni).map(|node|{node.id=0;});
  println!("{} after requeue: {}",&ni, &mh.requeue(ni));
  while let Some(node) = mh.pop() {
    println!("got node with id {}",&node.id);
  }
}//main



pub struct HashVec<'lt,T>
{
   vector: Vec<T>,
   hash: HashMap<&'lt T, usize>, // hash T back to index in vec
}
impl<'lt,T:Eq+Hash+'lt> HashVec<'lt,T>
{
  fn new() -> Self {
    HashVec { vector:Vec::new(),  hash:HashMap::new(), }
  }//new
  fn push(&mut self, x:T) {
    let ti = self.vector.len();
    self.vector.push(x);
    self.hash.insert(&self.vector[ti], ti);
  }//push
}//impl HashVec
*/