User:Narc/NCurses BinTree
From NarcWiki
Mini-design doc for a ncurses-displayed implementation of /CAVLTree, as shown in bin-tree2.cpp.
Contents |
Intention
To create something like this, but displayed in an xterm, using ncurses for the visuals.
Methodology
I will be using the existing implementations of CAVLTree and CAVLNode (see file://hermes/~narc/src/CAVL*.hpp).
Implementation details
Virtual "screen" space
Instead of drawing directly onto the screen, we will be drawing into a (much bigger) data structure instead. To display this data structure on screen, we will be making use of a "viewport", a subset of this data structure that can be scrolled and printed to the terminal, using ncurses.
This gives us two classes: CScreen and CViewport. A CViewport has a CScreen inside it, and any drawing to the viewport is done to the screen. Any drawing of the viewport will draw a subset of the CScreen, though in some cases (dumping to file), that subset may simply represent all of the not empty part of the CScreen.
A CScreen has coordinates (x,y). A CViewport has coordinates (top, left) and a size (width, height), which map onto the CScreen and onto the terminal.
Interface
There are two ncurses windows on the interface: the top one, providing the display area, extends from (0,0) to (LINES-1,COLS). The bottom one is the status line, from (LINES-1,0) to (LINES, COLS), and provides feedback, an input line, etc.
Commands
Commands will be handled as in vi, preceded by a ":" (colon) character. The default command will be ":add", and will be implied when a number is passed in. Abbreviations are permitted as long as they are unambiguous (e.g. ":del" for ":delete" is unambiguous because there is no other command starting with ":del").
Complete list of commands includes:
- :add -- add a number to the tree (pass number in as argument)
- :delete -- remove a number from the tree (see above)
- :lookup -- find and highlight a number in the tree
- :quit -- exit the program
- :dumpfile -- dump the full listing to a text file (passed in as argument), optionally overwriting (ask for confirmation!)
- :save -- save the tree to a file from which it can be restored using the :load command.
- :load -- load a tree from a file created by the :save command.
- :set -- change a setting.
- :balance -- force a manual rebalancing of the tree, if the $autobalance setting is off. No effect if $autobalance is on.
Commands can be chained using commas between them (e.g. ":a 4, :a 5, :d 4" is a valid chain), and the chain will be followed until a command fails (e.g., the example chain above will abort at ":a 5" if 5 is already in the tree). This requirement can be overridden by starting the chain with a "!" (exclamation point) (e.g. "!:a 4, :a 5, :d 4" will ignore errors).
Settings
Runtime settings can be modified using the :set command. They are saved in ~/.nc-bintree.conf.
Full listing of settings includes:
- animation -- (bool, default true) Master switch to turn animation on and off.
- autofocus -- (bool, default true) Whether to automatically focus on the currently animating part of the tree (e.g., during a lookup, animation will highlight each visited node, and which connection gets followed, by turning them bold yellow for $animation_delay milliseconds; this flag controls whether the highlighted area gets brought into focus automatically).
- animation_delay -- (int, default 250) Number of milliseconds to highlight animated parts.
- autobalance -- (bool, default true) Whether to automatically balance the tree on insert and delete. If off, the :balance command can be used to force a manual balancing. When turned on after being off, :balance will be called automatically to rebalance the tree before auto-balancing is activated.
Settings and the :set command
The :set command's basic syntax is :set <setting> <value>. For boolean settings, there is an alternative syntax: :set [no]<setting>, whereby a setting will be turned on if its name is given, or off if preceded by a "no". For instance, :set animation will turn on animation, and :set noanimation will turn it off.
