On Tue, Aug 30, 2011 at 12:23, Stephen Bloch <sbl...@adelphi.edu> wrote:
> > On Aug 30, 2011, at 3:18 AM, Laurent wrote: > > Thank you very much for this nice intermediate solution, though I need > constant-time append, split, insert, remove, + pointers to items, etc. > Mutation does seem unavoidable, right. > > > The "zipper" structure Neil posted has constant-time append if you're > already at the head of one zipper and the tail of the other, but in general > it'll be linear time. It has constant-time split, insert, and remove. > Not if you are not already at the right place in the lists. Finding the place of the element in the list would take linear time. > What do you mean by "pointers to items" -- that is, what do you need to > DO with pointers to items? > Items are struct instances. By pointers I meant references, as they are handled automatically in Racket. The list of items gives me a modifiable preference order on the items (the preference criterion may vary). Each hash entry holds a "reference" to an item, and an item holds a reference to the previous and next elements in the list. For example, given a key in the hash I get the reference to the item, and I can then put that element at the end of the list, or exchange it with the next element, or remove it, etc. This does not seem possible with the same time complexity with zippers. Laurent
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
