Link to home
Start Free TrialLog in
Avatar of entercite
entercite

asked on

How to sort a vector of objects.

Hello experts,

 I am not sure how best to sort a vector of objects I made. The objects in the vector is something I made called a LogError with these properties:

String date
String time
String exception
String className
String methodName
String errorMessage
int lineNumber
int numberOfTimes

Say the vector contains 150 to 1000 LogErrors. The value I want to sort by is the numberOfTimes value from high number to low.

I was messing around with an insertion sort which i think might be best for this situation but I dont really know how to apply it to my vector.

I thought about using an int array to hold an index of the items in my Vector then call my sort algorithm (sort it) and then come back to my vector and try to sort it using the sorted int array holding the new positions.

Here is what I have so far. Is this a good idea or is there something better. Code examples would be great. Thanks!!!!!

int[] sortItem = new int[totalsVector.size()]; //Index array to used to sort the vector.
HashMap totals  = new HashMap();  // thought about using this to hold the index as well.
            
for(int i=0; i<totalsVector.size(); i++)
{
      LogError log = (LogError)totalsVector.get(i);  // Main vector of items to sort //
      int num = log.getNumberOfTimes();
      totals.put(new Integer(i), new Integer(num));
      sortItem[i] = num; // load this with number of times value?
}
            
try{
      insertionSort(sortItem, totalsVector.size() );
      for(int i= 0; i< sortItem.length; i++){
            System.out.println("item= "+ sortItem[i]);
      }
}catch(Exception e){
      e.printStackTrace();
}

public static void insertionSort(int numbers[], int array_size)
{
      int i, j, index;
      for (i=1; i < array_size; i++)
      {
            index = numbers[i];
            j = i;
            while ((j > 0) && (numbers[j-1] > index))
            {
                  numbers[j] = numbers[j-1];
                  j = j - 1;
            }
            numbers[j] = index;
      }
}
Avatar of imladris
imladris
Flag of Canada image

It would be much simpler and more reasonable to operate on the Vector itself. The insertionSort method could get the Vector passed in and would then look something like:

public static void insertionSort(Vector tv)
{
     int i, j, index;

     int array_size=tv.size();
     for (i=1; i < array_size; i++)
     {
          index = ((LogError)tv.get(i)).getNumberOfTimes();
           j = i;
          while((j>0) && ((LogError)tv.get(j-1)).getNumberOfTimes()>index)
         {
               tv.set(j,tv.get(j-1));
               j = j - 1;
          }
          tv.set(j,tv.get(i));
     }
}
Sorry, looks like you would have to save the original object too:

public static void insertionSort(Vector tv)
{
     int i, j, index;
     LogError tmp;

     int array_size=tv.size();
     for (i=1; i < array_size; i++)
     {
          tmp=(LogError)tv.get(i);
          index=tmp.getNumberOfTimes();
           j = i;
          while((j>0) && ((LogError)tv.get(j-1)).getNumberOfTimes()>index)
         {
               tv.set(j,tv.get(j-1));
               j = j - 1;
          }
          tv.set(j,tmp);
     }
}
Avatar of CEHJ
You just need a Comparator

Collection.sort(yourVector, new LogComparator());


................................



      class LogComparator implements java.util.Comparator {
            public int compare(Object o1, Object o2) {
                  LogError le1 = LogError(o1);
                  LogError le2 = LogError(o2);
                  return le2.getNumberOfTimes() - le1.getNumberOfTimes();
            }
      }
Typo

>>Collection.sort(yourVector, new LogComparator());

should be

Collections.sort(yourVector, new LogComparator());
Avatar of mjzalewski
mjzalewski

Make your LogError class implement Comparable

public class LogError implements Comparable {
  public int lineNumber;
  public int numberOfTimes;
  ...
  // negative if this < oCompare. positive if this > oCompare
  public int compareTo( Object oCompare) {
      LogError leCompare = (LogError) oCompare;
      if( leCompare.numberOfTimes == this.numberOfTimes) {
        return this.lineNumber - leCompare.lineNumber;
      }
      return leCompare.numberOfTimes - this.numberOfTimes;
  }
}

