1 //
2 // "$Id$"
3 //
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 #include <FL/Fl_Tree_Item_Array.H>
10 #include <FL/Fl_Tree_Item.H>
11
12 //////////////////////
13 // Fl_Tree_Item_Array.cxx
14 //////////////////////
15 //
16 // Fl_Tree -- This file is part of the Fl_Tree widget for FLTK
17 // Copyright (C) 2009-2010 by Greg Ercolano.
18 //
19 // This library is free software. Distribution and use rights are outlined in
20 // the file "COPYING" which should have been included with this file. If this
21 // file is missing or damaged, see the license at:
22 //
23 // http://www.fltk.org/COPYING.php
24 //
25 // Please report all bugs and problems on the following page:
26 //
27 // http://www.fltk.org/str.php
28 //
29
30 /// Constructor; creates an empty array.
31 ///
32 /// The optional 'chunksize' can be specified to optimize
33 /// memory allocation for potentially large arrays. Default chunksize is 10.
34 ///
Fl_Tree_Item_Array(int new_chunksize)35 Fl_Tree_Item_Array::Fl_Tree_Item_Array(int new_chunksize) {
36 _items = 0;
37 _total = 0;
38 _size = 0;
39 #if FLTK_ABI_VERSION >= 10303
40 _flags = 0;
41 #endif
42 _chunksize = new_chunksize;
43 }
44
45 /// Destructor. Calls each item's destructor, destroys internal _items array.
~Fl_Tree_Item_Array()46 Fl_Tree_Item_Array::~Fl_Tree_Item_Array() {
47 clear();
48 }
49
50 /// Copy constructor. Makes new copy of array, with new instances of each item.
Fl_Tree_Item_Array(const Fl_Tree_Item_Array * o)51 Fl_Tree_Item_Array::Fl_Tree_Item_Array(const Fl_Tree_Item_Array* o) {
52 _items = (Fl_Tree_Item**)malloc(o->_size * sizeof(Fl_Tree_Item*));
53 _total = 0;
54 _size = o->_size;
55 _chunksize = o->_chunksize;
56 #if FLTK_ABI_VERSION >= 10303
57 _flags = o->_flags;
58 #endif
59 for ( int t=0; t<o->_total; t++ ) {
60 #if FLTK_ABI_VERSION >= 10303
61 if ( _flags & MANAGE_ITEM ) {
62 _items[t] = new Fl_Tree_Item(o->_items[t]); // make new copy of item
63 ++_total;
64 _items[t]->update_prev_next(t); // update uses _total's current value
65 } else {
66 _items[t] = o->_items[t]; // copy ptr only
67 ++_total;
68 }
69 #else
70 _items[t] = new Fl_Tree_Item(o->_items[t]); // make new copy of item
71 ++_total;
72 _items[t]->update_prev_next(t); // update uses _total's current value
73 #endif
74 }
75 }
76
77 /// Clear the entire array.
78 ///
79 /// Each item will be deleted (destructors will be called),
80 /// and the array will be cleared. total() will return 0.
81 ///
clear()82 void Fl_Tree_Item_Array::clear() {
83 if ( _items ) {
84 for ( int t=0; t<_total; t++ ) {
85 #if FLTK_ABI_VERSION >= 10303
86 if ( _flags & MANAGE_ITEM )
87 #endif
88 {
89 delete _items[t];
90 _items[t] = 0;
91 }
92 }
93 free((void*)_items); _items = 0;
94 }
95 _total = _size = 0;
96 }
97
98 // Internal: Enlarge the items array.
99 //
100 // Adjusts size/items memory allocation as needed.
101 // Does NOT change total.
102 //
enlarge(int count)103 void Fl_Tree_Item_Array::enlarge(int count) {
104 int newtotal = _total + count; // new total
105 if ( newtotal >= _size ) { // more than we have allocated?
106 if ( (newtotal/150) > _chunksize ) _chunksize *= 10;
107 // Increase size of array
108 int newsize = _size + _chunksize;
109 Fl_Tree_Item **newitems = (Fl_Tree_Item**)malloc(newsize * sizeof(Fl_Tree_Item*));
110 if ( _items ) {
111 // Copy old array -> new, delete old
112 memmove(newitems, _items, _size * sizeof(Fl_Tree_Item*));
113 free((void*)_items); _items = 0;
114 }
115 // Adjust items/sizeitems
116 _items = newitems;
117 _size = newsize;
118 }
119 }
120
121 /// Insert an item at index position \p pos.
122 ///
123 /// Handles enlarging array if needed, total increased by 1.
124 /// If \p pos \>= total(), the item is appended to the array.
125 /// If \p pos \< 0, the item is prepended (works like pos == 0).
126 ///
insert(int pos,Fl_Tree_Item * new_item)127 void Fl_Tree_Item_Array::insert(int pos, Fl_Tree_Item *new_item) {
128 if (pos < 0)
129 pos = 0;
130 else if (pos > _total)
131 pos = _total;
132 enlarge(1);
133 // printf("*** POS=%d TOTAL-1=%d NITEMS=%d\n", pos, _total-1, (_total-pos));
134 if ( pos <= (_total - 1) ) { // need to move memory around?
135 int nitems = _total - pos;
136 memmove(&_items[pos+1], &_items[pos], sizeof(Fl_Tree_Item*) * nitems);
137 }
138 _items[pos] = new_item;
139 _total++;
140 #if FLTK_ABI_VERSION >= 10303
141 if ( _flags & MANAGE_ITEM )
142 #endif
143 {
144 _items[pos]->update_prev_next(pos); // adjust item's prev/next and its neighbors
145 }
146 }
147
148 /// Add an item* to the end of the array.
149 ///
150 /// Assumes the item was created with 'new', and will remain
151 /// allocated.. Fl_Tree_Item_Array will handle calling the
152 /// item's destructor when the array is cleared or the item remove()'ed.
153 ///
add(Fl_Tree_Item * val)154 void Fl_Tree_Item_Array::add(Fl_Tree_Item *val) {
155 insert(_total, val);
156 }
157
158 /// Replace the item at \p index with \p newitem.
159 ///
160 /// Old item at index position will be destroyed,
161 /// and the new item will take it's place, and stitched into the linked list.
162 ///
replace(int index,Fl_Tree_Item * newitem)163 void Fl_Tree_Item_Array::replace(int index, Fl_Tree_Item *newitem) {
164 if ( _items[index] ) { // delete if non-zero
165 #if FLTK_ABI_VERSION >= 10303
166 if ( _flags & MANAGE_ITEM )
167 #endif
168 // Destroy old item
169 delete _items[index];
170 }
171 _items[index] = newitem; // install new item
172 #if FLTK_ABI_VERSION >= 10303
173 if ( _flags & MANAGE_ITEM )
174 #endif
175 {
176 // Restitch into linked list
177 _items[index]->update_prev_next(index);
178 }
179 }
180
181 /// Remove the item at \param[in] index from the array.
182 ///
183 /// The item will be delete'd (if non-NULL), so its destructor will be called.
184 ///
remove(int index)185 void Fl_Tree_Item_Array::remove(int index) {
186 if ( _items[index] ) { // delete if non-zero
187 #if FLTK_ABI_VERSION >= 10303
188 if ( _flags & MANAGE_ITEM )
189 #endif
190 delete _items[index];
191 }
192 _items[index] = 0;
193 _total--;
194 for ( int i=index; i<_total; i++ ) { // reshuffle the array
195 _items[i] = _items[i+1];
196 }
197 #if FLTK_ABI_VERSION >= 10303
198 if ( _flags & MANAGE_ITEM )
199 #endif
200 {
201 if ( index < _total ) { // removed item not last?
202 _items[index]->update_prev_next(index); // update next item's prev/next and neighbors
203 } else if ( ((index-1) >= 0) && // removed item IS last?
204 ((index-1) < _total)) {
205 _items[index-1]->update_prev_next(index-1);// update prev item's prev/next and neighbors
206 }
207 }
208 }
209
210 /// Remove the item from the array.
211 ///
212 /// \returns 0 if removed, or -1 if the item was not in the array.
213 ///
remove(Fl_Tree_Item * item)214 int Fl_Tree_Item_Array::remove(Fl_Tree_Item *item) {
215 for ( int t=0; t<_total; t++ ) {
216 if ( item == _items[t] ) {
217 remove(t);
218 return(0);
219 }
220 }
221 return(-1);
222 }
223
224 #if FLTK_ABI_VERSION >= 10301
225 /// Swap the two items at index positions \p ax and \p bx.
swap(int ax,int bx)226 void Fl_Tree_Item_Array::swap(int ax, int bx) {
227 Fl_Tree_Item *asave = _items[ax];
228 _items[ax] = _items[bx];
229 _items[bx] = asave;
230 #if FLTK_ABI_VERSION >= 10303
231 if ( _flags & MANAGE_ITEM )
232 #endif
233 {
234 // Adjust prev/next ptrs
235 _items[ax]->update_prev_next(ax);
236 _items[bx]->update_prev_next(bx);
237 }
238 }
239 #endif /* FLTK_ABI_VERSION */
240
241 /// Move item at 'from' to new position 'to' in the array.
242 /// Due to how the moving an item shuffles the array around,
243 /// a positional 'move' implies things that may not be obvious:
244 /// - When 'from' moved lower in tree, appears BELOW item that was at 'to'.
245 /// - When 'from' moved higher in tree, appears ABOVE item that was at 'to'.
246 ///
247 /// \returns 0 on success, -1 on range error (e.g. if \p 'to' or \p 'from' out of range)
248 ///
move(int to,int from)249 int Fl_Tree_Item_Array::move(int to, int from) {
250 if ( from == to ) return 0; // nop
251 if ( to<0 || to>=_total || from<0 || from>=_total ) return -1;
252 Fl_Tree_Item *item = _items[from];
253 // Remove item..
254 if ( from < to )
255 for ( int t=from; t<to && t<(_total+1); t++ )
256 _items[t] = _items[t+1];
257 else
258 for ( int t=from; t>to && t>0; t-- )
259 _items[t] = _items[t-1];
260 // Move to new position
261 _items[to] = item;
262 // Update all children
263 for ( int r=0; r<_total; r++ ) // XXX: excessive to do all children,
264 _items[r]->update_prev_next(r); // XXX: but avoids weird boundary issues
265 return 0;
266 }
267
268 /// Deparent item at \p 'pos' from our list of children.
269 /// Similar to a remove() without the destruction of the item.
270 /// This creates an orphaned item (still allocated, has no parent)
271 /// which soon after is typically reparented elsewhere.
272 ///
273 /// \returns 0 on success, -1 on error (e.g. if \p 'pos' out of range)
274 ///
deparent(int pos)275 int Fl_Tree_Item_Array::deparent(int pos) {
276 if ( pos>=_total || pos<0 ) return -1;
277 // Save item being deparented, and its two nearest siblings
278 Fl_Tree_Item *item = _items[pos];
279 Fl_Tree_Item *prev = item->prev_sibling();
280 Fl_Tree_Item *next = item->next_sibling();
281 // Remove from parent's list of children
282 _total -= 1;
283 for ( int t=pos; t<_total; t++ )
284 _items[t] = _items[t+1]; // delete, no destroy
285 // Now an orphan: remove association with old parent and siblings
286 item->update_prev_next(-1); // become an orphan
287 // Adjust bereaved siblings
288 if ( prev ) prev->update_prev_next(pos-1);
289 if ( next ) next->update_prev_next(pos);
290 return 0;
291 }
292
293 /// Reparent specified item as a child of ourself.
294 /// Typically 'newchild' was recently orphaned with deparent().
295 ///
296 /// \returns 0 on success, -1 on error (e.g. if \p 'pos' out of range)
297 ///
reparent(Fl_Tree_Item * item,Fl_Tree_Item * newparent,int pos)298 int Fl_Tree_Item_Array::reparent(Fl_Tree_Item *item, Fl_Tree_Item* newparent, int pos) {
299 if ( pos<0 || pos>_total ) return -1;
300 // Add item to new parent
301 enlarge(1);
302 _total += 1;
303 for ( int t=_total-1; t>pos; --t ) // shuffle array to make room for new entry
304 _items[t] = _items[t-1];
305 _items[pos] = item; // insert new entry
306 // Attach to new parent and siblings
307 _items[pos]->parent(newparent); // reparent (update_prev_next() needs this)
308 _items[pos]->update_prev_next(pos); // find new siblings
309 return 0;
310 }
311
312 //
313 // End of "$Id$".
314 //
315