commit 3ed539e164b4d88fb9599411cd085e6fcac61081
Author: Mohammad-Reza Nabipoor <mnabipoor@gnu.org>
Date: Sat, 28 May 2022 00:49:05 +0430
stlab/: Add stlab
Diffstat:
11 files changed, 2467 insertions(+), 0 deletions(-)
diff --git a/stlab/algorithm/reverse.hpp b/stlab/algorithm/reverse.hpp
@@ -0,0 +1,97 @@
+/*
+ Copyright 2013 Adobe
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+*/
+/*************************************************************************************************/
+
+#ifndef STLAB_ALGORITHM_REVERSE_HPP
+#define STLAB_ALGORITHM_REVERSE_HPP
+
+#include <algorithm>
+#include <utility>
+
+#include <stlab/iterator/set_next.hpp>
+
+/*************************************************************************************************/
+
+namespace stlab {
+
+/*************************************************************************************************/
+
+namespace unsafe {
+
+/*************************************************************************************************/
+
+template <typename I> // I models NodeIterator
+I reverse_append(I first, I last, I result) {
+ while (first != last) {
+ I prior(first);
+ ++first;
+ stlab::unsafe::set_next(prior, result);
+ result = prior;
+ }
+ return result;
+}
+
+template <typename R, // R models NodeRange
+ typename I> // I models NodeIterator
+inline I reverse_append(R& range, I result) {
+ return stlab::unsafe::reverse_append(std::begin(range), std::end(range), result);
+}
+
+template <typename I> // I models NodeIterator
+inline I reverse_nodes(I first, I last) {
+ return stlab::unsafe::reverse_append(first, last, last);
+}
+
+template <typename R> // R models NodeRange
+inline typename R::iterator reverse_nodes(R& range) {
+ return stlab::unsafe::reverse_nodes(std::begin(range), std::end(range));
+}
+
+/*************************************************************************************************/
+
+} // namspace unsafe
+
+/*************************************************************************************************/
+
+template <class BidirectionalRange>
+inline void reverse(BidirectionalRange& range) {
+ std::reverse(std::begin(range), std::end(range));
+}
+
+template <class BidirectionalRange, class OutputIterator>
+inline void reverse_copy(BidirectionalRange& range, OutputIterator result) {
+ std::reverse_copy(std::begin(range), std::end(range), result);
+}
+
+template <class BidirectionalRange, class OutputIterator>
+inline void reverse_copy(const BidirectionalRange& range, OutputIterator result) {
+ std::reverse_copy(std::begin(range), std::end(range), result);
+}
+
+/*************************************************************************************************/
+
+template <typename I> // I models BidirectionalIterator
+std::pair<I, I> reverse_until(I f, I m, I l) {
+ while (f != m && m != l) {
+ --l;
+
+ std::iter_swap(f, l);
+
+ ++f;
+ }
+
+ return std::pair<I, I>(f, l);
+}
+
+/*************************************************************************************************/
+
+} // namespace stlab
+
+/*************************************************************************************************/
+
+#endif // STLAB_ALGORITHM_REVERSE_HPP
+
+/*************************************************************************************************/
diff --git a/stlab/copy_on_write.hpp b/stlab/copy_on_write.hpp
@@ -0,0 +1,216 @@
+/*
+ Copyright 2013 Adobe
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+*/
+/**************************************************************************************************/
+
+#ifndef STLAB_COPY_ON_WRITE_HPP
+#define STLAB_COPY_ON_WRITE_HPP
+
+/**************************************************************************************************/
+
+#include <atomic>
+#include <cassert>
+#include <cstddef>
+#include <utility>
+
+/**************************************************************************************************/
+
+namespace stlab {
+
+/**************************************************************************************************/
+
+template <typename T> // T models Regular
+class copy_on_write {
+ struct model {
+ std::atomic<std::size_t> _count{1};
+
+ model() = default;
+
+ template <class... Args>
+ explicit model(Args&&... args) : _value(std::forward<Args>(args)...) {}
+
+ T _value;
+ };
+
+ model* _self;
+
+ template <class U>
+ using disable_copy = std::enable_if_t<!std::is_same<std::decay_t<U>, copy_on_write>::value>*;
+
+ template <typename U>
+ using disable_copy_assign =
+ std::enable_if_t<!std::is_same<std::decay_t<U>, copy_on_write>::value, copy_on_write&>;
+
+public:
+ /* [[deprecated]] */ using value_type = T;
+
+ using element_type = T;
+
+ copy_on_write() {
+ static model default_s;
+ _self = &default_s;
+
+ // coverity[useless_call]
+ ++_self->_count;
+ }
+
+ template <class U>
+ copy_on_write(U&& x, disable_copy<U> = nullptr) : _self(new model(std::forward<U>(x))) {}
+
+ template <class U, class V, class... Args>
+ copy_on_write(U&& x, V&& y, Args&&... args)
+ : _self(new model(std::forward<U>(x), std::forward<V>(y), std::forward<Args>(args)...)) {}
+
+ copy_on_write(const copy_on_write& x) noexcept : _self(x._self) {
+ assert(_self && "FATAL (sparent) : using a moved copy_on_write object");
+
+ // coverity[useless_call]
+ ++_self->_count;
+ }
+ copy_on_write(copy_on_write&& x) noexcept : _self(x._self) {
+ assert(_self && "WARNING (sparent) : using a moved copy_on_write object");
+ x._self = nullptr;
+ }
+
+ ~copy_on_write() {
+ if (_self && (--_self->_count == 0)) delete _self;
+ }
+
+ auto operator=(const copy_on_write& x) noexcept -> copy_on_write& {
+ return *this = copy_on_write(x);
+ }
+
+ auto operator=(copy_on_write&& x) noexcept -> copy_on_write& {
+ auto tmp = std::move(x);
+ swap(*this, tmp);
+ return *this;
+ }
+
+ template <class U>
+ auto operator=(U&& x) -> disable_copy_assign<U> {
+ if (_self && unique()) {
+ _self->_value = std::forward<U>(x);
+ return *this;
+ }
+
+ return *this = copy_on_write(std::forward<U>(x));
+ }
+
+ auto write() -> element_type& {
+ if (!unique()) *this = copy_on_write(read());
+
+ return _self->_value;
+ }
+
+ auto read() const noexcept -> const element_type& {
+ assert(_self && "FATAL (sparent) : using a moved copy_on_write object");
+
+ return _self->_value;
+ }
+
+ operator const element_type&() const noexcept { return read(); }
+
+ auto operator*() const noexcept -> const element_type& { return read(); }
+
+ auto operator-> () const noexcept -> const element_type* { return &read(); }
+
+ bool unique() const noexcept {
+ assert(_self && "FATAL (sparent) : using a moved copy_on_write object");
+
+ return _self->_count == 1;
+ }
+ [[deprecated]] bool unique_instance() const noexcept { return unique(); }
+
+ bool identity(const copy_on_write& x) const noexcept {
+ assert((_self && x._self) && "FATAL (sparent) : using a moved copy_on_write object");
+
+ return _self == x._self;
+ }
+
+ friend inline void swap(copy_on_write& x, copy_on_write& y) noexcept {
+ std::swap(x._self, y._self);
+ }
+
+ friend inline bool operator<(const copy_on_write& x, const copy_on_write& y) noexcept {
+ return !x.identity(y) && (*x < *y);
+ }
+
+ friend inline bool operator<(const copy_on_write& x, const element_type& y) noexcept {
+ return *x < y;
+ }
+
+ friend inline bool operator<(const element_type& x, const copy_on_write& y) noexcept {
+ return x < *y;
+ }
+
+ friend inline bool operator>(const copy_on_write& x, const copy_on_write& y) noexcept {
+ return y < x;
+ }
+
+ friend inline bool operator>(const copy_on_write& x, const element_type& y) noexcept {
+ return y < x;
+ }
+
+ friend inline bool operator>(const element_type& x, const copy_on_write& y) noexcept {
+ return y < x;
+ }
+
+ friend inline bool operator<=(const copy_on_write& x, const copy_on_write& y) noexcept {
+ return !(y < x);
+ }
+
+ friend inline bool operator<=(const copy_on_write& x, const element_type& y) noexcept {
+ return !(y < x);
+ }
+
+ friend inline bool operator<=(const element_type& x, const copy_on_write& y) noexcept {
+ return !(y < x);
+ }
+
+ friend inline bool operator>=(const copy_on_write& x, const copy_on_write& y) noexcept {
+ return !(x < y);
+ }
+
+ friend inline bool operator>=(const copy_on_write& x, const element_type& y) noexcept {
+ return !(x < y);
+ }
+
+ friend inline bool operator>=(const element_type& x, const copy_on_write& y) noexcept {
+ return !(x < y);
+ }
+
+ friend inline bool operator==(const copy_on_write& x, const copy_on_write& y) noexcept {
+ return x.identity(y) || (*x == *y);
+ }
+
+ friend inline bool operator==(const copy_on_write& x, const element_type& y) noexcept {
+ return *x == y;
+ }
+
+ friend inline bool operator==(const element_type& x, const copy_on_write& y) noexcept {
+ return x == *y;
+ }
+
+ friend inline bool operator!=(const copy_on_write& x, const copy_on_write& y) noexcept {
+ return !(x == y);
+ }
+
+ friend inline bool operator!=(const copy_on_write& x, const element_type& y) noexcept {
+ return !(x == y);
+ }
+
+ friend inline bool operator!=(const element_type& x, const copy_on_write& y) noexcept {
+ return !(x == y);
+ }
+};
+/**************************************************************************************************/
+
+} // namespace stlab
+
+/**************************************************************************************************/
+
+#endif
+
+/**************************************************************************************************/
diff --git a/stlab/enum_ops.hpp b/stlab/enum_ops.hpp
@@ -0,0 +1,367 @@
+/*
+ Copyright 2013 Adobe
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+*/
+/**************************************************************************************************/
+
+#ifndef STLAB_ENUM_OPS_HPP
+#define STLAB_ENUM_OPS_HPP
+
+/**************************************************************************************************/
+
+#include <type_traits>
+
+/**************************************************************************************************/
+
+/*!
+ \defgroup enum_ops Typesafe Integers and Bit Fields (enums)
+ \ingroup utility
+
+ \section Description Description
+
+ \c enum_ops provides optional typesafe bitset and arithmetic operations for enumeration types.
+ Without these typesafe operations, the compiler will promote the operand(s) to the appropriate
+ integral type, and the result will be an integral type. When the typesafe operations have been
+ defined for an enumeration type, \c E, the result will be of type \c E exactly when the
+ operand(s) are of type \c E.
+
+ \c auto stlab_enable_bitmask_enum(E) -> std::true_type;
+ enables the bitset operations <code>~, |, &, ^, |=, &=, ^= </code>
+ for enumeration type \c E.
+
+ \c auto stlab_enable_arithmetic_enum(E) -> std::true_type;
+ enables the typesafe arithmetic operations <code>+, -, *, /,
+ %, +=, *=, -=, /=, \%=</code> for enumeration type \c E.
+
+ \section Definition Definition
+
+ Defined in \link enum_ops.hpp <code>stlab/enum_ops.hpp</code> \endlink
+
+ \section Example Example
+
+ The following is an example of code that will compile:
+ \dontinclude enum_ops_example.cpp
+ \skip start_of_example
+ \until end_of_example
+
+ The following is contains an example of code that will not compile
+ since the typesafe operators have not been defined.
+
+ \dontinclude enum_ops_example_fail.cpp
+ \skip start_of_example
+ \until end_of_example
+*/
+
+/**************************************************************************************************/
+
+namespace stlab {
+
+/**************************************************************************************************/
+
+auto stlab_enable_bitmask_enum(...) -> std::false_type;
+auto stlab_enable_arithmetic_enum(...) -> std::false_type;
+
+/**************************************************************************************************/
+
+namespace implementation {
+
+/**************************************************************************************************/
+
+template <class T>
+using has_enabled_bitmask_t = decltype(stlab_enable_bitmask_enum(std::declval<T>()));
+
+template <class T>
+constexpr bool has_enabled_bitmask = has_enabled_bitmask_t<T>::value;
+
+template <class T>
+using has_enabled_arithmetic_t = decltype(stlab_enable_arithmetic_enum(std::declval<T>()));
+
+template <class T>
+constexpr bool has_enabled_arithmetic = has_enabled_arithmetic_t<T>::value;
+
+template <class T, class U>
+using enable_if_bitmask_or_arithmetic =
+ std::enable_if_t<std::disjunction_v<stlab::implementation::has_enabled_bitmask_t<T>,
+ stlab::implementation::has_enabled_arithmetic_t<T>>,
+ U>;
+
+template <class, bool>
+struct safe_underlying_type;
+
+template <class T>
+struct safe_underlying_type<T, true> {
+ using type = std::underlying_type_t<T>;
+};
+
+template <class T>
+struct safe_underlying_type<T, false> {
+ using type = void;
+};
+
+template <class T>
+using safe_underlying_type_t = typename safe_underlying_type<T, std::is_enum<T>::value>::type;
+
+template <class U, class T>
+using is_convertible_to_underlying =
+ std::is_convertible<U, stlab::implementation::safe_underlying_type_t<T>>;
+
+/**************************************************************************************************/
+
+} // namespace implementation
+
+/**************************************************************************************************/
+
+} // namespace stlab
+
+/**************************************************************************************************/
+
+template <class T>
+constexpr auto operator&(T lhs, T rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_bitmask<T>, T> {
+ using underlying = std::underlying_type_t<T>;
+ return static_cast<T>(static_cast<underlying>(lhs) & static_cast<underlying>(rhs));
+}
+
+template <class T>
+constexpr auto operator~(T a)
+ -> std::enable_if_t<stlab::implementation::has_enabled_bitmask<T>, T> {
+ using underlying = std::underlying_type_t<T>;
+ return static_cast<T>(~static_cast<underlying>(a));
+}
+
+template <class T>
+constexpr auto operator|(T lhs, T rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_bitmask<T>, T> {
+ using underlying = std::underlying_type_t<T>;
+ return static_cast<T>(static_cast<underlying>(lhs) | static_cast<underlying>(rhs));
+}
+
+template <class T>
+constexpr auto operator^(T lhs, T rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_bitmask<T>, T> {
+ using underlying = std::underlying_type_t<T>;
+ return static_cast<T>(static_cast<underlying>(lhs) ^ static_cast<underlying>(rhs));
+}
+
+template <class T>
+constexpr auto operator<<(T lhs, std::size_t rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_bitmask<T>, T> {
+ using underlying = std::make_unsigned<std::underlying_type_t<T>>;
+
+ return lhs = static_cast<underlying>(lhs) << static_cast<underlying>(rhs);
+}
+
+template <class T>
+constexpr auto operator>>(T lhs, std::size_t rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_bitmask<T>, T> {
+ using underlying = std::make_unsigned<std::underlying_type_t<T>>;
+
+ return lhs = static_cast<underlying>(lhs) >> static_cast<underlying>(rhs);
+}
+
+template <class T>
+constexpr auto operator^=(T& lhs, T rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_bitmask<T>, T&> {
+ return lhs = lhs ^ rhs;
+}
+
+template <class T>
+constexpr auto operator&=(T& lhs, T rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_bitmask<T>, T&> {
+ return lhs = lhs & rhs;
+}
+
+template <class T>
+constexpr auto operator|=(T& lhs, T rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_bitmask<T>, T&> {
+ return lhs = lhs | rhs;
+}
+
+template <class T>
+constexpr auto operator<<=(T& lhs, std::size_t rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_bitmask<T>, T&> {
+ return lhs = lhs << rhs;
+}
+
+template <class T>
+constexpr auto operator>>=(T& lhs, std::size_t rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_bitmask<T>, T&> {
+ return lhs = lhs >> rhs;
+}
+
+template <class T, class U>
+constexpr auto operator-(T lhs, U rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_bitmask<T> &&
+ stlab::implementation::is_convertible_to_underlying<U, T>::value,
+ T> {
+ using underlying = std::underlying_type_t<T>;
+ return static_cast<T>(static_cast<underlying>(lhs) - static_cast<underlying>(rhs));
+}
+
+/**************************************************************************************************/
+
+template <class T>
+constexpr auto operator+(T a)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T>, T> {
+ using underlying = std::underlying_type_t<T>;
+ return static_cast<T>(+static_cast<underlying>(a));
+}
+
+template <class T>
+constexpr auto operator-(T a)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T>, T> {
+ using underlying = std::underlying_type_t<T>;
+ return static_cast<T>(-static_cast<underlying>(a));
+}
+
+template <class T>
+constexpr auto operator+(T lhs, T rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T>, T> {
+ using underlying = std::underlying_type_t<T>;
+ return static_cast<T>(static_cast<underlying>(lhs) + static_cast<underlying>(rhs));
+}
+
+template <class T>
+constexpr auto operator-(T lhs, T rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T>, T> {
+ using underlying = std::underlying_type_t<T>;
+ return static_cast<T>(static_cast<underlying>(lhs) - static_cast<underlying>(rhs));
+}
+
+template <class T, class U>
+constexpr auto operator*(T lhs, U rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T> &&
+ stlab::implementation::is_convertible_to_underlying<U, T>::value,
+ T> {
+ using underlying = std::underlying_type_t<T>;
+ return static_cast<T>(static_cast<underlying>(lhs) * rhs);
+}
+
+template <class U, class T>
+constexpr auto operator*(U lhs, T rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T> &&
+ stlab::implementation::is_convertible_to_underlying<U, T>::value,
+ T> {
+ using underlying = std::underlying_type_t<T>;
+ return static_cast<T>(lhs * static_cast<underlying>(rhs));
+}
+
+template <class T, class U>
+constexpr auto operator/(T lhs, U rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T> &&
+ stlab::implementation::is_convertible_to_underlying<U, T>::value,
+ T> {
+ using underlying = std::underlying_type_t<T>;
+ return static_cast<T>(static_cast<underlying>(lhs) / rhs);
+}
+
+template <class T, class U>
+constexpr auto operator%(T lhs, U rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T> &&
+ stlab::implementation::is_convertible_to_underlying<U, T>::value,
+ T> {
+ using underlying = std::underlying_type_t<T>;
+ return static_cast<T>(static_cast<underlying>(lhs) % rhs);
+}
+
+template <class T>
+constexpr auto operator+=(T& lhs, T rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T>, T&> {
+ return lhs = lhs + rhs;
+}
+
+template <class T>
+constexpr auto operator-=(T& lhs, T rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T>, T&> {
+ return lhs = lhs - rhs;
+}
+
+template <class T, class U>
+constexpr auto operator*=(T& lhs, U rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T> &&
+ stlab::implementation::is_convertible_to_underlying<U, T>::value,
+ T&> {
+ return lhs = lhs * rhs;
+}
+
+template <class T, class U>
+constexpr auto operator/=(T& lhs, U rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T> &&
+ stlab::implementation::is_convertible_to_underlying<U, T>::value,
+ T&> {
+ return lhs = lhs / rhs;
+}
+
+template <class T, class U>
+constexpr auto operator%=(T& lhs, U rhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T> &&
+ stlab::implementation::is_convertible_to_underlying<U, T>::value,
+ T&> {
+ return lhs = lhs % rhs;
+}
+
+template <class T>
+constexpr auto operator++(T& lhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T>, T&> {
+ return lhs += static_cast<T>(1);
+}
+
+template <class T>
+constexpr auto operator++(T& lhs, int)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T>, T> {
+ T result = lhs;
+ lhs += static_cast<T>(1);
+ return result;
+}
+
+template <class T>
+constexpr auto operator--(T& lhs)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T>, T&> {
+ return lhs -= static_cast<T>(1);
+}
+
+template <class T>
+constexpr auto operator--(T& lhs, int)
+ -> std::enable_if_t<stlab::implementation::has_enabled_arithmetic<T>, T> {
+ T result = lhs;
+ lhs -= static_cast<T>(1);
+ return result;
+}
+
+/**************************************************************************************************/
+
+template <class T>
+constexpr auto operator==(T lhs, std::nullptr_t)
+ -> stlab::implementation::enable_if_bitmask_or_arithmetic<T, bool> {
+ return !lhs;
+}
+
+template <class T>
+constexpr auto operator==(std::nullptr_t, T rhs)
+ -> stlab::implementation::enable_if_bitmask_or_arithmetic<T, bool> {
+ return !rhs;
+}
+
+template <class T>
+constexpr auto operator!=(T lhs, std::nullptr_t rhs)
+ -> stlab::implementation::enable_if_bitmask_or_arithmetic<T, bool> {
+ return !(lhs == rhs);
+}
+
+template <class T>
+constexpr auto operator!=(std::nullptr_t lhs, T rhs)
+ -> stlab::implementation::enable_if_bitmask_or_arithmetic<T, bool> {
+ return !(lhs == rhs);
+}
+
+template <class T>
+constexpr auto operator!(T lhs) -> stlab::implementation::enable_if_bitmask_or_arithmetic<T, bool> {
+ return !static_cast<bool>(lhs);
+}
+
+/**************************************************************************************************/
+
+#endif
+
+/**************************************************************************************************/
diff --git a/stlab/forest.hpp b/stlab/forest.hpp
@@ -0,0 +1,1229 @@
+/*
+ Copyright 2013 Adobe
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+*/
+/**************************************************************************************************/
+
+#ifndef STLAB_FOREST_HPP
+#define STLAB_FOREST_HPP
+
+/**************************************************************************************************/
+
+#include <cassert>
+#include <cstddef>
+#include <functional>
+#include <iterator>
+
+#include <stlab/algorithm/reverse.hpp>
+#include <stlab/iterator/set_next.hpp>
+
+/**************************************************************************************************/
+
+namespace stlab {
+
+/**************************************************************************************************/
+
+enum class forest_edge : bool { trailing, leading };
+
+constexpr auto forest_trailing_edge{forest_edge::trailing};
+constexpr auto forest_leading_edge{forest_edge::leading};
+
+/**************************************************************************************************/
+
+constexpr auto pivot(forest_edge e) { return forest_edge(static_cast<bool>(e) ^ 1); }
+
+template <class I> // I models FullorderIterator
+void pivot(I& i) {
+ i.edge() = pivot(i.edge());
+}
+
+template <class I> // I models FullorderIterator
+auto pivot_of(I i) {
+ pivot(i);
+ return i;
+}
+
+/**************************************************************************************************/
+
+template <class I> // I models a FullorderIterator
+auto leading_of(I i) {
+ i.edge() = forest_edge::leading;
+ return i;
+}
+
+template <class I> // I models a FullorderIterator
+auto trailing_of(I i) {
+ i.edge() = forest_edge::trailing;
+ return i;
+}
+
+/**************************************************************************************************/
+
+constexpr auto is_leading(forest_edge e) {
+ return e == forest_edge::leading;
+}
+
+template <class I> // I models a FullorderIterator
+auto is_leading(const I& i) {
+ return is_leading(i.edge());
+}
+
+constexpr auto is_trailing(forest_edge e) {
+ return e == forest_edge::trailing;
+}
+
+template <class I> // I models a FullorderIterator
+auto is_trailing(const I& i) {
+ return is_trailing(i.edge());
+}
+
+/**************************************************************************************************/
+
+template <class I> // I models FullorderIterator
+I find_parent(I i) {
+ do {
+ i = std::next(trailing_of(i));
+ } while (i.edge() != forest_edge::trailing);
+ return i;
+}
+
+/**************************************************************************************************/
+
+template <class I> // I models FullorderIterator
+bool has_children(const I& i) {
+ return !i.equal_node(std::next(leading_of(i)));
+}
+
+/**************************************************************************************************/
+
+template <class I> // I models FullorderIterator
+struct child_iterator {
+ using value_type = typename std::iterator_traits<I>::value_type;
+ using difference_type = typename std::iterator_traits<I>::difference_type;
+ using reference = typename std::iterator_traits<I>::reference;
+ using pointer = typename std::iterator_traits<I>::pointer;
+ using iterator_category = typename std::iterator_traits<I>::iterator_category;
+
+ child_iterator() = default;
+ explicit child_iterator(I x) : _x(std::move(x)) {}
+ template <class U>
+ child_iterator(const child_iterator<U>& u) : _x(u.base()) {}
+
+ I base() const { return _x; }
+
+ reference operator*() { return dereference(); }
+ pointer operator->() { return &dereference(); }
+ auto& operator++() {
+ increment();
+ return *this;
+ }
+ auto operator++(int) {
+ auto result{*this};
+ increment();
+ return result;
+ }
+ auto& operator--() {
+ decrement();
+ return *this;
+ }
+ auto operator--(int) {
+ auto result{*this};
+ decrement();
+ return result;
+ }
+
+ friend bool operator==(const child_iterator& a, const child_iterator& b) {
+ return a.base() == b.base();
+ }
+ friend bool operator!=(const child_iterator& a, const child_iterator& b) { return !(a == b); }
+
+private:
+ I _x;
+
+ void increment() {
+ pivot(_x);
+ ++_x;
+ }
+ void decrement() {
+ --_x;
+ pivot(_x);
+ }
+
+ reference dereference() { return *_x; }
+};
+
+/**************************************************************************************************/
+
+template <class I> // I models FullorderIterator
+I find_edge(I x, forest_edge edge) {
+ while (x.edge() != edge)
+ ++x;
+ return x;
+}
+
+template <class I> // I models FullorderIterator
+I find_edge_reverse(I x, forest_edge edge) {
+ while (x.edge() != edge)
+ --x;
+ return x;
+}
+
+/**************************************************************************************************/
+
+template <class I, forest_edge Edge> // I models FullorderIterator
+struct edge_iterator {
+ using value_type = typename std::iterator_traits<I>::value_type;
+ using difference_type = typename std::iterator_traits<I>::difference_type;
+ using reference = typename std::iterator_traits<I>::reference;
+ using pointer = typename std::iterator_traits<I>::pointer;
+ using iterator_category = typename std::iterator_traits<I>::iterator_category;
+
+ edge_iterator() = default;
+ explicit edge_iterator(I x) : _x(find_edge(x, Edge)) {}
+ template <class U>
+ edge_iterator(const edge_iterator<U, Edge>& u) : _x(u.base()) {}
+
+ I base() const { return _x; }
+
+ reference operator*() { return dereference(); }
+ pointer operator->() { return &dereference(); }
+ auto& operator++() {
+ increment();
+ return *this;
+ }
+ auto operator++(int) {
+ auto result{*this};
+ increment();
+ return result;
+ }
+ auto& operator--() {
+ decrement();
+ return *this;
+ }
+ auto operator--(int) {
+ auto result{*this};
+ decrement();
+ return result;
+ }
+
+ friend bool operator==(const edge_iterator& a, const edge_iterator& b) {
+ return a.base() == b.base();
+ }
+ friend bool operator!=(const edge_iterator& a, const edge_iterator& b) { return !(a == b); }
+
+private:
+ I _x;
+
+ void increment() { _x = find_edge(std::next(_x), Edge); }
+
+ void decrement() { _x = find_edge_reverse(std::prev(_x), Edge); }
+
+ reference dereference() { return *_x; }
+};
+
+/**************************************************************************************************/
+
+template <class I, // I models a Forest
+ class P> // P models UnaryPredicate of value_type(I)
+struct filter_fullorder_iterator {
+ using value_type = typename std::iterator_traits<I>::value_type;
+ using difference_type = typename std::iterator_traits<I>::difference_type;
+ using reference = typename std::iterator_traits<I>::reference;
+ using pointer = typename std::iterator_traits<I>::pointer;
+ using iterator_category = typename std::iterator_traits<I>::iterator_category;
+
+ filter_fullorder_iterator() = default;
+
+ filter_fullorder_iterator(I f, I l, P p) :
+ _x(skip_forward(f, l, p)), _inside(true), _first(f), _last(l), _predicate(p) {}
+
+ filter_fullorder_iterator(I f, I l) :
+ _x(skip_forward(f, l, P())), _inside(true), _first(f), _last(l) {}
+
+ template <class U>
+ filter_fullorder_iterator(const filter_fullorder_iterator<U, P>& x) :
+ _x(x.base()), _inside(x._inside), _first(x._first), _last(x._last),
+ _predicate(x._predicate) {}
+
+ P predicate() const { return _predicate; }
+
+ forest_edge edge() const { return this->base().edge(); }
+ forest_edge& edge() { return this->base_reference().edge(); }
+
+ bool equal_node(const filter_fullorder_iterator& y) const {
+ return this->base().equal_node(y.base());
+ }
+
+ I base() const { return _x; }
+
+ reference operator*() { return dereference(); }
+ pointer operator->() { return &dereference(); }
+ auto& operator++() {
+ increment();
+ return *this;
+ }
+ auto operator++(int) {
+ auto result{*this};
+ increment();
+ return result;
+ }
+ auto& operator--() {
+ decrement();
+ return *this;
+ }
+ auto operator--(int) {
+ auto result{*this};
+ decrement();
+ return result;
+ }
+
+ friend bool operator==(const filter_fullorder_iterator& a, const filter_fullorder_iterator& b) {
+ return a.base() == b.base();
+ }
+ friend bool operator!=(const filter_fullorder_iterator& a, const filter_fullorder_iterator& b) {
+ return !(a == b);
+ }
+
+private:
+ I _x;
+ bool _inside;
+ I _first;
+ I _last;
+ P _predicate;
+
+ void increment() {
+ I i = this->base();
+
+ if (i == _last) _inside = false;
+ ++i;
+ if (i == _first) _inside = true;
+ if (_inside) i = skip_forward(i, _last, _predicate);
+ this->base_reference() = i;
+ }
+
+ static I skip_forward(I f, I l, P p)
+ // Precondition: l is on a leading edge
+ {
+ while ((f.edge() == forest_edge::leading) && (f != l) && !p(*f)) {
+ f.edge() = forest_edge::trailing;
+ ++f;
+ }
+ return f;
+ }
+
+ static I skip_backward(I f, I l, P p)
+ // Precondition: f is on a trailing edge
+ {
+ while ((l.edge() == forest_edge::trailing) && (f != l) && !p(*l)) {
+ l.edge() = forest_edge::leading;
+ --l;
+ }
+ return l;
+ }
+
+ void decrement() {
+ I i = this->base();
+
+ if (i == _first) _inside = false;
+ --i;
+ if (i == _last) _inside = true;
+ if (_inside) i = skip_backward(_first, i, _predicate);
+ this->base_reference() = i;
+ }
+
+ reference dereference() { return *_x; }
+};
+
+/**************************************************************************************************/
+
+template <class I> // I models a FullorderIterator
+struct reverse_fullorder_iterator {
+ using iterator_type = I;
+
+ using value_type = typename std::iterator_traits<I>::value_type;
+ using difference_type = typename std::iterator_traits<I>::difference_type;
+ using reference = typename std::iterator_traits<I>::reference;
+ using pointer = typename std::iterator_traits<I>::pointer;
+ using iterator_category = typename std::iterator_traits<I>::iterator_category;
+
+ reverse_fullorder_iterator() : _edge(forest_edge::trailing) {}
+ explicit reverse_fullorder_iterator(I x) : _base(--x), _edge(pivot(_base.edge())) {}
+ template <class U>
+ reverse_fullorder_iterator(const reverse_fullorder_iterator<U>& x) :
+ _base(--x.base()), _edge(pivot(_base.edge())) {}
+
+ iterator_type base() const { return std::next(_base); }
+
+ forest_edge edge() const { return _edge; }
+ forest_edge& edge() { return _edge; }
+
+ bool equal_node(const reverse_fullorder_iterator& y) const { return _base.equal_node(y._base); }
+
+ reference operator*() { return dereference(); }
+ pointer operator->() { return &dereference(); }
+ auto& operator++() {
+ increment();
+ return *this;
+ }
+ auto operator++(int) {
+ auto result{*this};
+ increment();
+ return result;
+ }
+ auto& operator--() {
+ decrement();
+ return *this;
+ }
+ auto operator--(int) {
+ auto result{*this};
+ decrement();
+ return result;
+ }
+
+ friend bool operator==(const reverse_fullorder_iterator& a,
+ const reverse_fullorder_iterator& b) {
+ return a.equal(b);
+ }
+ friend bool operator!=(const reverse_fullorder_iterator& a,
+ const reverse_fullorder_iterator& b) {
+ return !(a == b);
+ }
+
+private:
+ I _base;
+ forest_edge _edge;
+
+ void increment() {
+ _base.edge() = pivot(_edge);
+ --_base;
+ _edge = pivot(_base.edge());
+ }
+ void decrement() {
+ _base.edge() = pivot(_edge);
+ ++_base;
+ _edge = pivot(_base.edge());
+ }
+ reference dereference() const { return *_base; }
+
+ bool equal(const reverse_fullorder_iterator& y) const {
+ return (_base == y._base) && (_edge == y._edge);
+ }
+};
+
+/**************************************************************************************************/
+
+template <class I> // I models FullorderIterator
+struct depth_fullorder_iterator {
+ using value_type = typename std::iterator_traits<I>::value_type;
+ using difference_type = typename std::iterator_traits<I>::difference_type;
+ using reference = typename std::iterator_traits<I>::reference;
+ using pointer = typename std::iterator_traits<I>::pointer;
+ using iterator_category = typename std::iterator_traits<I>::iterator_category;
+
+ depth_fullorder_iterator(difference_type d = 0) : _depth(d) {}
+ explicit depth_fullorder_iterator(I x, difference_type d = 0) : _x(x), _depth(d) {}
+ template <class U>
+ depth_fullorder_iterator(const depth_fullorder_iterator<U>& x) :
+ _x(x.base()), _depth(x._depth) {}
+
+ difference_type depth() const { return _depth; }
+ forest_edge edge() const { return this->base().edge(); }
+ forest_edge& edge() { return _x.edge(); }
+ bool equal_node(depth_fullorder_iterator const& y) const {
+ return this->base().equal_node(y.base());
+ }
+
+ I base() const { return _x; }
+
+ reference operator*() { return dereference(); }
+ pointer operator->() { return &dereference(); }
+ auto& operator++() {
+ increment();
+ return *this;
+ }
+ auto operator++(int) {
+ auto result{*this};
+ increment();
+ return result;
+ }
+ auto& operator--() {
+ decrement();
+ return *this;
+ }
+ auto operator--(int) {
+ auto result{*this};
+ decrement();
+ return result;
+ }
+
+ friend bool operator==(const depth_fullorder_iterator& a, const depth_fullorder_iterator& b) {
+ return a.base() == b.base();
+ }
+ friend bool operator!=(const depth_fullorder_iterator& a, const depth_fullorder_iterator& b) {
+ return !(a == b);
+ }
+
+private:
+ I _x;
+ difference_type _depth;
+
+ void increment() {
+ forest_edge old_edge(edge());
+ ++_x;
+ if (old_edge == edge())
+ _depth += difference_type(static_cast<std::size_t>(old_edge) << 1) - 1;
+ }
+
+ void decrement() {
+ forest_edge old_edge(edge());
+ --_x;
+ if (old_edge == edge())
+ _depth -= difference_type(static_cast<std::size_t>(old_edge) << 1) - 1;
+ }
+
+ reference dereference() { return *_x; }
+};
+
+/**************************************************************************************************/
+
+template <class Forest>
+class child_adaptor;
+template <class T>
+class forest;
+
+/**************************************************************************************************/
+
+namespace detail {
+
+/**************************************************************************************************/
+
+template <class D> // derived class
+struct node_base {
+ enum next_prior_t { prior_s, next_s };
+
+ using node_ptr = D*;
+ using reference = node_ptr&;
+
+ node_ptr& link(forest_edge edge, next_prior_t link) {
+ return _nodes[static_cast<std::size_t>(edge)][static_cast<std::size_t>(link)];
+ }
+
+ node_ptr link(forest_edge edge, next_prior_t link) const {
+ return _nodes[static_cast<std::size_t>(edge)][static_cast<std::size_t>(link)];
+ }
+
+ node_ptr _nodes[2][2];
+
+ node_base() :
+ _nodes{{static_cast<node_ptr>(this), static_cast<node_ptr>(this)},
+ {static_cast<node_ptr>(this), static_cast<node_ptr>(this)}} {}
+};
+
+template <class T> // T models Regular
+struct node : public node_base<node<T>> {
+ using value_type = T;
+
+ explicit node(const value_type& data) : _data(data) {}
+
+ value_type _data;
+};
+
+/**************************************************************************************************/
+
+template <class T>
+struct forest_const_iterator;
+
+template <class T> // T is value_type
+struct forest_iterator {
+ using value_type = T;
+ using difference_type = std::ptrdiff_t;
+ using reference = T&;
+ using pointer = T*;
+ using iterator_category = std::bidirectional_iterator_tag;
+
+ forest_iterator() = default;
+
+ forest_iterator(const forest_iterator& x) : _node(x._node), _edge(x._edge) {}
+
+ forest_iterator& operator=(const forest_iterator&) = default;
+
+ forest_edge edge() const { return _edge; }
+ forest_edge& edge() { return _edge; }
+
+ bool equal_node(forest_iterator const& y) const { return _node == y._node; }
+
+ reference operator*() const { return dereference(); }
+ pointer operator->() const { return &dereference(); }
+ auto& operator++() {
+ increment();
+ return *this;
+ }
+ auto operator++(int) {
+ auto result{*this};
+ increment();
+ return result;
+ }
+ auto& operator--() {
+ decrement();
+ return *this;
+ }
+ auto operator--(int) {
+ auto result{*this};
+ decrement();
+ return result;
+ }
+
+ friend bool operator==(const forest_iterator& a, const forest_iterator& b) {
+ return a.equal(b);
+ }
+ friend bool operator!=(const forest_iterator& a, const forest_iterator& b) { return !(a == b); }
+
+private:
+ friend class stlab::forest<value_type>;
+ template <class>
+ friend struct forest_iterator;
+ template <class>
+ friend struct forest_const_iterator;
+ friend struct unsafe::set_next_fn<forest_iterator>;
+
+ using node_t = node<T>;
+
+ reference dereference() const { return _node->_data; }
+
+ void increment() {
+ node_t* next(_node->link(_edge, node_t::next_s));
+
+ if (is_leading(_edge))
+ _edge = forest_edge(next != _node);
+ else
+ _edge = forest_edge(next->link(forest_edge::leading, node_t::prior_s) == _node);
+
+ _node = next;
+ }
+
+ void decrement() {
+ node_t* next(_node->link(_edge, node_t::prior_s));
+
+ if (is_leading(_edge))
+ _edge = forest_edge(next->link(forest_edge::trailing, node_t::next_s) != _node);
+ else
+ _edge = forest_edge(next == _node);
+
+ _node = next;
+ }
+
+ bool equal(const forest_iterator& y) const { return (_node == y._node) && (_edge == y._edge); }
+
+ node_t* _node{nullptr};
+ forest_edge _edge{forest_edge::leading};
+
+ forest_iterator(node_t* node, forest_edge edge) : _node(node), _edge(edge) {}
+};
+
+/**************************************************************************************************/
+
+template <class T> // T is value_type
+struct forest_const_iterator {
+ using value_type = const T;
+ using difference_type = std::ptrdiff_t;
+ using reference = const T&;
+ using pointer = const T*;
+ using iterator_category = std::bidirectional_iterator_tag;
+
+ forest_const_iterator() = default;
+
+ forest_const_iterator(const forest_const_iterator& x) : _node(x._node), _edge(x._edge) {}
+
+ forest_const_iterator& operator=(const forest_const_iterator&) = default;
+
+ forest_const_iterator(const forest_iterator<T>& x) : _node(x._node), _edge(x._edge) {}
+
+ forest_edge edge() const { return _edge; }
+ forest_edge& edge() { return _edge; }
+ bool equal_node(forest_const_iterator const& y) const { return _node == y._node; }
+
+ reference operator*() const { return dereference(); }
+ pointer operator->() const { return &dereference(); }
+ auto& operator++() {
+ increment();
+ return *this;
+ }
+ auto operator++(int) {
+ auto result{*this};
+ increment();
+ return result;
+ }
+ auto& operator--() {
+ decrement();
+ return *this;
+ }
+ auto operator--(int) {
+ auto result{*this};
+ decrement();
+ return result;
+ }
+
+ friend bool operator==(const forest_const_iterator& a, const forest_const_iterator& b) {
+ return a.equal(b);
+ }
+ friend bool operator!=(const forest_const_iterator& a, const forest_const_iterator& b) {
+ return !(a == b);
+ }
+
+private:
+ template <class>
+ friend class stlab::forest;
+ template <class>
+ friend struct forest_const_iterator;
+ friend struct unsafe::set_next_fn<forest_const_iterator>;
+
+ using node_t = const node<T>;
+
+ reference dereference() const { return _node->_data; }
+
+ void increment() {
+ node_t* next(_node->link(_edge, node_t::next_s));
+
+ if (is_leading(_edge))
+ _edge = forest_edge(next != _node);
+ else
+ _edge = forest_edge(next->link(forest_edge::leading, node_t::prior_s) == _node);
+
+ _node = next;
+ }
+
+ void decrement() {
+ node_t* next(_node->link(_edge, node_t::prior_s));
+
+ if (is_leading(_edge))
+ _edge = forest_edge(next->link(forest_edge::trailing, node_t::next_s) != _node);
+ else
+ _edge = forest_edge(next == _node);
+
+ _node = next;
+ }
+
+ bool equal(const forest_const_iterator& y) const {
+ return (_node == y._node) && (_edge == y._edge);
+ }
+
+ node_t* _node{nullptr};
+ forest_edge _edge{forest_edge::leading};
+
+ forest_const_iterator(node_t* node, forest_edge edge) : _node(node), _edge(edge) {}
+};
+
+/**************************************************************************************************/
+
+} // namespace detail
+
+/**************************************************************************************************/
+
+namespace unsafe {
+
+/**************************************************************************************************/
+
+template <class T> // T is node<T>
+struct set_next_fn<detail::forest_iterator<T>> {
+ void operator()(detail::forest_iterator<T> x, detail::forest_iterator<T> y) const {
+ using node_t = typename detail::node<T>;
+
+ x._node->link(x.edge(), node_t::next_s) = y._node;
+ y._node->link(y.edge(), node_t::prior_s) = x._node;
+ }
+};
+
+/**************************************************************************************************/
+
+} // namespace unsafe
+
+/**************************************************************************************************/
+
+template <class T>
+class forest {
+private:
+ using node_t = detail::node<T>;
+ friend class child_adaptor<forest<T>>;
+
+public:
+ // types
+ using reference = T&;
+ using const_reference = const T&;
+ using iterator = detail::forest_iterator<T>;
+ using const_iterator = detail::forest_const_iterator<T>;
+ using size_type = std::size_t;
+ using difference_type = std::ptrdiff_t;
+ using value_type = T;
+ using pointer = T*;
+ using const_pointer = const T*;
+ using reverse_iterator = reverse_fullorder_iterator<iterator>;
+ using const_reverse_iterator = reverse_fullorder_iterator<const_iterator>;
+
+ /* qualification needed since: A name N used in a class S shall refer to the same declaration
+ in its context and when re-evaluated in the completed scope of
+ S. */
+ using child_iterator = stlab::child_iterator<iterator>;
+ using const_child_iterator = stlab::child_iterator<const_iterator>;
+ using reverse_child_iterator = std::reverse_iterator<child_iterator>;
+
+ using preorder_iterator = edge_iterator<iterator, forest_edge::leading>;
+ using const_preorder_iterator = edge_iterator<const_iterator, forest_edge::leading>;
+ using postorder_iterator = edge_iterator<iterator, forest_edge::trailing>;
+ using const_postorder_iterator = edge_iterator<const_iterator, forest_edge::trailing>;
+
+ forest() = default;
+ ~forest() { clear(); }
+
+ forest(const forest& x) : forest() {
+ insert(end(), const_child_iterator(x.begin()), const_child_iterator(x.end()));
+ }
+ forest(forest&& x) noexcept : forest() { splice(end(), x); }
+ forest& operator=(const forest& x) {
+ return *this = forest(x);
+ }
+ forest& operator=(forest&& x) noexcept {
+ auto tmp{move(x)}; // this is `release()`
+ clear(); // these two lines are `reset()`
+ splice(end(), tmp);
+ return *this;
+ }
+
+ void swap(forest& x) { std::swap(*this, x); }
+
+ size_type size() const;
+ size_type max_size() const { return size_type(-1); }
+ bool size_valid() const { return _size != 0 || empty(); }
+ bool empty() const { return begin() == end(); } // Don't test size which may be expensive
+
+ // iterators
+ iterator root() { return iterator(tail(), forest_edge::leading); }
+ const_iterator root() const { return const_iterator(tail(), forest_edge::leading); }
+
+ iterator begin() { return ++root(); }
+ iterator end() { return iterator(tail(), forest_edge::trailing); }
+ const_iterator begin() const { return ++root(); }
+ const_iterator end() const { return const_iterator(tail(), forest_edge::trailing); }
+
+ reverse_iterator rbegin() { return reverse_iterator(end()); }
+ reverse_iterator rend() { return reverse_iterator(begin()); }
+ const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
+ const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
+
+ reference front() {
+ assert(!empty());
+ return *begin();
+ }
+ const_reference front() const {
+ assert(!empty());
+ return *begin();
+ }
+ reference back() {
+ assert(!empty());
+ return *(--end());
+ }
+ const_reference back() const {
+ assert(!empty());
+ return *(--end());
+ }
+
+ // modifiers
+ void clear() {
+ erase(begin(), end());
+ assert(empty()); // Make sure our erase is correct
+ }
+
+ iterator erase(const iterator& position);
+ iterator erase(const iterator& first, const iterator& last);
+
+ iterator insert(const iterator& position, T x) {
+ iterator result(new node_t(std::move(x)), forest_edge::leading);
+
+ if (size_valid()) ++_size;
+
+ unsafe::set_next(std::prev(position), result);
+ unsafe::set_next(std::next(result), position);
+
+ return result;
+ }
+
+ void push_front(const T& x) { insert(begin(), x); }
+ void push_back(const T& x) { insert(end(), x); }
+ void pop_front() {
+ assert(!empty());
+ erase(begin());
+ }
+ void pop_back() {
+ assert(!empty());
+ erase(--end());
+ }
+
+ iterator insert(iterator position, const_child_iterator first, const_child_iterator last);
+
+ iterator splice(iterator position, forest<T>& x);
+ iterator splice(iterator position, forest<T>& x, iterator i);
+ iterator splice(iterator position, forest<T>& x, child_iterator first, child_iterator last);
+ iterator splice(iterator position,
+ forest<T>& x,
+ child_iterator first,
+ child_iterator last,
+ size_type count);
+
+ iterator insert_parent(child_iterator front, child_iterator back, const T& x);
+ void reverse(child_iterator first, child_iterator last);
+
+private:
+ friend struct detail::forest_iterator<value_type>;
+ friend struct detail::forest_const_iterator<value_type>;
+ friend struct unsafe::set_next_fn<iterator>;
+
+ mutable size_type _size{0};
+ detail::node_base<node_t> _tail;
+
+ node_t* tail() { return static_cast<node_t*>(&_tail); }
+ const node_t* tail() const { return static_cast<const node_t*>(&_tail); }
+};
+
+/**************************************************************************************************/
+
+template <class T>
+bool operator==(const forest<T>& x, const forest<T>& y) {
+ if (x.size() != y.size()) return false;
+
+ for (auto first(x.begin()), last(x.end()), pos(y.begin()); first != last; ++first, ++pos) {
+ if (first.edge() != pos.edge()) return false;
+ if (is_leading(first) && (*first != *pos)) return false;
+ }
+
+ return true;
+}
+
+template <class T>
+bool operator!=(const forest<T>& x, const forest<T>& y) {
+ return !(x == y);
+}
+
+/**************************************************************************************************/
+
+namespace unsafe {
+
+/**************************************************************************************************/
+
+template <class I> // I models a FullorderIterator
+struct set_next_fn<child_iterator<I>> {
+ void operator()(child_iterator<I> x, child_iterator<I> y) {
+ unsafe::set_next(pivot_of(x.base()), y.base());
+ }
+};
+
+/**************************************************************************************************/
+
+} // namespace unsafe
+
+/**************************************************************************************************/
+
+template <class T>
+typename forest<T>::size_type forest<T>::size() const {
+ if (!size_valid()) {
+ const_preorder_iterator first(begin());
+ const_preorder_iterator last(end());
+
+ _size = size_type(std::distance(first, last));
+ }
+
+ return _size;
+}
+
+/**************************************************************************************************/
+
+template <class T>
+typename forest<T>::iterator forest<T>::erase(const iterator& first, const iterator& last) {
+ difference_type stack_depth(0);
+ iterator position(first);
+
+ while (position != last) {
+ if (position.edge() == forest_edge::leading) {
+ ++stack_depth;
+ ++position;
+ } else {
+ if (stack_depth > 0)
+ position = erase(position);
+ else
+ ++position;
+ stack_depth = std::max<difference_type>(0, stack_depth - 1);
+ }
+ }
+ return last;
+}
+
+/**************************************************************************************************/
+
+template <class T>
+typename forest<T>::iterator forest<T>::erase(const iterator& position) {
+ /*
+ NOTE (sparent) : After the first call to set_next() the invariants of the forest are
+ violated and we can't determing leading/trailing if we navigate from the affected node.
+ So we gather all the iterators up front then do the set_next calls.
+ */
+
+ if (size_valid()) --_size;
+
+ iterator leading_prior(std::prev(leading_of(position)));
+ iterator leading_next(std::next(leading_of(position)));
+ iterator trailing_prior(std::prev(trailing_of(position)));
+ iterator trailing_next(std::next(trailing_of(position)));
+
+ if (has_children(position)) {
+ unsafe::set_next(leading_prior, leading_next);
+ unsafe::set_next(trailing_prior, trailing_next);
+ } else {
+ unsafe::set_next(leading_prior, trailing_next);
+ }
+
+ delete position._node;
+
+ return is_leading(position) ? std::next(leading_prior) : trailing_next;
+}
+
+/**************************************************************************************************/
+
+template <class T>
+typename forest<T>::iterator forest<T>::splice(iterator position, forest<T>& x) {
+ return splice(position, x, child_iterator(x.begin()), child_iterator(x.end()),
+ x.size_valid() ? x.size() : 0);
+}
+
+/**************************************************************************************************/
+
+template <class T>
+typename forest<T>::iterator forest<T>::splice(iterator position, forest<T>& x, iterator i) {
+ i.edge() = forest_edge::leading;
+ return splice(position, x, child_iterator(i), ++child_iterator(i), has_children(i) ? 0 : 1);
+}
+
+/**************************************************************************************************/
+
+template <class T>
+typename forest<T>::iterator forest<T>::insert(iterator pos,
+ const_child_iterator f,
+ const_child_iterator l) {
+ for (const_iterator first(f.base()), last(l.base()); first != last; ++first, ++pos) {
+ if (is_leading(first)) pos = insert(pos, *first);
+ }
+
+ return pos;
+}
+
+/**************************************************************************************************/
+
+template <class T>
+typename forest<T>::iterator forest<T>::splice(
+ iterator pos, forest<T>& x, child_iterator first, child_iterator last, size_type count) {
+ if (first == last || first.base() == pos) return pos;
+
+ if (&x != this) {
+ if (count) {
+ if (size_valid()) _size += count;
+ if (x.size_valid()) x._size -= count;
+ } else {
+ _size = 0;
+ x._size = 0;
+ }
+ }
+
+ iterator back(std::prev(last.base()));
+
+ unsafe::set_next(std::prev(first), last);
+
+ unsafe::set_next(std::prev(pos), first.base());
+ unsafe::set_next(back, pos);
+
+ return first.base();
+}
+
+/**************************************************************************************************/
+
+template <class T>
+typename forest<T>::iterator forest<T>::splice(iterator pos,
+ forest<T>& x,
+ child_iterator first,
+ child_iterator last) {
+ return splice(pos, x, first, last, 0);
+}
+
+/**************************************************************************************************/
+
+template <class T>
+typename forest<T>::iterator forest<T>::insert_parent(child_iterator first,
+ child_iterator last,
+ const T& x) {
+ iterator result(insert(last.base(), x));
+ if (first == last) return result;
+ splice(trailing_of(result), *this, first, child_iterator(result));
+ return result;
+}
+
+/**************************************************************************************************/
+
+template <class T>
+void forest<T>::reverse(child_iterator first, child_iterator last) {
+ iterator prior(first.base());
+ --prior;
+ first = unsafe::reverse_nodes(first, last);
+ unsafe::set_next(prior, first.base());
+}
+
+/**************************************************************************************************/
+
+template <class I> // I models FullorderIterator
+child_iterator<I> child_begin(const I& x) {
+ return child_iterator<I>(std::next(leading_of(x)));
+}
+
+/**************************************************************************************************/
+
+template <class I> // I models FullorderIterator
+child_iterator<I> child_end(const I& x) {
+ return child_iterator<I>(trailing_of(x));
+}
+
+/**************************************************************************************************/
+
+template <class Forest>
+class child_adaptor {
+public:
+ using forest_type = Forest;
+ using value_type = typename Forest::value_type;
+ using iterator_type = typename Forest::iterator;
+ using reference = typename Forest::reference;
+ using const_reference = typename Forest::const_reference;
+ using difference_type = typename Forest::difference_type;
+ using iterator = typename Forest::child_iterator;
+
+ child_adaptor(forest_type& f, iterator_type& i) : _forest(f), _iterator(i) {}
+
+ value_type& back() { return *(--child_end(_iterator)); }
+ value_type& front() { return *(child_begin(_iterator)); }
+
+ void push_back(const value_type& x) { _forest.insert(child_end(_iterator).base(), x); }
+ void push_front(const value_type& x) { _forest.insert(child_begin(_iterator).base(), x); }
+
+ void pop_back() { _forest.erase(--child_end(_iterator).base()); }
+ void pop_front() { _forest.erase(child_begin(_iterator).base()); }
+
+private:
+ child_adaptor(); // not defined
+
+ forest_type& _forest;
+ iterator_type& _iterator;
+};
+
+/**************************************************************************************************/
+
+template <class I>
+struct forest_range {
+ I _f;
+ I _l;
+
+ auto begin() const { return _f; }
+ auto end() const { return _l; }
+};
+
+/**************************************************************************************************/
+
+template <class I> // I models FullorderIterator
+auto child_range(const I& x) {
+ return forest_range<child_iterator<I>>{child_begin(x), child_end(x)};
+}
+
+/**************************************************************************************************/
+
+template <class R, typename P> // R models FullorderRange
+auto filter_fullorder_range(R& x, P p) {
+ using iterator = filter_fullorder_iterator<typename R::iterator, P>;
+
+ return forest_range<iterator>{iterator(std::begin(x), std::end(x), p),
+ iterator(std::end(x), std::end(x), p)};
+}
+
+template <class R, typename P> // R models FullorderRange
+auto filter_fullorder_range(const R& x, P p) {
+ using iterator = filter_fullorder_iterator<typename R::const_iterator, P>;
+
+ return forest_range<iterator>{iterator(std::begin(x), std::end(x), p),
+ iterator(std::end(x), std::end(x), p)};
+}
+
+/**************************************************************************************************/
+
+template <class R> // R models FullorderRange
+auto reverse_fullorder_range(R& x) {
+ using iterator = reverse_fullorder_iterator<typename R::iterator>;
+
+ return forest_range<iterator>{iterator(std::end(x)), iterator(std::begin(x))};
+}
+
+template <class R> // R models FullorderRange
+auto reverse_fullorder_range(const R& x) {
+ using iterator = reverse_fullorder_iterator<typename R::const_iterator>;
+
+ return forest_range<iterator>{iterator(std::end(x)), iterator(std::begin(x))};
+}
+
+/**************************************************************************************************/
+
+template <class R> // R models FullorderRange
+auto depth_range(R& x) {
+ using iterator = depth_fullorder_iterator<typename R::iterator>;
+
+ return forest_range<iterator>{iterator(std::begin(x)), iterator(std::end(x))};
+}
+
+template <class R> // R models FullorderRange
+auto depth_range(const R& x) {
+ using iterator = depth_fullorder_iterator<typename R::const_iterator>;
+
+ return forest_range<iterator>{iterator(std::begin(x)), iterator(std::end(x))};
+}
+
+/**************************************************************************************************/
+
+template <class R> // R models FullorderRange
+auto postorder_range(R& x) {
+ using iterator = edge_iterator<typename R::iterator, forest_edge::trailing>;
+
+ return forest_range<iterator>{iterator(std::begin(x)), iterator(std::end(x))};
+}
+
+template <class R> // R models FullorderRange
+auto postorder_range(const R& x) {
+ using iterator = edge_iterator<typename R::const_iterator, forest_edge::trailing>;
+
+ return forest_range<iterator>{iterator(std::begin(x)), iterator(std::end(x))};
+}
+
+/**************************************************************************************************/
+
+template <class R> // R models FullorderRange
+auto preorder_range(R& x) {
+ using iterator = edge_iterator<typename R::iterator, forest_edge::leading>;
+
+ return forest_range<iterator>{iterator(std::begin(x)), iterator(std::end(x))};
+}
+
+template <class R> // R models FullorderRange
+auto preorder_range(const R& x) {
+ using iterator = edge_iterator<typename R::const_iterator, forest_edge::leading>;
+
+ return forest_range<iterator>{iterator(std::begin(x)), iterator(std::end(x))};
+}
+
+/**************************************************************************************************/
+
+} // namespace stlab
+
+/**************************************************************************************************/
+
+#endif // STLAB_FOREST_HPP
+
+/**************************************************************************************************/
diff --git a/stlab/forest_algorithms.hpp b/stlab/forest_algorithms.hpp
@@ -0,0 +1,146 @@
+/**************************************************************************************************/
+
+#ifndef STLAB_FOREST_ALGORITHMS_HPP
+#define STLAB_FOREST_ALGORITHMS_HPP
+
+/**************************************************************************************************/
+
+// stlab
+#include <stlab/concurrency/optional.hpp>
+#include <stlab/forest.hpp>
+
+/**************************************************************************************************/
+
+namespace stlab {
+
+/**************************************************************************************************/
+
+namespace forests {
+
+/**************************************************************************************************/
+// "Congruent" would be a nice name here, but in geometry that also implies reflection.
+template <class Forest1, class Forest2>
+bool equal_shape(const Forest1& x, const Forest2& y) {
+ if (x.size_valid() && y.size_valid() && x.size() != y.size()) return false;
+ auto pos{y.begin()};
+ for (auto first(x.begin()), last(x.end()); first != last; ++first, ++pos) {
+ if (first.edge() != pos.edge()) return false;
+ }
+ return true;
+}
+
+/**************************************************************************************************/
+
+template <class Container>
+struct transcribe_iterator {
+ using iterator_category = std::output_iterator_tag;
+ using value_type = void;
+ using difference_type = void;
+ using pointer = void;
+ using reference = void;
+ using container_type = Container;
+
+ transcribe_iterator(Container& c, typename Container::iterator i) : _c{&c}, _i{std::move(i)} {}
+
+ constexpr auto& operator*() { return *this; }
+ constexpr auto& operator++() {
+ ++_i;
+ return *this;
+ }
+ constexpr auto operator++(int) {
+ auto result{*this};
+ ++_i;
+ return result;
+ }
+
+ constexpr auto& operator=(const typename Container::value_type& value) {
+ _i = _c->insert(_i, value);
+ return *this;
+ }
+
+ constexpr auto& operator=(typename Container::value_type&& value) {
+ _i = _c->insert(_i, std::move(value));
+ return *this;
+ }
+
+ constexpr auto trailing() { _i = trailing_of(_i); }
+
+private:
+ Container* _c;
+ typename Container::iterator _i;
+};
+
+template <class Container>
+auto transcriber(Container& c) {
+ return transcribe_iterator<Container>(c, c.begin());
+}
+
+/**************************************************************************************************/
+
+template <class I, class O, class P, class UP>
+auto transcribe(I first, I last, O out, P proj, UP pred) {
+ for (; first != last; ++first, ++out) {
+ if (pred(first)) {
+ out = proj(*first);
+ } else {
+ out.trailing();
+ }
+ }
+ return out;
+}
+
+template <class R, class O, class P, class UP>
+auto transcribe(const R& range, O out, P proj, UP pred) {
+ return transcribe(std::cbegin(range), std::cend(range), std::move(out), std::move(proj),
+ std::move(pred));
+}
+
+template <class I, class O, class P>
+auto transcribe(I first, I last, O out, P proj) {
+ return transcribe(std::move(first), std::move(last), std::move(out), std::move(proj),
+ [](const auto& p) { return is_leading(p); });
+}
+
+template <class R, class O, class P>
+auto transcribe(const R& range, O out, P proj) {
+ return transcribe(std::cbegin(range), std::cend(range), std::move(out), std::move(proj));
+}
+
+/**************************************************************************************************/
+
+template <class I, // models ForestFullorderIterator
+ class O> // models OutputIterator
+auto flatten(I first, I last, O out) {
+ for (; first != last; ++first) {
+ if (is_leading(first)) {
+ *out++ = *first;
+ } else {
+ *out++ = nullopt;
+ }
+ }
+ return out;
+}
+
+/**************************************************************************************************/
+
+template <class I, // I models ForwardIterator; I::value_type == stlab::optional<T>
+ class F> // F models Forest
+auto unflatten(I first, I last, F& f) {
+ return forests::transcribe(
+ first, last, transcriber(f), [](const auto& x) { return *x; },
+ [](const auto& p) { return *p; });
+}
+
+/**************************************************************************************************/
+
+} // namespace forests
+
+/**************************************************************************************************/
+
+} // namespace stlab
+
+/**************************************************************************************************/
+
+#endif // STLAB_FOREST_ALGORITHMS_HPP
+
+/**************************************************************************************************/
diff --git a/stlab/functional.hpp b/stlab/functional.hpp
@@ -0,0 +1,83 @@
+/*
+ Copyright 2017 Adobe
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+*/
+
+/**************************************************************************************************/
+
+#ifndef STLAB_FUNCTIONAL_HPP
+#define STLAB_FUNCTIONAL_HPP
+
+/**************************************************************************************************/
+
+#include <functional>
+#include <type_traits>
+
+/**************************************************************************************************/
+
+namespace stlab {
+
+/**************************************************************************************************/
+
+inline namespace v1 {
+/**************************************************************************************************/
+
+template <class T>
+struct unwrap_reference {
+ using type = T;
+};
+
+template <class T>
+struct unwrap_reference<std::reference_wrapper<T>> {
+ using type = T;
+};
+
+template <class T>
+using unwrap_reference_t = typename unwrap_reference<T>::type;
+
+/**************************************************************************************************/
+
+template <class T>
+struct is_reference_wrapper : std::false_type {};
+template <class T>
+struct is_reference_wrapper<std::reference_wrapper<T>> : std::true_type {};
+
+template <class T>
+constexpr bool is_reference_wrapper_v = is_reference_wrapper<T>::value;
+
+/**************************************************************************************************/
+
+template <typename T>
+T& unwrap(T& val) {
+ return val;
+}
+
+template <typename T>
+const T& unwrap(const T& val) {
+ return val;
+}
+
+template <typename T>
+T& unwrap(std::reference_wrapper<T>& val) {
+ return val.get();
+}
+
+template <typename T>
+const T& unwrap(const std::reference_wrapper<T>& val) {
+ return val.get();
+}
+
+/**************************************************************************************************/
+
+} // namespace v1
+
+/**************************************************************************************************/
+
+} // namespace stlab
+
+/**************************************************************************************************/
+
+#endif
+
+/**************************************************************************************************/
diff --git a/stlab/iterator/set_next.hpp b/stlab/iterator/set_next.hpp
@@ -0,0 +1,62 @@
+/*
+ Copyright 2013 Adobe
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+*/
+/*************************************************************************************************/
+
+#ifndef STLAB_ITERATOR_SET_NEXT_HPP
+#define STLAB_ITERATOR_SET_NEXT_HPP
+
+/*************************************************************************************************/
+
+namespace stlab {
+
+/*************************************************************************************************/
+
+namespace unsafe {
+
+/*************************************************************************************************/
+
+template <typename I> // I models NodeIterator
+struct set_next_fn; // Must be specialized
+
+/*************************************************************************************************/
+
+template <typename I> // I models NodeIterator
+inline void set_next(I x, I y) {
+ set_next_fn<I>()(x, y);
+}
+
+/*************************************************************************************************/
+
+template <typename I> // T models ForwardNodeIterator
+inline void splice_node_range(I location, I first, I last) {
+ I successor(std::next(location));
+ set_next(location, first);
+ set_next(last, successor);
+}
+
+template <typename I> // I models ForwardNodeIterator
+inline void skip_next_node(I location) {
+ set_next(location, std::next(std::next(location)));
+}
+
+template <typename I> // I models BidirectionalNodeIterator
+inline void skip_node(I location) {
+ set_next(std::prev(location), std::next(location));
+}
+
+/*************************************************************************************************/
+
+} // namespace unsafe
+
+/*************************************************************************************************/
+
+} // namespace stlab
+
+/*************************************************************************************************/
+
+#endif // STLAB_ITERATOR_SET_NEXT_HPP
+
+/*************************************************************************************************/
diff --git a/stlab/memory.hpp b/stlab/memory.hpp
@@ -0,0 +1,40 @@
+/*
+ Copyright 2017 Adobe
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+*/
+
+/**************************************************************************************************/
+
+#ifndef STLAB_MEMORY_HPP
+#define STLAB_MEMORY_HPP
+
+/**************************************************************************************************/
+
+#include <memory>
+
+/**************************************************************************************************/
+
+namespace stlab {
+
+/**************************************************************************************************/
+
+inline namespace v1 {
+/**************************************************************************************************/
+
+template <typename T>
+auto make_weak_ptr(const std::shared_ptr<T>& x) {
+ return std::weak_ptr<T>(x);
+}
+
+/**************************************************************************************************/
+
+} // namespace v1
+
+/**************************************************************************************************/
+
+} // namespace stlab
+
+/**************************************************************************************************/
+
+#endif
+\ No newline at end of file
diff --git a/stlab/scope.hpp b/stlab/scope.hpp
@@ -0,0 +1,68 @@
+/*
+ Copyright 2015 Adobe
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+*/
+
+/**************************************************************************************************/
+
+#ifndef STLAB_SCOPE_HPP
+#define STLAB_SCOPE_HPP
+
+/**************************************************************************************************/
+
+#include <mutex>
+#include <tuple>
+#include <utility>
+
+/**************************************************************************************************/
+
+namespace stlab {
+
+/**************************************************************************************************/
+
+inline namespace v1 {
+/**************************************************************************************************/
+
+namespace detail {
+
+template <typename T, typename Tuple, size_t... S>
+auto scope_call(Tuple&& t, std::index_sequence<S...>) {
+ T scoped(std::forward<std::tuple_element_t<S, Tuple>>(std::get<S>(t))...);
+ (void)scoped;
+
+ // call the function
+ constexpr size_t last_index = std::tuple_size<Tuple>::value - 1;
+ return std::forward<std::tuple_element_t<last_index, Tuple>>(std::get<last_index>(t))();
+}
+
+} // namespace detail
+
+/**************************************************************************************************/
+
+template <typename T, typename... Args>
+inline auto scope(Args&&... args) {
+ return detail::scope_call<T>(std::forward_as_tuple(std::forward<Args>(args)...),
+ std::make_index_sequence<sizeof...(args) - 1>());
+}
+
+/* Workaround until VS2017 bug is fixed */
+template <typename T, typename F>
+inline auto scope(std::mutex& m, F&& f) {
+ T scoped(m);
+ return std::forward<F>(f)();
+}
+
+/**************************************************************************************************/
+
+} // namespace v1
+
+/**************************************************************************************************/
+
+} // namespace stlab
+
+/**************************************************************************************************/
+
+#endif
+
+/**************************************************************************************************/
diff --git a/stlab/utility.hpp b/stlab/utility.hpp
@@ -0,0 +1,127 @@
+/*
+ Copyright 2017 Adobe
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+*/
+
+/**************************************************************************************************/
+
+#ifndef STLAB_UTILITY_HPP
+#define STLAB_UTILITY_HPP
+
+/**************************************************************************************************/
+
+#include <array>
+#include <type_traits>
+
+/**************************************************************************************************/
+
+namespace stlab {
+
+/**************************************************************************************************/
+
+inline namespace v1 {
+/**************************************************************************************************/
+
+namespace detail {
+
+/**************************************************************************************************/
+
+template <bool, class T>
+struct move_if_helper;
+
+template <class T>
+struct move_if_helper<true, T> {
+ using type = std::remove_reference_t<T>&&;
+};
+
+template <class T>
+struct move_if_helper<false, T> {
+ using type = std::remove_reference_t<T>&;
+};
+
+template <bool P, class T>
+using move_if_helper_t = typename move_if_helper<P, T>::type;
+
+/**************************************************************************************************/
+
+} // namespace detail
+
+/**************************************************************************************************/
+
+template <class Seq1, class Seq2>
+struct index_sequence_cat;
+
+template <std::size_t... N1, std::size_t... N2>
+struct index_sequence_cat<std::index_sequence<N1...>, std::index_sequence<N2...>> {
+ using type = std::index_sequence<N1..., N2...>;
+};
+
+template <class Seq1, class Seq2>
+using index_sequence_cat_t = typename index_sequence_cat<Seq1, Seq2>::type;
+
+/**************************************************************************************************/
+
+template <class Seq>
+struct index_sequence_to_array;
+
+template <std::size_t... N>
+struct index_sequence_to_array<std::index_sequence<N...>> {
+ static constexpr std::array<std::size_t, sizeof...(N)> value{{N...}};
+};
+
+/**************************************************************************************************/
+
+template <class Seq, template <std::size_t> class F, std::size_t Index, std::size_t Count>
+struct index_sequence_transform;
+
+template <class Seq,
+ template <std::size_t> class F,
+ std::size_t Index = 0,
+ std::size_t Count = Seq::size()>
+using index_sequence_transform_t = typename index_sequence_transform<Seq, F, Index, Count>::type;
+
+template <class Seq, template <std::size_t> class F, std::size_t Index, std::size_t Count>
+struct index_sequence_transform {
+ using type = index_sequence_cat_t<
+ index_sequence_transform_t<Seq, F, Index, Count / 2>,
+ index_sequence_transform_t<Seq, F, Index + Count / 2, Count - Count / 2>>;
+};
+
+template <class Seq, template <std::size_t> class F, std::size_t Index>
+struct index_sequence_transform<Seq, F, Index, 0> {
+ using type = std::index_sequence<>;
+};
+
+template <class Seq, template <std::size_t> class F, std::size_t Index>
+struct index_sequence_transform<Seq, F, Index, 1> {
+ using type = typename F<index_sequence_to_array<Seq>::value[Index]>::type;
+};
+
+/**************************************************************************************************/
+
+template <bool P, class T>
+constexpr detail::move_if_helper_t<P, T> move_if(T&& t) noexcept {
+ return static_cast<detail::move_if_helper_t<P, T>>(t);
+}
+
+/**************************************************************************************************/
+
+template <class F, class... Args>
+void for_each_argument(F&& f, Args&&... args) {
+ return (void)std::initializer_list<int>{(std::forward<F>(f)(args), 0)...};
+}
+
+/**************************************************************************************************/
+
+} // namespace v1
+
+/**************************************************************************************************/
+
+} // namespace stlab
+
+/**************************************************************************************************/
+
+#endif
+
+/**************************************************************************************************/
diff --git a/stlab/version.hpp b/stlab/version.hpp
@@ -0,0 +1,31 @@
+/*
+ Copyright 2015 Adobe
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+*/
+
+// See http://www.stlab.cc for documentation
+
+#ifndef STLAB_VERSION_HPP
+#define STLAB_VERSION_HPP
+
+//
+// Caution: this is the only stlab header that is guaranteed
+// to change with every stlab release. Including this header
+// will cause a recompile every time a new stlab version is
+// used.
+//
+// STLAB_VERSION % 100 is the patch level
+// STLAB_VERSION / 100 % 1000 is the minor version
+// STLAB_VERSION / 100000 is the major version
+
+#define STLAB_VERSION 100602
+
+//
+// STLAB_LIB_VERSION must be defined to be the same as STLAB_VERSION
+// but as a *string* in the form "x_y[_z]" where x is the major version
+// number, y is the minor version number, and z is the patch level if not 0.
+
+#define STLAB_LIB_VERSION "1_6_2"
+
+#endif
