Skip to content

Instantly share code, notes, and snippets.

/josephus.cc Secret

Created November 8, 2015 11:29
Download ZIP
Raw
josephus.cc
#include <iostream>
template <typename T>
struct JNode {
JNode() = default;
JNode(T t, bool c, JNode *l, JNode *r, JNode *p):
value(std::move(t)), color(c), left(l), right(r), parent(p) {}
T value;
bool color = 0;
JNode *left = nullptr;
JNode *right = nullptr;
JNode *parent = nullptr;
std::size_t cnt = 0;
};
void josephus(std::size_t, std::size_t) noexcept;
template <typename T>
class JTree {
friend void josephus(std::size_t, std::size_t) noexcept;
static constexpr bool BLACK = 0;
static constexpr bool RED = 1;
static JNode<T> nil;
JNode<T> *root = &nil;
public:
JTree() = default;
JTree(const JTree &) = delete;
JTree(JTree &&) = delete;
~JTree() { if (root != &nil) free(root); }
JNode<T> *insert(T t)
{
JNode<T> *new_node = new JNode<T>{std::move(t), RED, &nil, &nil, &nil};
new_node->cnt = 1;
if (root == &nil) {
root = new_node;
} else {
JNode<T> *p = root;
while (true) {
if (new_node->value < p->value) {
if (p->left == &nil) {
p->left = new_node;
new_node->parent = p;
break;
} p = p->left;
} else {
if (p->right == &nil) {
p->right = new_node;
new_node->parent = p;
break;
} p = p->right;
}
}
while (p != &nil) {
++p->cnt;
p = p->parent;
}
} insert_fix(new_node);
return new_node;
}
void erase(JNode<T> *p) noexcept
{
JNode<T> *replace_p = p, *fix_p = p;
bool no_left = p->left == &nil, no_right = p->right == &nil;
bool old_color = replace_p->color;
if (no_left || no_right) {
replace_p = (no_left ? p->right : p->left);
old_color = replace_p->color;
(p == root ? root : p == p->parent->left
? p->parent->left
: p->parent->right) = replace_p;
replace_p->parent = p->parent;
replace_p->color = p->color;
fix_p = replace_p;
while (p->parent != &nil) {
--p->parent->cnt;
p = p->parent;
}
} else {
replace_p = p->right;
while (replace_p->left != &nil)
replace_p = replace_p->left;
old_color = replace_p->color;
fix_p = replace_p->right;
fix_p->parent = replace_p;
if (p->right != replace_p) {
fix_p->parent = replace_p->parent;
fix_p->parent->left = fix_p;
replace_p->right = p->right;
p->right->parent = replace_p;
JNode<T> *c = fix_p->parent;
while (c != replace_p) {
--c->cnt;
c = c->parent;
}
} replace_p->color = p->color;
replace_p->parent = p->parent;
(p == root ? root : p == p->parent->left
? p->parent->left
: p->parent->right) = replace_p;
replace_p->left = p->left;
p->left->parent = replace_p;
replace_p->cnt = p->cnt;
while (replace_p != &nil) {
--replace_p->cnt;
replace_p = replace_p->parent;
}
}
if (old_color == BLACK)
erase_fix(fix_p);
}
JNode<T> *search_cnt(std::size_t m) noexcept
{
JNode<T> *p = root;
while (p != &nil) {
if (p->left->cnt + 1 == m) {
break;
} else if (p->left->cnt + 1 < m) {
m -= p->left->cnt + 1;
p = p->right;
} else {
p = p->left;
}
} return p;
}
void josephus(T n, T m) noexcept
{
for (T i = T(); i != n; ++i)
insert(i + 1);
JNode<T> *p = search_cnt(m);
std::size_t cnt = m;
while (p != &nil) {
std::cout << p->value << ' ';
erase(p);
--n;
cnt = (cnt + m - 1) % n;
if (cnt == 0)
cnt = n;
p = search_cnt(cnt);
} std::cout << std::endl;
}
private:
void left_rotate(JNode<T> *p) noexcept
{
(p == root ? root : p == p->parent->left
? p->parent->left
: p->parent->right) = p->right;
p->right->parent = p->parent;
p->parent = p->right;
p->right = p->parent->left;
if (p->right != &nil)
p->right->parent = p;
p->parent->left = p;
p->parent->cnt = p->cnt;
p->cnt = p->left->cnt + p->right->cnt + 1;
}
void right_rotate(JNode<T> *p) noexcept
{
(p == root ? root : p == p->parent->left
? p->parent->left
: p->parent->right) = p->left;
p->left->parent = p->parent;
p->parent = p->left;
p->left = p->parent->right;
if (p->left != &nil)
p->left->parent = p;
p->parent->right = p;
p->parent->cnt = p->cnt;
p->cnt = p->left->cnt + p->right->cnt + 1;
}
void insert_fix(JNode<T> *p) noexcept
{
while (p->parent->color == RED) {
if (p->parent == p->parent->parent->left) {
if (p->parent->parent->right->color == RED) {
p->parent->parent->right->color = BLACK;
p->parent->parent->color = RED;
p->parent->color = BLACK;
p = p->parent->parent;
} else {
if (p == p->parent->right) {
left_rotate(p->parent);
p = p->left;
} p->parent->color = BLACK;
p->parent->parent->color = RED;
right_rotate(p->parent->parent);
p = root;
}
} else {
if (p->parent->parent->left->color == RED) {
p->parent->parent->left->color = BLACK;
p->parent->parent->color = RED;
p->parent->color = BLACK;
p = p->parent->parent;
} else {
if (p == p->parent->left) {
right_rotate(p->parent);
p = p->right;
} p->parent->color = BLACK;
p->parent->parent->color = RED;
left_rotate(p->parent->parent);
p = root;
}
}
} root->color = BLACK;
}
void erase_fix(JNode<T> *p) noexcept
{
while (p->color == BLACK && p != root) {
if (p == p->parent->left) {
if (p->parent->right->color == RED) {
p->parent->right->color = BLACK;
p->parent->color = RED;
left_rotate(p->parent);
}
if (p->parent->right->right->color == BLACK) {
p->parent->right->color = RED;
if (p->parent->right->left->color == BLACK) {
p = p->parent;
continue;
} p->parent->right->left->color = BLACK;
right_rotate(p->parent->right);
} p->parent->right->right->color = BLACK;
p->parent->right->color = p->parent->color;
p->parent->color = BLACK;
left_rotate(p->parent);
p = root;
} else {
if (p->parent->left->color == RED) {
p->parent->left->color = BLACK;
p->parent->color = RED;
right_rotate(p->parent);
}
if (p->parent->left->left->color == BLACK) {
p->parent->left->color = RED;
if (p->parent->left->right->color == BLACK) {
p = p->parent;
continue;
} p->parent->left->right->color = BLACK;
left_rotate(p->parent->left);
} p->parent->left->left->color = BLACK;
p->parent->left->color = p->parent->color;
p->parent->color = BLACK;
right_rotate(p->parent);
p = root;
}
} p->color = BLACK;
}
void free(JNode<T> *p) noexcept
{
if (p->left != &nil)
free(p->left);
if (p->right != &nil)
free(p->right);
delete p;
}
};
template <typename T>
JNode<T> JTree<T>::nil = JNode<T>();
int main()
{
JTree<std::size_t> j;
j.josephus(7, 3);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment