Array.h

Go to the documentation of this file.

//     ____   ______ __
//    / __ \ / ____// /
//   / /_/ // /    / /
//  / ____// /___ / /___   PixInsight Class Library
// /_/     \____//_____/   PCL 2.6.5
// ----------------------------------------------------------------------------
// pcl/Array.h - Released 2024-01-13T15:47:58Z
// ----------------------------------------------------------------------------
// This file is part of the PixInsight Class Library (PCL).
// PCL is a multiplatform C++ framework for development of PixInsight modules.
//
// Copyright (c) 2003-2024 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_Array_h
#define __PCL_Array_h
 
 
#include <pcl/Defs.h>
#include <pcl/Diagnostics.h>
 
#include <pcl/Allocator.h>
#include <pcl/Container.h>
#include <pcl/Indirect.h>
#include <pcl/Iterator.h>
#include <pcl/Math.h>
#include <pcl/Memory.h>
#include <pcl/ReferenceCounter.h>
#include <pcl/Relational.h>
#include <pcl/Rotate.h>
#include <pcl/Search.h>
#include <pcl/Sort.h>
#include <pcl/StandardAllocator.h>
#include <pcl/Utility.h>
 
namespace pcl
{
 
// ----------------------------------------------------------------------------
 
// ----------------------------------------------------------------------------
 
template <class T, class A = StandardAllocator>
class PCL_CLASS Array : public DirectContainer<T>
{
public:
 
   using block_allocator = A;
 
   using allocator = pcl::Allocator<T,A>;
 
   using iterator = T*;
 
   using const_iterator = const T*;
 
   using reverse_iterator = ReverseRandomAccessIterator<iterator, T>;
 
   using const_reverse_iterator = ReverseRandomAccessIterator<const_iterator, const T>;
 
   // -------------------------------------------------------------------------
 
   Array()
   {
      m_data = new Data;
   }
 
   explicit
   Array( size_type n )
   {
      m_data = new Data;
      m_data->Allocate( n );
      m_data->Initialize( m_data->begin, m_data->end );
   }
 
   Array( size_type n, const T& v )
   {
      m_data = new Data;
      m_data->Allocate( n );
      m_data->Initialize( m_data->begin, m_data->end, v );
   }
 
   template <class FI>
   Array( FI i, FI j )
   {
      m_data = new Data;
      m_data->Allocate( size_type( pcl::Distance( i, j ) ) );
      if ( m_data->begin != nullptr )
         m_data->Build( m_data->begin, i, j );
   }
 
   template <typename T1>
   Array( std::initializer_list<T1> l )
      : Array( l.begin(), l.end() )
   {
   }
 
   Array( const Array& x )
      : m_data( x.m_data )
   {
      if ( m_data != nullptr )
         m_data->Attach();
   }
 
   Array( Array&& x )
      : m_data( x.m_data )
   {
      x.m_data = nullptr;
   }
 
   ~Array()
   {
      if ( m_data != nullptr )
      {
         DetachFromData();
         m_data = nullptr;
      }
   }
 
   bool IsUnique() const noexcept
   {
      return m_data->IsUnique();
   }
 
   bool IsAliasOf( const Array& x ) const noexcept
   {
      return m_data == x.m_data;
   }
 
   void EnsureUnique()
   {
      if ( !IsUnique() )
      {
         Data* newData = new Data;
         newData->Allocate( Length() );
         newData->Build( newData->begin, m_data->begin, m_data->end );
         DetachFromData();
         m_data = newData;
      }
   }
 
   size_type Size() const noexcept
   {
      return m_data->Size();
   }
 
   size_type Length() const noexcept
   {
      return m_data->Length();
   }
 
   size_type Capacity() const noexcept
   {
      return m_data->Capacity();
   }
 
   size_type Available() const noexcept
   {
      return m_data->Available();
   }
 
   bool IsValid() const noexcept
   {
      return m_data != nullptr;
   }
 
   bool IsEmpty() const noexcept
   {
      return m_data->IsEmpty();
   }
 
   size_type LowerBound() const noexcept
   {
      return 0;
   }
 
