summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBryce Harrington <bryce@osg.samsung.com>2018-01-12 11:24:59 -0800
committerCedric BAIL <cedric@osg.samsung.com>2018-01-12 11:25:04 -0800
commitebdfc54defbb433056be2be42c73b56bf0d5e290 (patch)
treec4d13d8205db9a2f80fdf92e8b965b7d6901da5b
parent4916973a6084edc5e213dcfe1b1fa8697ff4138d (diff)
eina: document quadtree
Reviewers: cedric, ajwillia.ms Subscribers: segfaultxavi, jpeg Differential Revision: https://phab.enlightenment.org/D5522 Signed-off-by: Cedric BAIL <cedric@osg.samsung.com>
-rw-r--r--src/lib/eina/eina_quadtree.h172
1 files changed, 160 insertions, 12 deletions
diff --git a/src/lib/eina/eina_quadtree.h b/src/lib/eina/eina_quadtree.h
index 2638d8ba59..ad23bc3343 100644
--- a/src/lib/eina/eina_quadtree.h
+++ b/src/lib/eina/eina_quadtree.h
@@ -23,31 +23,179 @@
23 23
24#include "eina_inlist.h" 24#include "eina_inlist.h"
25 25
26typedef struct _Eina_QuadTree Eina_QuadTree; 26/**
27 * @addtogroup Eina_Data_Types_Group Data Types
28 *
29 * @{
30 */
31
32/**
33 * @typedef Eina_QuadTree
34 *
35 * A quadtree is a data structure where each node contains four child
36 * nodes. It can be used to partition 2D spaces through subdivision
37 * into quadrants.
38 */
39typedef struct _Eina_QuadTree Eina_QuadTree;
40
41/**
42 * @typedef Eina_QuadTree_Item
43 *
44 * A quadtree item is a holder for (void *) data items inside a
45 * quadtree, that includes some state tracking for lifecycle management
46 * and optimization purposes.
47 */
27typedef struct _Eina_QuadTree_Item Eina_QuadTree_Item; 48typedef struct _Eina_QuadTree_Item Eina_QuadTree_Item;
28 49
50/**
51 * @typedef Eina_Quad_Direction
52 */
29typedef enum { 53typedef enum {
30 EINA_QUAD_LEFT, 54 EINA_QUAD_LEFT,
31 EINA_QUAD_RIGHT, 55 EINA_QUAD_RIGHT,
32 EINA_QUAD_BOTH 56 EINA_QUAD_BOTH
33} Eina_Quad_Direction; 57} Eina_Quad_Direction;
34 58
59/**
60 * @typedef Eina_Quad_Callback
61 *
62 * Signature for a callback routine used to determine the location of an
63 * object within a quadtree. These are used in sorting by determining
64 * where in the tree the given data @p object belongs, using @p middle
65 * as the division line for the two halves of the space.
66 */
35typedef Eina_Quad_Direction (*Eina_Quad_Callback)(const void *object, size_t middle); 67typedef Eina_Quad_Direction (*Eina_Quad_Callback)(const void *object, size_t middle);
36 68
37EAPI Eina_QuadTree *eina_quadtree_new(size_t w, size_t h, Eina_Quad_Callback vertical, Eina_Quad_Callback horizontal); 69/**
38EAPI void eina_quadtree_free(Eina_QuadTree *q); 70 * @brief Constructs a quadtree object.
39EAPI void eina_quadtree_resize(Eina_QuadTree *q, size_t w, size_t h); 71 *
72 * @param[in] w The geometric width of the quadtree.
73 * @param[in] h The geometric height of the quadtree.
74 * @param[in] vertical The callback for vertical direction determination.
75 * @param[in] horizontal The callback for horizontal direction determination.
76 * @return The newly allocated and initialized quadtree, or @c NULL on error.
77 *
78 * The vertical and horizontal callbacks are used to assist in
79 * determining which quadrant a given data item belongs to.
80 */
81EAPI Eina_QuadTree *eina_quadtree_new(size_t w, size_t h, Eina_Quad_Callback vertical, Eina_Quad_Callback horizontal);
82
83/**
84 * @brief Destructs quadtree and its data.
85 *
86 * @param[in] q The quadtree to be freed.
87 *
88 * Frees the memory for the Eina_QuadTree object, and any memory used by
89 * its change tracking and garbage collection internals.
90 */
91EAPI void eina_quadtree_free(Eina_QuadTree *q);
40 92
41EAPI void eina_quadtree_cycle(Eina_QuadTree *q); 93/**
42EAPI void eina_quadtree_increase(Eina_QuadTree_Item *object); 94 * @brief Changes the width and height of the quadtree.
95 *
96 * @param[in,out] q The quadtree to resize.
97 * @param[in] w The new geometric width for the quadtree.
98 * @param[in] h The new geometric height for the quadtree.
99 *
100 * Sets the width and height of the quadtree, but the actual update is
101 * done lazily.
102 */
103EAPI void eina_quadtree_resize(Eina_QuadTree *q, size_t w, size_t h);
104
105/**
106 * @brief Sets the quadtree's index to 0.
107 *
108 * @param[in,out] q The quadtree to cycle.
109 */
110EAPI void eina_quadtree_cycle(Eina_QuadTree *q);
111
112/**
113 * @brief Increases the index of the quadtree item by one.
114 *
115 * @param[in,out] object The quadtree item to increase.
116 *
117 * If necessary, records that the root is no longer sorted.
118 */
119EAPI void eina_quadtree_increase(Eina_QuadTree_Item *object);
43 120
121/**
122 * @brief Inserts a data object into the quadtree.
123 *
124 * @param[in,out] q The quadtree to add @p object to.
125 * @param[in] object A data object to store in the quadtree.
126 * @return Pointer to the stored quadtree item.
127 *
128 * Creates an Eina_QuadTree_Item (or recycles one from the quadtree's
129 * trash) and stores the data @p object in it, then arranges to lazily
130 * insert the item into the quadtree (i.e. insertion is delayed until
131 * it needs to be used.)
132 */
44EAPI Eina_QuadTree_Item *eina_quadtree_add(Eina_QuadTree *q, const void *object); 133EAPI Eina_QuadTree_Item *eina_quadtree_add(Eina_QuadTree *q, const void *object);
45EAPI Eina_Bool eina_quadtree_del(Eina_QuadTree_Item *object);
46EAPI Eina_Bool eina_quadtree_change(Eina_QuadTree_Item *object);
47EAPI Eina_Bool eina_quadtree_hide(Eina_QuadTree_Item *object);
48EAPI Eina_Bool eina_quadtree_show(Eina_QuadTree_Item *object);
49 134
50EAPI Eina_Inlist *eina_quadtree_collide(Eina_QuadTree *q, int x, int y, int w, int h); 135/**
51EAPI void *eina_quadtree_object(Eina_Inlist *list); 136 * @brief Deletes a given quadtree item from the quadtree.
137 *
138 * @param[in] object The quadtree item to be deleted.
139 * @return #EINA_TRUE on success, #EINA_FALSE otherwise.
140 *
141 * Moves the item to the quadtree's internal garbage heap for later
142 * reclamation.
143 */
144EAPI Eina_Bool eina_quadtree_del(Eina_QuadTree_Item *object);
145
146/**
147 * @brief Marks an object within the quadtree as needing changed.
148 *
149 * @param[in,out] object The object that has changed.
150 * @return #EINA_TRUE if change successfully noted, or #EINA_FALSE otherwise.
151 */
152EAPI Eina_Bool eina_quadtree_change(Eina_QuadTree_Item *object);
153
154/**
155 * @brief Sets @p object invisible.
156 *
157 * @param[in,out] object The item within the quadtree to hide.
158 * @return #EINA_TRUE if @p object was successfully hidden, or
159 * #EINA_FALSE if it wasn't in the quadtree.
160 */
161EAPI Eina_Bool eina_quadtree_hide(Eina_QuadTree_Item *object);
162
163/**
164 * @brief Sets @p object to visible.
165 *
166 * @param[in,out] object The item within the quadtree to show.
167 * @return #EINA_TRUE if @p object was successfully shown, or
168 * #EINA_FALSE if it wasn't in the quadtree.
169 */
170EAPI Eina_Bool eina_quadtree_show(Eina_QuadTree_Item *object);
171
172/**
173 * @brief Retrieves items in quadtree inside the target geometry.
174 *
175 * @param[in,out] q The quadtree to recompute.
176 * @param[in] x New target X coordinate.
177 * @param[in] y New target Y coordinate.
178 * @param[in] w New target width.
179 * @param[in] h New target height.
180 * @return The list of collided items or @c NULL on error.
181 *
182 * Forces a rebuild and resort of the quadtree if needed due to pending
183 * changes, then performs a collision detection to find items whose
184 * geometry is contained within or intersects the given target geometry.
185 */
186EAPI Eina_Inlist *eina_quadtree_collide(Eina_QuadTree *q, int x, int y, int w, int h);
187
188/**
189 * @brief Retrieves the quadtree item's data for the given inline list.
190 *
191 * @param[in] list The inline list item to lookup
192 * @return The contained data object in the Eina_QuadTree_Item, or @c
193 * NULL if none could be found.
194 */
195EAPI void *eina_quadtree_object(Eina_Inlist *list);
196
197/**
198 * @}
199 */
52 200
53#endif 201#endif