Link to home
Start Free TrialLog in
Avatar of coffee_bean
coffee_bean

asked on

Sorting String of data stored in an Arraylist using insertionSort.

How to use an insertionSort to sort the data according to dueDate stored in book.txt file & print the data out on the screen?
I can't sort the String of data stored in an Arraylist. What do I need to do? TIA.

--------------------BookApp.java----------------------
import java.io.*;
import java.util.*;

public class BookApp {

public static void main (String args[]){

FileController f = new FileController ("book.txt");

ArrayList recsReturn = new ArrayList();
         
recsReturn = f.readRequest(); // invoke the readRequest methods in FileController to read recoreds from book.txt file. & stores the records in recsResturn
.....
....
System.out.println(......................);
  }
}
-----------------------------------------------------------------
Content of my book.txt:
Title 1;Author 1;false;null;28/06/2003;21/06/2003      
Title 2;Author 2;false;null;28/06/2003;28/07/2003    
Title 3;Author 3;false;null;28/06/2003;10/07/2003
Title 4;Author 4;false;null;28/06/2003;08/06/2003

Output after sorting is to looks like:
Title 4  08/06/2003
Title 1  21/06/2003    
Title 3  10/07/2003
Title 2  28/07/2003

-------------------FileController.java--------------------
import java.io.*;
import java.util.*;

public class FileController {
   private String file;
     
public FileController(String file){
   this.file = file;
}
public ArrayList readRequest(){
   String line = null;
   ArrayList records = new ArrayList();
     
try{
   FileReader fr = new FileReader (file);
   BufferedReader inFile = new BufferedReader (fr);
   line = inFile.readLine();
   while (line!=null){
       records.add(line);
       line = inFile.readLine();
}
   inFile.close();
}
   catch (FileNotFoundException exception){
         System.out.println ("The file " + file + " was not found.");
}
   catch (IOException exception){
         System.out.println (exception);
}
    return records;
 }
}
---------------------Book.java ----------------------------
import java.io.*;
import java.util.*;
public class Book implements Comparable {
   private String title;
   private String author;
   private boolean loanStatus;
   private String borrowerId;
   private GregorianCalendar loanDate;
   private GregorianCalendar dueDate;

public Book(String title, String author){
   this.title = title;
   this.author = author;
   loanStatus = false;
}

// Overload constructor to take in a String
public Book (String record){
   String title;
   String author;
   boolean loanStatus;
   String borrowerId;
   GregorianCalendar loanDate = null;
   GregorianCalendar dueDate = null;
   String status;
   StringTokenizer tokenizer;
   Book bk=null;

   tokenizer = new StringTokenizer (record, ";");
   title = tokenizer.nextToken();
   author = tokenizer.nextToken();
   status = tokenizer.nextToken();
   loanStatus = Boolean.valueOf(status).booleanValue();
   borrowerId = tokenizer.nextToken();
   loanDate = MyCalendar.convertDate(tokenizer.nextToken());
   dueDate = MyCalendar.convertDate(tokenizer.nextToken());
                   
   this.title = title;
   this.author = author;
   this.loanStatus = loanStatus;
   this.borrowerId = borrowerId;
   this.loanDate = loanDate;
   this.dueDate = dueDate;
}
//  Accessor methods to get attributes of the book.
public String getTitle(){
   return title;
}
public String getAuthor(){
   return author;
}
public boolean getLoanStatus(){
   return loanStatus;
}
public String getBorrowerId(){
   return borrowerId;
}
public GregorianCalendar getLoanDate(){
   return loanDate;
}
public GregorianCalendar getDueDate(){
   return dueDate;
}

// Accessor methods to update attributes of the book.

public void setTitle(String title){
   this.title = title;
}
public void setAuthor(String author){
   this.author = author;
}
public void setLoanStatus(boolean status){
   loanStatus = status;
}
public void setBorrowerId(String id){
   borrowerId = id;
}
public void setLoanDate(GregorianCalendar loan){
   loanDate = loan;
}
public void setDueDate(GregorianCalendar due){
   dueDate = due;
}
// Returns information about this book object as a string.

public String toString(){
   return title + ";" + author + ";" + loanStatus + ";" + borrowerId + ";" + MyCalendar.formatDate(loanDate) + ";" + MyCalendar.formatDate(dueDate);
 }

public int compareTo(Object x){
   Book bk = (Book)x;
   int result;
   
   if(dueDate.before(bk.getDueDate()))
   result =-1;
   else if (dueDate.after(bk.getDueDate()))
      result =1;
   else
      result =0;
return result;
  }
}

