1 // Copyright (C) 2007-2022 CEA/DEN, EDF R&D, OPEN CASCADE
3 // Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
6 // This library is free software; you can redistribute it and/or
7 // modify it under the terms of the GNU Lesser General Public
8 // License as published by the Free Software Foundation; either
9 // version 2.1 of the License, or (at your option) any later version.
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // Lesser General Public License for more details.
16 // You should have received a copy of the GNU Lesser General Public
17 // License along with this library; if not, write to the Free Software
18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
22 // File : SMDS_ElementFactory.hxx
25 #ifndef _SMDS_ElementFactory_HeaderFile
26 #define _SMDS_ElementFactory_HeaderFile
28 #include "SMDS_MeshCell.hxx"
29 #include "SMDS_Position.hxx"
31 #include <Utils_SALOME_Exception.hxx>
33 #include <boost/container/flat_set.hpp>
34 #include <boost/dynamic_bitset.hpp>
35 #include <boost/make_shared.hpp>
36 #include <boost/ptr_container/ptr_vector.hpp>
37 #include <boost/shared_ptr.hpp>
43 #include <smIdType.hxx>
45 class SMDS_ElementChunk;
50 struct _ChunkCompare {
51 bool operator () (const SMDS_ElementChunk* c1, const SMDS_ElementChunk* c2) const;
53 typedef boost::ptr_vector<SMDS_ElementChunk> TChunkVector;
54 typedef std::set<SMDS_ElementChunk*,_ChunkCompare> TChunkPtrSet;
56 //------------------------------------------------------------------------------------
58 * \brief Allocate SMDS_MeshElement's (SMDS_MeshCell's or SMDS_MeshNode's )
59 * and bind some attributes to elements:
60 * element ID, element VTK ID, sub-mesh ID, position on shape.
62 * Elements are allocated by chunks, so there are used and non-used elements
64 class SMDS_ElementFactory
67 bool myIsNodal; // what to allocate: nodes or cells
69 TChunkVector myChunks; // array of chunks of elements
70 TChunkPtrSet myChunksWithUnused; // sorted chunks having unused elements
71 std::vector< vtkIdType > myVtkIDs; // myVtkIDs[ smdsID-1 ] == vtkID
72 std::vector< smIdType > mySmdsIDs; // mySmdsIDs[ vtkID ] == smdsID - 1
73 smIdType myNbUsedElements; // counter of elements
75 friend class SMDS_ElementChunk;
79 SMDS_ElementFactory( SMDS_Mesh* mesh, const bool isNodal=false );
80 virtual ~SMDS_ElementFactory();
82 //! Return minimal ID of a non-used element
85 //! Return maximal ID of an used element
88 //! Return minimal ID of an used element
91 //! Return an element by ID. NULL if the element with the given ID is already used
92 SMDS_MeshElement* NewElement( const smIdType id );
94 //! Return a SMDS_MeshCell by ID. NULL if the cell with the given ID is already used
95 SMDS_MeshCell* NewCell( const smIdType id ) { return static_cast<SMDS_MeshCell*>( NewElement( id )); }
97 //! Return an used element by ID. NULL if the element with the given ID is not yet used
98 const SMDS_MeshElement* FindElement( const smIdType id ) const;
100 //! Return a number of used elements
101 smIdType NbUsedElements() const { return myNbUsedElements; }
103 //! Return an iterator on all element filtered using a given filter.
104 // nbElemsToReturn is used to optimize by stopping the iteration as soon as
105 // all elements satisfying filtering condition encountered.
106 template< class ElemIterator >
107 boost::shared_ptr< ElemIterator > GetIterator( SMDS_MeshElement::Filter* filter,
108 size_t nbElemsToReturn = -1 );
110 //! Return an iterator on all element assigned to a given shape.
111 // nbElemsToReturn is used to optimize by stopping the iteration as soon as
112 // all elements assigned to the shape encountered.
113 // sm1stElem is used to quickly find the first chunk holding elements of the shape;
114 // it must have smallest ID between elements on the shape
115 template< class ElemIterator >
116 boost::shared_ptr< ElemIterator > GetShapeIterator( int shapeID,
117 size_t nbElemsToReturn,
118 const SMDS_MeshElement* sm1stElem );
119 //! Clear marked flag of all elements
120 void SetAllNotMarked();
122 //! Mark the element as non-used
123 void Free( const SMDS_MeshElement* );
125 //! Return an SMDS ID by a Vtk one
126 smIdType FromVtkToSmds( vtkIdType vtkID );
128 //! De-allocate all elements
129 virtual void Clear();
131 //! Remove unused elements located not at the end of the last chunk.
132 // Minimize allocated memory
133 virtual void Compact(std::vector<smIdType>& idCellsOldToNew);
135 //! Return true if Compact() will change IDs of elements
136 virtual bool CompactChangePointers();
138 //! Return a number of elements in a chunk
139 static int ChunkSize();
142 //------------------------------------------------------------------------------------
144 * \brief Allocate SMDS_MeshNode's
146 class SMDS_NodeFactory : public SMDS_ElementFactory
148 std::vector<char> myShapeDim; // dimension of shapes
152 SMDS_NodeFactory( SMDS_Mesh* mesh );
155 //! Return a SMDS_MeshNode by ID. NULL if the node with the given ID is already used
156 SMDS_MeshNode* NewNode( smIdType id ) { return (SMDS_MeshNode*) NewElement(id); }
158 //! Return an used node by ID. NULL if the node with the given ID is not yet used
159 const SMDS_MeshNode* FindNode( smIdType id ) { return (const SMDS_MeshNode*) FindElement(id); }
161 //! Set a total number of sub-shapes in the main shape
162 void SetNbShapes( size_t nbShapes );
164 //! Return a dimension of a shape
165 int GetShapeDim( int shapeID ) const;
167 //! Set a dimension of a shape
168 void SetShapeDim( int shapeID, int dim );
170 //! De-allocate all nodes
171 virtual void Clear();
173 //! Remove unused nodes located not at the end of the last chunk.
174 // Minimize allocated memory
175 virtual void Compact(std::vector<smIdType>& idNodesOldToNew);
177 //! Return true if Compact() will change IDs of node
178 virtual bool CompactChangePointers();
181 //------------------------------------------------------------------------------------
183 * \brief Range of elements in a chunk having the same attribute value
185 template< typename ATTR>
190 attr_t myValue; // common attribute value
191 int my1st; // index in the chunk of the 1st element
192 _Range( int i0 = 0, attr_t v = 0 ): myValue( v ), my1st( i0 ) {}
194 bool operator < (const _Range& other) const { return my1st < other.my1st; }
197 typedef std::vector< std::pair< int, int > > TIndexRanges;
199 //------------------------------------------------------------------------------------
201 * \brief Sorted set of ranges
203 template< class RANGE >
206 typedef typename RANGE::attr_t attr_t;
207 typedef boost::container::flat_set< RANGE > set_t;
208 typedef typename set_t::const_iterator set_iterator;
212 _RangeSet() { mySet.insert( RANGE( 0, 0 )); }
215 * \brief Return a number of ranges
217 size_t Size() const { return mySet.size(); }
220 * \brief Return a mutable _Range::my1st of a range pointed by an iterator
222 int& First( set_iterator rangePtr ) { return const_cast< int& >( rangePtr->my1st ); }
225 * \brief Return a number of elements in a range pointed by an iterator
227 size_t Size( set_iterator rangePtr ) const
230 ( rangePtr + 1 == mySet.end() ) ? SMDS_ElementFactory::ChunkSize() : ( rangePtr + 1 )->my1st;
231 return next1st - rangePtr->my1st;
235 * \brief Return ranges of indices (from,to) of elements having a given value
237 bool GetIndices( const attr_t theValue, TIndexRanges & theIndices,
238 const attr_t* /*theMinValue*/ = 0, const attr_t* /*theMaxValue*/ = 0) const
240 bool isFound = false;
242 // if ( sizeof( attr_t ) == sizeof( int ) && theMinValue )
243 // if ( theValue < *theMinValue || theValue > *theMaxValue )
246 for ( set_iterator it = mySet.begin(); it < mySet.end(); ++it )
248 if ( it->myValue == theValue )
250 theIndices.push_back( std::make_pair( it->my1st, it->my1st + Size( it )));
252 ++it; // the next range value differs from theValue
259 * \brief Return value of an element attribute
260 * \param [in] theIndex - element index
261 * \return attr_t - attribute value
263 attr_t GetValue( int theIndex ) const
265 set_iterator r = mySet.upper_bound( theIndex ) - 1;
270 * \brief Change value of an element attribute
271 * \param [in] theIndex - element index
272 * \param [in] theValue - attribute value
273 * \return attr_t - previous value
275 attr_t SetValue( int theIndex, attr_t theValue )
277 set_iterator rNext = mySet.end(); // case of adding elements
278 set_iterator r = rNext - 1;
279 if ( r->my1st > theIndex )
281 rNext = mySet.upper_bound( theIndex );
284 int rSize = Size( r ); // range size
285 attr_t rValue = r->myValue;
286 if ( rValue == theValue )
287 return rValue; // it happens while compacting
289 if ( r->my1st == theIndex ) // theIndex is the first in the range
291 bool joinPrev = // can join theIndex to the previous range
292 ( r->my1st > 0 && ( r-1 )->myValue == theValue );
296 bool joinNext = // can join to the next range
297 ( rNext != mySet.end() && rNext->myValue == theValue );
301 if ( joinNext ) // && joinPrev
303 mySet.erase( r, r + 2 );
305 else // joinPrev && !joinNext
312 if ( joinNext ) // && !joinPrev
314 r = mySet.erase( r ); // then r points to the next range
317 else // !joinPrev && !joinNext
319 const_cast< attr_t & >( r->myValue ) = theValue;
331 r = mySet.insert( r, RANGE( theIndex + 1, rValue )) - 1;
332 const_cast< attr_t & >( r->myValue ) = theValue;
336 else if ( r->my1st + rSize - 1 == theIndex ) // theIndex is last in the range
338 if ( rNext != mySet.end() && rNext->myValue == theValue ) // join to the next
344 mySet.insert( r, RANGE( theIndex, theValue ));
347 else // theIndex in the middle of the range
349 r = mySet.insert( r, RANGE( theIndex, theValue ));
350 r = mySet.insert( r, RANGE( theIndex + 1, rValue ));
354 }; // struct _RangeSet
357 typedef _Range< int > _ShapeIDRange; // sub-mesh ID range
358 typedef _Range< bool > _UsedRange; // range of used elements
360 typedef _RangeSet< _ShapeIDRange > TSubIDRangeSet;
361 typedef _RangeSet< _UsedRange > TUsedRangeSet;
362 typedef boost::dynamic_bitset<> TBitSet;
363 //typedef float TParam;
364 typedef double TParam;
365 //typedef std::unordered_set<int> TSubIDSet;
367 //------------------------------------------------------------------------------------
369 * \brief Allocate SMDS_MeshElement's (SMDS_MeshCell's or SMDS_MeshNode's )
370 * and bind some attributes to elements:
371 * element ID, sub-shape ID, isMarked flag, parameters on shape
373 class SMDS_ElementChunk
375 SMDS_ElementFactory* myFactory; // holder of this chunk
376 SMDS_MeshElement* myElements; // array of elements
377 smIdType my1stID; // ID of myElements[0]
378 TBitSet myMarkedSet; // mark some elements
379 TUsedRangeSet myUsedRanges; // ranges of used/unused elements
380 TSubIDRangeSet mySubIDRanges; // ranges of elements on the same sub-shape
381 //TSubIDSet* mySubIDSet; // set of sub-shape IDs
382 // int myMinSubID; // min sub-shape ID
383 // int myMaxSubID; // max sub-shape ID
384 std::vector<TParam> myPositions; // UV parameters on shape: 2*param_t per an element
388 SMDS_ElementChunk( SMDS_ElementFactory* factory = 0, smIdType id0 = 0 );
389 ~SMDS_ElementChunk();
391 //! Return an element by an index [0,ChunkSize()]
392 SMDS_MeshElement* Element(int index) { return & myElements[index]; }
394 //! Return an element by an index [0,ChunkSize()]
395 const SMDS_MeshElement* Element(int index) const { return & myElements[index]; }
397 //! Return ID of the first non-used element
398 smIdType GetUnusedID() const;
400 //! Mark an element as used
401 void UseElement( const int index );
403 //! Mark an element as non-used
404 void Free( const SMDS_MeshElement* e );
406 //! Check if a given range holds used or non-used elements
407 static bool IsUsed( const _UsedRange& r ) { return r.myValue; }
409 //! Return index of an element in the chunk
410 int Index( const SMDS_MeshElement* e ) const { return (int)( e - myElements ); }
412 //! Return ID of the 1st element in the chunk
413 smIdType Get1stID() const { return my1stID; }
415 //! Return pointer to on-shape-parameters of a node
416 TParam* GetPositionPtr( const SMDS_MeshElement* node, bool allocate=false );
418 //! Return ranges of used/non-used elements
419 const TUsedRangeSet& GetUsedRanges() const { return myUsedRanges; }
420 const TUsedRangeSet& GetUsedRangesMinMax( bool& min, bool& max ) const
421 { min = false; max = true; return myUsedRanges; }
423 //! Return ranges of elements assigned to sub-shapes and min/max of sub-shape IDs
424 const TSubIDRangeSet& GetSubIDRangesMinMax( int& /*min*/, int& /*max*/ ) const
425 { /*min = myMinSubID; max = myMaxSubID;*/ return mySubIDRanges; }
427 //! Minimize allocated memory
431 void Dump() const; // debug
434 // Methods called by SMDS_MeshElement
436 smIdType GetID( const SMDS_MeshElement* e ) const;
438 vtkIdType GetVtkID( const SMDS_MeshElement* e ) const;
439 void SetVTKID( const SMDS_MeshElement* e, const vtkIdType id );
441 int GetShapeID( const SMDS_MeshElement* e ) const;
442 void SetShapeID( const SMDS_MeshElement* e, int shapeID ) const;
444 bool IsMarked ( const SMDS_MeshElement* e ) const;
445 void SetIsMarked( const SMDS_MeshElement* e, bool is );
446 void SetAllNotMarked();
448 SMDS_PositionPtr GetPosition( const SMDS_MeshNode* n ) const;
449 void SetPosition( const SMDS_MeshNode* n, const SMDS_PositionPtr& pos, int shapeID );
451 SMDS_Mesh* GetMesh() { return myFactory->myMesh; }
454 //------------------------------------------------------------------------------------
456 * \brief Iterator on elements in chunks
458 template< class ELEM_ITERATOR, class RANGE_SET >
459 struct _ChunkIterator : public ELEM_ITERATOR
461 typedef typename ELEM_ITERATOR::value_type element_type;
462 typedef SMDS_MeshElement::Filter* filter_ptr;
463 typedef typename RANGE_SET::attr_t attr_type;
464 typedef const RANGE_SET& (SMDS_ElementChunk::*get_rangeset_fun)(attr_type&, attr_type&) const;
466 const SMDS_MeshElement* myElement;
467 TIndexRanges myRanges;
469 const TChunkVector& myChunks;
471 get_rangeset_fun myGetRangeSetFun;
473 attr_type myMinValue;
474 attr_type myMaxValue;
476 size_t myNbElemsToReturn;
479 _ChunkIterator( const TChunkVector & theChunks,
480 get_rangeset_fun theGetRangeSetFun,
481 attr_type theAttrValue,
482 SMDS_MeshElement::Filter* theFilter,
483 size_t theNbElemsToReturn = -1,
484 int theChunkIndex = 0):
487 myChunks( theChunks ),
488 myChunkIndex( theChunkIndex-1 ),
489 myGetRangeSetFun( theGetRangeSetFun ),
490 myValue( theAttrValue ),
491 myFilter( theFilter ),
492 myNbElemsToReturn( theNbElemsToReturn ),
507 virtual element_type next()
509 element_type result = (element_type) myElement;
510 myNbReturned += bool( result );
513 if ( myNbReturned < myNbElemsToReturn )
514 while ( ! nextInRange() )
516 if ( ++myRangeIndex >= (int)myRanges.size() )
520 while ( ++myChunkIndex < (int)myChunks.size() &&
521 !getRangeSet().GetIndices( myValue, myRanges, &myMinValue, &myMaxValue ))
523 if ( myChunkIndex >= (int)myChunks.size() )
532 if ( myRangeIndex < (int)myRanges.size() )
534 std::pair< int, int > & range = myRanges[ myRangeIndex ];
535 while ( range.first < range.second && !myElement )
537 myElement = myChunks[ myChunkIndex ].Element( range.first++ );
538 if ( !(*myFilter)( myElement ))
545 const RANGE_SET& getRangeSet()
547 return ( myChunks[ myChunkIndex ].*myGetRangeSetFun )( myMinValue, myMaxValue );
549 }; // struct _ChunkIterator
552 template< class ElemIterator >
553 boost::shared_ptr< ElemIterator >
554 SMDS_ElementFactory::GetIterator( SMDS_MeshElement::Filter* filter,
555 size_t nbElemsToReturn )
557 typedef _ChunkIterator< ElemIterator, TUsedRangeSet > TChuckIterator;
558 return boost::make_shared< TChuckIterator >( myChunks,
559 & SMDS_ElementChunk::GetUsedRangesMinMax,
565 template< class ElemIterator >
566 boost::shared_ptr< ElemIterator >
567 SMDS_ElementFactory::GetShapeIterator( int shapeID,
568 size_t nbElemsToReturn,
569 const SMDS_MeshElement* sm1stElem )
571 smIdType iChunk = sm1stElem ? (( sm1stElem->GetID() - 1 ) / ChunkSize()) : 0;
572 typedef _ChunkIterator< ElemIterator, TSubIDRangeSet > TChuckIterator;
573 return boost::make_shared< TChuckIterator >( myChunks,
574 & SMDS_ElementChunk::GetSubIDRangesMinMax,
576 new SMDS_MeshElement::NonNullFilter(),