SHARE
TWEET

Untitled

a guest Apr 24th, 2019 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <utility>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <vector>
  5. #include <optional>
  6.  
  7. namespace library {
  8.  
  9. using node_ref = std::size_t;
  10.  
  11. enum direction { down, up };
  12. template <typename T> struct node_t;
  13. template <typename T> struct forest_iterator;
  14. template <typename T> struct child_iterator;
  15.  
  16. template <typename T>
  17. struct forest {
  18.   node_ref add(T value);
  19.   node_ref add_child(node_ref ref, T value);
  20.   node_ref add_sibling(node_ref ref, T value);
  21.   node_ref remove(node_ref ref);
  22.  
  23.   forest_iterator<T> begin() {
  24.     if (!pool.size()) return forest_iterator<T>();
  25.     // assume root will always be in the 0 index
  26.     return forest_iterator<T>(this, node_ref(0), node_ref(0));
  27.   }
  28.   forest_iterator<T> end() {
  29.     if (!pool.size()) return forest_iterator<T>();
  30.     // assume root will always be in the 0 index
  31.     return forest_iterator<T>(this, node(0).a12, node_ref(0));
  32.   }
  33.  
  34.   forest_iterator<T> begin(node_ref ref) { return forest_iterator<T>(this, ref, node(ref).a11); }
  35.   forest_iterator<T> end(node_ref ref) { return forest_iterator<T>(this, node(ref).a12, ref); }
  36.  
  37.   child_iterator<T> begin_child(node_ref ref = 0) {
  38.     if (!pool.size()) return child_iterator<T>();
  39.     return child_iterator<T>(this, node(ref).a21, ref);
  40.   }
  41.   child_iterator<T> end_child(node_ref ref = 0) {
  42.     if (!pool.size()) return child_iterator<T>();
  43.     return child_iterator<T>(this, ref, node(ref).a22);
  44.   }
  45.  
  46.   node_ref next_free(T&& value) {
  47.     auto p = try_used_space();
  48.     if (p) {
  49.       pool[*p] = node_t<T> {std::forward<T>(value), *p, *p, *p, *p};
  50.       return *p;
  51.     }
  52.     auto i = pool.size();
  53.     pool.push_back(node_t<T> {std::forward<T>(value), i, i, i, i});
  54.     return i;
  55.   }
  56.  
  57.   std::optional<node_ref> try_used_space();
  58.   void free(node_ref ref) { deleted_set.push_back({node(ref).a21, ref}); }
  59.   node_t<T>& node(node_ref ref) { return pool[ref]; }
  60.   const node_t<T>& node(node_ref ref) const { return pool[ref]; }
  61.   bool is_leaf(node_ref ref) { return ref == node(ref).a21 && ref == node(ref).a22; }
  62.   void link_parent_child(node_ref, node_ref);
  63.   void link_siblings(node_ref, node_ref);
  64.  
  65.   std::vector<node_t<T>> pool;
  66.   std::vector<std::pair<node_ref, node_ref>> deleted_set; // [f,l]
  67. };
  68.  
  69. /*---------- node --------------*/
  70.  
  71. template <typename T>
  72. struct node_t {
  73.   T value;
  74.   node_ref a11, a12, a21, a22;
  75.   /*    a11 | a12
  76.         ---- ----
  77.         a21 | a22    */
  78. };
  79.  
  80. /* ------ forest ---------- */
  81.  
  82. template <typename T>
  83. node_ref forest<T>::add(T value) {
  84.   auto next = next_free(std::move(value));
  85.   node(next).a12 = node_ref(-1); // root's last value
  86.   return next;
  87. }
  88.  
  89. template <typename T>
  90. node_ref forest<T>::add_child(node_ref ref, T value) {
  91.   // assert ref in [0, pool.size())
  92.   auto next = next_free(std::move(value));
  93.   if (is_leaf(ref)) link_parent_child(ref, next);
  94.   else link_siblings(node(ref).a22, next);
  95.   return next;
  96. }
  97.  
  98. template <typename T>
  99. node_ref forest<T>::add_sibling(node_ref ref, T value) {
  100.   // assert ref in [0, pool.size())
  101.   auto next = next_free(std::move(value));
  102.   link_siblings(ref, next);
  103.   return next;
  104. }
  105.  
  106. template <typename T>
  107. node_ref forest<T>::remove(node_ref ref) {
  108.   if (node(ref).a12 == node_ref(-1)) { // root
  109.     free(ref);
  110.     node(ref) = node_t<T> {T(), 0, node_ref(-1), 0, 0};
  111.     return node_ref(-1);
  112.   }
  113.   auto prev = node(ref).a11;
  114.   auto next = node(ref).a12;
  115.   bool is_sibling_left = node(prev).a12 == ref;
  116.   bool is_sibling_right = node(next).a11 == ref;
  117.  
  118.   if (is_sibling_left) node(prev).a12 = next;
  119.   else node(prev).a21 = next; // parent on the left
  120.   if (is_sibling_right) node(next).a11 = prev;
  121.   else node(next).a22 = prev; // parent on the right
  122.   free(ref);
  123.   return next;
  124. }
  125.  
  126. template <typename T>
  127. std::optional<node_ref> forest<T>::try_used_space() {
  128.   if (!deleted_set.size()) { return {}; }
  129.   auto& back = deleted_set.back();
  130.   node_ref first(back.first);
  131.   node_ref last(back.second);
  132.   if (first == last) { // just one elem
  133.     deleted_set.pop_back();
  134.     return {first};
  135.   }
  136.   if (!is_leaf(first)) {
  137.     auto next = node(first).a12;
  138.     auto prev = node(first).a22;
  139.     node(next).a11 = prev;
  140.     node(prev).a12 = next;
  141.   }
  142.   back.first = is_leaf(first) ? node(first).a12 : node(first).a21;
  143.   return {first};
  144. }
  145.  
  146. template <typename T>
  147. void forest<T>::link_parent_child(node_ref parent, node_ref child) {
  148.   node(parent).a21 = child;
  149.   node(parent).a22 = child;
  150.   node(child).a11 = parent;
  151.   node(child).a12 = parent;
  152. }
  153.  
  154. template <typename T>
  155. void forest<T>::link_siblings(node_ref x, node_ref y) {
  156.   auto next = node(x).a12;
  157.   if (x == node(next).a22) node(next).a22 = y;
  158.   else node(next).a11 = y;
  159.   node(x).a12 = y;
  160.   node(y).a12 = next;
  161.   node(y).a11 = x;
  162. }
  163.  
  164. /*----------- algorithms  -------- */
  165.  
  166. /*
  167.   dir:
  168.     down --> pre-order
  169.     up --> post-order
  170. */
  171. template <typename I, typename Op>
  172. void traverse(I f, I l, direction dir, Op op) {
  173.   while (f != l) {
  174.     if (f.dir() == dir) op(*f);
  175.     ++f;
  176.   }
  177. }
  178.  
  179. template <typename I, typename Op>
  180. void traverse(I f, I l, Op op) {
  181.   while (f != l) { op(*f); ++f; }
  182. }
  183.  
  184. template <typename I, typename Op>
  185. void traverse_back(I f, I l, Op op) {
  186.   while (f != l) { --l; op(*l); }
  187. }
  188.  
  189. /* ------------ forest_iterator --------- */
  190.  
  191. template <typename T>
  192. struct forest_iterator {
  193.   typedef typename std::iterator_traits<forest_iterator<T>>::pointer pointer;
  194.   typedef typename std::iterator_traits<forest_iterator<T>>::reference reference;
  195.   forest_iterator() = default;
  196.   forest_iterator(const forest_iterator<T>& x) = default;
  197.   forest_iterator<T>& operator=(const forest_iterator<T>& x) = default;
  198.   forest_iterator(forest<T>* f, node_ref ref, node_ref prev)
  199.     : f(f), ref(ref), prev(prev) { }
  200.   forest_iterator& operator++() { next(); return *this; }
  201.   forest_iterator operator++(int) { auto tmp = *this; next(); return tmp; }
  202.   forest_iterator& operator--() { previous(); return *this; }
  203.   forest_iterator operator--(int) { auto tmp = *this; previous(); return tmp; }
  204.   const reference operator*() const { return (*f).node(ref).value; }
  205.   reference operator*() { return (*f).node(ref).value; }
  206.   pointer operator->() const { return &(*f).node(ref).value; }
  207.   void next();
  208.   void previous();
  209.   direction dir() const { return (*f).node(ref).a11 == prev ? down : up; }
  210.  
  211.   forest<T>* f;
  212.   node_ref ref;
  213.   node_ref prev;
  214. };
  215.  
  216. template <typename T>
  217. void forest_iterator<T>::next() {
  218.   if ((*f).node(ref).a11 == prev) {
  219.     prev = ref; ref = (*f).node(ref).a21;
  220.   } else {
  221.     prev = ref; ref = (*f).node(ref).a12;
  222.   }
  223. }
  224.  
  225. template <typename T>
  226. void forest_iterator<T>::previous() {
  227.   if ((*f).node(prev).a21 == ref) {
  228.     ref = prev; prev = (*f).node(prev).a11;
  229.   } else {
  230.     ref = prev; prev = (*f).node(prev).a22;
  231.   }
  232. }
  233.  
  234. template <typename T>
  235. bool operator==(const forest_iterator<T>& i, const forest_iterator<T>& j) {
  236.   return i.ref == j.ref && i.dir() == j.dir();
  237. }
  238.  
  239. template <typename T>
  240. bool operator!=(const forest_iterator<T>& i, const forest_iterator<T>& j) {
  241.   return !(i == j);
  242. }
  243.  
  244. /* ------------ child_iterator --------- */
  245.  
  246. template <typename T>
  247. struct child_iterator {
  248.   typedef typename std::iterator_traits<child_iterator<T>>::pointer pointer;
  249.   typedef typename std::iterator_traits<child_iterator<T>>::reference reference;
  250.   child_iterator() = default;
  251.   child_iterator(const child_iterator<T>& x) = default;
  252.   child_iterator<T>& operator=(const child_iterator<T>& x) = default;
  253.   child_iterator(forest<T>* f, node_ref ref, node_ref prev) : f(f), ref(ref), prev(prev) {}
  254.   child_iterator& operator++() { next(); return *this; }
  255.   child_iterator operator++(int) { auto tmp = *this; next(); return tmp; }
  256.   child_iterator operator--(int) { auto tmp = *this; previous(); return tmp; }
  257.   child_iterator operator--() { previous(); return *this; }
  258.   const reference operator*() const { return (*f).node(ref).value; }
  259.   reference operator*() { return (*f).node(ref).value; }
  260.   pointer operator->() const { return &(*f).node(ref).value; }
  261.   void next() { prev = ref; ref = (*f).node(ref).a12; }
  262.   void previous() { ref = prev; prev = (*f).node(prev).a11; }
  263.  
  264.   forest<T> *f;
  265.   node_ref ref;
  266.   node_ref prev;
  267. };
  268.  
  269. template <typename T>
  270. bool operator==(const child_iterator<T>& i, const child_iterator<T>& j) {
  271.   return i.ref == j.ref;
  272. }
  273.  
  274. template <typename T>
  275. bool operator!=(const child_iterator<T>& i, const child_iterator<T>& j) {
  276.   return !(i == j);
  277. }
  278.  
  279. }; // namespace library
  280.  
  281. template <typename T>
  282. struct std::iterator_traits<library::forest_iterator<T>> {
  283.   typedef std::ptrdiff_t difference_type;
  284.   typedef T value_type;
  285.   typedef T& reference;
  286.   typedef T* pointer;
  287.   typedef std::bidirectional_iterator_tag iterator_category;
  288. };
  289.  
  290. template <typename T>
  291. struct std::iterator_traits<library::child_iterator<T>> {
  292.   typedef std::ptrdiff_t difference_type;
  293.   typedef T value_type;
  294.   typedef T& reference;
  295.   typedef T* pointer;
  296.   typedef std::bidirectional_iterator_tag iterator_category;
  297. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top