Justin Bailey wrote:
The other day I decided to implement a ring buffer with a current
element (i.e. a doubly-linked zipper list). In order to allow inserts
(and, in the future, deletes and updates), I have a special sentinel
element called "Join" in the structure. When inserting, I find the
join first, insert and then rebuild the buffer using circular
programming techniques. This also allows the buffer to be converted
back to a list. The current element can be changed by rotating right
or left, which never fails. Rotating n positions takes n steps.
I'm posting it here for comments and feedback. How could the structure
be smarter? Would storing a unique ID with each element make more
sense? Any comments on the space behavior under insert and rotates? I
wanted to "maximize" sharing. Thanks in advance.
Do you really need to realize the cycle by sharing? I mean, sharing
doesn't go well with insertion / updates / deletion since each of these
operations breaks it and needs to restore it everywhere. In other words,
your insert takes O(n) time. I'd simply drop the sharing and use two
double ended queues (or something like that) instead
data Ring a = Ring (DeQueue a) a (DeQueue a)
-- pseudo-code missing lots of cases. I want views!
left (Ring (l' :< ls :> l) x (r :< rs :> r')) =
Ring (ls :> l :> x) r (rs :> r' :> l')
This way, you can implement update operations in O(1) time instead of
O(n). With a fancy random access queue like Data.Sequence , you can even
have rotations like rotL xs n in O(log n) time.
(I keep mixing up the meaning of rotL and rotR , does L push the
current element to the left or does it rotate the ring clockwise?)
Regards,
apfelmus
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
