**Posted By:**
Robert_Smith

**Posted On:**
Thursday, August 26, 2004 12:05 PM

Heres the basis of the problem: You have one structure (figuring out what kind of structure is part of the problem) that contains a set of objects, lets call it ALL. You have another that contains a subset of these objects which well call SOME. You want to sort ALL on some criteria, then go through the elements of SOME, and look at the elements just before and after this element in ALL. Whats important is that Im sorting the big list, and examining previous and next items from that list, but only for elements in the little list. The way I first implemented it is as follows: Both ALL and SOME are ArrayLists. I sort ALL (which is an O(N log(N) operation), then to an index=ALL.indexOf(SOME(j)), and

More>>
Heres the basis of the problem:

You have one structure (figuring out what kind of structure is part of the problem) that contains a set of objects, lets call it ALL. You have another that contains a subset of these objects which well call SOME.

You want to sort ALL on some criteria, then go through the elements of SOME, and look at the elements just before and after this element in ALL.

Whats important is that Im sorting the big list, and examining previous and next items from that list, but only for elements in the little list.

The way I first implemented it is as follows:

Both ALL and SOME are ArrayLists. I sort ALL (which is an O(N log(N) operation), then to an index=ALL.indexOf(SOME(j)), and look at ALL(index-1) and ALL(index+1).

The problem with this is that indexOf in an ArrayList is an order N operation, which I may have to do O(N) times. This is clearly slower than it should be.

A better approach is:

Make a TreeSet called ALLTREE. ALLTREE.add(ALL) automatically sorts ALLTREE, in O(N log(N)) time. Then, I look at the appropriate elements of headSet=ALLTREE.headSet(SOME(j)) and tailSet=ALLTREE tailSet(SOME(j)).

Getting these sets is an O(log(N)) operation, that I have to do O(N) times, getting me back to O(N log(N)).

However, I know it should be faster than that, yet I cant figure how one can do it under Javas classes (without writing several new classes, and perhaps a sort routine).

This is how Id think about doing it from scratch in C:

Imagine ALL as a doubly linked list of elements, with each element containing a pointer to the previous and next elements in the list. Imagine that SOME contains references (pointers) to some of the elements in this list (which implicitly contain their next and previous references). Sort ALL (thus changing the next and previous pointers appropriately). You should be able to do this in O(N log(N)) time.

Then finding the next and previous elements (relative to ALL) for the elements of SOME should be an O(1) operation! I mean, youve got the pointer, just go look at the values pointed to by previous and next!

But, because things class in Collections hide the linked list functionality details, I cant do this (or at least I cant see how to).

All possibilities appreciated.

R.

<<Less