Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.posted.palinacquisition!news.posted.palinacquisition.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 05 Nov 2011 16:52:00 -0500
Date: Sat, 05 Nov 2011 14:51:59 -0700
From: Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.5; rv:7.0.1) Gecko/20110929 Thunderbird/7.0.1
MIME-Version: 1.0
Newsgroups: comp.lang.java.programmer
Subject: Re: Immutable Datastructures with good Sharing
References: <j9292v$f69$1@news.albasani.net> <jamdnUwVbvmRMSjTnZ2dnUVZ_uKdnZ2d@posted.palinacquisition> <j94ajg$ost$1@news.albasani.net>
In-Reply-To: <j94ajg$ost$1@news.albasani.net>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <IuednQhC8Y-dLSjTnZ2dnUVZ_gmdnZ2d@posted.palinacquisition>
Lines: 29
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 50.46.118.188
X-Trace: sv3-2w42oGQt3C6SyIvRwVMfL3kEODTgTy91DyEq8ot7HddvNIQ/og/on06MZCpq8250LWZK9WuESaD9WVH!u+pO1kyHJdSj60OQ+sfYq+3Rh64i/wAWWqNFJd9lFgLlo6gtSpNZ9LWuC2s86zAKqK2t1/i+7GX9!dWalIWZNJ20WXwHRMlE0D1k/+5U9+tDuuZ+uUj5ie/8=
X-Complaints-To: abuse@iinet.com
X-DMCA-Complaints-To: abuse@iinet.com
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2398
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:9621

On 11/5/11 2:42 PM, Jan Burse wrote:
> Peter Duniho schrieb:
>> Once you have seen those examples, hopefully that will help you see some
>> of the basic techniques used that can lead you to implementations of
>> other complex immutable data structures you might want.
>>
>> Pete
>
> It fullfils the requirement of immutable. But it has no sharing.
>
> public IQueue<T> Enqueue(T t) {
> return new Queue<T>(backwards.Push(t)); }
> public IQueue<T> Dequeue(T t) {
> return new Queue<T>(backwards.Reverse().Pop().Reverse()); }
>
> Eric himself remarks when initially defining Reverse:
>
> This is an O(n) operation for a stack of size n.
>
> So I guess we did not yet find a solution.

Yes, I agree…if you are looking for someone who has already done your 
work for you, then the link I offered doesn't specifically answer your 
question.

But maybe you can learn something from it anyway.  You may even find 
that it's not practical to expect an immutable queue to have "good sharing".

Pete