/* Weemenu!  Uses 12 bytes of RAM and no heap allocation.

If you configure it to support less than its default 8 levels of
menu nesting, it will use even less memory.

Existing menu stuff for the Arduino sucked, building menu trees in
RAM and stupid shit like that.  So this is a really wee menu, which
doesn’t store the entire menu tree in RAM.

You can avoid storing the menu labels in RAM too, but only at the cost
of manually copying each of them into a RAM buffer:

    char buf[16];
    if (m.item(strcpy_P(buf, PSTR("Open door")))) open_door();
    if (m.item(strcpy_P(buf, PSTR("Close door")))) close_door();

It should be possible with enough
<http://playground.arduino.cc/Learning/Memory> says:

> Version 1.0 of the Arduino IDE introduced the F() syntax for
> storing strings in flash memory rather than RAM. e.g.

>        Serial.println(F("This string will be stored in flash memory"));

This seems to be the F() macro from
<http://andybrown.me.uk/wk/wp-content/images//avr-gcc-4.7.0/WString.h>,
which is defined as
class __FlashStringHelper;
#define F(string_literal) (reinterpret_cast<const __FlashStringHelper *>\
 (PSTR(string_literal)))
which means that supporting it isn’t totally free; you need an
override that accepts a const __FlashStringHelper (a class that
doesn’t actually exist, but serves to make it possible to provide
overrides that distinguish between flash strings and RAM strings).
LiquidCrystal::print does have such an override.

(Or maybe <https://github.com/johnmccombs/arduino-libraries/blob/master/Flash/Flash.h>,
which defines it as
#define F(str) (_FLASH_STRING(PSTR(str)).Printable())

where _FLASH_STRING is an actual class with different methods to
access it.

*/

template <typename canvas, int max_nesting = 8>
struct weeweemenu {
  // For menu nesting, the user’s current position needs to be an
  // array of locations (one for each level of nesting) and a counter
  // of the current nesting level; and the current tree-walking
  // position is then two counters, of the current nesting level and
  // one of the position within that nesting level.  Something like
  // this:
  char user_index[max_nesting]; // User’s current pos in each nesting level.
  char user_nesting_level;      // Which level the user is on.
  char walk_depth;    // Current level of walking the tree.
  char walk_index;    // Current position on current walking level.
  enum actions_enum { drawing = 1, selecting = 2, returning = 4 };
  char actions;                 // Bitmask of actions_enum.

  char& goal_index()
  {
    return user_index[(int)walk_depth];
  }

  weeweemenu() : user_nesting_level(0)
  {
    go_to_root(); 
  }

  char& visible_index()
  {
    return user_index[(int)user_nesting_level];
  }

public:
  void go_to_root()
  {
    user_nesting_level = 0;
    visible_index() = 0;
  }

  bool item(const char *label) 
  {
    if (user_nesting_level != walk_depth) {
      walk_index++;
      return false;
    }

    if (actions & drawing) {
      if (walk_index == goal_index()) {
        canvas::print(this, 0, "[");
        canvas::print(this, 0, label);
        canvas::println(this, 0, "]");
      } else {
        canvas::println(this, walk_index - goal_index(), label);
      }
    }

    return (walk_index++ == goal_index()) && (actions & selecting);
  }

  bool nest(const char *label)
  {
    // First, if the user is in this nested menu or a submenu, we just
    // need to move the tree walk down to that level; we signal to the
    // tree that we want to enter the nested menu by returning true
    // here.  But only if we’re not in the process of returning.
    if (!(actions & returning)
        && walk_index == goal_index()
        && user_nesting_level > walk_depth) {
      walk_depth++;
      walk_index = 0;
      return true;
    }

    // Second, we delegate to item() to handle any possible drawing;
    // note that this also increments walk_index.
    item(label);

    // Third, we need to handle our own selection behavior: moving the
    // user’s selection to the top of our submenu.
    if ((actions & selecting)
        && user_nesting_level == walk_depth 
        && walk_index - 1 == goal_index()) {
      user_nesting_level++;
      visible_index() = 0;
    }

    // Finally, we already decided we aren’t going to recurse into the
    // submenu.
    return false;
  }

  // End a level of menu.
  void end()
  {
    // Keep the user from marching off the bottom of a menu.
    if (user_nesting_level == walk_depth
        && visible_index() >= walk_index) {
      visible_index() = walk_index-1;
    }
    if (walk_depth) walk_depth--;
    // Prevent any further menu items from being drawn, selected, or
    // recursed into, because from here on out walk_index will be
    // bogus.
    actions = returning;
  }

  // Disallow copying in case someone accidentally writes main_tree
  // without an "&".
private:
  weeweemenu(weeweemenu<canvas, max_nesting> &) { }
};

template <typename canvas, typename menu_items, int max_nesting = 8>
class weemenu {
  weeweemenu<canvas, max_nesting> weewee;

  // Initiate a walk of the menu tree.
  void walk(char what_actions)
  {
    weewee.actions = what_actions;
    weewee.walk_depth = 0;
    weewee.walk_index = 0;
    menu_items::main_tree(weewee);
  }

public:
  void draw()
  {
    canvas::clear(this);
    walk(weewee.drawing);
    canvas::update(this);
  }

  void up()
  {
    if (weewee.visible_index()) weewee.visible_index()--;
  }

  void down()
  {
    weewee.visible_index()++;
    // Walk the tree, doing nothing, to bounds-check the new visible
    // index and make sure we haven’t moved off the end of a menu.
    walk(0);
  }

  void left()
  {
    if (weewee.user_nesting_level) weewee.user_nesting_level--;
  }

  void right()
  {
    walk(weewee.selecting);
  }
};