Results 1 to 7 of 7
  1. #1
    pansylea is offline Member
    Join Date
    Feb 2009
    Posts
    20
    Rep Power
    0

    Default java binary search and insert

    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

    Java Code:
    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

    Java Code:
    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

    Java Code:
    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

    Java Code:
    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

  2. #2
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    6

    Default

    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...

  3. #3
    pansylea is offline Member
    Join Date
    Feb 2009
    Posts
    20
    Rep Power
    0

    Default

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

  4. #4
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    6

    Default

    if you can sort, then you can search.

  5. #5
    pansylea is offline Member
    Join Date
    Feb 2009
    Posts
    20
    Rep Power
    0

    Default

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

  6. #6
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    6

    Default

    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.

  7. #7
    pansylea is offline Member
    Join Date
    Feb 2009
    Posts
    20
    Rep Power
    0

    Default

    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

    Java Code:
       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()
          */
       
       }

Similar Threads

  1. Binary Search Problem
    By sharpnova in forum New To Java
    Replies: 2
    Last Post: 02-19-2009, 10:22 AM
  2. Recursive Binary Search
    By EternalSolitude in forum New To Java
    Replies: 2
    Last Post: 11-21-2008, 06:26 AM
  3. Help. Binary Search Problem
    By Krooger in forum Advanced Java
    Replies: 1
    Last Post: 11-03-2008, 06:19 AM
  4. Binary Search in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 07:43 PM
  5. binary search
    By tranceluv in forum New To Java
    Replies: 10
    Last Post: 01-14-2008, 07:13 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •