src/creaImageIOIndexedHeap.h

   1 /*
   2 # ---------------------------------------------------------------------
   3 #
   4 # Copyright (c) CREATIS (Centre de Recherche en Acquisition et Traitement de l'Image
   5 #                        pour la Santé)
   6 # Authors : Eduardo Davila, Frederic Cervenansky, Claire Mouton
   7 # Previous Authors : Laurent Guigues, Jean-Pierre Roux
   8 # CreaTools website : www.creatis.insa-lyon.fr/site/fr/creatools_accueil
   9 #
  10 #  This software is governed by the CeCILL-B license under French law and
  11 #  abiding by the rules of distribution of free software. You can  use,
  12 #  modify and/ or redistribute the software under the terms of the CeCILL-B
  13 #  license as circulated by CEA, CNRS and INRIA at the following URL
  14 #  http://www.cecill.info/licences/Licence_CeCILL-B_V1-en.html
  15 #  or in the file LICENSE.txt.
  16 #
  17 #  As a counterpart to the access to the source code and  rights to copy,
  18 #  modify and redistribute granted by the license, users are provided only
  19 #  with a limited warranty  and the software's author,  the holder of the
  20 #  economic rights,  and the successive licensors  have only  limited
  21 #  liability.
  22 #
  23 #  The fact that you are presently reading this means that you have had
  24 #  knowledge of the CeCILL-B license and that you accept its terms.
  25 # ------------------------------------------------------------------------
  26 */
  27
  28
  29 /*
  30
  31 */
  32 /*! \file
  33         \brief Indexed priority queues handled by binary trees.
  34 */
  35 #ifndef __creaImageIOIndexedHeap_h_INCLUDED__
  36 #define __creaImageIOIndexedHeap_h_INCLUDED__
  37
  38 #include <vector>
  39
  40 namespace creaImageIO
  41 {
  42
  43
  44
  45   template <class T,
  46             class Comparator/*=Less<T>*/,
  47             class Indexer/*=Index<T> */>
  48   class IndexedHeap ;
  49   template < class T,
  50              class C,
  51              class I>
  52   std::ostream& operator << (std::ostream&, const IndexedHeap<T,C,I>& );
  53
  54
  55   //template <class T, class Comparator=std::less<T>, class Index=IndexIndex<T> > class SlicedIndexedHeap;
  56
  57
  58   //========================================================================
  59   /// \brief Indexed priority queues handled by binary trees.
  60   ///
  61   ///   Heap Allows :
  62   ///           - log(n) insertion
  63   ///           - constant time acces to the first element
  64   ///           - log(n) removal of the first element
  65   ///           - log(n) priority change of a random element
  66   /// Indexation Allows :
  67   ///           - constant time access to a random element (for priority change)
  68   ///
  69   /// The Indexer is an unary_function<T,int&> whose operator()(T& t)
  70   /// returns a reference on an integer which
  71   /// is maintained by the IndexedHeap in order to provide at any time
  72   /// the position of the object t in the Heap
  73   /// (hence allowing constant time random access to an object).
  74   template <class T,
  75             class Comparator /*=Less<T>*/,
  76             class Indexer /*=Index<T>*/>
  77   class IndexedHeap
  78   {
  79     //                  friend class SlicedIndexedHeap<T,Comparator,Index>;
  80   public :
  81
  82     //======================================================================
  83     /// Constructor
  84     IndexedHeap () {}
  85     /// Constructor
  86     IndexedHeap ( const Comparator& comp, const Indexer& ind ) ;
  87     /// Destructor
  88     ~IndexedHeap() { }
  89     /// Sets the comparator
  90     void set( const Comparator& comp );
  91     /// Sets the Index
  92     void set( const Indexer& ind );
  93     //======================================================================
  94
  95     //======================================================================
  96     /// inserts an element in the Heap and returns its position
  97     int insert(T);
  98     /// return a reference on the first element of the Heap
  99     T& top();
 100     /// return a constant reference on the first element of the Heap
 101     const T& top() const;
 102     /// removes and returns the first element of the Heap
 103     T remove_top();
 104     /// removes and returns the nth element
 105     T remove(int n);
 106     /// returns the size of the Heap
 107     inline int size() const {return (int)m_p.size(); }
 108     /// empties the Heap
 109         void clear();
 110     //======================================================================
 111
 112     //======================================================================
 113     /// returns a constant on the stack of elements
 114     const std::vector<T> & stack() const {return m_p;}
 115     /// returns a reference to the ith element of the stack
 116     T& operator [] (int i) { return m_p[i];}
 117     /// returns a constant reference to the ith element of the stack
 118     const T& operator [] (int i) const { return m_p[i];}
 119     /// returns the index (position) of t
 120     inline int index(T& t) { return (*m_i)(t); }
 121     //======================================================================
 122
 123     //======================================================================
 124     /// returns the position of the father of i
 125     inline int father( int i ) const;
 126     /// returns the position of the right son of i
 127     inline int rightson( int i ) const;
 128     /// returns the position of the leftson of i
 129     inline int leftson( int i ) const;
 130     //======================================================================
 131     /// swaps ith and jth elements
 132     inline void swap(int i, int j);
 133     /// remonte un element dans le tas tant qu'il n'est pas a sa place.
 134     /// renvoie la position finale
 135     inline int upsort(int);
 136     /// descend un element dans le tas tant qu'il n'est pas a sa place.
 137     /// renvoie la position finale
 138     inline int downsort(int);
 139     //======================================================================
 140
 141   protected :
 142     /// binary tree handled by a vector
 143     std::vector<T> m_p;
 144     /// comparator pointer
 145     const Comparator* m_c;
 146     /// Index pointer
 147     const Indexer*  m_i;
 148   };
 149   //========================================================================
 150   // EO class IndexedHeap
 151   //========================================================================
 152
 153
 154 #include "creaImageIOIndexedHeap.txx"
 155
 156
 157 };
 158 //===========================================================================
 159 // EO namespace creaImageIO
 160 //===========================================================================
 161
 162
 163
 164 //===========================================================================
 165 // EOF
 166 //===========================================================================
 167 #endif