// Copyright 2004 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software

// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at

// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Douglas Gregor

//           Andrew Lumsdaine

#ifndef BOOST_RELAXED_HEAP_HEADER

#define BOOST_RELAXED_HEAP_HEADER

#include <functional>

#include <boost/property_map.hpp>

#include <boost/optional.hpp>

#include <vector>

#ifdef BOOST_RELAXED_HEAP_DEBUG

#  include <iostream>

#endif // BOOST_RELAXED_HEAP_DEBUG

#if defined(BOOST_MSVC)

#  pragma warning(push)

#  pragma warning(disable:4355) // complaint about using 'this' to

#endif                          // initialize a member

namespace boost {

template<typename IndexedType,

         typename Compare = std::less<IndexedType>,

         typename ID = identity_property_map>

class relaxed_heap

{

  struct group;

  typedef relaxed_heap self_type;

  typedef std::size_t  rank_type;

public:

  typedef IndexedType  value_type;

  typedef rank_type    size_type;

private:

  /**

   * The kind of key that a group has. The actual values are discussed

   * in-depth in the documentation of the @c kind field of the @c group

   * structure. Note that the order of the enumerators *IS* important

   * and must not be changed.

   */

  enum group_key_kind { smallest_key, stored_key, largest_key };

  struct group {

    explicit group(group_key_kind kind = largest_key)

      : kind(kind), parent(this), rank(0) { }

    /** The value associated with this group. This value is only valid

     *  when @c kind!=largest_key (which indicates a deleted

     *  element). Note that the use of boost::optional increases the

     *  memory requirements slightly but does not result in extraneous

     *  memory allocations or deallocations. The optional could be

     *  eliminated when @c value_type is a model of

     *  DefaultConstructible.

     */

    ::boost::optional<value_type> value;

    /**

     * The kind of key stored at this group. This may be @c

     * smallest_key, which indicates that the key is infinitely small;

     * @c largest_key, which indicates that the key is infinitely

     * large; or @c stored_key, which means that the key is unknown,

     * but its relationship to other keys can be determined via the

     * comparison function object.

     */

    group_key_kind        kind;

    /// The parent of this group. Will only be NULL for the dummy root group

    group*                parent;

    /// The rank of this group. Equivalent to the number of children in

    /// the group.

    rank_type            rank;

    /** The children of this group. For the dummy root group, these are

     * the roots. This is an array of length log n containing pointers

     * to the child groups.

     */

    group**               children;

  };

  size_type log_base_2(size_type n) // log2 is a macro on some platforms

  {

    size_type leading_zeroes = 0;

    do {

      size_type next = n << 1;

      if (n == (next >> 1)) {

        ++leading_zeroes;

        n = next;

      } else {

        break;

      }

    } while (true);

    return sizeof(size_type) * CHAR_BIT - leading_zeroes - 1;

  }

public:

  relaxed_heap(size_type n, const Compare& compare = Compare(),

               const ID& id = ID())

    : compare(compare), id(id), root(smallest_key), groups(n),

      smallest_value(0)

  {

    if (n == 0) {

      root.children = new group*[1];

      return;

    }

    log_n = log_base_2(n);

    if (log_n == 0) log_n = 1;

    size_type g = n / log_n;

    if (n % log_n > 0) ++g;

    size_type log_g = log_base_2(g);

    size_type r = log_g;

    // Reserve an appropriate amount of space for data structures, so

    // that we do not need to expand them.

    index_to_group.resize(g);

    A.resize(r + 1, 0);

    root.rank = r + 1;

    root.children = new group*[(log_g + 1) * (g + 1)];

    for (rank_type i = 0; i < r+1; ++i) root.children[i] = 0;

    // Build initial heap

    size_type idx = 0;

    while (idx < g) {

      root.children[r] = &index_to_group[idx];

      idx = build_tree(root, idx, r, log_g + 1);

      if (idx != g)

        r = static_cast<size_type>(log_base_2(g-idx));

    }

  }

  ~relaxed_heap() { delete [] root.children; }

  void push(const value_type& x)

  {

    groups[get(id, x)] = x;

    update(x);

  }

  void update(const value_type& x)

