From 149cae2ad431d69da2171561d9dbe51021c86b6d Mon Sep 17 00:00:00 2001 From: Ethereal Date: Sun, 20 Feb 2011 12:49:48 -0700 Subject: [PATCH] The R-tree is sophisticated enough to support basic insertions and searches. Of course, as long as a node does not need to be split . . . --- include/storage/RTree.h | 161 +++++++++++++++++++++++++++++++++++++++++++++--- src/monitor/Aesalon.cpp | 25 +++++++- 2 files changed, 175 insertions(+), 11 deletions(-) diff --git a/include/storage/RTree.h b/include/storage/RTree.h index cb27f3f..313ab16 100644 --- a/include/storage/RTree.h +++ b/include/storage/RTree.h @@ -12,6 +12,8 @@ #include +#include "util/MessageSystem.h" + namespace Storage { /** An n-dimensional R-tree. @@ -22,15 +24,21 @@ class RTree { public: class Range { private: + bool m_valid; Key m_start, m_end; public: - Range(Key start = 0, Key end = 0) : m_start(start), m_end(end) {} + Range() : m_valid(false) {} + Range(Key start, Key end) : m_valid(true), m_start(start), m_end(end) {} + bool valid() const { return m_valid; } Key start() const { return m_start; } Key end() const { return m_end; } Key size() const { return m_end - m_start; } bool overlaps(const Range &other) const { + Message(Debug, "Overlap test:"); + Message(Debug, "\tm_start: " << m_start << "\t m_end: " << m_end); + Message(Debug, "\tother.m_start: " << other.m_start << "\tother.m_end: " << other.m_end); if(m_start > other.m_end || other.m_start > m_end) return false; return true; } @@ -54,6 +62,7 @@ public: void setRange(Range &range, int dimension) { m_ranges[dimension] = range; } Range &range(int dimension) { return m_ranges[dimension]; } + const Range &range(int dimension) const { return m_ranges[dimension]; } bool overlaps(const Bound &other) { for(int i = 0; i < Dimensions; i ++) { @@ -61,6 +70,20 @@ public: } return true; } + + void enclose(const Bound &other) { + for(int i = 0; i < Dimensions; i ++) { + if(m_ranges[i].valid() && other.m_ranges[i].valid()) { + m_ranges[i] = Range( + std::min(m_ranges[i].start(), other.m_ranges[i].start()), + std::max(m_ranges[i].end(), other.m_ranges[i].end())); + } + else if(other.m_ranges[i].valid()) { + m_ranges[i] = other.m_ranges[i]; + } + // If other.m_ranges[i] is not valid, nothing needs to be done. + } + } }; class SearchProcessor { @@ -81,13 +104,16 @@ protected: bool m_isLeaf; Branch m_branches[Maximum]; int m_branchCount; + Node *m_parent; public: - Node(bool isLeaf) : m_isLeaf(isLeaf) {} + Node(bool isLeaf) : m_isLeaf(isLeaf), m_branchCount(0), m_parent(NULL) {} bool isLeaf() const { return m_isLeaf; } Branch &branch(int which) { return m_branches[which]; } int branchCount() const { return m_branchCount; } void setBranchCount(int count) { m_branchCount = count; } + Node *parent() const { return m_parent; } + void setParent(Node *node) { m_parent = node; } }; private: Node *m_root; @@ -101,14 +127,15 @@ private: void search(const Bound &bound, Node *node, SearchProcessor *processor); Node *chooseLeaf(const Bound &bound); - Node *splitNode(Node *node, const Bound &bound, Value value); - Node *adjustTree(Node *l, Node *ll); + Node *adjustTree(Node *n, Node *nn); + + Node *splitNode(Node *node, Branch &branch); }; template RTree::RTree() { - m_root = NULL; + m_root = new Node(true); } template @@ -121,6 +148,8 @@ void RTree::search( const RTree::Bound &bound, RTree::SearchProcessor *processor) { + Message(Debug, "Beginning search."); + search(bound, m_root, processor); } @@ -129,17 +158,29 @@ void RTree::insert( const RTree::Bound &bound, Value value) { + Message(Debug, "Beginning insertion of value " << value); + + Message(Debug, "Calling chooseLeaf() . . ."); Node *leaf = chooseLeaf(bound), *ll = NULL; int count = leaf->branchCount(); if(count < Maximum) { + Message(Debug, "Leaf node count is less than the maximum, inserting as usual."); + leaf->branch(count).bound = bound; leaf->branch(count).value = value; leaf->setBranchCount(count+1); + Message(Debug, "Leaf node new branch count: " << leaf->branchCount()); } else { - ll = splitNode(leaf, bound, value); + Branch b; + b.bound = bound; + b.value = value; + ll = splitNode(leaf, b); } - Node *r = adjustTree(leaf, ll); + Message(Debug, "Calling adjustTree() . . ."); + adjustTree(leaf, ll); + + Message(Debug, "Finished."); } template @@ -151,9 +192,16 @@ void RTree::search( if(node == NULL) return; if(node->isLeaf()) { + Message(Debug, "At leaf node! Branch count: " << node->branchCount()); for(int i = 0; i < node->branchCount(); i ++) { Branch &branch = node->branch(i); - if(branch.bound.overlaps(bound)) processor->process(branch.bound, branch.value); + + Message(Debug, "Considering branch #" << i); + if(branch.bound.overlaps(bound)) { + Message(Debug, "Branch overlaps bound, processing . . ."); + processor->process(branch.bound, branch.value); + } + else Message(Debug, "Branch does not overlap bound, ignoring."); } } else { @@ -191,17 +239,110 @@ typename RTree::Node * } if(volume < smallestVolume || smallestNode == NULL) smallestNode = node, smallestVolume = volume; + else if(volume == smallestVolume) { + /* TODO: implement tiebreaker. */ + Message(Debug, "Tie-breaker not implemented!"); + } } - /* TODO: implement tiebreaker. */ - node = smallestNode; } + Message(Debug, "Found leaf node."); + Message(Debug, "Leaf node branch count: " << node->branchCount()); + return node; } +template +typename RTree::Node * + RTree::adjustTree( + RTree::Node *n, + RTree::Node *nn) { + + while(n != m_root) { + Node *p = n->parent(); + + int i = 0; + for(; i < p->branchCount(); i ++) { + if(p->branch(i).node == n) { + break; + } + } + + Bound &bound = p->branch(i).bound; + + for(; i < n->branchCount(); i ++) { + bound.enclose(p->branch(i).bound); + } + + if(nn != NULL) { + // Add nn to p. + int count = p->branchCount(); + if(count < Maximum) { + for(i = 0; i < nn->branchCount(); i ++) { + p->branch(count).bound.enclose(nn->branch(i).bound); + } + p->branch(count).node = nn; + nn = NULL; + } + else { + // Invoke splitNode. TBI. + Message(Fatal, "Splitting nodes in adjustTree NYI."); + //nn = splitNode(n); + } + } + + n = p; + } + + return nn; +} +template +typename RTree::Node * + RTree::splitNode( + RTree::Node *node, + RTree::Branch &branch) { + + // Linear-time algorithm specified in original R-tree publication. + + Node *nn = new Node(node->isLeaf()); + nn->setParent(node->parent()); + + Branch list[Maximum+1]; + int listSize = Maximum-1; + + for(int i = 0; i < Maximum; i ++) { + list[i] = node->branch(i); + } + list[Maximum] = branch; + + Key lowestValues[Dimensions]; + Key highestValues[Dimensions]; + Branch lowestBranches[Dimensions]; + Branch highestBranches[Dimensions]; + + for(int i = 0; i < Dimensions; i ++) { + for(int j = 0; j < Maximum+1; j ++) { + if(lowestValues[i] > list[j].bound.range(i).start()) { + } + //lowestValues[i] = std::min(lowestValues[i], list[j].bound.range(i).start()); + //highestValues[i] = std::max(highestValues[i], list[j].bound.range(i).end()); + } + } + + while(true) { + + // PickNext algorithm for linear-time is to simply pick any. Choose the first. + + } + + node = NULL; + branch.node = NULL; + + return NULL; +} } // namespace Storage diff --git a/src/monitor/Aesalon.cpp b/src/monitor/Aesalon.cpp index 22b233d..656b03e 100644 --- a/src/monitor/Aesalon.cpp +++ b/src/monitor/Aesalon.cpp @@ -23,9 +23,32 @@ int main(int argc, char *argv[]) { int main(int argc, char *argv[]) { - typedef Storage::RTree RTree; + typedef Storage::RTree RTree; RTree rt; + RTree::Range range[] = { + RTree::Range(-2.0, 2.0) + }; + RTree::Bound b(range); + rt.insert(b, 0); + + class Processor : public RTree::SearchProcessor { + public: + virtual bool process(const RTree::Bound &bound, int value) { + Message(Debug, "Found value " << value); + } + }; + + Processor p; + + RTree::Range searchRange[] = { + RTree::Range(-3.0, 3.0) + }; + + RTree::Bound sb(searchRange); + + rt.search(searchRange, &p); + return 0; } -- 2.11.4.GIT