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;
}