I understand how you feel, but the admins said to us not to install anything, so I will feel bad if doing so.
I understand how you feel, but the admins said to us not to install anything, so I will feel bad if doing so.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
O_oshouldn't we free what we allocated?
Yes, but the "who" is important: who owns the resource allocated? The owner is responsible for deletion.
In other words, if you create multiple references to the same node, only one reference holder is the owner. If you say to yourself "each node owns its children" and structure your code accordingly chaining a `freeChildren' function as you have is perfectly fine.
You could go for shared ownership, but that is more complicated.
Yes, but care must be taken to ensure that nodes may only be created from `new'.Can an object safely delete itself?
Consider what happens when you create a `Inner' on the stack and call `freeTree': most likely a crash or anything awful.
In practice, this approach is fine, but again care must be taken to ensure the object is created with `new'; this is usually accomplished by making the constructor `private' and making a factory function a `friend' of the class. (The factory function just forwards construction parameters returning a `new' pointer to the class.)
However, anyone attempting "self deletion" should realize that once `delete' is called the object literally does not exist: once `delete' is called no `virtual' methods, members, or of instance specific aspect of the object may be touched in any way.
The example has all the appearance of being safer without being meaningfully safer when the rules of "self deletion" are followed.This might be safer (a function that's not part of any object)
Both `freeNode' and `DeleteTree' destroy an object and all children belonging to that object without otherwise touching any reference. Basically, if a reference to an object is used after `delete' operator is used the programmer is at fault for using an invalidated reference. With `DeleteTree' the point of invalidation is, semantically, the point after `DeleteTree' returns, but any references may still be, wrongly, used. A similar situation is true with `freeNode' where the primary difference is the point of invalidation; with `freeNode' the point of invalidation is the `delete' line which basically means even `this' is invalid within `freeNode'.
Well, certainly, you should have a virtual destructor if you plan on using `delete' polymorphically.And you need to add a virtual destructor to Node
Here though, with destruction already `virtual' from `freeTree', you don't also need a `virtual' destructor. Wthin `freeTree' the exact type of `this' is known from within the overridden virtual method so `delete' will call the correct destructor. However, this is one of the problems with "self deletion" of the form posted: if `freeTree' is not overridden by a class, such as a refinement of `Leaf', `delete' will use the wrong destructor. So, yes, even with this type of "self deletion" the destructor should arguably be `virtual'.
That all said, a better approach is only using `delete' for owned objects and considering `this' as owned by some other object with a `virtual' destructor and appropriate interfaces.
As you can see, there is no "delete this" in sight, but even still, the destruction of the tree happens recursively by virtue of the chain of ownership: the tree owns the "root" node, which is destroyed as part of the lifetime of a `Tree' object, where the "root" node is responsible for destroying its own owned nodes.Code:class Node { // ... virtual ~Node() { } // ... }; class Inner: public Node { // ... virtual ~Inner() { freeChildren(); } // ... void freeChildren() { delete mLeft; delete mRight; } // ... void releaseChildren() { mLeft = 0; mRight = 0; } // ... }; class Tree { // ... ~Tree() { delete mRoot; } // ... Inner * mRoot; // ... };
With most compilers it is sufficient to simply not name parameters which are unused:And you can eliminate the "unused parameter" warnings for setLeft and setRight in Leaf like this:
That said, operations on pointers themselves are trivial, and you should use this fact. (Such trivial operations do not raise exceptions.) If we return, partially, to earlier code you had the right idea: the `VECTOR', named ` v', should be an owned reference to an allocated `VECTOR'. With that small change, allocating the storage `VECTOR', the allocation of new nodes may fail, but that is the only point of failure for most tree operations. Many primitive tree operations, such as inserting a new "inner node" node between a "leaf node" and "inner node", may be accomplished by allocating the new, setting the pointers, and swapping the node entirely with an existing node. Because the "swap" can't raise an exception, we have easy "commit or rollback" semantics: an insertion either completes entirely or fails entirely leaving the tree in the same state it was when the attempt to insert was made.Code:void setLeft(Node*) {} // avoid unused parameter warning void setRight(Node*) {}
All that said, this is pretty bad way to go about this construct. You have, as it stands, broken polymorphisms with respect to a node, the tree, and multiple trees within the same program. I suggest at least exploring the possibility of just using dumb nodes.
This structure isn't fancy, but the tree can easily branch any node: if data is not null you allocate a new branch, swap the `data' pointers, and assign the newly created branch `left' or `right' depending on what kind of tree you are creating.Code:struct node { node * parent; node * left; node * right; std::vector<Data> * data; };
Soma
“Salem Was Wrong!” -- Pedant Necromancer
“Four isn't random!” -- Gibbering Mouther
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
So, yes we need to get rid from the unused parameter warnings.
My Inner class has an object, that I need to get. The Leaf class does not have it.
I had:
and then I would do something like thisCode:virtual Point3d& split() { return p; }
By going to this:Code:root->split().memberFunctionOfPoint3d
I can not access the methods like before. Any ideas?Code:virtual void split(Point3d& )
[EDIT]
I have tried many things but none of them worked. Maybe we should find another way to get rid of the unused parameter warning.
Last edited by std10093; 09-04-2013 at 07:51 PM.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
phantomotap pointed out (and I should have remembered this) that on most compilers simply leaving out the parameter name is enough to suppress the warning.
If that doesn't work on your compiler then you can do this:Code:int func(int) { }
But since you use gcc, the first solution should work and seems better, though it may be less portable (?).Code:int func(int x) { (void)x; }
The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss
I recommend commenting out the parameter name rather than deleting it outright.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
O_oI can not access the methods like before. Any ideas?
You weren't getting an unused parameter warning from `virtual Point3d& split()' in the first place. If you made the change for that sake, the warning comes elsewhere within your code.
If you are fine chancing it for the sake of syntax, return a pointer:
You could return a reference and use exceptions for an object where `split' would fail to provide a reference, but now you've added needless polymorphisms, exceptions, and sacrificed code readability for a tiny bit of syntax.Code:virtual Point3d* split(); // ... // ... root->split()->memberFunctionOfPoint3d
I wouldn't recommend such things unless you already know `split' returns a valid reference for a particular object. You can test this in several ways, but all of them leave you querying the type directly or indirectly so why not just do your job and test a pointer for validity on the spot?
Code:virtual Point3d* split(); // ... // ... Whatever * s(root->split()); if(s) s->memberFunctionOfPoint3d // ...You can't chain the methods with the example you posted because you chose to return `void'; the problem has nothing to do with parameters.Maybe we should find another way to get rid of the unused parameter warning.
If `split' had a parameter, `virtual Point3d& split(int f)', then the omission works fine and without warnings for many compilers:
Code:Point3d & split ( int ) { // ... } // ... root->split(/*whatever*/).memberFunctionOfPoint3d // ...If you want portable, you will need macros of form:But since you use gcc, the first solution should work and seems better, though it may be less portable (?).
Code:#if defined(__GNUC__) /* || defined(others) */ # define unused(X) # define suppress(X) #else # define unused(X) X # define suppress(X) (void)X #endif void DoSomething ( void * unused(fWhatever) ) { suppress(fWhatever); }... in defense of "self documentation"?I recommend commenting out the parameter name rather than deleting it outright.
You can have the function declaration keep the parameter name yet not use it with the definition.
I would even recommend, as it is what I do, not "decorating" the parameter name in the headers if one goes the macro path.
Soma
“Salem Was Wrong!” -- Pedant Necromancer
“Four isn't random!” -- Gibbering Mouther
I agree about readability. As oogabooga's signature says simplicity is the ultimate sophistication (L. da Vinci). The more simple our code is, the more readable it is!
So, I had a really rough time deciding to take or not the approach of polymorphism.
So - of course - I thought about the struct phantomotap suggested before, which was like this:
(D is the dimension in which the code runs, I have used D = 3 for simplicity)
So I thought to make them pointers, in order to dynamically allocate - deallocate data, so the struct would be actually something like this:Code:struct{ Point3d split; // Need this only in inner nodes std::vector<int> v; // Need this only in leaves Pointers array[8]; // Need this only in inner nodes }
So, the inner nodes, would have the split point and the pointers alive and the vector pointer set to null (a useless pointer per inner node).Code:struct{ Point3d* split; // Need this only in inner nodes std::vector<int>* v; // Need this only in leaves Pointers array[8]; // Need this only in inner nodes }
As for the leaves, split and array would be useless pointers, 9 in number per leaf.
Imagine now an Octree of one-level depth only:
Number of unused pointers:
1 // vector pointer in root
+ 8 * 9 // 9 unused pointers per leaf
= 73 unused pointers for a tree of only one level.
I want to use as less memory as a programmer of my level can. Moreover, I saw that the readability is affected only in quadtree.h. Readability in implementation file of quadtree did not get affected from the its previous state (that used the struct I have above).
As a result, I decided to go for this approach (even if someone raises some great argument and convince me that I should give up on this approach and turn back to the struct I have above, I will not regret the time I spent on polymorphism (why is this red-highlighted by the spelling check? Did I spell it wrong?), because it really refreshed my knowledge. (thanks oogabooga)
I have a question however:
Why is this necessary?Code:virtual ~Node() { } // does nothing, but necessary
As for the warning: no return statement in function returning non-void, I decided to go with the approach of returning a pointer, rather than a reference.
I have enclosed the classes Node, Inner and Leaf in the class of the tree (I made them Inner classes). That way, I do not think that I can have access issues outside the class of the tree.
Do you think using pointers rather than references in the return types can cause problems? The cost is the same I guess.
EDIT:
I also found the std:air, but I do not think I am going to go for this.
Last edited by std10093; 09-05-2013 at 09:42 AM.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
Node's virtual destructor let's you completely delete Inner objects pointed to by Node* variables. Welcome to inheritance. And polymorphism.Why is this necessary?Code:virtual ~Node() { } // does nothing, but necessary
Last edited by whiteflags; 09-05-2013 at 09:39 AM.
Oh I see. Well I was welcomed in 2011, but I had to write a good C++ project from the summer of the same year.
And whiteflags, I am also interested in the question about having the returning type as a pointer, instead of a reference. Doesn't it have the same cost? Since the function returning the pointer is a public one of the inner class. The inner class is in the private field of the outer class. The outer class provides only two associated public methods, which are the factory functions phantomotap suggested. I can not make the returning pointer a const one, because, I want the private methods of the outer class to be able to modify the object that the pointer points to.
Code:/** * Factory function for an inner node. * @return - pointer to the new inner node */ Inner* createInner() { Inner* temp = new Inner; if(temp) return temp; // Check if allocation succeeded else std::cout << "Error in createInner" << std::endl; return 0; } /** * Factory function for a leaf. * @return - pointer to the new leaf */ Leaf* createLeaf() { Leaf* temp = new Leaf; if(temp) return temp; // Check if allocation succeeded else std::cout << "Error in createLeaf" << std::endl; return 0; }
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
As far as I know, the only reason pointers are used is because createInner() and createLeaf() allocates via new, and the return value needs to be a type suitable for delete.
I am referring to the get functions of the Inner and Leaf classes.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
Oh. Well that is information I didn't have before. In general I think those functions, the get functions of Inner and Leaf, are design flaws. Since they return the implementation of the class, it is very easy to abuse. But right now you are using those functions to traverse the tree. I've never seen anyone traverse a data structure with references before, because if the variable you use to mark your current place is a reference, it can't be reassigned or empty (null). References are different from pointers, in that pointers can be reassigned, pointers can be null, and references cannot.
So wait, is there a final product version of this? I like the idea of a polymorphic tree and I'd be very interested in seeing the final product. If not try to do it myself as well because it sounds fun/interesting. I'm addicted to trees. Trees best structure!!!
Whiteflags has a point and I am going to do some changes. I can post it when I am done John, if you like of course.
In order to make the factory functions work, I had to do the outer class friend of the two inner classes (Inner and Leaf). That way I have access. However this will affect the readability a bit in the .cpp file, because of the static castings I am going to do.
As a consequence, all the get functions are not needed anymore. Moreover, the "getType" function is also unesescairy (whiteflags had told a mnemonic rule to remember the spelling, but I forgot, both the rule and the spelling :P ), since I can use dynamic_cast.
I wanted to do something like this:
but did not work...Code:typedef (static_cast<const Inner*>) (cast);
Last edited by std10093; 09-05-2013 at 04:35 PM.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson