Solved

java timetabling problems

Posted on 2006-11-20
1
188 Views
Last Modified: 2010-03-31
I've been trying to implement a timetable allocating system which allocates courses to timeslots randomly. i've just done 2 classes :-
Two_D_Allocation class which contains a main method for running the program and, Two_TimeArray class which is a 2-d array class which handles the timeslots, and methods to manipulate the timeslots. I, ve been having the following errors

cd /s_home1/tor3/project/
/usr/lib/j2sdk1.4-sun/bin/java Two_D_Allocation

Exception in thread "main" java.lang.StackOverflowError

Process Two_D_Allocation exited abnormally with code 1


the source code for both classes are shown below


/**
 * Two_D_Allocation.java
 *
 *
 * Created: Mon Nov 20 13:35:39 2006
 *
 * @author <a href="mailto:">T. O. ROGERS-HALLIDAY</a>
 * @version 1.0
 */
public class Two_D_Allocation {

   
    public static void allocateTimeSlot(String course, Two_TimeArray ts){
      int dayIdx = ts.generateDay(ts.getNoOfDays() - 1);
      int periodIdx = ts.generatePeriod(ts.getDailyCapacity() - 1);
      if(ts.availabilityCheck(dayIdx, periodIdx)== true){ts.assignCourse(course, dayIdx, periodIdx);}
      else allocateTimeSlot(course, ts);
      
      }

    public static void main (String [] args){
      
      Two_TimeArray cs = new Two_TimeArray(5);
      String [] courses  = {"maths" , "english", "physics", "chemistry"};

//       for(int i = 0; i <= courses.length - 1 ; i++) {
//           allocateTimeSlot(courses[i], cs);
//          //   System.out.println("just assigned " + courses[i]+ "/n" + "/n");
//       }

//       int d = cs.generateDay(4);
//       int p = cs.generatePeriod(4);
      allocateTimeSlot("maths",cs);
      allocateTimeSlot("english",cs);

      cs.printSlots();
    }
}

the class for handling timeslots is shown below

/**
 * Describe class 2-DTimeArray here.
 *
 *
 * Created: Fri Nov 17 13:08:46 2006
 *
 * @author <a href="mailto:">T. O. ROGERS-HALLIDAY</a>
 * @version 1.0
 */

import java.util.*;
import java.awt.*;

public class Two_TimeArray {
   
    private static String [] days = {"monday","tuesday","wednesday","thursday","friday"};
    private  int capacity;
   
    private  String slots [][];
   
    public Two_TimeArray(int slotcapacity) {
      
      capacity = slotcapacity;
      slots = new String[days.length][slotcapacity];
      
      for(int i = 0; i < days.length ; i++){

          int count = 0;
          while(count < capacity ){
            slots[i][count] = "free";
            //            System.out.println("just assigned to free");
            count++;
          }
      }
    }

    public  boolean availabilityCheck(int dayIdx, int periodIdx){
      
      if(slots[dayIdx][periodIdx] == "free"){return true;}
      else return false;
    }

    public  int generatePeriod(int no_of_periods){
      Random r = new Random();
      return r.nextInt(no_of_periods);
    }
    public  int generateDay(int no_of_days){
       Random r = new Random();
       return r.nextInt(no_of_days);
     }
   
    public  int getDailyCapacity(){return capacity;}
   
    public int getNoOfDays(){return days.length;}
   
    public  void assignCourse(String course, int dayIdx, int periodIdx){           slots[dayIdx][periodIdx] = course;
    }
   

    public void printSlots(){
      
      for(int i = 0; i < days.length ; i++){
          int count = 0;
          while(count < capacity ){
            System.out.println(slots[i][count]);
            count++;
          }
          System.out.println("\n" + "\n");
      }
    }
}







0
Comment
Question by:vrameen
1 Comment
 
LVL 10

Accepted Solution

by:
ADSLMark earned 500 total points
ID: 17982188
Well you probably won;t get this error all the time, but the idea is that you have a semi-recursive method, which in theory should end, but in practice, the computer won't be able to handle it.
Problem is in Two_D_Allocation

public static void allocateTimeSlot(String course, Two_TimeArray ts)
{
    int dayIdx = ts.generateDay(ts.getNoOfDays() - 1);
    int periodIdx = ts.generatePeriod(ts.getDailyCapacity() - 1);
    if(ts.availabilityCheck(dayIdx, periodIdx)== true) {ts.assignCourse(course, dayIdx, periodIdx);}
    else allocateTimeSlot(course, ts);
}

if the if-check fails, then the else is done, which is a recursive call with the same parameters to allocateTimeSlot. Let's assume the if-check fails.. 1.000.000 times after eachother, then java has to call allocateTimeSlot 1.000.000 times. There is something like a call-stack which keeps track on what method is called and from which method.. You can imagine something like:

allocateTimeSlot
--> allocateTimeSlot
    --> allocateTimeSlot
        --> allocateTimeSlot
            --> allocateTimeSlot
                --> allocateTimeSlot
                    --> etc.

Well that's where the stack overflow comes from.
A solution would be to use pseudo random numbers. Create a list of all the possible numbers/slots and then make a limited number of swaps. Next you iterate over this list and take the current number as index.

int capacity = 100;
int[] randomNumbers = new int[capacity];
for(int i=0;i<capacity;i++)
    randomNumbers[i] = i;

int numSwaps = 10000;
Random r = new Random();
for(int i=0;i<numSwaps;i++)
{
    int r1 = r.nextInt(capacity);
    int r2 = r.nextInt(capacity);

    int tmp = randomNumbers[r1];
    randomNumbers[r1] = randomNumbers[r2];
    randomNumbers[r2] = tmp;
}

for(int i=0;i<capacity;i++)
{
    index = randomNumbers[i];
    //Do whatever you want with the index.
}

I hope this explains the problem.
Mark
0

Featured Post

Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Are you developing a Java application and want to create Excel Spreadsheets? You have come to the right place, this article will describe how you can create Excel Spreadsheets from a Java Application. For the purposes of this article, I will be u…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…

789 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question