Re: Ordered Sets

From:

"Mike Schilling" <mscottschilling@hotmail.com>

Newsgroups:

comp.lang.java.programmer

Date:

Wed, 19 Dec 2007 17:34:22 -0800

Message-ID:

<yEjaj.340$El5.249@newssvr22.news.prodigy.net>

"Patricia Shanahan" <pats@acm.org> wrote in message
news:fkcbcf$1jsp$1@ihnp4.ucsd.edu...

Stefan Ram wrote:

Patricia Shanahan <pats@acm.org> writes:

That approach was one of my first suggestions,

Sorry, I must have missed that.

but the OP wants to be able to insert items at arbitrary
positions, not according to Comparable order, or even a
Comparator.

  Actually, it could be done.

  For example, the ordered set might have been: |1, 2|

  Now, to insert ?4? into the middle, i.e., to get |1, 4, 2|,

      - add ?4? to the set

      - make sure that the ordering relation will evaluate as
follows
          (1,4)=1
          (1,2)=1
          (4,2)=1
          (x,y)=-(y,x)
          (x,x)=0

        This includes, possibly changing the Comparator at
run-time.

  It might not be a good for anything, so it might be idle
  to write about this, but it is not impossible either.

I did think of an evil variant using a TreeMap<BigDecimal,Whatever>.
An
insert into an empty structure uses key 0. An insert at the start of
a
non-empty uses key one less than the current lowest key. Similarly,
insert at the end by using key one greater than the current highest
key.
To insert between two items, use the mean of their keys.

That doesn't help with duplicate detection, though. You'll still need
a Map or Set with the Whatevers as keys. My best first try uses a
LinkedList and a HashSet, the LL for iteration in both directions and
the HS for duplicate direction. The iterate() method returns
something like a ListIterator but whose add() method returns a
boolean. The requirments aren't complete enough to refine this.