   size_type UpperBound() const noexcept
   {
      return Length()-1;
   }
 
   const allocator& Allocator() const noexcept
   {
      return m_data->alloc;
   }
 
   void SetAllocator( const allocator& a )
   {
      EnsureUnique();
      m_data->alloc = a;
   }
 
   iterator At( size_type i )
   {
      PCL_PRECONDITION( !IsEmpty() && i < Length() )
      EnsureUnique();
      return m_data->begin + i;
   }
 
   const_iterator At( size_type i ) const noexcept
   {
      PCL_PRECONDITION( !IsEmpty() && i < Length() )
      return m_data->begin + i;
   }
 
   iterator MutableIterator( const_iterator i )
   {
      return At( i - m_data->begin );
   }
 
   T& operator []( size_type i )
   {
      return *At( i );
   }
 
   const T& operator []( size_type i ) const noexcept
   {
      return *At( i );
   }
 
   T& operator *()
   {
      PCL_PRECONDITION( m_data->begin != nullptr )
      EnsureUnique();
      return *m_data->begin;
   }
 
   const T& operator *() const noexcept
   {
      PCL_PRECONDITION( m_data->begin != nullptr )
      return *m_data->begin;
   }
 
   iterator Begin()
   {
      EnsureUnique();
      return m_data->begin;
   }
 
   const_iterator Begin() const noexcept
   {
      return m_data->begin;
   }
 
   const_iterator ConstBegin() const noexcept
   {
      return m_data->begin;
   }
 
   iterator End()
   {
      EnsureUnique();
      return m_data->end;
   }
 
   const_iterator End() const noexcept
   {
      return m_data->end;
   }
 
   const_iterator ConstEnd() const noexcept
   {
      return m_data->end;
   }
 
   reverse_iterator ReverseBegin()
   {
      PCL_PRECONDITION( m_data->end != nullptr )
      EnsureUnique();
      return m_data->end - 1;
   }
 
   const_reverse_iterator ReverseBegin() const noexcept
   {
      PCL_PRECONDITION( m_data->end != nullptr )
      return m_data->end - 1;
   }
 
   const_reverse_iterator ConstReverseBegin() const noexcept
   {
      PCL_PRECONDITION( m_data->end != nullptr )
      return m_data->end - 1;
   }
 
   reverse_iterator ReverseEnd()
   {
      PCL_PRECONDITION( m_data->begin != nullptr )
      EnsureUnique();
      return m_data->begin - 1;
   }
 
   const_reverse_iterator ReverseEnd() const noexcept
   {
      PCL_PRECONDITION( m_data->begin != nullptr )
      return m_data->begin - 1;
   }
 
   const_reverse_iterator ConstReverseEnd() const noexcept
   {
      PCL_PRECONDITION( m_data->begin != nullptr )
      return m_data->begin - 1;
   }
 
   void UniquifyIterator( iterator& i )
   {
      PCL_PRECONDITION( i >= m_data->begin && i <= m_data->end )
      if ( !IsUnique() )
      {
         distance_type d = i - m_data->begin;
         EnsureUnique();
         i = m_data->begin + d;
      }
   }
 
   void UniquifyIterators( iterator& i, iterator& j )
   {
      PCL_PRECONDITION( i >= m_data->begin && i <= m_data->end )
      PCL_PRECONDITION( j >= m_data->begin && j <= m_data->end )
      if ( !IsUnique() )
      {
         distance_type d = i - m_data->begin;
         distance_type r = j - i;
         EnsureUnique();
         j = (i = m_data->begin + d) + r;
      }
   }
 
#ifndef __PCL_NO_STL_COMPATIBLE_ITERATORS
 
   iterator begin()
   {
      return Begin();
   }
 
   const_iterator begin() const noexcept
   {
      return Begin();
   }
 
   iterator end()
   {
      return End();
   }
 
   const_iterator end() const noexcept
   {
      return End();
   }
#endif   // !__PCL_NO_STL_COMPATIBLE_ITERATORS
 
   Array& operator =( const Array& x )
   {
      Assign( x );
      return *this;
   }
 
