Ideone.com

fork download

copy

#include <bits/stdc++.h>
using namespace std;
 
// ==================== Node ====================
 
template <typename Type, int Ord>
struct Node
{
    bool is_leaf;
    int num_keys;
    Type key[Ord];
 
    Node(bool leaf)
    {
        is_leaf = leaf;
        num_keys = 0;
    }
 
    virtual ~Node() = default;
};
 
// ==================== Leaf Node ====================
 
template <typename Type, int Ord>
struct LeafNode : public Node<Type, Ord>
{
    LeafNode() : Node<Type, Ord>(true) {}
};
 
// ==================== Internal Node ====================
 
template <typename Type, int Ord>
struct InternalNode : public Node<Type, Ord>
{
    Node<Type, Ord>* child[Ord + 1];
 
    InternalNode() : Node<Type, Ord>(false)
    {
        for (int i = 0; i <= Ord; i++)
            child[i] = nullptr;
    }
};
 
// ==================== B Tree ====================
 
template <typename Type, int Ord>
struct BTree
{
private:
    static_assert(Ord >= 3, "Ord must be at least 3");
 
    Node<Type, Ord>* root = nullptr;
 
    static constexpr int MIN_KEYS = (Ord + 1) / 2 - 1;
 
    // ==================== Search ====================
 
    bool searchNode(Node<Type, Ord>* node, Type value) const
    {
        if (node == nullptr)
            return false;
 
        int i;
 
        for (i = 0; i < node->num_keys; i++)
        {
            if (value <= node->key[i]) break;
        }
 
        if (i < node->num_keys && value == node->key[i])
            return true;
 
        if (node->is_leaf)
            return false;
 
        auto* p = static_cast<InternalNode<Type, Ord>*>(node);
 
        return searchNode(p->child[i], value);
    }
 
    // ==================== Split Leaf ====================
 
    bool splitLeaf(Node<Type, Ord>* node, Type value,
                   Type& promoted, Node<Type, Ord>*& right)
    {
        Type temp[Ord + 1];
 
        int i;
 
        for (i = node->num_keys - 1; i >= 0; i--)
        {
            if (value >= node->key[i]) break;
            temp[i + 1] = node->key[i];
        }
 
        temp[i + 1] = value;
 
        for (int j = 0; j <= i; j++)
            temp[j] = node->key[j];
 
        int mid = (Ord + 1) / 2;
 
        promoted = temp[mid];
 
        right = new LeafNode<Type, Ord>();
 
        node->num_keys = mid;
 
        for (int j = 0; j < mid; j++)
            node->key[j] = temp[j];
 
        right->num_keys = Ord - mid;
 
        for (int j = 0; j < right->num_keys; j++)
            right->key[j] = temp[mid + 1 + j];
 
        return true;
    }
 
    // ==================== Split Internal ====================
 
    bool splitInternal(Node<Type, Ord>* node, int pos,
                       Type value, Node<Type, Ord>* newChild,
                       Type& promoted, Node<Type, Ord>*& right)
    {
        auto* p = static_cast<InternalNode<Type, Ord>*>(node);
 
        Type tempKeys[Ord + 1];
        Node<Type, Ord>* tempChildren[Ord + 2];
 
        for (int i = 0; i < pos; i++)
            tempKeys[i] = node->key[i];
 
        tempKeys[pos] = value;
 
        for (int i = pos; i < node->num_keys; i++)
            tempKeys[i + 1] = node->key[i];
 
        for (int i = 0; i <= pos; i++)
            tempChildren[i] = p->child[i];
 
        tempChildren[pos + 1] = newChild;
 
        for (int i = pos + 1; i <= node->num_keys; i++)
            tempChildren[i + 1] = p->child[i];
 
        int mid = (Ord + 1) / 2;
 
        promoted = tempKeys[mid];
 
        right = new InternalNode<Type, Ord>();
 
        auto* r = static_cast<InternalNode<Type, Ord>*>(right);
 
        node->num_keys = mid;
 
        for (int i = 0; i < mid; i++)
            node->key[i] = tempKeys[i];
 
        for (int i = 0; i <= mid; i++)
            p->child[i] = tempChildren[i];
 
        for (int i = mid + 1; i <= Ord; i++)
            p->child[i] = nullptr;
 
        right->num_keys = Ord - mid;
 
        for (int i = 0; i < right->num_keys; i++)
            right->key[i] = tempKeys[mid + 1 + i];
 
        for (int i = 0; i <= right->num_keys; i++)
            r->child[i] = tempChildren[mid + 1 + i];
 
        return true;
    }
 
    // ==================== Insert ====================
 
    bool insertRecursive(Node<Type, Ord>* node, Type value,
                         Type& promoted, Node<Type, Ord>*& right)
    {
        if (node->is_leaf)
        {
            if (node->num_keys < Ord)
            {
                int i;
 
                for (i = node->num_keys - 1; i >= 0; i--)
                {
                    if (value >= node->key[i]) break;
                    node->key[i + 1] = node->key[i];
                }
 
                node->key[i + 1] = value;
                node->num_keys++;
 
                return false;
            }
 
            return splitLeaf(node, value, promoted, right);
        }
 
        auto* p = static_cast<InternalNode<Type, Ord>*>(node);
 
        int pos;
 
        for (pos = 0; pos < node->num_keys; pos++)
        {
            if (value <= node->key[pos]) break;
        }
 
        Type childPromoted{};
        Node<Type, Ord>* childRight = nullptr;
 
        if (!insertRecursive(p->child[pos], value,
                             childPromoted, childRight))
            return false;
 
        if (node->num_keys < Ord)
        {
            for (int i = node->num_keys; i > pos; i--)
                node->key[i] = node->key[i - 1];
 
            for (int i = node->num_keys + 1; i > pos + 1; i--)
                p->child[i] = p->child[i - 1];
 
            node->key[pos] = childPromoted;
            p->child[pos + 1] = childRight;
            node->num_keys++;
 
            return false;
        }
 
        return splitInternal(node, pos, childPromoted, childRight,
                             promoted, right);
    }
 
    // ==================== Get Predecessor ====================
 
    Type getPredecessor(Node<Type, Ord>* node) const
    {
        while (!node->is_leaf)
        {
            auto* p = static_cast<InternalNode<Type, Ord>*>(node);
            node = p->child[node->num_keys];
        }
 
        return node->key[node->num_keys - 1];
    }
 
    // ==================== Remove From Leaf ====================
 
    void removeFromLeaf(Node<Type, Ord>* node, int idx)
    {
        for (int i = idx; i < node->num_keys - 1; i++)
            node->key[i] = node->key[i + 1];
 
        node->num_keys--;
    }
 
    // ==================== Borrow From Previous ====================
 
    void borrowFromPrev(Node<Type, Ord>* parent, int idx)
    {
        auto* p = static_cast<InternalNode<Type, Ord>*>(parent);
 
        Node<Type, Ord>* child = p->child[idx];
        Node<Type, Ord>* sibling = p->child[idx - 1];
 
        for (int i = child->num_keys; i > 0; i--)
            child->key[i] = child->key[i - 1];
 
        if (!child->is_leaf)
        {
            auto* c = static_cast<InternalNode<Type, Ord>*>(child);
            auto* s = static_cast<InternalNode<Type, Ord>*>(sibling);
 
            for (int i = child->num_keys + 1; i > 0; i--)
                c->child[i] = c->child[i - 1];
 
            c->child[0] = s->child[sibling->num_keys];
            s->child[sibling->num_keys] = nullptr;
        }
 
        child->key[0] = parent->key[idx - 1];
 
        parent->key[idx - 1] = sibling->key[sibling->num_keys - 1];
 
        child->num_keys++;
        sibling->num_keys--;
    }
 
