Author: greg.ercolano
Date: 2012-01-19 04:44:26 -0800 (Thu, 19 Jan 2012)
New Revision: 9231
Log:
Fl_Tree optimizations for selecting large trees (100k items).
Added _next_sibling and _prev_sibling to Fl_Tree_Item class to make
next_sibling() and prev_sibling() more efficient during item selection.
Used new FLTK_ABI_VERSION macro (as designed by Greg and Albrecht on fltk.dev)
to protect the ABI breaking features.
Modified:
branches/branch-1.3/CHANGES
branches/branch-1.3/FL/Fl_Tree_Item.H
branches/branch-1.3/FL/Fl_Tree_Item_Array.H
branches/branch-1.3/src/Fl_Tree_Item.cxx
branches/branch-1.3/src/Fl_Tree_Item_Array.cxx
Modified: branches/branch-1.3/CHANGES
===================================================================
--- branches/branch-1.3/CHANGES 2012-01-18 15:30:50 UTC (rev 9230)
+++ branches/branch-1.3/CHANGES 2012-01-19 12:44:26 UTC (rev 9231)
@@ -1,4 +1,13 @@
+CHANGES IN FLTK 1.3.2
+ 1.3.2 ABI FEATURES
+ (To enable the following ABI features, put: #define FLTK_ABI_VERSION
10302
+ at the top of your FL/Enumerations.H and rebuild FLTK and your app)
+
+ - Fl_Tree optimized to support large trees (eg. 100k items):
+ Added _next_sibling and _prev_sibling to Fl_Tree_Item class,
+ and support methods.
+
CHANGES IN FLTK 1.3.1
- Fixed Fl_Input_::maximum_size() documentation and replace() method
Modified: branches/branch-1.3/FL/Fl_Tree_Item.H
===================================================================
--- branches/branch-1.3/FL/Fl_Tree_Item.H 2012-01-18 15:30:50 UTC (rev
9230)
+++ branches/branch-1.3/FL/Fl_Tree_Item.H 2012-01-19 12:44:26 UTC (rev
9231)
@@ -69,6 +69,10 @@
Fl_Tree_Item_Array _children; // array of child items
Fl_Tree_Item *_parent; // parent item (=0 if root)
void *_userdata; // user data that can be
associated with an item
+#if FLTK_ABI_VERSION >= 10302
+ Fl_Tree_Item *_prev_sibling; // previous sibling (same level)
+ Fl_Tree_Item *_next_sibling; // next sibling (same level)
+#endif /*FLTK_ABI_VERSION*/
protected:
void show_widgets();
void hide_widgets();
@@ -178,6 +182,7 @@
Fl_Tree_Item *next();
Fl_Tree_Item *next_sibling();
Fl_Tree_Item *prev_sibling();
+ void update_prev_next(int index);
Fl_Tree_Item *next_displayed(Fl_Tree_Prefs &prefs);
Fl_Tree_Item *prev_displayed(Fl_Tree_Prefs &prefs);
Modified: branches/branch-1.3/FL/Fl_Tree_Item_Array.H
===================================================================
--- branches/branch-1.3/FL/Fl_Tree_Item_Array.H 2012-01-18 15:30:50 UTC (rev
9230)
+++ branches/branch-1.3/FL/Fl_Tree_Item_Array.H 2012-01-19 12:44:26 UTC (rev
9231)
@@ -5,6 +5,7 @@
#ifndef _FL_TREE_ITEM_ARRAY_H
#define _FL_TREE_ITEM_ARRAY_H
+#include <FL/Fl.H>
#include "Fl_Export.H"
class FL_EXPORT Fl_Tree_Item; // forward decl must *precede* first doxygen
comment block
@@ -66,11 +67,17 @@
return(_total);
}
/// Swap the two items at index positions \p ax and \p bx.
+#if FLTK_ABI_VERSION >= 10302
+ // NEW -- code moved to .cxx
+ void swap(int ax, int bx);
+#else /*FLTK_ABI_VERSION*/
+ // OLD
void swap(int ax, int bx) {
Fl_Tree_Item *asave = _items[ax];
_items[ax] = _items[bx];
_items[bx] = asave;
}
+#endif /*FLTK_ABI_VERSION*/
void clear();
void add(Fl_Tree_Item *val);
void insert(int pos, Fl_Tree_Item *new_item);
Modified: branches/branch-1.3/src/Fl_Tree_Item.cxx
===================================================================
--- branches/branch-1.3/src/Fl_Tree_Item.cxx 2012-01-18 15:30:50 UTC (rev
9230)
+++ branches/branch-1.3/src/Fl_Tree_Item.cxx 2012-01-19 12:44:26 UTC (rev
9231)
@@ -61,6 +61,10 @@
_usericon = 0;
_userdata = 0;
_parent = 0;
+#if FLTK_ABI_VERSION >= 10302
+ _prev_sibling = 0;
+ _next_sibling = 0;
+#endif /*FLTK_ABI_VERSION*/
}
// DTOR
@@ -101,6 +105,10 @@
_usericon = o->usericon();
_userdata = o->user_data();
_parent = o->_parent;
+#if FLTK_ABI_VERSION >= 10302
+ _prev_sibling = 0; // do not copy ptrs! use
update_prev_next()
+ _next_sibling = 0; // do not copy ptrs! use
update_prev_next()
+#endif /*FLTK_ABI_VERSION*/
}
/// Print the tree as 'ascii art' to stdout.
@@ -108,8 +116,14 @@
///
void Fl_Tree_Item::show_self(const char *indent) const {
if ( label() ) {
+#if FLTK_ABI_VERSION >= 10302
+ printf("%s-%s (%d children, this=%p, parent=%p, prev=%p, next=%p,
depth=%d)\n",
+ indent,label(),children(),(void*)this, (void*)_parent,
+ _prev_sibling, _next_sibling, depth());
+#else /*FLTK_ABI_VERSION*/
printf("%s-%s (%d children, this=%p, parent=%p depth=%d)\n",
indent,label(),children(),(void*)this, (void*)_parent, depth());
+#endif /*FLTK_ABI_VERSION*/
}
if ( children() ) {
char *i2 = (char*)malloc(strlen(indent) + 2);
@@ -793,12 +807,22 @@
if ( c->has_children() ) {
return(c->child(0));
}
+#if FLTK_ABI_VERSION >= 10302
+ // NEW
while ( ( p = c->parent() ) != NULL ) { // loop upwards through parents
+ if ( c->_next_sibling ) // not last child?
+ return(c->_next_sibling); // return next child
+ c = p; // child becomes parent to move
up generation
+ } // loop: moves up to next parent
+#else /*FLTK_ABI_VERSION*/
+ // OLD
+ while ( ( p = c->parent() ) != NULL ) { // loop upwards through parents
int t = p->find_child(c); // find our position in
parent's children[] array
if ( ++t < p->children() ) // not last child?
return(p->child(t)); // return next child
c = p; // child becomes parent to move
up generation
} // loop: moves up to next parent
+#endif /*FLTK_ABI_VERSION*/
return(0); // hit root? done
}
@@ -810,6 +834,37 @@
/// \returns the previous item in the tree, or 0 if there's no item above this
one (hit the root).
///
Fl_Tree_Item *Fl_Tree_Item::prev() {
+#if FLTK_ABI_VERSION >= 10302
+ // NEW
+ if ( !parent() ) return(0); // hit root? done
+ if ( !_prev_sibling ) { // are we first child?
+ return(parent()); // return parent
+ }
+ // Tricky: in the following example our current position
+ // in the tree is 'j', and we need to move "up one" to 'i':
+ //
+ // ROOT
+ // |-- a
+ // b-- c
+ // | d-- e
+ // | | f
+ // | |
+ // | g-- h
+ // | i
+ // j
+ //
+ // We do this via b->g->i:
+ // 1. Find j's prev_sibling (b) _
+ // 2. Find b's 'last child' (g) |_ while loop
+ // 3. Find g's 'last child' (i) _|
+ //
+ Fl_Tree_Item *p = _prev_sibling; // focus on our prev sibling
+ while ( p->has_children() ) { // item has children?
+ p = p->child(p->children()-1); // descend hierarchy finding deepest
'last child'
+ }
+ return(p);
+#else /*FLTK_ABI_VERSION*/
+ // OLD
Fl_Tree_Item *p=parent(); // start with parent
if ( ! p ) return(0); // hit root? done
int t = p->find_child(this); // find our position in parent's
children[] array
@@ -821,6 +876,7 @@
p = p->child(p->children()-1); // take last child
}
return(p);
+#endif /*FLTK_ABI_VERSION*/
}
/// Return this item's next sibling.
@@ -832,12 +888,18 @@
/// \returns item's next sibling, or 0 if none.
///
Fl_Tree_Item *Fl_Tree_Item::next_sibling() {
+#if FLTK_ABI_VERSION >= 10302
+ // NEW
+ return(_next_sibling);
+#else /*FLTK_ABI_VERSION*/
+ // OLD
if ( !parent() ) return(0); // No parent (root)? We have no
siblings
int index = parent()->find_child(this); // find our position in
parent's child() array
if ( index == -1 ) return(0); // parent doesn't know
us? weird
if ( (index+1) < parent()->children() ) // is there a next child?
return(parent()->child(index+1)); // return next child if there's
one below us
return(0); // no siblings below us
+#endif /*FLTK_ABI_VERSION*/
}
/// Return this item's previous sibling.
@@ -848,13 +910,44 @@
/// \returns This item's previous sibling, or 0 if none.
///
Fl_Tree_Item *Fl_Tree_Item::prev_sibling() {
+#if FLTK_ABI_VERSION >= 10302
+ // NEW
+ return(_prev_sibling);
+#else /*FLTK_ABI_VERSION*/
+ // OLD
if ( !parent() ) return(0); // No parent (root)? We
have no siblings
int index = parent()->find_child(this); // find next position
up in parent's child() array
if ( index == -1 ) return(0); // parent
doesn't know us? weird
if ( index > 0 ) return(parent()->child(index-1)); // return previous
child if there's one above us
return(0); // no siblings above us
+#endif /*FLTK_ABI_VERSION*/
}
+/// Update our _prev_sibling and _next_sibling pointers to point to neighbors,
+/// given \p index as being our current position in the parent's item array.
+/// Call this whenever items in the array are added/removed/moved/swapped.
+///
+void Fl_Tree_Item::update_prev_next(int index) {
+#if FLTK_ABI_VERSION >= 10302
+ // NEW
+ int pchildren = parent() ? parent()->children() : 0;
+ int index_prev = index-1;
+ int index_next = index+1;
+ // Get pointers to prev+next items
+ Fl_Tree_Item *item_prev = (index_prev>=0)&&(index_prev<pchildren) ?
parent()->child(index_prev) : 0;
+ Fl_Tree_Item *item_next = (index_next>=0)&&(index_next<pchildren) ?
parent()->child(index_next) : 0;
+ // Adjust our prev+next ptrs
+ _prev_sibling = item_prev;
+ _next_sibling = item_next;
+ // Adjust neighbors to point to us
+ if ( item_prev ) item_prev->_next_sibling = this;
+ if ( item_next ) item_next->_prev_sibling = this;
+#else /*FLTK_ABI_VERSION*/
+ // OLD
+ // -- does nothing --
+#endif /*FLTK_ABI_VERSION*/
+}
+
/// Return the next visible item. (If this item has children and is closed,
children are skipped)
///
/// This method can be used to walk the tree forward, skipping items
Modified: branches/branch-1.3/src/Fl_Tree_Item_Array.cxx
===================================================================
--- branches/branch-1.3/src/Fl_Tree_Item_Array.cxx 2012-01-18 15:30:50 UTC
(rev 9230)
+++ branches/branch-1.3/src/Fl_Tree_Item_Array.cxx 2012-01-19 12:44:26 UTC
(rev 9231)
@@ -47,11 +47,13 @@
/// Copy constructor. Makes new copy of array, with new instances of each item.
Fl_Tree_Item_Array::Fl_Tree_Item_Array(const Fl_Tree_Item_Array* o) {
_items = (Fl_Tree_Item**)malloc(o->_size * sizeof(Fl_Tree_Item*));
- _total = o->_total;
+ _total = 0;
_size = o->_size;
_chunksize = o->_chunksize;
for ( int t=0; t<o->_total; t++ ) {
_items[t] = new Fl_Tree_Item(o->_items[t]);
+ ++_total;
+ _items[t]->update_prev_next(t); // update uses _total's current
value
}
}
@@ -108,6 +110,7 @@
}
_items[pos] = new_item;
_total++;
+ _items[pos]->update_prev_next(pos); // adjust item's prev/next and its
neighbors
}
/// Add an item* to the end of the array.
@@ -125,13 +128,20 @@
/// The item will be delete'd (if non-NULL), so its destructor will be
called.
///
void Fl_Tree_Item_Array::remove(int index) {
- if ( _items[index] ) { // delete if non-zero
+ if ( _items[index] ) { // delete if non-zero
delete _items[index];
}
_items[index] = 0;
- for ( _total--; index<_total; index++ ) {
- _items[index] = _items[index+1];
+ _total--;
+ for ( int i=index; i<_total; i++ ) { // reshuffle the array
+ _items[i] = _items[i+1];
}
+ if ( index < _total ) { // removed item not last?
+ _items[index]->update_prev_next(index); // update next item's prev/next
and neighbors
+ } else if ( ((index-1) >= 0) && // removed item IS last?
+ ((index-1) < _total)) {
+ _items[index-1]->update_prev_next(index-1); // update prev item's
prev/next and neighbors
+ }
}
/// Remove the item from the array.
@@ -148,6 +158,18 @@
return(-1);
}
+#if FLTK_ABI_VERSION >= 10302
+/// Swap the two items at index positions \p ax and \p bx.
+void Fl_Tree_Item_Array::swap(int ax, int bx) {
+ Fl_Tree_Item *asave = _items[ax];
+ _items[ax] = _items[bx];
+ _items[bx] = asave;
+ // Adjust prev/next ptrs
+ _items[ax]->update_prev_next(ax);
+ _items[bx]->update_prev_next(bx);
+}
+#endif /* FLTK_ABI_VERSION */
+
//
// End of "$Id$".
//
_______________________________________________
fltk-commit mailing list
[email protected]
http://lists.easysw.com/mailman/listinfo/fltk-commit