   void Assign( const Array& x )
   {
      x.m_data->Attach();
      DetachFromData();
      m_data = x.m_data;
   }
 
   Array& operator =( Array&& x )
   {
      Transfer( x );
      return *this;
   }
 
   void Transfer( Array& x )
   {
      DetachFromData();
      m_data = x.m_data;
      x.m_data = nullptr;
   }
 
   void Transfer( Array&& x )
   {
      DetachFromData();
      m_data = x.m_data;
      x.m_data = nullptr;
   }
 
   void Assign( const T& v, size_type n = 1 )
   {
      if ( n > 0 )
      {
         if ( !IsUnique() )
         {
            Data* newData = new Data;
            DetachFromData();
            m_data = newData;
         }
 
         if ( Capacity() < n )
         {
            m_data->Deallocate();
            m_data->Allocate( n );
         }
         else
         {
            m_data->Destroy( m_data->begin, m_data->end );
            m_data->end = m_data->begin + n;
         }
 
         m_data->Initialize( m_data->begin, m_data->end, v );
      }
      else
         Clear();
   }
 
   template <class FI>
   void Assign( FI i, FI j )
   {
      size_type n = size_type( pcl::Distance( i, j ) );
      if ( n > 0 )
      {
         if ( !IsUnique() )
         {
            Data* newData = new Data;
            DetachFromData();
            m_data = newData;
         }
 
         if ( Capacity() < n )
         {
            m_data->Deallocate();
            m_data->Allocate( n );
         }
         else
         {
            m_data->Destroy( m_data->begin, m_data->end );
            m_data->end = m_data->begin + n;
         }
 
         m_data->Build( m_data->begin, i, j );
      }
      else
         Clear();
   }
 
   void Import( iterator i, iterator j )
   {
      if ( i >= m_data->available || j <= m_data->begin )
      {
         Clear();
         size_type n = size_type( pcl::Distance( i, j ) );
         if ( n > 0 )
         {
            EnsureUnique();
            m_data->begin = i;
            m_data->end = m_data->available = j;
         }
      }
   }
 
   iterator Release()
   {
      EnsureUnique();
      iterator b = m_data->begin;
      m_data->begin = m_data->end = m_data->available = nullptr;
      return b;
   }
 
   iterator Grow( iterator i, size_type n = 1 )
   {
      i = pcl::Range( i, m_data->begin, m_data->end );
      if ( n > 0 )
      {
         UniquifyIterator( i );
         m_data->Initialize( i = m_data->UninitializedGrow( i, n ), n );
      }
      return i;
   }
 
   iterator Expand( size_type n = 1 )
   {
      return Grow( m_data->end, n );
   }
 
   void Shrink( size_type n = 1 )
   {
      if ( n < m_data->Length() )
         Truncate( m_data->end - n );
      else
         Clear();
   }
 
   void Resize( size_type n )
   {
      size_type l = m_data->Length();
      if ( n > l )
         Expand( n - l );
      else
         Shrink( l - n );
   }
 
   iterator Insert( iterator i, const Array& x )
   {
      if ( &x != this )
         return Insert( i, x.Begin(), x.End() );
      Array t( *this );
      t.EnsureUnique();
      return Insert( i, t.m_data->begin, t.m_data->end );
   }
 
   iterator Insert( iterator i, const T& v, size_type n = 1 )
   {
      i = pcl::Range( i, m_data->begin, m_data->end );
      if ( n > 0 )
      {
         UniquifyIterator( i );
         m_data->Initialize( i = m_data->UninitializedGrow( i, n ), n, v );
      }
      return i;
   }
 
   template <class FI>
   iterator Insert( iterator i, FI p, FI q )
   {
      i = pcl::Range( i, m_data->begin, m_data->end );
      size_type n = size_type( pcl::Distance( p, q ) );
      if ( n > 0 )
      {
         UniquifyIterator( i );
         m_data->Build( i = m_data->UninitializedGrow( i, n ), p, q );
      }
      return i;
   }
 
   void Append( const Array& x )
   {
      Insert( m_data->end, x );
   }
 
