summaryrefslogtreecommitdiff
path: root/starmath/inc/caret.hxx
blob: 327ee1d6ed162f1a4ea2e94a3465ff3c91d60131 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/*
 * This file is part of the LibreOffice project.
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */
#ifndef INCLUDED_STARMATH_INC_CARET_HXX
#define INCLUDED_STARMATH_INC_CARET_HXX

#include <sal/config.h>

#include "node.hxx"

#include <cassert>
#include <memory>
#include <vector>

/** Representation of caret position with an equation */
struct SmCaretPos{
    SmCaretPos(SmNode* selectedNode = nullptr, int iIndex = 0)
        : pSelectedNode(selectedNode)
        , nIndex(iIndex)
    {
        assert(nIndex >= 0);
    }

    /** Selected node */
    SmNode* pSelectedNode;

    /** Index (invariant: non-negative) within the selected node
     *
     * 0: Position in front 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 unpleasant.
    int nIndex;

    /** True, if this is a valid caret position */
    bool IsValid() const { return pSelectedNode != nullptr; }
    bool operator==(const SmCaretPos &pos) const {
        return pos.pSelectedNode == pSelectedNode && nIndex == pos.nIndex;
    }
    /** 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() == SmNodeType::Text)
            return SmCaretPos(pNode, static_cast<SmTextNode*>(pNode)->GetText().getLength());
        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(const SmCaretLine& line) const{
        return (GetLeft() - line.GetLeft()) * (GetLeft() - line.GetLeft());
    }
    long SquaredDistanceX(const Point &pos) const{
        return (GetLeft() - pos.X()) * (GetLeft() - pos.X());
    }
    long SquaredDistanceY(const 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(const 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,
                         SmCaretPosGraphEntry* left,
                         SmCaretPosGraphEntry* right) {
        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;
    }
};

/** A graph over all caret positions
 * @remarks Graphs can only grow, entries cannot be removed!
 */
class SmCaretPosGraph{
public:
    SmCaretPosGraph();

    ~SmCaretPosGraph();

    /** Add a caret position
     *  @remarks If left is NULL, they will point back to the entry.
     */
    SmCaretPosGraphEntry* Add(SmCaretPos pos,
                            SmCaretPosGraphEntry* left = nullptr);

    std::vector<std::unique_ptr<SmCaretPosGraphEntry>>::iterator begin()
    {
        return mvEntries.begin();
    }

    std::vector<std::unique_ptr<SmCaretPosGraphEntry>>::iterator end()
    {
        return mvEntries.end();
    }

private:
    std::vector<std::unique_ptr<SmCaretPosGraphEntry>> mvEntries;
};

/** \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: &#183; (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 represented 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 in front 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
 * in front 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: &#183; (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 instance 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, represented 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 whether 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 positions 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 // INCLUDED_STARMATH_INC_CARET_HXX

/* vim:set shiftwidth=4 softtabstop=4 expandtab: */