SortedArray.h

Go to the documentation of this file.

//     ____   ______ __
//    / __ \ / ____// /
//   / /_/ // /    / /
//  / ____// /___ / /___   PixInsight Class Library
// /_/     \____//_____/   PCL 2.9.3
// ----------------------------------------------------------------------------
// pcl/SortedArray.h - Released 2025-02-21T12:13:32Z
// ----------------------------------------------------------------------------
// This file is part of the PixInsight Class Library (PCL).
// PCL is a multiplatform C++ framework for development of PixInsight modules.
//
// Copyright (c) 2003-2025 Pleiades Astrophoto S.L. All Rights Reserved.
//
// Redistribution and use in both source and binary forms, with or without
// modification, is permitted provided that the following conditions are met:
//
// 1. All redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
//
// 2. All redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
//
// 3. Neither the names "PixInsight" and "Pleiades Astrophoto", nor the names
//    of their contributors, may be used to endorse or promote products derived
//    from this software without specific prior written permission. For written
//    permission, please contact info@pixinsight.com.
//
// 4. All products derived from this software, in any form whatsoever, must
//    reproduce the following acknowledgment in the end-user documentation
//    and/or other materials provided with the product:
//
//    "This product is based on software from the PixInsight project, developed
//    by Pleiades Astrophoto and its contributors (https://pixinsight.com/)."
//
//    Alternatively, if that is where third-party acknowledgments normally
//    appear, this acknowledgment must be reproduced in the product itself.
//
// THIS SOFTWARE IS PROVIDED BY PLEIADES ASTROPHOTO AND ITS CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
// TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL PLEIADES ASTROPHOTO OR ITS
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, BUSINESS
// INTERRUPTION; PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; AND LOSS OF USE,
// DATA OR PROFITS) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.
// ----------------------------------------------------------------------------
 
#ifndef __PCL_SortedArray_h
#define __PCL_SortedArray_h
 
 
#include <pcl/Defs.h>
#include <pcl/Diagnostics.h>
 
#include <pcl/Array.h>
 
namespace pcl
{
 
// ----------------------------------------------------------------------------
 
template <class T, class A = StandardAllocator>
class PCL_CLASS SortedArray : public DirectSortedContainer<T>
{
public:
 
   using container_type = DirectSortedContainer<T>;
 
   using item_type = typename container_type::item_type;
 
   using const_item_type = typename container_type::const_item_type;
 
   using array_implementation = Array<T,A>;
 
   using block_allocator = typename array_implementation::block_allocator;
 
   using allocator = typename array_implementation::allocator;
 
   using iterator = typename array_implementation::iterator;
 
   using const_iterator = typename array_implementation::const_iterator;
 
   using reverse_iterator = typename array_implementation::reverse_iterator;
 
   using const_reverse_iterator = typename array_implementation::const_reverse_iterator;
 
   // -------------------------------------------------------------------------
 
   SortedArray() = default;
 
   explicit
   SortedArray( size_type n )
      : m_array( n )
   {
   }
 
   SortedArray( size_type n, const T& v )
      : m_array( n, v )
   {
   }
 
   template <class FI>
   SortedArray( FI i, FI j )
      : m_array( i, j )
   {
      Sort();
   }
 
   template <typename T1>
   SortedArray( std::initializer_list<T1> l )
      : SortedArray( l.begin(), l.end() )
   {
   }
 
   SortedArray( const SortedArray& ) = default;
 
   SortedArray( SortedArray&& ) = default;
 
   ~SortedArray()
   {
   }
 
   bool IsUnique() const
   {
      return m_array.IsUnique();
   }
 
   bool IsAliasOf( const SortedArray& x ) const
   {
      return m_array.IsAliasOf( x.m_array );
   }
 
   void EnsureUnique()
   {
      m_array.EnsureUnique();
   }
 
   size_type Size() const
   {
      return m_array.Size();
   }
 
   size_type Length() const
   {
      return m_array.Length();
   }
 
   size_type Capacity() const
   {
      return m_array.Capacity();
   }
 
   size_type Available() const
   {
      return m_array.Available();
   }
 
