123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743 |
- BOOST_HEADER_DEPRECATED("the standard heap functions")
- 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:
-
- 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)
- {
- }
-
- ::boost::optional< value_type > value;
-
- group_key_kind kind;
-
- group* parent;
-
-
- rank_type rank;
-
- group** children;
- };
- size_type log_base_2(size_type n)
- {
- 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;
-
-
- 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;
-
- 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)]);
- a->value = x;
- a->kind = smallest_key;
- promote(a);
- smallest_value = a;
- pop();
- }
- value_type& top()
- {
- find_smallest();
- assert(smallest_value->value != none);
- return *smallest_value->value;
- }
- const value_type& top() const
- {
- find_smallest();
- assert(smallest_value->value != none);
- 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 static_cast< bool >(groups[get(id, x)]);
- }
- void pop()
- {
-
- find_smallest();
- group* x = smallest_value;
- smallest_value = 0;
-
- rank_type r = x->rank;
- group* p = x->parent;
- {
- assert(x->value != none);
-
- 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();
-
-
- 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;
-
- 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 (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;
- }
- }
-
- 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);
-
- 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()
- {
-
-
-
- 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;
- }
-
- 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)
- {
-
- if (c->parent != p)
- return false;
- if (c->rank != i)
- return false;
-
- if (do_compare(c, p) && A[i] != c)
- return false;
-
- if (!valid(c))
- return false;
- }
- else
- {
-
- if (p != &root)
- return false;
- }
- }
- return true;
- }
- 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))
- {
-
- group* s = p->rank > r + 1 ? p->children[r + 1] : 0;
-
- 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 (A[s] == x)
- {
- q->children[s] = xp;
- xp->parent = q;
- qp->children[s] = x;
- x->parent = qp;
- }
- }
- void pair_transform(group* a)
- {
- std::cerr << "- pair transform\n";
- rank_type r = a->rank;
-
- group* p = a->parent;
- assert(p != 0);
-
- group* g = p->parent;
- assert(g != 0);
-
- assert(A[r] != 0);
- group* ap = A[r];
- assert(ap != 0);
-
- A[r] = 0;
-
- group* pp = ap->parent;
- assert(pp != 0);
-
- group* gp = pp->parent;
- assert(gp != 0);
-
- assert(ap
- == pp->children[pp->rank - 1]);
- --pp->rank;
-
- assert(a == p->children[p->rank - 1]);
- --p->rank;
-
- if (do_compare(pp, p))
- {
- do_swap(a, ap);
- do_swap(p, pp);
- do_swap(g, gp);
- }
-
-
- assert(r == p->rank);
- p->children[p->rank++] = pp;
- pp->parent = p;
-
- group* c = combine(a, ap);
-
- assert(gp->rank > r + 1);
- gp->children[r + 1] = c;
- c->parent = gp;
- std::cerr << "After pair transform...\n";
- dump_tree();
- if (A[r + 1] == pp)
- A[r + 1] = c;
- else
- promote(c);
- }
- void active_sibling_transform(group* a, group* s)
- {
- std::cerr << "- active sibling transform\n";
- group* p = a->parent;
- group* g = p->parent;
-
- 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);
-
- 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)
- {
- std::cerr << "- good sibling transform\n";
- rank_type r = a->rank;
- group* c = s->children[s->rank - 1];
- assert(c->rank == r);
- if (A[r] == c)
- {
- std::cerr << "- good sibling pair transform\n";
- A[r] = 0;
- group* p = a->parent;
-
- --s->rank;
-
- s->parent = p;
- p->children[r] = s;
-
- 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);
- dump_tree(std::cerr);
-
- }
- else
- {
-
- 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;
- }
-
- Compare compare;
-
- ID id;
-
- group root;
-
- std::vector< group > index_to_group;
-
- std::vector< ::boost::optional< value_type > > groups;
-
- std::vector< group* > A;
-
- mutable group* smallest_value;
-
- size_type log_n;
- };
- }
|