PCL
ReferenceSortedArray.h
Go to the documentation of this file.
1 // ____ ______ __
2 // / __ \ / ____// /
3 // / /_/ // / / /
4 // / ____// /___ / /___ PixInsight Class Library
5 // /_/ \____//_____/ PCL 2.7.0
6 // ----------------------------------------------------------------------------
7 // pcl/ReferenceSortedArray.h - Released 2024-06-18T15:48:54Z
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-2024 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 (https://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_ReferenceSortedArray_h
53 #define __PCL_ReferenceSortedArray_h
54 
56 
57 #include <pcl/Diagnostics.h>
58 
59 #include <pcl/Allocator.h>
60 #include <pcl/Container.h>
62 #include <pcl/Iterator.h>
63 #include <pcl/ReferenceArray.h>
64 #include <pcl/SortedArray.h>
65 #include <pcl/StandardAllocator.h>
66 
67 namespace pcl
68 {
69 
70 // ----------------------------------------------------------------------------
71 
99 template <typename T, class A = StandardAllocator>
100 class PCL_CLASS ReferenceSortedArray : public DirectContainer<T>
101 {
102 public:
103 
107 
111 
115 
119 
123 
127 
131 
135 
139 
140  // -------------------------------------------------------------------------
141 
145  ReferenceSortedArray() = default;
146 
154  {
155  PCL_PRECONDITION( p != nullptr )
156  if ( p != nullptr )
157  m_array = array_implementation( n, p );
158  }
159 
169  template <class FI>
170  ReferenceSortedArray( FI i, FI j )
171  : m_array( i, j )
172  {
173  Sort();
174  }
175 
180 
185 
194  {
195  }
196 
201  bool IsUnique() const
202  {
203  return m_array.IsUnique();
204  }
205 
212  bool IsAliasOf( const ReferenceSortedArray& x ) const
213  {
214  return m_array.IsAliasOf( x.m_array );
215  }
216 
226  {
227  m_array.EnsureUnique();
228  }
229 
234  size_type Size() const
235  {
236  return m_array.Size();
237  }
238 
243  {
244  return m_array.Length();
245  }
246 
253  {
254  return m_array.Capacity();
255  }
256 
265  {
266  return m_array.Available();
267  }
268 
284  bool IsValid() const
285  {
286  return m_array.IsValid();
287  }
288 
292  bool IsEmpty() const
293  {
294  return m_array.IsEmpty();
295  }
296 
302  {
303  return m_array.LowerBound();
304  }
305 
311  {
312  return m_array.UpperBound();
313  }
314 
318  const allocator& Allocator() const
319  {
320  return m_array.Allocator();
321  }
322 
326  void SetAllocator( const allocator& a )
327  {
328  m_array.SetAllocator( a );
329  }
330 
336  {
337  return m_array.At( i );
338  }
339 
345  {
346  return m_array.At( i );
347  }
348 
360  {
361  return m_array.MutableIterator( i );
362  }
363 
368  const T& operator []( size_type i ) const
369  {
370  return m_array[i];
371  }
372 
377  const T& operator *() const
378  {
379  return *m_array;
380  }
381 
386  {
387  return m_array.ConstBegin();
388  }
389 
394  {
395  return m_array.Begin();
396  }
397 
402  {
403  return m_array.ConstEnd();
404  }
405 
410  {
411  return m_array.End();
412  }
413 
421  {
422  return m_array.ConstReverseBegin();
423  }
424 
432  {
433  return m_array.ReverseBegin();
434  }
435 
444  {
445  return m_array.ConstReverseEnd();
446  }
447 
456  {
457  return m_array.ReverseEnd();
458  }
459 
464  const T& First() const
465  {
466  return m_array.First();
467  }
468 
473  T& MutableFirst()
474  {
475  return m_array.First();
476  }
477 
482  const T& Last() const
483  {
484  return m_array.Last();
485  }
486 
491  T& MutableLast()
492  {
493  return m_array.Last();
494  }
495 
506  {
507  m_array.UniquifyIterator( i );
508  }
509 
521  {
522  m_array.UniquifyIterators( i, j );
523  }
524 
525 #ifndef __PCL_NO_STL_COMPATIBLE_ITERATORS
530  {
531  return Begin();
532  }
533 
538  {
539  return End();
540  }
541 #endif // !__PCL_NO_STL_COMPATIBLE_ITERATORS
542 
551  {
552  Assign( x );
553  return *this;
554  }
555 
565  void Assign( const ReferenceSortedArray& x )
566  {
567  m_array.Assign( x.m_array );
568  }
569 
574  {
575  Transfer( x );
576  return *this;
577  }
578 
589  {
590  m_array.Transfer( x.m_array );
591  }
592 
603  {
604  m_array.Transfer( std::move( x.m_array ) );
605  }
606 
615  {
616  Assign( x );
617  return *this;
618  }
619 
627  void Assign( const array_implementation& x )
628  {
629  m_array.Assign( x );
630  Sort();
631  }
632 
640  {
641  Transfer( x );
642  return *this;
643  }
644 
655  {
656  m_array.Transfer( x );
657  Sort();
658  }
659 
670  {
671  m_array.Transfer( std::move( x ) );
672  Sort();
673  }
674 
681  void Assign( const T* p, size_type n = 1 )
682  {
683  m_array.Assign( p, n );
684  }
685 
697  template <class FI>
698  void Assign( FI i, FI j )
699  {
700  m_array.Assign( i, j );
701  Sort();
702  }
703 
715  template <class C>
716  void CloneAssign( const C& x )
717  {
718  m_array.CloneAssign( x );
719  Sort();
720  }
721 
725  {
726  m_array.CloneAssign( x.m_array );
727  }
728 
732  {
733  m_array.CloneAssign( x );
734  }
735 
739  {
740  m_array.CloneAssign( x );
741  }
742 
750  void Import( iterator i, iterator j )
751  {
752  m_array.Import( i, j );
753  Sort();
754  }
755 
768  {
769  return m_array.Release();
770  }
771 
774  void Add( const ReferenceSortedArray& x )
775  {
776  const_iterator p = x.Begin(), q = x.End();
777  for ( iterator i = Begin(); i < End() && p < q; ++i )
778  if ( *p < *i )
779  i = m_array.Insert( i, (T*)p++ );
780  if ( p < q )
781  m_array.Append( p, q );
782  }
783 
786  void Add( const array_implementation& x )
787  {
788  Add( x.Begin(), x.End() );
789  }
790 
793  const_iterator Add( const T* p, size_type n = 1 )
794  {
795  if ( p != nullptr )
796  return m_array.Insert( pcl::InsertionPoint( Begin(), End(), *p ), p, n );
797  return const_iterator( nullptr );
798  }
799 
802  template <class FI>
803  void Add( FI i, FI j )
804  {
805  if ( i != j )
806  {
807  EnsureUnique();
808  for ( const_iterator l = Begin(), r = End(); ; )
809  {
810  FI h = i;
811  const_iterator m = m_array.Insert( pcl::InsertionPoint( l, r, **i ), *i );
812 
813  if ( ++i == j )
814  break;
815 
816  if ( **i < **h )
817  {
818  l = m_array.Begin();
819  r = m;
820  }
821  else
822  {
823  l = m + 1;
824  r = m_array.End();
825  }
826  }
827  }
828  }
829 
837  void Remove( const_iterator i, size_type n = 1 )
838  {
839  m_array.Remove( i, n );
840  }
841 
850  {
851  m_array.Remove( i, j );
852  }
853 
868  {
869  m_array.Truncate( i );
870  }
871 
884  void Shrink( size_type n = 1 )
885  {
886  m_array.Shrink( n );
887  }
888 
896  void Remove( const T& v )
897  {
898  m_array.Remove( v );
899  }
900 
908  template <class BP>
909  void Remove( const T& v, BP p )
910  {
911  m_array.Remove( v, p );
912  }
913 
920  void RemovePointer( const T* p )
921  {
922  m_array.RemovePointer( p );
923  }
924 
939  void Clear()
940  {
941  m_array.Clear();
942  }
943 
955  void Destroy( iterator i, size_type n = 1 )
956  {
957  m_array.Destroy( i, n );
958  }
959 
978  void Destroy( iterator i, iterator j )
979  {
980  m_array.Destroy( i, j );
981  }
982 
994  void Destroy( const T& v )
995  {
996  m_array.Destroy( v );
997  }
998 
1010  template <class BP>
1011  void Destroy( const T& v, BP p )
1012  {
1013  m_array.Destroy( v, p );
1014  }
1015 
1023  void Destroy()
1024  {
1025  m_array.Destroy();
1026  }
1027 
1035  void Reserve( size_type n )
1036  {
1037  m_array.Reserve( n );
1038  }
1039 
1052  void Squeeze()
1053  {
1054  m_array.Squeeze();
1055  }
1056 
1060  void Fill( const T& v )
1061  {
1062  m_array.Fill( v );
1063  }
1064 
1069  template <class F>
1070  void Apply( F f ) const
1071  {
1072  pcl::Apply( Begin(), End(), f );
1073  }
1074 
1080  template <class F>
1082  {
1083  return pcl::FirstThat( Begin(), End(), f );
1084  }
1085 
1091  template <class F>
1093  {
1094  return pcl::LastThat( Begin(), End(), f );
1095  }
1096 
1100  size_type Count( const T& v ) const
1101  {
1102  const_iterator i = pcl::BinarySearch( Begin(), End(), v );
1103  return (i != End()) ? pcl::InsertionPoint( i+1, End(), v ) - i : 0;
1104  }
1105 
1113  size_type Count( const T* p ) const
1114  {
1115  return m_array.Count( p );
1116  }
1117 
1122  template <class BP>
1123  size_type Count( const T& v, BP p ) const
1124  {
1125  return m_array.Count( v, p );
1126  }
1127 
1132  template <class UP>
1133  size_type CountIf( UP p ) const
1134  {
1135  return m_array.CountIf( p );
1136  }
1137 
1141  {
1142  return Begin();
1143  }
1144 
1147  template <class BP>
1148  const_iterator MinItem( BP p ) const
1149  {
1150  return pcl::MinItem( Begin(), End(), p );
1151  }
1152 
1156  {
1157  return IsEmpty() ? End() : End()-1;
1158  }
1159 
1162  template <class BP>
1163  const_iterator MaxItem( BP p ) const
1164  {
1165  return pcl::MaxItem( Begin(), End(), p );
1166  }
1167 
1170  const_iterator Search( const T& v ) const
1171  {
1172  return pcl::BinarySearch( Begin(), End(), v );
1173  }
1174 
1177  const_iterator Search( const T* p ) const
1178  {
1179  return m_array.Search( p );
1180  }
1181 
1184  template <class BP>
1185  const_iterator Search( const T& v, BP p ) const
1186  {
1187  return pcl::LinearSearch( Begin(), End(), v, p );
1188  }
1189 
1192  const_iterator SearchLast( const T& v ) const
1193  {
1194  return pcl::BinarySearchLast( Begin(), End(), v );
1195  }
1196 
1199  const_iterator SearchLast( const T* p ) const
1200  {
1201  return m_array.SearchLast( p );
1202  }
1203 
1206  template <class BP>
1207  const_iterator SearchLast( const T& v, BP p ) const
1208  {
1209  return pcl::LinearSearchLast( Begin(), End(), v, p );
1210  }
1211 
1214  bool Contains( const T& v ) const
1215  {
1216  return Search( v ) != End();
1217  }
1218 
1221  bool Contains( const T* p ) const
1222  {
1223  return m_array.Contains( p );
1224  }
1225 
1228  template <class BP>
1229  bool Contains( const T& v, BP p ) const
1230  {
1231  return Search( v, p ) != End();
1232  }
1233 
1236  void Sort()
1237  {
1238  m_array.Sort();
1239  }
1240 
1245  {
1246  pcl::Swap( x1.m_array, x2.m_array );
1247  }
1248 
1254  friend bool operator ==( const ReferenceSortedArray& x1, const ReferenceSortedArray& x2 )
1255  {
1256  return x1.m_array == x2.m_array;
1257  }
1258 
1264  friend bool operator ==( const ReferenceSortedArray& x1, const array_implementation& x2 )
1265  {
1266  return x1.m_array == x2;
1267  }
1268 
1274  friend bool operator ==( const array_implementation& x1, const ReferenceSortedArray& x2 )
1275  {
1276  return x1 == x2.m_array;
1277  }
1278 
1284  friend bool operator <( const ReferenceSortedArray& x1, const ReferenceSortedArray& x2 )
1285  {
1286  return x1.m_array < x2.m_array;
1287  }
1288 
1294  friend bool operator <( const ReferenceSortedArray& x1, const array_implementation& x2 )
1295  {
1296  return x1.m_array < x2;
1297  }
1298 
1304  friend bool operator <( const array_implementation& x1, const ReferenceSortedArray& x2 )
1305  {
1306  return x1 < x2.m_array;
1307  }
1308 
1325  template <class S, typename SP>
1326  S& ToSeparated( S& s, SP separator ) const
1327  {
1328  return m_array.ToSeparated( s, separator );
1329  }
1330 
1353  template <class S, typename SP, class AF>
1354  S& ToSeparated( S& s, SP separator, AF append ) const
1355  {
1356  return m_array.ToSeparated( s, separator, append );
1357  }
1358 
1367  template <class S>
1368  S& ToCommaSeparated( S& s ) const
1369  {
1370  return m_array.ToCommaSeparated( s );
1371  }
1372 
1381  template <class S>
1382  S& ToSpaceSeparated( S& s ) const
1383  {
1384  return m_array.ToSpaceSeparated( s );
1385  }
1386 
1395  template <class S>
1396  S& ToTabSeparated( S& s ) const
1397  {
1398  return m_array.ToTabSeparated( s );
1399  }
1400 
1409  template <class S>
1410  S& ToNewLineSeparated( S& s ) const
1411  {
1412  return m_array.ToNewLineSeparated( s );
1413  }
1414 
1425  uint64 Hash64( uint64 seed = 0 ) const
1426  {
1427  return m_array.Hash64( seed );
1428  }
1429 
1440  uint32 Hash32( uint32 seed = 0 ) const
1441  {
1442  return m_array.Hash32( seed );
1443  }
1444 
1449  uint64 Hash( uint64 seed = 0 ) const
1450  {
1451  return Hash64( seed );
1452  }
1453 
1454 private:
1455 
1456  array_implementation m_array;
1457 };
1458 
1459 // ----------------------------------------------------------------------------
1460 
1468 template <class T, class A, class V> inline
1469 ReferenceSortedArray<T,A>& operator <<( ReferenceSortedArray<T,A>& x, const V* p )
1470 {
1471  x.Add( static_cast<const T*>( p ) );
1472  return x;
1473 }
1474 
1482 template <class T, class A, class V> inline
1483 ReferenceSortedArray<T,A>& operator <<( ReferenceSortedArray<T,A>&& x, const V* p )
1484 {
1485  x.Add( static_cast<const T*>( p ) );
1486  return x;
1487 }
1488 
1494 template <class T, class A> inline
1495 ReferenceSortedArray<T,A>& operator <<( ReferenceSortedArray<T,A>& x1, const ReferenceSortedArray<T,A>& x2 )
1496 {
1497  x1.Add( x2 );
1498  return x1;
1499 }
1500 
1506 template <class T, class A> inline
1507 ReferenceSortedArray<T,A>& operator <<( ReferenceSortedArray<T,A>&& x1, const ReferenceSortedArray<T,A>& x2 )
1508 {
1509  x1.Add( x2 );
1510  return x1;
1511 }
1512 
1518 template <class T, class A> inline
1519 ReferenceSortedArray<T,A>& operator <<( ReferenceSortedArray<T,A>& x1, const ReferenceArray<T,A>& x2 )
1520 {
1521  x1.Add( x2 );
1522  return x1;
1523 }
1524 
1530 template <class T, class A> inline
1531 ReferenceSortedArray<T,A>& operator <<( ReferenceSortedArray<T,A>&& x1, const ReferenceArray<T,A>& x2 )
1532 {
1533  x1.Add( x2 );
1534  return x1;
1535 }
1536 
1537 // ----------------------------------------------------------------------------
1538 
1539 } // pcl
1540 
1541 #endif // __PCL_ReferenceSortedArray_h
1542 
1543 // ----------------------------------------------------------------------------
1544 // EOF pcl/ReferenceSortedArray.h - Released 2024-06-18T15:48:54Z
Root base class of all PCL containers of objects.
Definition: Container.h:78
Generic dynamic sorted array of pointers to objects.
Immutable ReferenceArray iterator.
Mutable ReferenceArray iterator.
Dynamic array of pointers to objects providing direct iteration and element access by reference.
typename array_implementation::iterator indirect_iterator
typename array_implementation::const_iterator const_indirect_iterator
typename array_implementation::allocator allocator
typename array_implementation::block_allocator block_allocator
Dynamic sorted array of pointers to objects providing direct iteration and element access by referenc...
const_iterator MinItem() const
ReferenceSortedArray(ReferenceSortedArray &&)=default
void Remove(const_iterator i, const_iterator j)
void Assign(const ReferenceSortedArray &x)
typename array_implementation::block_allocator block_allocator
iterator MutableIterator(const_iterator i)
const_iterator MaxItem(BP p) const
void Destroy(iterator i, iterator j)
friend void Swap(ReferenceSortedArray &x1, ReferenceSortedArray &x2)
void Truncate(const_iterator i)
reverse_iterator MutableReverseEnd()
const_iterator Search(const T &v) const
void Transfer(ReferenceSortedArray &&x)
void Add(const ReferenceSortedArray &x)
void Assign(const T *p, size_type n=1)
typename array_implementation::const_reverse_iterator const_reverse_iterator
typename array_implementation::const_indirect_iterator const_indirect_iterator
void Destroy(const T &v, BP p)
void Transfer(array_implementation &x)
const_iterator End() const
void UniquifyIterators(iterator &i, iterator &j)
ReferenceSortedArray(const ReferenceSortedArray &)=default
bool IsAliasOf(const ReferenceSortedArray &x) const
void Assign(const array_implementation &x)
typename array_implementation::const_iterator const_iterator
bool Contains(const T &v) const
void Destroy(iterator i, size_type n=1)
void CloneAssign(ReferenceSortedArray &x)
void Transfer(ReferenceSortedArray &x)
const_iterator SearchLast(const T *p) const
bool Contains(const T *p) const
const_iterator Add(const T *p, size_type n=1)
void UniquifyIterator(iterator &i)
size_type Count(const T *p) const
uint32 Hash32(uint32 seed=0) const
bool Contains(const T &v, BP p) const
typename array_implementation::iterator iterator
uint64 Hash(uint64 seed=0) const
ReferenceSortedArray(size_type n, const T *p)
const_iterator SearchLast(const T &v) const
const_iterator Search(const T &v, BP p) const
size_type Count(const T &v, BP p) const
typename array_implementation::allocator allocator
const_iterator Search(const T *p) const
const_reverse_iterator ReverseEnd() const
typename array_implementation::indirect_iterator indirect_iterator
const_iterator SearchLast(const T &v, BP p) const
const_iterator end() const
uint64 Hash64(uint64 seed=0) const
const allocator & Allocator() const
void Remove(const_iterator i, size_type n=1)
const_reverse_iterator ReverseBegin() const
void Remove(const T &v, BP p)
void Import(iterator i, iterator j)
const_iterator MinItem(BP p) const
const_iterator begin() const
void CloneAssign(IndirectSortedArray< T, A > &x)
const_iterator MaxItem() const
typename array_implementation::reverse_iterator reverse_iterator
size_type CountIf(UP p) const
void Transfer(array_implementation &&x)
const_iterator Begin() const
iterator MutableAt(size_type i)
reverse_iterator MutableReverseBegin()
void SetAllocator(const allocator &a)
const_iterator At(size_type i) const
void Add(const array_implementation &x)
const_iterator LastThat(F f) const
size_type Count(const T &v) const
void CloneAssign(SortedArray< T, A > &x)
const_iterator FirstThat(F f) const
Reverse random access iterator.
Definition: Iterator.h:420
Generic dynamic sorted array.
Definition: SortedArray.h:83
Array< T, A > & operator<<(Array< T, A > &x, const V &v)
Definition: Array.h:2295
bool operator==(const Array< T, A > &x1, const Array< T, A > &x2) noexcept
Definition: Array.h:2267
bool operator<(const Array< T, A > &x1, const Array< T, A > &x2) noexcept
Definition: Array.h:2278
Complex< T1 > operator*(const Complex< T1 > &c1, const Complex< T2 > &c2) noexcept
Definition: Complex.h:548
uint64 Hash64(const void *data, size_type size, uint64 seed=0) noexcept
Definition: Math.h:4750
void Swap(GenericPoint< T > &p1, GenericPoint< T > &p2) noexcept
Definition: Point.h:1459
unsigned long long uint64
Definition: Defs.h:682
unsigned int uint32
Definition: Defs.h:666
FI BinarySearch(FI i, FI j, const T &v) noexcept
Definition: Search.h:170
FI LinearSearch(FI i, FI j, const T &v) noexcept
Definition: Search.h:91
FI BinarySearchLast(FI i, FI j, const T &v) noexcept
Definition: Search.h:238
BI LinearSearchLast(BI i, BI j, const T &v) noexcept
Definition: Search.h:129
FI1 Search(FI1 i1, FI1 j1, FI2 i2, FI2 j2) noexcept
Definition: Search.h:397
FI InsertionPoint(FI i, FI j, const T &v) noexcept
Definition: Search.h:326
size_t size_type
Definition: Defs.h:609
void Sort(BI i, BI j)
Definition: Sort.h:520
BI LastThat(BI i, BI j, UP p) noexcept(noexcept(p))
Definition: Utility.h:350
FI MinItem(FI i, FI j) noexcept
Definition: Utility.h:441
FI MaxItem(FI i, FI j) noexcept
Definition: Utility.h:479
void Apply(FI i, FI j, F f) noexcept(noexcept(f))
Definition: Utility.h:249
FI FirstThat(FI i, FI j, UP p) noexcept(noexcept(p))
Definition: Utility.h:316
PCL root namespace.
Definition: AbstractImage.h:77