Re: opinion poll on text widget iterators

[Karl Nelson <kenelson ece ucdavis edu>]

> 
> Karl Nelson <kenelson@ece.ucdavis.edu> writes: 
> > // checks to see if an iterator is the same
> > gint froo_tkxt_buffer_iter_comp(FrooTkxtIter*,FrooTkxtIter*)
> > 
> 
> Just as a random note, qsort()-style compare is going to be relatively
> expensive, but equality is super-cheap. (For equality, you just check
> whether it's the same line and same byte offset; for compare, if the
> lines are different you have to start futzing around in the btree to
> see which is first.)

Yes, that is what I meant by compare there.  Just checking to see
if two iterators came to the same point is fine.  

  gint froo_tkxt_buffer_iter_equal(FrooTkxtIter*,FrooTkxtIter*);

 
> > See best of both worlds and no need for messy ref/unref and
> > managing a dynamic buffer.  (Wow, that is actually cool, I
> > wonder if we can use this to make a generic g_container) 
> >
> 
> Nice, that is good to hear.
>  
> 
> >         FrooTkxt_Iter& operator =(const FrooTkxt_Iter& iter)
> >           { froo_tkxt_iter_copy(iter_,iter); }
> 
> Default operator= works fine, since you're guaranteed that there's no
> allocated memory in the iterator.

Okay, although I would rather you write an equals.  That way you can
scratch pad it.  

By the way there is a really cool way to keep caches so that 
you can avoid the O(n) problem.  You place an int in the
class and the iterator.  Every time a change is made to the 
class you increment the int.  The iterator keeps a copy of 
this int in itself so that if can match the item.  Then when you go 
to use the iterator you can check to see if the iterators cache
is up to date with the current widget.  If it is use it, otherwise
use the O(n) to get the data.  Since it is unlikely that you
are going to have too many iterators walking through the 
class changing things, this provides a very fast and robust
way of handling things.

 
> For the public FrooTkxtIter I would have just:
>  struct _FrooTkxtIter {
>   gpointer dummy1;
>   gpointer dummy2;
>   gpointer dummy3;
>  };
> 
> then cast that to my real object, of course.

Be sure to place the object pointer in there itself so that we
don't have to lug it around.  It is okay if it breaks if the
iterator is held through the deletion of the widget as iterators
should only be local in scope.  I like my iterators to be
useful outside of the most basic uses.


Also if you want to be really special you can place a class
pointer in the iterator.  The iterator could be made to 
then be abstract and skip items.  Thus you make an iterator
which jumps from picture to picture or char to char and 
all have the same size.

 
> > Why does it need to be O(n) the iter can have a pointer to a 
> > structure?  (Note, if it is O(n) don't provide it, O(n^2) 
> > use of this would just be too killer)
> > 
> 
> See mail to Guillaume; it's O(n) because it's semi-robust.
> You could add tags and marks while you are iterating, and you could
> insert text on lines that come before or after the iterator.

Does my time stamp solve that problem?  If CList/Ctree/List and
others had this mechanism then we could aggressively cache the
tail pointer, and I would stop my incessant whining about the
tail pointers.
 
> However the loop as a whole isn't _really_ O(n^2), because n is not
> the same in each case; the loop will be n steps, where n is the number
> of characters in the buffer (probably in the hundreds of thousands),
> the dereference will be n steps, where n is the number of segments in
> the line, typically 1 segment for text with no attributes, and no more
> than a dozen or so segments for a line in a typical font-locked Emacs
> buffer.

> > That shouldn't really be too big of deal.  You can make the
> > darn thing large with plenty of expansion area and then change
> > its size between major versions.
> > 
> 
> OK, I agree.
> 
> Oh, I haven't told you guys about another problem: some iterators
> point to embedded pixmaps or widgets instead of characters. Probably
> the incr/decrement functions would just skip the pixmaps and
> widgets. But then it might be nice to iterate over _everything_ in the
> buffer...

Actually we have been handling that better than gtk+ in most places.  
I just rewrote the CList wrapper so that it handles the 
4 data types in a unified manner.  Thus rather than having a 

  set_text()
  set_pixmap()
  set_pixtext()

I switched to
  clear()
  set_text() 
  set_pixmap()

And make it so that if you change the type it will just place change
the current type to one which has both.

Thus you can do things like set the text and then add a pixmap later,
then remove the text.  (GTK_CLIST_TEXT -> GTK_CLIST_PIXTEXT ->GTK_CLIST_PIXMAP)

I assume that yours is similar, and thus if done right we can deal
with any type on the list.   (Two weeks ago I would say skip, but
now we can handle it quite well.)

--Karl