In writing a free word class for ttauto, I wanted to use STL-style generic algorithms. To reduce a free word, one needs to go through and cancel adjacent elements. I ended up writing this algorithm, adjacent_remove_if:
// Remove from container adjacent elements satisfying a comparison function.
// Similar to unique (http://www.cplusplus.com/reference/algorithm/unique/)
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator
adjacent_remove_if(ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
{
if (first == last) return last;
ForwardIterator result = first;
while (++first != last)
{
if (!pred(*result,*first))
{
// The elements are not equal, so copy to result and move on.
*(++result) = std::move(*first);
}
else
{
// The elements are equal.
// Point the the next element (after the elements to be cancelled).
// If we're at the end of the container, we're done.
if (++first == last) return result;
// Copy the next element after the cancelled ones.
*result = std::move(*first);
}
}
return ++result;
}
I can then reduce a free word by repeatedly running this algo until nothing changes:
// Reduce a word by canceling adjacent inverses.
template<class T>
inline free_word<T>& free_word<T>::reduce()
{
// Elements are "equal" if they are inverses of each other.
struct IsInv {
bool operator() (const T& a, const T& b) { return (a == -b); }
} isinv;
while (true)
{
auto i = adjacent_remove_if(this->begin(),this->end(),isinv);
if (i == this->end()) break;
this->erase(i,this->end());
}
return *this;
}
This kind of algo could be used to greatly simplify braid.compact. But it's much less obvious to see how to implement the 121==212 relation. Is it worth implementing?
In writing a free word class for
ttauto
, I wanted to use STL-style generic algorithms. To reduce a free word, one needs to go through and cancel adjacent elements. I ended up writing this algorithm,adjacent_remove_if
:I can then reduce a free word by repeatedly running this algo until nothing changes:
This kind of algo could be used to greatly simplify
braid.compact
. But it's much less obvious to see how to implement the121==212
relation. Is it worth implementing?