TrigCompositeUtils::KFromNItr Class Reference

Iterates over all combinations of k values chosen from a range n. More...

#include <KFromNItr.h>

Collaboration diagram for TrigCompositeUtils::KFromNItr:

Public Types
using	iterator_category = std::input_iterator_tag
	Iterator traits. More...
using	value_type = std::vector< std::size_t >
using	reference = const value_type &
using	pointer = const value_type *
using	difference_type = std::ptrdiff_t

Public Member Functions
	KFromNItr ()=default
	Default constructor creates a generic past-the-end iterator. More...
	KFromNItr (std::size_t k, std::size_t N)
	Construct the iterator choosing k from N. More...
std::size_t	size () const
	The size of each combination (k) More...
void	reset ()
	Reset the iterator to its start position. More...
bool	exhausted () const
	True if this iterator is past the end. More...
reference	operator* () const
	Dereference. More...
pointer	operator-> () const
KFromNItr &	operator++ ()
	Pre-increment operator. More...
KFromNItr	operator++ (int)
	Post-increment operator. More...
bool	operator== (const KFromNItr &other) const
	Iterator comparison functions. More...
bool	operator!= (const KFromNItr &other) const

Private Attributes
std::size_t	m_N {0}
	The number of indices. More...
std::vector< std::size_t >	m_current
	The current combination. More...

Detailed Description

Iterates over all combinations of k values chosen from a range n.

Generates all distinct combinations of k distinct values less than N.

This is an input iterator as it's impossible to satisfy the multi-pass guarantee in the forward iterator category where the return value is generated on the fly. However, this still follows the forward iterator convention that all past-the-end iterators compare equal, and that a default constructed iterator counts as a past-the-end iterator.

Combinations are generated in ascending order, with the indices in ascending order. The highest index is always incremented first if possible. Therefore the combinations generated by an iterator constructed as KFromNItr(3, 4); would be (0, 1, 2) (0, 1, 3) (0, 2, 3) (1, 2, 3)

Definition at line 34 of file KFromNItr.h.

Member Typedef Documentation

difference_type

using TrigCompositeUtils::KFromNItr::difference_type = std::ptrdiff_t

Definition at line 42 of file KFromNItr.h.

iterator_category

using TrigCompositeUtils::KFromNItr::iterator_category = std::input_iterator_tag

Iterator traits.

Definition at line 38 of file KFromNItr.h.

pointer

using TrigCompositeUtils::KFromNItr::pointer = const value_type *

Definition at line 41 of file KFromNItr.h.

reference

using TrigCompositeUtils::KFromNItr::reference = const value_type &

Definition at line 40 of file KFromNItr.h.

value_type

using TrigCompositeUtils::KFromNItr::value_type = std::vector<std::size_t>

Definition at line 39 of file KFromNItr.h.

Constructor & Destructor Documentation

KFromNItr() [1/2]

TrigCompositeUtils::KFromNItr::KFromNItr ( )

default

Default constructor creates a generic past-the-end iterator.

KFromNItr() [2/2]

TrigCompositeUtils::KFromNItr::KFromNItr	(	std::size_t	k,
		std::size_t	N
	)

Construct the iterator choosing k from N.

Definition at line 10 of file KFromNItr.cxx.

      : m_N(N),
        m_current(k, 0)
  {
    // Fill the iterator with the first combination
    reset();
  }

Member Function Documentation

exhausted()

bool TrigCompositeUtils::KFromNItr::exhausted

(

)

const

True if this iterator is past the end.

Definition at line 24 of file KFromNItr.cxx.

  {
    return size() == 0 || m_current.back() >= m_N;
  }

operator!=()

bool TrigCompositeUtils::KFromNItr::operator!=

(

const KFromNItr &

other

)

const

Definition at line 109 of file KFromNItr.cxx.

  {
    return !(*this == other);
  }

operator*()

KFromNItr::reference TrigCompositeUtils::KFromNItr::operator*

(

)

const

