GetFEM  5.4.2
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  };
86 
87  template<class T, unsigned char pks> dnt_iterator<T, pks> &
88  dnt_iterator<T, pks>::operator ++()
89  { ++ib; ++id; while(id.in <= lt && !*ib) {++ib; ++id; } return *this; }
90 
91  template<class T, unsigned char pks = 5> struct dnt_const_iterator {
92  typedef T value_type;
93  typedef const value_type* pointer;
94  typedef const value_type& reference;
95  typedef size_t size_type;
96  typedef ptrdiff_t difference_type;
97  typedef std::bidirectional_iterator_tag iterator_category;
98 
99  typename dynamic_array<T,pks>::const_iterator id;
100  bit_vector::const_iterator ib;
101  size_type lt;
102 
103  dnt_const_iterator(void) {}
104  dnt_const_iterator(const dynamic_tas<T,pks> &da, size_type ii)
105  : id(da, ii), ib(da.index(), ii) { lt = da.index().last_true(); }
106  dnt_const_iterator(const dnt_iterator<T,pks> &it)
107  : id(it.id), ib(it.ib), lt(it.lt) { }
108 
109  inline size_type index(void) const { return id.index(); }
110 
111  dnt_const_iterator &operator ++()
112  { ++ib; ++id; while(id.in <= lt && !*ib) {++ib; ++id; } return *this; }
113  dnt_const_iterator &operator --()
114  { while (!*(--ib)) --id; --id; return *this; }
115  dnt_const_iterator operator ++(int)
116  { dnt_const_iterator tmp = *this; ++(*this); return tmp; }
117  dnt_const_iterator operator --(int)
118  { dnt_const_iterator tmp = *this; --(*this); return tmp; }
119 
120  difference_type operator -(const dnt_const_iterator &i) const
121  { return id - i.id; }
122 
123  reference operator *() const { return (*id); }
124  pointer operator->() const { return &(operator*()); }
125 
126  bool operator ==(const dnt_const_iterator &i) const
127  { return i.id == id;}
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 id < i.id;}
132  };
133 
134  template<class T, unsigned char pks> class dynamic_tas
135  : public dynamic_array<T, pks> {
136  protected :
137  bit_vector ind;
138 
139  public :
140  typedef typename dynamic_array<T, pks>::iterator iterator;
141  typedef typename dynamic_array<T, pks>::const_iterator const_iterator;
142  typedef dnt_iterator<T, pks> tas_iterator;
143  typedef dnt_const_iterator<T, pks> const_tas_iterator;
144  typedef typename dynamic_array<T, pks>::size_type size_type;
145 
146  size_type memsize(void) const
147  { return dynamic_array<T, pks>::memsize() + ind.memsize(); }
148  size_type size(void) const
149  { return (ind.card() == 0) ? 0 : (ind.last_true() + 1); }
150  size_type ind_first(void) const
151  { return (ind.card() == 0) ? 0 : ind.first_true(); }
152  size_type ind_last(void) const
153  { return (ind.card() == 0) ? 0 : ind.last_true(); }
154  size_type card(void) const { return ind.card(); }
155 
156  tas_iterator tas_begin(void)
157  { return tas_iterator(*this, ind, ind_first()); }
158  const_tas_iterator tas_begin(void) const
159  { return const_tas_iterator(*this, ind_first()); }
160  tas_iterator tas_end(void) { return tas_iterator(*this, ind, size()); }
161  const_tas_iterator tas_end(void) const
162  { return const_tas_iterator(*this, size()); }
163 
164  const bit_vector &index(void) const { return ind; }
165  bool index_valid(size_type i) const { return ind[i]; }
166  bool empty(void) const { return (ind.card() == 0); }
167 
168  void swap(size_type i, size_type j);
169  void compact(void);
170  size_type add(const T &e)
171  { size_type n=ind.first_false(); ind[n]=true; (*this)[n]=e; return n; }
172  void add_to_index(size_type i, const T &e) { ind[i]=true; (*this)[i]=e; }
173  void sup(size_type n) { ind[n] = false; }
174  void clear(void) { dynamic_array<T,pks>::clear(); ind.clear(); }
175  };
176 
177  template<class T, unsigned char pks>
178  void dynamic_tas<T, pks>::swap(size_type i, size_type j) {
179  bool ti = ind[i], tj = ind[j]; ind.swap(i,j);
180  if (!ti && tj) (*this)[i] = (*this)[j];
181  if (ti && !tj) (*this)[j] = (*this)[i];
182  if (ti && tj) std::swap((*this)[i], (*this)[j]);
183  }
184 
185  template<class T, unsigned char pks>
186  void dynamic_tas<T, pks>::compact(void) {
187  if (!empty())
188  while (ind.last_true() >= ind.card())
189  swap(ind.first_false(), ind.last_true());
190  }
191 }
192 
193 #endif /* DAL_TAS_H__ */
bgeot::size_type
size_t size_type
used as the common size type in the library
Definition: bgeot_poly.h:49
gmm::clear
void clear(L &l)
clear (fill with zeros) a vector or matrix.
Definition: gmm_blas.h:59
dal
Dynamic Array Library.
Definition: dal_backtrace.cc:29
dal_basic.h
Dynamic array class.
dal::dynamic_array::clear
void clear(void)
Clear and desallocate all the elements.
Definition: dal_basic.h:298
dal_bit_vector.h
Provide a dynamic bit container.
dal::dynamic_array::memsize
size_type memsize(void) const
Gives the total memory occupied by the array.
Definition: dal_basic.h:273
bgeot::operator-
rational_fraction< T > operator-(const polynomial< T > &P, const rational_fraction< T > &Q)
Subtract Q from P.
Definition: bgeot_poly.h:756
gmm::add
void add(const L1 &l1, L2 &l2)
*‍/
Definition: gmm_blas.h:1268