   void Append( const T& v, size_type n = 1 )
   {
      Insert( m_data->end, v, n );
   }
 
   template <class FI>
   void Append( FI p, FI q )
   {
      Insert( m_data->end, p, q );
   }
 
   void Prepend( const Array& x )
   {
      Insert( m_data->begin, x );
   }
 
   void Prepend( const T& v, size_type n = 1 )
   {
      Insert( m_data->begin, v, n );
   }
 
   template <class FI>
   void Prepend( FI p, FI q )
   {
      Insert( m_data->begin, p, q );
   }
 
   void Add( const Array& x )
   {
      Append( x );
   }
 
   void Add( const T& v, size_type n = 1 )
   {
      Append( v, n );
   }
 
   template <class FI>
   void Add( FI p, FI q )
   {
      Append( p, q );
   }
 
   void Remove( iterator i, size_type n = 1 )
   {
      Remove( i, i+n );
   }
 
   void Remove( iterator i, iterator j )
   {
      if ( i < m_data->end )
         if ( i < j )
         {
            i = pcl::Max( m_data->begin, i );
            j = pcl::Min( j, m_data->end );
            if ( i > m_data->begin || j < m_data->end )
            {
               UniquifyIterators( i, j );
               m_data->Destroy( j = pcl::Copy( i, j, m_data->end ), m_data->end );
               m_data->end = j;
            }
            else
               Clear();
         }
   }
 
   void Truncate( iterator i )
   {
      Remove( i, m_data->end );
   }
 
   void Remove( const T& v )
   {
      Array a;
      for ( iterator i = m_data->begin, j = i; ; ++j )
      {
         if ( j == m_data->end )
         {
            if ( i != m_data->begin )
            {
               a.Add( i, j );
               Transfer( a );
            }
            break;
         }
 
         if ( *j == v )
         {
            a.Add( i, j );
            i = j;
            ++i;
         }
      }
   }
 
   template <class BP>
   void Remove( const T& v, BP p )
   {
      Array a;
      for ( iterator i = m_data->begin, j = i; ; ++j )
      {
         if ( j == m_data->end )
         {
            if ( i != m_data->begin )
            {
               a.Add( i, j );
               Transfer( a );
            }
            break;
         }
 
         if ( p( *j, v ) )
         {
            a.Add( i, j );
            i = j;
            ++i;
         }
      }
   }
 
   void Clear()
   {
      if ( !IsEmpty() )
         if ( IsUnique() )
            m_data->Deallocate();
         else
         {
            Data* newData = new Data;
            DetachFromData();
            m_data = newData;
         }
   }
 
   iterator Replace( iterator i, iterator j, const Array& x )
   {
      if ( &x != this )
         return Replace( i, j, x.Begin(), x.End() );
      Array t( *this );
      t.EnsureUnique();
      return Replace( i, j, t.ConstBegin(), t.ConstEnd() );
   }
 
   iterator Replace( iterator i, iterator j, const T& v, size_type n = 1 )
   {
      i = pcl::Range( i, m_data->begin, m_data->end );
      j = pcl::Range( j, m_data->begin, m_data->end );
      if ( i < j )
         if ( i < m_data->end )
         {
            UniquifyIterators( i, j );
            size_type d = size_type( j - i );
            if ( d < n )
            {
               m_data->Destroy( i, j );
               m_data->Initialize( i = m_data->UninitializedGrow( i, n-d ), n, v );
            }
            else
            {
               iterator k = i + n;
               pcl::Fill( i, k, v );
               Remove( k, j );
               if ( m_data->begin == nullptr )
                  i = nullptr;
            }
         }
      return i;
   }
 
   template <class FI>
   iterator Replace( iterator i, iterator j, FI p, FI q )
   {
      i = pcl::Range( i, m_data->begin, m_data->end );
      j = pcl::Range( j, m_data->begin, m_data->end );
      if ( i < j )
         if ( i < m_data->end )
         {
            UniquifyIterators( i, j );
            size_type d = size_type( j - i );
            size_type n = size_type( pcl::Distance( p, q ) );
            if ( d < n )
            {
               m_data->Destroy( i, j );
               m_data->Build( i = m_data->UninitializedGrow( i, n-d ), p, q );
            }
            else
            {
               Remove( pcl::Move( i, p, q ), j );
               if ( m_data->begin == nullptr )
                  i = nullptr;
            }
         }
      return i;
   }
 