Now just use the java.util.Collections class to sort your Vector

  Collections.sort( totalsVector);

Even better, put your LogError items into a TreeSet class instead of a Vector, then TreeSet.iterator() returns the LogError elements in sorted order.
Use java.util.TreeSet instead of Vector. Elements will already be sorted.
Sorry, i didn't see the end of your comment, mjzalewski.
>>Use java.util.TreeSet instead of Vector. Elements will already be sorted.

Not without implementing Comparable. And if you implement it as mjzalewski has outlined, you've effectively 'hard-coded' its natural ordering, which is probably undesirable.

Using a Comparator does not tie you to one criterion of ordering

Avatar of entercite

ASKER

  So far I made the idea mjzalewski  suggested, using the Comparable value. I dont like the idea of being locked into one sort type but in the short term it works.

  Tried using the insertionSort imladris fixed but that did not sort the list at all?

  CEHJ-
    I am a bit confused about your idea. Is that all the code I need to test it or do I have to rewrite my insert sort using that compare method?
 
  If I use the java.util.TreeSet how does it know to sort my LogErrors based on the numberOfTimes value on the LogError?

> I dont like the idea of being locked into one sort type but in the short term it works.

That's fine, you have just defined the natural ordering for your LogError objects.

You can then create seperate Comparator instances to define additional sort orders, and pass that to your sort method.

>  do I have to rewrite my insert sort using that compare method?

You could change you sort method to also accept a Comparator instance, and use it to do the comparison (if providied). This would enable doing different sort orders.

> If I use the java.util.TreeSet how does it know to sort my LogErrors based on the numberOfTimes value on the LogError?

If you don't provide it with a Comparator on construction it uses the natual sort order defined by Comparable.
>>Is that all the code I need to test it

Yes. Java will do the sorting for you
Just noticed a couple of typos in my example. This is better:

      class LogComparator implements java.util.Comparator {
            public int compare(Object o1, Object o2) {
                  LogError errorOne = (LogError)o1;
                  LogError errorTwo = (LogError)o2;
                  return errorTwo.getNumberOfTimes() - errorOne.getNumberOfTimes();
            }
      }
I had a similar problem a while ago and give you a short extract of the guidelines i got from about the same people quoting in this thread
, and it works perfectly

You just have to replace the file object with your logrecord and voila...

class FileDateComparator implements Comparator {

     public int compare(Object o1, Object o2) {
          if (!(o1 instanceof File) || !(o2 instanceof File)) {
               throw new IllegalArgumentException();
          }
          File f1 = (File)o1;          
          File f2 = (File)o2;
          if (f1.lastModified()<f2.lastModified()) {
               return 1;
          }
          else if (f1.lastModified()>f2.lastModified()) {
               return -1;
          }
          return 0;
     }
}

Use the implementation like so:

TreeSet fileSet = new TreeSet(new FileDateComparator());
// Add files to fileSet

Iterator fileIt = fileSet.iterator();
while (fileIt.hasNext()) {
// do stuff to the files or something!
}
To use a TreeSet, you must have things in the set that implement Comparable. Or, you can supply a Comparator class in the constructor.

Make a LogComparator object like CEHJ suggested

  LogComparator lcSorter = new LogComparator();