   bool IsValid() const
   {
      return m_array.IsValid();
   }
 
   bool IsEmpty() const
   {
      return m_array.IsEmpty();
   }
 
   size_type LowerBound() const
   {
      return m_array.LowerBound();
   }
 
   size_type UpperBound() const
   {
      return m_array.UpperBound();
   }
 
   const allocator& Allocator() const
   {
      return m_array.Allocator();
   }
 
   void SetAllocator( const allocator& a )
   {
      m_array.SetAllocator( a );
   }
 
   const_iterator At( size_type i ) const
   {
      return m_array.At( i );
   }
 
   iterator MutableAt( size_type i )
   {
      return m_array.At( i );
   }
 
   iterator MutableIterator( const_iterator i )
   {
      return m_array.MutableIterator( i );
   }
 
   const T& operator []( size_type i ) const
   {
      return m_array[i];
   }
 
   const T& operator *() const
   {
      return *Begin();
   }
 
   const_iterator Begin() const
   {
      return m_array.ConstBegin();
   }
 
   iterator MutableBegin()
   {
      return m_array.Begin();
   }
 
   const_iterator End() const
   {
      return m_array.ConstEnd();
   }
 
   iterator MutableEnd()
   {
      return m_array.End();
   }
 
   const_reverse_iterator ReverseBegin() const
   {
      return m_array.ConstReverseBegin();
   }
 
   reverse_iterator MutableReverseBegin()
   {
      return m_array.ReverseBegin();
   }
 
   const_reverse_iterator ReverseEnd() const
   {
      return m_array.ConstReverseEnd();
   }
 
   reverse_iterator MutableReverseEnd()
   {
      return m_array.ReverseEnd();
   }
 
   void UniquifyIterator( iterator& i )
   {
      return m_array.UniquifyIterator( i );
   }
 
   void UniquifyIterators( iterator& i, iterator& j )
   {
      return m_array.UniquifyIterators( i, j );
   }
 
#ifndef __PCL_NO_STL_COMPATIBLE_ITERATORS
   const_iterator begin() const
   {
      return Begin();
   }
 
   const_iterator end() const
   {
      return End();
   }
#endif   // !__PCL_NO_STL_COMPATIBLE_ITERATORS
 
   SortedArray& operator =( const SortedArray& x )
   {
      Assign( x );
      return *this;
   }
 
   void Assign( const SortedArray& x )
   {
      m_array.Assign( x.m_array );
   }
 
   SortedArray& operator =( SortedArray&& x )
   {
      Transfer( x );
      return *this;
   }
 
   void Transfer( SortedArray& x )
   {
      m_array.Transfer( x.m_array );
   }
 
   void Transfer( SortedArray&& x )
   {
      m_array.Transfer( x.m_array );
   }
 
   SortedArray& operator =( const array_implementation& x )
   {
      Assign( x );
      return *this;
   }
 
   void Assign( const array_implementation& x )
   {
      m_array.Assign( x );
      Sort();
   }
 
   SortedArray& operator =( array_implementation&& x )
   {
      Transfer( x );
      return *this;
   }
 
   void Transfer( array_implementation& x )
   {
      m_array.Transfer( x );
      Sort();
   }
 
   void Transfer( array_implementation&& x )
   {
      m_array.Transfer( x );
      Sort();
   }
 
   void Assign( const T& v, size_type n = 1 )
   {
      m_array.Assign( v, n );
   }
 
   template <class FI>
   void Assign( FI i, FI j )
   {
      m_array.Assign( i, j );
      Sort();
   }
 
   void Import( iterator i, iterator j )
   {
      m_array.Import( i, j );
      Sort();
   }
 
   iterator Release()
   {
      return m_array.Release();
   }
 
   array_implementation ToUnsorted() const
   {
      return m_array;
   }
 
   void Add( const SortedArray& x )
   {
      const_iterator p = x.Begin(), q = x.End();
      for ( iterator i = m_array.Begin(); i < m_array.End() && p < q; ++i )
         if ( *p < *i )
            i = m_array.Insert( i, *p++ );
      if ( p < q )
         m_array.Append( p, q );
   }
 