   void Reserve( size_type n )
   {
      if ( n > 0 )
         if ( IsUnique() )
         {
            if ( Capacity() < n )
            {
               iterator b = m_data->alloc.Allocate( n );
               iterator e = m_data->Build( b, m_data->begin, m_data->end );
               m_data->Deallocate();
               m_data->begin = b;
               m_data->end = e;
               m_data->available = m_data->begin + n;
            }
         }
         else
         {
            Data* newData = new Data;
            newData->begin = newData->alloc.Allocate( n = pcl::Max( Length(), n ) );
            newData->end = newData->Build( newData->begin, m_data->begin, m_data->end );
            newData->available = newData->begin + n;
            DetachFromData();
            m_data = newData;
         }
   }
 
   void Squeeze()
   {
      if ( IsUnique() )
      {
         if ( Available() > 0 )
         {
            iterator b = m_data->alloc.Allocate( Length() );
            iterator e = m_data->Build( b, m_data->begin, m_data->end );
            m_data->Deallocate();
            m_data->begin = b;
            m_data->end = m_data->available = e;
         }
      }
      else
      {
         Data* newData = new Data;
         if ( !IsEmpty() )
         {
            newData->begin = newData->alloc.Allocate( Length() );
            newData->available = newData->end = newData->Build( newData->begin, m_data->begin, m_data->end );
         }
         DetachFromData();
         m_data = newData;
      }
   }
 
   void Fill( const T& v )
   {
      EnsureUnique();
      pcl::Fill( m_data->begin, m_data->end, v );
   }
 
   void SecureFill( const T& v )
   {
      pcl::Fill( m_data->begin, m_data->end, v );
   }
 
   template <class F>
   void Apply( F f )
   {
      EnsureUnique();
      pcl::Apply( m_data->begin, m_data->end, f );
   }
 
   template <class F>
   void Apply( F f ) const noexcept( noexcept( f ) )
   {
      pcl::Apply( m_data->begin, m_data->end, f );
   }
 
   template <class F>
   iterator FirstThat( F f ) const noexcept( noexcept( f ) )
   {
      return const_cast<iterator>( pcl::FirstThat( m_data->begin, m_data->end, f ) );
   }
 
   template <class F>
   iterator LastThat( F f ) const noexcept( noexcept( f ) )
   {
      return const_cast<iterator>( pcl::LastThat( m_data->begin, m_data->end, f ) );
   }
 
   size_type Count( const T& v ) const noexcept
   {
      return pcl::Count( m_data->begin, m_data->end, v );
   }
 
   template <class BP>
   size_type Count( const T& v, BP p ) const noexcept( noexcept( p ) )
   {
      return pcl::Count( m_data->begin, m_data->end, v, p );
   }
 
   template <class UP>
   size_type CountIf( UP p ) const noexcept( noexcept( p ) )
   {
      return pcl::CountIf( m_data->begin, m_data->end, p );
   }
 
   iterator MinItem() const noexcept
   {
      return const_cast<iterator>( pcl::MinItem( m_data->begin, m_data->end ) );
   }
 
   template <class BP>
   iterator MinItem( BP p ) const noexcept( noexcept( p ) )
   {
      return const_cast<iterator>( pcl::MinItem( m_data->begin, m_data->end, p ) );
   }
 
   iterator MaxItem() const noexcept
   {
      return const_cast<iterator>( pcl::MaxItem( m_data->begin, m_data->end ) );
   }
 
   template <class BP>
   iterator MaxItem( BP p ) const noexcept( noexcept( p ) )
   {
      return const_cast<iterator>( pcl::MaxItem( m_data->begin, m_data->end, p ) );
   }
 
   void Reverse()
   {
      EnsureUnique();
      pcl::Reverse( m_data->begin, m_data->end );
   }
 
   void Rotate( distance_type n )
   {
      if ( Length() > 1 && n != 0 )
      {
         EnsureUnique();
         if ( (n %= Length()) < 0 )
            n += Length();
         pcl::Rotate( m_data->begin, m_data->begin+n, m_data->end );
      }
   }
 
   void ShiftLeft( const T& v, size_type n = 1 )
   {
      if ( !IsEmpty() && n > 0 )
      {
         EnsureUnique();
         if ( n >= Length() )
            pcl::Fill( m_data->begin, m_data->end, v );
         else
            pcl::ShiftLeft( m_data->begin, m_data->begin+n, m_data->end, v );
      }
   }
 
   void ShiftRight( const T& v, size_type n = 1 )
   {
      if ( !IsEmpty() && n > 0 )
      {
         EnsureUnique();
         if ( n >= Length() )
            pcl::Fill( m_data->begin, m_data->end, v );
         else
            pcl::ShiftRight( m_data->begin, m_data->end-n, m_data->end, v );
      }
   }
 
   iterator Search( const T& v ) const noexcept
   {
      return const_cast<iterator>( pcl::LinearSearch( m_data->begin, m_data->end, v ) );
   }
 
   template <class BP>
   iterator Search( const T& v, BP p ) const noexcept( noexcept( p ) )
   {
      return const_cast<iterator>( pcl::LinearSearch( m_data->begin, m_data->end, v, p ) );
   }
 
   iterator SearchLast( const T& v ) const noexcept
   {
      return const_cast<iterator>( pcl::LinearSearchLast( m_data->begin, m_data->end, v ) );
   }
 
   template <class BP>
   iterator SearchLast( const T& v, BP p ) const noexcept( noexcept( p ) )
   {
      return const_cast<iterator>( pcl::LinearSearchLast( m_data->begin, m_data->end, v, p ) );
   }
 
   template <class FI>
   iterator SearchSubset( FI i, FI j ) const noexcept
   {
      return const_cast<iterator>( pcl::Search( m_data->begin, m_data->end, i, j ) );
   }
 
   template <class FI, class BP>
   iterator SearchSubset( FI i, FI j, BP p ) const noexcept( noexcept( p ) )
   {
      return const_cast<iterator>( pcl::Search( m_data->begin, m_data->end, i, j, p ) );
   }
 
   template <class C>
   iterator SearchSubset( const C& x ) const noexcept
   {
      PCL_ASSERT_DIRECT_CONTAINER( C, T );
      return const_cast<iterator>( pcl::Search( m_data->begin, m_data->end, x.Begin(), x.End() ) );
   }
 
   template <class C, class BP>
   iterator SearchSubset( const C& x, BP p ) const noexcept( noexcept( p ) )
   {
      PCL_ASSERT_DIRECT_CONTAINER( C, T );
      return const_cast<iterator>( pcl::Search( m_data->begin, m_data->end, x.Begin(), x.End(), p ) );
   }
 
   template <class BI>
   iterator SearchLastSubset( BI i, BI j ) const noexcept
   {
      return const_cast<iterator>( pcl::SearchLast( m_data->begin, m_data->end, i, j ) );
   }
 
   template <class BI, class BP>
   iterator SearchLastSubset( BI i, BI j, BP p ) const noexcept( noexcept( p ) )
   {
      return const_cast<iterator>( pcl::SearchLast( m_data->begin, m_data->end, i, j, p ) );
   }
 
   template <class C>
   iterator SearchLastSubset( const C& x ) const noexcept
   {
      PCL_ASSERT_DIRECT_CONTAINER( C, T );
      return const_cast<iterator>( pcl::SearchLast( m_data->begin, m_data->end, x.Begin(), x.End() ) );
   }
 
   template <class C, class BP>
   iterator SearchLastSubset( const C& x, BP p ) const noexcept( noexcept( p ) )
   {
      PCL_ASSERT_DIRECT_CONTAINER( C, T );
      return const_cast<iterator>( pcl::SearchLast( m_data->begin, m_data->end, x.Begin(), x.End(), p ) );
   }
 