-------------------MyCalendar.java------------------------------
import java.util.*;
import java.text.DecimalFormat;

public class MyCalendar {

//Get the number of days for first date minus second date
public static long getDifference (GregorianCalendar d1, GregorianCalendar d2){
   long firstDate = d1.getTimeInMillis();
   long secDate = d2.getTimeInMillis();
   return (firstDate - secDate)/(24*60*60*1000);
}
public static String formatDate (GregorianCalendar d1){
   DecimalFormat fmt = new DecimalFormat ("00");
   int day = d1.get(Calendar.DATE);
   int month = d1.get(Calendar.MONTH)+ 1 ;
   int year = d1.get(Calendar.YEAR);
   return fmt.format(day) + "/" + fmt.format(month) + "/" + year;
}

public static GregorianCalendar convertDate (String date){
   int day, month, year;
   day = Integer.parseInt(date.substring(0,2));
   month = Integer.parseInt(date.substring(3,5));
   year = Integer.parseInt(date.substring(6,10));
   return new GregorianCalendar(year, month-1, day);
}
public static void main (String args[]){
   GregorianCalendar d1 = new GregorianCalendar(2003, 1, 20);
   GregorianCalendar d2 = new GregorianCalendar(2003, 0, 16);

   System.out.println("First Date = " +  MyCalendar.formatDate(d1));
   System.out.println("Second Date = " + MyCalendar.formatDate(d2));
   long days = MyCalendar.getDifference(d1, d2);
   System.out.println("Difference in Days = " + days);
         
   GregorianCalendar d3 = MyCalendar.convertDate("02/03/2009");
   System.out.println("Third Date = " + MyCalendar.formatDate(d3));
 }
}
-------------------Sort.java-------------------------------
public class Sort{

public static void insertionSort (Comparable[] object)
   {
   for (int index = 1; index < object.length; index++)
    {
     Comparable key = object[index];
     int position = index;
// shift larger values to the right
     while (position > 0 && object[position-1].compareTo(key) > 0)
      {
       object[position] = object[position-1];
       position--;
      }
     object[position]= key;
    }
  }    
}
Avatar of expertmb
expertmb

>>I can't sort the String of data stored in an Arraylist
you can sort.
arraylist sorting example
import java.util.*;

class CustomerComparator implements Comparator  {

   public int compare ( Object a, Object b) {
      return (((Customer)a).getName()).compareTo(((Customer)b).getName());
      }
   }

     class CustomerSortTest1{

     public static void main(String[] s){

          System.out.println("Before Sort ....");
          ArrayList arr = new ArrayList();


          arr.add(new Customer("ABC"));
          arr.add(new Customer("PQR"));
          arr.add(new Customer("BCD"));
          arr.add(new Customer("GHK"));
          arr.add(new Customer("QWE"));
          arr.add(new Customer("AAB"));


          for(int i = 0; i < arr.size() ; i++){
               System.out.println(((Customer)arr.get(i)).getName());
          }

          System.out.println();
          System.out.println();

              Object []  cust = arr.toArray();

          Arrays.sort(cust, new CustomerComparator());

          System.out.println("After Sort ....");

          for(int i = 0; i < 6 ; i++){
               System.out.println(((Customer)cust[i]).getName());
          }
     }

}

  class Customer {
     private String name;

     public Customer(String name){
       this.name = name;
     }


     public String getName(){
         return name;
     }
}
Avatar of zzynx
Why do you use

   GregorianCalendar loanDate = null;
   GregorianCalendar dueDate = null;

instead of

   java.util.Date loanDate = null;
   java.util.Date dueDate = null;

?
ASKER CERTIFIED SOLUTION
Avatar of zzynx
zzynx
Flag of Belgium image

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
Avatar of coffee_bean

ASKER

Hi  expertmb,

I get this error while trying to compile CustomerSortTest1.

Object[]  cust = arr.toArray();
                            ^
cannot resolve symbol
symbol  : method toArray ()
location: class ArrayList

Any luck with my suggestion?
Hi zzynx,

I wish I know how to use ur codes. But I had a difficulty of  inserting them correctly into my code and make it works. You see my knowledge of java is still very limited(i m 1 yr old to java yet I m still weak in my foundation).

