[Olena-patches] 3161: Add soft heap implementation.

* headers.mk: add new headers to distribution. * mln/util/soft_heap.hh: new file. New implementation. New members may be added later. * mln/util/tracked_ptr.hh: Fix an issue while assigning a null tracked_ptr to another tracked_ptr. An internal pointer was not initialized but dereferenced and led to a segfault. * tests/unit_test/Makefile.am, * tests/unit_test/mln_util_soft_heap.cc: add a new unit test. * tests/util/Makefile.am, * tests/util/soft_heap.cc: add a new test. --- milena/ChangeLog | 19 + milena/headers.mk | 1 + milena/mln/util/soft_heap.hh | 1137 ++++++++++++++++++++++++++ milena/mln/util/tracked_ptr.hh | 46 +- milena/tests/unit_test/Makefile.am | 2 + milena/tests/unit_test/mln_util_soft_heap.cc | 11 + milena/tests/util/Makefile.am | 2 + milena/tests/util/soft_heap.cc | 79 ++ 8 files changed, 1273 insertions(+), 24 deletions(-) create mode 100644 milena/mln/util/soft_heap.hh create mode 100644 milena/tests/unit_test/mln_util_soft_heap.cc create mode 100644 milena/tests/util/soft_heap.cc diff --git a/milena/ChangeLog b/milena/ChangeLog index 0166541..583f2d7 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,24 @@ 2009-01-16 Guillaume Lazzara &lt;z(a)lrde.epita.fr&gt; + Add soft heap implementation. + + * headers.mk: add new headers to distribution. + + * mln/util/soft_heap.hh: new file. New implementation. New members may + be added later. + + * mln/util/tracked_ptr.hh: Fix an issue while assigning a null + tracked_ptr to another tracked_ptr. An internal pointer was not + initialized but dereferenced and led to a segfault. + + * tests/unit_test/Makefile.am, + * tests/unit_test/mln_util_soft_heap.cc: add a new unit test. + + * tests/util/Makefile.am, + * tests/util/soft_heap.cc: add a new test. + +2009-01-16 Guillaume Lazzara &lt;z(a)lrde.epita.fr&gt; + Rename histo::data as histo::array. * mln/histo/data.hh: rename file as... diff --git a/milena/headers.mk b/milena/headers.mk index fc78f90..9380631 100644 --- a/milena/headers.mk +++ b/milena/headers.mk @@ -64,6 +64,7 @@ mln/registration/icp.hh \ mln/util/graph.hh \ mln/util/max.hh \ mln/util/lazy_set.hh \ +mln/util/soft_heap.hh \ mln/util/set.hh \ mln/util/tree_to_image.hh \ mln/util/lemmings.hh \ diff --git a/milena/mln/util/soft_heap.hh b/milena/mln/util/soft_heap.hh new file mode 100644 index 0000000..144110f --- /dev/null +++ b/milena/mln/util/soft_heap.hh @@ -0,0 +1,1137 @@ +// Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_UTIL_FAST_HEAP_HH +# define MLN_UTIL_FAST_HEAP_HH + +/// \file mln/util/soft_heap.hh +/// +/// Define a generic soft heap. +/* + This implementation is not an usual heap, it allows to set an error + rate so that some nodes may be "corrupted". A "corrupted node" means + that its correct order is not totally preserved for performance reasons. + Of course, it will have an impact on the returned values. + As a result, be ware of not using this data structure if the element + order is relevant for to you. + + A corruption threshold can be passed to the constructor. + This threshold means that if nodes have a rank higher than this + threshold they can be "corrupted" and therefore their rank can be + reduced. Tuning this threshold may have an impact on the structure + entropy thus on the returned values order. It may also have an impact + on the performance. + + + More implementation details are available in: + "The soft heap: an approximate priority queue with optimal error rate", + Bernard Chazelle, JACM, 2000. + + URL: http://www.cs.princeton.edu/~chazelle/pubs/sheap.pdf + + \todo try not to use tracked_ptr. + \todo try not to call T::plus_infty(). This is not generic enough but + it works with mln::point<>. +*/ + +# include <mln/core/concept/object.hh> +# include <mln/trait/value_.hh> +# include <mln/util/tracked_ptr.hh> +# include <climits> +# include <stack> + + + +namespace mln +{ + + namespace util + { + + + /// Element of an item list. Store the data (key) used in soft_heap. + template <typename T> + struct ilcell + { + typedef util::tracked_ptr< ilcell<T> > ilcell_t; + + ilcell(); + ilcell(const T& key, ilcell_t next = 0); + + ilcell_t next() const; + const T& key() const; + + void set_next(ilcell_t next); + void set_key(const T& key); + + private: + T key_; + ilcell_t next_; + }; + + + /// Meta-data of an element in the heap. + template <typename T, typename R> + class node + { + + typedef util::tracked_ptr< ilcell<T> > ilcell_t; + + public: + node(); + node(const T& ckey, const R& rank, + node<T,R> *next = 0, node<T,R> *child = 0, + ilcell_t il = 0, ilcell_t il_tail = 0); + ~node(); + + const T& ckey() const; + const R& rank() const; + node<T,R> * next() const; + node<T,R> * child() const; + ilcell_t il() const; + ilcell_t il_tail() const; + + void set_il(ilcell_t il); + void set_il_tail(ilcell_t il_tail); + void set_ckey(const T& ckey); + void set_rank(const R& rank); + void set_next(node<T,R> * next); + void set_child(node<T,R> *child); + + private: + T ckey_; + R rank_; + node<T,R> *next_; + node<T,R> *child_; + ilcell_t il_; + ilcell_t il_tail_; + + }; + + + + + /// Top structure of the soft heap. + template <typename T, typename R> + class head + { + public: + + head(); + head(const R& rank, node<T,R> *queue = 0, head<T,R> *next = 0, + head<T,R> *prev = 0, head<T,R> *suffix_min = 0); + ~head(); + + node<T,R> *queue() const; + head<T,R> *next() const; + head<T,R> *prev() const; + head<T,R> *suffix_min() const; + const R& rank() const; + + void set_queue(node<T,R> *queue); + void set_next(head<T,R> *next); + void set_prev(head<T,R> *prev); + void set_suffix_min(head<T,R> *suffix_min); + void set_rank(const R& rank); + + private: + node<T,R> *queue_; + head<T,R> *next_; + head<T,R> *prev_; + head<T,R> *suffix_min_; + R rank_; + + }; + + + + + /// T key, the data to store in the heap. For instance a point 2d. + /// R rank, for instance int_u8 + template <typename T, typename R> + class soft_heap : public Object< soft_heap<T,R> > + { + typedef util::tracked_ptr< ilcell<T> > ilcell_t; + + public: + + /// Element associated type. + typedef T element; + + + /// Default constructor. + /// A corruption threshold \p r can be specified. + /// This threshold means that if nodes have a rank higher than this + /// threshold they can be "corrupted" and therefore their rank can be + /// reduced. + /// + // FIXME: is it a correct value for r? + soft_heap(unsigned r = 20); + /// Destructor + ~soft_heap(); + + + /// Add a new element \p element. + void push(const T& element); + /// Insert a site \p p (equivalent as 'push'). + void insert(const T& p); + + /// Merge \p sh with this heap. + /// Be ware that after this call, \p sh will be empty. This heap will + /// hold the elements which were part of \p sh. + void take(soft_heap<T,R>& sh); + + /// Returns the element with the lowest priority and remove it from the + /// heap. + T pop_front(); + + /// Return true if there is at least one element. + bool is_valid() const; + + /// Return true if there is at least one element. + bool is_empty() const; + + /// Return the number of element in the heap. + int nelements() const; + + /// Clear the heap. + void clear(); + + /// Internal use only. Return a pointer to the first header struct + /// of this heap. + head<T,R> *head_hook_() const; + + /// Reset the heap to an empty heap. Do *NOT* delete element which may + /// have been inserted. + /// \sa take + void soft_clear_(); + + + + private: + /// Merge a node \p q to this heap. + /// \sa take + void meld(node<T,R> *q); + + /// Update suffix_min pointer according to the new values inserted in + /// the item lists. + void fix_minlist(head<T,R> *h); + + /// After the deletion of an element, this function move/update item lists + /// in the proper nodes. + node<T,R> * sift(node<T,R> *v); + + /// Delete all element in a C-list from \p begin to \p end. \p end is not + /// deleted. + /// The type L must provide 'L *next()'. + /// + /// next + /// + /// |x| -> |x| -> |x| + /// + template <typename L> + void clear_list(L *begin, L *end = 0); + + /// Delete all element in a 2 dimensional C-list. + /// The type L must provide 'L *next()' and 'L *child()'. + /// + /// next + /// + /// |x| -> |x| -> |x| + /// | + /// child v + /// |x| -> |x| + /// + template <typename L> + void deep_clear_list(L *n); + + /// Print which node is part of which head. + void debug_head_list() const; + + /// Display the heap, preserving the hierarchy of the elements. + void println_() const; + + head<T,R> *header_; + head<T,R> *tail_; + + /// Corruption threshold. Must be set once through the constructor. + unsigned r_; + + int nelements_; + }; + + + +# ifndef MLN_INCLUDE_ONLY + + + /*-------` + | ilcell | + \-------*/ + + + template <typename T> + inline + ilcell<T>::ilcell() + { + } + + + template <typename T> + inline + ilcell<T>::ilcell(const T& key, ilcell_t next) + : key_(key), next_(next) + { + } + + + template <typename T> + inline + typename ilcell<T>::ilcell_t + ilcell<T>::next() const + { + return next_; + } + + + template <typename T> + inline + const T& + ilcell<T>::key() const + { + return key_; + } + + + template <typename T> + inline + void + ilcell<T>::set_next(ilcell_t next) + { + next_ = next; + } + + + template <typename T> + inline + void + ilcell<T>::set_key(const T& key) + { + key_ = key; + } + + + + + /*-----` + | node | + \-----*/ + + + template <typename T, typename R> + inline + node<T,R>::node() + : il_(0), il_tail_(0) + { + } + + + template <typename T, typename R> + inline + node<T,R>::node(const T& ckey, const R& rank, + node<T,R> *next, node<T,R> *child, + ilcell_t il, ilcell_t il_tail) + : ckey_(ckey), rank_(rank), next_(next), child_(child), + il_(il), il_tail_(il_tail) + { + } + + + template <typename T, typename R> + inline + node<T,R>::~node() + { + } + + + template <typename T, typename R> + inline + const T& + node<T,R>::ckey() const + { + return ckey_; + } + + + template <typename T, typename R> + inline + const R& + node<T,R>::rank() const + { + return rank_; + } + + + template <typename T, typename R> + inline + node<T,R> * + node<T,R>::next() const + { + return next_; + } + + + template <typename T, typename R> + inline + node<T,R> * + node<T,R>::child() const + { + return child_; + } + + + template <typename T, typename R> + inline + typename node<T,R>::ilcell_t + node<T,R>::il() const + { + return il_; + } + + + template <typename T, typename R> + inline + typename node<T,R>::ilcell_t + node<T,R>::il_tail() const + { + return il_tail_; + } + + + template <typename T, typename R> + inline + void + node<T,R>::set_il(ilcell_t il) + { + il_ = il; + } + + + template <typename T, typename R> + inline + void + node<T,R>::set_il_tail(ilcell_t il_tail) + { + il_tail_ = il_tail; + } + + + template <typename T, typename R> + inline + void + node<T,R>::set_ckey(const T& ckey) + { + ckey_ = ckey; + } + + + template <typename T, typename R> + inline + void + node<T,R>::set_rank(const R& rank) + { + rank_ = rank; + } + + + template <typename T, typename R> + inline + void + node<T,R>::set_next(node<T,R> * next) + { + next_ = next; + } + + + template <typename T, typename R> + inline + void + node<T,R>::set_child(node<T,R> *child) + { + child_ = child; + } + + + + + /*-----` + | head | + \-----*/ + + + template <typename T, typename R> + inline + head<T,R>::head() + { + } + + + template <typename T, typename R> + inline + head<T,R>::head(const R& rank, node<T,R> *queue, head<T,R> *next, + head<T,R> *prev, head<T,R> *suffix_min) + : queue_(queue), next_(next), prev_(prev), + suffix_min_(suffix_min), rank_(rank) + { + } + + + template <typename T, typename R> + inline + head<T,R>::~head() + { + } + + + template <typename T, typename R> + inline + node<T,R> * + head<T,R>::queue() const + { + return queue_; + } + + + template <typename T, typename R> + inline + head<T,R> * + head<T,R>::next() const + { + return next_; + } + + + template <typename T, typename R> + inline + head<T,R> * + head<T,R>::prev() const + { + return prev_; + } + + + template <typename T, typename R> + inline + head<T,R> * + head<T,R>::suffix_min() const + { + return suffix_min_; + } + + + template <typename T, typename R> + inline + const R& + head<T,R>::rank() const + { + return rank_; + } + + + template <typename T, typename R> + inline + void + head<T,R>::set_queue(node<T,R> *queue) + { + queue_ = queue; + } + + + template <typename T, typename R> + inline + void + head<T,R>::set_next(head<T,R> *next) + { + next_ = next; + } + + + template <typename T, typename R> + inline + void + head<T,R>::set_prev(head<T,R> *prev) + { + prev_ = prev; + } + + + template <typename T, typename R> + inline + void + head<T,R>::set_suffix_min(head<T,R> *suffix_min) + { + suffix_min_ = suffix_min; + } + + + template <typename T, typename R> + inline + void + head<T,R>::set_rank(const R& rank) + { + rank_ = rank; + } + + + + + /*------------` + | soft_heap | + \------------*/ + + + template <typename T, typename R> + inline + soft_heap<T,R>::soft_heap(unsigned r) + { + nelements_ = 0; + r_ = r; + header_ = new head<T,R>(mln_max(R)); + tail_ = new head<T,R>(mln_max(R), 0, 0, header_); + header_->set_next(tail_); + } + + + template <typename T, typename R> + inline + soft_heap<T,R>::~soft_heap() + { + head<T,R> *tmp = header_; + while (tmp != 0) + { + deep_clear_list(tmp->queue()); + tmp = tmp->next(); + } + clear_list(header_, tail_->next()); + } + + + template <typename T, typename R> + inline + void + soft_heap<T,R>::push(const T& element) + { + ilcell_t l(new ilcell<T>(element)); + node<T,R> *q = new node<T,R>(element, 0, 0, 0, l, l); + meld(q); + ++nelements_; + } + + + template <typename T, typename R> + inline + void + soft_heap<T,R>::take(soft_heap<T,R>& psh) + { + head<T,R> *head = psh.head_hook_(); + while (head != 0) + { + if (head->queue() != 0) + meld(head->queue()); + head = head->next(); + } + nelements_ += psh.nelements(); + psh.soft_clear_(); + } + + + template <typename T, typename R> + inline + T + soft_heap<T,R>::pop_front() + { + mln_precondition(is_valid()); + + node<T,R> *tmp; + + T min; + int childcount; + head<T,R> *h = header_->next()->suffix_min(); + while (h->queue()->il() == 0) + { + tmp = h->queue(); + childcount = 0; + while (tmp->next() != 0) + { + tmp = tmp->next(); + ++childcount; + } + + if (childcount < h->rank() / 2) + { + h->prev()->set_next(h->next()); + h->next()->set_prev(h->prev()); + fix_minlist(h->prev()); + tmp = h->queue(); + while (tmp->next() != 0) + { + meld(tmp->child()); + tmp = tmp->next(); + } + //FIXME: is it right? + deep_clear_list(h->queue()); + delete h; + } + else + { + h->set_queue(sift(h->queue())); + // FIXME: not generic enough. + if (h->queue()->ckey() == T::plus_infty()) + { + h->prev()->set_next(h->next()); + h->next()->set_prev(h->prev()); + + // Remove h and switch to h->prev. + head<T,R> *h_bak = h; + h = h->prev(); + deep_clear_list(h_bak->queue()); + delete h_bak; + } + fix_minlist(h); + } + h = header_->next()->suffix_min(); + } + + min = h->queue()->il()->key(); + + //Don't need to delete h->queue()->il(). May be used in another node. + h->queue()->set_il(h->queue()->il()->next()); + if (h->queue()->il() == 0) + h->queue()->set_il_tail(0); + + --nelements_; + return min; + } + + + template <typename T, typename R> + inline + bool + soft_heap<T,R>::is_valid() const + { + return header_ != 0 && tail_ != 0; + } + + + template <typename T, typename R> + inline + bool + soft_heap<T,R>::is_empty() const + { + return nelements_ == 0 ; + } + + + template <typename T, typename R> + inline + int + soft_heap<T,R>::nelements() const + { + return nelements_; + } + + + template <typename T, typename R> + inline + void + soft_heap<T,R>::clear() + { + if (header_->next() == tail_) + return; + + head<T,R> *tohead = header_->next(); + head<T,R> *prevtail = tail_->prev(); + prevtail->set_next(0); + tohead->set_prev(0); + header_->set_next(tail_); + tail_->set_prev(header_); + + head<T,R> *tmp = tohead; + while (tmp != 0) + { + deep_clear_list(tmp->queue()); + tmp = tmp->next(); + } + clear_list(tohead); + + nelements_ = 0; + } + + + template <typename T, typename R> + inline + void + soft_heap<T,R>::soft_clear_() + { + clear_list(header_->next(), tail_); + header_->set_next(tail_); + header_->set_prev(0); + tail_->set_next(0); + tail_->set_prev(header_); + nelements_ = 0; + } + + + template <typename T, typename R> + inline + head<T,R> * + soft_heap<T,R>::head_hook_() const + { + return header_; + } + + + template <typename T, typename R> + inline + void + soft_heap<T,R>::meld(node<T,R>* q) + { + head<T,R> *tohead = header_->next(); + while (q->rank() > tohead->rank()) + tohead = tohead->next(); + head<T,R> *prevhead = tohead->prev(); + + node<T,R> *top, *bottom; + + while (q->rank() == tohead->rank()) + { + if (util::ord_strict(q->ckey(), tohead->queue()->ckey())) + { + top = q; + bottom = tohead->queue(); + } + else + { + top = tohead->queue(); + bottom = q; + } + + q = new node<T,R>(top->ckey(), top->rank() + 1, top, bottom, + top->il(), top->il_tail()); + + tohead = tohead->next(); + } + + head<T,R> *h; + if (prevhead == tohead->prev()) + { + h = new head<T,R>(q->rank(), q, tohead, prevhead); + } + else + { + // Do not create a new head. + h = prevhead->next(); + + //Discard/delete everything between h and tohead. + head<T,R> *head_del = h->next(), *tmp_del; + while (head_del != tohead) + { + tmp_del = head_del->next(); + delete head_del; + head_del = tmp_del; + } + + } + h->set_queue(q); + h->set_rank(q->rank()); + h->set_prev(prevhead); + h->set_next(tohead); + + prevhead->set_next(h); + tohead->set_prev(h); + + fix_minlist(h); + } + + + template <typename T, typename R> + inline + void + soft_heap<T,R>::fix_minlist(head<T,R> *h) + { + head<T,R> *tmpmin; + if (h->next() == tail_) + tmpmin = h; + else + tmpmin = h->next()->suffix_min(); + + while (h != header_) + { + if (util::ord_strict(h->queue()->ckey(), tmpmin->queue()->ckey())) + tmpmin = h; + h->set_suffix_min(tmpmin); + h = h->prev(); + } + } + + + template <typename T, typename R> + inline + node<T,R> * + soft_heap<T,R>::sift(node<T,R> *v) + { + node<T,R> *tmp; + // We do not need to free the list since these object are also pointed by + // other structs. + v->set_il(0); + v->set_il_tail(0); + + if (v->next() == 0 && v->child() == 0) + { + //FIXME: not generic enough... + v->set_ckey(T::plus_infty()); + return v; + } + node<T,R> *v_next_bak = v->next(); + v->set_next(sift(v->next())); + + // Cleanup possibly removed nodes. + while (v_next_bak != v->next()) + { + deep_clear_list(v_next_bak->next()); + deep_clear_list(v_next_bak->child()); + tmp = v_next_bak->next(); + delete v_next_bak; + v_next_bak = tmp; + } + + if (util::ord_strict(v->child()->ckey(), v->next()->ckey())) + { + // Swap child and next. + tmp = v->child(); + v->set_child(v->next()); + v->set_next(tmp); + } + + v->set_il(v->next()->il()); + v->set_il_tail(v->next()->il_tail()); + v->set_ckey(v->next()->ckey()); + + if (v->rank() > r_ && (v->rank() % 2 == 1 + || v->child()->rank() < static_cast<unsigned>((v->rank() - 1)))) + { + node<T,R> *v_next_bak = v->next(); + v->set_next(sift(v->next())); + + // Cleanup possibly removed nodes. + while (v_next_bak != v->next()) + { + deep_clear_list(v_next_bak->next()); + deep_clear_list(v_next_bak->child()); + tmp = v_next_bak->next(); + delete v_next_bak; + v_next_bak = tmp; + } + + if (util::ord_strict(v->child()->ckey(), v->next()->ckey())) + { + tmp = v->child(); + v->set_child(v->next()); + v->set_next(tmp); + } + + if (v->next()->ckey() != T::plus_infty() && v->next()->il() != 0) + { + v->next()->il_tail()->set_next(v->il()); + v->set_il(v->next()->il()); + if (v->il_tail() == 0) + v->set_il_tail(v->next()->il_tail()); + v->set_ckey(v->next()->ckey()); + } + } + + if (v->child()->ckey() == T::plus_infty()) + { + if (v->next()->ckey() == T::plus_infty()) + { + // Clear child and next lists. + deep_clear_list(v->child()); + deep_clear_list(v->next()); + + v->set_child(0); + v->set_next(0); + } + else + { + node<T,R> *next_bak = v->next(); + + // There may be several children, we must clear all of them. + deep_clear_list(v->child()); + + v->set_child(v->next()->child()); + v->set_next(v->next()->next()); + delete next_bak; + } + } + + return v; + } + + + template <typename T, typename R> + template <typename L> + inline + void + soft_heap<T,R>::clear_list(L *begin, L *end) + { + L *tmp; + while (begin != end) + { + tmp = begin->next(); + delete begin; + begin = tmp; + } + } + + + template <typename T, typename R> + template <typename L> + inline + void + soft_heap<T,R>::deep_clear_list(L *n) + { + L *current_node, *tmp; + std::stack<L *> st; + + st.push(n); + while (!st.empty()) + { + current_node = st.top(); + st.pop(); + while (current_node != 0) + { + if (current_node->child() != 0) + st.push(current_node->child()); + + tmp = current_node->next(); + delete current_node; + + current_node = tmp; + } + } + } + + + template <typename T, typename R> + inline + void + soft_heap<T,R>::debug_head_list() const + { + head<T,R> *n = header_; + std::cout << "Head list = " << std::endl; + while (n != 0) + { + std::cout << n->id << "("; + + node<T,R> *current_node; + std::stack< node<T,R> *> st; + st.push(n->queue()); + while (!st.empty()) + { + current_node = st.top(); + st.pop(); + while (current_node != 0) + { + if (current_node->child() != 0) + st.push(current_node->child()); + std::cout << current_node->id << ","; + current_node = current_node->next(); + } + } + + std::cout << ") - "; + n = n->next(); + } + std::cout << std::endl; + } + + + template <typename T, typename R> + inline + void + soft_heap<T,R>::println_() const + { + + std::cout << "===============" << std::endl; + head<T,R> *head = header_; + while (head != 0) + { + std::cout << "<Head>" << std::endl; + node<T,R> *node = head->queue(), *child; + while (node != 0) + { + std::cout << " <node>" << std::endl; + + ilcell_t il(node->il()); + while (il != 0) + { + std::cout << il->item() << std::endl; + il = il->next(); + } + + child = node->child(); + while (child != 0) + { + std::cout << " <child>" << std::endl; + ilcell_t il(child->il()); + while (il != 0) + { + std::cout << il->item() << std::endl; + il = il->next(); + } + child = child->child(); + std::cout << " </child>" << std::endl; + } + node = node->next(); + + std::cout << " </node>" << std::endl; + } + std::cout << "</Head>" << std::endl; + head = head->next(); + } + } + + +# endif // ! MLN_INCLUDE_ONLY + + + } // end of namespace mln::util + +} // end of namespace mln + + +#endif // ! MLN_UTIL_FAST_HEAP_HH diff --git a/milena/mln/util/tracked_ptr.hh b/milena/mln/util/tracked_ptr.hh index 6d22451..0148880 100644 --- a/milena/mln/util/tracked_ptr.hh +++ b/milena/mln/util/tracked_ptr.hh @@ -1,4 +1,5 @@ -// Copyright (C) 2006 EPITA Research and Development Laboratory +// Copyright (C) 2006, 2009 EPITA Research and Development Laboratory +// (LRDE) // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -28,12 +29,11 @@ #ifndef MLN_UTIL_TRACKED_PTR_HH # define MLN_UTIL_TRACKED_PTR_HH -/*! \file mln/util/tracked_ptr.hh - * - * \brief Definition of a smart pointer for shared data with tracking. - * - * \todo Split defs from decls. - */ +/// \file mln/util/tracked_ptr.hh +/// +/// Definition of a smart pointer for shared data with tracking. +/// +/// \todo Split defs from decls. # include <set> # include <iostream> @@ -63,16 +63,14 @@ namespace mln /// Negation (for arithmetical tests). bool operator !() const; - /*! \brief Mimics the behavior of op-> for a pointer in the const case. - ** - ** \invariant Pointer proxy exists. - */ + /// Mimics the behavior of op-> for a pointer in the const case. + /// + /// \invariant Pointer proxy exists. const T* operator->() const; - /*! \brief Mimics the behavior of op-> for a pointer in the mutable case. - ** - ** \invariant Pointer proxy exists. - */ + /// Mimics the behavior of op-> for a pointer in the mutable case. + /// + /// \invariant Pointer proxy exists. T* operator->(); /// Ctor. @@ -122,10 +120,9 @@ namespace mln } template <typename T> - /*! \brief Mimics the behavior of op-> for a pointer in the const case. - ** - ** \invariant Pointer proxy exists. - */ + /// Mimics the behavior of op-> for a pointer in the const case. + /// + /// \invariant Pointer proxy exists. inline const T* tracked_ptr<T>::operator->() const { @@ -135,10 +132,9 @@ namespace mln } template <typename T> - /*! \brief Mimics the behavior of op-> for a pointer in the mutable case. - ** - ** \invariant Pointer proxy exists. - */ + /// \brief Mimics the behavior of op-> for a pointer in the mutable case. + /// + /// \invariant Pointer proxy exists. inline T* tracked_ptr<T>::operator->() { @@ -201,7 +197,9 @@ namespace mln clean_(); ptr_ = rhs.ptr_; holders_ = rhs.holders_; - holders_->insert(this); + // If ptr == 0, holders_ == 0 so we cannot insert anything in it. + if (holders_ != 0) + holders_->insert(this); return *this; } diff --git a/milena/tests/unit_test/Makefile.am b/milena/tests/unit_test/Makefile.am index e055ee3..2eef268 100644 --- a/milena/tests/unit_test/Makefile.am +++ b/milena/tests/unit_test/Makefile.am @@ -64,6 +64,7 @@ mln_registration_icp \ mln_util_graph \ mln_util_max \ mln_util_lazy_set \ +mln_util_soft_heap \ mln_util_set \ mln_util_tree_to_image \ mln_util_lemmings \ @@ -1074,6 +1075,7 @@ mln_registration_icp_SOURCES = mln_registration_icp.cc mln_util_graph_SOURCES = mln_util_graph.cc mln_util_max_SOURCES = mln_util_max.cc mln_util_lazy_set_SOURCES = mln_util_lazy_set.cc +mln_util_soft_heap_SOURCES = mln_util_soft_heap.cc mln_util_set_SOURCES = mln_util_set.cc mln_util_tree_to_image_SOURCES = mln_util_tree_to_image.cc mln_util_lemmings_SOURCES = mln_util_lemmings.cc diff --git a/milena/tests/unit_test/mln_util_soft_heap.cc b/milena/tests/unit_test/mln_util_soft_heap.cc new file mode 100644 index 0000000..6a98bb0 --- /dev/null +++ b/milena/tests/unit_test/mln_util_soft_heap.cc @@ -0,0 +1,11 @@ +// Unit test for mln/util/soft_heap.hh. +// Generated by ./build_unit_test.sh, do not modify. + +// Include the file twice, so we detect missing inclusion guards. +#include <mln/util/soft_heap.hh> +#include <mln/util/soft_heap.hh> + +int main() +{ + // Nothing. +} diff --git a/milena/tests/util/Makefile.am b/milena/tests/util/Makefile.am index 0e9c5ab..1dcd5c5 100644 --- a/milena/tests/util/Makefile.am +++ b/milena/tests/util/Makefile.am @@ -12,6 +12,7 @@ check_PROGRAMS = \ lazy_set \ lemmings \ ord_pair \ + soft_heap \ tree \ tree_fast \ tree_fast_to_image \ @@ -26,6 +27,7 @@ graph_SOURCES = graph.cc lazy_set_SOURCES = lazy_set.cc lemmings_SOURCES = lemmings.cc ord_pair_SOURCES = ord_pair.cc +soft_heap_SOURCES = soft_heap.cc tree_SOURCES = tree.cc tree_fast_SOURCES = tree_fast.cc tree_fast_to_image_SOURCES = tree_to_image.cc diff --git a/milena/tests/util/soft_heap.cc b/milena/tests/util/soft_heap.cc new file mode 100644 index 0000000..d2bffcc --- /dev/null +++ b/milena/tests/util/soft_heap.cc @@ -0,0 +1,79 @@ +// Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library 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 library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +/// \file mln/core/site_set/p_soft_heap.hh +/// +/// Test for the soft heap (approximate priority queue). + +#include <mln/util/soft_heap.hh> +#include <mln/core/alias/point2d.hh> +#include <mln/value/int_u8.hh> + +using mln::point2d; + +point2d p[] = { point2d(4,5), point2d(3,4), point2d(3,2), + point2d(1,6), point2d(2,3), point2d(3,5), + point2d(2,4), point2d(7,2), point2d(9,6), + point2d(7,3) }; + +point2d res[] = { point2d(1,6), point2d(2,3), point2d(2,4), + point2d(3,2), point2d(3,4), point2d(3,5), + point2d(4,5), point2d(7,2), point2d(7,3), + point2d(9,6) }; + + +int main() +{ + using namespace mln; + + util::soft_heap<point2d, value::int_u8> fh; + + for (unsigned i = 0; i < 5; ++i) + fh.push(p[i]); + + util::soft_heap<point2d, value::int_u8> fh2; + for (unsigned i = 5; i < 10; ++i) + fh2.push(p[i]); + + // Merge fh in fh2. + fh2.take(fh); + + // fh2 now holds both its elements and fh's. + unsigned i = 0; + while (!fh2.is_empty()) + mln_assertion(fh2.pop_front() == res[i++]); + + // fh must be empty, fh2 now holds its elements. + mln_assertion(fh.is_empty()); + + for (unsigned i = 5; i < 10; ++i) + fh2.push(p[i]); + + fh2.clear(); + mln_assertion(fh2.nelements() == 0); + mln_assertion(fh2.is_empty()); +} -- 1.5.6.5