src/ds/bst/ost/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | #include "../../bt_trv/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | namespace ostnode_impl_ { | ||
| 8 | template <class T, class K> | ||
| 9 | struct ostree_node_t {}; | ||
| 10 | } // namespace ostnode_impl_ | ||
| 11 | namespace ost_impl_ { | ||
| 12 | struct ostree_tag_base { | ||
| 13 | template <tp2_ds_c pointer> | ||
| 14 |
6/6unsigned int tifa_libs::ost_impl_::ostree_tag_base::size<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*):
✓ Branch 0 taken 2144307 times.
✓ Branch 1 taken 326861 times.
unsigned int tifa_libs::ost_impl_::ostree_tag_base::size<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*):
✓ Branch 0 taken 1838881 times.
✓ Branch 1 taken 2709899 times.
unsigned int tifa_libs::ost_impl_::ostree_tag_base::size<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*):
✓ Branch 0 taken 164673896 times.
✓ Branch 1 taken 15516631 times.
|
187210475 | static CEXP u32 size(pointer p) NE { retif_((p), p->sz, 0); } |
| 15 | template <tp2_ds_c pointer> | ||
| 16 |
4/8unsigned int tifa_libs::ost_impl_::ostree_tag_base::count<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> const*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> const*):
✓ Branch 0 taken 474922 times.
✗ Branch 1 not taken.
unsigned int tifa_libs::ost_impl_::ostree_tag_base::count<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*):
✓ Branch 0 taken 347016 times.
✗ Branch 1 not taken.
unsigned int tifa_libs::ost_impl_::ostree_tag_base::count<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> const*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> const*):
✓ Branch 0 taken 35826998 times.
✗ Branch 1 not taken.
unsigned int tifa_libs::ost_impl_::ostree_tag_base::count<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*):
✓ Branch 0 taken 20903657 times.
✗ Branch 1 not taken.
|
57552593 | static CEXP u32 count(pointer p) NE { retif_((p), p->sz - size(p->ch[0]) - size(p->ch[1]), 0); } |
| 17 | // [size(begin), size(begin->fa), ..., size(end)) += v | ||
| 18 | template <tp2_ds_c pointer> | ||
| 19 | 15958950 | static CEXP void modify_size(pointer begin, i32 v, pointer end = nullptr) NE { | |
| 20 |
6/6void tifa_libs::ost_impl_::ostree_tag_base::modify_size<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, int, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*):
✓ Branch 0 taken 3042836 times.
✓ Branch 1 taken 232599 times.
void tifa_libs::ost_impl_::ostree_tag_base::modify_size<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*, int, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*):
✓ Branch 0 taken 142522060 times.
✓ Branch 1 taken 5873836 times.
void tifa_libs::ost_impl_::ostree_tag_base::modify_size<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, int, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*):
✓ Branch 0 taken 282361294 times.
✓ Branch 1 taken 9852515 times.
|
443885140 | while (begin != end) begin->sz += (u32)v, begin = begin->fa; |
| 21 | 15958950 | } | |
| 22 | |||
| 23 | template <tp2_ds_c pointer> | ||
| 24 | 2193717 | static CEXP pointer neighbour(pointer p, bool dir) NE { | |
| 25 |
2/4tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>* tifa_libs::ost_impl_::ostree_tag_base::neighbour<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, bool):
✗ Branch 0 not taken.
✓ Branch 1 taken 55305 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>* tifa_libs::ost_impl_::ostree_tag_base::neighbour<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, bool):
✗ Branch 0 not taken.
✓ Branch 1 taken 2138412 times.
|
2193717 | if (!p) return nullptr; |
| 26 |
4/4tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>* tifa_libs::ost_impl_::ostree_tag_base::neighbour<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, bool):
✓ Branch 0 taken 20654 times.
✓ Branch 1 taken 34651 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>* tifa_libs::ost_impl_::ostree_tag_base::neighbour<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, bool):
✓ Branch 0 taken 730372 times.
✓ Branch 1 taken 1408040 times.
|
2193717 | if (p->ch[dir]) return most(p->ch[dir], !dir); |
| 27 |
14/16tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>* tifa_libs::ost_impl_::ostree_tag_base::neighbour<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, bool):
✓ Branch 0 taken 68683 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 68669 times.
✓ Branch 3 taken 14 times.
✓ Branch 5 taken 34032 times.
✓ Branch 6 taken 34637 times.
✓ Branch 7 taken 34032 times.
✓ Branch 8 taken 34651 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>* tifa_libs::ost_impl_::ostree_tag_base::neighbour<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, bool):
✓ Branch 0 taken 6077830 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 5619632 times.
✓ Branch 3 taken 458198 times.
✓ Branch 5 taken 4669790 times.
✓ Branch 6 taken 949842 times.
✓ Branch 7 taken 4669790 times.
✓ Branch 8 taken 1408040 times.
|
6146513 | while (p && p->fa && p->child_dir() == dir) p = p->fa; |
| 28 |
2/4tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>* tifa_libs::ost_impl_::ostree_tag_base::neighbour<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, bool):
✓ Branch 0 taken 34651 times.
✗ Branch 1 not taken.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>* tifa_libs::ost_impl_::ostree_tag_base::neighbour<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, bool):
✓ Branch 0 taken 1408040 times.
✗ Branch 1 not taken.
|
1442691 | retif_((p), p->fa, nullptr); |
| 29 | } | ||
| 30 | template <tp2_ds_c pointer> | ||
| 31 | 1713443 | static CEXP auto prev(pointer p) NE { return neighbour(p, 0); } | |
| 32 | template <tp2_ds_c pointer> | ||
| 33 | 480274 | static CEXP auto next(pointer p) NE { return neighbour(p, 1); } | |
| 34 | |||
| 35 | template <tp2_ds_c pointer> | ||
| 36 | 12963244 | static CEXP pointer rotate(pointer& root, pointer p, bool dir) NE { | |
| 37 | 12963244 | auto g = p->fa, s = p->ch[!dir]; | |
| 38 | 12963244 | u32 psz = p->sz, ssz = s->sz; | |
| 39 | 12963244 | s->sz = psz, p->sz += size(s->ch[dir]) - ssz; | |
| 40 | 12963244 | auto c = s->ch[dir]; | |
| 41 |
6/6tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>* tifa_libs::ost_impl_::ostree_tag_base::rotate<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, bool):
✓ Branch 0 taken 26634 times.
✓ Branch 1 taken 79493 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >* tifa_libs::ost_impl_::ostree_tag_base::rotate<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*, bool):
✓ Branch 0 taken 1838881 times.
✓ Branch 1 taken 2709899 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>* tifa_libs::ost_impl_::ostree_tag_base::rotate<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, bool):
✓ Branch 0 taken 4054232 times.
✓ Branch 1 taken 4254105 times.
|
12963244 | if (c) c->fa = p; |
| 42 | 12963244 | p->ch[!dir] = c, s->ch[dir] = p, p->fa = s, s->fa = g; | |
| 43 |
6/6tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>* tifa_libs::ost_impl_::ostree_tag_base::rotate<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, bool):
✓ Branch 0 taken 106108 times.
✓ Branch 1 taken 19 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >* tifa_libs::ost_impl_::ostree_tag_base::rotate<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*, bool):
✓ Branch 0 taken 4548637 times.
✓ Branch 1 taken 143 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>* tifa_libs::ost_impl_::ostree_tag_base::rotate<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, bool):
✓ Branch 0 taken 8301544 times.
✓ Branch 1 taken 6793 times.
|
12963244 | (g ? g->ch[p == g->ch[1]] : root) = s; |
| 44 | 12963244 | return s; | |
| 45 | } | ||
| 46 | }; | ||
| 47 | //! will NOT change sz | ||
| 48 | struct bst_op_leaf : ostree_tag_base { | ||
| 49 | template <tp2_ds_c pointer> | ||
| 50 | 14883892 | static CEXP void insert_leaf(pointer& root, pointer p, pointer n, bool dir) NE { | |
| 51 |
6/6void tifa_libs::ost_impl_::bst_op_leaf::insert_leaf<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, bool):
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 171932 times.
void tifa_libs::ost_impl_::bst_op_leaf::insert_leaf<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*, bool):
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 5873816 times.
void tifa_libs::ost_impl_::bst_op_leaf::insert_leaf<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, bool):
✓ Branch 0 taken 72972 times.
✓ Branch 1 taken 8765142 times.
|
14883892 | if (!p) return void(root = n); |
| 52 | 14810890 | p->ch[dir] = n, n->fa = p; | |
| 53 | } | ||
| 54 | template <tp2_ds_c pointer> | ||
| 55 | 772056 | static CEXP void erase_branch_leaf(pointer& root, pointer n) NE { | |
| 56 |
4/4void tifa_libs::ost_impl_::bst_op_leaf::erase_branch_leaf<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*):
✓ Branch 0 taken 2510 times.
✓ Branch 1 taken 32242 times.
void tifa_libs::ost_impl_::bst_op_leaf::erase_branch_leaf<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*):
✓ Branch 0 taken 42227 times.
✓ Branch 1 taken 695077 times.
|
772056 | auto p = n->fa, s = n->ch[0] ? n->ch[0] : n->ch[1]; |
| 57 |
4/4void tifa_libs::ost_impl_::bst_op_leaf::erase_branch_leaf<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*):
✓ Branch 0 taken 7704 times.
✓ Branch 1 taken 27048 times.
void tifa_libs::ost_impl_::bst_op_leaf::erase_branch_leaf<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*):
✓ Branch 0 taken 118413 times.
✓ Branch 1 taken 618891 times.
|
772056 | if (s) s->fa = p; |
| 58 |
4/4void tifa_libs::ost_impl_::bst_op_leaf::erase_branch_leaf<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*):
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 34750 times.
void tifa_libs::ost_impl_::bst_op_leaf::erase_branch_leaf<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*>(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*):
✓ Branch 0 taken 93721 times.
✓ Branch 1 taken 643583 times.
|
772056 | if (!p) return void(root = s); |
| 59 | 678333 | p->ch[n->child_dir()] = s; | |
| 60 | } | ||
| 61 | }; | ||
| 62 | template <class leaf> | ||
| 63 | struct bst_op : leaf { | ||
| 64 | using tag_t = ostree_tag_base; | ||
| 65 | template <tp2_ds_c pointer, class K, class Alloc, class Comp> | ||
| 66 | 14893213 | CEXP pointer insert(pointer& root, const K& data, Alloc& alloc, Comp compare) NE { | |
| 67 | 14893213 | pointer now = root, p = nullptr; | |
| 68 | 14893213 | bool dir = false; | |
| 69 |
6/6tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>* tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>::insert<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, int, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> >, std::less<int> >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*&, int const&, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> >&, std::less<int>):
✓ Branch 0 taken 2507152 times.
✓ Branch 1 taken 171942 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >* tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>::insert<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*, std::pair<unsigned long, unsigned long>, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> > >, std::less<std::pair<unsigned long, unsigned long> > >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*&, std::pair<unsigned long, unsigned long> const&, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> > >&, std::less<std::pair<unsigned long, unsigned long> >):
✓ Branch 0 taken 142522060 times.
✓ Branch 1 taken 5873836 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>* tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>::insert<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, unsigned int, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> >, std::less<unsigned int> >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*&, unsigned int const&, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> >&, std::less<unsigned int>):
✓ Branch 0 taken 271386080 times.
✓ Branch 1 taken 8838114 times.
|
431299184 | while (now) |
| 70 |
14/18tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>* tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>::insert<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, int, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> >, std::less<int> >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*&, int const&, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> >&, std::less<int>):
✓ Branch 1 taken 1264293 times.
✓ Branch 2 taken 1242859 times.
✓ Branch 4 taken 9321 times.
✓ Branch 5 taken 1254972 times.
✓ Branch 6 taken 9321 times.
✓ Branch 7 taken 2497831 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >* tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>::insert<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*, std::pair<unsigned long, unsigned long>, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> > >, std::less<std::pair<unsigned long, unsigned long> > >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> >*&, std::pair<unsigned long, unsigned long> const&, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::pair<unsigned long, unsigned long> > >&, std::less<std::pair<unsigned long, unsigned long> >):
✓ Branch 1 taken 27921335 times.
✓ Branch 2 taken 114600725 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 27921335 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 142522060 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>* tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>::insert<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, unsigned int, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> >, std::less<unsigned int> >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*&, unsigned int const&, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> >&, std::less<unsigned int>):
✓ Branch 1 taken 6147103 times.
✓ Branch 2 taken 265238977 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 6147103 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 271386080 times.
|
416415292 | if (dir = compare((p = now)->data, data), now = now->ch[dir]; !dir && !compare(data, p->data)) { |
| 71 | 9321 | tag_t::modify_size(p, 1); | |
| 72 | 9321 | return p; | |
| 73 | } | ||
| 74 | 14883892 | pointer n = alloc.allocate(1); | |
| 75 | 14883892 | n->fa = n->ch[0] = n->ch[1] = nullptr, n->data = data, n->sz = 1; | |
| 76 | 14883892 | tag_t::modify_size(p, 1), leaf::insert_leaf(root, p, n, dir); | |
| 77 | 14883892 | return n; | |
| 78 | } | ||
| 79 | template <tp2_ds_c pointer, class Alloc> | ||
| 80 | 772056 | CEXP pointer erase(pointer& root, pointer p, Alloc& alloc) NE { | |
| 81 |
2/4tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>* tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>::erase<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> > >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> >&):
✗ Branch 0 not taken.
✓ Branch 1 taken 34752 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>* tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>::erase<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> > >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> >&):
✗ Branch 0 not taken.
✓ Branch 1 taken 737304 times.
|
772056 | if (!p) return nullptr; |
| 82 | pointer result; | ||
| 83 |
8/8tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>* tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>::erase<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> > >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, int> >&):
✓ Branch 0 taken 17195 times.
✓ Branch 1 taken 17557 times.
✓ Branch 2 taken 14685 times.
✓ Branch 3 taken 2510 times.
tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>* tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>::erase<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> > >(tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*&, tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int>*, std::pmr::polymorphic_allocator<tifa_libs::ostnode_impl_::ostree_node_t<tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, unsigned int> >&):
✓ Branch 0 taken 319324 times.
✓ Branch 1 taken 417980 times.
✓ Branch 2 taken 277097 times.
✓ Branch 3 taken 42227 times.
|
772056 | if (p->ch[0] && p->ch[1]) { |
| 84 | 291782 | auto s = leftmost(p->ch[1]); | |
| 85 | 291782 | std::swap(s->data, p->data); | |
| 86 | 291782 | tag_t::modify_size(s, (i32)tag_t::count(p) - (i32)tag_t::count(s), p); | |
| 87 | 291782 | result = p, p = s; | |
| 88 | 772056 | } else result = tag_t::next(p); | |
| 89 | 772056 | tag_t::modify_size(p, -(i32)tag_t::count(p)); | |
| 90 | 772056 | leaf::erase_branch_leaf(root, p), alloc.deallocate(p, 1); | |
| 91 | 772056 | return result; | |
| 92 | } | ||
| 93 | }; | ||
| 94 | using bst_tag = bst_op<bst_op_leaf>; | ||
| 95 | } // namespace ost_impl_ | ||
| 96 | namespace ostnode_impl_ { | ||
| 97 | template <class K> | ||
| 98 | struct ostree_node_t<ost_impl_::bst_tag, K> { | ||
| 99 | ostree_node_t *fa, *ch[2]; // NOLINT(modernize-avoid-c-arrays) | ||
| 100 | K data; | ||
| 101 | u32 sz; | ||
| 102 | // @return child direction of this non-root point | ||
| 103 | ND CEXP bool child_dir() CNE { return this == fa->ch[1]; } | ||
| 104 | }; | ||
| 105 | } // namespace ostnode_impl_ | ||
| 106 | namespace ost_impl_ { | ||
| 107 | using namespace ostnode_impl_; | ||
| 108 | template <class K, std::derived_from<ostree_tag_base> tag_t, class Comp = std::less<K>> | ||
| 109 | requires requires(ostree_node_t<tag_t, K>*& root, ostree_node_t<tag_t, K> n, tag_t tag, bool dir, K key, alc<ostree_node_t<tag_t, K>> alloc, Comp comp) { | ||
| 110 | n.fa->ch[0]->ch[1]->data; | ||
| 111 | n.sz; | ||
| 112 | { comp(key, key) } -> std::same_as<bool>; | ||
| 113 | { n.child_dir() } -> std::same_as<bool>; | ||
| 114 | { tag.size(&n) } -> std::same_as<u32>; | ||
| 115 | tag.insert(root, key, alloc, comp); | ||
| 116 | tag.erase(root, &n, alloc); | ||
| 117 | } | ||
| 118 | struct ostree : tag_t { | ||
| 119 | using node_t = ostree_node_t<tag_t, K>; | ||
| 120 | using pointer = node_t*; | ||
| 121 | using const_pointer = node_t CP; | ||
| 122 | using pointer_const = node_t PC; | ||
| 123 | |||
| 124 | static CEXP Comp compare{}; | ||
| 125 | pointer root{nullptr}; | ||
| 126 | |||
| 127 | 67 | CEXP ostree() NE = default; | |
| 128 | ostree(ostree CR) = delete; | ||
| 129 | ostree& operator=(ostree CR) = delete; | ||
| 130 | 67 | CEXP ~ostree() NE { dealloc_subtree(root, alloc); } | |
| 131 | 2981723 | ND CEXP u32 size() CNE { return tag_t::size(root); } | |
| 132 | |||
| 133 | 33245265 | CEXP pointer lower_bound(const K& key) CNE { | |
| 134 | 33245265 | const_pointer now = root, ans = nullptr; | |
| 135 |
6/6tifa_libs::ost_impl_::ostree<int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<int> >::lower_bound(int const&) const:
✓ Branch 0 taken 1001331 times.
✓ Branch 1 taken 72081 times.
tifa_libs::ost_impl_::ostree<std::pair<unsigned long, unsigned long>, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<std::pair<unsigned long, unsigned long> > >::lower_bound(std::pair<unsigned long, unsigned long> const&) const:
✓ Branch 0 taken 338757690 times.
✓ Branch 1 taken 15673163 times.
tifa_libs::ost_impl_::ostree<unsigned int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<unsigned int> >::lower_bound(unsigned int const&) const:
✓ Branch 0 taken 225469213 times.
✓ Branch 1 taken 17500021 times.
|
598473499 | while (now) { |
| 136 |
6/6tifa_libs::ost_impl_::ostree<int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<int> >::lower_bound(int const&) const:
✓ Branch 1 taken 502080 times.
✓ Branch 2 taken 499251 times.
tifa_libs::ost_impl_::ostree<std::pair<unsigned long, unsigned long>, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<std::pair<unsigned long, unsigned long> > >::lower_bound(std::pair<unsigned long, unsigned long> const&) const:
✓ Branch 1 taken 90406993 times.
✓ Branch 2 taken 248350697 times.
tifa_libs::ost_impl_::ostree<unsigned int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<unsigned int> >::lower_bound(unsigned int const&) const:
✓ Branch 1 taken 126485778 times.
✓ Branch 2 taken 98983435 times.
|
565228234 | if (!compare(now->data, key)) ans = now, now = now->ch[0]; |
| 137 | 347833383 | else now = now->ch[1]; | |
| 138 | } | ||
| 139 | 33245265 | return (pointer)ans; | |
| 140 | } | ||
| 141 | 35127 | CEXP pointer upper_bound(const K& key) CNE { | |
| 142 | 35127 | const_pointer now = root, ans = nullptr; | |
| 143 |
2/2✓ Branch 0 taken 487373 times.
✓ Branch 1 taken 35127 times.
|
522500 | while (now) { |
| 144 |
2/2✓ Branch 1 taken 247016 times.
✓ Branch 2 taken 240357 times.
|
487373 | if (compare(key, now->data)) ans = now, now = now->ch[0]; |
| 145 | 240357 | else now = now->ch[1]; | |
| 146 | } | ||
| 147 | 35127 | return (pointer)ans; | |
| 148 | } | ||
| 149 | 36651 | CEXP pointer find(const K& key) CNE { | |
| 150 | 36651 | auto p = lower_bound(key); | |
| 151 |
4/8✓ Branch 0 taken 36651 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 36651 times.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 36651 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 36651 times.
|
36651 | retif_(((!p || compare(p->data, key) || compare(key, p->data))), nullptr, p); |
| 152 | } | ||
| 153 | // Order start from 0 | ||
| 154 | 3017909 | CEXP u32 order_of_key(const K& key) CNE { | |
| 155 | 3017909 | u32 ans = 0; | |
| 156 | 3017909 | auto now = root; | |
| 157 |
4/4tifa_libs::ost_impl_::ostree<int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<int> >::order_of_key(int const&) const:
✓ Branch 0 taken 498000 times.
✓ Branch 1 taken 35837 times.
tifa_libs::ost_impl_::ostree<unsigned int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<unsigned int> >::order_of_key(unsigned int const&) const:
✓ Branch 0 taken 39439059 times.
✓ Branch 1 taken 2982072 times.
|
42954968 | while (now) { |
| 158 |
4/4tifa_libs::ost_impl_::ostree<int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<int> >::order_of_key(int const&) const:
✓ Branch 1 taken 251757 times.
✓ Branch 2 taken 246243 times.
tifa_libs::ost_impl_::ostree<unsigned int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<unsigned int> >::order_of_key(unsigned int const&) const:
✓ Branch 1 taken 19826900 times.
✓ Branch 2 taken 19612159 times.
|
39937059 | if (!compare(now->data, key)) now = now->ch[0]; |
| 159 | 19858402 | else ans += tag_t::size(now->ch[0]) + tag_t::count(now), now = now->ch[1]; | |
| 160 | } | ||
| 161 | 3017909 | return ans; | |
| 162 | } | ||
| 163 | // Order start from 0 | ||
| 164 | 2864017 | CEXP const_pointer find_by_order(u32 order) CNE { | |
| 165 | 2864017 | const_pointer now = root, ans = nullptr; | |
| 166 |
4/8tifa_libs::ost_impl_::ostree<int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<int> >::find_by_order(unsigned int) const:
✓ Branch 0 taken 474922 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 474922 times.
✗ Branch 3 not taken.
tifa_libs::ost_impl_::ostree<unsigned int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<unsigned int> >::find_by_order(unsigned int) const:
✓ Branch 0 taken 35826998 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 35826998 times.
✗ Branch 3 not taken.
|
36301920 | while (now && now->sz >= order) |
| 167 |
4/4tifa_libs::ost_impl_::ostree<int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<int> >::find_by_order(unsigned int) const:
✓ Branch 2 taken 221296 times.
✓ Branch 3 taken 253626 times.
tifa_libs::ost_impl_::ostree<unsigned int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<unsigned int> >::find_by_order(unsigned int) const:
✓ Branch 2 taken 16404616 times.
✓ Branch 3 taken 19422382 times.
|
36301920 | if (auto lsz = tag_t::size(now->ch[0]), cnt = tag_t::count(now); order < lsz) now = now->ch[0]; |
| 168 | else { | ||
| 169 |
4/4tifa_libs::ost_impl_::ostree<int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<int> >::find_by_order(unsigned int) const:
✓ Branch 0 taken 36872 times.
✓ Branch 1 taken 216754 times.
tifa_libs::ost_impl_::ostree<unsigned int, tifa_libs::ost_impl_::bst_op<tifa_libs::rbt_impl_::rbt_op_leaf>, std::less<unsigned int> >::find_by_order(unsigned int) const:
✓ Branch 0 taken 2827145 times.
✓ Branch 1 taken 16595237 times.
|
19676008 | if (ans = now; order < lsz + cnt) break; |
| 170 | 16811991 | now = now->ch[1], order -= lsz + cnt; | |
| 171 | } | ||
| 172 | 2864017 | return ans; | |
| 173 | } | ||
| 174 | 14893213 | CEXP const_pointer insert(const K& data) NE { return tag_t::insert(root, data, alloc, compare); } | |
| 175 | //! count -= 1 | ||
| 176 | 36651 | CEXP bool erase(const K& key) NE { | |
| 177 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 36651 times.
|
36651 | if (auto p = find(key); !p) return false; |
| 178 |
2/2✓ Branch 1 taken 1899 times.
✓ Branch 2 taken 34752 times.
|
36651 | else if (tag_t::count(p) > 1) { |
| 179 | 1899 | tag_t::modify_size(p, -1); | |
| 180 | 1899 | return true; | |
| 181 | } else { | ||
| 182 | 34752 | erase(p); | |
| 183 | 34752 | return true; | |
| 184 | } | ||
| 185 | } | ||
| 186 | 772056 | CEXP const_pointer erase(pointer p) NE { return tag_t::erase(root, p, alloc); } | |
| 187 | |||
| 188 | private: | ||
| 189 | alc<node_t> alloc; | ||
| 190 | }; | ||
| 191 | } // namespace ost_impl_ | ||
| 192 | |||
| 193 | template <class K, class Comp = std::less<K>> | ||
| 194 | using bstree = ost_impl_::ostree<K, ost_impl_::bst_tag, Comp>; | ||
| 195 | |||
| 196 | } // namespace tifa_libs | ||
| 197 |