    // ==================== Borrow From Next ====================
 
    void borrowFromNext(Node<Type, Ord>* parent, int idx)
    {
        auto* p = static_cast<InternalNode<Type, Ord>*>(parent);
 
        Node<Type, Ord>* child = p->child[idx];
        Node<Type, Ord>* sibling = p->child[idx + 1];
 
        child->key[child->num_keys] = parent->key[idx];
 
        if (!child->is_leaf)
        {
            auto* c = static_cast<InternalNode<Type, Ord>*>(child);
            auto* s = static_cast<InternalNode<Type, Ord>*>(sibling);
 
            c->child[child->num_keys + 1] = s->child[0];
 
            for (int i = 0; i < sibling->num_keys; i++)
                s->child[i] = s->child[i + 1];
 
            s->child[sibling->num_keys] = nullptr;
        }
 
        parent->key[idx] = sibling->key[0];
 
        for (int i = 0; i < sibling->num_keys - 1; i++)
            sibling->key[i] = sibling->key[i + 1];
 
        child->num_keys++;
        sibling->num_keys--;
    }
 
    // ==================== Merge ====================
 
    void merge(Node<Type, Ord>* parent, int idx)
    {
        auto* p = static_cast<InternalNode<Type, Ord>*>(parent);
 
        Node<Type, Ord>* left = p->child[idx];
        Node<Type, Ord>* right = p->child[idx + 1];
 
        int size = left->num_keys;
 
        left->key[size] = parent->key[idx];
 
        for (int i = 0; i < right->num_keys; i++)
            left->key[size + 1 + i] = right->key[i];
 
        if (!left->is_leaf)
        {
            auto* l = static_cast<InternalNode<Type, Ord>*>(left);
            auto* r = static_cast<InternalNode<Type, Ord>*>(right);
 
            for (int i = 0; i <= right->num_keys; i++)
            {
                l->child[size + 1 + i] = r->child[i];
                r->child[i] = nullptr;
            }
        }
 
        left->num_keys += right->num_keys + 1;
 
        for (int i = idx; i < parent->num_keys - 1; i++)
            parent->key[i] = parent->key[i + 1];
 
        for (int i = idx + 1; i < parent->num_keys; i++)
            p->child[i] = p->child[i + 1];
 
        p->child[parent->num_keys] = nullptr;
 
        parent->num_keys--;
 
        delete right;
    }
 
    // ==================== Fix Underflow ====================
 
    void fixChild(Node<Type, Ord>* parent, int idx)
    {
        auto* p = static_cast<InternalNode<Type, Ord>*>(parent);
 
        Node<Type, Ord>* child = p->child[idx];
 
        if (child->num_keys >= MIN_KEYS)
            return;
 
        if (idx > 0 && p->child[idx - 1]->num_keys > MIN_KEYS)
            borrowFromPrev(parent, idx);
        else if (idx < parent->num_keys &&
                 p->child[idx + 1]->num_keys > MIN_KEYS)
            borrowFromNext(parent, idx);
        else if (idx < parent->num_keys)
            merge(parent, idx);
        else if (idx > 0)
            merge(parent, idx - 1);
    }
 
    // ==================== Remove ====================
 
    bool removeRecursive(Node<Type, Ord>* node, Type value)
    {
        int idx;
 
        for (idx = 0; idx < node->num_keys; idx++)
        {
            if (value <= node->key[idx]) break;
        }
 
        if (idx < node->num_keys && value == node->key[idx])
        {
            if (node->is_leaf)
            {
                removeFromLeaf(node, idx);
                return true;
            }
 
            auto* p = static_cast<InternalNode<Type, Ord>*>(node);
 
            Type pred = getPredecessor(p->child[idx]);
 
            node->key[idx] = pred;
 
            bool removed = removeRecursive(p->child[idx], pred);
 
            if (removed)
                fixChild(node, idx);
 
            return removed;
        }
 
        if (node->is_leaf)
            return false;
 
        auto* p = static_cast<InternalNode<Type, Ord>*>(node);
 
        bool removed = removeRecursive(p->child[idx], value);
 
        if (removed)
            fixChild(node, idx);
 
        return removed;
    }
 
    // ==================== Display ====================
 
    void displayNode(Node<Type, Ord>* node, int level) const
    {
        if (node == nullptr)
            return;
 
        cout << string(level * 4, ' ') << "[ ";
 
        for (int i = 0; i < node->num_keys; i++)
            cout << node->key[i] << " ";
 
        cout << "]\n";
 
        if (!node->is_leaf)
        {
            auto* p = static_cast<InternalNode<Type, Ord>*>(node);
 
            for (int i = 0; i <= node->num_keys; i++)
                displayNode(p->child[i], level + 1);
        }
    }
 
    // ==================== Destroy ====================
 
    void destroy(Node<Type, Ord>* node)
    {
        if (node == nullptr)
            return;
 
        if (!node->is_leaf)
        {
            auto* p = static_cast<InternalNode<Type, Ord>*>(node);
 
            for (int i = 0; i <= node->num_keys; i++)
                destroy(p->child[i]);
        }
 
        delete node;
    }
 
public:
 
    BTree() = default;
 
    ~BTree()
    {
        destroy(root);
    }
 
    BTree(const BTree&) = delete;
    BTree& operator=(const BTree&) = delete;
 
    // ==================== Search ====================
 
    bool search(Type value) const
    {
        return searchNode(root, value);
    }
 
    // ==================== Insert ====================
 
    void insert(Type value)
    {
        if (search(value))
        {
            cout << "Value already exists!\n";
            return;
        }
 
        if (root == nullptr)
        {
            root = new LeafNode<Type, Ord>();
            root->key[0] = value;
            root->num_keys = 1;
 
            return;
        }
 
        Type promoted{};
        Node<Type, Ord>* right = nullptr;
 
        if (insertRecursive(root, value, promoted, right))
        {
            auto* newRoot = new InternalNode<Type, Ord>();
 
            newRoot->key[0] = promoted;
            newRoot->num_keys = 1;
 
            newRoot->child[0] = root;
            newRoot->child[1] = right;
 
            root = newRoot;
        }
    }
 
    // ==================== Remove ====================
 
    void remove(Type value)
    {
        if (root == nullptr)
        {
            cout << "Tree is empty!\n";
            return;
        }
 
        if (!search(value))
        {
            cout << "Value not found!\n";
            return;
        }
 
        removeRecursive(root, value);
 
        if (root->num_keys == 0)
        {
            Node<Type, Ord>* oldRoot = root;
 
            if (root->is_leaf)
            {
                root = nullptr;
            }
            else
            {
                auto* p = static_cast<InternalNode<Type, Ord>*>(root);
 
                root = p->child[0];
                p->child[0] = nullptr;
            }
 
            delete oldRoot;
        }
    }
 
    // ==================== Display ====================
 
