bump product version to 7.2.5.1
[LibreOffice.git] / starmath / inc / caret.hxx
blobeff810792c2fdd06e30320f77a64504910a8d4b4
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3 * This file is part of the LibreOffice project.
5 * This Source Code Form is subject to the terms of the Mozilla Public
6 * License, v. 2.0. If a copy of the MPL was not distributed with this
7 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 */
10 #pragma once
12 #include <sal/config.h>
13 #include "node.hxx"
15 /** Representation of caret position with an equation */
16 struct SmCaretPos
18 SmCaretPos(SmNode* selectedNode = nullptr, int iIndex = 0)
19 : pSelectedNode(selectedNode)
20 , nIndex(iIndex)
22 assert(nIndex >= 0);
25 /** Selected node */
26 SmNode* pSelectedNode;
28 /** Index (invariant: non-negative) within the selected node
30 * 0: Position in front of a node
31 * 1: Position after a node or after first char in SmTextNode
32 * n: Position after n char in SmTextNode
34 * Notice how there's special cases for SmTextNode.
36 //TODO: Special cases for SmBlankNode is needed
37 //TODO: Consider forgetting about the todo above... As it's really unpleasant.
38 int nIndex;
40 /** True, if this is a valid caret position */
41 bool IsValid() const { return pSelectedNode != nullptr; }
42 bool operator==(const SmCaretPos& pos) const
44 return pos.pSelectedNode == pSelectedNode && nIndex == pos.nIndex;
46 /** Get the caret position after pNode, regardless of pNode
48 * Gets the caret position following pNode, this is SmCaretPos(pNode, 1).
49 * Unless pNode is an instance of SmTextNode, then the index is the text length.
51 static SmCaretPos GetPosAfter(SmNode* pNode)
53 if (pNode && pNode->GetType() == SmNodeType::Text)
54 return SmCaretPos(pNode, static_cast<SmTextNode*>(pNode)->GetText().getLength());
55 return SmCaretPos(pNode, 1);
59 /** A line that represents a caret */
60 class SmCaretLine
62 public:
63 SmCaretLine(tools::Long left = 0, tools::Long top = 0, tools::Long height = 0)
65 _top = top;
66 _left = left;
67 _height = height;
69 tools::Long GetTop() const { return _top; }
70 tools::Long GetLeft() const { return _left; }
71 tools::Long GetHeight() const { return _height; }
72 tools::Long SquaredDistanceX(const SmCaretLine& line) const
74 return (GetLeft() - line.GetLeft()) * (GetLeft() - line.GetLeft());
76 tools::Long SquaredDistanceX(const Point& pos) const
78 return (GetLeft() - pos.X()) * (GetLeft() - pos.X());
80 tools::Long SquaredDistanceY(const SmCaretLine& line) const
82 tools::Long d = GetTop() - line.GetTop();
83 if (d < 0)
84 d = (d * -1) - GetHeight();
85 else
86 d = d - line.GetHeight();
87 if (d < 0)
88 return 0;
89 return d * d;
91 tools::Long SquaredDistanceY(const Point& pos) const
93 tools::Long d = GetTop() - pos.Y();
94 if (d < 0)
95 d = (d * -1) - GetHeight();
96 if (d < 0)
97 return 0;
98 return d * d;
101 private:
102 tools::Long _top;
103 tools::Long _left;
104 tools::Long _height;
107 // SmCaretPosGraph
109 /** An entry in SmCaretPosGraph */
110 struct SmCaretPosGraphEntry
112 SmCaretPosGraphEntry(SmCaretPos pos, SmCaretPosGraphEntry* left, SmCaretPosGraphEntry* right)
113 : CaretPos{ pos }
114 , Left{ left }
115 , Right{ right }
118 /** Caret position */
119 const SmCaretPos CaretPos;
120 /** Entry to the left visually */
121 SmCaretPosGraphEntry* Left;
122 /** Entry to the right visually */
123 SmCaretPosGraphEntry* Right;
124 void SetRight(SmCaretPosGraphEntry* right) { Right = right; }
125 void SetLeft(SmCaretPosGraphEntry* left) { Left = left; }
128 /** A graph over all caret positions
129 * @remarks Graphs can only grow, entries cannot be removed!
131 class SmCaretPosGraph
133 public:
134 SmCaretPosGraph();
136 ~SmCaretPosGraph();
138 /** Add a caret position
139 * @remarks If left is NULL, they will point back to the entry.
141 SmCaretPosGraphEntry* Add(SmCaretPos pos, SmCaretPosGraphEntry* left = nullptr);
143 std::vector<std::unique_ptr<SmCaretPosGraphEntry>>::iterator begin()
145 return mvEntries.begin();
148 std::vector<std::unique_ptr<SmCaretPosGraphEntry>>::iterator end() { return mvEntries.end(); }
150 private:
151 std::vector<std::unique_ptr<SmCaretPosGraphEntry>> mvEntries;
154 /** \page visual_formula_editing Visual Formula Editing
155 * A visual formula editor allows users to easily edit formulas without having to learn and
156 * use complicated commands. A visual formula editor is a WYSIWYG editor. For OpenOffice Math
157 * this essentially means that you can click on the formula image, to get a caret, which you
158 * can move with arrow keys, and use to modify the formula by entering text, clicking buttons
159 * or using shortcuts.
161 * \subsection formula_trees Formula Trees
162 * A formula in OpenOffice Math is a tree of nodes, take for instance the formula
163 * "A + {B cdot C} over D", it looks like this
164 * \f$ \mbox{A} + \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$. The tree for this formula
165 * looks like this:
167 * \dot
168 * digraph {
169 * labelloc = "t";
170 * label= "Equation: \"A + {B cdot C} over D\"";
171 * size = "9,9";
172 * n0 [label="SmTableNode (1)"];
173 * n0 -> n1 [label="0"];
174 * n1 [label="SmLineNode (2)"];
175 * n1 -> n2 [label="0"];
176 * n2 [label="SmExpressionNode (3)"];
177 * n2 -> n3 [label="0"];
178 * n3 [label="SmBinHorNode (4)"];
179 * n3 -> n4 [label="0"];
180 * n4 [label="SmTextNode: A (5)"];
181 * n3 -> n5 [label="1"];
182 * n5 [label="SmMathSymbolNode: + (6)"];
183 * n3 -> n6 [label="2"];
184 * n6 [label="SmBinVerNode (7)"];
185 * n6 -> n7 [label="0"];
186 * n7 [label="SmExpressionNode (8)"];
187 * n7 -> n8 [label="0"];
188 * n8 [label="SmBinHorNode (9)"];
189 * n8 -> n9 [label="0"];
190 * n9 [label="SmTextNode: B (10)"];
191 * n8 -> n10 [label="1"];
192 * n10 [label="SmMathSymbolNode: &#183; (11)"];
193 * n8 -> n11 [label="2"];
194 * n11 [label="SmTextNode: C (12)"];
195 * n6 -> n12 [label="1"];
196 * n12 [label="SmRectangleNode (13)"];
197 * n6 -> n13 [label="2"];
198 * n13 [label="SmTextNode: D (14)"];
200 * \enddot
202 * The vertices are nodes, their label says what kind of node and the number in parentheses is
203 * the identifier of the node (In practices a pointer is used instead of the id). The direction
204 * of the edges tells which node is parent and which is child. The label of the edges are the
205 * child node index number, given to SmNode::GetSubNode() of the parent to get the child node.
208 * \subsection visual_lines Visual Lines
210 * Inorder to do caret movement in visual lines, we need a definition of caret position and
211 * visual line. In a tree such as the above there are three visual lines. There's the outer most
212 * line, with entries such as
213 * \f$\mbox{A}\f$, \f$ + \f$ and \f$ \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$. Then there's
214 * the numerator line of the fraction it has entries \f$ \mbox{B} \f$, \f$ \cdot \f$ and \f$ \mbox{C} \f$.
215 * And last by not least there's the denominator line of the fraction it's only entry is \f$ \mbox{D} \f$.
217 * For visual editing it should be possible to place a caret on both sides of any line entry,
218 * consider a line entry a character or construction that in a line is treated as a character.
219 * Imagine the caret is placed to the right of the plus sign (id: 6), now if user presses
220 * backspace this should delete the plus sign (id: 6), and if the user presses delete this
221 * should delete the entire fraction (id: 7). This is because the caret is in the outer most
222 * line where the fraction is considered a line entry.
224 * However, inorder to prevent users from accidentally deleting large subtrees, just because
225 * they logically placed there caret a in the wrong line, require that complex constructions
226 * such as a fraction is selected before it is deleted. Thus in this case it wouldn't be
227 * deleted, but only selected and then deleted if the user hit delete again. Anyway, this is
228 * slightly off topic for now.
230 * Important about visual lines is that they don't always have an SmExpressionNode as root
231 * and the entries in a visual line is all the nodes of a subtree ordered left to right that
232 * isn't either an SmExpressionNode, SmBinHorNode or SmUnHorNode.
235 * \subsection caret_positions Caret Positions
237 * A caret position in OpenOffice Math is represented by an instance of SmCaretPos.
238 * That is a caret position is a node and an index related to this node. For most nodes the
239 * index 0, means caret is in front of this node, the index 1 means caret is after this node.
240 * For SmTextNode the index is the caret position after the specified number of characters,
241 * imagine an SmTextNode with the number 1337. The index 3 in such SmTextNode would mean a
242 * caret placed right before 7, e.g. "133|7".
244 * For SmExpressionNode, SmBinHorNode and SmUnHorNode the only legal index is 0, which means
245 * in front of the node. Actually the index 0 may only because for the first caret position
246 * in a visual line. From the example above, consider the following subtree that constitutes
247 * a visual line:
249 * \dot
250 * digraph {
251 * labelloc = "t";
252 * label= "Subtree that constitutes a visual line";
253 * size = "7,5";
254 * n7 [label="SmExpressionNode (8)"];
255 * n7 -> n8 [label="0"];
256 * n8 [label="SmBinHorNode (9)"];
257 * n8 -> n9 [label="0"];
258 * n9 [label="SmTextNode: B (10)"];
259 * n8 -> n10 [label="1"];
260 * n10 [label="SmMathSymbolNode: &#183; (11)"];
261 * n8 -> n11 [label="2"];
262 * n11 [label="SmTextNode: C (12)"];
264 * \enddot
265 * Here the caret positions are:
267 * <TABLE>
268 * <TR><TD><B>Caret position:</B></TD><TD><B>Example:</B></TD>
269 * </TR><TR>
270 * <TD>{id: 8, index: 0}</TD>
271 * <TD>\f$ \mid \mbox{C} \cdot \mbox{C} \f$</TD>
272 * </TR><TR>
273 * <TD>{id: 10, index: 1}</TD>
274 * <TD>\f$ \mbox{C} \mid \cdot \mbox{C} \f$</TD>
275 * </TR><TR>
276 * <TD>{id: 11, index: 1}</TD>
277 * <TD>\f$ \mbox{C} \cdot \mid \mbox{C} \f$</TD>
278 * </TR><TR>
279 * <TD>{id: 12, index: 1}</TD>
280 * <TD>\f$ \mbox{C} \cdot \mbox{C} \mid \f$</TD>
281 * </TR><TR>
282 * </TABLE>
284 * Where \f$ \mid \f$ is used to denote caret position.
286 * With these exceptions included in the definition the id and index: {id: 11, index: 0} does
287 * \b not constitute a caret position in the given context. Note the method
288 * SmCaretPos::IsValid() does not check if this invariant holds true, but code in SmCaret,
289 * SmSetSelectionVisitor and other places depends on this invariant to hold.
292 * \subsection caret_movement Caret Movement
294 * As the placement of caret positions depends very much on the context within which a node
295 * appears it is not trivial to find all caret positions and determine which follows which.
296 * In OpenOffice Math this is done by the SmCaretPosGraphBuildingVisitor. This visitor builds
297 * graph (an instance of SmCaretPosGraph) over the caret positions. For details on how this
298 * graph is build, and how new methods should be implemented see SmCaretPosGraphBuildingVisitor.
300 * The result of the SmCaretPosGraphBuildingVisitor is a graph over the caret positions in a
301 * formula, represented by an instance of SmCaretPosGraph. Each entry (instances of SmCaretPosGraphEntry)
302 * has a pointer to the entry to the left and right of itself. This way we can easily find
303 * the caret position to a right or left of a given caret position. Note each caret position
304 * only appears once in this graph.
306 * When searching for a caret position after a left click on the formula this map is also used.
307 * We simply iterate over all entries, uses the SmCaretPos2LineVisitor to find a line for each
308 * caret position. Then the distance from the click to the line is computed and we choose the
309 * caret position closest to the click.
311 * For up and down movement, we also iterator over all caret positions and use SmCaretPos2LineVisitor
312 * to find a line for each caret position. Then we compute the distance from the current
313 * caret position to every other caret position and chooses the one closest that is either
314 * above or below the current caret position, depending on whether we're doing up or down movement.
316 * This result of this approach to caret movement is that we have logically predictable
317 * movement for left and right, whilst leftclick, up and down movement depends on the sizes
318 * and placement of all node and may be less logically predictable. This solution also means
319 * that we only have one complex visitor generating the graph, imagine the nightmare if we
320 * had a visitor for movement in each direction.
322 * Making up and down movement independent of node sizes and placement wouldn't necessarily
323 * be a good thing either. Consider the formula \f$ \frac{1+2+3+4+5}{6} \f$, if the caret is
324 * placed as displayed here: \f$ \frac{1+2+3+4+5}{6 \mid} \f$, up movement should move to right
325 * after "3": \f$ \frac{1+2+3|+4+5}{6} \f$. However, such a move depends on the sizes and placement
326 * of all nodes in the fraction.
329 * \subsubsection caretpos_graph_example Example of Caret Position Graph
331 * If we consider the formula
332 * \f$ \mbox{A} + \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$ from \ref formula_trees.
333 * It has the following caret positions:
335 * <TABLE>
336 * <TR>
337 * <TD><B>Caret position:</B></TD>
338 * <TD><B>Example:</B></TD>
339 * </TR><TR>
340 * <TD>{id: 3, index: 0}</TD>
341 * <TD>\f$ \mid\mbox{A} + \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$</TD>
342 * </TR><TR>
343 * <TD>{id: 5, index: 1}</TD>
344 * <TD>\f$ \mbox{A}\mid + \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$</TD>
345 * </TR><TR>
346 * <TD>{id: 6, index: 1}</TD>
347 * <TD>\f$ \mbox{A} + \mid \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$</TD>
348 * </TR><TR>
349 * <TD>{id: 8, index: 0}</TD>
350 * <TD>\f$ \mbox{A} + \frac{ \mid \mbox{B} \cdot \mbox{C}}{\mbox{D}} \f$</TD>
351 * </TR><TR>
352 * <TD>{id: 10, index: 1}</TD>
353 * <TD>\f$ \mbox{A} + \frac{\mbox{B} \mid \cdot \mbox{C}}{\mbox{D}} \f$</TD>
354 * </TR><TR>
355 * <TD>{id: 11, index: 1}</TD>
356 * <TD>\f$ \mbox{A} + \frac{\mbox{B} \cdot \mid \mbox{C}}{\mbox{D}} \f$</TD>
357 * </TR><TR>
358 * <TD>{id: 12, index: 1}</TD>
359 * <TD>\f$ \mbox{A} + \frac{\mbox{B} \cdot \mbox{C} \mid}{\mbox{D}} \f$</TD>
360 * </TR><TR>
361 * <TD>{id: 14, index: 0}</TD>
362 * <TD>\f$ \mbox{A} + \frac{\mbox{B} \cdot \mbox{C}}{\mid \mbox{D}} \f$</TD>
363 * </TR><TR>
364 * <TD>{id: 14, index: 1}</TD>
365 * <TD>\f$ \mbox{A} + \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D} \mid} \f$</TD>
366 * </TR><TR>
367 * <TD>{id: 7, index: 1}</TD>
368 * <TD>\f$ \mbox{A} + \frac{\mbox{B} \cdot \mbox{C}}{\mbox{D}} \mid \f$</TD>
369 * </TR>
370 * </TABLE>
372 * Below is a directed graph over the caret positions and how you can move between them.
373 * \dot
374 * digraph {
375 * labelloc = "t";
376 * label= "Caret Position Graph";
377 * size = "4,6";
378 * p0 [label = "{id: 3, index: 0}"];
379 * p0 -> p1 [fontsize = 10.0, label = "right"];
380 * p1 [label = "{id: 5, index: 1}"];
381 * p1 -> p0 [fontsize = 10.0, label = "left"];
382 * p1 -> p2 [fontsize = 10.0, label = "right"];
383 * p2 [label = "{id: 6, index: 1}"];
384 * p2 -> p1 [fontsize = 10.0, label = "left"];
385 * p2 -> p3 [fontsize = 10.0, label = "right"];
386 * p3 [label = "{id: 8, index: 0}"];
387 * p3 -> p2 [fontsize = 10.0, label = "left"];
388 * p3 -> p4 [fontsize = 10.0, label = "right"];
389 * p4 [label = "{id: 10, index: 1}"];
390 * p4 -> p3 [fontsize = 10.0, label = "left"];
391 * p4 -> p5 [fontsize = 10.0, label = "right"];
392 * p5 [label = "{id: 11, index: 1}"];
393 * p5 -> p4 [fontsize = 10.0, label = "left"];
394 * p5 -> p6 [fontsize = 10.0, label = "right"];
395 * p6 [label = "{id: 12, index: 1}"];
396 * p6 -> p5 [fontsize = 10.0, label = "left"];
397 * p6 -> p9 [fontsize = 10.0, label = "right"];
398 * p7 [label = "{id: 14, index: 0}"];
399 * p7 -> p2 [fontsize = 10.0, label = "left"];
400 * p7 -> p8 [fontsize = 10.0, label = "right"];
401 * p8 [label = "{id: 14, index: 1}"];
402 * p8 -> p7 [fontsize = 10.0, label = "left"];
403 * p8 -> p9 [fontsize = 10.0, label = "right"];
404 * p9 [label = "{id: 7, index: 1}"];
405 * p9 -> p6 [fontsize = 10.0, label = "left"];
407 * \enddot
410 /* TODO: Write documentation about the following keywords:
412 * Visual Selections:
413 * - Show images
414 * - Talk about how the visitor does this
416 * Modifying a Visual Line:
417 * - Find top most non-compo of the line (e.g. The subtree that constitutes a line)
418 * - Make the line into a list
419 * - Edit the list, add/remove/modify nodes
420 * - Parse the list back into a subtree
421 * - Insert the new subtree where the old was taken
424 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */