Main Issues
#Main Issues AsAs it currently stands, I see 2 main issues:
Documentation
#Documentation WhatWhat is a "multi-walk" tree? An LCRS tree? I've never heard either term. I can look up LCRS Tree in Wikipedia or whatever and figure out which one it is, but it sure would be nice to have a link in a comment somewhere. Or at least expand the acronym once. I've used these plenty of times but never heard it called by that name. As for "multi-walk" tree, I can't find any information on what that is. Because the words "walk" and "tree" have such common meanings, my searches turned up nothing useful. (There were 2 Stack Overflow results, but both have since been deleted!) So you should probably at least document something basic about that type of tree, or list some synonyms, or link to something that explains it.
Interfaces
#Interfaces
ItIt seems like the point of having all these different types of trees, but requiring the user to define which one to use is that they share the same interface. This is like defining an abstract base class called Tree, which is very useful. But it turns out they don't share the same interface! LCRS and Multi-walk have different insert/delete function prototypes and the other trees don't have a parseFunc type definition. So that's a little odd. I would make the parseFunc be a member of the implementations of the LCRS and Multi-walk trees and not pass the function in to the insert/delete item functions. However, that may mean having to have different newTree() functions, as you generally want members to be fully defined after creating a new instance. It's a tricky problem.
Naming
#Naming
AsAs I mentioned in the arrayImpl answer, you've named things a little oddly. You have <something>Tree() and tree<something>() names. You should make them consistent. I notice you also named the deallocation function destroyTree() whereas other deallocation functions are named free<something>(). It would be good to make those consistent as well.
Don't Repeat Yourself
#Don't Repeat Yourself What'sWhat's the difference between an LCRS tree, a binary tree, a binary search tree, and a multi-walk tree with only 2 siblings per node? They look like the same thing to me. Maybe it makes sense to only have the multi-walk tree, but have a flag the user can set to say "this is an LCRS tree", or whatever type it is? Otherwise, I feel like you're going to write the same code several times.
Answers
#Answers ToTo answer your actual questions:
#Main Issues As it currently stands, I see 2 main issues:
#Documentation What is a "multi-walk" tree? An LCRS tree? I've never heard either term. I can look up LCRS Tree in Wikipedia or whatever and figure out which one it is, but it sure would be nice to have a link in a comment somewhere. Or at least expand the acronym once. I've used these plenty of times but never heard it called by that name. As for "multi-walk" tree, I can't find any information on what that is. Because the words "walk" and "tree" have such common meanings, my searches turned up nothing useful. (There were 2 Stack Overflow results, but both have since been deleted!) So you should probably at least document something basic about that type of tree, or list some synonyms, or link to something that explains it.
#Interfaces
It seems like the point of having all these different types of trees, but requiring the user to define which one to use is that they share the same interface. This is like defining an abstract base class called Tree, which is very useful. But it turns out they don't share the same interface! LCRS and Multi-walk have different insert/delete function prototypes and the other trees don't have a parseFunc type definition. So that's a little odd. I would make the parseFunc be a member of the implementations of the LCRS and Multi-walk trees and not pass the function in to the insert/delete item functions. However, that may mean having to have different newTree() functions, as you generally want members to be fully defined after creating a new instance. It's a tricky problem.
#Naming
As I mentioned in the arrayImpl answer, you've named things a little oddly. You have <something>Tree() and tree<something>() names. You should make them consistent. I notice you also named the deallocation function destroyTree() whereas other deallocation functions are named free<something>(). It would be good to make those consistent as well.
#Don't Repeat Yourself What's the difference between an LCRS tree, a binary tree, a binary search tree, and a multi-walk tree with only 2 siblings per node? They look like the same thing to me. Maybe it makes sense to only have the multi-walk tree, but have a flag the user can set to say "this is an LCRS tree", or whatever type it is? Otherwise, I feel like you're going to write the same code several times.
#Answers To answer your actual questions:
Main Issues
As it currently stands, I see 2 main issues:
Documentation
What is a "multi-walk" tree? An LCRS tree? I've never heard either term. I can look up LCRS Tree in Wikipedia or whatever and figure out which one it is, but it sure would be nice to have a link in a comment somewhere. Or at least expand the acronym once. I've used these plenty of times but never heard it called by that name. As for "multi-walk" tree, I can't find any information on what that is. Because the words "walk" and "tree" have such common meanings, my searches turned up nothing useful. (There were 2 Stack Overflow results, but both have since been deleted!) So you should probably at least document something basic about that type of tree, or list some synonyms, or link to something that explains it.
Interfaces
It seems like the point of having all these different types of trees, but requiring the user to define which one to use is that they share the same interface. This is like defining an abstract base class called Tree, which is very useful. But it turns out they don't share the same interface! LCRS and Multi-walk have different insert/delete function prototypes and the other trees don't have a parseFunc type definition. So that's a little odd. I would make the parseFunc be a member of the implementations of the LCRS and Multi-walk trees and not pass the function in to the insert/delete item functions. However, that may mean having to have different newTree() functions, as you generally want members to be fully defined after creating a new instance. It's a tricky problem.
Naming
As I mentioned in the arrayImpl answer, you've named things a little oddly. You have <something>Tree() and tree<something>() names. You should make them consistent. I notice you also named the deallocation function destroyTree() whereas other deallocation functions are named free<something>(). It would be good to make those consistent as well.
Don't Repeat Yourself
What's the difference between an LCRS tree, a binary tree, a binary search tree, and a multi-walk tree with only 2 siblings per node? They look like the same thing to me. Maybe it makes sense to only have the multi-walk tree, but have a flag the user can set to say "this is an LCRS tree", or whatever type it is? Otherwise, I feel like you're going to write the same code several times.
Answers
To answer your actual questions:
EDIT Question from comments:
Do you have any comments on the way every function is conditionally compiled using macros?
I feel like I covered this above, but to make it more clear: personally, I don't like it. If you are working in some sort of constrained environment such as an embedded processor and absolutely need to keep binary size to a minimum, then it's probably worth doing. Otherwise, it makes using the code a lot harder. A user of this code now has to know what type of Tree they're going to use, and what it's going to be backed by (a linked list or array). The savings in code size will be insignificant on a modern desktop or mobile device. Also, maintaining it seems harder than it needs to be. Any time you change the interface, you now have to update each implementation and compile and test them. Because you can only have one at a time, that likely means compiling several different projects. It's very likely to miss something in the process.
EDIT Question from comments:
Do you have any comments on the way every function is conditionally compiled using macros?
I feel like I covered this above, but to make it more clear: personally, I don't like it. If you are working in some sort of constrained environment such as an embedded processor and absolutely need to keep binary size to a minimum, then it's probably worth doing. Otherwise, it makes using the code a lot harder. A user of this code now has to know what type of Tree they're going to use, and what it's going to be backed by (a linked list or array). The savings in code size will be insignificant on a modern desktop or mobile device. Also, maintaining it seems harder than it needs to be. Any time you change the interface, you now have to update each implementation and compile and test them. Because you can only have one at a time, that likely means compiling several different projects. It's very likely to miss something in the process.
Looking at the tree implementation I have to say that this is really ambitious. It's a great way to learn how these algorithms work. Kudos to you!
That said, if you're going to use these types of data structures and algorithms professionally, I'd recommend using an existing library. In 30 years of professional development, I've never had to write my own, and the few times I tried, I've ended up with subtle bugs.
#Main Issues As it currently stands, I see 2 main issues:
- When I start development of a project, I may not know which particular implementation of a container I need. I may have a general idea that I need a tree, but not have a specific one in mind. Making me set a bunch of
#defines just to get working seems cumbersome. - As it currently stands, a user of this code can't have more than one type of tree in same file due to macros. If I needed to, say, put incoming network packets into a priority queue, then as I pull them out I need to put them into a binary search tree, I can't because I can only define
Treeas being one of those 2 things. At least, I can't do it in the same file. That seems problematic to me.
#Documentation What is a "multi-walk" tree? An LCRS tree? I've never heard either term. I can look up LCRS Tree in Wikipedia or whatever and figure out which one it is, but it sure would be nice to have a link in a comment somewhere. Or at least expand the acronym once. I've used these plenty of times but never heard it called by that name. As for "multi-walk" tree, I can't find any information on what that is. Because the words "walk" and "tree" have such common meanings, my searches turned up nothing useful. (There were 2 Stack Overflow results, but both have since been deleted!) So you should probably at least document something basic about that type of tree, or list some synonyms, or link to something that explains it.
#Interfaces
It seems like the point of having all these different types of trees, but requiring the user to define which one to use is that they share the same interface. This is like defining an abstract base class called Tree, which is very useful. But it turns out they don't share the same interface! LCRS and Multi-walk have different insert/delete function prototypes and the other trees don't have a parseFunc type definition. So that's a little odd. I would make the parseFunc be a member of the implementations of the LCRS and Multi-walk trees and not pass the function in to the insert/delete item functions. However, that may mean having to have different newTree() functions, as you generally want members to be fully defined after creating a new instance. It's a tricky problem.
Looking at all this, it occurs to me that you're manually reinventing object-oriented programming with this approach. You've got an abstract base class (or interface), you've got inheritance, and you've got polymorphism. Is there a reason why you don't just write this in an object-oriented language? It seems very well suited for this particular job.
#Naming
As I mentioned in the arrayImpl answer, you've named things a little oddly. You have <something>Tree() and tree<something>() names. You should make them consistent. I notice you also named the deallocation function destroyTree() whereas other deallocation functions are named free<something>(). It would be good to make those consistent as well.
#Don't Repeat Yourself What's the difference between an LCRS tree, a binary tree, a binary search tree, and a multi-walk tree with only 2 siblings per node? They look like the same thing to me. Maybe it makes sense to only have the multi-walk tree, but have a flag the user can set to say "this is an LCRS tree", or whatever type it is? Otherwise, I feel like you're going to write the same code several times.
#Answers To answer your actual questions:
- Does the code structure that involves conditional compilation, at function level, looks maintainable? If no, can the code get further structured that minimizes conditional compilations?
It's probably maintainable, but I don't feel it's very usable for the reasons stated at the beginning. Mainly that I can't use 2 different types of tree at the same time. Also, having the user of the code pick which type may not be the best idea.
- As per this declaration, void inOrderTraversal(Tree *, visitFunc); inOrder traversal is applied on N-ary tree(N>2). As per this answer, does it practically make sense to apply on other than a binary tree?
I've never heard of that happening. Do you know of any uses for it? If not, then I'd say YAGNI (You aren't going to need it), so don't make it an option.
- Further, PriorityQueue abstraction code will not be part of tree directory, by definition. It will sit in codedirectory. Please confirm the correction of this approach.
I think making a PriorityQueue type that internally uses (or even is) a Tree is a fine idea. Users of a priority queue don't care how it's implemented, so long as it works and meets their performance criteria.