permutation.hpp

Go to the documentation of this file.

/*
 * $Id: permutation.hpp 315 2014-02-22 14:31:35Z jdl3 $
 * Copyright (C) 2010, 2011, 2012, 2014, 2024 John D Lamb
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or (at
 * your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */
 
#ifndef CCGSL_PERMUTATION_HPP
#define CCGSL_PERMUTATION_HPP
 
#include<cstddef>
#include<new>
#include<algorithm>
#include<gsl/gsl_permutation.h>
#include"exception.hpp"
 
namespace gsl {
  class permutation {
  public:
    permutation(){
      ccgsl_pointer = 0;
      count = 0; // initially nullptr will do
    }
    explicit permutation( size_t const n, bool init = false ){
      ccgsl_pointer = gsl_permutation_alloc( n );
      // just plausibly we could allocate permutation but not count
      try { count = new size_t; } catch( std::bad_alloc& e ){
    // try to tidy up before rethrowing
    gsl_permutation_free( ccgsl_pointer );
    throw e;
      }
      *count = 1; // initially there is just one reference to ccgsl_pointer
      if( init ) this->init();
    }
    explicit permutation( gsl_permutation* v ){
      ccgsl_pointer = v;
      // just plausibly we could fail to allocate count: no further action needed.
      count = new size_t;
      *count = 1; // initially there is just one reference to ccgsl_pointer
    }
    // copy constructor
    permutation( permutation const& v ) : ccgsl_pointer( v.ccgsl_pointer ), count( v.count ){
      if( count != 0 ) ++*count; // permutation is now shared.
    }
    // assignment operator
    permutation& operator=( permutation const& v ){
      // first, possibly delete anything pointed to by this
      if( count == 0 or --*count == 0 ){
    if( ccgsl_pointer != 0 ) gsl_permutation_free( ccgsl_pointer );
    delete count;
      }
      // Then copy
      ccgsl_pointer = v.ccgsl_pointer;
      count = v.count;
      if( count != 0 ) ++*count; // permutation is now shared.
      return *this;
    }
    // clone()
    permutation clone() const {
      permutation copy( get()->size );
      // Now copy
      gsl_permutation_memcpy( copy.get(), get() );
      // return new object
      return copy;
    }
    // destructor
    ~permutation(){
      if( count == 0 or --*count == 0 ){
    // could have allocated null pointer
    if( ccgsl_pointer != 0 ) gsl_permutation_free( ccgsl_pointer );
    delete count;
      }
    }
#ifdef __GXX_EXPERIMENTAL_CXX0X__
    permutation( permutation&& v ) : ccgsl_pointer( v.ccgsl_pointer ), count( nullptr ){
      std::swap( count, v.count );
      v.ccgsl_pointer = nullptr;
    }
    permutation& operator=( permutation&& v ){
      std::swap( ccgsl_pointer, v.ccgsl_pointer );
      std::swap( count, v.count );
      return *this;
    }
#endif
  private:
    gsl_permutation* ccgsl_pointer;
    size_t* count;
  public:
    // shared reference functions
    gsl_permutation* get(){ return ccgsl_pointer; }
    gsl_permutation const* get() const { return ccgsl_pointer; }
    bool unique() const { return count != 0 and *count == 1; }
    size_t use_count() const { return count == 0 ? 0 : *count; }
#ifdef __GXX_EXPERIMENTAL_CXX0X__
    explicit
#endif
    operator bool() const { return ccgsl_pointer != 0; }
  public:
    // GSL functions
    static permutation calloc( size_t const n ){ return permutation( gsl_permutation_calloc( n ) ); }
    void init(){ gsl_permutation_init( get() ); }
    int memcpy( permutation const& src ){ return gsl_permutation_memcpy( get(), src.get() ); }
    int fread( FILE* stream ){ return gsl_permutation_fread( stream, get() ); }
    int fwrite( FILE* stream ) const { return gsl_permutation_fwrite( stream, get() ); }
    int fscanf( FILE* stream ){ return gsl_permutation_fscanf( stream, get() ); }
    int fprintf( FILE* stream, char const* format ) const {
      return gsl_permutation_fprintf( stream, get(), format ); }
    size_t size() const { return gsl_permutation_size( get() ); }
    size_t* data() const { return gsl_permutation_data( get() ); }
    int swap( size_t const i, size_t const j ){ return gsl_permutation_swap( get(), i, j ); }
    int valid() const { return gsl_permutation_valid( get() ); }
    void reverse(){ gsl_permutation_reverse( get() ); }
    int inverse( permutation const& p ){ return gsl_permutation_inverse( get(), p.get() ); }
    int next(){ return gsl_permutation_next( get() ); }
    int prev(){ return gsl_permutation_prev( get() ); }
    int mul( permutation const& pa, permutation const& pb ){
      return gsl_permutation_mul( get(), pa.get(), pb.get() ); }
 