  {

    group* a = &index_to_group[get(id, x) / log_n];

    if (!a->value

        || *a->value == x

        || compare(x, *a->value)) {

      if (a != smallest_value) smallest_value = 0;

      a->kind = stored_key;

      a->value = x;

      promote(a);

    }

  }

  void remove(const value_type& x)

  {

    group* a = &index_to_group[get(id, x) / log_n];

    assert(groups[get(id, x)] != 0);

    a->value = x;

    a->kind = smallest_key;

    promote(a);

    smallest_value = a;

    pop();

  }

  value_type& top()

  {

    find_smallest();

    assert(smallest_value->value != 0);

    return *smallest_value->value;

  }

  const value_type& top() const

  {

    find_smallest();

    assert(smallest_value->value != 0);

    return *smallest_value->value;

  }

  bool empty() const

  {

    find_smallest();

    return !smallest_value || (smallest_value->kind == largest_key);

  }

  bool contains(const value_type& x) const { return groups[get(id, x)]; }

  void pop()

  {

    // Fill in smallest_value. This is the group x.

    find_smallest();

    group* x = smallest_value;

    smallest_value = 0;

    // Make x a leaf, giving it the smallest value within its group

    rank_type r = x->rank;

    group* p = x->parent;

    {

      assert(x->value != 0);

      // Find x's group

      size_type start = get(id, *x->value) - get(id, *x->value) % log_n;

      size_type end = start + log_n;

      if (end > groups.size()) end = groups.size();

      // Remove the smallest value from the group, and find the new

      // smallest value.

      groups[get(id, *x->value)].reset();

      x->value.reset();

      x->kind = largest_key;

      for (size_type i = start; i < end; ++i) {

        if (groups[i] && (!x->value || compare(*groups[i], *x->value))) {

          x->kind = stored_key;

          x->value = groups[i];

        }

      }

    }

    x->rank = 0;

    // Combine prior children of x with x

    group* y = x;

    for (size_type c = 0; c < r; ++c) {

      group* child = x->children[c];

      if (A[c] == child) A[c] = 0;

      y = combine(y, child);

    }

    // If we got back something other than x, let y take x's place

    if (y != x) {

      y->parent = p;

      p->children[r] = y;

      assert(r == y->rank);

      if (A[y->rank] == x)

        A[y->rank] = do_compare(y, p)? y : 0;

    }

  }

#ifdef BOOST_RELAXED_HEAP_DEBUG

  /*************************************************************************

   * Debugging support                                                     *

   *************************************************************************/

  void dump_tree() { dump_tree(std::cout); }

  void dump_tree(std::ostream& out) { dump_tree(out, &root); }

  void dump_tree(std::ostream& out, group* p, bool in_progress = false)

  {

    if (!in_progress) {

      out << "digraph heap {\n"

          << "  edge[dir=\"back\"];\n";

    }

    size_type p_index = 0;

    if (p != &root) while (&index_to_group[p_index] != p) ++p_index;

    for (size_type i = 0; i < p->rank; ++i) {

      group* c = p->children[i];

      if (c) {

        size_type c_index = 0;

        if (c != &root) while (&index_to_group[c_index] != c) ++c_index;

        out << "  ";

        if (p == &root) out << 'p'; else out << p_index;

        out << " -> ";

        if (c == &root) out << 'p'; else out << c_index;

        if (A[c->rank] == c) out << " [style=\"dotted\"]";

        out << ";\n";

        dump_tree(out, c, true);

        // Emit node information

        out << "  ";

        if (c == &root) out << 'p'; else out << c_index;

        out << " [label=\"";

        if (c == &root) out << 'p'; else out << c_index;

        out << ":";

        size_type start = c_index * log_n;

        size_type end = start + log_n;

        if (end > groups.size()) end = groups.size();

        while (start != end) {

          if (groups[start]) {

            out << " " << get(id, *groups[start]);

            if (*groups[start] == *c->value) out << "(*)";

          }

          ++start;

        }

        out << '"';

        if (do_compare(c, p)) {

          out << "  ";

          if (c == &root) out << 'p'; else out << c_index;

          out << ", style=\"filled\", fillcolor=\"gray\"";

        }

        out << "];\n";

      } else {

        assert(p->parent == p);

      }

    }

    if (!in_progress) out << "}\n";

  }

