java binary search and insert

[pansylea]

I'm currently writing a program which is an appointment book. I currently have 4 classes and at the minute it can sort the array and print it out. I'm stuck at binary search and inserting a new appointment record. How would i code binary search to insert a new appointment which the user will input. I will include the classes which i have got.

Appointment

import java.util.*;
   import java.io.*;
   import java.util.Scanner;
 
    class Appointment implements Comparable
   {
      private String description;
      private int day;
      private int month;
      private int year;
      private String startTime;
      private String endTime;
   	
      protected static Scanner keyboard = new Scanner(System.in);	
   	
       public Appointment()
      {
         description = "";
         day = 0;
         month = 0;;
         year = 0;;
         startTime = "";
         endTime = "";
      }
   	
       public Appointment(String appDesc, int appDay, int appMonth, int appYear, String appStartTime, String appEndTime)
      {
         description = appDesc;
         day = appDay;
         month = appMonth;
         year = appYear;
         startTime = appStartTime;
         endTime = appEndTime;
      }
   		
       public void display()       
      {
         System.out.print("  Description: " + description);
         System.out.print(", Date: " + day + "/" +month+ "/" +year);
         System.out.println(", Start Time: " + startTime);
         System.out.println(", End Time: " + endTime);
      }
   	
   	
       public void setDay(int day) 
      { this.day = day; }
   	
       public int getDay()      
      { 
         return day; }
   	
       public void setMonth(int month) 
      { this.month = month; }
   	
       public int getMonth()      
      { 
         return month; }
   		
       public void setYear(int year) 
      { this.year = year; }
   	  
       public int getYear() 
      { 
         return year; }
   	
       public int compareTo(Object obj)
      {
         if (obj instanceof Appointment) 
         {
            Appointment appt = (Appointment) obj;
            if (this.day > appt.getDay())
               return 1;
            else if (this.day < appt.getDay());
            return -1;
         }
         return 0;
      } 	
   	
       public String toString() {
            
         StringBuffer buffer = new StringBuffer();
         buffer.append("Description: " + description);
         buffer.append(", Date: " + day + "/" +month+ "/" +year);
         buffer.append(", Start Time: " + startTime);
         buffer.append(", End Time: " + endTime);
            
         return buffer.toString();
      }
   	  
       public void read(){
         System.out.print("Description : ");String descIn=keyboard.next();
         System.out.print("Day : ");int dayIn=keyboard.nextInt();
         System.out.print("Month : ");int monthIn=keyboard.nextInt();
         System.out.print("Year : ");int yearIn=keyboard.nextInt();
         System.out.print("Start Time : ");String startIn=keyboard.next();
         System.out.print("End Time : ");String endIn=keyboard.next();
      
         boolean goodInput = false;
      
         do{		
            try{
               setDay(dayIn);
               setMonth(monthIn);
               setYear(yearIn);
               goodInput = true;
            }
                catch(IllegalArgumentException e){
                  System.out.println("INVALID ARGUMENT PASSED FOR day or month or year");
                  System.out.println(e);
                  System.out.print("RE-ENTER VALID ARGUMENT FOR DAY : ");dayIn=keyboard.nextInt();
                  System.out.print("RE-ENTER VALID ARGUMENT FOR MONTH : ");monthIn=keyboard.nextInt();
                  System.out.print("RE-ENTER VALID ARGUMENT FOR YEAR : ");yearIn=keyboard.nextInt();								
               }
         }while(!goodInput);
      }
   
   
   }

Array

import java.util.*;
 
class Array
{
	private Appointment[] app;
	private int nElems;
	Appointment tempApp;
		
	public Array(int max)
	{
		app = new Appointment[max];
		nElems = 0;
	}
	
	public Array(String desc, int day, int month, int year, String sTime, String eTime)
	{
		app = new Appointment[100];
		nElems = 0;
	}
	
   public int size()
      { return nElems; }
	
	void add(){
		Appointment appointmentToAdd = new Appointment();
 
		// Read its details
		appointmentToAdd.read();
		
		// And add it to the studentList
		//app[nElems].add(appointmentToAdd);
	}
 
