Handling leaves in tree-based menus

Question

Tl;Dr

Given a language with no polymorphism how to you elegantly modify the behavior of a leaf in a tree data structure.

Context

I'm programming an application in C for a microcontroller and I'm wondering what would be the best way to design flexible GUI-less menus.

Basically inputs may come from 2 different sources: The built-in buttons on the board used by the user and a Uart port used by the production team to calibrate the device before shipping.

I already have a mechanism using a thread to listen to inputs (from both the buttons and the serial port) who post them to a crude parser. The parser then takes action depending on the currently registered callback for the received input. It also knows if the menu must be printed on the LCD screen or through the serial port.

I'm also using a k-ary tree to represent the hierarchy between sub-menus and different options. Since the menus are not defined yet it'll allow me to simply add / remove nodes when my supervisor makes his mind on the supported features.

Now when the currently displayed menu is not a leaf, the behavior is quite simply. Left and Right moves between siblings, Back selects the parent and Enter selects the first child.

If its a leaf, Enter activates / deactivates modifications, Left and Right increment / decrement the value and Back cancels the moficiation.

Other concerns

• Am I over-engeenering stuff that could be done with a bunch of switch-cases?
• Are there ressources giving example of clean GUI-less menus when you don't know where the inputs come from, the actions you will have to take, the menus you must offer and where to display those menus?
• Since there is basically 2 options (leaf or not) should I just do everything with if/elses and move on?

Answer 1

The answer to this kind of question is always the same: if the language doesn't provide a useful abstraction, you must emulate it. (Whether doing this is worth the additional effort depends on the specific circumstances of your program, which you know better than we do, but for the purposes of this answer I'm assuming that it is.)

Polymorphism is the ability of objects of related classes to behave differently in response to the same message, and language implementers usually provide it by keeping type/class information associated with each object instance and consulting it when dispatching a message. So that is what you'd have to do yourself: implement a notion of "I'm a leaf"/"I'm an inner node" that an object can consult and change its behaviour accordingly. That can mean a type flag and switch statements in the appropriate places, but any other language construct that achieves the same could be used.

Such a solution can become inelegant as the program grows and a good illustration of why polymorphism was raised to the level of language feature in the first place, but it doesn't have to be. One example is the implementation of the virtual file system in the Linux kernel; despite the fact that it's pure C, i.e. with no class-related features, it allows adding new file systems very easily, and it's also reasonably easy to read (via C macros) and even a lot more efficient than the obvious C++ solution would be. (Greg Kroah-Hartman describes this in detail in his chapter of Beautiful code, so he thinks it's rather elegant indeed.)

Answer 2

1. Switch cases are still a viable option for such limited scenarios(it is doubtful that your tree navigation will ever change so radically, that switch case won't be able to handle it). It is the simplest solution, but not nesessarily the best.

2. So, I could recommend you to use pointer-to-functions to implement some sort of polymorphic behaviour:

   struct TreeElement
   {
       char* DisplayName;
   
       void (*Enter)(void);
   
       void (*MoveToPrevious)(void);
   
       void (*MoveToNext)(void);
   }    
   
   ReturnCode TreeElement_Leaf_Initialize(TreeElement* leaf, char* displayName ...)
   ReturnCode TreeElement_Node_Initialize(TreeElement* node, char* displayName ...)
   //...
   treeElement->Enter();
   

Well, you should think which functions(pointers-to-functions) exactly you would really need, but this solution is quite generic and will allow you to easily modify element behaviours and avoid huge switch-cases.

3. If your project is going to need something more powerful, than you may want to read this SO thread about how to turn your C program into C++ -like framework. Especially you may want to read this book.

P.S. Proposal 3 could easily become an overkill for most projects, so it should be used only for really complex projects for which C++ compiler cannot be used.

Answer 3

C provides plenty of polymorphism for what you're doing. Cast one pointer-to-function to another, cast pointer-to-struct or overlay them with unions. Some macros can really help the readability -- read some big C projects to get ideas of how. Just be careful, because the compiler won't help much.

Bullets:

• No, looks fine to me. Avoid switches.
• External resources? Search engines are good at that.
• No, avoid conditional logic too.

My view is you're on the right track. A menu structure should be modeled as data, and a node-leaf structure is a good match. Things that can be data should be data, because they're easier to read, test and maintain.