Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!news.swapon.de!feedme.ziplink.net!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!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:35:08 -0500 Date: Sat, 05 Nov 2011 14:35:07 -0700 From: Peter Duniho 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: In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Message-ID: Lines: 31 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 50.46.118.188 X-Trace: sv3-EEWNNzvrVDsz3wvDB0ySUn/OTFiUy82wOzOW1XCRkCP5c7FNeiID2xiqg04KZ3/4c5B2A2MpgOsT5xg!y8QpTcQxjOxZP16n61PE/xRpUVXTeO17xFUEAi8WUU41RXnGkgBmitFJDehdAjTKJfBxV0LoL5lU!NK6zz78r6t0trlEcH4ynvbVJrceeznPIZDO5vZsFjRI= 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: 2498 Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:9618 On 11/4/11 8:03 PM, Jan Burse wrote: > [...]I am looking for: > > Some stack class, where: (Easy) > pop() creates a new immutable stack > push() creates a new immutable stack > With good sharing. > > Some queue class, where: (Hard?) > enqueue() creates a new immutable queue > dequeue() creates a new immutable queue > With good sharing. You have already seen the article Eric Lippert wrote on an immutable stack. On the same blog are two different queue implementations. Here's the first: http://blogs.msdn.com/b/ericlippert/archive/2007/12/10/immutability-in-c-part-four-an-immutable-queue.aspx There are also implementations of a double-ended queue and a binary tree. As I suggested earlier, browse through the articles under the "Immutability" tag for those and other good info. All the code is C#, but other than the iterator methods it should be fairly trivial to port to Java (and I don't think iterator methods are a critical point of the data structure). 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