Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From: Eric Sosman <esosman@comcast-dot-net.invalid>
Newsgroups: comp.lang.java.programmer
Subject: Re: SortedMap question?
Date: Mon, 26 Nov 2012 20:29:46 -0500
Organization: A noiseless patient Spider
Lines: 24
Message-ID: <k9152f$kl4$2@dont-email.me>
References: <k8rkud$i3o$1@dont-email.me> <q4qoyde15lpk$.13amx8nbfrj28.dlg@40tude.net> <k8t7l5$l22$2@dont-email.me> <k8t87f$rsq$2@dont-email.me> <50b2705c$0$295$14726298@news.sunsite.dk> <k8ujuj$mu4$2@dont-email.me> <yaTss.19810$W21.8324@newsfe27.iad>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 27 Nov 2012 01:29:51 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="ffb8f7085759b339c1002252b48331a4"; logging-data="21156"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX198NShC4lqFWLimGSKUS9Y6"
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:17.0) Gecko/17.0 Thunderbird/17.0
In-Reply-To: <yaTss.19810$W21.8324@newsfe27.iad>
Cancel-Lock: sha1:m2HnR2nMPEITIhW0IXL3Ryv2k10=
Xref: csiph.com comp.lang.java.programmer:19991

On 11/26/2012 6:45 PM, Daniel Pitts wrote:
> On 11/25/12 6:25 PM, David Lamb wrote:
>> On 25/11/2012 2:24 PM, Arne Vajhøj wrote:
>>> On 11/25/2012 8:59 AM, David Lamb wrote:
>>>> Which, sigh, of course they're not, as Arne pointed out. O(logN) for
>>>> SortedMap, as I should have immediately picked up on from the name
>>>> alone.
>>>
>>> SortedMap is still just an interface.
>>
>> Maybe so, but I suspect programmers would be unhappy if an
>> implementation didn't actually sort anything. I suppose there might be
>> special cases; sortedMap from small integers to anything could be O(1)
>> for get()
>>
> That special case happens to be called BitSet, which doesn't implement
> SortedMap :-)

     Another name for that special case is Value[] -- which
doesn't actually implement SortedMap, but does all that's needed.

-- 
Eric Sosman
esosman@comcast-dot-net.invalid