  bool valid()

  {

    // Check that the ranks in the A array match the ranks of the

    // groups stored there. Also, the active groups must be the last

    // child of their parent.

    for (size_type r = 0; r < A.size(); ++r) {

      if (A[r] && A[r]->rank != r) return false;

      if (A[r] && A[r]->parent->children[A[r]->parent->rank-1] != A[r])

        return false;

    }

    // The root must have no value and a key of -Infinity

    if (root.kind != smallest_key) return false;

    return valid(&root);

  }

  bool valid(group* p)

  {

    for (size_type i = 0; i < p->rank; ++i) {

      group* c = p->children[i];

      if (c) {

        // Check link structure

        if (c->parent != p) return false;

        if (c->rank != i) return false;

        // A bad group must be active

        if (do_compare(c, p) && A[i] != c) return false;

        // Check recursively

        if (!valid(c)) return false;

      } else {

        // Only the root may

        if (p != &root) return false;

      }

    }

    return true;

  }

#endif // BOOST_RELAXED_HEAP_DEBUG

private:

  size_type

  build_tree(group& parent, size_type idx, size_type r, size_type max_rank)

  {

    group& this_group = index_to_group[idx];

    this_group.parent = &parent;

    ++idx;

    this_group.children = root.children + (idx * max_rank);

    this_group.rank = r;

    for (size_type i = 0; i < r; ++i) {

      this_group.children[i] = &index_to_group[idx];

      idx = build_tree(this_group, idx, i, max_rank);

    }

    return idx;

  }

  void find_smallest() const

  {

    group** roots = root.children;

    if (!smallest_value) {

      std::size_t i;

      for (i = 0; i < root.rank; ++i) {

        if (roots[i] &&

            (!smallest_value || do_compare(roots[i], smallest_value))) {

          smallest_value = roots[i];

        }

      }

      for (i = 0; i < A.size(); ++i) {

        if (A[i] && (!smallest_value || do_compare(A[i], smallest_value)))

          smallest_value = A[i];

      }

    }

  }

  bool do_compare(group* x, group* y) const

  {

    return (x->kind < y->kind

            || (x->kind == y->kind

                && x->kind == stored_key

                && compare(*x->value, *y->value)));

  }

  void promote(group* a)

  {

    assert(a != 0);

    rank_type r = a->rank;

    group* p = a->parent;

    assert(p != 0);

    if (do_compare(a, p)) {

      // s is the rank + 1 sibling

      group* s = p->rank > r + 1? p->children[r + 1] : 0;

      // If a is the last child of p

      if (r == p->rank - 1) {

        if (!A[r]) A[r] = a;

        else if (A[r] != a) pair_transform(a);

      } else {

        assert(s != 0);

        if (A[r + 1] == s) active_sibling_transform(a, s);

        else good_sibling_transform(a, s);

      }

    }

  }

  group* combine(group* a1, group* a2)

  {

    assert(a1->rank == a2->rank);

    if (do_compare(a2, a1)) do_swap(a1, a2);

    a1->children[a1->rank++] = a2;

    a2->parent = a1;

    clean(a1);

    return a1;

  }

  void clean(group* q)

  {

    if (2 > q->rank) return;

    group* qp = q->children[q->rank-1];

    rank_type s = q->rank - 2;

    group* x = q->children[s];

    group* xp = qp->children[s];

    assert(s == x->rank);

    // If x is active, swap x and xp

    if (A[s] == x) {

      q->children[s] = xp;

      xp->parent = q;

      qp->children[s] = x;

      x->parent = qp;

    }

  }

  void pair_transform(group* a)

