3.4. orbit.hpp

Full path: orbit.hpp

template<template<typename> class T>
concept InOrbitHandler
Notation
type value_type

An integer type that T can be instantiated with.

value_type n
value_type i
value_type j
T<value_type> handler
Orbit orbit

A range of value_types.

Valid Expressions

  • T<value_type>(i), constructible from a maximum element size n.

  • handler.clear(i, orbit), reset the orbit to just i.

  • handler(i), check if i is in the orbit. Must return a boolean.

  • handler.add(i, j), add i as the j th orbit element starting from 1. i is the 0th element.

template<typename ValueType>
class InOrbitHandlerBitset

Models InOrbitHandler.

template<typename ValueType>
class InOrbitHandlerVector

Models InOrbitHandler. .. function:: ValueType position(ValueType u) const

Requires the clear method to have been called. Requires either u has been added or was the element given to the latest clear.

returns

the position of u in the orbit. The initial orbit element is at position 0.

template<typename ValueType, template<typename> class InOrbitHandlerT = InOrbitHandlerBitset>
class Orbit

Requires InOrbitHandler<InOrbitHandlerT>.

An orbit calculator, which also acts as a range of the calculated orbit elements.

Orbit(ValueType n, ValueType w)

Construct with a maximum element size n and an initial orbit element w.

void clear(ValueType w)

Reset the object to an orbit with just w.

template<typename GenPtrIter, typename OnNewElement, typename OnDupElement>
bool update(const GenPtrIter &first, const GenPtrIter &lastOld, const GenPtrIter &lastNew, OnNewElement onNewElement, OnDupElement onDupElement)

Requires the iterators to iterator over pointer-like values to permutations (Permutation). That is, Permutation<typename std::pointer_traits<typename std::iterator_traits<GenPtrIter>::value_type>::element_type>.

Given two ranges of generators, first to lastOld and lastOld to lastNew, extend the current orbit using first the new generators, lastOld to lastNew, and then with all generators.

When a new orbit element o is found, by mapping a known orbit element w through a permutation pointed to by an iterator it, then onNewElement(w, o, it) is called. Similarly, when o is already in the orbit then onDupElement(w, o, it) is called.

auto begin() const
Returns

an iterator to the first orbit element.

auto end() const
Returns

an iterator to past-the-end of the orbit.

Todo

document

ValueType position(ValueType u) const

Requires InOrbitHandlerT to have a position method.

Returns the position of u in the orbit (starting from 0). See also InOrbitHandlerVector::position.

template<typename GenPtrIter, typename OnNewElement, typename OnDupElement>
void orbit(std::size_t w, const GenPtrIter &first, const GenPtrIter &last, std::size_t n, OnNewElement onNewElement, OnDupElement onDupElement)
template<typename GenPtrIter, typename OnNewElement, typename OnDupElement>
void orbit(std::size_t w, const GenPtrIter &first, const GenPtrIter &last, OnNewElement onNewElement, OnDupElement onDupElement)
template<typename GenPtrIter, typename OnNewElement>
void orbit(std::size_t w, const GenPtrIter &first, const GenPtrIter &last, OnNewElement onNewElement)

Calculate the orbit of w under the non-empty range of generators first to last. See Orbit::update for the details of first, last, onNewElement, and onDupElement. Note though that onNewElement(w, w, last) is called in the beginning in addition. The overload without n requires SizeAwarePermutation<decltype(**first)> and sets n = perm_group::degree(**first).

template<typename Group, typename Callback>
void orbit(std::size_t w, const Group &g, Callback callback)

Calculate the orbit of w in the group g. See Orbit::update::onNewElement for the meaning of callback.

template<typename OutIter>
orbit_callback_output_iterator<OutIter> make_orbit_callback_output_iterator(OutIter iter)
Returns

a callback usable in the Orbit::update or orbit functions that outputs the elements to the given output iterator iter.