All I wanted is to sort my data (according to dueDate)that has been stored into an Arraylist after having retrieved from my book.txt file (using readRequest mtd).  
>> I wish I know how to use ur codes.
Just copy/paste that main() function in your Book.java class.
Then run that main function.
That's just to prove you that it works. But you don't need that main() function.

>> I had a difficulty of  inserting them correctly into my code
>> All I wanted is to sort my data (according to dueDate)that has been stored into an Arraylist after having retrieved from my book.txt file

Well, assume that your ArrayList is called "lst", all you have to do to sort it is adding

Collections.sort(lst, new Comparator() {
          public int compare(Object o1, Object o2) {
              Book b1 = (Book)o1;
              Book b2 = (Book)o2;
              if ( b1.getDueDate().getTime().before(b2.getDueDate().getTime()) )
                  return -1;
              else if ( b1.getDueDate().getTime().after(b2.getDueDate().getTime()) )
                  return 1;
              else return 0;
          }
      });

Try it.
After that code your arraylist is sorted on duedate.
Hey zzynx  :)

yes, the main method works.  But how to print out the dueDate next beside the Title Name as well?
>> yes, the main method works.
Good!

>>how to print out the dueDate next beside the Title Name as well?

while (it.hasNext()) {
        Book b = (Book)it.next();
        System.out.println( b.getTitle() + " - " + b.getDueDate().getTime() );
}
Thanks zzynx, it works beautifully :)

I will close the qn and award u the points in next 2 days if there are no more comments that are closer to what I am looking at.  

>>Thanks zzynx, it works beautifully :)
:°))

>>I will close the qn and award u the points in next 2 days if there are no more comments that are closer to what I am looking at.  
That's OK.
Ok.. I added this codes to my BookApp.java just to print out the content in the book.txt (see my main qn). InsertionSort has not been excuted yet. Becos I don't know how.

System.out.println("Before sorting: " );
for (int i =0; i<recsReturn.size();i++ ){
    String aList = (String)recsReturn.get(i);
    System.out.println(aList);
}

System.out.println("After sorting: " );
.......
.......
*********
I added the codes below to call insertionSort mtd before the "Before sorting" stt  

Sort.insertionSort(recsReturn);

But got the error:
insertionSort(java.lang.Comparable[]) in Sort cannot be applied to (java.util.ArrayList)

               
You should pay attention to the objects you are using and the classes they instantiate. I'm having trouble following the bits and pieces of algorithm that were written here, but for sure you haven't stated what type is recsReturn object.
Anyway, from what I see here you didn't get your best sollution, you wanted a way to sort on-the-fly, on insertion of objects, just like StringList objects, with sorted property set are behaving in Delphi. Your best alternative in this case is to use SortedMap. It will help you keep your objects in the exact order that you want and, in my opinion, also keep your code much more clear.
Lose the comparable implementation, you don't need it with the SortedMap object, let's call it bookKeeper :)

for every book you read from the file:
bookKeeper.put( bk.getDueDate(), bk);

and, at the end:
Book bk;
try
{
  bk = (Book)(bookKeeper.remove( bookKeeper.firstKey())); //this gets the first (lowest) key in map and removes the book
  //print info about the book
}catch( NoSuchElementException e)
{//nothing to do here, you get this error when the map is empty}

Of course, you can avoid this try-catch nasty business, but I can't remember exactly how, I'm writing this by memory... I will give you the proper code tomorrow.

Good luck!
>>error:
>>insertionSort(java.lang.Comparable[]) in Sort cannot be applied to (java.util.ArrayList)

Well, according to the error "recsReturn" is an ArrayList
while insertionSort() expects an array of Comparable as parameter.
:) thanks zzynx for the clarification.

Hmmm...i think i need to cast the objects stored in the ArrayList, recsReturn to something??? Then invoke the insertionSort mtd. Is it???

Sld I be casting objects in recsReturn into an Arrays (for storing into Arrays) and then cast to comparable objects??? (oh...those reading this, pls don't faint. I really don't know)
I don't know why you don't like my ideea, but anyway...
It seems to me that you are really trying to keep the list sorted while inserting. Your insertionSort method should use the list that you keep adding to and add the current book in the right place. Something like:

