PCL
SortedArray.h
Go to the documentation of this file.
1 // ____ ______ __
2 // / __ \ / ____// /
3 // / /_/ // / / /
4 // / ____// /___ / /___ PixInsight Class Library
5 // /_/ \____//_____/ PCL 2.1.19
6 // ----------------------------------------------------------------------------
7 // pcl/SortedArray.h - Released 2019-11-07T10:59:34Z
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_SortedArray_h
53 #define __PCL_SortedArray_h
54 
56 
57 #include <pcl/Defs.h>
58 #include <pcl/Diagnostics.h>
59 
60 #include <pcl/Array.h>
61 
62 namespace pcl
63 {
64 
65 // ----------------------------------------------------------------------------
66 
81 template <class T, class A = StandardAllocator>
82 class PCL_CLASS SortedArray : public DirectSortedContainer<T>
83 {
84 public:
85 
89 
94 
97  typedef typename array_implementation::allocator
99 
102  typedef typename array_implementation::iterator
104 
107  typedef typename array_implementation::const_iterator
109 
114 
119 
120  // -------------------------------------------------------------------------
121 
125  SortedArray() : m_array()
126  {
127  }
128 
132  explicit
133  SortedArray( size_type n ) : m_array( n )
134  {
135  }
136 
140  SortedArray( size_type n, const T& v ) : m_array( n, v )
141  {
142  }
143 
148  template <class FI>
149  SortedArray( FI i, FI j ) : m_array( i, j )
150  {
151  Sort();
152  }
153 
162  template <typename T1>
163  SortedArray( std::initializer_list<T1> l ) : SortedArray( l.begin(), l.end() )
164  {
165  }
166 
170  SortedArray( const SortedArray& x ) : m_array( x.m_array )
171  {
172  }
173 
177  SortedArray( SortedArray&& x ) : m_array( std::move( x.m_array ) )
178  {
179  }
180 
186  {
187  }
188 
192  bool IsUnique() const
193  {
194  return m_array.IsUnique();
195  }
196 
202  bool IsAliasOf( const SortedArray& x ) const
203  {
204  return m_array.IsAliasOf( x.m_array );
205  }
206 
215  {
216  m_array.EnsureUnique();
217  }
218 
223  size_type Size() const
224  {
225  return m_array.Size();
226  }
227 
232  {
233  return m_array.Length();
234  }
235 
239  {
240  return m_array.Capacity();
241  }
242 
246  {
247  return m_array.Available();
248  }
249 
252  bool IsValid() const
253  {
254  return m_array.IsValid();
255  }
256 
259  bool IsEmpty() const
260  {
261  return m_array.IsEmpty();
262  }
263 
267  {
268  return m_array.LowerBound();
269  }
270 
274  {
275  return m_array.UpperBound();
276  }
277 
280  const allocator& GetAllocator() const
281  {
282  return m_array.GetAllocator();
283  }
284 
287  void SetAllocator( const allocator& a )
288  {
289  m_array.SetAllocator( a );
290  }
291 
295  {
296  return m_array.At( i );
297  }
298 
302  {
303  return m_array.At( i );
304  }
305 
309  {
310  return m_array.MutableIterator( i );
311  }
312 
315  const T& operator []( size_type i ) const
316  {
317  return m_array[i];
318  }
319 
322  const T& operator *() const
323  {
324  return *Begin();
325  }
326 
330  {
331  return m_array.ConstBegin();
332  }
333 
337  {
338  return m_array.Begin();
339  }
340 
344  {
345  return m_array.ConstEnd();
346  }
347 
351  {
352  return m_array.End();
353  }
354 
358  {
359  return m_array.ConstReverseBegin();
360  }
361 
365  {
366  return m_array.ReverseBegin();
367  }
368 
372  {
373  return m_array.ConstReverseEnd();
374  }
375 
379  {
380  return m_array.ReverseEnd();
381  }
382 
392  {
393  return m_array.UniquifyIterator( i );
394  }
395 
406  {
407  return m_array.UniquifyIterators( i, j );
408  }
409 
410 #ifndef __PCL_NO_STL_COMPATIBLE_ITERATORS
411 
415  {
416  return Begin();
417  }
418 
423  {
424  return End();
425  }
426 #endif // !__PCL_NO_STL_COMPATIBLE_ITERATORS
427 
434  SortedArray& operator =( const SortedArray& x )
435  {
436  Assign( x );
437  return *this;
438  }
439 
442  void Assign( const SortedArray& x )
443  {
444  m_array.Assign( x.m_array );
445  }
446 
450  SortedArray& operator =( SortedArray&& x )
451  {
452  Transfer( x );
453  return *this;
454  }
455 
459  {
460  m_array.Transfer( x.m_array );
461  }
462 
465  void Transfer( SortedArray&& x )
466  {
467  m_array.Transfer( x.m_array );
468  }
469 
472  SortedArray& operator =( const array_implementation& x )
473  {
474  Assign( x );
475  return *this;
476  }
477 
480  void Assign( const array_implementation& x )
481  {
482  m_array.Assign( x );
483  Sort();
484  }
485 
488  SortedArray& operator =( array_implementation&& x )
489  {
490  Transfer( x );
491  return *this;
492  }
493 
496  void Transfer( array_implementation& x )
497  {
498  m_array.Transfer( x );
499  Sort();
500  }
501 
504  void Transfer( array_implementation&& x )
505  {
506  m_array.Transfer( x );
507  Sort();
508  }
509 
512  void Assign( const T& v, size_type n = 1 )
513  {
514  m_array.Assign( v, n );
515  }
516 
519  template <class FI>
520  void Assign( FI i, FI j )
521  {
522  m_array.Assign( i, j );
523  Sort();
524  }
525 
528  void Import( iterator i, iterator j )
529  {
530  m_array.Import( i, j );
531  Sort();
532  }
533 
537  {
538  return m_array.Release();
539  }
540 
543  void Add( const SortedArray& x )
544  {
545  const_iterator p = x.Begin(), q = x.End();
546  for ( iterator i = m_array.Begin(); i < m_array.End() && p < q; ++i )
547  if ( *p < *i )
548  i = m_array.Insert( i, *p++ );
549  if ( p < q )
550  m_array.Append( p, q );
551  }
552 
555  void Add( const Array<T,A>& x )
556  {
557  Add( x.Begin(), x.End() );
558  }
559 
562  const_iterator Add( const T& v, size_type n = 1 )
563  {
564  return m_array.Insert( pcl::InsertionPoint( m_array.Begin(), m_array.End(), v ), v, n );
565  }
566 
569  template <class FI>
570  void Add( FI i, FI j )
571  {
572  if ( i != j )
573  {
574  m_array.EnsureUnique();
575  for ( iterator l = m_array.Begin(), r = m_array.End(); ; )
576  {
577  FI h = i;
578  iterator m = m_array.Insert( pcl::InsertionPoint( l, r, *i ), *i );
579 
580  if ( ++i == j )
581  break;
582 
583  if ( *i < *h )
584  {
585  l = m_array.Begin();
586  r = m;
587  }
588  else
589  {
590  l = m + 1;
591  r = m_array.End();
592  }
593  }
594  }
595  }
596 
599  void Remove( const_iterator i, size_type n = 1 )
600  {
601  m_array.Remove( const_cast<iterator>( i ), n );
602  }
603 
607  {
608  m_array.Remove( const_cast<iterator>( i ), const_cast<iterator>( j ) );
609  }
610 
622  {
623  m_array.Truncate( const_cast<iterator>( i ) );
624  }
625 
635  void Shrink( size_type n = 1 )
636  {
637  m_array.Shrink( n );
638  }
639 
642  void Remove( const T& v )
643  {
644  const_iterator i = pcl::BinarySearch( Begin(), End(), v );
645  if ( i != End() )
646  Remove( i, pcl::InsertionPoint( i+1, End(), v ) );
647  }
648 
651  void Clear()
652  {
653  m_array.Clear();
654  }
655 
658  void Reserve( size_type n )
659  {
660  m_array.Reserve( n );
661  }
662 
665  void Squeeze()
666  {
667  m_array.Squeeze();
668  }
669 
673  void Fill( const T& v )
674  {
675  m_array.Fill( v );
676  }
677 
680  template <class F>
681  void Apply( F f ) const
682  {
683  pcl::Apply( Begin(), End(), f );
684  }
685 
688  template <class F>
690  {
691  return pcl::FirstThat( Begin(), End(), f );
692  }
693 
696  template <class F>
698  {
699  return pcl::LastThat( Begin(), End(), f );
700  }
701 
704  size_type Count( const T& v ) const
705  {
706  const_iterator i = pcl::BinarySearch( Begin(), End(), v );
707  return (i != End()) ? pcl::InsertionPoint( i+1, End(), v ) - i : 0;
708  }
709 
712  template <class BP>
713  size_type Count( const T& v, BP p ) const
714  {
715  return m_array.Count( v, p );
716  }
717 
720  template <class UP>
721  size_type CountIf( UP p ) const
722  {
723  return m_array.CountIf( p );
724  }
725 
729  {
730  return Begin();
731  }
732 
735  template <class BP>
736  const_iterator MinItem( BP p ) const
737  {
738  return pcl::MinItem( Begin(), End(), p );
739  }
740 
744  {
745  return IsEmpty() ? End() : End()-1;
746  }
747 
750  template <class BP>
751  const_iterator MaxItem( BP p ) const
752  {
753  return pcl::MaxItem( Begin(), End(), p );
754  }
755 
758  const_iterator Search( const T& v ) const
759  {
760  return pcl::BinarySearch( Begin(), End(), v );
761  }
762 
765  template <class BP>
766  const_iterator Search( const T& v, BP p ) const
767  {
768  return m_array.Search( v, p );
769  }
770 
773  const_iterator SearchLast( const T& v ) const
774  {
775  return pcl::BinarySearchLast( Begin(), End(), v );
776  }
777 
780  template <class BP>
781  const_iterator SearchLast( const T& v, BP p ) const
782  {
783  return m_array.SearchLast( v, p );
784  }
785 
788  bool Contains( const T& v ) const
789  {
790  return Search( v ) != End();
791  }
792 
795  template <class BP>
796  bool Contains( const T& v, BP p ) const
797  {
798  return Search( v, p ) != End();
799  }
800 
803  void Sort()
804  {
805  m_array.Sort();
806  }
807 
811  friend void Swap( SortedArray& x1, SortedArray& x2 )
812  {
813  pcl::Swap( x1.m_array, x2.m_array );
814  }
815 
820  friend bool operator ==( const SortedArray& x1, const SortedArray& x2 )
821  {
822  return x1.m_array == x2.m_array;
823  }
824 
829  friend bool operator ==( const SortedArray& x1, const array_implementation& x2 )
830  {
831  return x1.m_array == x2;
832  }
833 
838  friend bool operator ==( const array_implementation& x1, const SortedArray& x2 )
839  {
840  return x1 == x2.m_array;
841  }
842 
848  friend bool operator <( const SortedArray& x1, const SortedArray& x2 )
849  {
850  return x1.m_array < x2.m_array;
851  }
852 
857  friend bool operator <( const SortedArray& x1, const array_implementation& x2 )
858  {
859  return x1.m_array < x2;
860  }
861 
866  friend bool operator <( const array_implementation& x1, const SortedArray& x2 )
867  {
868  return x1 < x2.m_array;
869  }
870 
887  template <class S, typename SP>
888  S& ToSeparated( S& s, SP separator ) const
889  {
890  return m_array.ToSeparated( s, separator );
891  }
892 
915  template <class S, typename SP, class AF>
916  S& ToSeparated( S& s, SP separator, AF append ) const
917  {
918  return m_array.ToSeparated( s, separator, append );
919  }
920 
929  template <class S>
930  S& ToCommaSeparated( S& s ) const
931  {
932  return m_array.ToCommaSeparated( s );
933  }
934 
943  template <class S>
944  S& ToSpaceSeparated( S& s ) const
945  {
946  return m_array.ToSpaceSeparated( s );
947  }
948 
957  template <class S>
958  S& ToTabSeparated( S& s ) const
959  {
960  return m_array.ToTabSeparated( s );
961  }
962 
971  uint64 Hash64( uint64 seed = 0 ) const
972  {
973  return m_array.Hash64( seed );
974  }
975 
984  uint32 Hash32( uint32 seed = 0 ) const
985  {
986  return m_array.Hash32( seed );
987  }
988 
993  uint64 Hash( uint64 seed = 0 ) const
994  {
995  return Hash64( seed );
996  }
997 
998  // -------------------------------------------------------------------------
999 
1000 private:
1001 
1002  array_implementation m_array;
1003 };
1004 
1005 // ----------------------------------------------------------------------------
1006 
1015 template <class T, class A, class V> inline
1016 SortedArray<T,A>& operator <<( SortedArray<T,A>& x, const V& v )
1017 {
1018  x.Add( T( v ) );
1019  return x;
1020 }
1021 
1030 template <class T, class A, class V> inline
1031 SortedArray<T,A>& operator <<( SortedArray<T,A>&& x, const V& v )
1032 {
1033  x.Add( T( v ) );
1034  return x;
1035 }
1036 
1042 template <class T, class A> inline
1043 SortedArray<T,A>& operator <<( SortedArray<T,A>& x1, const SortedArray<T,A>& x2 )
1044 {
1045  x1.Add( x2 );
1046  return x1;
1047 }
1048 
1054 template <class T, class A> inline
1055 SortedArray<T,A>& operator <<( SortedArray<T,A>&& x1, const SortedArray<T,A>& x2 )
1056 {
1057  x1.Add( x2 );
1058  return x1;
1059 }
1060 
1066 template <class T, class A> inline
1067 SortedArray<T,A>& operator <<( SortedArray<T,A>& x1, const Array<T,A>& x2 )
1068 {
1069  x1.Add( x2 );
1070  return x1;
1071 }
1072 
1078 template <class T, class A> inline
1079 SortedArray<T,A>& operator <<( SortedArray<T,A>&& x1, const Array<T,A>& x2 )
1080 {
1081  x1.Add( x2 );
1082  return x1;
1083 }
1084 
1085 // ----------------------------------------------------------------------------
1086 
1087 } // pcl
1088 
1089 #endif // __PCL_SortedArray_h
1090 
1091 // ----------------------------------------------------------------------------
1092 // EOF pcl/SortedArray.h - Released 2019-11-07T10:59:34Z
const_iterator MinItem(BP p) const
Definition: SortedArray.h:736
void Transfer(array_implementation &&x)
Definition: SortedArray.h:504
reverse_iterator MutableReverseEnd()
Definition: SortedArray.h:378
uint64 Hash64(const void *data, size_type size, uint64 seed=0)
Definition: Math.h:3551
bool IsValid() const
Definition: SortedArray.h:252
const_iterator SearchLast(const T &v) const
Definition: SortedArray.h:773
SortedArray(size_type n)
Definition: SortedArray.h:133
Complex< T1 > operator*(const Complex< T1 > &c1, const Complex< T2 > &c2)
Definition: Complex.h:539
void Remove(const T &v)
Definition: SortedArray.h:642
iterator MutableIterator(const_iterator i)
Definition: SortedArray.h:308
const_iterator LastThat(F f) const
Definition: SortedArray.h:697
void SetAllocator(const allocator &a)
Definition: SortedArray.h:287
void Swap(GenericPoint< T > &p1, GenericPoint< T > &p2)
Definition: Point.h:1402
const_iterator At(size_type i) const
Definition: SortedArray.h:294
SortedArray(SortedArray &&x)
Definition: SortedArray.h:177
uint64 Hash64(uint64 seed=0) const
Definition: SortedArray.h:971
iterator Release()
Definition: SortedArray.h:536
void Import(iterator i, iterator j)
Definition: SortedArray.h:528
array_implementation::allocator allocator
Definition: SortedArray.h:98
void Assign(FI i, FI j)
Definition: SortedArray.h:520
iterator MutableAt(size_type i)
Definition: SortedArray.h:301
size_type UpperBound() const
Definition: SortedArray.h:273
PCL root namespace.
Definition: AbstractImage.h:76
iterator MutableEnd()
Definition: SortedArray.h:350
iterator Begin()
Definition: Array.h:425
const_iterator end() const
Definition: SortedArray.h:422
BI LastThat(BI i, BI j, UP p)
Definition: Utility.h:350
array_implementation::iterator iterator
Definition: SortedArray.h:103
FI BinarySearchLast(FI i, FI j, const T &v)
Definition: Search.h:238
void Assign(const SortedArray &x)
Definition: SortedArray.h:442
const_iterator End() const
Definition: SortedArray.h:343
FI MaxItem(FI i, FI j)
Definition: Utility.h:479
Root base class of all PCL sorted containers of objects.
Definition: Container.h:99
void Remove(const_iterator i, const_iterator j)
Definition: SortedArray.h:606
void Sort(BI i, BI j)
Definition: Sort.h:534
const_iterator begin() const
Definition: SortedArray.h:414
size_type CountIf(UP p) const
Definition: SortedArray.h:721
void Add(FI i, FI j)
Definition: SortedArray.h:570
void Transfer(SortedArray &x)
Definition: SortedArray.h:458
SortedArray(FI i, FI j)
Definition: SortedArray.h:149
void UniquifyIterator(iterator &i)
Definition: SortedArray.h:391
const_iterator Search(const T &v) const
Definition: SortedArray.h:758
const_iterator MaxItem(BP p) const
Definition: SortedArray.h:751
bool Contains(const T &v, BP p) const
Definition: SortedArray.h:796
const allocator & GetAllocator() const
Definition: SortedArray.h:280
size_t size_type
Definition: Defs.h:543
Provides memory allocation for PCL containers.
Definition: Allocator.h:131
FI InsertionPoint(FI i, FI j, const T &v)
Definition: Search.h:326
bool Contains(const T &v) const
Definition: SortedArray.h:788
void Apply(FI i, FI j, F f)
Definition: Utility.h:249
void Fill(const T &v)
Definition: SortedArray.h:673
FI BinarySearch(FI i, FI j, const T &v)
Definition: Search.h:170
void Reserve(size_type n)
Definition: SortedArray.h:658
unsigned long long uint64
Definition: Defs.h:616
const_iterator Begin() const
Definition: SortedArray.h:329
const_iterator FirstThat(F f) const
Definition: SortedArray.h:689
void Truncate(const_iterator i)
Definition: SortedArray.h:621
uint64 Hash(uint64 seed=0) const
Definition: SortedArray.h:993
friend void Swap(SortedArray &x1, SortedArray &x2)
Definition: SortedArray.h:811
bool IsUnique() const
Definition: SortedArray.h:192
size_type Count(const T &v) const
Definition: SortedArray.h:704
void Transfer(SortedArray &&x)
Definition: SortedArray.h:465
reverse_iterator MutableReverseBegin()
Definition: SortedArray.h:364
SortedArray(size_type n, const T &v)
Definition: SortedArray.h:140
SortedArray(std::initializer_list< T1 > l)
Definition: SortedArray.h:163
array_implementation::block_allocator block_allocator
Definition: SortedArray.h:93
bool IsEmpty() const
Definition: SortedArray.h:259
void Apply(F f) const
Definition: SortedArray.h:681
bool operator<(const Array< T, A > &x1, const Array< T, A > &x2)
Definition: Array.h:2086
iterator MutableBegin()
Definition: SortedArray.h:336
void Remove(const_iterator i, size_type n=1)
Definition: SortedArray.h:599
size_type LowerBound() const
Definition: SortedArray.h:266
Generic dynamic array.
Definition: Array.h:99
uint32 Hash32(uint32 seed=0) const
Definition: SortedArray.h:984
size_type Count(const T &v, BP p) const
Definition: SortedArray.h:713
const_iterator MaxItem() const
Definition: SortedArray.h:743
SortedArray(const SortedArray &x)
Definition: SortedArray.h:170
void Shrink(size_type n=1)
Definition: SortedArray.h:635
const_reverse_iterator ReverseEnd() const
Definition: SortedArray.h:371
const_iterator MinItem() const
Definition: SortedArray.h:728
const_iterator SearchLast(const T &v, BP p) const
Definition: SortedArray.h:781
Reverse random access iterator.
Definition: Iterator.h:414
array_implementation::const_iterator const_iterator
Definition: SortedArray.h:108
array_implementation::reverse_iterator reverse_iterator
Definition: SortedArray.h:113
void Assign(const T &v, size_type n=1)
Definition: SortedArray.h:512
iterator End()
Definition: Array.h:450
A block allocator class that uses the standard new and delete operators.
Definition: StdAlloc.h:81
const_iterator Add(const T &v, size_type n=1)
Definition: SortedArray.h:562
FI MinItem(FI i, FI j)
Definition: Utility.h:441
FI1 Search(FI1 i1, FI1 j1, FI2 i2, FI2 j2)
Definition: Search.h:397
size_type Available() const
Definition: SortedArray.h:245
bool operator==(const Array< T, A > &x1, const Array< T, A > &x2)
Definition: Array.h:2075
array_implementation::const_reverse_iterator const_reverse_iterator
Definition: SortedArray.h:118
Array< T, A > array_implementation
Definition: SortedArray.h:88
void Add(const SortedArray &x)
Definition: SortedArray.h:543
void UniquifyIterators(iterator &i, iterator &j)
Definition: SortedArray.h:405
FI FirstThat(FI i, FI j, UP p)
Definition: Utility.h:316
const_iterator Search(const T &v, BP p) const
Definition: SortedArray.h:766
const_reverse_iterator ReverseBegin() const
Definition: SortedArray.h:357
void Add(const Array< T, A > &x)
Definition: SortedArray.h:555
size_type Capacity() const
Definition: SortedArray.h:238
size_type Size() const
Definition: SortedArray.h:223
void Transfer(array_implementation &x)
Definition: SortedArray.h:496
bool IsAliasOf(const SortedArray &x) const
Definition: SortedArray.h:202
unsigned int uint32
Definition: Defs.h:600
void Assign(const array_implementation &x)
Definition: SortedArray.h:480
size_type Length() const
Definition: SortedArray.h:231
Generic dynamic sorted array.
Definition: SortedArray.h:82