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