public static void insertionSort (Book bk)
   {
    boolean added = false;
   for (int index = 0; index < (theList.size() && !added); index++)
    {
      if(theList.get(index).compareTo(bk) >0) //you start with 'lower' values and hit one 'greater', here is the place to insert
      {
         theList.add( index, bk);
         added = true;
      }
     }
      //maybe all the books were 'lower', just append
      if(addde == false)
      {
         theList.add(bk);
       }
}

Or, if you decide on sorting after all books have been added to the list, you can use your algorithm, slightly changed:

public static void insertionSort (ArrayList theList)
   {
   for (int index = 0; index < theList.size(); index++) //one problem, first index is 0, not 1
    {
     int frompos = index;
// shift larger values to the right
     for( int position = index +1; position < theList.size()-1; position ++ )
      {
            if(((String)(theList.get(frompos))).compareTo((String)(theList.get(position))) > 0)
                  frompos = position;
      }
     theList.add(index, theList.remove(frompos));
    }
  }
>> It seems to me that you are really trying to keep the list sorted while inserting.
coffee_bean,
could you please confirm or deny this statement so that we know where (not) to put effort in?

>> Or, if you decide on sorting after all books have been added to the list
you can just use my earlier solution and forget about your insertionSort() function
Hi   zzynx
>>could you please confirm or deny this statement so that we know where (not) to put effort in?

Deny the stt. The insertionSort method is just one of the sorting algorithm that I'm using to sort a list of book records retrieved from book.txt (file) using readRequest() from the FileController class. I manually typed the book records n saved as book.txt (taking care to follow the same format as the body of the toString() inside the Book class.

What i m trying to do is to amend my BookApp.java to read the records from the text file, store them into an ArrayList. Then create an array of these book objects and sort them according to the dueDate(with the nearest due date appearing first). Finally display these book records on screen.

>>you can just use my earlier solution and forget about your insertionSort() function

your solution works well if I m supposed to create and instantiate an ArrayList containing Book objects and sort them according to the DueDate.  But now I m given a different scenario.

hi primusmagestri ,
>>I don't know why you don't like my ideea, but anyway...

Not that I don't like your ideas. I believe SortMap maybe a better sorting algorithm to use than insertionSort. But I have not learnt SortMap yet to use it.

>> your solution works well if I m supposed to create and instantiate an ArrayList containing Book objects
>> But now I m given a different scenario.
I don't see the different scenario.
The error you got revealed that "recsReturn" is an ArrayList. (and I think recsReturn is the result of the file read in)
So...?

   Can't you just

       Collections.sort(recsReturn, new Comparator() {
          public int compare(Object o1, Object o2) {
              Book b1 = (Book)o1;
              Book b2 = (Book)o2;
              if ( b1.getDueDate().getTime().before(b2.getDueDate().getTime()) )
                  return -1;
              else if ( b1.getDueDate().getTime().after(b2.getDueDate().getTime()) )
                  return 1;
              else return 0;
          }
      });

?
Don't understand...
The above gives you a sorted ArrayList.

To become the corresponding array of Books (sorted!) :

  Books[] books = (Books[]) recsReturn.toArray();
SOLUTION
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
Hi primusmagestri

How do u call the insertionSort(ArrayList theList) from the BookApp.java? I can't insert your insertionSort into my Sort class without getting error as ArrayList theList is declared my BookApp.java.

But if I were to insert your insertionSort(ArrayList theList) into my BookApp.java, I manage to get the output I wanted. :-) provided that I create n initialised my Book objects. eg:

theList.add(new Book(Title 1;Author 1;false;null;28/06/2003;21/06/2003));
......
.....
theList.add(new Book(Title 4;Author 4;false;null;28/06/2003;08/06/2003));

 
opps I haven't finished what I wanted to say...continue from above:

But I get errors executing your insertionSort(ArrayList theList) if I the book objects are read from the file using readRequest();

Hi zzynx,
Overall your codes works wonderfully.  However when it comes to reading the records from the file and sorting them, I will have errors as the records are in String which are later stored into ArrayListrecsReturn.  

By the way,  

Books[] books = (Books[]) recsReturn.toArray();

has this error: Exception in thread "main" java.lang.ClassCastException at BookApp.main(BookApp.java:35)

Similarly to the problem i had early on with expertmb's code (Object []  cust = arr.toArray(); or Customer[] cust = (Customer[])arr.toArray();) otherwise kind of curious how his codes run.

But anyway, I will be closing the qn tomorrow since both u n primusmagestri had help me with the codes that works.
Hi zzynx,