Dereference.

Definition at line 29 of file KFromNItr.cxx.

  {
    if (exhausted())
      throw std::runtime_error("Dereferencing past-the-end iterator!");
    return m_current;
  }

operator++() [1/2]

KFromNItr & TrigCompositeUtils::KFromNItr::operator++

(

)

Pre-increment operator.

Definition at line 43 of file KFromNItr.cxx.

  {
    if (exhausted())
      // Don't iterate an iterator that is already past the end
      return *this;
    // All index combinations pointed to by this iterator are in ascending order.
    // In order to generate the next combination, go through the following steps,
    // starting with the highest (last) index
    //
    // 1. Increment the current index
    // 2. If it is less than its end point then go to step 4
    // 3. If it is equal to its end point then shift the current index to be the
    //    before this one and go to step 1.
    // 4. Set each index after the current one to larger than its preceding
    //    index's value
    //
    // For an example, consider picking 3 values from the range 0 - 4.
    // The maximum value here is '5'
    // The combination starts at  (0, 1, 2). For the first two increments only the
    // third index changes as the comparison in step 2 is always true and the
    // iterator yields the sequence (0, 1, 3), (0, 1, 4).
    // After this, the third index increments to 5 (the max value) and so we
    // increment the second index. As this is now less than its maximum value (4)
    // we reset all following indices in an ascending sequence, yielding (0, 2, 3)
 
    // Start from the last index
    auto backItr = m_current.rbegin();
    // the end point decreases as we go back through the sequence
    std::size_t end = m_N;
    while (backItr != m_current.rend())
    {
      // This statement increments the value pointed to by backItr, then checks
      // that it's still below its maximum value
      if (++(*backItr) < end)
      {
        // step 4 - this value is now OK. We have to set each following element
        // in increasing sequence
        // backItr.base() returns an iterator pointing to the element *after* this
        // one
        std::iota(backItr.base(), m_current.end(), *backItr + 1);
        break;
      }
      ++backItr;
      --end;
    }
    return *this;
  }

operator++() [2/2]

KFromNItr TrigCompositeUtils::KFromNItr::operator++

(

int

)

Post-increment operator.

Copy our current state

Definition at line 91 of file KFromNItr.cxx.

  {
    KFromNItr ret(*this);
    // step us past this point
    this->operator++();
    return ret;
  }

operator->()

KFromNItr::pointer TrigCompositeUtils::KFromNItr::operator->

(

)

const

Definition at line 36 of file KFromNItr.cxx.

  {
    if (exhausted())
      throw std::runtime_error("Dereferencing past-the-end iterator!");
    return &m_current;
  }

operator==()

bool TrigCompositeUtils::KFromNItr::operator==

(

const KFromNItr &

other

)

const

Iterator comparison functions.

Definition at line 100 of file KFromNItr.cxx.

  {
    // All past-the-end iterators compare equal
    if (exhausted() && other.exhausted())
      return true;
    // Otherwise make sure that the iterators point to the same combination
    return m_current == other.m_current;
  }

reset()

void TrigCompositeUtils::KFromNItr::reset

(

)

Reset the iterator to its start position.

Definition at line 18 of file KFromNItr.cxx.

  {
    // The first combination is just an ascending sequence starting from 0
    std::iota(m_current.begin(), m_current.end(), 0);
  }

size()

std::size_t TrigCompositeUtils::KFromNItr::size ( ) const

inline

The size of each combination (k)

Definition at line 51 of file KFromNItr.h.

{ return m_current.size(); }

Member Data Documentation

m_current

std::vector<std::size_t> TrigCompositeUtils::KFromNItr::m_current

private

The current combination.

Definition at line 77 of file KFromNItr.h.

m_N

std::size_t TrigCompositeUtils::KFromNItr::m_N {0}

private

The number of indices.

Definition at line 75 of file KFromNItr.h.

---

The documentation for this class was generated from the following files:

• KFromNItr.h
• KFromNItr.cxx