Mesh Oriented datABase  (version 5.5.1)
An array-based unstructured mesh library
MeshSet.cpp
Go to the documentation of this file.
1 #ifdef WIN32
2 #ifdef _DEBUG
3 // turn off warnings that say they debugging identifier has been truncated
4 // this warning comes up when using some STL containers
5 #pragma warning( disable : 4786 )
6 #endif
7 #endif
8 
9 #include "MeshSet.hpp"
10 #include "AEntityFactory.hpp"
11 
12 namespace moab
13 {
14 
15 /*****************************************************************************************
16  * Helper Function Declarations *
17  *****************************************************************************************/
18 
19 /**\brief Insert into parent/child list */
20 static inline MeshSet::Count insert_in_vector( const MeshSet::Count count,
21  MeshSet::CompactList& list,
22  const EntityHandle h,
23  int& result );
24 
25 /**\brief Remvoe from parent/child list */
26 static inline MeshSet::Count remove_from_vector( const MeshSet::Count count,
27  MeshSet::CompactList& list,
28  const EntityHandle h,
29  int& result );
30 
31 /**\brief Resize MeshSet::CompactList. Returns pointer to storage */
32 static EntityHandle* resize_compact_list( MeshSet::Count& count, MeshSet::CompactList& clist, size_t new_list_size );
33 /**\brief Methods to insert/remove range-based data from contents list.
34  * Templatized to operate on both Range and set-based MeshSets.
35  */
36 template < typename pair_iter_t >
38 {
39  public:
40  /** Insert range-based data into range-based MeshSet */
41  inline static ErrorCode ranged_insert_entities( MeshSet::Count& count,
42  MeshSet::CompactList& clist,
43  pair_iter_t begin,
44  pair_iter_t end,
45  EntityHandle my_handle,
46  AEntityFactory* adj );
47 
48  /** Remove range-based data from range-based MeshSet */
49  inline static ErrorCode ranged_remove_entities( MeshSet::Count& count,
50  MeshSet::CompactList& clist,
51  pair_iter_t begin,
52  pair_iter_t end,
53  EntityHandle my_handle,
54  AEntityFactory* adj );
55 
56  /** Insert range-based data into list-based MeshSet */
57  inline static ErrorCode vector_insert_entities( MeshSet::Count& count,
58  MeshSet::CompactList& clist,
59  pair_iter_t begin,
60  pair_iter_t end,
61  EntityHandle my_handle,
62  AEntityFactory* adj );
63 };
64 
65 /** Remove Range of handles fromr vector-based MeshSet */
67  MeshSet::CompactList& clist,
68  const Range& range,
69  EntityHandle my_handle,
70  AEntityFactory* adj );
71 
72 /** Remove range-based MeshSet contents from vector-based MeshSet */
74  MeshSet::CompactList& clist,
75  const EntityHandle* pair_list,
76  size_t num_pairs,
77  EntityHandle my_handle,
78  AEntityFactory* adj );
79 
80 /** Remove unsorted array of handles from vector-based MeshSet */
82  MeshSet::CompactList& clist,
83  const EntityHandle* vect,
84  size_t vect_size,
85  EntityHandle my_handle,
86  AEntityFactory* adj );
87 
88 /** Insert unsorted array of handles into vector-based MeshSet */
90  MeshSet::CompactList& clist,
91  const EntityHandle* vect,
92  size_t vect_size,
93  EntityHandle my_handle,
94  AEntityFactory* adj );
95 
96 /** Convert unsorted array of handles into array of ranged [begin,end] pairs */
97 static void convert_to_ranges( const EntityHandle* vect_in, size_t vect_in_len, std::vector< EntityHandle >& vect_out );
98 
99 /*****************************************************************************************
100  * Parent/Child Operations *
101  *****************************************************************************************/
102 
103 static inline MeshSet::Count insert_in_vector( const MeshSet::Count count,
104  MeshSet::CompactList& list,
105  const EntityHandle h,
106  int& result )
107 {
108  switch( count )
109  {
110  case MeshSet::ZERO:
111  list.hnd[0] = h;
112  result = true;
113  return MeshSet::ONE;
114  case MeshSet::ONE:
115  if( list.hnd[0] == h )
116  {
117  result = false;
118  return MeshSet::ONE;
119  }
120  else
121  {
122  result = true;
123  list.hnd[1] = h;
124  return MeshSet::TWO;
125  }
126  case MeshSet::TWO:
127  if( list.hnd[0] == h || list.hnd[1] == h )
128  {
129  result = false;
130  return MeshSet::TWO;
131  }
132  else
133  {
134  EntityHandle* ptr = (EntityHandle*)malloc( 3 * sizeof( EntityHandle ) );
135  ptr[0] = list.hnd[0];
136  ptr[1] = list.hnd[1];
137  ptr[2] = h;
138  list.ptr[0] = ptr;
139  list.ptr[1] = ptr + 3;
140  result = true;
141  return MeshSet::MANY;
142  }
143  case MeshSet::MANY:
144  if( std::find( list.ptr[0], list.ptr[1], h ) != list.ptr[1] )
145  {
146  result = false;
147  }
148  else
149  {
150  int size = list.ptr[1] - list.ptr[0];
151  list.ptr[0] = (EntityHandle*)realloc( list.ptr[0], ( size + 1 ) * sizeof( EntityHandle ) );
152  list.ptr[0][size] = h;
153  list.ptr[1] = list.ptr[0] + size + 1;
154  result = true;
155  }
156  return MeshSet::MANY;
157  }
158 
159  return MeshSet::ZERO;
160 }
161 
163  MeshSet::CompactList& list,
164  const EntityHandle h,
165  int& result )
166 {
167  switch( count )
168  {
169  case MeshSet::ZERO:
170  result = false;
171  return MeshSet::ZERO;
172  case MeshSet::ONE:
173  if( h == list.hnd[0] )
174  {
175  result = true;
176  return MeshSet::ZERO;
177  }
178  else
179  {
180  result = false;
181  return MeshSet::ONE;
182  }
183  case MeshSet::TWO:
184  if( h == list.hnd[0] )
185  {
186  list.hnd[0] = list.hnd[1];
187  result = true;
188  return MeshSet::ONE;
189  }
190  else if( h == list.hnd[1] )
191  {
192  result = true;
193  return MeshSet::ONE;
194  }
195  else
196  {
197  result = false;
198  return MeshSet::TWO;
199  }
200  case MeshSet::MANY: {
201  EntityHandle *i, *j, *p;
202  i = std::find( list.ptr[0], list.ptr[1], h );
203  if( i == list.ptr[1] )
204  {
205  result = false;
206  return MeshSet::MANY;
207  }
208 
209  result = true;
210  p = list.ptr[1] - 1;
211  while( i != p )
212  {
213  j = i + 1;
214  *i = *j;
215  i = j;
216  }
217  int size = p - list.ptr[0];
218  if( size == 2 )
219  {
220  p = list.ptr[0];
221  list.hnd[0] = p[0];
222  list.hnd[1] = p[1];
223  free( p );
224  return MeshSet::TWO;
225  }
226  else
227  {
228  list.ptr[0] = (EntityHandle*)realloc( list.ptr[0], size * sizeof( EntityHandle ) );
229  list.ptr[1] = list.ptr[0] + size;
230  return MeshSet::MANY;
231  }
232  }
233  }
234 
235  return MeshSet::ZERO;
236 }
237 
239 {
240  int result = 0;
242  return result;
243 }
245 {
246  int result = 0;
248  return result;
249 }
250 
252 {
253  int result = 0;
255  return result;
256 }
258 {
259  int result = 0;
261  return result;
262 }
263 
264 /*****************************************************************************************
265  * Flag Conversion Operations *
266  *****************************************************************************************/
267 
268 ErrorCode MeshSet::convert( unsigned flg, EntityHandle my_handle, AEntityFactory* adj )
269 {
270  ErrorCode rval = MB_SUCCESS;
271  if( ( mFlags & MESHSET_TRACK_OWNER ) && !( flg & MESHSET_TRACK_OWNER ) )
272  rval = remove_adjacencies( my_handle, adj );
273  else if( !( mFlags & MESHSET_TRACK_OWNER ) && ( flg & MESHSET_TRACK_OWNER ) )
274  rval = create_adjacencies( my_handle, adj );
275  if( MB_SUCCESS != rval ) return rval;
276 
277  if( !( mFlags & MESHSET_ORDERED ) && ( flg & MESHSET_ORDERED ) )
278  {
279  size_t datalen;
280  EntityHandle* data = get_contents( datalen );
281  if( datalen )
282  {
283  std::vector< EntityHandle > list( datalen );
284  memcpy( &list[0], data, datalen * sizeof( EntityHandle ) );
285  int num_ents = num_entities();
286  Count count = (Count)mContentCount;
287  data = resize_compact_list( count, contentList, num_ents );
288  mContentCount = count;
289  assert( list.size() % 2 == 0 );
290  std::vector< EntityHandle >::iterator i = list.begin();
291  while( i != list.end() )
292  {
293  EntityHandle h = *i;
294  ++i;
295  EntityHandle e = *i;
296  ++i;
297  for( ; h <= e; ++h )
298  {
299  *data = h;
300  ++data;
301  }
302  }
303  }
304  }
305  else if( ( mFlags & MESHSET_ORDERED ) && !( flg & MESHSET_ORDERED ) )
306  {
307  size_t datalen;
308  EntityHandle* data = get_contents( datalen );
309  if( datalen )
310  {
311  std::vector< EntityHandle > ranges;
312  convert_to_ranges( data, datalen, ranges );
313  Count count = (Count)mContentCount;
314  data = resize_compact_list( count, contentList, ranges.size() );
315  mContentCount = count;
316  memcpy( data, &ranges[0], ranges.size() * sizeof( EntityHandle ) );
317  }
318  }
319 
320  return MB_SUCCESS;
321 }
322 
324 {
325  ErrorCode rval = MB_SUCCESS;
326  ;
327  size_t count;
328  const EntityHandle* const ptr = get_contents( count );
329  const EntityHandle* const end = ptr + count;
330  if( vector_based() )
331  {
332  for( const EntityHandle* i = ptr; i != end; ++i )
333  {
334  rval = adj->add_adjacency( *i, my_handle, false );
335  if( MB_SUCCESS != rval )
336  {
337  for( const EntityHandle* j = ptr; j != i; ++j )
338  adj->remove_adjacency( *j, my_handle );
339  return rval;
340  }
341  }
342  }
343  else
344  {
345  assert( 0 == count % 2 );
346  for( const EntityHandle* i = ptr; i != end; i += 2 )
347  {
348  for( EntityHandle h = i[0]; h <= i[1]; ++h )
349  {
350  rval = adj->add_adjacency( h, my_handle, false );
351  if( MB_SUCCESS != rval )
352  {
353  for( EntityHandle j = i[0]; j < h; ++j )
354  adj->remove_adjacency( j, my_handle );
355  for( const EntityHandle* j = ptr; j != i; j += 2 )
356  for( EntityHandle k = j[0]; k <= j[1]; ++k )
357  adj->remove_adjacency( k, my_handle );
358  return rval;
359  }
360  }
361  }
362  }
363  return MB_SUCCESS;
364 }
365 
367 {
368  size_t count;
369  const EntityHandle* const ptr = get_contents( count );
370  const EntityHandle* const end = ptr + count;
371  if( vector_based() )
372  {
373  for( const EntityHandle* i = ptr; i != end; ++i )
374  adj->remove_adjacency( *i, my_handle );
375  }
376  else
377  {
378  assert( 0 == count % 2 );
379  for( const EntityHandle* i = ptr; i != end; i += 2 )
380  for( EntityHandle h = i[0]; h <= i[1]; ++h )
381  adj->remove_adjacency( h, my_handle );
382  }
383  return MB_SUCCESS;
384 }
385 
386 /*****************************************************************************************
387  * Contents Modifiction Methods *
388  *****************************************************************************************/
389 
390 static EntityHandle* resize_compact_list( MeshSet::Count& count, MeshSet::CompactList& clist, size_t new_list_size )
391 {
392  if( count <= 2 )
393  {
394  if( new_list_size <= 2 )
395  {
396  count = (MeshSet::Count)new_list_size;
397  return clist.hnd;
398  }
399  else
400  {
401  EntityHandle* list = (EntityHandle*)malloc( new_list_size * sizeof( EntityHandle ) );
402  list[0] = clist.hnd[0];
403  list[1] = clist.hnd[1];
404  clist.ptr[0] = list;
405  clist.ptr[1] = list + new_list_size;
406  count = MeshSet::MANY;
407  return list;
408  }
409  }
410  else if( new_list_size > 2 )
411  {
412  if( new_list_size > (size_t)( clist.ptr[1] - clist.ptr[0] ) )
413  clist.ptr[0] = (EntityHandle*)realloc( clist.ptr[0], new_list_size * sizeof( EntityHandle ) );
414  clist.ptr[1] = clist.ptr[0] + new_list_size;
415  count = MeshSet::MANY;
416  return clist.ptr[0];
417  }
418  else
419  {
420  EntityHandle* list = clist.ptr[0];
421  clist.hnd[0] = list[0];
422  clist.hnd[1] = list[1];
423  free( list );
424  count = (MeshSet::Count)new_list_size;
425  return clist.hnd;
426  }
427 }
428 
429 typedef std::pair< EntityHandle, EntityHandle > MeshSetRange;
430 
432 {
433  public:
434  bool operator()( const MeshSetRange& r, const MeshSetRange& h )
435  {
436  return r.second < h.first;
437  }
438 };
439 
440 template < typename pair_iter_t >
442  MeshSet::CompactList& clist,
443  pair_iter_t begin,
444  pair_iter_t end,
445  EntityHandle my_handle,
446  AEntityFactory* adj )
447 {
448  // first pass:
449  // 1) merge existing ranges
450  // 2) count number of new ranges that must be inserted
451  EntityHandle* list_ptr;
452  size_t list_size;
453  if( count < MeshSet::MANY )
454  {
455  list_ptr = clist.hnd;
456  list_size = count;
457  }
458  else
459  {
460  list_ptr = clist.ptr[0];
461  list_size = clist.ptr[1] - clist.ptr[0];
462  }
463 
464  MeshSetRange* list = reinterpret_cast< MeshSetRange* >( list_ptr );
465  assert( 0 == list_size % 2 );
466  assert( 2 * sizeof( EntityHandle ) == sizeof( MeshSetRange ) );
467  list_size /= 2;
468  MeshSetRange* const list_end = list + list_size;
469  MeshSetRange *list_read = list, *list_write = list;
470  pair_iter_t i = begin;
471 
472  // count number of range pairs that are straight insertions
473  // (don't overlap any range pair in the current set) that
474  // could not be inserted during the first pass.
475  size_t insert_count = 0;
476 
477  // merge lists
478  while( i != end )
479  {
480  // find first range that intersects the current input range
481 
482  // do binary search if no holes in current set contents
483  if( list_read == list_write )
484  {
485  // subtract one from i->first because if it is one greater
486  // then the the last value of some block, then we want that
487  // block to append to.
488  MeshSetRange tmp;
489  tmp.first = i->first - 1;
490  tmp.second = i->second;
491  list_write = std::lower_bound( list_read, list_end, tmp, MeshSetRComp() );
492  list_read = list_write;
493  }
494  // otherwise shift down until we find where we find a range block
495  // that intersects
496  else
497  while( list_read != list_end && list_read->second + 1 < i->first )
498  {
499  *list_write = *list_read;
500  ++list_write;
501  ++list_read;
502  }
503 
504  // handle any straight insertions of range blocks
505  for( ; i != end && ( list_read == list_end || i->second + 1 < list_read->first ); ++i )
506  {
507  // If we haven't removed any range pairs, we don't have space to
508  // insert here. Defer the insertion until later.
509  if( list_read == list_write )
510  {
511  ++insert_count;
512  }
513  else
514  {
515  if( adj )
516  for( EntityHandle j = i->first; j <= i->second; ++j )
517  adj->add_adjacency( j, my_handle, false );
518 
519  list_write->first = i->first;
520  list_write->second = i->second;
521  ++list_write;
522  }
523  }
524 
525  // merge all the stuff that gets merged into a single range pair
526  // from both the input list and the existing set data
527  if( list_read != list_end )
528  {
529  MeshSetRange working = *list_read; // copy because might be the same as list_write
530  ++list_read;
531 
532  // Check if we need to prepend to the existing block.
533  // We only need to check this for the first input range because
534  // after this working.first will always be the first possible handle
535  // in the merged set of ranges.
536  if( i != end && i->first < working.first && i->second + 1 >= working.first )
537  {
538  if( adj )
539  for( EntityHandle h = i->first; h < working.first; ++h )
540  adj->add_adjacency( h, my_handle, false );
541  working.first = i->first;
542  }
543 
544  // Now append from the input list and the remaining set contents
545  // until we've consolidated all overlapping/touching ranges.
546  bool done = false;
547  while( !done )
548  {
549  // does next set contents range touch working range?
550  bool set_overlap = list_read != list_end && list_read->first <= working.second + 1;
551  // does next input range touch working range?
552  bool inp_overlap = i != end && i->first <= working.second + 1;
553 
554  // if both ranges touch...
555  if( inp_overlap && set_overlap )
556  {
557  // if next set range is contained in working, skip it
558  if( list_read->second <= working.second ) ++list_read;
559  // if next input range is contained in working, skip it
560  else if( i->second <= working.second )
561  ++i;
562  // Otherwise set the working end to the smaller of the two
563  // ends: either the next set end or the next input end.
564  // We want the smaller of the two because the larger might
565  // intersect additional ranges in the other list.
566  else if( list_read->second <= i->second )
567  {
568  working.second = list_read->second;
569  ++list_read;
570  }
571  else
572  {
573  working.second = i->second;
574  ++i;
575  }
576  }
577  // If only the input range intersect the current working range...
578  else if( inp_overlap )
579  {
580  // Would it be more efficient to just extent 'working' to
581  // the end of the current input range? We'd end up adding
582  // adjacencies for for entities that are already in the tracking
583  // set and therefore already have the adjacency.
584  EntityHandle last = i->second;
585  if( list_read != list_end && list_read->first < last )
586  last = list_read->first - 1;
587  else
588  ++i;
589 
590  if( last > working.second )
591  {
592  if( adj )
593  for( EntityHandle h = working.second + 1; h <= last; ++h )
594  adj->add_adjacency( h, my_handle, false );
595 
596  working.second = last;
597  }
598  }
599  else if( set_overlap )
600  {
601  if( working.second < list_read->second ) working.second = list_read->second;
602  ++list_read;
603  }
604  else
605  {
606  done = true;
607  }
608  }
609 
610  assert( list_write < list_read );
611  *list_write = working;
612  ++list_write;
613  }
614  }
615 
616  // shuffle down entries to fill holes
617  if( list_read == list_write )
618  list_read = list_write = list_end;
619  else
620  while( list_read < list_end )
621  {
622  *list_write = *list_read;
623  ++list_read;
624  ++list_write;
625  }
626 
627  // adjust allocated array size
628  const size_t occupied_size = list_write - list;
629  const size_t new_list_size = occupied_size + insert_count;
630  list_ptr = resize_compact_list( count, clist, 2 * new_list_size );
631  // done?
632  if( !insert_count ) return MB_SUCCESS;
633  list = reinterpret_cast< MeshSetRange* >( list_ptr );
634 
635  // Second pass: insert non-mergable range pairs
636  // All range pairs in the input are either completely disjoint from
637  // the ones in the mesh set and must be inserted or are entirely contained
638  // within a range pair in the mesh set.
639  assert( begin != end ); // can't have items to insert if given empty input list
640  pair_iter_t ri = end;
641  --ri;
642  list_write = list + new_list_size - 1;
643  list_read = list + occupied_size - 1;
644  for( ; list_write >= list; --list_write )
645  {
646  if( list_read >= list )
647  {
648  while( ri->first >= list_read->first && ri->second <= list_read->second )
649  {
650  assert( ri != begin );
651  --ri;
652  }
653 
654  if( list_read->first > ri->second )
655  {
656  *list_write = *list_read;
657  --list_read;
658  continue;
659  }
660  }
661 
662  assert( insert_count > 0 );
663  if( adj )
664  for( EntityHandle h = ri->first; h <= ri->second; ++h )
665  adj->add_adjacency( h, my_handle, false );
666  list_write->first = ri->first;
667  list_write->second = ri->second;
668 
669  // don't have reverse iterator, so check before decrement
670  // if insert_count isn't zero, must be more in range
671  if( 0 == --insert_count )
672  {
673  assert( list_read == list_write - 1 );
674  break;
675  }
676  else
677  {
678  --ri;
679  }
680  }
681 
682  assert( !insert_count );
683  return MB_SUCCESS;
684 }
685 
686 template < typename pair_iter_t >
688  MeshSet::CompactList& clist,
689  pair_iter_t begin,
690  pair_iter_t end,
691  EntityHandle my_handle,
692  AEntityFactory* adj )
693 {
694  // first pass:
695  // 1) remove (from) existing ranges
696  // 2) count number of ranges that must be split
697  ptrdiff_t split_count = 0;
698  EntityHandle* list;
699  size_t list_size;
700  if( count < MeshSet::MANY )
701  {
702  list = clist.hnd;
703  list_size = count;
704  }
705  else
706  {
707  list = clist.ptr[0];
708  list_size = clist.ptr[1] - clist.ptr[0];
709  }
710 
711  EntityHandle* list_write = list;
712  EntityHandle *const list_end = list + list_size, *list_read = list;
713  pair_iter_t i = begin;
714 
715  while( list_read != list_end && i != end )
716  {
717 
718  while( i != end && i->second < list_read[0] )
719  ++i;
720  if( i == end ) break;
721 
722  // if there are holes in the current array, shuffle blocks
723  // down until we find the next block to remove
724  if( list_read != list_write )
725  {
726  while( list_read != list_end && i->second < list_read[0] )
727  {
728  list_write[0] = list_read[0];
729  list_write[1] = list_read[1];
730  list_write += 2;
731  list_read += 2;
732  }
733  }
734  // otherwise do a binary search
735  else
736  {
737  list_write = std::lower_bound( list_write, list_end, i->first );
738  // if in middle of range block (odd index), back up to start of block
739  list_write -= ( list_write - list ) % 2;
740  list_read = list_write;
741  }
742 
743  // if everything remaning is past end of set contents...
744  if( list_read == list_end ) break;
745 
746  // skip any remove pairs that aren't in the list
747  if( i->second < list_read[0] )
748  {
749  ++i;
750  continue;
751  }
752 
753  // Begin by assuming that we will keep the entire block
754  list_write[0] = list_read[0];
755  list_write[1] = list_read[1];
756  list_read += 2;
757 
758  for( ; i != end && i->first <= list_write[1]; ++i )
759  {
760  if( i->first <= list_write[0] )
761  {
762  // remove whole block
763  if( i->second >= list_write[1] )
764  {
765  if( adj )
766  for( EntityHandle h = list_write[0]; h <= list_write[1]; ++h )
767  adj->remove_adjacency( h, my_handle );
768  list_write -= 2;
769  break;
770  }
771  // remove from start of block
772  else if( i->second >= list_write[0] )
773  {
774  if( adj )
775  for( EntityHandle h = list_write[0]; h <= i->second; ++h )
776  adj->remove_adjacency( h, my_handle );
777  list_write[0] = i->second + 1;
778  }
779  }
780  else if( i->first <= list_write[1] )
781  {
782  // remove from end of block
783  if( i->second >= list_write[1] )
784  {
785  if( adj )
786  for( EntityHandle h = i->first; h <= list_write[1]; ++h )
787  adj->remove_adjacency( h, my_handle );
788  list_write[1] = i->first - 1;
789  // list_write += 2;
790  break;
791  }
792  // split block
793  else
794  {
795  if( adj )
796  for( EntityHandle h = i->first; h <= i->second; ++h )
797  adj->remove_adjacency( h, my_handle );
798 
799  if( list_read - list_write <= 2 )
800  {
801  ++split_count;
802  continue;
803  }
804  else
805  {
806  list_write[3] = list_write[1];
807  list_write[1] = i->first - 1;
808  list_write[2] = i->second + 1;
809  list_write += 2;
810  }
811  }
812  }
813  }
814  list_write += 2;
815  }
816 
817  // shuffle down entries to fill holes
818  if( list_read == list_write )
819  list_read = list_write = list_end;
820  else
821  while( list_read < list_end )
822  {
823  list_write[0] = list_read[0];
824  list_write[1] = list_read[1];
825  list_read += 2;
826  list_write += 2;
827  }
828 
829  // adjust allocated array size
830  const size_t occupied_size = list_write - list;
831  const size_t new_list_size = occupied_size + 2 * split_count;
832  list = resize_compact_list( count, clist, new_list_size );
833  // done?
834  if( !split_count ) return MB_SUCCESS;
835 
836  // Second pass: split range pairs
837  // All range pairs in the input are either already removed or
838  // require one of the existing range pairs to be split
839  assert( begin != end ); // can't have ranges to split if given empty input list
840  pair_iter_t ri = end;
841  --ri;
842  list_write = list + new_list_size - 2;
843  list_read = list + occupied_size - 2;
844  for( ; list_write >= list; list_write -= 2 )
845  {
846  if( list_read >= list )
847  {
848  while( ri->second > list_read[1] )
849  {
850  assert( ri != begin );
851  --ri;
852  }
853 
854  if( list_read[0] > ri->second )
855  {
856  list_write[0] = list_read[0];
857  list_write[1] = list_read[1];
858  list_read -= 2;
859  continue;
860  }
861  }
862 
863  assert( split_count > 0 );
864  list_write[0] = ri->second + 1;
865  list_write[1] = list_read[1];
866  list_read[1] = ri->first - 1;
867 
868  // don't have reverse iterator, so check before decrement
869  // if insert_count isn't zero, must be more in range
870  if( 0 == --split_count )
871  {
872  assert( list_read == list_write - 2 );
873  break;
874  }
875  else
876  {
877  --ri;
878  }
879  }
880 
881  assert( !split_count );
882  return MB_SUCCESS;
883 }
884 
885 template < typename pair_iter_t >
887  MeshSet::CompactList& clist,
888  pair_iter_t begin,
889  pair_iter_t end,
890  EntityHandle my_handle,
891  AEntityFactory* adj )
892 {
893  const size_t init_size = count < MeshSet::MANY ? (int)count : clist.ptr[1] - clist.ptr[0];
894  size_t add_size = 0;
895  for( pair_iter_t i = begin; i != end; ++i )
896  add_size += i->second - i->first + 1;
897  EntityHandle* list = resize_compact_list( count, clist, init_size + add_size );
898  EntityHandle* li = list + init_size;
899 
900  for( pair_iter_t i = begin; i != end; ++i )
901  {
902  for( EntityHandle h = i->first; h <= i->second; ++h )
903  {
904  if( adj ) adj->add_adjacency( h, my_handle, false );
905  *li = h;
906  ++li;
907  }
908  }
909 
910  return MB_SUCCESS;
911 }
912 
914  MeshSet::CompactList& clist,
915  const Range& range,
916  EntityHandle my_handle,
917  AEntityFactory* adj )
918 {
919  EntityHandle* list;
920  size_t list_size;
921  if( count < MeshSet::MANY )
922  {
923  list = clist.hnd;
924  list_size = count;
925  }
926  else
927  {
928  list = clist.ptr[0];
929  list_size = clist.ptr[1] - clist.ptr[0];
930  }
931 
932  const EntityHandle* const list_end = list + list_size;
933  EntityHandle* list_write = list;
934  for( const EntityHandle* list_read = list; list_read != list_end; ++list_read )
935  {
936  if( range.find( *list_read ) == range.end() )
937  { // keep
938  *list_write = *list_read;
939  ++list_write;
940  }
941  else if( adj )
942  {
943  adj->remove_adjacency( *list_read, my_handle );
944  }
945  }
946 
947  resize_compact_list( count, clist, list_write - list );
948  return MB_SUCCESS;
949 }
950 
952  MeshSet::CompactList& clist,
953  const EntityHandle* pair_list,
954  size_t num_pairs,
955  EntityHandle my_handle,
956  AEntityFactory* adj )
957 {
958  EntityHandle* list;
959  size_t list_size;
960  if( count < MeshSet::MANY )
961  {
962  list = clist.hnd;
963  list_size = count;
964  }
965  else
966  {
967  list = clist.ptr[0];
968  list_size = clist.ptr[1] - clist.ptr[0];
969  }
970 
971  const EntityHandle *const list_end = list + list_size, *const input_end = pair_list + 2 * num_pairs;
972  EntityHandle* list_write = list;
973  for( const EntityHandle* list_read = list; list_read != list_end; ++list_read )
974  {
975  const EntityHandle* ptr = std::lower_bound( pair_list, input_end, *list_read );
976  if( ( ptr != input_end && ( *ptr == *list_read || ( ptr - pair_list ) % 2 ) ) && // if in delete list
977  std::find( list_read + 1, list_end, *list_read ) == list_end )
978  { // and is last occurance in list
979  // only remove adj if no previous occurance
980  if( adj && std::find( list, list_write, *list_read ) == list_write )
981  adj->remove_adjacency( *list_read, my_handle );
982  }
983  else
984  {
985  *list_write = *list_read;
986  ++list_write;
987  }
988  }
989 
990  resize_compact_list( count, clist, list_write - list );
991  return MB_SUCCESS;
992 }
993 
995  MeshSet::CompactList& clist,
996  const EntityHandle* vect,
997  size_t vect_size,
998  EntityHandle my_handle,
999  AEntityFactory* adj )
1000 {
1001  EntityHandle* list;
1002  size_t list_size;
1003  if( count < MeshSet::MANY )
1004  {
1005  list = clist.hnd;
1006  list_size = count;
1007  }
1008  else
1009  {
1010  list = clist.ptr[0];
1011  list_size = clist.ptr[1] - clist.ptr[0];
1012  }
1013 
1014  const EntityHandle *const list_end = list + list_size, *const input_end = vect + vect_size;
1015  EntityHandle* list_write = list;
1016  for( const EntityHandle* list_read = list; list_read != list_end; ++list_read )
1017  {
1018  if( std::find( vect, input_end, *list_read ) != input_end && // if in delete list
1019  std::find( list_read + 1, list_end, *list_read ) == list_end )
1020  { // and is last occurance in list
1021  // only remove adj if no previous occurance?
1022  if( adj ) // && std::find(list, list_write, *list_read) == list_write)
1023  adj->remove_adjacency( *list_read, my_handle );
1024  }
1025  else
1026  {
1027  *list_write = *list_read;
1028  ++list_write;
1029  }
1030  }
1031 
1032  resize_compact_list( count, clist, list_write - list );
1033  return MB_SUCCESS;
1034 }
1035 
1037  MeshSet::CompactList& clist,
1038  const EntityHandle* vect,
1039  size_t vect_size,
1040  EntityHandle my_handle,
1041  AEntityFactory* adj )
1042 {
1043  const size_t orig_size = count < MeshSet::MANY ? (int)count : clist.ptr[1] - clist.ptr[0];
1044  EntityHandle* list = resize_compact_list( count, clist, orig_size + vect_size );
1045  if( adj )
1046  for( size_t i = 0; i < vect_size; ++i )
1047  adj->add_adjacency( vect[i], my_handle, false );
1048  memcpy( list + orig_size, vect, sizeof( EntityHandle ) * vect_size );
1049  return MB_SUCCESS;
1050 }
1051 
1053  size_t len,
1054  EntityHandle my_h,
1055  AEntityFactory* adj )
1056 {
1057  typedef const std::pair< EntityHandle, EntityHandle >* pair_vect_t;
1058  pair_vect_t pair_vect = reinterpret_cast< pair_vect_t >( range_vect );
1059  MeshSet::Count count = static_cast< MeshSet::Count >( mContentCount );
1060  ErrorCode rval;
1061  if( !vector_based() )
1062  rval = range_tool< pair_vect_t >::ranged_insert_entities( count, contentList, pair_vect, pair_vect + len / 2,
1063  my_h, tracking() ? adj : 0 );
1064  else
1065  rval = range_tool< pair_vect_t >::vector_insert_entities( count, contentList, pair_vect, pair_vect + len / 2,
1066  my_h, tracking() ? adj : 0 );
1067  mContentCount = count;
1068  return rval;
1069 }
1070 
1072 {
1073  ErrorCode rval;
1074  MeshSet::Count count = static_cast< MeshSet::Count >( mContentCount );
1075  if( !vector_based() )
1077  count, contentList, range.const_pair_begin(), range.const_pair_end(), my_h, tracking() ? adj : 0 );
1078  else
1080  count, contentList, range.const_pair_begin(), range.const_pair_end(), my_h, tracking() ? adj : 0 );
1081  mContentCount = count;
1082  return rval;
1083 }
1084 
1086  size_t len,
1087  EntityHandle my_h,
1088  AEntityFactory* adj )
1089 {
1090  ErrorCode rval;
1091  MeshSet::Count count = static_cast< MeshSet::Count >( mContentCount );
1092  if( vector_based() )
1093  rval = vector_remove_ranges( count, contentList, range_vect, len / 2, my_h, tracking() ? adj : 0 );
1094  else
1095  {
1096  typedef const std::pair< EntityHandle, EntityHandle >* pair_vect_t;
1097  pair_vect_t pair_vect = reinterpret_cast< pair_vect_t >( range_vect );
1098  rval = range_tool< pair_vect_t >::ranged_remove_entities( count, contentList, pair_vect, pair_vect + len / 2,
1099  my_h, tracking() ? adj : 0 );
1100  }
1101  mContentCount = count;
1102  return rval;
1103 }
1104 
1106 {
1107  ErrorCode rval;
1108  MeshSet::Count count = static_cast< MeshSet::Count >( mContentCount );
1109  if( vector_based() )
1110  rval = vector_remove_range( count, contentList, range, my_h, tracking() ? adj : 0 );
1111  else
1113  count, contentList, range.const_pair_begin(), range.const_pair_end(), my_h, tracking() ? adj : 0 );
1114  mContentCount = count;
1115  return rval;
1116 }
1117 
1119 {
1120  ErrorCode rval;
1121  if( !vector_based() && !other->vector_based() )
1122  {
1123  size_t other_count = 0;
1124  const EntityHandle* other_vect = other->get_contents( other_count );
1125  if( !other_count ) return clear( my_handle, adj );
1126  assert( 0 == other_count % 2 );
1127 
1128  std::vector< EntityHandle > compliment;
1129  compliment.reserve( other_count + 4 );
1130  if( *other_vect > 0 )
1131  {
1132  compliment.push_back( 0 );
1133  compliment.push_back( *other_vect - 1 );
1134  }
1135  ++other_vect;
1136  const EntityHandle* const other_end = other_vect + other_count - 2;
1137  for( ; other_vect < other_end; other_vect += 2 )
1138  {
1139  compliment.push_back( other_vect[0] + 1 );
1140  compliment.push_back( other_vect[1] - 1 );
1141  }
1142  if( *other_vect < ~(EntityHandle)0 )
1143  {
1144  compliment.push_back( *other_vect + 1 );
1145  compliment.push_back( ~(EntityHandle)0 );
1146  }
1147 
1148  return remove_entity_ranges( &compliment[0], compliment.size(), my_handle, adj );
1149  }
1150  else
1151  {
1152  Range my_ents, other_ents;
1153  rval = get_entities( my_ents );
1154  if( MB_SUCCESS != rval ) return rval;
1155  rval = other->get_entities( other_ents );
1156  return remove_entities( moab::subtract( my_ents, other_ents ), my_handle, adj );
1157  }
1158 }
1159 
1160 static void convert_to_ranges( const EntityHandle* vect_in, size_t vect_in_len, std::vector< EntityHandle >& vect_out )
1161 {
1162  vect_out.reserve( 2 * vect_in_len );
1163  vect_out.resize( vect_in_len );
1164  std::copy( vect_in, vect_in + vect_in_len, vect_out.begin() );
1165  std::sort( vect_out.begin(), vect_out.end() );
1166  vect_out.erase( std::unique( vect_out.begin(), vect_out.end() ), vect_out.end() );
1167 
1168  // duplicate all entries
1169  vect_out.resize( vect_out.size() * 2 );
1170  for( long i = vect_out.size() - 1; i >= 0; --i )
1171  vect_out[i] = vect_out[i / 2];
1172 
1173  // compact adjacent ranges
1174  std::vector< EntityHandle >::iterator r = vect_out.begin(), w = vect_out.begin();
1175  while( r != vect_out.end() )
1176  {
1177  *w = *r;
1178  ++w;
1179  ++r;
1180  *w = *r;
1181  ++r;
1182 
1183  while( r != vect_out.end() && *w + 1 == *r )
1184  {
1185  ++r;
1186  *w = *r;
1187  ++r;
1188  }
1189  ++w;
1190  }
1191 
1192  // remove extra space
1193  vect_out.erase( w, vect_out.end() );
1194 }
1195 
1197 {
1198  MeshSet::Count count = static_cast< MeshSet::Count >( mContentCount );
1199  ErrorCode rval;
1200  if( vector_based() )
1201  rval = vector_insert_vector( count, contentList, vect, len, my_h, tracking() ? adj : 0 );
1202  else
1203  {
1204  std::vector< EntityHandle > rangevect;
1205  convert_to_ranges( vect, len, rangevect );
1206  typedef const std::pair< EntityHandle, EntityHandle >* pair_vect_t;
1207  pair_vect_t pair_vect = ( rangevect.empty() ) ? NULL : reinterpret_cast< pair_vect_t >( &rangevect[0] );
1209  count, contentList, pair_vect, pair_vect + rangevect.size() / 2, my_h, tracking() ? adj : 0 );
1210  }
1211  mContentCount = count;
1212  return rval;
1213 }
1214 
1216 {
1217  MeshSet::Count count = static_cast< MeshSet::Count >( mContentCount );
1218  ErrorCode rval;
1219  if( vector_based() )
1220  rval = vector_remove_vector( count, contentList, vect, len, my_h, tracking() ? adj : 0 );
1221  else
1222  {
1223  std::vector< EntityHandle > rangevect;
1224  convert_to_ranges( vect, len, rangevect );
1225  typedef const std::pair< EntityHandle, EntityHandle >* pair_vect_t;
1226  pair_vect_t pair_vect = ( rangevect.empty() ) ? NULL : reinterpret_cast< pair_vect_t >( &rangevect[0] );
1228  count, contentList, pair_vect, pair_vect + rangevect.size() / 2, my_h, tracking() ? adj : 0 );
1229  }
1230  mContentCount = count;
1231  return rval;
1232 }
1233 
1235  const EntityHandle* old_entities,
1236  const EntityHandle* new_entities,
1237  size_t num_ents,
1238  AEntityFactory* adjfact )
1239 {
1240  if( vector_based() )
1241  {
1242  ErrorCode result = MB_SUCCESS;
1243  size_t count;
1244  EntityHandle* vect = get_contents( count );
1245  EntityHandle* const vect_end = vect + count;
1246  for( size_t i = 0; i < num_ents; ++i )
1247  {
1248  EntityHandle* p = std::find( vect, vect_end, old_entities[i] );
1249  if( p == vect_end )
1250  {
1251  result = MB_ENTITY_NOT_FOUND;
1252  }
1253  else
1254  do
1255  {
1256  if( tracking() )
1257  {
1258  adjfact->remove_adjacency( *p, my_handle );
1259  adjfact->add_adjacency( new_entities[i], my_handle, false );
1260  }
1261  *p = new_entities[i];
1262  p = std::find( p + 1, vect_end, old_entities[i] );
1263  } while( p != vect_end );
1264  }
1265  return result;
1266  }
1267  else
1268  {
1269  ErrorCode r1 = remove_entities( old_entities, num_ents, my_handle, adjfact );
1270  ErrorCode r2 = add_entities( new_entities, num_ents, my_handle, adjfact );
1271  return ( MB_SUCCESS == r2 ) ? r1 : r2;
1272  }
1273 }
1274 
1275 /*****************************************************************************************
1276  * Misc. Methods *
1277  *****************************************************************************************/
1278 
1279 unsigned long MeshSet::get_memory_use() const
1280 {
1281  unsigned long result = 0;
1282  if( mParentCount == MANY ) result += parentMeshSets.ptr[1] - parentMeshSets.ptr[0];
1283  if( mChildCount == MANY ) result += childMeshSets.ptr[1] - childMeshSets.ptr[0];
1284  if( mContentCount == MANY ) result += contentList.ptr[1] - contentList.ptr[0];
1285  return sizeof( EntityHandle ) * result;
1286 }
1287 
1288 } // namespace moab