u were suggestion me to use previous:

java.util.Date loanDate = null;
java.util.Date dueDate = null;

private Date loanDate;
private Date dueDate;
....
....

How then do I set the dueDate for for my Book object b1, b2 & b3 etc using the date format as suggested?
>How to use an insertionSort to sort the data according to dueDate stored in book.txt file & print the data out on the screen?
Correct me if I am wrong, but wasn't this the original question? Didn't you want a Java implementation of the algorithm to sort 'by insertion'? If that is the case, then, with all the respect, I have to ask why I received the 'Assisted answer' rank and zzynx got 'Accepted answer'?
Hi primusmagestri

>> If that is the case, then, with all the respect, I have to ask why I received the 'Assisted answer' rank and zzynx got 'Accepted answer'?

If u didn't point out, i didn't even realised it stated as Assisted answer. I accepted both answers since both sort according to dueDate. I have splited the points, but I have no idea why yours is not stated as accepted answer as well.  Yours rightfully should be 'Accepted answers' like zzynx.

>>Correct me if I am wrong, but wasn't this the original question? Didn't you want a Java implementation of the algorithm to sort 'by insertion'?

hmm...actually I already have the sort algorithm (insertionSort) in place. What I need is how to use 'my' insertionSort to sort my record according to dueDate n print out on screen. Becos i was having problem executing 'my' insertionSort in my BookApp.java.

Quoting my qn >>... I can't sort the String of data stored in an Arraylist.
Hi primusmagestri

I think i know why yours was stated as 'Assisted answer'.  Seem like there can be only 1 'Accepted answer' and the rest will be stated as 'Assisted answer'.

I had clicked on the buttons of both of your comments. But before I submited the grade, I scrolled up to counter-check on my grading and I saw zzynx's button was unchecked (becos i last clicked on yours). Thinking that I could have missed out on zzynx's button, I checked it and submitted the grade. Now then I realised the grading system only allows 1 'Accepted answer'.  

 
Hey, no harm done; glad I could help along with zzynx ;-)
Hi wanna thank you all for helping me with the problem.

I've learnt something other just solving the problem. You all have helped me understand the java concept better and cleared up some of the doubts I had all along. Now I see some light to those concept  ; p

Oh...i've benefit so much from this.

To expertmb,

I finally manage to get your codes working after closing the qn. :p

By changing
>> Object []  cust = arr.toArray();  to
Customer[] cust =(Customer[])arr.toArray(new Customer[0]);



>>for(int i = 0; i < 6 ; i++){....} to
for(int i = 0; i < cust.length ; i++){.....}

I'd even can use your codes with mine to work by changing a couple of codes.  Thank you too.
Thanks for accepting.


P.S. You are aware of A, B and C grades, aren't you?
Hi zzynx

Yes...in fact the solutions to this qn deserve an A. I have just asked the community support on how to get the grade change. Waiting for their reply/action. ;)

To those interested,

This is how I get them to work. (Below codes to retrieve the Book objects that returned as a String from the book.txt. And later sort according to the dueDate.)

Note: I manually typed the book records and save as book.txt file. Refer to my qn on top on the content inside the book.txt.

Title 1;Author 1;false;null;28/06/2003;21/06/2003      
Title 2;....
.....

Here is the code:
-----------BookApp.java--------------------------------
import java.io.*;
import java.util.*;

public class BookApp {
public static void main (String args[]){

FileController f = new FileController ("book.txt");

ArrayList recsReturn = new ArrayList();

recsReturn = f.readRequest(); // invoke the readRequest methods in FileController to read records from book.txt file. & stores the records to recsResturn

String line;
Book book;
Book[] bkList = new Book[recsReturn.size()];
            
System.out.println("======Before Sorting=====");
            
for (int i=0; i<recsReturn.size(); i++){
   line=(String)recsReturn.get(i);
   book = new Book(line);
   bkList[i]=book;
   System.out.println(book.getTitle() +" " + MyCalendar.formatDate(book.getDueDate()));
}
            
Sort.insertionSort(bkList);
            
System.out.println("======After Sorting=====");
for (int i=0; i<recsReturn.size(); i++){
   book=bkList[i];
      
   System.out.println(book.getTitle() +" " +   MyCalendar.formatDate(book.getDueDate()));
  }
 }
}

>>in fact the solutions to this qn deserve an A. I have just asked the community support on how to get the grade change.
Thanks coffee_bean