    int linear_to_canonical( permutation const& p ){
      return gsl_permutation_linear_to_canonical( get(), p.get() ); }
    int canonical_to_linear( permutation const& q ){
      return gsl_permutation_canonical_to_linear( get(), q.get() ); }
    size_t inversions() const { return gsl_permutation_inversions( get() ); }
    size_t linear_cycles() const { return gsl_permutation_linear_cycles( get() ); }
    size_t canonical_cycles(  ) const { return gsl_permutation_canonical_cycles( get() ); }
    size_t get( size_t const i ) const { return gsl_permutation_get( get(), i ); }
    size_t operator[]( size_t const i ) const { return gsl_permutation_get( get(), i ); }
  private:
    template<typename container, typename content, bool reverse> class iterator_base {
      friend class permutation;
    public:
      typedef std::random_access_iterator_tag iterator_category;
      typedef size_t value_type;
      typedef value_type* pointer;
      typedef value_type& reference;
      // // type iterator_traits<permutation>::difference_type
      typedef ptrdiff_t difference_type;
    public:
      // // operator*
      reference operator*() const {
    // Always try to return something
    static content something = 0;
    // First check that iterator is initialised.
    if( v == 0 ){
      gsl_error( "iterator not initialised", __FILE__, __LINE__, exception::GSL_EFAULT );
      return something;
    } else if( v->ccgsl_pointer == 0 ){
      gsl_error( "permutation not initialised", __FILE__, __LINE__, exception::GSL_EFAULT );
      return something;
    }
    // Check that position make sense
    if( position >= static_cast<difference_type>( v->size() ) ){
      gsl_error( "trying to dereference beyond rbegin()", __FILE__, __LINE__, exception::GSL_EFAILED );
      return something;
    }
    if( position <= -1 ){
      gsl_error( "trying to dereference beyond begin()", __FILE__, __LINE__, exception::GSL_EFAILED );
      return something;
    }
    // position and v are valid: return data
    return *(v->ccgsl_pointer->data + position);
      }
      // // operator->
      pointer operator->() const {
    // First check that iterator is initialised.
    if( v == 0 ){
      gsl_error( "iterator not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return 0;
    } else if( v->ccgsl_pointer == 0 ){
      gsl_error( "permutation not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return 0;
    }
    // Check that position make sense
    if( position >= static_cast<difference_type>( v->size() ) ){
      gsl_error( "trying to dereference end()", __FILE__, __LINE__, exception::GSL_EFAILED );
      return 0;
    }
    if( position <= -1 ){
      gsl_error( "trying to dereference rend()", __FILE__, __LINE__, exception::GSL_EFAILED );
      return 0;
    }
    // position and v are valid: return data
    return *(v->ccgsl_pointer->data + position);
      }
      // // operator[]
      reference operator[]( difference_type const n ) const {
    // Always try to return something
    static content something = 0;
    // First check that iterator is initialised.
    if( v == 0 ){
      gsl_error( "iterator not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return something;
    } else if( v->ccgsl_pointer == 0 ){
      gsl_error( "permutation not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return something;
    }
    // Check that position make sense
    difference_type const p = reverse ? position - n : position + n;
    if( p >= static_cast<difference_type>( v->size() ) ){
      gsl_error( "trying to dereference beyond rbegin()", __FILE__, __LINE__, exception::GSL_EFAILED );
      return something;
    }
    if( p <= -1 ){
      gsl_error( "trying to dereference beyond begin()", __FILE__, __LINE__, exception::GSL_EFAILED );
      return something;
    }
    // p is a valid position
    return *(v->ccgsl_pointer->data + p );
      }
      // // operator-: find distance between two iterators
      difference_type operator-( iterator_base<container,content,reverse> const& i ) const {
    // Warn if either iterator undefined
    if( v == 0 or i.v == 0 ){
      gsl_error( "iterator not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return 0;
    } else if( v->ccgsl_pointer == 0 or i.v->ccgsl_pointer == 0 ){
      gsl_error( "permutation not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return 0;
    }
    // Warn if iterators do not point to same permutation
    if( v->ccgsl_pointer != i.v->ccgsl_pointer ){
      gsl_error( "trying to take difference of iterators for different permutations", __FILE__, __LINE__,
             exception::GSL_EFAILED );
      return 0;
    }
    return reverse ? i.position - position : position - i.position;
      }
      // // operator!=
      // // operator<
      bool operator==( iterator_base<container,content,reverse> const& i ) const {
    return this->v == i.v and this->position == i.position;
      }
      bool operator!=( iterator_base<container,content,reverse> const& i ) const {
    return not this->operator==( i );
      }
      bool operator<( iterator_base<container,content,reverse> const& i ) const {
    // Warn if either iterator undefined
    if( v == 0 or i.v == 0 ){
      gsl_error( "iterator not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return false;
    }
    // Warn if iterators do not point to same permutation
    if( v->ccgsl_pointer != i.v->ccgsl_pointer ){
      gsl_error( "trying to take difference of iterators for different permutations", __FILE__, __LINE__,
             exception::GSL_EFAILED );
      return false;
    }
    return reverse ? i.position < position : position < i.position;
      }
    protected:
      void increment(){
    // Only makes sense if v points to a permutation
    if( v == 0 ){
      gsl_error( "iterator not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return;
    } else if( v->ccgsl_pointer == 0 ){
      gsl_error( "permutation not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return;
    }
    // increment position and check against size
    if( reverse ){ if( position >= 0 ) --position; }
    else { if( position < static_cast<difference_type>( v->size() ) ) ++position; }
      }
      void decrement(){
    // Only makes sense if v points to a permutation
    if( v == 0 ){
      gsl_error( "iterator not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return;
    } else if( v->ccgsl_pointer == 0 ){
      gsl_error( "permutation not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return;
    }
    // decrement position and check against size
    if( reverse ){ if( position < static_cast<difference_type>( v->size() ) ) ++position; }
    else { if( position >= 0 ) --position; }
      }
      void shift( difference_type const n ){
    // Warn if iterator undefined
    if( v == 0 ){
      gsl_error( "iterator not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return;
    } else if( v->ccgsl_pointer == 0 ){
      gsl_error( "permutation not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return;
    }
    position += reverse ? -n : n;
      }
      iterator_base(){ v = 0; }
      iterator_base( container* v, difference_type position )
    : v( v ), position( position ){}
      container* v;
      difference_type position;
    };
    template<bool reverse> class const_iterator_t
      : public iterator_base<permutation const,unsigned long,reverse>{
    public:
      // // Refines output iterator
      // // operator=
      const_iterator_t<reverse>& operator=( const_iterator_t<reverse> const& i ){
    iterator_base<permutation const,unsigned long,reverse>::v = i.v;
    iterator_base<permutation const,unsigned long,reverse>::position = i.position;
    return *this;
      }
      // // Refines forward iterator
      // // operator++ (both)
      const_iterator_t<reverse>& operator++(){
    iterator_base<permutation const,unsigned long,reverse>::increment();
    return *this;
      }
      const_iterator_t<reverse> operator++( int ){
    // return value
    const_iterator_t<reverse> result( *this );
    iterator_base<permutation const,unsigned long,reverse>::increment();
    return result;
      }
      // // Refines bidirectional iterator
      // // operator-- (both)
      const_iterator_t<reverse>& operator--(){
    iterator_base<permutation const,unsigned long,reverse>::decrement();
    return *this;
      }
      const_iterator_t<reverse> operator--( int ){
    // return value
    const_iterator_t<reverse> result( *this );
    iterator_base<permutation const,unsigned long,reverse>::decrement();
    return result;
      }
      typedef typename iterator_base<permutation const,unsigned long,reverse>::difference_type
    difference_type;
      // // operator+=
      const_iterator_t<reverse>& operator+=( difference_type const n ){
    this->shift( n );
    return *this;
      }
      // // operator-=
      const_iterator_t<reverse>& operator-=( difference_type const n ){
    this->shift( -n );
    return *this;
      }
      // // operator+ (n+i)(i+n)
      const_iterator_t<reverse> operator+( difference_type const n ) const {
    const_iterator_t<reverse> result( *this );
    result += n;
    return result;
      }
      // // operator- (n-i)(i-n)(i-j)
      const_iterator_t<reverse> operator-( difference_type const n ) const {
    const_iterator_t<reverse> result( *this );
    result -= n;
    return result;
      }
      difference_type operator-( const_iterator_t<reverse> const& i ) const {
    return iterator_base<permutation const,unsigned long,reverse>::operator-( i );
      }
      const_iterator_t() : iterator_base<permutation,unsigned long,reverse>(){}
      const_iterator_t( const_iterator_t<reverse> const&i ){
    const_iterator_t<reverse>::v = i.v;
    const_iterator_t<reverse>::position = i.position;
      }
      bool operator==( const_iterator_t<reverse> const& i ) const {
        return this->v == i.v and this->position == i.position;
      }
      bool operator!=( const_iterator_t<reverse> const& i ) const {
        return not this->operator==( i );
      }
      bool operator<( const_iterator_t<reverse> const& i ) const {
    // Warn if either iterator undefined
    if( this->v == 0 or i.v == 0 ){
      gsl_error( "iterator not initialised", __FILE__, __LINE__, exception::GSL_EFAILED );
      return false;
    }
    // Warn if iterators do not point to same permutation
    if( this->v->ccgsl_pointer != i.v->ccgsl_pointer ){
      gsl_error( "trying to take difference of iterators for different permutations", __FILE__, __LINE__,
             exception::GSL_EFAILED );
      return false;
    }
    return reverse ? i.position < this->position : this->position < i.position;
      }
    protected:
      // We need a constructor for permutation
      friend class permutation;
      const_iterator_t( permutation const* v, difference_type position )
      : iterator_base<permutation const,unsigned long,reverse>( v, position ){}
    };
  public:
    typedef const_iterator_t<false> const_iterator;
    typedef const_iterator_t<true> const_reverse_iterator;
    // type difference_type
    typedef const_iterator::difference_type difference_type;
    // type size_type
    typedef size_t size_type;
    // begin()
    const_iterator begin() const {
      return const_iterator( this, 0 );
    }
    // end()
    const_iterator end() const {
      if( ccgsl_pointer == 0 ) return const_iterator( this, 0 );
      return const_iterator( this, size() );
    }
  };
 
}
#endif