rs-graph 0.14.1

// Copyright (c) 2016, 2017 Frank Fischer <frank-fischer@shadow-soft.de>
//
// This program is free software: you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

//! Binary heap implementation

use shortestpath::heap::Heap;

use num::traits::PrimInt;

/// Heap item information.
struct BinHeapItem<K, ID> {
    /// The key associated with this item.
    key: K,
    /// Position of this element on the heap. If this element is *not*
    /// on the heap, its the index of the next element in the free
    /// list.
    pos: ID,
}

/// Simply binary heap data structure.
pub struct BinHeap<K, ID = u32> {
    /// The heap elements.
    heap: Vec<ID>,
    /// The key and heap-index for each element.
    data: Vec<BinHeapItem<K, ID>>,
    /// First free item.
    free: Option<ID>,
}

impl<K, ID> Heap for BinHeap<K, ID>
where
    K: Copy + PartialOrd,
    ID: PrimInt,
{
    type Item = ID;
    type Key = K;

    fn new() -> Self {
        BinHeap {
            heap: vec![],
            data: vec![],
            free: None,
        }
    }

    fn clear(&mut self) {
        self.heap.clear();
        self.data.clear();
        self.free = None;
    }

    fn is_empty(&self) -> bool {
        self.heap.is_empty()
    }

    fn insert(&mut self, key: K) -> ID {
        let item = if let Some(i) = self.free {
            let next = self.data[i.to_usize().unwrap()].pos;
            if next == i {
                self.free = None
            } else {
                self.free = Some(next)
            }
            self.data[i.to_usize().unwrap()].key = key;
            self.data[i.to_usize().unwrap()].pos = ID::from(self.heap.len()).unwrap();
            i
        } else {
            let item = ID::from(self.data.len()).unwrap();
            self.data.push(BinHeapItem {
                key: key,
                pos: ID::from(self.heap.len()).unwrap(),
            });
            item
        };
        self.heap.push(item);
        self.decrease(item);
        item
    }

    fn decrease(&mut self, item: ID) {
        let mut cur = self.data[item.to_usize().unwrap()].pos.to_usize().unwrap();
        let key = self.data[item.to_usize().unwrap()].key;
        while cur > 0 {
            let par = (cur - 1) / 2;
            let paritem: ID = self.heap[par];
            if key >= self.data[paritem.to_usize().unwrap()].key {
                break;
            }
            self.heap[cur] = paritem;
            self.data[paritem.to_usize().unwrap()].pos = ID::from(cur).unwrap();
            cur = par;
        }
        self.heap[cur] = item;
        self.data[item.to_usize().unwrap()].pos = ID::from(cur).unwrap();
    }

    fn pop_min(&mut self) -> Option<Self::Key> {
        if self.heap.is_empty() {
            return None;
        }
        let minindex = self.heap.swap_remove(0);

        if let Some(next) = self.free {
            self.data[minindex.to_usize().unwrap()].pos = next;
        } else {
            self.data[minindex.to_usize().unwrap()].pos = minindex;
        }
        self.free = Some(minindex);

        if !self.heap.is_empty() {
            let n = self.heap.len();
            let item = *self.heap.first().unwrap();
            let key: K = self.data[item.to_usize().unwrap()].key;
            let mut cur = 0;
            loop {
                let left = 2 * cur + 1;
                let right = left + 1;
                let next = if right >= n
                    || self.data[self.heap[left].to_usize().unwrap()].key
                        < self.data[self.heap[right].to_usize().unwrap()].key
                {
                    left
                } else {
                    right
                };
                if next >= n || key <= self.data[self.heap[next].to_usize().unwrap()].key {
                    break;
                }
                self.heap[cur] = self.heap[next];
                self.data[next].pos = ID::from(cur).unwrap();
                cur = next;
            }
            self.heap[cur] = item;
            self.data[item.to_usize().unwrap()].pos = ID::from(cur).unwrap();
        }
        Some(self.data[minindex.to_usize().unwrap()].key)
    }

    fn key(&mut self, item: ID) -> &mut K {
        &mut self.data[item.to_usize().unwrap()].key
    }
}