PCL
Array.h
Go to the documentation of this file.
1 // ____ ______ __
2 // / __ \ / ____// /
3 // / /_/ // / / /
4 // / ____// /___ / /___ PixInsight Class Library
5 // /_/ \____//_____/ PCL 02.01.12.0947
6 // ----------------------------------------------------------------------------
7 // pcl/Array.h - Released 2019-04-30T16:30:41Z
8 // ----------------------------------------------------------------------------
9 // This file is part of the PixInsight Class Library (PCL).
10 // PCL is a multiplatform C++ framework for development of PixInsight modules.
11 //
12 // Copyright (c) 2003-2019 Pleiades Astrophoto S.L. All Rights Reserved.
13 //
14 // Redistribution and use in both source and binary forms, with or without
15 // modification, is permitted provided that the following conditions are met:
16 //
17 // 1. All redistributions of source code must retain the above copyright
18 // notice, this list of conditions and the following disclaimer.
19 //
20 // 2. All redistributions in binary form must reproduce the above copyright
21 // notice, this list of conditions and the following disclaimer in the
22 // documentation and/or other materials provided with the distribution.
23 //
24 // 3. Neither the names "PixInsight" and "Pleiades Astrophoto", nor the names
25 // of their contributors, may be used to endorse or promote products derived
26 // from this software without specific prior written permission. For written
27 // permission, please contact info@pixinsight.com.
28 //
29 // 4. All products derived from this software, in any form whatsoever, must
30 // reproduce the following acknowledgment in the end-user documentation
31 // and/or other materials provided with the product:
32 //
33 // "This product is based on software from the PixInsight project, developed
34 // by Pleiades Astrophoto and its contributors (http://pixinsight.com/)."
35 //
36 // Alternatively, if that is where third-party acknowledgments normally
37 // appear, this acknowledgment must be reproduced in the product itself.
38 //
39 // THIS SOFTWARE IS PROVIDED BY PLEIADES ASTROPHOTO AND ITS CONTRIBUTORS
40 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
41 // TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
42 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL PLEIADES ASTROPHOTO OR ITS
43 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
44 // EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, BUSINESS
45 // INTERRUPTION; PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; AND LOSS OF USE,
46 // DATA OR PROFITS) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
47 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
48 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
49 // POSSIBILITY OF SUCH DAMAGE.
50 // ----------------------------------------------------------------------------
51 
52 #ifndef __PCL_Array_h
53 #define __PCL_Array_h
54 
56 
57 #include <pcl/Defs.h>
58 #include <pcl/Diagnostics.h>
59 
60 #include <pcl/Allocator.h>
61 #include <pcl/Container.h>
62 #include <pcl/Indirect.h>
63 #include <pcl/Iterator.h>
64 #include <pcl/Math.h>
65 #include <pcl/Memory.h>
66 #include <pcl/ReferenceCounter.h>
67 #include <pcl/Relational.h>
68 #include <pcl/Rotate.h>
69 #include <pcl/Search.h>
70 #include <pcl/Sort.h>
71 #include <pcl/StdAlloc.h>
72 #include <pcl/Utility.h>
73 
74 namespace pcl
75 {
76 
77 // ----------------------------------------------------------------------------
78 
83 // ----------------------------------------------------------------------------
84 
98 template <class T, class A = StandardAllocator>
99 class PCL_CLASS Array : public DirectContainer<T>
100 {
101 public:
102 
105  typedef A block_allocator;
106 
110 
113  typedef T* iterator;
114 
117  typedef const T* const_iterator;
118 
123 
128 
129  // -------------------------------------------------------------------------
130 
135  {
136  m_data = new Data;
137  }
138 
142  explicit
144  {
145  m_data = new Data;
146  m_data->Allocate( n );
147  m_data->Initialize( m_data->begin, m_data->end );
148  }
149 
153  Array( size_type n, const T& v )
154  {
155  m_data = new Data;
156  m_data->Allocate( n );
157  m_data->Initialize( m_data->begin, m_data->end, v );
158  }
159 
164  template <class FI>
165  Array( FI i, FI j )
166  {
167  m_data = new Data;
168  m_data->Allocate( size_type( pcl::Distance( i, j ) ) );
169  if ( m_data->begin != nullptr )
170  m_data->Build( m_data->begin, i, j );
171  }
172 
181  template <typename T1>
182  Array( std::initializer_list<T1> l ) : Array( l.begin(), l.end() )
183  {
184  }
185 
189  Array( const Array& x ) : m_data( x.m_data )
190  {
191  if ( m_data != nullptr )
192  m_data->Attach();
193  }
194 
198  Array( Array&& x ) : m_data( x.m_data )
199  {
200  x.m_data = nullptr;
201  }
202 
208  {
209  if ( m_data != nullptr )
210  {
211  DetachFromData();
212  m_data = nullptr;
213  }
214  }
215 
219  bool IsUnique() const
220  {
221  return m_data->IsUnique();
222  }
223 
229  bool IsAliasOf( const Array& x ) const
230  {
231  return m_data == x.m_data;
232  }
233 
242  {
243  if ( !IsUnique() )
244  {
245  Data* newData = new Data;
246  newData->Allocate( Length() );
247  newData->Build( newData->begin, m_data->begin, m_data->end );
248  DetachFromData();
249  m_data = newData;
250  }
251  }
252 
257  size_type Size() const
258  {
259  return m_data->Size();
260  }
261 
266  {
267  return m_data->Length();
268  }
269 
275  {
276  return m_data->Capacity();
277  }
278 
286  {
287  return m_data->Available();
288  }
289 
303  bool IsValid() const
304  {
305  return m_data != nullptr;
306  }
307 
311  bool IsEmpty() const
312  {
313  return m_data->IsEmpty();
314  }
315 
321  {
322  return 0;
323  }
324 
330  {
331  return Length()-1;
332  }
333 
337  const allocator& GetAllocator() const
338  {
339  return m_data->alloc;
340  }
341 
345  void SetAllocator( const allocator& a )
346  {
347  EnsureUnique();
348  m_data->alloc = a;
349  }
350 
354  iterator At( size_type i )
355  {
356  PCL_PRECONDITION( !IsEmpty() && i < Length() )
357  EnsureUnique();
358  return m_data->begin + i;
359  }
360 
364  const_iterator At( size_type i ) const
365  {
366  PCL_PRECONDITION( !IsEmpty() && i < Length() )
367  return m_data->begin + i;
368  }
369 
380  iterator MutableIterator( const_iterator i )
381  {
382  return At( i - m_data->begin );
383  }
384 
389  T& operator []( size_type i )
390  {
391  return *At( i );
392  }
393 
398  const T& operator []( size_type i ) const
399  {
400  return *At( i );
401  }
402 
407  {
408  PCL_PRECONDITION( m_data->begin != nullptr )
409  EnsureUnique();
410  return *m_data->begin;
411  }
412 
416  const T& operator *() const
417  {
418  PCL_PRECONDITION( m_data->begin != nullptr )
419  return *m_data->begin;
420  }
421 
425  iterator Begin()
426  {
427  EnsureUnique();
428  return m_data->begin;
429  }
430 
434  const_iterator Begin() const
435  {
436  return m_data->begin;
437  }
438 
442  const_iterator ConstBegin() const
443  {
444  return m_data->begin;
445  }
446 
450  iterator End()
451  {
452  EnsureUnique();
453  return m_data->end;
454  }
455 
459  const_iterator End() const
460  {
461  return m_data->end;
462  }
463 
467  const_iterator ConstEnd() const
468  {
469  return m_data->end;
470  }
471 
479  {
480  PCL_PRECONDITION( m_data->end != nullptr )
481  EnsureUnique();
482  return m_data->end - 1;
483  }
484 
492  {
493  PCL_PRECONDITION( m_data->end != nullptr )
494  return m_data->end - 1;
495  }
496 
504  {
505  PCL_PRECONDITION( m_data->end != nullptr )
506  return m_data->end - 1;
507  }
508 
517  {
518  PCL_PRECONDITION( m_data->begin != nullptr )
519  EnsureUnique();
520  return m_data->begin - 1;
521  }
522 
531  {
532  PCL_PRECONDITION( m_data->begin != nullptr )
533  return m_data->begin - 1;
534  }
535 
544  {
545  PCL_PRECONDITION( m_data->begin != nullptr )
546  return m_data->begin - 1;
547  }
548 
557  void UniquifyIterator( iterator& i )
558  {
559  PCL_PRECONDITION( i >= m_data->begin && i <= m_data->end )
560  if ( !IsUnique() )
561  {
562  distance_type d = i - m_data->begin;
563  EnsureUnique();
564  i = m_data->begin + d;
565  }
566  }
567 
577  void UniquifyIterators( iterator& i, iterator& j )
578  {
579  PCL_PRECONDITION( i >= m_data->begin && i <= m_data->end )
580  PCL_PRECONDITION( j >= m_data->begin && j <= m_data->end )
581  if ( !IsUnique() )
582  {
583  distance_type d = i - m_data->begin;
584  distance_type r = j - i;
585  EnsureUnique();
586  j = (i = m_data->begin + d) + r;
587  }
588  }
589 
590 #ifndef __PCL_NO_STL_COMPATIBLE_ITERATORS
591 
594  iterator begin()
595  {
596  return Begin();
597  }
598 
602  const_iterator begin() const
603  {
604  return Begin();
605  }
606 
610  iterator end()
611  {
612  return End();
613  }
614 
618  const_iterator end() const
619  {
620  return End();
621  }
622 #endif // !__PCL_NO_STL_COMPATIBLE_ITERATORS
623 
630  Array& operator =( const Array& x )
631  {
632  Assign( x );
633  return *this;
634  }
635 
645  void Assign( const Array& x )
646  {
647  x.m_data->Attach();
648  DetachFromData();
649  m_data = x.m_data;
650  }
651 
655  Array& operator =( Array&& x )
656  {
657  Transfer( x );
658  return *this;
659  }
660 
670  void Transfer( Array& x )
671  {
672  DetachFromData();
673  m_data = x.m_data;
674  x.m_data = nullptr;
675  }
676 
686  void Transfer( Array&& x )
687  {
688  DetachFromData();
689  m_data = x.m_data;
690  x.m_data = nullptr;
691  }
692 
697  void Assign( const T& v, size_type n = 1 )
698  {
699  if ( n > 0 )
700  {
701  if ( !IsUnique() )
702  {
703  Data* newData = new Data;
704  DetachFromData();
705  m_data = newData;
706  }
707 
708  if ( Capacity() < n )
709  {
710  m_data->Deallocate();
711  m_data->Allocate( n );
712  }
713  else
714  {
715  m_data->Destroy( m_data->begin, m_data->end );
716  m_data->end = m_data->begin + n;
717  }
718 
719  m_data->Initialize( m_data->begin, m_data->end, v );
720  }
721  else
722  Clear();
723  }
724 
731  template <class FI>
732  void Assign( FI i, FI j )
733  {
734  size_type n = size_type( pcl::Distance( i, j ) );
735  if ( n > 0 )
736  {
737  if ( !IsUnique() )
738  {
739  Data* newData = new Data;
740  DetachFromData();
741  m_data = newData;
742  }
743 
744  if ( Capacity() < n )
745  {
746  m_data->Deallocate();
747  m_data->Allocate( n );
748  }
749  else
750  {
751  m_data->Destroy( m_data->begin, m_data->end );
752  m_data->end = m_data->begin + n;
753  }
754 
755  m_data->Build( m_data->begin, i, j );
756  }
757  else
758  Clear();
759  }
760 
770  void Import( iterator i, iterator j )
771  {
772  if ( i >= m_data->available || j <= m_data->begin )
773  {
774  Clear();
775  size_type n = size_type( pcl::Distance( i, j ) );
776  if ( n > 0 )
777  {
778  EnsureUnique();
779  m_data->begin = i;
780  m_data->end = m_data->available = j;
781  }
782  }
783  }
784 
797  iterator Release()
798  {
799  EnsureUnique();
800  iterator b = m_data->begin;
801  m_data->begin = m_data->end = m_data->available = nullptr;
802  return b;
803  }
804 
815  iterator Grow( iterator i, size_type n = 1 )
816  {
817  i = pcl::Range( i, m_data->begin, m_data->end );
818  if ( n > 0 )
819  {
820  UniquifyIterator( i );
821  m_data->Initialize( i = m_data->UninitializedGrow( i, n ), n );
822  }
823  return i;
824  }
825 
835  iterator Expand( size_type n = 1 )
836  {
837  return Grow( m_data->end, n );
838  }
839 
849  void Shrink( size_type n = 1 )
850  {
851  if ( n < m_data->Length() )
852  Truncate( m_data->end - n );
853  else
854  Clear();
855  }
856 
869  void Resize( size_type n )
870  {
871  size_type l = m_data->Length();
872  if ( n > l )
873  Expand( n - l );
874  else
875  Shrink( l - n );
876  }
877 
889  iterator Insert( iterator i, const Array& x )
890  {
891  if ( &x != this )
892  return Insert( i, x.Begin(), x.End() );
893  Array t( *this );
894  t.EnsureUnique();
895  return Insert( i, t.m_data->begin, t.m_data->end );
896  }
897 
908  iterator Insert( iterator i, const T& v, size_type n = 1 )
909  {
910  i = pcl::Range( i, m_data->begin, m_data->end );
911  if ( n > 0 )
912  {
913  UniquifyIterator( i );
914  m_data->Initialize( i = m_data->UninitializedGrow( i, n ), n, v );
915  }
916  return i;
917  }
918 
931  template <class FI>
932  iterator Insert( iterator i, FI p, FI q )
933  {
934  i = pcl::Range( i, m_data->begin, m_data->end );
935  size_type n = size_type( pcl::Distance( p, q ) );
936  if ( n > 0 )
937  {
938  UniquifyIterator( i );
939  m_data->Build( i = m_data->UninitializedGrow( i, n ), p, q );
940  }
941  return i;
942  }
943 
947  void Append( const Array& x )
948  {
949  Insert( m_data->end, x );
950  }
951 
956  void Append( const T& v, size_type n = 1 )
957  {
958  Insert( m_data->end, v, n );
959  }
960 
967  template <class FI>
968  void Append( FI p, FI q )
969  {
970  Insert( m_data->end, p, q );
971  }
972 
977  void Prepend( const Array& x )
978  {
979  Insert( m_data->begin, x );
980  }
981 
986  void Prepend( const T& v, size_type n = 1 )
987  {
988  Insert( m_data->begin, v, n );
989  }
990 
997  template <class FI>
998  void Prepend( FI p, FI q )
999  {
1000  Insert( m_data->begin, p, q );
1001  }
1002 
1006  void Add( const Array& x )
1007  {
1008  Append( x );
1009  }
1010 
1014  void Add( const T& v, size_type n = 1 )
1015  {
1016  Append( v, n );
1017  }
1018 
1022  template <class FI>
1023  void Add( FI p, FI q )
1024  {
1025  Append( p, q );
1026  }
1027 
1037  void Remove( iterator i, size_type n = 1 )
1038  {
1039  Remove( i, i+n );
1040  }
1041 
1051  void Remove( iterator i, iterator j )
1052  {
1053  if ( i < m_data->end )
1054  if ( i < j )
1055  {
1056  i = pcl::Max( m_data->begin, i );
1057  j = pcl::Min( j, m_data->end );
1058  if ( i > m_data->begin || j < m_data->end )
1059  {
1060  UniquifyIterators( i, j );
1061  m_data->Destroy( j = pcl::Copy( i, j, m_data->end ), m_data->end );
1062  m_data->end = j;
1063  }
1064  else
1065  Clear();
1066  }
1067  }
1068 
1079  void Truncate( iterator i )
1080  {
1081  Remove( i, m_data->end );
1082  }
1083 
1088  void Remove( const T& v )
1089  {
1090  Array a;
1091  for ( iterator i = m_data->begin, j = i; ; ++j )
1092  {
1093  if ( j == m_data->end )
1094  {
1095  if ( i != m_data->begin )
1096  {
1097  a.Add( i, j );
1098  Transfer( a );
1099  }
1100  break;
1101  }
1102 
1103  if ( *j == v )
1104  {
1105  a.Add( i, j );
1106  i = j;
1107  ++i;
1108  }
1109  }
1110  }
1111 
1116  template <class BP>
1117  void Remove( const T& v, BP p )
1118  {
1119  Array a;
1120  for ( iterator i = m_data->begin, j = i; ; ++j )
1121  {
1122  if ( j == m_data->end )
1123  {
1124  if ( i != m_data->begin )
1125  {
1126  a.Add( i, j );
1127  Transfer( a );
1128  }
1129  break;
1130  }
1131 
1132  if ( p( *j, v ) )
1133  {
1134  a.Add( i, j );
1135  i = j;
1136  ++i;
1137  }
1138  }
1139  }
1140 
1152  void Clear()
1153  {
1154  if ( !IsEmpty() )
1155  if ( IsUnique() )
1156  m_data->Deallocate();
1157  else
1158  {
1159  Data* newData = new Data;
1160  DetachFromData();
1161  m_data = newData;
1162  }
1163  }
1164 
1178  iterator Replace( iterator i, iterator j, const Array& x )
1179  {
1180  if ( &x != this )
1181  return Replace( i, j, x.Begin(), x.End() );
1182  Array t( *this );
1183  t.EnsureUnique();
1184  return Replace( i, j, t.ConstBegin(), t.ConstEnd() );
1185  }
1186 
1200  iterator Replace( iterator i, iterator j, const T& v, size_type n = 1 )
1201  {
1202  i = pcl::Range( i, m_data->begin, m_data->end );
1203  j = pcl::Range( j, m_data->begin, m_data->end );
1204  if ( i < j )
1205  if ( i < m_data->end )
1206  {
1207  UniquifyIterators( i, j );
1208  size_type d = size_type( j - i );
1209  if ( d < n )
1210  {
1211  m_data->Destroy( i, j );
1212  m_data->Initialize( i = m_data->UninitializedGrow( i, n-d ), n, v );
1213  }
1214  else
1215  {
1216  iterator k = i + n;
1217  pcl::Fill( i, k, v );
1218  Remove( k, j );
1219  if ( m_data->begin == nullptr )
1220  i = nullptr;
1221  }
1222  }
1223  return i;
1224  }
1225 
1242  template <class FI>
1243  iterator Replace( iterator i, iterator j, FI p, FI q )
1244  {
1245  i = pcl::Range( i, m_data->begin, m_data->end );
1246  j = pcl::Range( j, m_data->begin, m_data->end );
1247  if ( i < j )
1248  if ( i < m_data->end )
1249  {
1250  UniquifyIterators( i, j );
1251  size_type d = size_type( j - i );
1252  size_type n = size_type( pcl::Distance( p, q ) );
1253  if ( d < n )
1254  {
1255  m_data->Destroy( i, j );
1256  m_data->Build( i = m_data->UninitializedGrow( i, n-d ), p, q );
1257  }
1258  else
1259  {
1260  Remove( pcl::Move( i, p, q ), j );
1261  if ( m_data->begin == nullptr )
1262  i = nullptr;
1263  }
1264  }
1265  return i;
1266  }
1267 
1274  void Reserve( size_type n )
1275  {
1276  if ( n > 0 )
1277  if ( IsUnique() )
1278  {
1279  if ( Capacity() < n )
1280  {
1281  iterator b = m_data->alloc.Allocate( n );
1282  iterator e = m_data->Build( b, m_data->begin, m_data->end );
1283  m_data->Deallocate();
1284  m_data->begin = b;
1285  m_data->end = e;
1286  m_data->available = m_data->begin + n;
1287  }
1288  }
1289  else
1290  {
1291  Data* newData = new Data;
1292  newData->begin = newData->alloc.Allocate( n = pcl::Max( Length(), n ) );
1293  newData->end = newData->Build( newData->begin, m_data->begin, m_data->end );
1294  newData->available = newData->begin + n;
1295  DetachFromData();
1296  m_data = newData;
1297  }
1298  }
1299 
1312  void Squeeze()
1313  {
1314  if ( IsUnique() )
1315  {
1316  if ( Available() > 0 )
1317  {
1318  iterator b = m_data->alloc.Allocate( Length() );
1319  iterator e = m_data->Build( b, m_data->begin, m_data->end );
1320  m_data->Deallocate();
1321  m_data->begin = b;
1322  m_data->end = m_data->available = e;
1323  }
1324  }
1325  else
1326  {
1327  Data* newData = new Data;
1328  if ( !IsEmpty() )
1329  {
1330  newData->begin = newData->alloc.Allocate( Length() );
1331  newData->available = newData->end = newData->Build( newData->begin, m_data->begin, m_data->end );
1332  }
1333  DetachFromData();
1334  m_data = newData;
1335  }
1336  }
1337 
1341  void Fill( const T& v )
1342  {
1343  EnsureUnique();
1344  pcl::Fill( m_data->begin, m_data->end, v );
1345  }
1346 
1359  void SecureFill( const T& v )
1360  {
1361  pcl::Fill( m_data->begin, m_data->end, v );
1362  }
1363 
1368  template <class F>
1369  void Apply( F f )
1370  {
1371  EnsureUnique();
1372  pcl::Apply( m_data->begin, m_data->end, f );
1373  }
1374 
1379  template <class F>
1380  void Apply( F f ) const
1381  {
1382  pcl::Apply( m_data->begin, m_data->end, f );
1383  }
1384 
1390  template <class F>
1391  iterator FirstThat( F f ) const
1392  {
1393  return const_cast<iterator>( pcl::FirstThat( m_data->begin, m_data->end, f ) );
1394  }
1395 
1401  template <class F>
1402  iterator LastThat( F f ) const
1403  {
1404  return const_cast<iterator>( pcl::LastThat( m_data->begin, m_data->end, f ) );
1405  }
1406 
1409  size_type Count( const T& v ) const
1410  {
1411  return pcl::Count( m_data->begin, m_data->end, v );
1412  }
1413 
1416  template <class BP>
1417  size_type Count( const T& v, BP p ) const
1418  {
1419  return pcl::Count( m_data->begin, m_data->end, v, p );
1420  }
1421 
1424  template <class UP>
1425  size_type CountIf( UP p ) const
1426  {
1427  return pcl::CountIf( m_data->begin, m_data->end, p );
1428  }
1429 
1432  iterator MinItem() const
1433  {
1434  return const_cast<iterator>( pcl::MinItem( m_data->begin, m_data->end ) );
1435  }
1436 
1439  template <class BP>
1440  iterator MinItem( BP p ) const
1441  {
1442  return const_cast<iterator>( pcl::MinItem( m_data->begin, m_data->end, p ) );
1443  }
1444 
1447  iterator MaxItem() const
1448  {
1449  return const_cast<iterator>( pcl::MaxItem( m_data->begin, m_data->end ) );
1450  }
1451 
1454  template <class BP>
1455  iterator MaxItem( BP p ) const
1456  {
1457  return const_cast<iterator>( pcl::MaxItem( m_data->begin, m_data->end, p ) );
1458  }
1459 
1462  void Reverse()
1463  {
1464  EnsureUnique();
1465  pcl::Reverse( m_data->begin, m_data->end );
1466  }
1467 
1471  {
1472  if ( Length() > 1 && n != 0 )
1473  {
1474  EnsureUnique();
1475  if ( (n %= Length()) < 0 )
1476  n += Length();
1477  pcl::Rotate( m_data->begin, m_data->begin+n, m_data->end );
1478  }
1479  }
1480 
1483  void ShiftLeft( const T& v, size_type n = 1 )
1484  {
1485  if ( !IsEmpty() && n > 0 )
1486  {
1487  EnsureUnique();
1488  if ( n >= Length() )
1489  pcl::Fill( m_data->begin, m_data->end, v );
1490  else
1491  pcl::ShiftLeft( m_data->begin, m_data->begin+n, m_data->end, v );
1492  }
1493  }
1494 
1497  void ShiftRight( const T& v, size_type n = 1 )
1498  {
1499  if ( !IsEmpty() && n > 0 )
1500  {
1501  EnsureUnique();
1502  if ( n >= Length() )
1503  pcl::Fill( m_data->begin, m_data->end, v );
1504  else
1505  pcl::ShiftRight( m_data->begin, m_data->end-n, m_data->end, v );
1506  }
1507  }
1508 
1511  iterator Search( const T& v ) const
1512  {
1513  return const_cast<iterator>( pcl::LinearSearch( m_data->begin, m_data->end, v ) );
1514  }
1515 
1518  template <class BP>
1519  iterator Search( const T& v, BP p ) const
1520  {
1521  return const_cast<iterator>( pcl::LinearSearch( m_data->begin, m_data->end, v, p ) );
1522  }
1523 
1526  iterator SearchLast( const T& v ) const
1527  {
1528  return const_cast<iterator>( pcl::LinearSearchLast( m_data->begin, m_data->end, v ) );
1529  }
1530 
1533  template <class BP>
1534  iterator SearchLast( const T& v, BP p ) const
1535  {
1536  return const_cast<iterator>( pcl::LinearSearchLast( m_data->begin, m_data->end, v, p ) );
1537  }
1538 
1541  template <class FI>
1542  iterator SearchSubset( FI i, FI j ) const
1543  {
1544  return const_cast<iterator>( pcl::Search( m_data->begin, m_data->end, i, j ) );
1545  }
1546 
1549  template <class FI, class BP>
1550  iterator SearchSubset( FI i, FI j, BP p ) const
1551  {
1552  return const_cast<iterator>( pcl::Search( m_data->begin, m_data->end, i, j, p ) );
1553  }
1554 
1557  template <class C>
1558  iterator SearchSubset( const C& x ) const
1559  {
1560  PCL_ASSERT_DIRECT_CONTAINER( C, T );
1561  return const_cast<iterator>( pcl::Search( m_data->begin, m_data->end, x.Begin(), x.End() ) );
1562  }
1563 
1566  template <class C, class BP>
1567  iterator SearchSubset( const C& x, BP p ) const
1568  {
1569  PCL_ASSERT_DIRECT_CONTAINER( C, T );
1570  return const_cast<iterator>( pcl::Search( m_data->begin, m_data->end, x.Begin(), x.End(), p ) );
1571  }
1572 
1575  template <class BI>
1576  iterator SearchLastSubset( BI i, BI j ) const
1577  {
1578  return const_cast<iterator>( pcl::SearchLast( m_data->begin, m_data->end, i, j ) );
1579  }
1580 
1583  template <class BI, class BP>
1584  iterator SearchLastSubset( BI i, BI j, BP p ) const
1585  {
1586  return const_cast<iterator>( pcl::SearchLast( m_data->begin, m_data->end, i, j, p ) );
1587  }
1588 
1591  template <class C>
1592  iterator SearchLastSubset( const C& x ) const
1593  {
1594  PCL_ASSERT_DIRECT_CONTAINER( C, T );
1595  return const_cast<iterator>( pcl::SearchLast( m_data->begin, m_data->end, x.Begin(), x.End() ) );
1596  }
1597 
1600  template <class C, class BP>
1601  iterator SearchLastSubset( const C& x, BP p ) const
1602  {
1603  PCL_ASSERT_DIRECT_CONTAINER( C, T );
1604  return const_cast<iterator>( pcl::SearchLast( m_data->begin, m_data->end, x.Begin(), x.End(), p ) );
1605  }
1606 
1609  bool Contains( const T& v ) const
1610  {
1611  return Search( v ) != m_data->end;
1612  }
1613 
1616  template <class BP>
1617  bool Contains( const T& v, BP p ) const
1618  {
1619  return Search( v, p ) != m_data->end;
1620  }
1621 
1624  template <class FI>
1625  iterator ContainsSubset( FI i, FI j ) const
1626  {
1627  return SearchSubset( i, j ) != m_data->end;
1628  }
1629 
1632  template <class FI, class BP>
1633  iterator ContainsSubset( FI i, FI j, BP p ) const
1634  {
1635  return SearchSubset( i, j, p ) != m_data->end;
1636  }
1637 
1640  template <class C>
1641  iterator ContainsSubset( const C& c ) const
1642  {
1643  return SearchSubset( c ) != m_data->end;
1644  }
1645 
1648  template <class C, class BP>
1649  iterator ContainsSubset( const C& c, BP p ) const
1650  {
1651  return SearchSubset( c, p ) != m_data->end;
1652  }
1653 
1656  void Sort()
1657  {
1658  EnsureUnique();
1659  pcl::QuickSort( m_data->begin, m_data->end );
1660  }
1661 
1664  template <class BP>
1665  void Sort( BP p )
1666  {
1667  EnsureUnique();
1668  pcl::QuickSort( m_data->begin, m_data->end, p );
1669  }
1670 
1674  friend void Swap( Array& x1, Array& x2 )
1675  {
1676  pcl::Swap( x1.m_data, x2.m_data );
1677  }
1678 
1695  template <class S, typename SP>
1696  S& ToSeparated( S& s, SP separator ) const
1697  {
1698  const_iterator i = m_data->begin;
1699  if ( i < m_data->end )
1700  {
1701  s.Append( S( *i ) );
1702  if ( ++i < m_data->end )
1703  do
1704  {
1705  s.Append( separator );
1706  s.Append( S( *i ) );
1707  }
1708  while ( ++i < m_data->end );
1709  }
1710  return s;
1711  }
1712 
1735  template <class S, typename SP, class AF>
1736  S& ToSeparated( S& s, SP separator, AF append ) const
1737  {
1738  const_iterator i = m_data->begin;
1739  if ( i < m_data->end )
1740  {
1741  append( s, S( *i ) );
1742  if ( ++i < m_data->end )
1743  {
1744  S p( separator );
1745  do
1746  {
1747  append( s, p );
1748  append( s, S( *i ) );
1749  }
1750  while ( ++i < m_data->end );
1751  }
1752  }
1753  return s;
1754  }
1755 
1764  template <class S>
1765  S& ToCommaSeparated( S& s ) const
1766  {
1767  return ToSeparated( s, ',' );
1768  }
1769 
1778  template <class S>
1779  S& ToSpaceSeparated( S& s ) const
1780  {
1781  return ToSeparated( s, ' ' );
1782  }
1783 
1792  template <class S>
1793  S& ToTabSeparated( S& s ) const
1794  {
1795  return ToSeparated( s, '\t' );
1796  }
1797 
1806  uint64 Hash64( uint64 seed = 0 ) const
1807  {
1808  return pcl::Hash64( m_data->begin, m_data->Size(), seed );
1809  }
1810 
1819  uint32 Hash32( uint32 seed = 0 ) const
1820  {
1821  return pcl::Hash32( m_data->begin, m_data->Size(), seed );
1822  }
1823 
1828  uint64 Hash( uint64 seed = 0 ) const
1829  {
1830  return Hash64( seed );
1831  }
1832 
1833  // -------------------------------------------------------------------------
1834 
1835 private:
1836 
1842  struct Data : public ReferenceCounter
1843  {
1844  iterator begin = nullptr;
1845  iterator end = nullptr;
1846  iterator available = nullptr;
1847  allocator alloc;
1848 
1852  Data() = default;
1853 
1857  ~Data()
1858  {
1859  Deallocate();
1860  }
1861 
1865  size_type Size() const
1866  {
1867  return Length()*sizeof( T );
1868  }
1869 
1873  size_type Length() const
1874  {
1875  return end - begin;
1876  }
1877 
1881  size_type Capacity() const
1882  {
1883  return available - begin;
1884  }
1885 
1889  size_type Available() const
1890  {
1891  return available - end;
1892  }
1893 
1897  bool IsEmpty() const
1898  {
1899  return begin == end;
1900  }
1901 
1906  void Allocate( size_type n )
1907  {
1908  if ( n > 0 )
1909  {
1910  size_type m = alloc.PagedLength( n );
1911  begin = alloc.Allocate( m );
1912  end = begin + n;
1913  available = begin + m;
1914  }
1915  }
1916 
1920  void Deallocate()
1921  {
1922  PCL_CHECK( (begin == nullptr) ? end == nullptr : begin < end )
1923  if ( begin != nullptr )
1924  {
1925  Destroy( begin, end );
1926  alloc.Deallocate( begin );
1927  begin = end = available = nullptr;
1928  }
1929  }
1930 
1934  void Initialize( iterator i, iterator j )
1935  {
1936  for ( ; i < j; ++i )
1937  pcl::Construct( i, alloc );
1938  }
1939 
1944  void Initialize( iterator i, size_type n )
1945  {
1946  for ( ; n > 0; ++i, --n )
1947  pcl::Construct( i, alloc );
1948  }
1949 
1954  void Initialize( iterator i, iterator j, const T& v )
1955  {
1956  for ( ; i < j; ++i )
1957  pcl::Construct( i, v, alloc );
1958  }
1959 
1964  void Initialize( iterator i, size_type n, const T& v )
1965  {
1966  for ( ; n > 0; ++i, --n )
1967  pcl::Construct( i, v, alloc );
1968  }
1969 
1975  template <class FI>
1976  iterator Build( iterator i, FI p, FI q )
1977  {
1978  for ( ; p != q; ++i, ++p )
1979  pcl::Construct( i, *p, alloc );
1980  return i;
1981  }
1982 
1988  iterator UninitializedGrow( iterator i, size_type n )
1989  {
1990  if ( n > 0 )
1991  if ( Available() >= n )
1992  {
1993  if ( i < end )
1994  {
1995  iterator j1 = end;
1996  iterator j2 = end + n;
1997 
1998  for ( ;; )
1999  {
2000  pcl::Construct( --j2, *--j1, alloc );
2001 
2002  if ( j1 == i )
2003  {
2004  j2 = end;
2005  break;
2006  }
2007  else if ( j2 == end )
2008  {
2009  do
2010  *--j2 = *--j1;
2011  while ( j1 != i );
2012  break;
2013  }
2014  }
2015 
2016  Destroy( i, j2 );
2017  }
2018  end += n;
2019  }
2020  else
2021  {
2022  size_type m = alloc.PagedLength( Length()+n );
2023  iterator b = alloc.Allocate( m );
2024  iterator r = Build( b, begin, i );
2025  iterator e = Build( r+n, i, end );
2026 
2027  Deallocate();
2028  begin = b;
2029  end = e;
2030  available = b + m;
2031  i = r;
2032  }
2033 
2034  return i;
2035  }
2036 
2040  static void Destroy( iterator i, iterator j )
2041  {
2042  pcl::Destroy( i, j );
2043  }
2044  };
2045 
2050  Data* m_data = nullptr;
2051 
2056  void DetachFromData()
2057  {
2058  if ( !m_data->Detach() )
2059  delete m_data;
2060  }
2061 };
2062 
2063 // ----------------------------------------------------------------------------
2064 
2074 template <class T, class A> inline
2075 bool operator ==( const Array<T,A>& x1, const Array<T,A>& x2 )
2076 {
2077  return x1.Length() == x2.Length() && pcl::Equal( x1.Begin(), x2.Begin(), x2.End() );
2078 }
2079 
2085 template <class T, class A> inline
2086 bool operator <( const Array<T,A>& x1, const Array<T,A>& x2 )
2087 {
2088  return pcl::Compare( x1.Begin(), x1.End(), x2.Begin(), x2.End() ) < 0;
2089 }
2090 
2102 template <class T, class A, class V> inline
2103 Array<T,A>& operator <<( Array<T,A>& x, const V& v )
2104 {
2105  x.Append( T( v ) );
2106  return x;
2107 }
2108 
2116 template <class T, class A, class V> inline
2117 Array<T,A>& operator <<( Array<T,A>&& x, const V& v )
2118 {
2119  x.Append( T( v ) );
2120  return x;
2121 }
2122 
2128 template <class T, class A> inline
2129 Array<T,A>& operator <<( Array<T,A>& x1, const Array<T,A>& x2 )
2130 {
2131  x1.Append( x2 );
2132  return x1;
2133 }
2134 
2140 template <class T, class A> inline
2141 Array<T,A>& operator <<( Array<T,A>&& x1, const Array<T,A>& x2 )
2142 {
2143  x1.Append( x2 );
2144  return x1;
2145 }
2146 
2147 // ----------------------------------------------------------------------------
2148 
2149 } // pcl
2150 
2151 #endif // __PCL_Array_h
2152 
2153 // ----------------------------------------------------------------------------
2154 // EOF pcl/Array.h - Released 2019-04-30T16:30:41Z
void Apply(F f)
Definition: Array.h:1369
bool IsEmpty() const
Definition: Array.h:311
distance_type Distance(FI i, FI j)
Definition: Iterator.h:161
iterator SearchLastSubset(const C &x, BP p) const
Definition: Array.h:1601
size_type UpperBound() const
Definition: Array.h:329
iterator SearchLastSubset(BI i, BI j) const
Definition: Array.h:1576
uint64 Hash64(const void *data, size_type size, uint64 seed=0)
Definition: Math.h:3445
uint64 Hash64(uint64 seed=0) const
Definition: Array.h:1806
void Remove(const T &v, BP p)
Definition: Array.h:1117
bool IsValid() const
Definition: Array.h:303
const_reverse_iterator ReverseBegin() const
Definition: Array.h:491
Complex< T1 > operator*(const Complex< T1 > &c1, const Complex< T2 > &c2)
Definition: Complex.h:539
iterator ContainsSubset(FI i, FI j, BP p) const
Definition: Array.h:1633
void Rotate(distance_type n)
Definition: Array.h:1470
void UniquifyIterators(iterator &i, iterator &j)
Definition: Array.h:577
void Clear()
Definition: Array.h:1152
ReverseRandomAccessIterator< const_iterator, const T > const_reverse_iterator
Definition: Array.h:127
iterator SearchSubset(FI i, FI j, BP p) const
Definition: Array.h:1550
void Squeeze()
Definition: Array.h:1312
BI LinearSearchLast(BI i, BI j, const T &v)
Definition: Search.h:129
uint64 Hash(uint64 seed=0) const
Definition: Array.h:1828
void Add(const T &v, size_type n=1)
Definition: Array.h:1014
void Deallocate(T *p)
Definition: Allocator.h:176
iterator MaxItem() const
Definition: Array.h:1447
void Swap(GenericPoint< T > &p1, GenericPoint< T > &p2)
Definition: Point.h:1290
size_type Count(FI i, FI j, const T &v)
Definition: Utility.h:387
iterator SearchSubset(FI i, FI j) const
Definition: Array.h:1542
iterator ContainsSubset(FI i, FI j) const
Definition: Array.h:1625
iterator Search(const T &v, BP p) const
Definition: Array.h:1519
size_type Count(const T &v) const
Definition: Array.h:1409
int Compare(FI1 i1, FI1 j1, FI2 i2, FI2 j2)
Definition: Utility.h:642
PCL root namespace.
Definition: AbstractImage.h:76
bool Contains(const T &v, BP p) const
Definition: Array.h:1617
void Sort()
Definition: Array.h:1656
iterator Begin()
Definition: Array.h:425
iterator begin()
Definition: Array.h:594
BI LastThat(BI i, BI j, UP p)
Definition: Utility.h:353
void Append(const T &v, size_type n=1)
Definition: Array.h:956
void Append(const Array &x)
Definition: Array.h:947
FI LinearSearch(FI i, FI j, const T &v)
Definition: Search.h:91
const_iterator ConstBegin() const
Definition: Array.h:442
bool Contains(const T &v) const
Definition: Array.h:1609
iterator Grow(iterator i, size_type n=1)
Definition: Array.h:815
FI MaxItem(FI i, FI j)
Definition: Utility.h:482
void ShiftRight(const T &v, size_type n=1)
Definition: Array.h:1497
friend void Swap(Array &x1, Array &x2)
Definition: Array.h:1674
bool IsUnique() const
Definition: Array.h:219
void Import(iterator i, iterator j)
Definition: Array.h:770
iterator Insert(iterator i, const Array &x)
Definition: Array.h:889
void Construct(T *p, A &a)
Definition: Allocator.h:246
void ShiftLeft(const T &v, size_type n=1)
Definition: Array.h:1483
Array(const Array &x)
Definition: Array.h:189
bool Equal(FI1 i1, FI2 i2, FI2 j2)
Definition: Utility.h:595
Array(size_type n)
Definition: Array.h:143
void Apply(F f) const
Definition: Array.h:1380
void Sort(BP p)
Definition: Array.h:1665
iterator ContainsSubset(const C &c, BP p) const
Definition: Array.h:1649
Generic vector of arbitrary length.
Definition: Vector.h:105
iterator begin()
Definition: Vector.h:1766
BI1 SearchLast(BI1 i1, BI1 j1, FI2 i2, FI2 j2)
Definition: Search.h:449
constexpr const T & Range(const T &x, const T &a, const T &b)
Definition: Utility.h:190
Array(Array &&x)
Definition: Array.h:198
size_t size_type
Definition: Defs.h:545
Provides memory allocation for PCL containers.
Definition: Allocator.h:131
void Assign(const T &v, size_type n=1)
Definition: Array.h:697
reverse_iterator ReverseEnd()
Definition: Array.h:516
const_iterator begin() const
Definition: Array.h:602
ReverseRandomAccessIterator< iterator, T > reverse_iterator
Definition: Array.h:122
iterator MaxItem(BP p) const
Definition: Array.h:1455
void Remove(iterator i, size_type n=1)
Definition: Array.h:1037
iterator MinItem(BP p) const
Definition: Array.h:1440
void Destroy(T *p)
Definition: Allocator.h:276
void Apply(FI i, FI j, F f)
Definition: Utility.h:252
iterator MutableIterator(const_iterator i)
Definition: Array.h:380
void Resize(size_type n)
Definition: Array.h:869
T * Allocate(size_type n, size_type extra=0)
Definition: Allocator.h:162
const_iterator End() const
Definition: Array.h:459
unsigned long long uint64
Definition: Defs.h:618
iterator Replace(iterator i, iterator j, const Array &x)
Definition: Array.h:1178
void Append(FI p, FI q)
Definition: Array.h:968
constexpr const T & Max(const T &a, const T &b)
Definition: Utility.h:119
const_reverse_iterator ReverseEnd() const
Definition: Array.h:530
void Truncate(iterator i)
Definition: Array.h:1079
void SetAllocator(const allocator &a)
Definition: Array.h:345
void Prepend(const T &v, size_type n=1)
Definition: Array.h:986
void Remove(const T &v)
Definition: Array.h:1088
constexpr const T & Min(const T &a, const T &b)
Definition: Utility.h:90
void SecureFill(const T &v)
Definition: Array.h:1359
iterator end()
Definition: Array.h:610
void Rotate(T &x, T &y, T1 sa, T1 ca, T2 xc, T2 yc)
Definition: Math.h:1823
reverse_iterator ReverseBegin()
Definition: Array.h:478
void Transfer(Array &x)
Definition: Array.h:670
void Transfer(Array &&x)
Definition: Array.h:686
void Assign(FI i, FI j)
Definition: Array.h:732
size_type Available() const
Definition: Array.h:285
size_type CountIf(FI i, FI j, UP p)
Definition: Utility.h:426
size_type Count(const T &v, BP p) const
Definition: Array.h:1417
void Reserve(size_type n)
Definition: Array.h:1274
iterator Search(const T &v) const
Definition: Array.h:1511
void Prepend(FI p, FI q)
Definition: Array.h:998
size_type PagedLength(size_type n) const
Definition: Allocator.h:205
iterator Replace(iterator i, iterator j, const T &v, size_type n=1)
Definition: Array.h:1200
void UniquifyIterator(iterator &i)
Definition: Array.h:557
uint32 Hash32(const void *data, size_type size, uint32 seed=0)
Definition: Math.h:3593
const_reverse_iterator ConstReverseBegin() const
Definition: Array.h:503
size_type LowerBound() const
Definition: Array.h:320
void Add(const Array &x)
Definition: Array.h:1006
size_type Capacity() const
Definition: Array.h:274
void EnsureUnique()
Definition: Array.h:241
Generic dynamic array.
Definition: Array.h:99
size_type CountIf(UP p) const
Definition: Array.h:1425
void Remove(iterator i, iterator j)
Definition: Array.h:1051
Array(FI i, FI j)
Definition: Array.h:165
iterator Replace(iterator i, iterator j, FI p, FI q)
Definition: Array.h:1243
Array(size_type n, const T &v)
Definition: Array.h:153
size_type Length() const
Definition: Array.h:265
void QuickSort(RI i, RI j)
Definition: Sort.h:250
const_reverse_iterator ConstReverseEnd() const
Definition: Array.h:543
void Fill(const T &v)
Definition: Array.h:1341
void Reverse()
Definition: Array.h:1462
Root base class of all PCL containers of objects.
Definition: Container.h:77
iterator SearchLast(const T &v, BP p) const
Definition: Array.h:1534
iterator LastThat(F f) const
Definition: Array.h:1402
void Shrink(size_type n=1)
Definition: Array.h:849
Array(std::initializer_list< T1 > l)
Definition: Array.h:182
pcl::Allocator< T, A > allocator
Definition: Array.h:109
Reverse random access iterator.
Definition: Iterator.h:414
iterator Insert(iterator i, const T &v, size_type n=1)
Definition: Array.h:908
const_iterator At(size_type i) const
Definition: Array.h:364
iterator End()
Definition: Array.h:450
A block allocator class that uses the standard new and delete operators.
Definition: StdAlloc.h:81
iterator Release()
Definition: Array.h:797
FI MinItem(FI i, FI j)
Definition: Utility.h:444
iterator SearchLastSubset(BI i, BI j, BP p) const
Definition: Array.h:1584
Array()
Definition: Array.h:134
FI1 Search(FI1 i1, FI1 j1, FI2 i2, FI2 j2)
Definition: Search.h:397
bool operator==(const Array< T, A > &x1, const Array< T, A > &x2)
Definition: Array.h:2075
uint32 Hash32(uint32 seed=0) const
Definition: Array.h:1819
iterator ContainsSubset(const C &c) const
Definition: Array.h:1641
iterator SearchSubset(const C &x, BP p) const
Definition: Array.h:1567
bool IsAliasOf(const Array &x) const
Definition: Array.h:229
iterator SearchLastSubset(const C &x) const
Definition: Array.h:1592
void Add(FI p, FI q)
Definition: Array.h:1023
iterator FirstThat(F f) const
Definition: Array.h:1391
ptrdiff_t distance_type
Definition: Defs.h:551
iterator MinItem() const
Definition: Array.h:1432
const_iterator ConstEnd() const
Definition: Array.h:467
iterator Insert(iterator i, FI p, FI q)
Definition: Array.h:932
const allocator & GetAllocator() const
Definition: Array.h:337
FI FirstThat(FI i, FI j, UP p)
Definition: Utility.h:319
const_iterator ConstBegin() const
Definition: Vector.h:1638
iterator SearchLast(const T &v) const
Definition: Array.h:1526
void Prepend(const Array &x)
Definition: Array.h:977
iterator SearchSubset(const C &x) const
Definition: Array.h:1558
~Array()
Definition: Array.h:207
unsigned int uint32
Definition: Defs.h:602
iterator At(size_type i)
Definition: Array.h:354
iterator Expand(size_type n=1)
Definition: Array.h:835
size_type Size() const
Definition: Array.h:257
void Assign(const Array &x)
Definition: Array.h:645
Thread-safe reference counter for copy-on-write data structures.
const_iterator end() const
Definition: Array.h:618
const_iterator Begin() const
Definition: Array.h:434