0

I wrote a simple KDTree structure for 2D Points and I currently have two traverse methods:

  • Build a vector of points that is returned (lot of copy)
  • Use a functional approach with a callback function (lot of function calls)

I would like to implement an iterator over this that I can use:

for (auto *Node : kdtree) {...}

What would be the starting point?

struct Node {
    int id;
    Vector point;
    Node *left, *right;
    Node(int id, double x, double y) : id(id), point(x, y), left(NULL), right(NULL) {}
};

class KDTree {
    Node *root;
    void insertNode(Node *node, int id, double x, double y);
    void searchNode(Node *node, double x, double y, double r, vector<int> &ids);
    void removeNode(Node *node, int id);
    void clearNode(Node *node);
    void traverseNode(Node *node, function<void(Node*)> func);
public:
    KDTree() : root(NULL) {}
    void remove(int id);
    void insert(int id, double x, double y);
    vector<int> search(double x, double y, double r);
    void clear();
    
    vector<Vector> traverse();
    void traverse(function<void(Node*)> func);
};

void KDTree::traverse(function<void(Node*)> func) {
    traverseNode(root, func);
}

void KDTree::traverseNode(Node *node, function<void(Node*)> func) {
    if (node == NULL) {
        return;
    }
    if (node->left != NULL) {
        func(node->left);
        traverseNode(node->left, func);
    }
    if (node->right != NULL) {
        func(node->right);
        traverseNode(node->left, func);
    }
}
nowox
  • 25,978
  • 39
  • 143
  • 293
  • How do you define "modern way"? And where is your own attempt at implementing the iterator? – UnholySheep Nov 29 '21 at 21:48
  • 1
    If you make a class that adheres to [Legacy Forward Iterator](https://en.cppreference.com/w/cpp/named_req/ForwardIterator), and give your linked list a `begin()` and `end()` function, you too can iterate through your container in a range-based for loop. – JohnFilleau Nov 29 '21 at 21:52
  • Would it be better to use the legacy iterator or the iterator_traits? In ether way I see examples that define another class such as `KDTreeIterator` that looks odd. – nowox Nov 29 '21 at 21:57
  • In this [answer](https://stackoverflow.com/a/8054856/2612235) I don't clearly see how I should implement it to my class `KDTree` – nowox Nov 29 '21 at 21:58
  • I wouldn't use recursive functions in production code, specially in cases like this. – Barmak Shemirani Nov 29 '21 at 22:26

0 Answers0