////////////////////////////////////////////////////////////////////////////// // This file is part of the Journey MMORPG client // // Copyright © 2015-2016 Daniel Allendorf // // // // This program is free software: you can redistribute it and/or modify // // it under the terms of the GNU Affero General Public License as // // published by the Free Software Foundation, either version 3 of the // // License, or (at your option) any later version. // // // // This program is distributed in the hope that it will be useful, // // but WITHOUT ANY WARRANTY; without even the implied warranty of // // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // // GNU Affero General Public License for more details. // // // // You should have received a copy of the GNU Affero General Public License // // along with this program. If not, see . // ////////////////////////////////////////////////////////////////////////////// #pragma once #include #include #include namespace jrc { template class QuadTree { public: enum Direction { LEFT, RIGHT, UP, DOWN }; QuadTree(std::function c) : comparator(c), root(0) {} QuadTree() : QuadTree(nullptr) {} void clear() { nodes.clear(); root = 0; } void add(K key, V value) { K parent = 0; if (root) { K current = root; while (current) { parent = current; current = nodes[parent].addornext(key, value, comparator); } } else { root = key; } nodes.emplace( std::piecewise_construct, std::forward_as_tuple(key), std::forward_as_tuple(value, parent, 0, 0, 0, 0) ); } void erase(K key) { if (!nodes.count(key)) { return; } Node& toerase = nodes[key]; std::vector leaves; for (size_t i = LEFT; i <= DOWN; ++i) { K leafkey = toerase[i]; if (leafkey) { leaves.push_back(leafkey); } } K parent = toerase.parent; if (root == key) { root = 0; } else if (nodes.count(parent)) { nodes[parent].erase(key); } nodes.erase(key); for (auto& leaf : leaves) { readd(parent, leaf); } } K findnode(const V& value, std::function predicate) { if (root) { K key = findfrom(root, value, predicate); return predicate(value, nodes[key].value) ? key : 0; } else { return 0; } } V& operator[](K key) { return nodes[key].value; } const V& operator[](K key) const { return nodes.at(key).value; } private: K findfrom(K start, const V& value, std::function predicate) { if (!start) { return 0; } bool fulfilled = predicate(value, nodes[start].value); Direction dir = comparator(value, nodes[start].value); if (dir == RIGHT) { K right = findfrom(nodes[start].right, value, predicate); if (right && predicate(value, nodes[right].value)) { return right; } else { return start; } } else if (dir == DOWN) { K bottom = findfrom(nodes[start].bottom, value, predicate); if (bottom && predicate(value, nodes[bottom].value)) { return bottom; } else if (fulfilled) { return start; } else { K right = findfrom(nodes[start].right, value, predicate); if (right && predicate(value, nodes[right].value)) { return right; } else { return start; } } } else if (dir == UP) { K top = findfrom(nodes[start].top, value, predicate); if (top && predicate(value, nodes[top].value)) { return top; } else if (fulfilled) { return start; } else { K right = findfrom(nodes[start].right, value, predicate); if (right && predicate(value, nodes[right].value)) { return right; } else { return start; } } } else { K left = findfrom(nodes[start].left, value, predicate); if (left && predicate(value, nodes[left].value)) { return left; } else if (fulfilled) { return start; } K bottom = findfrom(nodes[start].bottom, value, predicate); if (bottom && predicate(value, nodes[bottom].value)) { return bottom; } else if (fulfilled) { return start; } K top = findfrom(nodes[start].top, value, predicate); if (top && predicate(value, nodes[top].value)) { return top; } else if (fulfilled) { return start; } K right = findfrom(nodes[start].right, value, predicate); if (right && predicate(value, nodes[right].value)) { return right; } else { return start; } } } void readd(K start, K key) { if (start) { K parent = 0; K current = start; while (current) { parent = current; current = nodes[parent].addornext(key, nodes[key].value, comparator); } nodes[key].parent = parent; } else if (start == root) { root = key; nodes[key].parent = 0; } else if (root) { readd(root, key); } } struct Node { V value; K parent; K left; K right; K top; K bottom; Node(const V& v, K p, K l, K r, K t, K b) : value(v), parent(p), left(l), right(r), top(t), bottom(b) {} Node() : Node(V(), 0, 0, 0, 0, 0) {} void erase(K key) { if (left == key) { left = 0; } else if (right == key) { right = 0; } else if (top == key) { top = 0; } else if (bottom == key) { bottom = 0; } } K addornext(K key, V val, std::function cmptor) { Direction dir = cmptor(val, value); K dirkey = leaf(dir); if (!dirkey) { switch (dir) { case LEFT: left = key; break; case RIGHT: right = key; break; case UP: top = key; break; case DOWN: bottom = key; break; } } return dirkey; } K leaf(Direction dir) { switch (dir) { case LEFT: return left; case RIGHT: return right; case UP: return top; case DOWN: return bottom; default: return 0; } } K operator[](size_t d) { auto dir = static_cast(d); return leaf(dir); } }; std::function comparator; std::unordered_map nodes; K root; }; }