   void Add( const Array<T,A>& x )
   {
      Add( x.Begin(), x.End() );
   }
 
   const_iterator Add( const T& v, size_type n = 1 )
   {
      return m_array.Insert( pcl::InsertionPoint( m_array.Begin(), m_array.End(), v ), v, n );
   }
 
   template <class FI>
   void Add( FI i, FI j )
   {
      if ( i != j )
      {
         m_array.EnsureUnique();
         for ( iterator l = m_array.Begin(), r = m_array.End(); ; )
         {
            FI h = i;
            iterator m = m_array.Insert( pcl::InsertionPoint( l, r, *i ), *i );
 
            if ( ++i == j )
               break;
 
            if ( *i < *h )
            {
               l = m_array.Begin();
               r = m;
            }
            else
            {
               l = m + 1;
               r = m_array.End();
            }
         }
      }
   }
 
   void Remove( const_iterator i, size_type n = 1 )
   {
      m_array.Remove( const_cast<iterator>( i ), n );
   }
 
   void Remove( const_iterator i, const_iterator j )
   {
      m_array.Remove( const_cast<iterator>( i ), const_cast<iterator>( j ) );
   }
 
   void RemoveFirst( size_type n = 1 )
   {
      m_array.RemoveFirst( n );
   }
 
   void RemoveLast( size_type n = 1 )
   {
      m_array.RemoveLast( n );
   }
 
   void Truncate( const_iterator i )
   {
      m_array.Truncate( const_cast<iterator>( i ) );
   }
 
   void Shrink( size_type n = 1 )
   {
      m_array.Shrink( n );
   }
 
   void Remove( const T& v )
   {
      const_iterator i = pcl::BinarySearch( Begin(), End(), v );
      if ( i != End() )
         Remove( i, pcl::InsertionPoint( i+1, End(), v ) );
   }
 
   void Clear()
   {
      m_array.Clear();
   }
 
   void Reserve( size_type n )
   {
      m_array.Reserve( n );
   }
 
   void Squeeze()
   {
      m_array.Squeeze();
   }
 
   void Fill( const T& v )
   {
      m_array.Fill( v );
   }
 
   template <class F>
   void Apply( F f ) const
   {
      pcl::Apply( Begin(), End(), f );
   }
 
   template <class F>
   const_iterator FirstThat( F f ) const
   {
      return pcl::FirstThat( Begin(), End(), f );
   }
 
   template <class F>
   const_iterator LastThat( F f ) const
   {
      return pcl::LastThat( Begin(), End(), f );
   }
 
   size_type Count( const T& v ) const
   {
      const_iterator i = pcl::BinarySearch( Begin(), End(), v );
      return (i != End()) ? pcl::InsertionPoint( i+1, End(), v ) - i : 0;
   }
 
   template <class BP>
   size_type Count( const T& v, BP p ) const
   {
      return m_array.Count( v, p );
   }
 
   template <class UP>
   size_type CountIf( UP p ) const
   {
      return m_array.CountIf( p );
   }
 
   const_iterator MinItem() const
   {
      return Begin();
   }
 
   template <class BP>
   const_iterator MinItem( BP p ) const
   {
      return pcl::MinItem( Begin(), End(), p );
   }
 
   const_iterator MaxItem() const
   {
      return IsEmpty() ? End() : End()-1;
   }
 
   template <class BP>
   const_iterator MaxItem( BP p ) const
   {
      return pcl::MaxItem( Begin(), End(), p );
   }
 
   const_iterator Search( const T& v ) const
   {
      return pcl::BinarySearch( Begin(), End(), v );
   }
 
   template <class BP>
   const_iterator Search( const T& v, BP p ) const
   {
      return m_array.Search( v, p );
   }
 
   const_iterator SearchLast( const T& v ) const
   {
      return pcl::BinarySearchLast( Begin(), End(), v );
   }
 
   template <class BP>
   const_iterator SearchLast( const T& v, BP p ) const
   {
      return m_array.SearchLast( v, p );
   }
 
