Data structure to represent menu which can have submenu

Question

For example I can have something like so,

A
B
 ba
 bb
C
 Ca
D

Right Now I have a 2D array,but this isn't very general, because I would need another dimension if I wanted to extend the maximum sublevel from 2 to 3. Any suggestions?

Answer 1

The Composite Pattern would be an appropriate application here:

(From wikipedia:) http://en.wikipedia.org/wiki/Composite_pattern

In your case:

• Create a base class called "Menu" (This corresponds to the Component part in the above diagram)
• Create a derived class called "MenuItem" (This corresponds to the Leaf part in the above diagram)
• Create a derived class called "SubMenu" (This corresponds to the Composite part in the above diagram) SubMenu can contain more Menu's - which can be more MenuItem's or SubMenu's.

You can achieve desired ordering of menu elements based on their insertion order into a Composite "SubMenu" by implementing a counter with each SubMenu object: each time you call aSubMenu.add(newMenuItemOrSubMenu), aSubMenu should increment its own counter and tag the new item with the ordering number. (Exact detail of the implementation is up to you, you don't have to use separate counter at all and just use a list or an array)

Answer 2

Perhaps this:

class MenuNode
{
public:
    MenuNode(std::string new_label);
    void Add(MenuNode * new_node);
private:
    std::string label;
    std::vector<MenuNode *> children; // changed to vector to preserve order
};

Usage:

MenuNode menu("root"),
         file("File"),
         edit("Edit"),
         open("Open..."),
         close("Close"),
         save("Save..."),
         prefs("Preferences"),
         yes_foo("Activate Foo"),
         no_foo("Deactivate Foo");

menu.Add(&file);
menu.Add(&edit);

file.Add(&open);
file.Add(&close);
file.Add(&save);

edit.Add(&prefs);

prefs.Add(&yes_foo);
prefs.Add(&no_foo);

Which represents:

Main Menu
  File
    Open...
    Close
    Save...
  Edit
    Preferences
      Activate Foo
      Deactivate Foo

Beware the obvious flaw with this example, the reliance on addresses of (probably) temporary variables. You wouldn't be able to create this in a function and return it.

Trivial parts of the implementation are missing as well, for example there is no way to traverse the private state of the nodes in the example code.

Answer 3

The Composite design pattern mentioned by sampson-chen was the right way for an implementation I did for a small developer monitor, letting you choose some test methods from a menu structure.

I have a base class "Menu Entry" from which I derive sub-menus and leafs (the menu entries). A leaf just executes something, while a sub menu opens another menu level.

For instance the base class could like similar to that (when you like to use shared_pointers):

 /*************************************************************//*!
 * @brief The base class for all menu entry types (sub menus and sub menu entries/items)
 ******************************************************************/
class MenuEntry : public boost::enable_shared_from_this<MenuEntry>
{

  public:
    virtual ~MenuEntry(){}

/**************************************************************//*!
 * @brief Default implementation to add menu entries; has to be re implemented
 * @param[in] newSubMenuEntry - the new menu entry (another sub menu or leaf)
 **************************************************************/
virtual void add(boost::shared_ptr<MenuEntry> newSubMenuEntry)=0;

/*****************************************************************//*!
 * @brief Default implementation for call to menu entries; always returns false
 * @return false - the function has not been re implemented
 ****************************************************************/
virtual bool call(void)
{
  // the member function has not been re-implemented
  return false;
}

/*****************************************************************************//*!
 * @brief Default implementation, has to be reimplemented
 * @return emptyVector - an empty vector
 *********************************************************************************/
virtual std::vector<boost::shared_ptr<MenuEntry> > getChildren(void)
{
  std::vector<boost::shared_ptr<MenuEntry> > emptyVector;
  return emptyVector;
}


/*******************************************************************************//*!
 * @brief Gives a pointer to the parent of the actual menu entry
 * @return m_parent - pointer to the parent
 ******************************************************************************/
boost::shared_ptr<MenuEntry> parent(void)
{
  return m_parent;
}

/***************************************************************************//*!
 * @brief Default implementation for selecting a menu entry
 * @param[in] desiredMenuEntry - the desired menu entry which shall be selected
 * @return notExisting - a pointer to <b>this</b>
 **********************************************************************************/
virtual boost::shared_ptr<MenuEntry> select(boost::shared_ptr<MenuEntry> desiredMenuEntry)=0;

/**************************************************************************//*!
 * <B>Criticality: C0 \n\n</B>
 * @brief Sets a pointer to the parent of new menu entry
 * @param[in] pointerToParent - pointer to the parent
 ****************************************************************************/
void setParent(boost::shared_ptr<MenuEntry> pointerToParent)
{
  m_parent = pointerToParent;
}

/***************************************************************************//*!
 * @brief Default implementation for destroying children
 *****************************************************************************/
virtual void destroy(void)=0;

  protected:
    /************************************************************************//*!
     * @brief Constructor for a menu entry (sub menu or leaf)
     * @param[in] menuEntryName - the name for the sub menu or leaf
     *************************************************************************/
    MenuEntry(std::string menuEntryName)
    {
      m_menuEntryName = menuEntryName;
    }

};

In the select method I check via return value if I have a leaf which executes something, or a sub menu, for which I have to change my pointers.

For convenience you can add methods which find you all the child menu entries in a sub menu for displaying, or methods which construct you a title line with the actual menu path or the like... Another idea would be methods for scanning your menu tree in order to avoid double menu entries asf.

Answer 4

Use a tree. This is best defined in a tree anyway.

where: the rootNode is connected to A, B, C, D. B is connected to ba and bb. C is connected to Ca. etc.