CODEWITHSUNDEEP
javadictionarydata-structures
Nick Heiner
Nick Heiner

Reputation: 122450

Java: Data structure for sorting objects/maintaining a key in that order?

I want to maintain a collection of objects of type Odp. Odp implements Comparable. I need to be able to refer to an object in the collection with its integer name. This integer must correspond to its sort order (not insertion order). Each integer only applies to one Odp, and vice versa.

I have a function compareOdp(Odp o1, Odp o2) that returns a numeric value representing the similarity of the two arguments. I the Odp collection to be set up in such a way that it's easy to ask questions like "What is the closest Odp to foo in the collection?" or "Of these several collections of Odp objects, how close are they to each other?"

What is the best way to do this? TreeMap? HashBiMap?

Related Question:

Let's say I have the following set of objects: o1, o2, o3 contained in collection col. Their sort order is 

o2
o3
o1

I want to ask col: "what is the nth object in the list?" From what I can see, SortedSet and TreeMap don't have a way to do this. I guess I could iterate over, but it feels like there should be an easier way.

Upvotes: 0

Views: 914

Answers (5)

Nicholas Jordan
Nicholas Jordan

Reputation: 656

// What is the nth object in the list...

Object oneObject = TreeMap.get(nthKey);

Okay, so far / so good. If you do not care how they are contained in the Data Structure, you can use a ( might have to look it up but it would be called a ) HashMap == in which case there would be a key that you supply, which can easily be:

Object placement= HashMap.put(new Integer(++index),new Object(data));// see docs for exact

if placement is null, the map did not contain the object previously, used in conjuction with containsKey() exact management of data set is obtainable

Which will work find for get and put by ordered key, it's only that if you do toArray() you get a bizarre ordering that is only comprehensible to whomever wrote the HashMap implementation.

Upvotes: 0

erickson
erickson

Reputation: 269667

If you are using Java 6, the NavigableSet API (implemented by TreeSet) can help.

public static Odp nearest(Odp o, NavigableSet<? extends Odp> set) {
  Odp f = set.floor(o), c = set.ceiling(o);
  if (f == null)
    return c;
  if (c == null)
    return f;
  int df = compareOdp(o, f), dc = compareOdp(c, o);
  return (df <= dc) ? f : c;
}

Upvotes: 3

brianegge
brianegge

Reputation: 29872

I would use the lowly LinkedList. Then use Collections.binarySearch for searching the list. The binary search function will return you the insertion point in your linked list. To find which one is closest, simply use your compareOdp function with the item below and the item above in the linkedlist.

Upvotes: 0

NawaMan
NawaMan

Reputation: 25687

TreeMap is a build-in solution and as far as I've used it. I think it is pretty good.

Upvotes: 1

Dave DiFranco
Dave DiFranco

Reputation: 1735

Any implementation of SortedSet will keep the items in order, according to the Comparable interface. TreeSet is an implementation of SortedSet.

Upvotes: 1

Related Questions