   bool Contains( const T& v ) const noexcept
   {
      return Search( v ) != m_data->end;
   }
 
   template <class BP>
   bool Contains( const T& v, BP p ) const noexcept( noexcept( p ) )
   {
      return Search( v, p ) != m_data->end;
   }
 
   template <class FI>
   iterator ContainsSubset( FI i, FI j ) const noexcept
   {
      return SearchSubset( i, j ) != m_data->end;
   }
 
   template <class FI, class BP>
   iterator ContainsSubset( FI i, FI j, BP p ) const noexcept( noexcept( p ) )
   {
      return SearchSubset( i, j, p ) != m_data->end;
   }
 
   template <class C>
   iterator ContainsSubset( const C& c ) const noexcept
   {
      return SearchSubset( c ) != m_data->end;
   }
 
   template <class C, class BP>
   iterator ContainsSubset( const C& c, BP p ) const noexcept( noexcept( p ) )
   {
      return SearchSubset( c, p ) != m_data->end;
   }
 
   void Sort()
   {
      EnsureUnique();
      pcl::QuickSort( m_data->begin, m_data->end );
   }
 
   template <class BP>
   void Sort( BP p )
   {
      EnsureUnique();
      pcl::QuickSort( m_data->begin, m_data->end, p );
   }
 
   friend void Swap( Array& x1, Array& x2 ) noexcept
   {
      pcl::Swap( x1.m_data, x2.m_data );
   }
 
   template <class S, typename SP>
   S& ToSeparated( S& s, SP separator ) const
   {
      const_iterator i = m_data->begin;
      if ( i < m_data->end )
      {
         s.Append( S( *i ) );
         if ( ++i < m_data->end )
            do
            {
               s.Append( separator );
               s.Append( S( *i ) );
            }
            while ( ++i < m_data->end );
      }
      return s;
   }
 
   template <class S, typename SP, class AF>
   S& ToSeparated( S& s, SP separator, AF append ) const
   {
      const_iterator i = m_data->begin;
      if ( i < m_data->end )
      {
         append( s, S( *i ) );
         if ( ++i < m_data->end )
         {
            S p( separator );
            do
            {
               append( s, p );
               append( s, S( *i ) );
            }
            while ( ++i < m_data->end );
         }
      }
      return s;
   }
 
   template <class S>
   S& ToCommaSeparated( S& s ) const
   {
      return ToSeparated( s, ',' );
   }
 
   template <class S>
   S& ToSpaceSeparated( S& s ) const
   {
      return ToSeparated( s, ' ' );
   }
 
   template <class S>
   S& ToTabSeparated( S& s ) const
   {
      return ToSeparated( s, '\t' );
   }
 
   template <class S>
   S& ToNewLineSeparated( S& s ) const
   {
      return ToSeparated( s, '\n' );
   }
 
   uint64 Hash64( uint64 seed = 0 ) const
   {
      return pcl::Hash64( m_data->begin, m_data->Size(), seed );
   }
 
   uint32 Hash32( uint32 seed = 0 ) const noexcept
   {
      return pcl::Hash32( m_data->begin, m_data->Size(), seed );
   }
 
   uint64 Hash( uint64 seed = 0 ) const noexcept
   {
      return Hash64( seed );
   }
 
   // -------------------------------------------------------------------------
 
private:
 
   struct Data : public ReferenceCounter
   {
      iterator  begin     = nullptr; 
      iterator  end       = nullptr; 
      iterator  available = nullptr; 
      allocator alloc;               
 
      Data() = default;
 
      ~Data()
      {
         Deallocate();
      }
 
      size_type Size() const noexcept
      {
         return Length()*sizeof( T );
      }
 
      size_type Length() const noexcept
      {
         return end - begin;
      }
 
      size_type Capacity() const noexcept
      {
         return available - begin;
      }
 
      size_type Available() const noexcept
      {
         return available - end;
      }
 
      bool IsEmpty() const noexcept
      {
         return begin == end;
      }
 
      void Allocate( size_type n )
      {
         if ( n > 0 )
         {
            size_type m = alloc.PagedLength( n );
            begin = alloc.Allocate( m );
            end = begin + n;
            available = begin + m;
         }
      }
 
