/*
* lftp - file transfer program
*
* Copyright (c) 1996-2013 by Alexander V. Lukyanov (lav@yars.free.net)
*
* 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/>.
*/
#ifndef XHEAP_H
#define XHEAP_H 1
// min-heap implementation with random remove
#include <assert.h>
#include "xarray.h"
#define costly_assert(x) /*assert(x)*/
template<class T>
class xheap
{
public:
class node
{
T *obj;
int heap_index;
friend class xheap<T>;
public:
node(T *t) : obj(t), heap_index(0) {}
};
private:
xarray<node*> heap;
int count() const { return heap.count(); }
node*& ptr(int i) { return heap[i-1]; }
T& elem(int i) { return *(ptr(i)->obj); }
void swap(int a,int b) {
ptr(a)=replace_value(ptr(b),ptr(a));
ptr(a)->heap_index=a;
ptr(b)->heap_index=b;
}
void siftup(int i) {
while(i>1 && elem(i)<elem(i/2)) {
swap(i,i/2);
i/=2;
}
}
void siftdown(int i) {
while(i<=count()/2) {
int i2=i*2;
// choose smallest of heirs
if(i2<count() && elem(i2+1)<elem(i2))
i2++;
if(elem(i)<elem(i2))
break;
swap(i,i2);
i=i2;
}
}
bool is_heap(int a,int b) {
while(a*2<=b) {
if(elem(a*2)<elem(a))
return false;
a++;
}
return true;
}
void chop() {
ptr(count())->heap_index=0;
heap.chop();
}
void fix(int i) {
siftdown(i);
siftup(i);
}
void remove(int i) {
if(i==count()) {
chop();
return;
}
assert(i>0 && i<count());
swap(i,count());
chop();
fix(i);
costly_assert(is_heap(1,count()));
}
public:
void add(node& n) {
if(n.heap_index) {
int i=n.heap_index;
assert(i>0 && i<=count());
assert(ptr(i)==&n);
return;
}
heap.append(&n);
siftup(n.heap_index=count());
costly_assert(is_heap(1,count()));
}
void fix(node& n) {
fix(n.heap_index);
}
T *get_min() {
return count()>0?ptr(1)->obj:0;
}
T *pop_min() {
T *m=get_min();
if(!m)
return 0;
remove(1);
return m;
}
void remove(node& x) {
if(!x.heap_index)
return;
assert(ptr(x.heap_index)==&x);
remove(x.heap_index);
assert(!x.heap_index);
}
};
#endif//XHEAP_H