	public void add(String desc, int day, int month, int year, String sTime, String eTime)
   {
	   app[nElems] = new Appointment(desc, day, month, year, sTime, eTime);
	   nElems++;             // increment size
		
		Appointment appointmentToAdd = new Appointment(desc, day, month, year, sTime, eTime);
	
		// And add it to the studentList
		//app[nElems].add(appointmentToAdd);
   }
 
	 public void insert(Appointment tempApp) {
    int j;
    for (j = 0; j < nElems; j++)
      // find where it goes
      if (app[j] > tempApp) // (linear search)
        break;
    for (int k = nElems; k > j; k--)
      // move bigger ones up
      app[k] = app[k - 1];
    app[j] = tempApp; // insert it
    nElems++; // increment size
  }
 
   public void display()       // displays array contents
   {
	   for(int j=0; j<nElems; j++)    // for each element,
	     app[j].display();     // display it
	   System.out.println("");
   }
	/*
	public void insertionSort()
   {
   int in, out;

   for(out=1; out<nElems; out++) // out is dividing line
     {
     Appointment temp = app[out];    // remove marked person
     in = out;          // start shifting at out

     while(in>0 &&        // until smaller one found,
        app[in-1].getMonth().compareTo(temp.getMonth())>0)
      {
      app[in] = app[in-1];     // shift item to the right
      --in;          // go left one position
      }
     app[in] = temp;        // insert marked item
     } // end for
   } // end insertionSort()
	*/
}

Menu

import java.util.*;
 
class Menu{
   private static Scanner keyboard = new Scanner(System.in);
 
   int option;
	
	Menu(){
	   option=0;
	}
	
	void display(){
		// Clear the screen
	   System.out.println("\n1 Display");
		System.out.println("\n2 Insert");		
		System.out.println("3 Quit");		
	}
	
	int readOption(){
	   System.out.print("Enter Option [1|2|3] : ");
		option=keyboard.nextInt();
		return option;
	}
}

Tester

import java.util.*;
   import java.util.Arrays;
 
    class ObjectSortApp
   {
       public static void main(String[] args)
      {
			int maxSize = 100;
			Array arr;
			arr = new Array(maxSize)
			
			Appointment app1 = new Appointment("College Closed", 30, 4, 2009, "09:30", "05:30");;
			Appointment app2 = new Appointment("Assignment Due", 25, 4, 2009, "09:30", "05:30");
         Appointment app3 = new Appointment("College Closed", 17, 4, 2009, "09:30", "05:30");
         Appointment app4 = new Appointment("Easter Break", 9, 4, 2009, "01:30", "05:30");
         Appointment app5 = new Appointment("College Opens", 15, 4, 2009, "09:30", "05:30");
         Appointment app6 = new Appointment("Assignment Due", 12, 4, 2009, "09:30", "05:30");
         Appointment app7 = new Appointment("Exams Begin", 11, 4, 2009, "09:30", "05:30");
			
		  //To sort them we create an array which is passed to the Arrays.sort()
        //method.
        Appointment[] appArray = new Appointment[] {app1, app2, app3, app4, app5, app6, app7};
		  
         System.out.println("Before sorting:");
        //Print out the unsorted array
        for (Appointment app : appArray)
            System.out.println(app.toString());  
      		
		  Arrays.sort(appArray);
      
         //arr.insertionSort();      // insertion-sort them
      
         System.out.println("\n\nAfter sorting:");			
        //Print out the sorted array
        for (Appointment app : appArray)
            System.out.println(app.toString());
				
		Menu appMenu = new Menu();
		int chosenOption;
		
		do{
		   appMenu.display();
			chosenOption=appMenu.readOption();
			
			for (Appointment app : appArray)
			switch(chosenOption){
			   case 1 : app.display(); break;
				case 2 : arr.add(); break;
				default:;
			}
		}while(chosenOption != 3);     
      } // end main()
   } // end class ObjectSortApp

[emceenugget]

search and insert are two different algorithms. have you successfully written either?

binary search: C++ Notes: Algorithms: Binary Search

insert: just insert into your list...

[pansylea]

Since the user will be inserting the full appointment, the search will be to find one on that day, how do i do that?