  {

#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1

    std::cerr << "- pair transform\n";

#endif

    rank_type r = a->rank;

    // p is a's parent

    group* p = a->parent;

    assert(p != 0);

    // g is p's parent (a's grandparent)

    group* g = p->parent;

    assert(g != 0);

    // a' <- A(r)

    assert(A[r] != 0);

    group* ap = A[r];

    assert(ap != 0);

    // A(r) <- nil

    A[r] = 0;

    // let a' have parent p'

    group* pp = ap->parent;

    assert(pp != 0);

    // let a' have grandparent g'

    group* gp = pp->parent;

    assert(gp != 0);

    // Remove a and a' from their parents

    assert(ap == pp->children[pp->rank-1]); // Guaranteed because ap is active

    --pp->rank;

    // Guaranteed by caller

    assert(a == p->children[p->rank-1]);

    --p->rank;

    // Note: a, ap, p, pp all have rank r

    if (do_compare(pp, p)) {

      do_swap(a, ap);

      do_swap(p, pp);

      do_swap(g, gp);

    }

    // Assuming k(p) <= k(p')

    // make p' the rank r child of p

    assert(r == p->rank);

    p->children[p->rank++] = pp;

    pp->parent = p;

    // Combine a, ap into a rank r+1 group c

    group* c = combine(a, ap);

    // make c the rank r+1 child of g'

    assert(gp->rank > r+1);

    gp->children[r+1] = c;

    c->parent = gp;

#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1

    std::cerr << "After pair transform...\n";

    dump_tree();

#endif

    if (A[r+1] == pp) A[r+1] = c;

    else promote(c);

  }

  void active_sibling_transform(group* a, group* s)

  {

#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1

    std::cerr << "- active sibling transform\n";

#endif

    group* p = a->parent;

    group* g = p->parent;

    // remove a, s from their parents

    assert(s->parent == p);

    assert(p->children[p->rank-1] == s);

    --p->rank;

    assert(p->children[p->rank-1] == a);

    --p->rank;

    rank_type r = a->rank;

    A[r+1] = 0;

    a = combine(p, a);

    group* c = combine(a, s);

    // make c the rank r+2 child of g

    assert(g->children[r+2] == p);

    g->children[r+2] = c;

    c->parent = g;

    if (A[r+2] == p) A[r+2] = c;

    else promote(c);

  }

  void good_sibling_transform(group* a, group* s)

  {

#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1

    std::cerr << "- good sibling transform\n";

#endif

    rank_type r = a->rank;

    group* c = s->children[s->rank-1];

    assert(c->rank == r);

    if (A[r] == c) {

#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1

      std::cerr << "- good sibling pair transform\n";

#endif

      A[r] = 0;

      group* p = a->parent;

      // Remove c from its parent

      --s->rank;

      // Make s the rank r child of p

      s->parent = p;

      p->children[r] = s;

      // combine a, c and let the result by the rank r+1 child of p

      assert(p->rank > r+1);

      group* x = combine(a, c);

      x->parent = p;

      p->children[r+1] = x;

      if (A[r+1] == s) A[r+1] = x;

      else promote(x);

#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1

      dump_tree(std::cerr);

#endif

      //      pair_transform(a);

    } else {

      // Clean operation

      group* p = a->parent;

      s->children[r] = a;

      a->parent = s;

      p->children[r] = c;

      c->parent = p;

      promote(a);

    }

  }

  static void do_swap(group*& x, group*& y)

  {

    group* tmp = x;

    x = y;

    y = tmp;

  }

  /// Function object that compares two values in the heap

  Compare compare;

  /// Mapping from values to indices in the range [0, n).

  ID id;

  /** The root group of the queue. This group is special because it will

   *  never store a value, but it acts as a parent to all of the

   *  roots. Thus, its list of children is the list of roots.

   */

  group root;

  /** Mapping from the group index of a value to the group associated

   *  with that value. If a value is not in the queue, then the "value"

   *  field will be empty.

   */

  std::vector<group> index_to_group;

  /** Flat data structure containing the values in each of the

   *  groups. It will be indexed via the id of the values. The groups

   *  are each log_n long, with the last group potentially being

   *  smaller.

   */

  std::vector< ::boost::optional<value_type> > groups;

  /** The list of active groups, indexed by rank. When A[r] is null,

   *  there is no active group of rank r. Otherwise, A[r] is the active

   *  group of rank r.

   */

  std::vector<group*> A;

  /** The group containing the smallest value in the queue, which must

   *  be either a root or an active group. If this group is null, then we

   *  will need to search for this group when it is needed.

   */

  mutable group* smallest_value;

  /// Cached value log_base_2(n)

  size_type log_n;

};

} // end namespace boost

#if defined(BOOST_MSVC)

#  pragma warning(pop)

#endif

#endif // BOOST_RELAXED_HEAP_HEADER