/*

 * 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)

	 swap(i,i/2);

	 i/=2;

      }

   }

   void siftdown(int i) {

      while(i<=count()/2) {

	 int i2=i*2;

	 // choose smallest of heirs

	 if(i2

	    i2++;

	 if(elem(i)

	    break;

	 swap(i,i2);

	 i=i2;

      }

   }

   bool is_heap(int a,int b) {

      while(a*2<=b) {

	 if(elem(a*2)

	    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

      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