|
This page contains an archived post to the Java Answers Forum made prior to February 25, 2002.
If you wish to participate in discussions, please visit the new
Artima Forums.
Message:
Re: Another LinkedList problem...
Posted by Brian Sanders on November 08, 2001 at 12:43 PM
There you go... I have 2 lists, one has the time and the other the events. I created a copy of both, as I had to sort the first one by ascendent order, using my LongComparator class, that converts to Long before using the Collections.sort. Two problems strike me right off the bat with your implementation: the first is that you're using Collections.binarySearch() on an unsorted list. According to the javadoc, the behavior when used on an unsorted list is undefined (in this case, returns odd values). The second problem I see is that your times list contains duplicates. This sequence of events causes problems:
The "times" list is cloned and sorted to make the "sortedTimes" list
For each entry in the "sortedTimes" list, a search is performed to find it's original index in the "times" list.
Thus, an ambiguity arises: in your sample data, does the time "15000" correspond to the event "WindowMalfunction" or "Bell"? This is a fundamental weakness in this data structure; unless you can guarantee no duplicates, you have no way of absolutely identifying which index is next. I've included my solution below; it handles duplicate times and does not use Collections.binarySearch()
import java.util.*;public class List
{
//using actual Long values (rather than Strings) for simplicity
public static Object[][] DATA = {
{ "FirstItem", new Long(50) },
{ "SecondItem", new Long(10) },
{ "ThirdItem", new Long(80) },
{ "FourthItem", new Long(0) },
{ "FifthItem", new Long(10) }
}; /**
* Sorts the two lists. Preserves the relative order of two events happening at the same time.
*/
public static void main(String[] args)
{
//initializing the two linked list off of the data in the constant array
LinkedList names = new LinkedList();
LinkedList times = new LinkedList(); for (int i=0; i < DATA.length; i++)
{
names.add(DATA[i][0]);
times.add(DATA[i][1]);
} //clone the array, and sort
LinkedList sortedTimes = (LinkedList) times.clone();
Collections.sort(sortedTimes); //for each time in the sorted times list, find it's index in the unsorted times list.
//this can be used to find the corresponding element in the names list.
LinkedList sortedNames = new LinkedList(); //As we find an index for each time, replace it with a token object to indicate that it's already been used;
//this will allow for duplicate times. We clone the list b/c we assume preserving the original list is
//important.
Object BLANK = new Object();
LinkedList unsortedTimes = (LinkedList) times.clone();
for (Iterator i = sortedTimes.listIterator(); i.hasNext(); )
{
Long time = (Long) i.next();
int index = 0;
while (unsortedTimes.get(index) != time || unsortedTimes.get(index) == BLANK)
index++;
unsortedTimes.set(index, BLANK);
sortedNames.add(names.get(index));
} //showing our results:
for (int i=0; i < sortedNames.size(); i++)
{
System.out.println(sortedNames.get(i) + ":" + sortedTimes.get(i));
}
}
}
Replies:
|
