No i need to traverse the octree through an iterator, and the iterator needs to work with any octree. Since the iterator will be going to neighbor or child nodes, it needs to keep track of the last node it was in and give it to the octree so the octree can start the search from that node. But the nodes need to maintain octree specific data, the iterator needs to use void* because the node can be of whatever type, and the iterator doesnt really even need to know the type of the node. Its like if the octree asked the iterator to keep a number so it can identify the iterator and know which node it was at.

Or something.

Ill just go with void*

The claases serieved from octreebase (an abstract class) handle storage of the nodes differently. One might store them in a vector so the node contains an index to it. Another might use several buckets so the node contains a bucket index AND a normal index.

So each octree type has a corresponding node class.

To create a node one would do:
1.Iterator=OctreeBase->Root()
2.Iterator2=Iterator.AddChildNode(true,true,true) //x,y,z

Iterator AddChildNode(x,y,z)
{
nodePointer=octreeRef.AddChildNode(x,y,z,nodePointer)
}

virtual void* OctreeBase::AddChildNode(x,y,z,void* n)
{
specificNodeType& node=staticcastTospecificNodeType(n)
this.nodes[node.specificMember].DoStuff()
}

On my phone so hopefully that wasnt too unclear to show how i would do it currently.

Consider that there is no std::arbitrary_iterator that you can point at any container. There is wisdom in this design decision. Why do you think you need a common iterator type work with any octree implementation? Are you planning on choosing the octree implementation at runtime?

I wanted to be able to have a bucketed octree which stores the nodes in buckets, and the buckets in another octree (so nearby nodes are in same buckets).

And, i felt like making it be able to scale at runtime based on the amount of nodes. so i could make something like BucketedOctree(BucketedOctree(NormalOctree))

I probably wont ever have the need for that but i think it gets me better design if its flexible.

(i cant do this if the iterator is a template)



Though i have another problem now. The iterator cannot point directly to the node as they might get rearranged when adding and removing nodes. The iterator does have the node position so it can be looked up, but that requires traversing from the top so i dont want to do that more than once every time i do some operation lets say draw a ball inside the octree.

The solution i came up with:

Each octree has a vector of iterators. Each node contains an index to this vector. Iterators only contain the node theyre at, so no more than 1 iterator is needed for a node and can be shared between multiple users. If the node is moved, the iterator is updated. When an user want an iterator to a node currently not pointed at by iterators, an iterator is added to the vector and pointed to by the node, and returned to the user. When the iterator is not used anymore (its reference counted), the space is freed in the vector.

Pros:
-I can rearrange the nodes as much as i want
-When i move a node i only need to update the object pointing at it if it actually exists (with a redirection vector with all the nodes i always need to update it)
-The less iterators at a time i intend to have, the less space is taken.
-I dont need an index for every single node like in a redirection vector, only for each iterator.

Cons:
-The amount of iterators i can have is limited unless i use a resizeable vector and 32/64 bit indexes in the nodes to it (which is still good)
-Iterators need to be accessed through references :c
-Each node needs a few bits to index the iterator vector (though the space added would be tiny compared to the overall size of the nodes)

If theres no space for a new iterator, it could somehow throw old ones away and when theyre used the next time, they need to find the node using the absolute position of the node or something overly complex like that (another layer on top of the iterators? ) but thats just a possibility, not needed as long as i index the iterators using ints.


Does that sound awesome enough?

I know i would probably be fine with hardcoding it to work for what i want but i dont really have a goal and im still learning to use c++ so i might as well just think about a perfectly flexible design for everything so i dont have to remake it when i need to do something different (which i certainly would need to some day)

[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]The iterator cannot point directly to the node as they might get rearranged when adding and removing nodes.[/background]

[/font]
[/quote]
The standard library approaches this problem by introducing the concept of iterator invalidation, along with the rules for which operations can cause invalidation. For example, std::vector<T>::erase(std::vector<T>::iterator) invalidates iterators. The API helps by returning a new valid iterator to the next element, or the end iterator if no such element exists.

[background=rgb(250, 251, 252)]The iterator cannot point directly to the node as they might get rearranged when adding and removing nodes.[/background]

The standard library approaches this problem by introducing the concept of iterator invalidation, along with the rules for which operations can cause invalidation. For example, std::vector<T>::erase(std::vector<T>::iterator) invalidates iterators. The API helps by returning a new valid iterator to the next element, or the end iterator if no such element exists.
[/quote]

Doesnt that only work for the iterator doing the operation? I only allow deleting and adding child nodes, so the iterator doesnt break, but if the octree decides to move other nodes around to add or remove the child, i have a problem if i use pointers. And there might be other iterators too (other threads? o,e), and the tree might rearrange itself at any time to save space or optimize.

It depends on your definition of "work". Iterator invalidation works, as a design decision, because it disallows those kind of cases. I'm not sure what you can do to solve the case of multiple iterators into the same node in the tree, where one decides to structurally modify the tree such that element pointed to is deleted.

Thread safety is only going to add more difficulty on top. Generally, iteration is achieved in a two-step process - a test to see if the iterator has more elements and then accessing the elements. If other threads are allowed to modify the tree asynchronously, then there can be an inconsistency between these steps.

I would encourage you to consider a high level view on the multi-threading here. An external lock to manage the octree and all iterators is one approach. Another is to duplicate the information into each thread that needs it - thus preventing concurrent editing.