   bool Contains( const T& v ) const
   {
      return Search( v ) != End();
   }
 
   template <class BP>
   bool Contains( const T& v, BP p ) const
   {
      return Search( v, p ) != End();
   }
 
   void Sort()
   {
      m_array.Sort();
   }
 
   friend void Swap( SortedArray& x1, SortedArray& x2 )
   {
      pcl::Swap( x1.m_array, x2.m_array );
   }
 
   friend bool operator ==( const SortedArray& x1, const SortedArray& x2 )
   {
      return x1.m_array == x2.m_array;
   }
 
   friend bool operator ==( const SortedArray& x1, const array_implementation& x2 )
   {
      return x1.m_array == x2;
   }
 
   friend bool operator ==( const array_implementation& x1, const SortedArray& x2 )
   {
      return x1 == x2.m_array;
   }
 
   friend bool operator <( const SortedArray& x1, const SortedArray& x2 )
   {
      return x1.m_array < x2.m_array;
   }
 
   friend bool operator <( const SortedArray& x1, const array_implementation& x2 )
   {
      return x1.m_array < x2;
   }
 
   friend bool operator <( const array_implementation& x1, const SortedArray& x2 )
   {
      return x1 < x2.m_array;
   }
 
   template <class S, typename SP>
   S& ToSeparated( S& s, SP separator ) const
   {
      return m_array.ToSeparated( s, separator );
   }
 
   template <class S, typename SP, class AF>
   S& ToSeparated( S& s, SP separator, AF append ) const
   {
      return m_array.ToSeparated( s, separator, append );
   }
 
   template <class S>
   S& ToCommaSeparated( S& s ) const
   {
      return m_array.ToCommaSeparated( s );
   }
 
   template <class S>
   S& ToSpaceSeparated( S& s ) const
   {
      return m_array.ToSpaceSeparated( s );
   }
 
   template <class S>
   S& ToTabSeparated( S& s ) const
   {
      return m_array.ToTabSeparated( s );
   }
 
   template <class S>
   S& ToNewLineSeparated( S& s ) const
   {
      return m_array.ToNewLineSeparated( s );
   }
 
   uint64 Hash64( uint64 seed = 0 ) const
   {
      return m_array.Hash64( seed );
   }
 
   uint32 Hash32( uint32 seed = 0 ) const
   {
      return m_array.Hash32( seed );
   }
 
   uint64 Hash( uint64 seed = 0 ) const
   {
      return Hash64( seed );
   }
 
   // -------------------------------------------------------------------------
 
private:
 
   array_implementation m_array;
};
 
// ----------------------------------------------------------------------------
 
template <class T, class A, class V> inline
SortedArray<T,A>& operator <<( SortedArray<T,A>& x, const V& v )
{
   x.Add( T( v ) );
   return x;
}
 
template <class T, class A, class V> inline
SortedArray<T,A>& operator <<( SortedArray<T,A>&& x, const V& v )
{
   x.Add( T( v ) );
   return x;
}
 
template <class T, class A> inline
SortedArray<T,A>& operator <<( SortedArray<T,A>& x1, const SortedArray<T,A>& x2 )
{
   x1.Add( x2 );
   return x1;
}
 
template <class T, class A> inline
SortedArray<T,A>& operator <<( SortedArray<T,A>&& x1, const SortedArray<T,A>& x2 )
{
   x1.Add( x2 );
   return x1;
}
 
template <class T, class A> inline
SortedArray<T,A>& operator <<( SortedArray<T,A>& x1, const Array<T,A>& x2 )
{
   x1.Add( x2 );
   return x1;
}
 
template <class T, class A> inline
SortedArray<T,A>& operator <<( SortedArray<T,A>&& x1, const Array<T,A>& x2 )
{
   x1.Add( x2 );
   return x1;
}
 
// ----------------------------------------------------------------------------
 
} // pcl
 
#endif  // __PCL_SortedArray_h
 
// ----------------------------------------------------------------------------
// EOF pcl/SortedArray.h - Released 2025-02-21T12:13:32Z