Integrated the visual formula editor patch

Ported the most recent version of the visual formula editor patch,
to LibreOffice. This patch is not finished yet, see README for more
information.

1 files changed, 445 insertions, 0 deletions

diff --git a/starmath/inc/caret.hxx b/starmath/inc/caret.hxx
new file mode 100644
index 000000000000..ae0f0fc1a0f4
--- /dev/null
+++ b/starmath/inc/caret.hxx
@@ -0,0 +1,445 @@
+#ifndef CARET_H
+#define CARET_H
+
+#include "node.hxx"
+
+/** Representation of caret position with an equantion */
+struct SmCaretPos{
+    SmCaretPos(SmNode* selectedNode = NULL, int iIndex = 0) {
+        pSelectedNode = selectedNode;
+        Index = iIndex;
+    }
+    /** Selected node */
+    SmNode* pSelectedNode;
+    /** Index within the selected node
+     *
+     * 0: Position infront of a node
+     * 1: Position after a node or after first char in SmTextNode
+     * n: Position after n char in SmTextNode
+     *
+     * Notice how there's special cases for SmTextNode.
+     */
+    //TODO: Special cases for SmBlankNode is needed
+    //TODO: Consider forgetting about the todo above... As it's really unpleasent.
+    int Index;
+    /** True, if this is a valid caret position */
+    bool IsValid() { return pSelectedNode != NULL; }
+    bool operator!=(SmCaretPos pos) const {
+        return pos.pSelectedNode != pSelectedNode || Index != pos.Index;
+    }
+    bool operator==(SmCaretPos pos) const {
+        return pos.pSelectedNode == pSelectedNode && Index == pos.Index;
+    }
+    /** Get the caret position after pNode, regardless of pNode
+     *
+     * Gets the caret position following pNode, this is SmCaretPos(pNode, 1).
+     * Unless pNode is an instance of SmTextNode, then the index is the text length.
+     */
+    static SmCaretPos GetPosAfter(SmNode* pNode) {
+        if(pNode && pNode->GetType() == NTEXT)
+            return SmCaretPos(pNode, ((SmTextNode*)pNode)->GetText().Len());
+        return SmCaretPos(pNode, 1);
+    }
+};
+
+/** A line that represents a caret */
+class SmCaretLine{
+public:
+    SmCaretLine(long left = 0, long top = 0, long height = 0) {
+        _top = top;
+        _left = left;
+        _height = height;
+    }
+    long GetTop() const {return _top;}
+    long GetLeft() const {return _left;}
+    long GetHeight() const {return _height;}
+    long SquaredDistanceX(SmCaretLine line) const{
+        return (GetLeft() - line.GetLeft()) * (GetLeft() - line.GetLeft());
+    }
+    long SquaredDistanceX(Point pos) const{
+        return (GetLeft() - pos.X()) * (GetLeft() - pos.X());
+    }
+    long SquaredDistanceY(SmCaretLine line) const{
+        long d = GetTop() - line.GetTop();
+        if(d < 0)
+            d = (d * -1) - GetHeight();
+        else
+            d = d - line.GetHeight();
+        if(d < 0)
+            return 0;
+        return d * d;
+    }
+    long SquaredDistanceY(Point pos) const{
+        long d = GetTop() - pos.Y();
+        if(d < 0)
+            d = (d * -1) - GetHeight();
+        if(d < 0)
+            return 0;
+        return d * d;
+    }
+private:
+    long _top;
+    long _left;
+    long _height;
+};
+
+/////////////////////////////// SmCaretPosGraph////////////////////////////////
+
+/** An entry in SmCaretPosGraph */
+struct SmCaretPosGraphEntry{
+    SmCaretPosGraphEntry(SmCaretPos pos = SmCaretPos(),
+                       SmCaretPosGraphEntry* left = NULL,
+                       SmCaretPosGraphEntry* right = NULL){
+        CaretPos = pos;
+        Left = left;
+        Right = right;
+    }
+    /** Caret position */
+    SmCaretPos CaretPos;
+    /** Entry to the left visually */
+    SmCaretPosGraphEntry* Left;
+    /** Entry to the right visually */
+    SmCaretPosGraphEntry* Right;
+    void SetRight(SmCaretPosGraphEntry* right){
+        Right = right;
+    }
+    void SetLeft(SmCaretPosGraphEntry* left){
+        Left = left;
+    }
+};
+
+/** Define SmCaretPosGraph to be less than one page 4096 */
+#define SmCaretPosGraphSize   255
+
+class SmCaretPosGraph;
+
+/** Iterator for SmCaretPosGraph */
+class SmCaretPosGraphIterator{
+public:
+    SmCaretPosGraphIterator(SmCaretPosGraph* graph){
+        pGraph = graph;
+        nOffset = 0;
+        pEntry = NULL;
+    }
+    /** Get the next entry, NULL if none */
+    SmCaretPosGraphEntry* Next();
+    /** Get the current entry, NULL if none */
+    SmCaretPosGraphEntry* Current(){
+        return pEntry;
+    }
+    /** Get the current entry, NULL if none */
+    SmCaretPosGraphEntry* operator->(){
+        return pEntry;
+    }
+private:
+    /** Next entry to return */
+    int nOffset;
+    /** Current graph */
+    SmCaretPosGraph* pGraph;
+    /** Current entry */
+    SmCaretPosGraphEntry* pEntry;
+};
+
+
+/** A graph over all caret positions
+ * @remarks Graphs can only grow, entries cannot be removed!
+ */
+class SmCaretPosGraph{
+public:
+    SmCaretPosGraph(){
+        pNext = NULL;
+        nOffset = 0;
+    }
+    ~SmCaretPosGraph();
+    SmCaretPosGraphEntry* Add(SmCaretPosGraphEntry entry);
+    SmCaretPosGraphEntry* Add(SmCaretPos pos,
+                            SmCaretPosGraphEntry* left = NULL,
+                            SmCaretPosGraphEntry* right = NULL){
+        j_assert(pos.Index >= 0, "Index shouldn't be -1!");
+        return Add(SmCaretPosGraphEntry(pos, left, right));
+    }
+    /** Get an iterator for this graph */
+    SmCaretPosGraphIterator GetIterator(){
+        return SmCaretPosGraphIterator(this);
+    }
+    friend class SmCaretPosGraphIterator;
+private:
+    /** Next graph, to be used when this graph is full */
+    SmCaretPosGraph* pNext;
+    /** Next free entry in graph */
+    int nOffset;
+    /** Entries in this graph segment */
+    SmCaretPosGraphEntry Graph[SmCaretPosGraphSize];
+};
+
+/** \page visual_formula_editing Visual Formula Editing
+ * A visual formula editor allows users to easily edit formulas without having to learn and
+ * use complicated commands. A visual formula editor is a WYSIWYG editor. For OpenOffice Math
+ * this essentially means that you can click on the formula image, to get a caret, which you
+ * can move with arrow keys, and use to modify the formula by entering text, clicking buttons
+ * or using shortcuts.
+ *
+ * \subsection formula_trees Formula Trees
+ * A formula in OpenOffice Math is a tree of nodes, take for instance the formula
+ * "A + {B cdot C} over D", it looks like this
+ * \f$ \mbox{A} + \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$. The tree for this formula
+ * looks like this:
+ *
+ * \dot
+ * digraph {
+ * labelloc = "t";
+ * label= "Equation: \"A  + {B  cdot C} over D\"";
+ * size = "9,9";
+ * n0 [label="SmTableNode (1)"];
+ * n0 -> n1 [label="0"];
+ * n1 [label="SmLineNode (2)"];
+ * n1 -> n2 [label="0"];
+ * n2 [label="SmExpressionNode (3)"];
+ * n2 -> n3 [label="0"];
+ * n3 [label="SmBinHorNode (4)"];
+ * n3 -> n4 [label="0"];
+ * n4 [label="SmTextNode: A (5)"];
+ * n3 -> n5 [label="1"];
+ * n5 [label="SmMathSymbolNode:  (6)"];
+ * n3 -> n6 [label="2"];
+ * n6 [label="SmBinVerNode (7)"];
+ * n6 -> n7 [label="0"];
+ * n7 [label="SmExpressionNode (8)"];
+ * n7 -> n8 [label="0"];
+ * n8 [label="SmBinHorNode (9)"];
+ * n8 -> n9 [label="0"];
+ * n9 [label="SmTextNode: B (10)"];
+ * n8 -> n10 [label="1"];
+ * n10 [label="SmMathSymbolNode: ⋅ (11)"];
+ * n8 -> n11 [label="2"];
+ * n11 [label="SmTextNode: C (12)"];
+ * n6 -> n12 [label="1"];
+ * n12 [label="SmRectangleNode (13)"];
+ * n6 -> n13 [label="2"];
+ * n13 [label="SmTextNode: D (14)"];
+ * }
+ * \enddot
+ *
+ * The vertices are nodes, their label says what kind of node and the number in parentheses is
+ *  the identifier of the node (In practices a pointer is used instead of the id). The direction
+ *  of the edges tells which node is parent and which is child. The label of the edges are the
+ *  child node index number, given to SmNode::GetSubNode() of the parent to get the child node.
+ *
+ *
+ * \subsection visual_lines Visual Lines
+ *
+ * Inorder to do caret movement in visual lines, we need a definition of caret position and
+ * visual line. In a tree such as the above there are three visual lines. There's the outer most
+ * line, with entries such as
+ * \f$\mbox{A}\f$, \f$ + \f$ and \f$ \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$. Then there's
+ *  the numerator line of the fraction it has entries \f$ \mbox{B} \f$, \f$ \cdot \f$ and \f$ \mbox{C} \f$.
+ *  And last by not least there's the denominator line of the fraction it's only entry is \f$ \mbox{D} \f$.
+ *
+ * For visual editing it should be possible to place a caret on both sides of any line entry,
+ * consider a line entry a character or construction that in a line is treated as a character.
+ *  Imagine the caret is placed to the right of the plus sign (id: 6), now if user presses
+ * backspace this should delete the plus sign (id: 6), and if the user presses delete this
+ * should delete the entire fraction (id: 7). This is because the caret is in the outer most
+ * line where the fraction is considered a line entry.
+ *
+ * However, inorder to prevent users from accidentally deleting large subtrees, just because
+ * they logically placed there caret a in the wrong line, require that complex constructions
+ * such as a fraction is selected before it is deleted. Thus in this case it wouldn't be
+ * deleted, but only selected and then deleted if the user hit delete again. Anyway, this is
+ * slightly off topic for now.
+ *
+ * Important about visual lines is that they don't always have an SmExpressionNode as root
+ * and the entries in a visual line is all the nodes of a subtree ordered left to right that
+ *  isn't either an SmExpressionNode, SmBinHorNode or SmUnHorNode.
+ *
+ *
+ * \subsection caret_positions Caret Positions
+ *
+ * A caret position in OpenOffice Math is representated by an instance of SmCaretPos.
+ * That is a caret position is a node and an index related to this node. For most nodes the
+ * index 0, means caret is infront of this node, the index 1 means caret is after this node.
+ * For SmTextNode the index is the caret position after the specified number of characters,
+ * imagine an SmTextNode with the number 1337. The index 3 in such SmTextNode would mean a
+ * caret placed right before 7, e.g. "133|7".
+ *
+ * For SmExpressionNode, SmBinHorNode and SmUnHorNode the only legal index is 0, which means
+ *  infront of the node. Actually the index 0 may only because for the first caret position
+ * in a visual line. From the example above, consider the following subtree that constitutes
+ * a visual line:
+ *
+ * \dot
+ * digraph {
+ * labelloc = "t";
+ * label= "Subtree that constitutes a visual line";
+ * size = "7,5";
+ * n7 [label="SmExpressionNode (8)"];
+ * n7 -> n8 [label="0"];
+ * n8 [label="SmBinHorNode (9)"];
+ * n8 -> n9 [label="0"];
+ * n9 [label="SmTextNode: B (10)"];
+ * n8 -> n10 [label="1"];
+ * n10 [label="SmMathSymbolNode: ⋅ (11)"];
+ * n8 -> n11 [label="2"];
+ * n11 [label="SmTextNode: C (12)"];
+ * }
+ * \enddot
+ * Here the caret positions are:
+ *
+ * <TABLE>
+ * <TR><TD><B>Caret position:</B></TD><TD><B>Example:</B></TD>
+ * </TR><TR>
+ *     <TD>{id: 8, index: 0}</TD>
+ *     <TD>\f$ \mid \mbox{C} \cdot \mbox{C} \f$</TD>
+ * </TR><TR>
+ *     <TD>{id: 10, index: 1}</TD>
+ *     <TD>\f$ \mbox{C} \mid \cdot \mbox{C} \f$</TD>
+ * </TR><TR>
+ *     <TD>{id: 11, index: 1}</TD>
+ *     <TD>\f$ \mbox{C} \cdot \mid \mbox{C} \f$</TD>
+ * </TR><TR>
+ *     <TD>{id: 12, index: 1}</TD>
+ *     <TD>\f$ \mbox{C} \cdot \mbox{C} \mid \f$</TD>
+ * </TR><TR>
+ * </TABLE>
+ *
+ * Where \f$ \mid \f$ is used to denote caret position.
+ *
+ * With these exceptions included in the definition the id and index: {id: 11, index: 0} does
+ * \b not constitute a caret position in the given context. Note the method
+ * SmCaretPos::IsValid() does not check if this invariant holds true, but code in SmCaret,
+ * SmSetSelectionVisitor and other places depends on this invariant to hold.
+ *
+ *
+ * \subsection caret_movement Caret Movement
+ *
+ * As the placement of caret positions depends very much on the context within which a node
+ * appears it is not trivial to find all caret positions and determine which follows which.
+ * In OpenOffice Math this is done by the SmCaretPosGraphBuildingVisitor. This visitor builds
+ * graph (an instnce of SmCaretPosGraph) over the caret positions. For details on how this
+ * graph is build, and how new methods should be implemented see SmCaretPosGraphBuildingVisitor.
+ *
+ * The result of the SmCaretPosGraphBuildingVisitor is a graph over the caret positions in a
+ * formula, representated by an instance of SmCaretPosGraph. Each entry (instances of SmCaretPosGraphEntry)
+ * has a pointer to the entry to the left and right of itself. This way we can easily find
+ * the caret position to a right or left of a given caret position. Note each caret position
+ * only appears once in this graph.
+ *
+ * When searching for a caret position after a left click on the formula this map is also used.
+ * We simply iterate over all entries, uses the SmCaretPos2LineVisitor to find a line for each
+ * caret position. Then the distance from the click to the line is computed and we choose the
+ * caret position closest to the click.
+ *
+ * For up and down movement, we also iterator over all caret positions and use SmCaretPos2LineVisitor
+ * to find a line for each caret position. Then we compute the distance from the current
+ * caret position to every other caret position and chooses the one closest that is either
+ * above or below the current caret position, depending on wether we're doing up or down movement.
+ *
+ * This result of this approach to caret movement is that we have logically predictable
+ * movement for left and right, whilst leftclick, up and down movement depends on the sizes
+ * and placement of all node and may be less logically predictable. This solution also means
+ * that we only have one complex visitor generating the graph, imagine the nightmare if we
+ * had a visitor for movement in each direction.
+ *
+ * Making up and down movement independent of node sizes and placement wouldn't necessarily
+ * be a good thing either. Consider the formula \f$ \frac{1+2+3+4+5}{6} \f$, if the caret is
+ * placed as displayed here: \f$ \frac{1+2+3+4+5}{6 \mid} \f$, up movement should move to right
+ * after "3": \f$ \frac{1+2+3|+4+5}{6} \f$. However, such a move depends on the sizes and placement
+ * of all nodes in the fraction.
+ *
+ *
+ * \subsubsection caretpos_graph_example Example of Caret Position Graph
+ *
+ * If we consider the formula
+ * \f$ \mbox{A} + \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$ from \ref formula_trees.
+ * It has the following caret positions:
+ *
+ * <TABLE>
+ * <TR>
+ *     <TD><B>Caret position:</B></TD>
+ *     <TD><B>Example:</B></TD>
+ * </TR><TR>
+ *     <TD>{id: 3, index: 0}</TD>
+ *     <TD>\f$ \mid\mbox{A} + \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$</TD>
+ * </TR><TR>
+ *     <TD>{id: 5, index: 1}</TD>
+ *     <TD>\f$ \mbox{A}\mid + \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$</TD>
+ * </TR><TR>
+ *     <TD>{id: 6, index: 1}</TD>
+ *     <TD>\f$ \mbox{A} + \mid \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$</TD>
+ * </TR><TR>
+ *     <TD>{id: 8, index: 0}</TD>
+ *     <TD>\f$ \mbox{A} + \frac{ \mid \mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$</TD>
+ * </TR><TR>
+ *     <TD>{id: 10, index: 1}</TD>
+ *     <TD>\f$ \mbox{A} + \frac{\mbox{B} \mid \cdot \mbox{C}}{\mbox{D}} \f$</TD>
+ * </TR><TR>
+ *     <TD>{id: 11, index: 1}</TD>
+ *     <TD>\f$ \mbox{A} + \frac{\mbox{B} \cdot \mid \mbox{C}}{\mbox{D}} \f$</TD>
+ * </TR><TR>
+ *     <TD>{id: 12, index: 1}</TD>
+ *     <TD>\f$ \mbox{A} + \frac{\mbox{B} \cdot \mbox{C} \mid}{\mbox{D}} \f$</TD>
+ * </TR><TR>
+ *     <TD>{id: 14, index: 0}</TD>
+ *     <TD>\f$ \mbox{A} + \frac{\mbox{B} \cdot \mbox{C}}{\mid \mbox{D}} \f$</TD>
+ * </TR><TR>
+ *     <TD>{id: 14, index: 1}</TD>
+ *     <TD>\f$ \mbox{A} + \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D} \mid} \f$</TD>
+ * </TR><TR>
+ *     <TD>{id: 7, index: 1}</TD>
+ *     <TD>\f$ \mbox{A} + \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \mid \f$</TD>
+ * </TR>
+ * </TABLE>
+ *
+ * Below is a directed graph over the caret postions and how you can move between them.
+ * \dot
+ * digraph {
+ *     labelloc = "t";
+ *     label= "Caret Position Graph";
+ *     size = "4,6";
+ *     p0 [label = "{id: 3, index: 0}"];
+ *     p0 -> p1 [fontsize = 10.0, label = "right"];
+ *     p1 [label = "{id: 5, index: 1}"];
+ *     p1 -> p0 [fontsize = 10.0, label = "left"];
+ *     p1 -> p2 [fontsize = 10.0, label = "right"];
+ *     p2 [label = "{id: 6, index: 1}"];
+ *     p2 -> p1 [fontsize = 10.0, label = "left"];
+ *     p2 -> p3 [fontsize = 10.0, label = "right"];
+ *     p3 [label = "{id: 8, index: 0}"];
+ *     p3 -> p2 [fontsize = 10.0, label = "left"];
+ *     p3 -> p4 [fontsize = 10.0, label = "right"];
+ *     p4 [label = "{id: 10, index: 1}"];
+ *     p4 -> p3 [fontsize = 10.0, label = "left"];
+ *     p4 -> p5 [fontsize = 10.0, label = "right"];
+ *     p5 [label = "{id: 11, index: 1}"];
+ *     p5 -> p4 [fontsize = 10.0, label = "left"];
+ *     p5 -> p6 [fontsize = 10.0, label = "right"];
+ *     p6 [label = "{id: 12, index: 1}"];
+ *     p6 -> p5 [fontsize = 10.0, label = "left"];
+ *     p6 -> p9 [fontsize = 10.0, label = "right"];
+ *     p7 [label = "{id: 14, index: 0}"];
+ *     p7 -> p2 [fontsize = 10.0, label = "left"];
+ *     p7 -> p8 [fontsize = 10.0, label = "right"];
+ *     p8 [label = "{id: 14, index: 1}"];
+ *     p8 -> p7 [fontsize = 10.0, label = "left"];
+ *     p8 -> p9 [fontsize = 10.0, label = "right"];
+ *     p9 [label = "{id: 7, index: 1}"];
+ *     p9 -> p6 [fontsize = 10.0, label = "left"];
+ * }
+ * \enddot
+ */
+
+/* TODO: Write documentation about the following keywords:
+ *
+ * Visual Selections:
+ *  - Show images
+ *  - Talk about how the visitor does this
+ *
+ * Modifying a Visual Line:
+ *  - Find top most non-compo of the line (e.g. The subtree that constitutes a line)
+ *  - Make the line into a list
+ *  - Edit the list, add/remove/modify nodes
+ *  - Parse the list back into a subtree
+ *  - Insert the new subtree where the old was taken
+ */
+
+#endif /* CARET_H */