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