Le 04/01/2012 21:44, Greg Ercolano a écrit :
Ya, looks like it's spending a lot of time calling find_child().
Apparently I never bothered to implement pointers to keep track
of 'next' and 'last' to speed up walking the tree.
Will follow up with a fix for that too..
Here a simple patch (I miss the Tree Item array swap for updating
_next_sibling and maybe somewhere else but the test case works)
I have not done the prev_sibling optimization.
May be, the other David can test it if it helps.
Index: FL/Fl_Tree_Item.H
===================================================================
--- FL/Fl_Tree_Item.H (revision 9217)
+++ FL/Fl_Tree_Item.H (working copy)
@@ -69,6 +69,7 @@
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
+ Fl_Tree_Item* _nextSibling;
protected:
void show_widgets();
void hide_widgets();
@@ -177,6 +178,7 @@
Fl_Tree_Item *prev();
Fl_Tree_Item *next();
Fl_Tree_Item *next_sibling();
+ void next_sibling(Fl_Tree_Item *i);
Fl_Tree_Item *prev_sibling();
Fl_Tree_Item *next_displayed(Fl_Tree_Prefs &prefs);
Fl_Tree_Item *prev_displayed(Fl_Tree_Prefs &prefs);
Index: src/Fl_Tree_Item.cxx
===================================================================
--- src/Fl_Tree_Item.cxx (revision 9217)
+++ src/Fl_Tree_Item.cxx (working copy)
@@ -61,6 +61,7 @@
_usericon = 0;
_userdata = 0;
_parent = 0;
+ _nextSibling = 0;
}
// DTOR
@@ -101,6 +102,7 @@
_usericon = o->usericon();
_userdata = o->user_data();
_parent = o->_parent;
+ _nextSibling = o->_nextSibling;
}
/// Print the tree as 'ascii art' to stdout.
@@ -794,9 +796,8 @@
return(c->child(0));
}
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
+ if ( c->_nextSibling ) // not last child?
+ return c->_nextSibling; // return next child
c = p; // child becomes parent to move
up generation
} // loop: moves up to next parent
return(0); // hit root? done
@@ -832,14 +833,14 @@
/// \returns item's next sibling, or 0 if none.
///
Fl_Tree_Item *Fl_Tree_Item::next_sibling() {
- 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
+ return _nextSibling;
}
+// Sets the next sibling
+void Fl_Tree_Item::next_sibling(Fl_Tree_Item *i) {
+ this->_nextSibling = i;
+}
+
/// Return this item's previous sibling.
///
/// Moves to the previous item above us at the same level (sibling).
Index: src/Fl_Tree_Item_Array.cxx
===================================================================
--- src/Fl_Tree_Item_Array.cxx (revision 9217)
+++ src/Fl_Tree_Item_Array.cxx (working copy)
@@ -52,7 +52,11 @@
_chunksize = o->_chunksize;
for ( int t=0; t<o->_total; t++ ) {
_items[t] = new Fl_Tree_Item(o->_items[t]);
+ _items[t]->next_sibling( 0 );
}
+ for ( int t=0; t<o->_total-1; t++ ) {
+ _items[t]->next_sibling( _items[t+1] );
+ }
}
/// Clear the entire array.
@@ -107,6 +111,7 @@
memmove(&_items[pos+1], &_items[pos], sizeof(Fl_Tree_Item*) * nitems);
}
_items[pos] = new_item;
+ if (pos) _items[pos-1]->next_sibling(_items[pos]);
_total++;
}
@@ -132,6 +137,7 @@
for ( _total--; index<_total; index++ ) {
_items[index] = _items[index+1];
}
+ if (index) _items[index-1]->next_sibling(_items[index]);
}
/// Remove the item from the array.
_______________________________________________
fltk mailing list
fltk@easysw.com
http://lists.easysw.com/mailman/listinfo/fltk
