GetFEM  5.5
dal_tas.h
Go to the documentation of this file.
1 /* -*- c++ -*- (enables emacs c++ mode) */
2 /*===========================================================================
3 
4  Copyright (C) 1995-2026 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, see https://www.gnu.org/licenses/.
19 
20  As a special exception, you may use this file as it is a part of a free
21  software library without restriction. Specifically, if other files
22  instantiate templates or use macros or inline functions from this file,
23  or you compile this file and link it with other files to produce an
24  executable, this file does not by itself cause the resulting executable
25  to be covered by the GNU Lesser General Public License. This exception
26  does not however invalidate any other reasons why the executable file
27  might be covered by the GNU Lesser General Public License.
28 
29 ===========================================================================*/
30 
31 /**@file dal_tas.h
32  @author Yves Renard <[email protected]>
33  @date June 01, 1995.
34  @brief Heap implementation.
35 */
36 #ifndef DAL_TAS_H__
37 #define DAL_TAS_H__
38 
39 #include "dal_basic.h"
40 #include "dal_bit_vector.h"
41 
42 namespace dal
43 {
44 
45  template<class T, unsigned char pks = 5> class dynamic_tas;
46 
47  template<class T, unsigned char pks = 5> struct dnt_iterator
48  {
49  typedef T value_type;
50  typedef value_type* pointer;
51  typedef value_type& reference;
52  typedef size_t size_type;
53  typedef ptrdiff_t difference_type;
54  typedef std::bidirectional_iterator_tag iterator_category;
55 
56  typename dynamic_array<T,pks>::iterator id;
57  bit_vector::iterator ib;
58  size_type lt;
59 
60  dnt_iterator(void) {}
61  dnt_iterator(dynamic_tas<T,pks> &da, bit_vector &bv, size_type ii)
62  : id(da, ii), ib(bv, ii) { lt = da.index().last_true(); }
63 
64  inline size_type index(void) const { return id.index(); }
65 
66  dnt_iterator &operator ++();
67  dnt_iterator &operator --()
68  { while (!*(--ib)) --id; --id; return *this; }
69  dnt_iterator operator ++(int)
70  { dnt_iterator tmp = *this; ++(*this); return tmp; }
71  dnt_iterator operator --(int)
72  { dnt_iterator tmp = *this; --(*this); return tmp; }
73 
74  difference_type operator -(const dnt_iterator &i) const
75  { return id - i.id; }
76 
77 
78  reference operator *() const { return (*id); }
79  pointer operator->() const { return &(operator*()); }
80 
81  bool operator ==(const dnt_iterator &i) const { return i.id==id;}
82  bool operator !=(const dnt_iterator &i) const { return i.id!=id;}
83  bool operator < (const dnt_iterator &i) const { return id < i.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  };
87 
88  template<class T, unsigned char pks> dnt_iterator<T, pks> &
89  dnt_iterator<T, pks>::operator ++()
90  { ++ib; ++id; while(id.in <= lt && !*ib) {++ib; ++id; } return *this; }
91 
92  template<class T, unsigned char pks = 5> struct dnt_const_iterator {
93  typedef T value_type;
94  typedef const value_type* pointer;
95  typedef const value_type& reference;
96  typedef size_t size_type;
97  typedef ptrdiff_t difference_type;
98  typedef std::bidirectional_iterator_tag iterator_category;
99 
100  typename dynamic_array<T,pks>::const_iterator id;
101  bit_vector::const_iterator ib;
102  size_type lt;
103 
104  dnt_const_iterator(void) {}
105  dnt_const_iterator(const dynamic_tas<T,pks> &da, size_type ii)
106  : id(da, ii), ib(da.index(), ii) { lt = da.index().last_true(); }
107  dnt_const_iterator(const dnt_iterator<T,pks> &it)
108  : id(it.id), ib(it.ib), lt(it.lt) { }
109 
110  inline size_type index(void) const { return id.index(); }
111 
112  dnt_const_iterator &operator ++()
113  { ++ib; ++id; while(id.in <= lt && !*ib) {++ib; ++id; } return *this; }
114  dnt_const_iterator &operator --()
115  { while (!*(--ib)) --id; --id; return *this; }
116  dnt_const_iterator operator ++(int)
117  { dnt_const_iterator tmp = *this; ++(*this); return tmp; }
118  dnt_const_iterator operator --(int)
119  { dnt_const_iterator tmp = *this; --(*this); return tmp; }
120 
121  difference_type operator -(const dnt_const_iterator &i) const
122  { return id - i.id; }
123 
124  reference operator *() const { return (*id); }
125  pointer operator->() const { return &(operator*()); }
126 
127  bool operator ==(const dnt_const_iterator &i) const
128  { return i.id == id;}
129  bool operator !=(const dnt_const_iterator &i) const
130  { return i.id != id;}
131  bool operator < (const dnt_const_iterator &i) const
132  { return id < i.id;}
133  bool operator > (const dnt_const_iterator &i) const
134  { return id > i.id;}
135  bool operator >=(const dnt_const_iterator &i) const
136  { return id >= i.id;}
137  };
138 
139  template<class T, unsigned char pks> class dynamic_tas
140  : public dynamic_array<T, pks> {
141  protected :
142  bit_vector ind;
143 
144  public :
145  typedef typename dynamic_array<T, pks>::iterator iterator;
146  typedef typename dynamic_array<T, pks>::const_iterator const_iterator;
147  typedef dnt_iterator<T, pks> tas_iterator;
148  typedef dnt_const_iterator<T, pks> const_tas_iterator;
149  typedef typename dynamic_array<T, pks>::size_type size_type;
150 
151  size_type memsize(void) const
152  { return dynamic_array<T, pks>::memsize() + ind.memsize(); }
153  size_type size(void) const
154  { return (ind.card() == 0) ? 0 : (ind.last_true() + 1); }
155  size_type ind_first(void) const
156  { return (ind.card() == 0) ? 0 : ind.first_true(); }
157  size_type ind_last(void) const
158  { return (ind.card() == 0) ? 0 : ind.last_true(); }
159  size_type card(void) const { return ind.card(); }
160 
161  tas_iterator tas_begin(void)
162  { return tas_iterator(*this, ind, ind_first()); }
163  const_tas_iterator tas_begin(void) const
164  { return const_tas_iterator(*this, ind_first()); }
165  tas_iterator tas_end(void) { return tas_iterator(*this, ind, size()); }
166  const_tas_iterator tas_end(void) const
167  { return const_tas_iterator(*this, size()); }
168 
169  const bit_vector &index(void) const { return ind; }
170  bool index_valid(size_type i) const { return ind[i]; }
171  bool empty(void) const { return (ind.card() == 0); }
172 
173  void swap(size_type i, size_type j);
174  void compact(void);
175  size_type add(const T &e)
176  { size_type n=ind.first_false(); ind[n]=true; (*this)[n]=e; return n; }
177  void add_to_index(size_type i, const T &e) { ind[i]=true; (*this)[i]=e; }
178  void sup(size_type n) { ind[n] = false; }
179  void clear(void) { dynamic_array<T,pks>::clear(); ind.clear(); }
180  };
181 
182  template<class T, unsigned char pks>
183  void dynamic_tas<T, pks>::swap(size_type i, size_type j) {
184  bool ti = ind[i], tj = ind[j]; ind.swap(i,j);
185  if (!ti && tj) (*this)[i] = (*this)[j];
186  if (ti && !tj) (*this)[j] = (*this)[i];
187  if (ti && tj) std::swap((*this)[i], (*this)[j]);
188  }
189 
190  template<class T, unsigned char pks>
191  void dynamic_tas<T, pks>::compact(void) {
192  if (!empty())
193  while (ind.last_true() >= ind.card())
194  swap(ind.first_false(), ind.last_true());
195  }
196 }
197 
198 #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:278
dal::dynamic_array::clear
void clear(void)
Clear and desallocate all the elements.
Definition: dal_basic.h:303
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:58
gmm::add
void add(const L1 &l1, L2 &l2)
*‍/
Definition: gmm_blas.h:1275
bgeot::operator-
rational_fraction< T > operator-(const polynomial< T > &P, const rational_fraction< T > &Q)
Subtract Q from P.
Definition: bgeot_poly.h:755
bgeot::size_type
size_t size_type
used as the common size type in the library
Definition: bgeot_poly.h:48
dal
Dynamic Array Library.
Definition: dal_backtrace.cc:28