      void Deallocate()
      {
         PCL_CHECK( (begin == nullptr) ? end == nullptr : begin < end )
         if ( begin != nullptr )
         {
            Destroy( begin, end );
            alloc.Deallocate( begin );
            begin = end = available = nullptr;
         }
      }
 
      void Initialize( iterator __restrict__ i, iterator __restrict__ j )
      {
         for ( ; i < j; ++i )
            pcl::Construct( i, alloc );
      }
 
      void Initialize( iterator __restrict__ i, size_type n )
      {
         for ( ; n > 0; ++i, --n )
            pcl::Construct( i, alloc );
      }
 
      void Initialize( iterator __restrict__ i, iterator __restrict__ j, const T& v )
      {
         for ( ; i < j; ++i )
            pcl::Construct( i, v, alloc );
      }
 
      void Initialize( iterator __restrict__ i, size_type n, const T& v )
      {
         for ( ; n > 0; ++i, --n )
            pcl::Construct( i, v, alloc );
      }
 
      template <class FI>
      iterator Build( iterator __restrict__ i, FI p, FI q )
      {
         for ( ; p != q; ++i, ++p )
            pcl::Construct( i, *p, alloc );
         return i;
      }
 
      iterator UninitializedGrow( iterator __restrict__ i, size_type n )
      {
         if ( n > 0 )
            if ( Available() >= n )
            {
               if ( i < end )
               {
                  iterator __restrict__ j1 = end;
                  iterator __restrict__ j2 = end + n;
 
                  for ( ;; )
                  {
                     pcl::Construct( --j2, *--j1, alloc );
 
                     if ( j1 == i )
                     {
                        j2 = end;
                        break;
                     }
                     else if ( j2 == end )
                     {
                        do
                           *--j2 = *--j1;
                        while ( j1 > i );
                        break;
                     }
                  }
 
                  Destroy( i, j2 );
               }
               end += n;
            }
            else
            {
               size_type m = alloc.PagedLength( Length()+n );
               iterator b = alloc.Allocate( m );
               iterator r = Build( b, begin, i );
               iterator e = Build( r+n, i, end );
 
               Deallocate();
               begin = b;
               end = e;
               available = b + m;
               i = r;
            }
 
         return i;
      }
 
      static void Destroy( iterator i, iterator j )
      {
         pcl::Destroy( i, j );
      }
   };
 
   Data* m_data = nullptr;
 
   void DetachFromData()
   {
      if ( !m_data->Detach() )
         delete m_data;
   }
};
 
// ----------------------------------------------------------------------------
 
template <class T, class A> inline
bool operator ==( const Array<T,A>& x1, const Array<T,A>& x2 ) noexcept
{
   return x1.Length() == x2.Length() && pcl::Equal( x1.Begin(), x2.Begin(), x2.End() );
}
 
template <class T, class A> inline
bool operator <( const Array<T,A>& x1, const Array<T,A>& x2 ) noexcept
{
   return pcl::Compare( x1.Begin(), x1.End(), x2.Begin(), x2.End() ) < 0;
}
 
template <class T, class A, class V> inline
Array<T,A>& operator <<( Array<T,A>& x, const V& v )
{
   x.Append( T( v ) );
   return x;
}
 
template <class T, class A, class V> inline
Array<T,A>& operator <<( Array<T,A>&& x, const V& v )
{
   x.Append( T( v ) );
   return x;
}
 
template <class T, class A> inline
Array<T,A>& operator <<( Array<T,A>& x1, const Array<T,A>& x2 )
{
   x1.Append( x2 );
   return x1;
}
 
template <class T, class A> inline
Array<T,A>& operator <<( Array<T,A>&& x1, const Array<T,A>& x2 )
{
   x1.Append( x2 );
   return x1;
}
 
// ----------------------------------------------------------------------------
 
} // pcl
 
#endif  // __PCL_Array_h
 
// ----------------------------------------------------------------------------
// EOF pcl/Array.h - Released 2024-01-13T15:47:58Z