toctave

t(iny)octave
git clone https://0xff.ir/g/toctave.git
Log | Files | Refs | README

forest_algorithms.hpp (4780B)

      1 /**************************************************************************************************/
      2 
      3 #ifndef STLAB_FOREST_ALGORITHMS_HPP
      4 #define STLAB_FOREST_ALGORITHMS_HPP
      5 
      6 /**************************************************************************************************/
      7 
      8 // stlab
      9 #include <stlab/concurrency/optional.hpp>
     10 #include <stlab/forest.hpp>
     11 
     12 /**************************************************************************************************/
     13 
     14 namespace stlab {
     15 
     16 /**************************************************************************************************/
     17 
     18 namespace forests {
     19 
     20 /**************************************************************************************************/
     21 // "Congruent" would be a nice name here, but in geometry that also implies reflection.
     22 template <class Forest1, class Forest2>
     23 bool equal_shape(const Forest1& x, const Forest2& y) {
     24     if (x.size_valid() && y.size_valid() && x.size() != y.size()) return false;
     25     auto pos{y.begin()};
     26     for (auto first(x.begin()), last(x.end()); first != last; ++first, ++pos) {
     27         if (first.edge() != pos.edge()) return false;
     28     }
     29     return true;
     30 }
     31 
     32 /**************************************************************************************************/
     33 
     34 template <class Container>
     35 struct transcribe_iterator {
     36     using iterator_category = std::output_iterator_tag;
     37     using value_type = void;
     38     using difference_type = void;
     39     using pointer = void;
     40     using reference = void;
     41     using container_type = Container;
     42 
     43     transcribe_iterator(Container& c, typename Container::iterator i) : _c{&c}, _i{std::move(i)} {}
     44 
     45     constexpr auto& operator*() { return *this; }
     46     constexpr auto& operator++() {
     47         ++_i;
     48         return *this;
     49     }
     50     constexpr auto operator++(int) {
     51         auto result{*this};
     52         ++_i;
     53         return result;
     54     }
     55 
     56     constexpr auto& operator=(const typename Container::value_type& value) {
     57         _i = _c->insert(_i, value);
     58         return *this;
     59     }
     60 
     61     constexpr auto& operator=(typename Container::value_type&& value) {
     62         _i = _c->insert(_i, std::move(value));
     63         return *this;
     64     }
     65 
     66     constexpr auto trailing() { _i = trailing_of(_i); }
     67 
     68 private:
     69     Container* _c;
     70     typename Container::iterator _i;
     71 };
     72 
     73 template <class Container>
     74 auto transcriber(Container& c) {
     75     return transcribe_iterator<Container>(c, c.begin());
     76 }
     77 
     78 /**************************************************************************************************/
     79 
     80 template <class I, class O, class P, class UP>
     81 auto transcribe(I first, I last, O out, P proj, UP pred) {
     82     for (; first != last; ++first, ++out) {
     83         if (pred(first)) {
     84             out = proj(*first);
     85         } else {
     86             out.trailing();
     87         }
     88     }
     89     return out;
     90 }
     91 
     92 template <class R, class O, class P, class UP>
     93 auto transcribe(const R& range, O out, P proj, UP pred) {
     94     return transcribe(std::cbegin(range), std::cend(range), std::move(out), std::move(proj),
     95                       std::move(pred));
     96 }
     97 
     98 template <class I, class O, class P>
     99 auto transcribe(I first, I last, O out, P proj) {
    100     return transcribe(std::move(first), std::move(last), std::move(out), std::move(proj),
    101                       [](const auto& p) { return is_leading(p); });
    102 }
    103 
    104 template <class R, class O, class P>
    105 auto transcribe(const R& range, O out, P proj) {
    106     return transcribe(std::cbegin(range), std::cend(range), std::move(out), std::move(proj));
    107 }
    108 
    109 /**************************************************************************************************/
    110 
    111 template <class I, // models ForestFullorderIterator
    112           class O> // models OutputIterator
    113 auto flatten(I first, I last, O out) {
    114     for (; first != last; ++first) {
    115         if (is_leading(first)) {
    116             *out++ = *first;
    117         } else {
    118             *out++ = nullopt;
    119         }
    120     }
    121     return out;
    122 }
    123 
    124 /**************************************************************************************************/
    125 
    126 template <class I, // I models ForwardIterator; I::value_type == stlab::optional<T>
    127           class F> // F models Forest
    128 auto unflatten(I first, I last, F& f) {
    129     return forests::transcribe(
    130         first, last, transcriber(f), [](const auto& x) { return *x; },
    131         [](const auto& p) { return *p; });
    132 }
    133 
    134 /**************************************************************************************************/
    135 
    136 } // namespace forests
    137 
    138 /**************************************************************************************************/
    139 
    140 } // namespace stlab
    141 
    142 /**************************************************************************************************/
    143 
    144 #endif // STLAB_FOREST_ALGORITHMS_HPP
    145 
    146 /**************************************************************************************************/