Sentinels in collections, was RE: Primitive Queue<any T> considerations

[Rezaei, Mohammad A.]

Many primitive collections use sentinels *without* requiring removal of those in the collection. This is done by storing a bit of side information. For example, for a set of int, GS Collections uses 0 and 1 as sentinels (meaning empty and removed, respectively). Every call to methods like get/contains/add/etc first checks to see if the value is a sentinel, and if so, queries/updates the side data. For a set, the side data is tiny and trivial: there is a single byte that encode if the set contains 0, 1, both or none.

Thanks
Moh

>-----Original Message-----
>From: valhalla-dev [mailto:valhalla-dev-bounces at openjdk.java.net] On Behalf Of
>Vitaly Davidovich
>Sent: Wednesday, November 18, 2015 2:31 PM
>To: Richard Warburton
>Cc: valhalla-dev at openjdk.java.net
>Subject: Re: Primitive Queue<any T> considerations
>
>Although I agree that sometimes a sentinel or even an entire range of
>values is available to indicate absence, I don't think it's the right
>answer to the question.  In particular, if you're writing a general purpose
>collection, you cannot expect your users to remove one possible value from
>their universe to signal absence.  The collections that do this today are
>simply working around lack of nullable primitives.
>
>On Wed, Nov 18, 2015 at 2:18 PM, Richard Warburton <
>richard.warburton at gmail.com> wrote:
>
>> Hi,
>>
>> I'm not sure about the default null-indicator because every time a queue is
>> > needed in our library, that can serve a source with unique choice of a
>> > default-null value. It is unlikely the users of the library want or can
>> > specify that all the time.
>> >
>>
>> I appreciate that this is diverging directly form your language related
>> question, but it is pertinent to writing anyfied collections using
>> Valhalla. My experience using primitive specialised collections is that it
>> has always been possible to have a sentinel value, though obviously my
>> experience won't necessary reflect that of every single person in the Java
>> community. It isn't always appropriate for it to be 0, which is what I
>> think T.default is currently going to return for primitives and when I've
>> done primitive specialised collections before they allow you to specify the
>> missing value sentinel.
>>
>> Have you got of an actual genuine use case where a sentinel value doesn't
>> work well, rather than a theoretical "hey, maybe you want to have a set
>> that contains every possible int?"
>>
>> regards,
>>
>>   Richard Warburton
>>
>>   http://insightfullogic.com
>>   @RichardWarburto <http://twitter.com/richardwarburto>
>>