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
|
/*
* tkQTree.h --
*
* Declarations for the Q-Tree implementation.
*
* Copyright (c) 2015-2017 Gregor Cramer
*
* See the file "license.terms" for information on usage and redistribution of
* this file, and for a DISCLAIMER OF ALL WARRANTIES.
*/
#ifndef _TKQTREE
#define _TKQTREE
#ifndef _TKINT
#include "tkInt.h"
#endif
#include "tkBool.h"
#include "mystdint.h"
#ifdef _MSC_VER
# if _MSC_VER >= 1900
# define inline __inline
# else
# define inline
# endif
#elif __STDC_VERSION__ < 199901L
# define inline /* we are not C99 conform */
#endif
/* =========================================================================
* Definitions for rectangle support.
* ========================================================================= */
typedef int32_t TkQTreeCoord;
typedef struct TkQTreeRect {
TkQTreeCoord xmin, ymin, xmax, ymax;
} TkQTreeRect;
/* Return whether rectangle is empty? */
inline bool TkQTreeRectIsEmpty(const TkQTreeRect *rect);
/* Return whether both rectangles are equal. */
inline bool TkQTreeRectIsEqual(const TkQTreeRect *rect1, const TkQTreeRect *rect2);
/* Return whether this rectangle contains the specified point. */
inline bool TkQTreeRectContainsPoint(const TkQTreeRect *rect, TkQTreeCoord x, TkQTreeCoord y);
/* Return whether the first rectangle contains the second one. */
inline bool TkQTreeRectContainsRect(const TkQTreeRect *rect1, const TkQTreeRect *rect2);
/* Return whether both rectangles are overlapping. */
inline bool TkQTreeRectIntersects(const TkQTreeRect *rect1, const TkQTreeRect *rect2);
/* Setup a rectangle. */
inline TkQTreeRect *TkQTreeRectSet(TkQTreeRect *rect,
TkQTreeCoord xmin, TkQTreeCoord ymin, TkQTreeCoord xmax, TkQTreeCoord ymax);
/* Translate a rectangle. */
inline TkQTreeRect *TkQTreeRectTranslate(TkQTreeRect *rect, TkQTreeCoord dx, TkQTreeCoord dy);
/* =========================================================================
* Definitions for the Q-Tree (Quartering Tree).
* ========================================================================= */
typedef int32_t TkQTreeState;
typedef uintptr_t TkQTreeUid;
typedef void *TkQTreeClientData;
struct TkQTree;
typedef struct TkQTree *TkQTree;
/*
* This is defining the callback function for searching and traversing the tree.
* Note that argument 'rect' will contain the coordinates according to the current
* scroll position. When returning false the search will be terminated, otherwise
* the search continues.
*/
typedef bool (*TkQTreeCallback)(
TkQTreeUid uid, const TkQTreeRect *rect, TkQTreeState *state, TkQTreeClientData arg);
/*
* Configure the dimensions of the given Q-Tree. A new tree will be created if
* given tree (derefernced treePtr) is NULL. This function returns false if the
* specified bounding box is empty, in this case the tree cannot be used.
*/
bool TkQTreeConfigure(TkQTree *treePtr, const TkQTreeRect *rect);
/*
* Destroy the given tree. Will do nothing if given tree (derefernced treePtr)
* is NULL.
*/
void TkQTreeDestroy(TkQTree *treePtr);
/*
* Return the bounding box of given tree.
*/
const TkQTreeRect *TkQTreeGetBoundingBox(const TkQTree tree);
/*
* Insert a rectangle into the tree. Each rectangle must be associated with an
* unique ID (argument 'uid'). This function returns whether the insertion was
* successful. The insertion fails if the given rectangle is empty, or if it
* does not overlap with the bounding box of the tree, in these case the
* return value will be false.
*/
bool TkQTreeInsertRect(TkQTree tree, const TkQTreeRect *rect, TkQTreeUid uid, TkQTreeState initialState);
/*
* Update the rectangle which belongs to the given unique ID. The argument
* 'oldRect' must exactly match the last provided rectangle (with
* TkQTreeInsertRect, or TkQTreeUpdateRect). For convenience it is allowed
* to insert a new rectangle (this means new unique ID), in this case
* argument 'oldRect' must be NULL. This function returns whether the
* insertion/update was successful. The insertion/update fails if the new
* rectangle is empty, or if it does not overlap with the bounding box of
* the tree, in these cases the return value will be false.
*/
bool TkQTreeUpdateRect(TkQTree tree, const TkQTreeRect *oldRect,
const TkQTreeRect *newRect, TkQTreeUid uid, TkQTreeState newState);
/*
* Delete the specified rectangle from the tree. It is mandatory that the specified
* rectangle is exactly matching the last provided rectangle for given uid (with
* TkQTreeInsertRect, or TkQTreeUpdateRect). This function returns whether the
* deletion was successful.
*/
bool TkQTreeDeleteRect(TkQTree tree, const TkQTreeRect *rect, TkQTreeUid uid);
/*
* Search for all rectangles containing the given point. For each hit the given
* function will be triggered. This function returns the number of hits. It is
* allowed to use NULL for argument 'cbHit'.
*/
unsigned TkQTreeSearch(const TkQTree tree, TkQTreeCoord x, TkQTreeCoord y,
TkQTreeCallback cbHit, TkQTreeClientData cbArg);
/*
* Trigger the given callback function for any rectangle in this tree.
*/
void TkQTreeTraverse(const TkQTree tree, TkQTreeCallback cbHit, TkQTreeClientData cbArg);
/*
* Find the current state of the specified rectangle. This functions returns true
* if and only if the specified rectangle has been found. It is allowed to use
* NULL for argument 'state', in this case only the existence of the specified
* rectangle will be tested.
*/
bool TkQTreeFindState(const TkQTree tree, const TkQTreeRect *rect, TkQTreeUid uid, TkQTreeState *state);
/*
* Set the current state of the specified rectangle. This functions returns true
* if successful, otherwise, if the specified rectangle is not exisiting, false
* will be returned.
*/
bool TkQTreeSetState(const TkQTree tree, const TkQTreeRect *rect, TkQTreeUid uid, TkQTreeState state);
#if QTREE_SEARCH_RECTS_CONTAINING
/*
* Search for all rectangles which are containing the given rectangle. Note that
* here the user will receive NULL for parameter 'state' in callback function,
* this means that this parameter cannot be used with the use of this function.
* This function returns the number of hits. It is allowed to use NULL for
* argument 'cbHit'.
*/
unsigned TkQTreeSearchRectsContaining(const TkQTree tree, const TkQTreeRect *rect,
TkQTreeCallback cbHit, TkQTreeClientData cbArg);
#endif /* QTREE_SEARCH_RECTS_CONTAINING */
#if __STDC_VERSION__ >= 199901L || (defined(_MSC_VER) && _MSC_VER >= 1900)
# define _TK_NEED_IMPLEMENTATION
#include "tkQTreePriv.h"
# undef _TK_NEED_IMPLEMENTATION
#else
# undef inline
#endif
#endif /* _TKQTREE */
/* vi:set ts=8 sw=4: */
|
