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.



git-svn-id: file:///fltk/svn/fltk/branches/branch-1.3@9231 ea41ed52-d2ee-0310-a9c1-e6b18d33e121

5 files changed, 140 insertions, 4 deletions

diff --git a/CHANGES b/CHANGES
index 1df13e805..b282478c1 100644
--- a/CHANGES
+++ b/CHANGES
@@ -1,3 +1,12 @@
+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
 
diff --git a/FL/Fl_Tree_Item.H b/FL/Fl_Tree_Item.H
index a3b4e2cda..d090df1b6 100644
--- a/FL/Fl_Tree_Item.H
+++ b/FL/Fl_Tree_Item.H
@@ -69,6 +69,10 @@ class FL_EXPORT Fl_Tree_Item {
   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 @@ public:
   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);
   
diff --git a/FL/Fl_Tree_Item_Array.H b/FL/Fl_Tree_Item_Array.H
index 8bdf21afc..18527a8ef 100644
--- a/FL/Fl_Tree_Item_Array.H
+++ b/FL/Fl_Tree_Item_Array.H
@@ -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 @@ public:
     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);
diff --git a/src/Fl_Tree_Item.cxx b/src/Fl_Tree_Item.cxx
index f37a20c55..1b28602c9 100644
--- a/src/Fl_Tree_Item.cxx
+++ b/src/Fl_Tree_Item.cxx
@@ -61,6 +61,10 @@ Fl_Tree_Item::Fl_Tree_Item(const Fl_Tree_Prefs &prefs) {
   _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 @@ Fl_Tree_Item::Fl_Tree_Item(const Fl_Tree_Item *o) {
   _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 @@ Fl_Tree_Item::Fl_Tree_Item(const Fl_Tree_Item *o) {
 ///
 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 @@ Fl_Tree_Item *Fl_Tree_Item::next() {
   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 @@ Fl_Tree_Item *Fl_Tree_Item::next() {
 /// \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 @@ Fl_Tree_Item *Fl_Tree_Item::prev() {
     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 @@ Fl_Tree_Item *Fl_Tree_Item::prev() {
 /// \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 @@ Fl_Tree_Item *Fl_Tree_Item::next_sibling() {
 /// \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
diff --git a/src/Fl_Tree_Item_Array.cxx b/src/Fl_Tree_Item_Array.cxx
index 358306a27..5518be46f 100644
--- a/src/Fl_Tree_Item_Array.cxx
+++ b/src/Fl_Tree_Item_Array.cxx
@@ -47,11 +47,13 @@ Fl_Tree_Item_Array::~Fl_Tree_Item_Array() {
 /// 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 @@ void Fl_Tree_Item_Array::insert(int pos, Fl_Tree_Item *new_item) {
   } 
   _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,12 +128,19 @@ void Fl_Tree_Item_Array::add(Fl_Tree_Item *val) {
 ///     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
   }
 }
 
@@ -148,6 +158,18 @@ int Fl_Tree_Item_Array::remove(Fl_Tree_Item *item) {
   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$".
 //