[emceenugget]

if you can sort, then you can search.

[pansylea]

it does sort at the minute, i just dont know how to implement the search with just taking the date from the users input

[emceenugget]

parse the user input into something you can compare to whatever you're comparing. then implement a binary search like in the link i sent you.

[pansylea]

I've added the binary search into the Array class and now when i run the tester i get the error of :

Exception in thread "main" java.lang.NullPointerException
at Array.add(Array.java:39)
at ObjectSortApp.main(ObjectSortApp.java:48)

Array

   import java.util.*;
   import java.io.*;
   import java.util.Arrays;

    class Array
   {
      private Appointment[] app;
      private int nElems;
   	
      private String descIn = "";
      private int dayIn = 0;
      private int monthIn = 0;
      private int yearIn = 0;
      private String sTimeIn = "";
      private String eTimeIn = "";
   	
       public Array(int max)
      {
         app = new Appointment[max];
         nElems = 0;
      }
   
       public Array(String desc, int day, int month, int year, String sTime, String eTime)
      {
         app = new Appointment[100];
         nElems = 0;
      }
   
       public int size()
      { 
         return nElems; }
   
       public void add(Appointment[] sortedArray){
         Appointment appointmentToAdd = new Appointment();
      
      // Read its details
         appointmentToAdd.read();
        
         descIn = app[nElems].getDescIn();
         dayIn = app[nElems].getDayIn();
         monthIn = app[nElems].getMonthIn();
         yearIn = app[nElems].getYearIn();
         sTimeIn = app[nElems].getSTimeIn();
         eTimeIn = app[nElems].getETimeIn();
        
         boolean goodInput = false;
         do{		
            try{
               app[nElems].setDay(dayIn);
               app[nElems].setMonth(monthIn);
               app[nElems].setYear(yearIn);
               goodInput = true;
            }
                catch(NullPointerException e){
                  System.out.println("\n\n");
                  //System.out.println(e);								
               }
         }while(!goodInput);
       
         binarySearch(sortedArray, dayIn);
      	
         //Array newArray = new Array(descIn, dayIn, monthIn, yearIn, sTimeIn, eTimeIn);
               
         nElems++;
        
      }
   	/*
       public void add(String desc, int day, int month, int year, String sTime, String eTime)
      {
         binarySearch(app, day);
      	
         app[nElems] = new Appointment(desc, day, month, year, sTime, eTime);
         nElems++;             // increment size
      
         Appointment appointmentToAdd = new Appointment(desc, day, month, year, sTime, eTime);
      
      // And add it to the studentList
        //tempApp.add(appointmentToAdd);
      }
   	*/
   
       public void display()       // displays array contents
      {
         for(int j=0; j<nElems; j++)    // for each element,
            app[j].display();     // display it
         System.out.println("");
      }
   	
       static int binarySearch(Appointment[] a, int tempDay) {
              // Searches the array A for the integer tempDay.
              // A is assumed to be sorted into increasing order.
              
         int lowestPossibleLoc = 0;
         int highestPossibleLoc = a.length - 1;
            
         while (highestPossibleLoc >= lowestPossibleLoc) {
            int middle = (lowestPossibleLoc + highestPossibleLoc) / 2;
            if (a[middle].getDay() == tempDay) {
                         // N has been found at this index!
               return middle;
            }
            else if (a[middle].getDay() > tempDay) {
                         // eliminate locations >= middle
               highestPossibleLoc = middle - 1;
            }
            else {
                         // eliminate locations <= middle
               lowestPossibleLoc = middle + 1;
            }
         }
         return -1;
      
      }
      /*
      public void insertionSort()
      {
      int in, out;
      
      for(out=1; out<nElems; out++) // out is dividing line
      {
      Appointment temp = app[out];    // remove marked person
      in = out;          // start shifting at out
      
      while(in>0 &&        // until smaller one found,
        app[in-1].getMonth().compareTo(temp.getMonth())>0)
      {
      app[in] = app[in-1];     // shift item to the right
      --in;          // go left one position
      }
      app[in] = temp;        // insert marked item
      } // end for
      } // end insertionSort()
      */
   
   }