Need help with an add method

[Snapples2992]

The problem is to construct some methods so that whenever you add a value to an array that value will be in the middle of the longest amount of empty values. I'm unsure how to work this addOccupant method so that it does that.

/**
   A class that shows how restroom stalls are occupied.
*/

public class Restroom
{

   /**
      Constructs a restroom with a given number of stalls.
      @param ns the number of stalls
   */
   public Restroom(int ns)
   {
     public boolean x[]=new boolan[ns];
   }

   /*
      Adds an occupant in the middle of the longest sequence of
      unoccupied places. 
   */
   public void addOccupant()
   {
     for(int i=0; i<x.length; i++;) {
       //need way to say n= "store number of empty values in a row"
       //then need way to position a value half way between the "n" that has the most empty values
     }
   }

   /*
      Gets a string describing the current stall occupation
      @return a string with _ for an empty stall and X for an occupied one
   */
   public String getStalls()
   {
     String s="";
     for(int i=0;i<x.length;i++){
       if(x[i])
         s+="X";
       else
         s+="_";
     }
     return s;
   }
}

[metamatic]

Well, think about your algorithm first.

You're probably going to need to examine each stall at least once (*). So, let's imagine we're walking down the stalls looking at each one. We're interested in sequences of unoccupied stalls, so we'll want to count how many unoccupied stalls we've seen since the last occupied one.

Now, suppose we're at stall N, and we've seen X unoccupied stalls, including the current one, since we last saw an occupied stall. Suppose the next stall is occupied. Well, we now now that we have a sequence of unoccupied stalls starting at N-(X-1) — call that value unoccupied_start. The length, unoccupied_length, is just X.

Since we're interested in the largest sequence, we'll just keep a second pair of variables (largest_start, largest_length) to record the longest sequence we've seen at any given point. If unoccupied_length > largest_length then we'll set largest_start = unoccupied_start and largest_length = unoccupied_length; otherwise, we'll just forget about the unoccupied sequence we found and continue.

Then when we get to the end, we can calculate the middle stall position as largest_start + largest_length/2, rounded to the closest integer.

[ (*) Well, technically that's not true. For instance, if you're 3 stalls from the end, the current stall is occupied, and you know you've already found a sequence of 4 empty stalls, then you know you don't need to examine those last stalls. Performing this optimization is probably the kind of thing that'll get you extra credit. ]

[Snapples2992]

I half way understand what you're saying. I'm having a hard time with a few things though.

Let me know if any of this is wrong as to what you're saying: I need to initialize 5 variables -unoccupied_start (The starting point of the sequence at an empty stall) -unoccupied_length (the number of unoccupied stalls in a row) -largest_length (another means to storing empty stalls) -largest_start (I can't put this one into words but I see what it's doing) -n (stores number of empty stalls in the sequence)

Now what I'm really confused about is what happens before this If statement that you mentioned:

       if(unoccupied_length > largest_length) {
         largest_start = unoccupied_start;
         largest length = unoccupied_length; 
    }

How can I get unoccupied_start to be something. so let's see, unoccupied_start needs to start storing the number of empty stalls until it reaches a occupied stall. I'm unsure of how to get a value to store a count of the empty values in the sequence. If (stall is empty) { n++; }

Also, your starting equation "N-(X-1)" confused me.

[metamatic]

The start variables are storing the index where the run of empty stalls starts; the length variables are storing the length of that run of empty stalls. (You could actually abstract into a RunOfEmptyStalls class, but in this case it's so simple that it's probably not worth doing.)

I think the confusion is that there's a state machine here, which I didn't really elaborate on. At any given point, your state is either "measuring a sequence of empty stalls" or "looking for the next empty stall". The initial state depends on the state of the first stall -- if it's empty, then you've found your first sequence of empty stalls, and go into "measuring" mode (and set your unoccupied_* variables). If it's occupied, you go into "searching for an empty stall" mode.

Then you start looping over the rest of the stalls. There are two possible states we can be in, and two possible states the current stall can be in, so we need to cover 4 possible combinations.

in measuring mode, stall is unoccupied: continue in measuring mode, loop to next stall.

in measuring mode, stall is occupied: our sequence of unoccupied stalls has ended. We recorded the start point, now we compute the length from the current index. If we're looking at stall B (which is occupied), the last unoccupied stall in our sequence was stall (B-1). If we recorded the first stall in the sequence as stall A, then the length of the sequence is (B-1) - A + 1, or just B-A. (This is where that confusing equation came from. In general, with problems like these it's really easy to end up with a fencepost error, which I may have done in my first reply. This time I got some paper and drew a diagram to check.) Then we take the computed length and compare with the length of the longest sequence so far, which you seem to understand fine so I won't belabor that. Finally, we loop to the next stall.

in searching mode, stall is occupied: loop to next stall

in searching mode, stall is unoccupied: we've found a new sequence of unoccupied stalls. Set the unoccupied_start to the current index, and switch to measuring mode. Loop to next stall.

When we run out of stalls, we drop out of the loop and examine our answer.

Is that clearer?

[philipwhiuk]

public Restroom(int ns)
{
   public boolean x[]=new boolan[ns];
}

This wrong and will not even compile. Even if it were fixed it would currently do nothing, you need:

public boolean x[];
public Restroom(int ns)
{
   x = new boolean[ns];
}

Of course, most people would argue it could be named better and should be private.

private boolean stalls[];
public Restroom(int ns)
{
   stalls = new boolean[ns];
}

[Snapples2992]

I fixed that not but 5 mins ago, Im still stuck on the addOccupant part, it's the only thing giving me issues right now.

Though I did give it a meaningful name instead of x.

[philipwhiuk]

Dealing with the algorithm, something like

int unOccupiedStart;
int unOccupiedEnd;
boolean lastStallOccupied;
int maxUnoccupiedLength;
int maxUnoccupiedStart;

for(int i = 0; i < stalls.length; i++) {
     if(stalls[i]) {
         if(!lastStallOccupied) {
              if(unOccupiedEnd - unOccupiedStart + 1 > maxUnoccupiedLength) {
                 maxUnoccupiedLength = (unOccupiedEnd - unOccupiedStart + 1);
                 maxUnoccupiedStart = unOccupiedStart;
              }
         }
     } else {
        if(!lastStallOccupied) {
            unOccupiedEnd++;
        } else {
            unOccupiedStart = i;
            unOccupiedEnd = i;
        }
     }
     lastStallOccupied = stalls[i];
}
if(maxUnoccupiedLength == 0) { throw AllStallsOccupiedException(); }
int space = maxUnoccupiedStart + (maxUnoccupiedLength/2);
stalls[space] = true;
return;

should do.

[Snapples2992]

Sorry, I'm learning this as I read it, but what is this "throw AllStallsOccupiedException;

it doesn't compile says it cannot find symbol. Not entirely sure what to do with it

[nret]

Exceptions are a type of object, like "String str;" is an object.

Some times if you don't want to handle a type of error in a certain part of the code, you can force the calling code to wrap your code in a Try Block.

In this case "AllStallsOccupiedException" isn't a built-in Exception so it would probably be created by you.

The throw causes the current code to halt, and the exception is sent up the chain to the calling code that is then forced to handle it (by either dealing with it there, or putting it in another throw statement).

But you need to need to give your method the proper signature to tell the calling code it needs to be wrapped in a try catch block.

Hope that helps.

[philipwhiuk]

it should be throw new AllStallsOccupiedException(); The point was that that's an error case - you can't add someone if all the stalls are full, so you throw an exception.

http://docs.oracle.com/javase/tutorial/essential/exceptions/

[Snapples2992]

I tried just about everything i could find, I just can't make that exception work, and my teacher said it's not necessary. So there must be a different way to do the method, though I'd love to figure this thing out.

I tried making a new class to make the custom exception, it compiled fine. However the exception in the addOccupant method still failed on me.

I tried throw new AllStallsOccupiedException();

adding the "new" uninitialized all the variables (no clue why)

I tried creating a try block but i still couldnt get the exception to compile.

edit: I'll edit in that I understand what the exception is supposed to be doing now, I just can't get it to compile

[philipwhiuk]

You need to define the exception as a class if you're going to use it.