GetFEM  5.4.3
dal_tas.h
Go to the documentation of this file.
1 /* -*- c++ -*- (enables emacs c++ mode) */
2 /*===========================================================================
3 
4  Copyright (C) 1995-2020 Yves Renard
5 
6  This file is a part of GetFEM
7 
8  GetFEM is free software; you can redistribute it and/or modify it
9  under the terms of the GNU Lesser General Public License as published
10  by the Free Software Foundation; either version 3 of the License, or
11  (at your option) any later version along with the GCC Runtime Library
12  Exception either version 3.1 or (at your option) any later version.
13  This program is distributed in the hope that it will be useful, but
14  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
16  License and GCC Runtime Library Exception for more details.
17  You should have received a copy of the GNU Lesser General Public License
18  along with this program; if not, write to the Free Software Foundation,
19  Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
20 
21  As a special exception, you may use this file as it is a part of a free
22  software library without restriction. Specifically, if other files
23  instantiate templates or use macros or inline functions from this file,
24  or you compile this file and link it with other files to produce an
25  executable, this file does not by itself cause the resulting executable
26  to be covered by the GNU Lesser General Public License. This exception
27  does not however invalidate any other reasons why the executable file
28  might be covered by the GNU Lesser General Public License.
29 
30 ===========================================================================*/
31 
32 /**@file dal_tas.h
33  @author Yves Renard <Yves.Renard@insa-lyon.fr>
34  @date June 01, 1995.
35  @brief Heap implementation.
36 */
37 #ifndef DAL_TAS_H__
38 #define DAL_TAS_H__
39 
40 #include "dal_basic.h"
41 #include "dal_bit_vector.h"
42 
43 namespace dal
44 {
45 
46  template<class T, unsigned char pks = 5> class dynamic_tas;
47 
48  template<class T, unsigned char pks = 5> struct dnt_iterator
49  {
50  typedef T value_type;
51  typedef value_type* pointer;
52  typedef value_type& reference;
53  typedef size_t size_type;
54  typedef ptrdiff_t difference_type;
55  typedef std::bidirectional_iterator_tag iterator_category;
56 
57  typename dynamic_array<T,pks>::iterator id;
58  bit_vector::iterator ib;
59  size_type lt;
60 
61  dnt_iterator(void) {}
62  dnt_iterator(dynamic_tas<T,pks> &da, bit_vector &bv, size_type ii)
63  : id(da, ii), ib(bv, ii) { lt = da.index().last_true(); }
64 
65  inline size_type index(void) const { return id.index(); }
66 
67  dnt_iterator &operator ++();
68  dnt_iterator &operator --()
69  { while (!*(--ib)) --id; --id; return *this; }
70  dnt_iterator operator ++(int)
71  { dnt_iterator tmp = *this; ++(*this); return tmp; }
72  dnt_iterator operator --(int)
73  { dnt_iterator tmp = *this; --(*this); return tmp; }
74 
75  difference_type operator -(const dnt_iterator &i) const
76  { return id - i.id; }
77 
78 
79  reference operator *() const { return (*id); }
80  pointer operator->() const { return &(operator*()); }
81 
82  bool operator ==(const dnt_iterator &i) const { return i.id==id;}
83  bool operator !=(const dnt_iterator &i) const { return i.id!=id;}
84  bool operator < (const dnt_iterator &i) const { return id < i.id;}
85  bool operator > (const dnt_iterator &i) const { return id > i.id;}
86  bool operator >=(const dnt_iterator &i) const { return id >= i.id;}
87  };
88 
89  template<class T, unsigned char pks> dnt_iterator<T, pks> &
90  dnt_iterator<T, pks>::operator ++()
91  { ++ib; ++id; while(id.in <= lt && !*ib) {++ib; ++id; } return *this; }
92 
93  template<class T, unsigned char pks = 5> struct dnt_const_iterator {
94  typedef T value_type;
95  typedef const value_type* pointer;
96  typedef const value_type& reference;
97  typedef size_t size_type;
98  typedef ptrdiff_t difference_type;
99  typedef std::bidirectional_iterator_tag iterator_category;
100 
101  typename dynamic_array<T,pks>::const_iterator id;
102  bit_vector::const_iterator ib;
103  size_type lt;
104 
105  dnt_const_iterator(void) {}
106  dnt_const_iterator(const dynamic_tas<T,pks> &da, size_type ii)
107  : id(da, ii), ib(da.index(), ii) { lt = da.index().last_true(); }
108  dnt_const_iterator(const dnt_iterator<T,pks> &it)
109  : id(it.id), ib(it.ib), lt(it.lt) { }
110 
111  inline size_type index(void) const { return id.index(); }
112 
113  dnt_const_iterator &operator ++()
114  { ++ib; ++id; while(id.in <= lt && !*ib) {++ib; ++id; } return *this; }
115  dnt_const_iterator &operator --()
116  { while (!*(--ib)) --id; --id; return *this; }
117  dnt_const_iterator operator ++(int)
118  { dnt_const_iterator tmp = *this; ++(*this); return tmp; }
119  dnt_const_iterator operator --(int)
120  { dnt_const_iterator tmp = *this; --(*this); return tmp; }
121 
122  difference_type operator -(const dnt_const_iterator &i) const
123  { return id - i.id; }
124 
125  reference operator *() const { return (*id); }
126  pointer operator->() const { return &(operator*()); }
127 
128  bool operator ==(const dnt_const_iterator &i) const
129  { return i.id == id;}
130  bool operator !=(const dnt_const_iterator &i) const
131  { return i.id != id;}
132  bool operator < (const dnt_const_iterator &i) const
133  { return id < i.id;}
134  bool operator > (const dnt_const_iterator &i) const
135  { return id > i.id;}
136  bool operator >=(const dnt_const_iterator &i) const
137  { return id >= i.id;}
138  };
139 
140  template<class T, unsigned char pks> class dynamic_tas
141  : public dynamic_array<T, pks> {
142  protected :
143  bit_vector ind;
144 
145  public :
146  typedef typename dynamic_array<T, pks>::iterator iterator;
147  typedef typename dynamic_array<T, pks>::const_iterator const_iterator;
148  typedef dnt_iterator<T, pks> tas_iterator;
149  typedef dnt_const_iterator<T, pks> const_tas_iterator;
150  typedef typename dynamic_array<T, pks>::size_type size_type;
151 
152  size_type memsize(void) const
153  { return dynamic_array<T, pks>::memsize() + ind.memsize(); }
154  size_type size(void) const
155  { return (ind.card() == 0) ? 0 : (ind.last_true() + 1); }
156  size_type ind_first(void) const
157  { return (ind.card() == 0) ? 0 : ind.first_true(); }
158  size_type ind_last(void) const
159  { return (ind.card() == 0) ? 0 : ind.last_true(); }
160  size_type card(void) const { return ind.card(); }
161 
162  tas_iterator tas_begin(void)
163  { return tas_iterator(*this, ind, ind_first()); }
164  const_tas_iterator tas_begin(void) const
165  { return const_tas_iterator(*this, ind_first()); }
166  tas_iterator tas_end(void) { return tas_iterator(*this, ind, size()); }
167  const_tas_iterator tas_end(void) const
168  { return const_tas_iterator(*this, size()); }
169 
170  const bit_vector &index(void) const { return ind; }
171  bool index_valid(size_type i) const { return ind[i]; }
172  bool empty(void) const { return (ind.card() == 0); }
173 
174  void swap(size_type i, size_type j);
175  void compact(void);
176  size_type add(const T &e)
177  { size_type n=ind.first_false(); ind[n]=true; (*this)[n]=e; return n; }
178  void add_to_index(size_type i, const T &e) { ind[i]=true; (*this)[i]=e; }
179  void sup(size_type n) { ind[n] = false; }
180  void clear(void) { dynamic_array<T,pks>::clear(); ind.clear(); }
181  };
182 
183  template<class T, unsigned char pks>
184  void dynamic_tas<T, pks>::swap(size_type i, size_type j) {
185  bool ti = ind[i], tj = ind[j]; ind.swap(i,j);
186  if (!ti && tj) (*this)[i] = (*this)[j];
187  if (ti && !tj) (*this)[j] = (*this)[i];
188  if (ti && tj) std::swap((*this)[i], (*this)[j]);
189  }
190 
191  template<class T, unsigned char pks>
192  void dynamic_tas<T, pks>::compact(void) {
193  if (!empty())
194  while (ind.last_true() >= ind.card())
195  swap(ind.first_false(), ind.last_true());
196  }
197 }
198 
199 #endif /* DAL_TAS_H__ */
dal::dynamic_array::memsize
size_type memsize(void) const
Gives the total memory occupied by the array.
Definition: dal_basic.h:279
dal::dynamic_array::clear
void clear(void)
Clear and desallocate all the elements.
Definition: dal_basic.h:304
dal_basic.h
Dynamic array class.
dal_bit_vector.h
Provide a dynamic bit container.
gmm::clear
void clear(L &l)
clear (fill with zeros) a vector or matrix.
Definition: gmm_blas.h:59
gmm::add
void add(const L1 &l1, L2 &l2)
*‍/
Definition: gmm_blas.h:1277
bgeot::operator-
rational_fraction< T > operator-(const polynomial< T > &P, const rational_fraction< T > &Q)
Subtract Q from P.
Definition: bgeot_poly.h:756
bgeot::size_type
size_t size_type
used as the common size type in the library
Definition: bgeot_poly.h:49
dal
Dynamic Array Library.
Definition: dal_backtrace.cc:29