This week's book giveaway is in the Mac OS forum. We're giving away four copies of a choice of "Take Control of Upgrading to Yosemite" or "Take Control of Automating Your Mac" and have Joe Kissell on-line! See this thread for details.

I need to have a data structure storing integers which can be added or removed in n*log n time. A TreeSet would be just fine for this purpose, but most of the time I do not know the exact element I wan to find. I just know that I need either the number 5, or if 5 is not present, then I need the closest number which is greater then 5 (6,7, whatever, depending on the contents of the data structure). This is not a major difference if I would write the tree structure myself, but can I somehow avoid doing that? Is there a possiblity to use TreeSet in this way, or maybe some other class?

<pre> public Object getBestMatch(SortedSet set, Object item) { if (set.contains(item)) return item; Set tail = set.tailSet(); if (tail.isEmpty()) return null; return tail.first(); } </pre>

"I'm not back." - Bill Harding, Twister

Joco Kedves
Greenhorn

Joined: Oct 11, 2001
Posts: 7

posted

0

Dear Jim! First of all, thanks for your reply. But assuming that you meant to type this code: public Object getBestMatch(SortedSet set, Object item){ if (set.contains(item)) return item; SortedSet tail = set.tailSet(item); if (tail.isEmpty()) return null; return tail.first(); } How do we know the cost of getting the "tailset" of our set. Can you explain why do you think that it is log n (where n means the number of elements stored in the sorted set)?

Originally posted by Joco Kedves: How do we know the cost of getting the "tailset" of our set. Can you explain why do you think that it is log n (where n means the number of elements stored in the sorted set)?

There are two steps to the algorithm given.

Create the tailSet. This is an O(1) operation, as the tailSet is no more than a view on the underlying Set (simply examine the source code of TreeMap, which backs the set, if you want to confirm this).

Find the first entry in the tailSet. This is done using tree traversal which takes O(log(n)) (examine TreeMap.getCeilEntry()).

- Peter

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

> assuming that you meant to type this code... Oops. Yes, I meant SortedSet rather than Set. Thanks Peter for the followup.

This is a smart student to ask his homework assignment question with his/her own thinking, and got his answer back. In contrast of some students just throwing his/her teacher's assignment here, I actually have no objections on this one. JavaChina has been moved to http://javachina.developergroup.org/

Joco Kedves
Greenhorn

Joined: Oct 11, 2001
Posts: 7

posted

0

Thanks everybody for the answers. To Peter: I certainly will need to look at the source code of TreeMap, because I need to confirm this thing. To Rosanne: No, Rosanne, this is not a student assignment. I am a mathematician, who is trying to write a little program as a demonstration of an algorithm which he invented with some collegues. He decided to write the code in JAVA and got a JAVA 1.1 book from the library, although he never wrote anything in that language before. To tell the truth, since he left the university (which was quite a few years ago) he never wrote anything in any language. So he did his little program, but then did not want to write a search tree "by hand", but did not know how to figure out what this TreeSet class does. So he posed a question here. (Maybe it should have been put in the "beginner" section?) Thanks again anyway.

Joco Kedves
Greenhorn

Joined: Oct 11, 2001
Posts: 7

posted

0

One more thing to Rosanne: My question was not about finding the colsest match in a TreeSet, but more like "is it possible to find the closest match using TreeSet and its methods in log n time, and if so, how." Since still I do not understand what "no more than a view on the underlying set" (as Peter put it) means, I am still not convinced, but I see that people here believe that tailSet() is an O(1) operation, which is very promising. I am very happy with it as an answer, now all I have to do is look at the souce to make suru. All the best.

Roseanne Zhang
Ranch Hand

Joined: Nov 14, 2000
Posts: 1953

posted

0

Sorry for misconception. It did look like a student hw assignment to me since I was/still is a teacher to certain extent. As to big O, Peter's answer is correct if you look into the source code. For TreeSet

A little surprising on 2) and 3) if you do not look at the code. Roseanne

Peter den Haan
author
Ranch Hand

Joined: Apr 20, 2000
Posts: 3252

posted

0

Small clarification: tailSet(), headSet() and subSet() return very small objects that delegate all the hard work to methods of the underlying set. No new set is constructed. Hence O(1) and pretty insignificant. - Peter

Joco Kedves
Greenhorn

Joined: Oct 11, 2001
Posts: 7

posted

0

Originally posted by Roseanne Zhang:

A little surprising on 2) and 3) if you do not look at the code. Roseanne [/B]

Yes, 2) seems surprising.

Joco Kedves
Greenhorn

Joined: Oct 11, 2001
Posts: 7

posted

0

I have come back here just to tell you what I have learned from the source of TreeMap and TreeSet (which is probably wasting our resources, but I want you to know that your answers really helped). I found out that a "tailset" is basically only a value where the tailset is "started", so creating a tailset is really an O(1) operation. Then getting the first element of the tailset is just looking for the element which is equal to this starting value of the tailset, or if no such element exists, then looking for the least element which is greater than the starting value. And exactly this is done (of course in log n time) by a method of TreeMap called getCeilEntry(...). Thanks again for your answers.