    void displayTree() const
    {
        if (root == nullptr)
        {
            cout << "Tree is empty!\n";
            return;
        }
 
        displayNode(root, 0);
    }
};
 
// ==================== Main ====================
 
int main()
{
    BTree<int, 3> tree;
 
    int choice;
    int value;
 
    while (true)
    {
        cout << "\n========== B-Tree ==========\n";
        cout << "1. Insert\n";
        cout << "2. Delete\n";
        cout << "3. Search\n";
        cout << "4. Display\n";
        cout << "0. Exit\n";
 
        cout << "Choice: ";
        cin >> choice;
 
        switch (choice)
        {
            case 1:
                cout << "Enter value: ";
                cin >> value;
                tree.insert(value);
                break;
 
            case 2:
                cout << "Enter value: ";
                cin >> value;
                tree.remove(value);
                break;
 
            case 3:
                cout << "Enter value: ";
                cin >> value;
 
                if (tree.search(value))
                    cout << "Found!\n";
                else
                    cout << "Not Found!\n";
 
                break;
 
            case 4:
                tree.displayTree();
                break;
 
            case 0:
                cout << "Goodbye!\n";
                break;
 
            default:
                cout << "Invalid choice!\n";
        }
 
        if (choice == 0) break;
    }
 
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyA9PT09PT09PT09PT09PT09PT09PSBOb2RlID09PT09PT09PT09PT09PT09PT09Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVHlwZSwgaW50IE9yZD4Kc3RydWN0IE5vZGUKewogICAgYm9vbCBpc19sZWFmOwogICAgaW50IG51bV9rZXlzOwogICAgVHlwZSBrZXlbT3JkXTsKCiAgICBOb2RlKGJvb2wgbGVhZikKICAgIHsKICAgICAgICBpc19sZWFmID0gbGVhZjsKICAgICAgICBudW1fa2V5cyA9IDA7CiAgICB9CgogICAgdmlydHVhbCB+Tm9kZSgpID0gZGVmYXVsdDsKfTsKCi8vID09PT09PT09PT09PT09PT09PT09IExlYWYgTm9kZSA9PT09PT09PT09PT09PT09PT09PQoKdGVtcGxhdGUgPHR5cGVuYW1lIFR5cGUsIGludCBPcmQ+CnN0cnVjdCBMZWFmTm9kZSA6IHB1YmxpYyBOb2RlPFR5cGUsIE9yZD4KewogICAgTGVhZk5vZGUoKSA6IE5vZGU8VHlwZSwgT3JkPih0cnVlKSB7fQp9OwoKLy8gPT09PT09PT09PT09PT09PT09PT0gSW50ZXJuYWwgTm9kZSA9PT09PT09PT09PT09PT09PT09PQoKdGVtcGxhdGUgPHR5cGVuYW1lIFR5cGUsIGludCBPcmQ+CnN0cnVjdCBJbnRlcm5hbE5vZGUgOiBwdWJsaWMgTm9kZTxUeXBlLCBPcmQ+CnsKICAgIE5vZGU8VHlwZSwgT3JkPiogY2hpbGRbT3JkICsgMV07CgogICAgSW50ZXJuYWxOb2RlKCkgOiBOb2RlPFR5cGUsIE9yZD4oZmFsc2UpCiAgICB7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPD0gT3JkOyBpKyspCiAgICAgICAgICAgIGNoaWxkW2ldID0gbnVsbHB0cjsKICAgIH0KfTsKCi8vID09PT09PT09PT09PT09PT09PT09IEIgVHJlZSA9PT09PT09PT09PT09PT09PT09PQoKdGVtcGxhdGUgPHR5cGVuYW1lIFR5cGUsIGludCBPcmQ+CnN0cnVjdCBCVHJlZQp7CnByaXZhdGU6CiAgICBzdGF0aWNfYXNzZXJ0KE9yZCA+PSAzLCAiT3JkIG11c3QgYmUgYXQgbGVhc3QgMyIpOwoKICAgIE5vZGU8VHlwZSwgT3JkPiogcm9vdCA9IG51bGxwdHI7CgogICAgc3RhdGljIGNvbnN0ZXhwciBpbnQgTUlOX0tFWVMgPSAoT3JkICsgMSkgLyAyIC0gMTsKCiAgICAvLyA9PT09PT09PT09PT09PT09PT09PSBTZWFyY2ggPT09PT09PT09PT09PT09PT09PT0KCiAgICBib29sIHNlYXJjaE5vZGUoTm9kZTxUeXBlLCBPcmQ+KiBub2RlLCBUeXBlIHZhbHVlKSBjb25zdAogICAgewogICAgICAgIGlmIChub2RlID09IG51bGxwdHIpCiAgICAgICAgICAgIHJldHVybiBmYWxzZTsKCiAgICAgICAgaW50IGk7CgogICAgICAgIGZvciAoaSA9IDA7IGkgPCBub2RlLT5udW1fa2V5czsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKHZhbHVlIDw9IG5vZGUtPmtleVtpXSkgYnJlYWs7CiAgICAgICAgfQoKICAgICAgICBpZiAoaSA8IG5vZGUtPm51bV9rZXlzICYmIHZhbHVlID09IG5vZGUtPmtleVtpXSkKICAgICAgICAgICAgcmV0dXJuIHRydWU7CgogICAgICAgIGlmIChub2RlLT5pc19sZWFmKQogICAgICAgICAgICByZXR1cm4gZmFsc2U7CgogICAgICAgIGF1dG8qIHAgPSBzdGF0aWNfY2FzdDxJbnRlcm5hbE5vZGU8VHlwZSwgT3JkPio+KG5vZGUpOwoKICAgICAgICByZXR1cm4gc2VhcmNoTm9kZShwLT5jaGlsZFtpXSwgdmFsdWUpOwogICAgfQoKICAgIC8vID09PT09PT09PT09PT09PT09PT09IFNwbGl0IExlYWYgPT09PT09PT09PT09PT09PT09PT0KCiAgICBib29sIHNwbGl0TGVhZihOb2RlPFR5cGUsIE9yZD4qIG5vZGUsIFR5cGUgdmFsdWUsCiAgICAgICAgICAgICAgICAgICBUeXBlJiBwcm9tb3RlZCwgTm9kZTxUeXBlLCBPcmQ+KiYgcmlnaHQpCiAgICB7CiAgICAgICAgVHlwZSB0ZW1wW09yZCArIDFdOwoKICAgICAgICBpbnQgaTsKCiAgICAgICAgZm9yIChpID0gbm9kZS0+bnVtX2tleXMgLSAxOyBpID49IDA7IGktLSkKICAgICAgICB7CiAgICAgICAgICAgIGlmICh2YWx1ZSA+PSBub2RlLT5rZXlbaV0pIGJyZWFrOwogICAgICAgICAgICB0ZW1wW2kgKyAxXSA9IG5vZGUtPmtleVtpXTsKICAgICAgICB9CgogICAgICAgIHRlbXBbaSArIDFdID0gdmFsdWU7CgogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDw9IGk7IGorKykKICAgICAgICAgICAgdGVtcFtqXSA9IG5vZGUtPmtleVtqXTsKCiAgICAgICAgaW50IG1pZCA9IChPcmQgKyAxKSAvIDI7CgogICAgICAgIHByb21vdGVkID0gdGVtcFttaWRdOwoKICAgICAgICByaWdodCA9IG5ldyBMZWFmTm9kZTxUeXBlLCBPcmQ+KCk7CgogICAgICAgIG5vZGUtPm51bV9rZXlzID0gbWlkOwoKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IG1pZDsgaisrKQogICAgICAgICAgICBub2RlLT5rZXlbal0gPSB0ZW1wW2pdOwoKICAgICAgICByaWdodC0+bnVtX2tleXMgPSBPcmQgLSBtaWQ7CgogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgcmlnaHQtPm51bV9rZXlzOyBqKyspCiAgICAgICAgICAgIHJpZ2h0LT5rZXlbal0gPSB0ZW1wW21pZCArIDEgKyBqXTsKCiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9CgogICAgLy8gPT09PT09PT09PT09PT09PT09PT0gU3BsaXQgSW50ZXJuYWwgPT09PT09PT09PT09PT09PT09PT0KCiAgICBib29sIHNwbGl0SW50ZXJuYWwoTm9kZTxUeXBlLCBPcmQ+KiBub2RlLCBpbnQgcG9zLAogICAgICAgICAgICAgICAgICAgICAgIFR5cGUgdmFsdWUsIE5vZGU8VHlwZSwgT3JkPiogbmV3Q2hpbGQsCiAgICAgICAgICAgICAgICAgICAgICAgVHlwZSYgcHJvbW90ZWQsIE5vZGU8VHlwZSwgT3JkPiomIHJpZ2h0KQogICAgewogICAgICAgIGF1dG8qIHAgPSBzdGF0aWNfY2FzdDxJbnRlcm5hbE5vZGU8VHlwZSwgT3JkPio+KG5vZGUpOwoKICAgICAgICBUeXBlIHRlbXBLZXlzW09yZCArIDFdOwogICAgICAgIE5vZGU8VHlwZSwgT3JkPiogdGVtcENoaWxkcmVuW09yZCArIDJdOwoKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IHBvczsgaSsrKQogICAgICAgICAgICB0ZW1wS2V5c1tpXSA9IG5vZGUtPmtleVtpXTsKCiAgICAgICAgdGVtcEtleXNbcG9zXSA9IHZhbHVlOwoKICAgICAgICBmb3IgKGludCBpID0gcG9zOyBpIDwgbm9kZS0+bnVtX2tleXM7IGkrKykKICAgICAgICAgICAgdGVtcEtleXNbaSArIDFdID0gbm9kZS0+a2V5W2ldOwoKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8PSBwb3M7IGkrKykKICAgICAgICAgICAgdGVtcENoaWxkcmVuW2ldID0gcC0+Y2hpbGRbaV07CgogICAgICAgIHRlbXBDaGlsZHJlbltwb3MgKyAxXSA9IG5ld0NoaWxkOwoKICAgICAgICBmb3IgKGludCBpID0gcG9zICsgMTsgaSA8PSBub2RlLT5udW1fa2V5czsgaSsrKQogICAgICAgICAgICB0ZW1wQ2hpbGRyZW5baSArIDFdID0gcC0+Y2hpbGRbaV07CgogICAgICAgIGludCBtaWQgPSAoT3JkICsgMSkgLyAyOwoKICAgICAgICBwcm9tb3RlZCA9IHRlbXBLZXlzW21pZF07CgogICAgICAgIHJpZ2h0ID0gbmV3IEludGVybmFsTm9kZTxUeXBlLCBPcmQ+KCk7CgogICAgICAgIGF1dG8qIHIgPSBzdGF0aWNfY2FzdDxJbnRlcm5hbE5vZGU8VHlwZSwgT3JkPio+KHJpZ2h0KTsKCiAgICAgICAgbm9kZS0+bnVtX2tleXMgPSBtaWQ7CgogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbWlkOyBpKyspCiAgICAgICAgICAgIG5vZGUtPmtleVtpXSA9IHRlbXBLZXlzW2ldOwoKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8PSBtaWQ7IGkrKykKICAgICAgICAgICAgcC0+Y2hpbGRbaV0gPSB0ZW1wQ2hpbGRyZW5baV07CgogICAgICAgIGZvciAoaW50IGkgPSBtaWQgKyAxOyBpIDw9IE9yZDsgaSsrKQogICAgICAgICAgICBwLT5jaGlsZFtpXSA9IG51bGxwdHI7CgogICAgICAgIHJpZ2h0LT5udW1fa2V5cyA9IE9yZCAtIG1pZDsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCByaWdodC0+bnVtX2tleXM7IGkrKykKICAgICAgICAgICAgcmlnaHQtPmtleVtpXSA9IHRlbXBLZXlzW21pZCArIDEgKyBpXTsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPD0gcmlnaHQtPm51bV9rZXlzOyBpKyspCiAgICAgICAgICAgIHItPmNoaWxkW2ldID0gdGVtcENoaWxkcmVuW21pZCArIDEgKyBpXTsKCiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9CgogICAgLy8gPT09PT09PT09PT09PT09PT09PT0gSW5zZXJ0ID09PT09PT09PT09PT09PT09PT09CgogICAgYm9vbCBpbnNlcnRSZWN1cnNpdmUoTm9kZTxUeXBlLCBPcmQ+KiBub2RlLCBUeXBlIHZhbHVlLAogICAgICAgICAgICAgICAgICAgICAgICAgVHlwZSYgcHJvbW90ZWQsIE5vZGU8VHlwZSwgT3JkPiomIHJpZ2h0KQogICAgewogICAgICAgIGlmIChub2RlLT5pc19sZWFmKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKG5vZGUtPm51bV9rZXlzIDwgT3JkKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpbnQgaTsKCiAgICAgICAgICAgICAgICBmb3IgKGkgPSBub2RlLT5udW1fa2V5cyAtIDE7IGkgPj0gMDsgaS0tKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGlmICh2YWx1ZSA+PSBub2RlLT5rZXlbaV0pIGJyZWFrOwogICAgICAgICAgICAgICAgICAgIG5vZGUtPmtleVtpICsgMV0gPSBub2RlLT5rZXlbaV07CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgbm9kZS0+a2V5W2kgKyAxXSA9IHZhbHVlOwogICAgICAgICAgICAgICAgbm9kZS0+bnVtX2tleXMrKzsKCiAgICAgICAgICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIHJldHVybiBzcGxpdExlYWYobm9kZSwgdmFsdWUsIHByb21vdGVkLCByaWdodCk7CiAgICAgICAgfQoKICAgICAgICBhdXRvKiBwID0gc3RhdGljX2Nhc3Q8SW50ZXJuYWxOb2RlPFR5cGUsIE9yZD4qPihub2RlKTsKCiAgICAgICAgaW50IHBvczsKCiAgICAgICAgZm9yIChwb3MgPSAwOyBwb3MgPCBub2RlLT5udW1fa2V5czsgcG9zKyspCiAgICAgICAgewogICAgICAgICAgICBpZiAodmFsdWUgPD0gbm9kZS0+a2V5W3Bvc10pIGJyZWFrOwogICAgICAgIH0KCiAgICAgICAgVHlwZSBjaGlsZFByb21vdGVke307CiAgICAgICAgTm9kZTxUeXBlLCBPcmQ+KiBjaGlsZFJpZ2h0ID0gbnVsbHB0cjsKCiAgICAgICAgaWYgKCFpbnNlcnRSZWN1cnNpdmUocC0+Y2hpbGRbcG9zXSwgdmFsdWUsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY2hpbGRQcm9tb3RlZCwgY2hpbGRSaWdodCkpCiAgICAgICAgICAgIHJldHVybiBmYWxzZTsKCiAgICAgICAgaWYgKG5vZGUtPm51bV9rZXlzIDwgT3JkKQogICAgICAgIHsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IG5vZGUtPm51bV9rZXlzOyBpID4gcG9zOyBpLS0pCiAgICAgICAgICAgICAgICBub2RlLT5rZXlbaV0gPSBub2RlLT5rZXlbaSAtIDFdOwoKICAgICAgICAgICAgZm9yIChpbnQgaSA9IG5vZGUtPm51bV9rZXlzICsgMTsgaSA+IHBvcyArIDE7IGktLSkKICAgICAgICAgICAgICAgIHAtPmNoaWxkW2ldID0gcC0+Y2hpbGRbaSAtIDFdOwoKICAgICAgICAgICAgbm9kZS0+a2V5W3Bvc10gPSBjaGlsZFByb21vdGVkOwogICAgICAgICAgICBwLT5jaGlsZFtwb3MgKyAxXSA9IGNoaWxkUmlnaHQ7CiAgICAgICAgICAgIG5vZGUtPm51bV9rZXlzKys7CgogICAgICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gc3BsaXRJbnRlcm5hbChub2RlLCBwb3MsIGNoaWxkUHJvbW90ZWQsIGNoaWxkUmlnaHQsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJvbW90ZWQsIHJpZ2h0KTsKICAgIH0KCiAgICAvLyA9PT09PT09PT09PT09PT09PT09PSBHZXQgUHJlZGVjZXNzb3IgPT09PT09PT09PT09PT09PT09PT0KCiAgICBUeXBlIGdldFByZWRlY2Vzc29yKE5vZGU8VHlwZSwgT3JkPiogbm9kZSkgY29uc3QKICAgIHsKICAgICAgICB3aGlsZSAoIW5vZGUtPmlzX2xlYWYpCiAgICAgICAgewogICAgICAgICAgICBhdXRvKiBwID0gc3RhdGljX2Nhc3Q8SW50ZXJuYWxOb2RlPFR5cGUsIE9yZD4qPihub2RlKTsKICAgICAgICAgICAgbm9kZSA9IHAtPmNoaWxkW25vZGUtPm51bV9rZXlzXTsKICAgICAgICB9CgogICAgICAgIHJldHVybiBub2RlLT5rZXlbbm9kZS0+bnVtX2tleXMgLSAxXTsKICAgIH0KCiAgICAvLyA9PT09PT09PT09PT09PT09PT09PSBSZW1vdmUgRnJvbSBMZWFmID09PT09PT09PT09PT09PT09PT09CgogICAgdm9pZCByZW1vdmVGcm9tTGVhZihOb2RlPFR5cGUsIE9yZD4qIG5vZGUsIGludCBpZHgpCiAgICB7CiAgICAgICAgZm9yIChpbnQgaSA9IGlkeDsgaSA8IG5vZGUtPm51bV9rZXlzIC0gMTsgaSsrKQogICAgICAgICAgICBub2RlLT5rZXlbaV0gPSBub2RlLT5rZXlbaSArIDFdOwoKICAgICAgICBub2RlLT5udW1fa2V5cy0tOwogICAgfQoKICAgIC8vID09PT09PT09PT09PT09PT09PT09IEJvcnJvdyBGcm9tIFByZXZpb3VzID09PT09PT09PT09PT09PT09PT09CgogICAgdm9pZCBib3Jyb3dGcm9tUHJldihOb2RlPFR5cGUsIE9yZD4qIHBhcmVudCwgaW50IGlkeCkKICAgIHsKICAgICAgICBhdXRvKiBwID0gc3RhdGljX2Nhc3Q8SW50ZXJuYWxOb2RlPFR5cGUsIE9yZD4qPihwYXJlbnQpOwoKICAgICAgICBOb2RlPFR5cGUsIE9yZD4qIGNoaWxkID0gcC0+Y2hpbGRbaWR4XTsKICAgICAgICBOb2RlPFR5cGUsIE9yZD4qIHNpYmxpbmcgPSBwLT5jaGlsZFtpZHggLSAxXTsKCiAgICAgICAgZm9yIChpbnQgaSA9IGNoaWxkLT5udW1fa2V5czsgaSA+IDA7IGktLSkKICAgICAgICAgICAgY2hpbGQtPmtleVtpXSA9IGNoaWxkLT5rZXlbaSAtIDFdOwoKICAgICAgICBpZiAoIWNoaWxkLT5pc19sZWFmKQogICAgICAgIHsKICAgICAgICAgICAgYXV0byogYyA9IHN0YXRpY19jYXN0PEludGVybmFsTm9kZTxUeXBlLCBPcmQ+Kj4oY2hpbGQpOwogICAgICAgICAgICBhdXRvKiBzID0gc3RhdGljX2Nhc3Q8SW50ZXJuYWxOb2RlPFR5cGUsIE9yZD4qPihzaWJsaW5nKTsKCiAgICAgICAgICAgIGZvciAoaW50IGkgPSBjaGlsZC0+bnVtX2tleXMgKyAxOyBpID4gMDsgaS0tKQogICAgICAgICAgICAgICAgYy0+Y2hpbGRbaV0gPSBjLT5jaGlsZFtpIC0gMV07CgogICAgICAgICAgICBjLT5jaGlsZFswXSA9IHMtPmNoaWxkW3NpYmxpbmctPm51bV9rZXlzXTsKICAgICAgICAgICAgcy0+Y2hpbGRbc2libGluZy0+bnVtX2tleXNdID0gbnVsbHB0cjsKICAgICAgICB9CgogICAgICAgIGNoaWxkLT5rZXlbMF0gPSBwYXJlbnQtPmtleVtpZHggLSAxXTsKCiAgICAgICAgcGFyZW50LT5rZXlbaWR4IC0gMV0gPSBzaWJsaW5nLT5rZXlbc2libGluZy0+bnVtX2tleXMgLSAxXTsKCiAgICAgICAgY2hpbGQtPm51bV9rZXlzKys7CiAgICAgICAgc2libGluZy0+bnVtX2tleXMtLTsKICAgIH0KCiAgICAvLyA9PT09PT09PT09PT09PT09PT09PSBCb3Jyb3cgRnJvbSBOZXh0ID09PT09PT09PT09PT09PT09PT09CgogICAgdm9pZCBib3Jyb3dGcm9tTmV4dChOb2RlPFR5cGUsIE9yZD4qIHBhcmVudCwgaW50IGlkeCkKICAgIHsKICAgICAgICBhdXRvKiBwID0gc3RhdGljX2Nhc3Q8SW50ZXJuYWxOb2RlPFR5cGUsIE9yZD4qPihwYXJlbnQpOwoKICAgICAgICBOb2RlPFR5cGUsIE9yZD4qIGNoaWxkID0gcC0+Y2hpbGRbaWR4XTsKICAgICAgICBOb2RlPFR5cGUsIE9yZD4qIHNpYmxpbmcgPSBwLT5jaGlsZFtpZHggKyAxXTsKCiAgICAgICAgY2hpbGQtPmtleVtjaGlsZC0+bnVtX2tleXNdID0gcGFyZW50LT5rZXlbaWR4XTsKCiAgICAgICAgaWYgKCFjaGlsZC0+aXNfbGVhZikKICAgICAgICB7CiAgICAgICAgICAgIGF1dG8qIGMgPSBzdGF0aWNfY2FzdDxJbnRlcm5hbE5vZGU8VHlwZSwgT3JkPio+KGNoaWxkKTsKICAgICAgICAgICAgYXV0byogcyA9IHN0YXRpY19jYXN0PEludGVybmFsTm9kZTxUeXBlLCBPcmQ+Kj4oc2libGluZyk7CgogICAgICAgICAgICBjLT5jaGlsZFtjaGlsZC0+bnVtX2tleXMgKyAxXSA9IHMtPmNoaWxkWzBdOwoKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBzaWJsaW5nLT5udW1fa2V5czsgaSsrKQogICAgICAgICAgICAgICAgcy0+Y2hpbGRbaV0gPSBzLT5jaGlsZFtpICsgMV07CgogICAgICAgICAgICBzLT5jaGlsZFtzaWJsaW5nLT5udW1fa2V5c10gPSBudWxscHRyOwogICAgICAgIH0KCiAgICAgICAgcGFyZW50LT5rZXlbaWR4XSA9IHNpYmxpbmctPmtleVswXTsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBzaWJsaW5nLT5udW1fa2V5cyAtIDE7IGkrKykKICAgICAgICAgICAgc2libGluZy0+a2V5W2ldID0gc2libGluZy0+a2V5W2kgKyAxXTsKCiAgICAgICAgY2hpbGQtPm51bV9rZXlzKys7CiAgICAgICAgc2libGluZy0+bnVtX2tleXMtLTsKICAgIH0KCiAgICAvLyA9PT09PT09PT09PT09PT09PT09PSBNZXJnZSA9PT09PT09PT09PT09PT09PT09PQoKICAgIHZvaWQgbWVyZ2UoTm9kZTxUeXBlLCBPcmQ+KiBwYXJlbnQsIGludCBpZHgpCiAgICB7CiAgICAgICAgYXV0byogcCA9IHN0YXRpY19jYXN0PEludGVybmFsTm9kZTxUeXBlLCBPcmQ+Kj4ocGFyZW50KTsKCiAgICAgICAgTm9kZTxUeXBlLCBPcmQ+KiBsZWZ0ID0gcC0+Y2hpbGRbaWR4XTsKICAgICAgICBOb2RlPFR5cGUsIE9yZD4qIHJpZ2h0ID0gcC0+Y2hpbGRbaWR4ICsgMV07CgogICAgICAgIGludCBzaXplID0gbGVmdC0+bnVtX2tleXM7CgogICAgICAgIGxlZnQtPmtleVtzaXplXSA9IHBhcmVudC0+a2V5W2lkeF07CgogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgcmlnaHQtPm51bV9rZXlzOyBpKyspCiAgICAgICAgICAgIGxlZnQtPmtleVtzaXplICsgMSArIGldID0gcmlnaHQtPmtleVtpXTsKCiAgICAgICAgaWYgKCFsZWZ0LT5pc19sZWFmKQogICAgICAgIHsKICAgICAgICAgICAgYXV0byogbCA9IHN0YXRpY19jYXN0PEludGVybmFsTm9kZTxUeXBlLCBPcmQ+Kj4obGVmdCk7CiAgICAgICAgICAgIGF1dG8qIHIgPSBzdGF0aWNfY2FzdDxJbnRlcm5hbE5vZGU8VHlwZSwgT3JkPio+KHJpZ2h0KTsKCiAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDw9IHJpZ2h0LT5udW1fa2V5czsgaSsrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBsLT5jaGlsZFtzaXplICsgMSArIGldID0gci0+Y2hpbGRbaV07CiAgICAgICAgICAgICAgICByLT5jaGlsZFtpXSA9IG51bGxwdHI7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGxlZnQtPm51bV9rZXlzICs9IHJpZ2h0LT5udW1fa2V5cyArIDE7CgogICAgICAgIGZvciAoaW50IGkgPSBpZHg7IGkgPCBwYXJlbnQtPm51bV9rZXlzIC0gMTsgaSsrKQogICAgICAgICAgICBwYXJlbnQtPmtleVtpXSA9IHBhcmVudC0+a2V5W2kgKyAxXTsKCiAgICAgICAgZm9yIChpbnQgaSA9IGlkeCArIDE7IGkgPCBwYXJlbnQtPm51bV9rZXlzOyBpKyspCiAgICAgICAgICAgIHAtPmNoaWxkW2ldID0gcC0+Y2hpbGRbaSArIDFdOwoKICAgICAgICBwLT5jaGlsZFtwYXJlbnQtPm51bV9rZXlzXSA9IG51bGxwdHI7CgogICAgICAgIHBhcmVudC0+bnVtX2tleXMtLTsKCiAgICAgICAgZGVsZXRlIHJpZ2h0OwogICAgfQoKICAgIC8vID09PT09PT09PT09PT09PT09PT09IEZpeCBVbmRlcmZsb3cgPT09PT09PT09PT09PT09PT09PT0KCiAgICB2b2lkIGZpeENoaWxkKE5vZGU8VHlwZSwgT3JkPiogcGFyZW50LCBpbnQgaWR4KQogICAgewogICAgICAgIGF1dG8qIHAgPSBzdGF0aWNfY2FzdDxJbnRlcm5hbE5vZGU8VHlwZSwgT3JkPio+KHBhcmVudCk7CgogICAgICAgIE5vZGU8VHlwZSwgT3JkPiogY2hpbGQgPSBwLT5jaGlsZFtpZHhdOwoKICAgICAgICBpZiAoY2hpbGQtPm51bV9rZXlzID49IE1JTl9LRVlTKQogICAgICAgICAgICByZXR1cm47CgogICAgICAgIGlmIChpZHggPiAwICYmIHAtPmNoaWxkW2lkeCAtIDFdLT5udW1fa2V5cyA+IE1JTl9LRVlTKQogICAgICAgICAgICBib3Jyb3dGcm9tUHJldihwYXJlbnQsIGlkeCk7CiAgICAgICAgZWxzZSBpZiAoaWR4IDwgcGFyZW50LT5udW1fa2V5cyAmJgogICAgICAgICAgICAgICAgIHAtPmNoaWxkW2lkeCArIDFdLT5udW1fa2V5cyA+IE1JTl9LRVlTKQogICAgICAgICAgICBib3Jyb3dGcm9tTmV4dChwYXJlbnQsIGlkeCk7CiAgICAgICAgZWxzZSBpZiAoaWR4IDwgcGFyZW50LT5udW1fa2V5cykKICAgICAgICAgICAgbWVyZ2UocGFyZW50LCBpZHgpOwogICAgICAgIGVsc2UgaWYgKGlkeCA+IDApCiAgICAgICAgICAgIG1lcmdlKHBhcmVudCwgaWR4IC0gMSk7CiAgICB9CgogICAgLy8gPT09PT09PT09PT09PT09PT09PT0gUmVtb3ZlID09PT09PT09PT09PT09PT09PT09CgogICAgYm9vbCByZW1vdmVSZWN1cnNpdmUoTm9kZTxUeXBlLCBPcmQ+KiBub2RlLCBUeXBlIHZhbHVlKQogICAgewogICAgICAgIGludCBpZHg7CgogICAgICAgIGZvciAoaWR4ID0gMDsgaWR4IDwgbm9kZS0+bnVtX2tleXM7IGlkeCsrKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKHZhbHVlIDw9IG5vZGUtPmtleVtpZHhdKSBicmVhazsKICAgICAgICB9CgogICAgICAgIGlmIChpZHggPCBub2RlLT5udW1fa2V5cyAmJiB2YWx1ZSA9PSBub2RlLT5rZXlbaWR4XSkKICAgICAgICB7CiAgICAgICAgICAgIGlmIChub2RlLT5pc19sZWFmKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICByZW1vdmVGcm9tTGVhZihub2RlLCBpZHgpOwogICAgICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGF1dG8qIHAgPSBzdGF0aWNfY2FzdDxJbnRlcm5hbE5vZGU8VHlwZSwgT3JkPio+KG5vZGUpOwoKICAgICAgICAgICAgVHlwZSBwcmVkID0gZ2V0UHJlZGVjZXNzb3IocC0+Y2hpbGRbaWR4XSk7CgogICAgICAgICAgICBub2RlLT5rZXlbaWR4XSA9IHByZWQ7CgogICAgICAgICAgICBib29sIHJlbW92ZWQgPSByZW1vdmVSZWN1cnNpdmUocC0+Y2hpbGRbaWR4XSwgcHJlZCk7CgogICAgICAgICAgICBpZiAocmVtb3ZlZCkKICAgICAgICAgICAgICAgIGZpeENoaWxkKG5vZGUsIGlkeCk7CgogICAgICAgICAgICByZXR1cm4gcmVtb3ZlZDsKICAgICAgICB9CgogICAgICAgIGlmIChub2RlLT5pc19sZWFmKQogICAgICAgICAgICByZXR1cm4gZmFsc2U7CgogICAgICAgIGF1dG8qIHAgPSBzdGF0aWNfY2FzdDxJbnRlcm5hbE5vZGU8VHlwZSwgT3JkPio+KG5vZGUpOwoKICAgICAgICBib29sIHJlbW92ZWQgPSByZW1vdmVSZWN1cnNpdmUocC0+Y2hpbGRbaWR4XSwgdmFsdWUpOwoKICAgICAgICBpZiAocmVtb3ZlZCkKICAgICAgICAgICAgZml4Q2hpbGQobm9kZSwgaWR4KTsKCiAgICAgICAgcmV0dXJuIHJlbW92ZWQ7CiAgICB9CgogICAgLy8gPT09PT09PT09PT09PT09PT09PT0gRGlzcGxheSA9PT09PT09PT09PT09PT09PT09PQoKICAgIHZvaWQgZGlzcGxheU5vZGUoTm9kZTxUeXBlLCBPcmQ+KiBub2RlLCBpbnQgbGV2ZWwpIGNvbnN0CiAgICB7CiAgICAgICAgaWYgKG5vZGUgPT0gbnVsbHB0cikKICAgICAgICAgICAgcmV0dXJuOwoKICAgICAgICBjb3V0IDw8IHN0cmluZyhsZXZlbCAqIDQsICcgJykgPDwgIlsgIjsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBub2RlLT5udW1fa2V5czsgaSsrKQogICAgICAgICAgICBjb3V0IDw8IG5vZGUtPmtleVtpXSA8PCAiICI7CgogICAgICAgIGNvdXQgPDwgIl1cbiI7CgogICAgICAgIGlmICghbm9kZS0+aXNfbGVhZikKICAgICAgICB7CiAgICAgICAgICAgIGF1dG8qIHAgPSBzdGF0aWNfY2FzdDxJbnRlcm5hbE5vZGU8VHlwZSwgT3JkPio+KG5vZGUpOwoKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPD0gbm9kZS0+bnVtX2tleXM7IGkrKykKICAgICAgICAgICAgICAgIGRpc3BsYXlOb2RlKHAtPmNoaWxkW2ldLCBsZXZlbCArIDEpOwogICAgICAgIH0KICAgIH0KCiAgICAvLyA9PT09PT09PT09PT09PT09PT09PSBEZXN0cm95ID09PT09PT09PT09PT09PT09PT09CgogICAgdm9pZCBkZXN0cm95KE5vZGU8VHlwZSwgT3JkPiogbm9kZSkKICAgIHsKICAgICAgICBpZiAobm9kZSA9PSBudWxscHRyKQogICAgICAgICAgICByZXR1cm47CgogICAgICAgIGlmICghbm9kZS0+aXNfbGVhZikKICAgICAgICB7CiAgICAgICAgICAgIGF1dG8qIHAgPSBzdGF0aWNfY2FzdDxJbnRlcm5hbE5vZGU8VHlwZSwgT3JkPio+KG5vZGUpOwoKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPD0gbm9kZS0+bnVtX2tleXM7IGkrKykKICAgICAgICAgICAgICAgIGRlc3Ryb3kocC0+Y2hpbGRbaV0pOwogICAgICAgIH0KCiAgICAgICAgZGVsZXRlIG5vZGU7CiAgICB9CgpwdWJsaWM6CgogICAgQlRyZWUoKSA9IGRlZmF1bHQ7CgogICAgfkJUcmVlKCkKICAgIHsKICAgICAgICBkZXN0cm95KHJvb3QpOwogICAgfQoKICAgIEJUcmVlKGNvbnN0IEJUcmVlJikgPSBkZWxldGU7CiAgICBCVHJlZSYgb3BlcmF0b3I9KGNvbnN0IEJUcmVlJikgPSBkZWxldGU7CgogICAgLy8gPT09PT09PT09PT09PT09PT09PT0gU2VhcmNoID09PT09PT09PT09PT09PT09PT09CgogICAgYm9vbCBzZWFyY2goVHlwZSB2YWx1ZSkgY29uc3QKICAgIHsKICAgICAgICByZXR1cm4gc2VhcmNoTm9kZShyb290LCB2YWx1ZSk7CiAgICB9CgogICAgLy8gPT09PT09PT09PT09PT09PT09PT0gSW5zZXJ0ID09PT09PT09PT09PT09PT09PT09CgogICAgdm9pZCBpbnNlcnQoVHlwZSB2YWx1ZSkKICAgIHsKICAgICAgICBpZiAoc2VhcmNoKHZhbHVlKSkKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQgPDwgIlZhbHVlIGFscmVhZHkgZXhpc3RzIVxuIjsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KCiAgICAgICAgaWYgKHJvb3QgPT0gbnVsbHB0cikKICAgICAgICB7CiAgICAgICAgICAgIHJvb3QgPSBuZXcgTGVhZk5vZGU8VHlwZSwgT3JkPigpOwogICAgICAgICAgICByb290LT5rZXlbMF0gPSB2YWx1ZTsKICAgICAgICAgICAgcm9vdC0+bnVtX2tleXMgPSAxOwoKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KCiAgICAgICAgVHlwZSBwcm9tb3RlZHt9OwogICAgICAgIE5vZGU8VHlwZSwgT3JkPiogcmlnaHQgPSBudWxscHRyOwoKICAgICAgICBpZiAoaW5zZXJ0UmVjdXJzaXZlKHJvb3QsIHZhbHVlLCBwcm9tb3RlZCwgcmlnaHQpKQogICAgICAgIHsKICAgICAgICAgICAgYXV0byogbmV3Um9vdCA9IG5ldyBJbnRlcm5hbE5vZGU8VHlwZSwgT3JkPigpOwoKICAgICAgICAgICAgbmV3Um9vdC0+a2V5WzBdID0gcHJvbW90ZWQ7CiAgICAgICAgICAgIG5ld1Jvb3QtPm51bV9rZXlzID0gMTsKCiAgICAgICAgICAgIG5ld1Jvb3QtPmNoaWxkWzBdID0gcm9vdDsKICAgICAgICAgICAgbmV3Um9vdC0+Y2hpbGRbMV0gPSByaWdodDsKCiAgICAgICAgICAgIHJvb3QgPSBuZXdSb290OwogICAgICAgIH0KICAgIH0KCiAgICAvLyA9PT09PT09PT09PT09PT09PT09PSBSZW1vdmUgPT09PT09PT09PT09PT09PT09PT0KCiAgICB2b2lkIHJlbW92ZShUeXBlIHZhbHVlKQogICAgewogICAgICAgIGlmIChyb290ID09IG51bGxwdHIpCiAgICAgICAgewogICAgICAgICAgICBjb3V0IDw8ICJUcmVlIGlzIGVtcHR5IVxuIjsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KCiAgICAgICAgaWYgKCFzZWFyY2godmFsdWUpKQogICAgICAgIHsKICAgICAgICAgICAgY291dCA8PCAiVmFsdWUgbm90IGZvdW5kIVxuIjsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KCiAgICAgICAgcmVtb3ZlUmVjdXJzaXZlKHJvb3QsIHZhbHVlKTsKCiAgICAgICAgaWYgKHJvb3QtPm51bV9rZXlzID09IDApCiAgICAgICAgewogICAgICAgICAgICBOb2RlPFR5cGUsIE9yZD4qIG9sZFJvb3QgPSByb290OwoKICAgICAgICAgICAgaWYgKHJvb3QtPmlzX2xlYWYpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJvb3QgPSBudWxscHRyOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgYXV0byogcCA9IHN0YXRpY19jYXN0PEludGVybmFsTm9kZTxUeXBlLCBPcmQ+Kj4ocm9vdCk7CgogICAgICAgICAgICAgICAgcm9vdCA9IHAtPmNoaWxkWzBdOwogICAgICAgICAgICAgICAgcC0+Y2hpbGRbMF0gPSBudWxscHRyOwogICAgICAgICAgICB9CgogICAgICAgICAgICBkZWxldGUgb2xkUm9vdDsKICAgICAgICB9CiAgICB9CgogICAgLy8gPT09PT09PT09PT09PT09PT09PT0gRGlzcGxheSA9PT09PT09PT09PT09PT09PT09PQoKICAgIHZvaWQgZGlzcGxheVRyZWUoKSBjb25zdAogICAgewogICAgICAgIGlmIChyb290ID09IG51bGxwdHIpCiAgICAgICAgewogICAgICAgICAgICBjb3V0IDw8ICJUcmVlIGlzIGVtcHR5IVxuIjsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KCiAgICAgICAgZGlzcGxheU5vZGUocm9vdCwgMCk7CiAgICB9Cn07CgovLyA9PT09PT09PT09PT09PT09PT09PSBNYWluID09PT09PT09PT09PT09PT09PT09CgppbnQgbWFpbigpCnsKICAgIEJUcmVlPGludCwgMz4gdHJlZTsKCiAgICBpbnQgY2hvaWNlOwogICAgaW50IHZhbHVlOwoKICAgIHdoaWxlICh0cnVlKQogICAgewogICAgICAgIGNvdXQgPDwgIlxuPT09PT09PT09PSBCLVRyZWUgPT09PT09PT09PVxuIjsKICAgICAgICBjb3V0IDw8ICIxLiBJbnNlcnRcbiI7CiAgICAgICAgY291dCA8PCAiMi4gRGVsZXRlXG4iOwogICAgICAgIGNvdXQgPDwgIjMuIFNlYXJjaFxuIjsKICAgICAgICBjb3V0IDw8ICI0LiBEaXNwbGF5XG4iOwogICAgICAgIGNvdXQgPDwgIjAuIEV4aXRcbiI7CgogICAgICAgIGNvdXQgPDwgIkNob2ljZTogIjsKICAgICAgICBjaW4gPj4gY2hvaWNlOwoKICAgICAgICBzd2l0Y2ggKGNob2ljZSkKICAgICAgICB7CiAgICAgICAgICAgIGNhc2UgMToKICAgICAgICAgICAgICAgIGNvdXQgPDwgIkVudGVyIHZhbHVlOiAiOwogICAgICAgICAgICAgICAgY2luID4+IHZhbHVlOwogICAgICAgICAgICAgICAgdHJlZS5pbnNlcnQodmFsdWUpOwogICAgICAgICAgICAgICAgYnJlYWs7CgogICAgICAgICAgICBjYXNlIDI6CiAgICAgICAgICAgICAgICBjb3V0IDw8ICJFbnRlciB2YWx1ZTogIjsKICAgICAgICAgICAgICAgIGNpbiA+PiB2YWx1ZTsKICAgICAgICAgICAgICAgIHRyZWUucmVtb3ZlKHZhbHVlKTsKICAgICAgICAgICAgICAgIGJyZWFrOwoKICAgICAgICAgICAgY2FzZSAzOgogICAgICAgICAgICAgICAgY291dCA8PCAiRW50ZXIgdmFsdWU6ICI7CiAgICAgICAgICAgICAgICBjaW4gPj4gdmFsdWU7CgogICAgICAgICAgICAgICAgaWYgKHRyZWUuc2VhcmNoKHZhbHVlKSkKICAgICAgICAgICAgICAgICAgICBjb3V0IDw8ICJGb3VuZCFcbiI7CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgY291dCA8PCAiTm90IEZvdW5kIVxuIjsKCiAgICAgICAgICAgICAgICBicmVhazsKCiAgICAgICAgICAgIGNhc2UgNDoKICAgICAgICAgICAgICAgIHRyZWUuZGlzcGxheVRyZWUoKTsKICAgICAgICAgICAgICAgIGJyZWFrOwoKICAgICAgICAgICAgY2FzZSAwOgogICAgICAgICAgICAgICAgY291dCA8PCAiR29vZGJ5ZSFcbiI7CiAgICAgICAgICAgICAgICBicmVhazsKCiAgICAgICAgICAgIGRlZmF1bHQ6CiAgICAgICAgICAgICAgICBjb3V0IDw8ICJJbnZhbGlkIGNob2ljZSFcbiI7CiAgICAgICAgfQoKICAgICAgICBpZiAoY2hvaWNlID09IDApIGJyZWFrOwogICAgfQoKICAgIHJldHVybiAwOwp9

Success #stdin #stdout 0.01s 5308KB

stdin

copy

Standard input is empty

stdout

copy

========== B-Tree ==========
1. Insert
2. Delete
3. Search
4. Display
0. Exit
Choice: Goodbye!

https://ideone.com/CgTO90

language:

C++ (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language