Then pass the Comparator to the TreeSet, and send your Vector at the TreeSet you create (or get rid of the Vector entirely, and just add LogError items one at a time to the TreeSet.

  TreeSet tsSorted = new TreeSet( lcSorter);
  tsSorted.addAll( totalVectors);

If you want to make the class implement Comparable, but would like to be able to set different sort orders, you could do that in various ways.

Perhaps you could use both ideas. Add a static field which contains a Comparator to LogError. Then use it in the compareTo() method. Even simpler (though less object oriented) would be to use a static int field. Here is an example:

public class LogError implements Comparable {
  public int lineNumber;
  public int numberOfTimes;
  public String date;

  public static int sortBy = LogError.SORT_BY_LINE_NUMBER;
  public static final int SORT_BY_DATE = 1;
  public static final int SORT_BY_LINE_NUMBER = 2;
  // ... add more sort types

  // negative if this < oCompare. positive if this > oCompare
  public int compareTo( Object oCompare) {
      LogError leCompare = (LogError) oCompare;
    public int compareTo( Object oCompare) {
      LogError leCompare = (LogError) oCompare;
      switch( LogError.sortBy) {
         case SORT_BY_LINE_NUMBER:

          if( leCompare.numberOfTimes == this.numberOfTimes) {
            return this.lineNumber - leCompare.lineNumber;
          }
          return leCompare.numberOfTimes - this.numberOfTimes;

         case SORT_BY_DATE:
          if( leCompare.date == this.date) {
            return this.lineNumber - leCompare.lineNumber;
          }
          return this.date.compareTo( leCompare.date);
      }
        ...
      return 0;
    }
}

  Now just do LogError.sortBy = LogError.SORT_BY_DATE;

> I dont like the idea of being locked into one sort type but in the short term it works.

Of course it works. I actually tried it on my own machine before I submitted it.
mjzalewski,

I got an error with this code:

: illegal start of expression
public int compareTo( Object oCompare)


      public int compareTo( Object oCompare)
      {
            LogError leCompare = (LogError) oCompare;
            public int compareTo( Object oCompare)
            {
                  LogError leCompare = (LogError) oCompare;
                  switch( LogError.sortBy )
                  {
                        case SORT_BY_LINE_NUMBER:
                        if( leCompare.numberOfTimes == this.numberOfTimes) {
                              return this.numberOfTimes - leCompare.numberOfTimes;
                        }
                        return leCompare.numberOfTimes - this.numberOfTimes;

                        case SORT_BY_DATE:
                        if( leCompare.date == this.date) {
                              return this.numberOfTimes - leCompare.numberOfTimes;
                        }
                        return this.date.compareTo( leCompare.date);
                  }
                  
                  return 0;
            }
      }
I think you meant:

      public int compareTo( Object oCompare)
      {
            LogError leCompare = (LogError) oCompare;
            switch( LogError.sortBy )
            {
                  case SORT_BY_LINE_NUMBER:
                  if( leCompare.numberOfTimes == this.numberOfTimes) {
                        return this.numberOfTimes - leCompare.numberOfTimes;
                  }
                  return leCompare.numberOfTimes - this.numberOfTimes;

                  case SORT_BY_DATE:
                  if( leCompare.date == this.date) {
                        return this.numberOfTimes - leCompare.numberOfTimes;
                  }
                  return this.date.compareTo( leCompare.date);
            }
            
            return 0;
      }
The if statements are redundant. This will suffice for the first type of sort

>>return leCompare.numberOfTimes - this.numberOfTimes;

You should use private scoped fields though, giving you

return leCompare.getNumberOfTimes() - this.numberOfTimes;

You can also parameterize on ascending/descending order of course

Your code will be a lot cleaner using seperate Comparator implementations for seperate sort orders.

public class SortByLineNumber implements Comparator
{
    public int compareTo( Object oCompare)
     {
          LogError leCompare = (LogError) oCompare;
          return this.numberOfTimes - leCompare.numberOfTimes;
     }
}

public class SortByDate implements Comparator
{
    public int compareTo( Object oCompare)
     {
          LogError leCompare = (LogError) oCompare;
               if( leCompare.date == this.date) {
                    return this.numberOfTimes - leCompare.numberOfTimes;
               }
               return this.date.compareTo( leCompare.date);
     }
}
ASKER CERTIFIED SOLUTION
Avatar of mjzalewski
mjzalewski

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial