On Wednesday 19th April 2006 21::55 Greg Fitzgerald wrote:
Brian,
> implementing the text buffer for an edit control
Just a few weeks ago I was thinking about a functional way to implement an edit control. I ended up with the code below. The function 'text' takes a stream of user input and returns the text to be displayed.
Rather than using a mutable buffer, I chose to implement this using a stream of user input and two stacks where each stack contains the characters on opposite sides of the cursor. I'm certainly no expert, but I believe all operations are constant time, except that returning the final string at the end of the input stream is O(n). Of course, if you have a huge amount of text to display and need to display it after each key is pressed, then this is pretty worthless. [snip]
Thanks! I see you are representing the text buffer from the point of view of the cursor therefore all edit ops are constant time or O(k) where k is the numbers of chars involved in the change (eg for cut and paste). Some ops such as clicking the mouse on a different part of the text after scrolling up/down would be O(n) in the difference between the old and new cursor position, but since most editing is presumably sequential, perhaps the amortized cost would still be constant.
I think this would also work even for very large texts, because many things can probably be done without having the create the whole string each time, but I'll have to try it out to see how it works in practice.
In any case it is a very useful pattern to make use of the locality of editing to get such a direct and efficient purely functional representation. Before I was just looking at the data structure from a "bird's eye" view, but I see the key to functional efficiency here is to represent it from a place where everything non-local is not changing ie from the point of change itself...
Thanks for this pattern, Brian. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
