binaryheap.hpp

Go to the documentation of this file.

/*
 * This file is part of OpenTTD.
 * OpenTTD 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, version 2.
 * OpenTTD 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 OpenTTD. If not, see <http://www.gnu.org/licenses/>.
 */
 
#ifndef BINARYHEAP_HPP
#define BINARYHEAP_HPP
 
#define BINARYHEAP_CHECK 0
 
#if BINARYHEAP_CHECK
# define CHECK_CONSISTY() this->CheckConsistency()
#else
# define CHECK_CONSISTY() ;
#endif
 
template <class T>
class CBinaryHeapT {
private:
  size_t items = 0; 
  std::vector<T *> data; 
 
public:
  explicit CBinaryHeapT(size_t initial_capacity)
  {
    this->data.reserve(initial_capacity);
    this->Clear();
  }
 
protected:
  inline size_t HeapifyDown(size_t gap, T *item)
  {
    assert(gap != 0);
 
    /* The first child of the gap is at [parent * 2] */
    size_t child = gap * 2;
 
    /* while children are valid */
    while (child <= this->items) {
      /* choose the smaller child */
      if (child < this->items && *this->data[child + 1] < *this->data[child]) {
        child++;
      }
      /* is it smaller than our parent? */
      if (!(*this->data[child] < *item)) {
        /* the smaller child is still bigger or same as parent => we are done */
        break;
      }
      /* if smaller child is smaller than parent, it will become new parent */
      this->data[gap] = this->data[child];
      gap = child;
      /* where do we have our new children? */
      child = gap * 2;
    }
    return gap;
  }
 
  inline size_t HeapifyUp(size_t gap, T *item)
  {
    assert(gap != 0);
 
    size_t parent;
 
    while (gap > 1) {
      /* compare [gap] with its parent */
      parent = gap / 2;
      if (!(*item < *this->data[parent])) {
        /* we don't need to continue upstairs */
        break;
      }
      this->data[gap] = this->data[parent];
      gap = parent;
    }
    return gap;
  }
 
#if BINARYHEAP_CHECK
  inline void CheckConsistency()
  {
    assert(this->items == this->data.size() - 1);
    for (size_t child = 2; child <= this->items; child++) {
      size_t parent = child / 2;
      assert(!(*this->data[child] < *this->data[parent]));
    }
  }
#endif
 
public:
  inline size_t Length() const
  {
    return this->items;
  }
 
  inline bool IsEmpty() const
  {
    return this->items == 0;
  }
 
  inline T *Begin()
  {
    assert(!this->IsEmpty());
    return this->data[1];
  }
 
  inline T *End()
  {
    return this->data[1 + this->items];
  }
 
  inline void Include(T *new_item)
  {
    /* Make place for new item. A gap is now at the end of the tree. */
    this->data.emplace_back();
    size_t gap = this->HeapifyUp(++items, new_item);
    this->data[gap] = new_item;
    CHECK_CONSISTY();
  }
 
  inline T *Shift()
  {
    assert(!this->IsEmpty());
 
    T *first = this->Begin();
 
    this->items--;
    /* at index 1 we have a gap now */
    T *last = this->End();
    size_t gap = this->HeapifyDown(1, last);
    /* move last item to the proper place */
    if (!this->IsEmpty()) this->data[gap] = last;
    this->data.pop_back();
 
    CHECK_CONSISTY();
    return first;
  }
 
  inline void Remove(size_t index)
  {
    if (index < this->items) {
      assert(index != 0);
      this->items--;
      /* at position index we have a gap now */
 
      T *last = this->End();
      /* Fix binary tree up and downwards */
      size_t gap = this->HeapifyUp(index, last);
      gap = this->HeapifyDown(gap, last);
      /* move last item to the proper place */
      if (!this->IsEmpty()) this->data[gap] = last;
    } else {
      assert(index == this->items);
      this->items--;
    }
    this->data.pop_back();
 
    CHECK_CONSISTY();
  }
 
  inline size_t FindIndex(const T &item) const
  {
    auto it = std::find(this->data.begin(), this->data.end(), &item);
    return it == this->data.end() ? 0 : std::distance(this->data.begin(), it);
  }
 
  inline void Clear()
  {
    this->items = 0;
    this->data.resize(1);
 
    CHECK_CONSISTY();
  }
};
 
#endif /* BINARYHEAP_HPP */