Logo  0.95.0-final
Finite Element Embedded Library and Language in C++
Feel++ Feel++ on Github Feel++ community
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
fmsheap.hpp
Go to the documentation of this file.
1 /* -*- mode: c++; coding: utf-8; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4; show-trailing-whitespace: t -*- vim:fenc=utf-8:ft=tcl:et:sw=4:ts=4:sts=4
2 
3  This file is part of the Feel library
4 
5  Author(s): Christoph Winkelmann <christoph.winkelmann@epfl.ch>
6  Date: 2006-10-23
7 
8  Copyright (C) 2005,2006 EPFL
9 
10  This library is free software; you can redistribute it and/or
11  modify it under the terms of the GNU Lesser General Public
12  License as published by the Free Software Foundation; either
13  version 3.0 of the License, or (at your option) any later version.
14 
15  This library is distributed in the hope that it will be useful,
16  but WITHOUT ANY WARRANTY; without even the implied warranty of
17  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18  Lesser General Public License for more details.
19 
20  You should have received a copy of the GNU Lesser General Public
21  License along with this library; if not, write to the Free Software
22  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23 */
29 #ifndef __FMS_Heap_H
30 #define __FMS_Heap_H 1
31 
32 namespace Feel
33 {
34 namespace details
35 {
36 
37 template<typename T>
38 class FmsHeap
39 {
40 
41 public:
42 
43  typedef T value_type;
44 
45  // pair < phi_value, index >
46  typedef std::pair<value_type, uint16_type> heap_entry_type;
47 
48  void push( heap_entry_type in )
49  {
50  M_heap.push_back( in );
51  push_heap( M_heap.begin(), M_heap.end(), farther );
52  }
53 
54  void change( heap_entry_type in )
55  {
56  for ( heapvect_iter it=M_heap.begin(); it != M_heap.end(); ++it )
57  {
58  // if the entry at index exists,
59  // this phi_entry take the min value between |phi_entry| and |phi_min|
60  if (it->second == in.second)
61  {
62  if ( farther( *it, in ) )
63  {
64  *it = in;
65  make_heap( M_heap.begin(),
66  M_heap.end(),
67  farther );
68  }
69  return;
70  }
71  }
72  // if not found, push
73  push( in );
74  }
75 
76  heap_entry_type pop()
77  {
78  // assert M_heap.size() > 0
79  heap_entry_type out = *(M_heap.begin());
80  pop_heap( M_heap.begin(), M_heap.end(), farther );
81  M_heap.pop_back();
82  return out;
83  }
84 
85 
86  bool checkExistingEntry(uint16_type index)
87  {
88  for (heapvect_iter it = M_heap.begin(); it != M_heap.end(); ++it )
89  if (it->second == index)
90  return true;
91  return false;
92  }
93 
94  bool removeFromHeap(uint16_type index)
95  {
96  bool removed = false;
97 
98  for (heapvect_iter it = M_heap.begin(); it != M_heap.end(); ++it )
99  if (it->second == index)
100  {
101  M_heap.erase(it);
102  removed = true;
103  break;
104  }
105 
106  return removed;
107  }
108 
109 
110  size_type size() const
111  {
112  return M_heap.size();
113  }
114 
115 private:
116 
117  typedef std::vector<heap_entry_type> heapvect_type;
118  typedef typename heapvect_type::iterator heapvect_iter;
119  typedef typename heapvect_type::const_iterator heapvect_constiter;
120 
121  static bool farther( heap_entry_type a, heap_entry_type b )
122  {
123  // returns true if |phi_a| > |phi_b|
124  value_type aa = a.first;
125  aa = aa < 0.0 ? -aa : aa;
126  value_type bb = b.first;
127  bb = bb < 0.0 ? -bb : bb;
128  return aa > bb;
129  }
130 
131  std::vector<heap_entry_type> M_heap;
132 };
133 
134 } // namespace details
135 
136 } // namespace Feel
137 
138 #endif /* __FMS_Heap_H */
size_t size_type
Indices (starting from 0)
Definition: feelcore/feel.hpp:319

Generated on Sun Dec 22 2013 13:11:00 for Feel++ by doxygen 1.8.5