add_with_prefs.java

//attempts to add the given request together, fulfilling all prefs.
    //if ALL preferences cannot be fulfilled, no change is made and method returns false
    public boolean add_with_prefs(String[] reqs)
    {
        String[][] tokend = new String[reqs.length][];

        //tokenize reqs
        for(int i = 0; i < reqs.length;i++)
        {
            tokend[i] = reqs[i].split("/");
        }
        int windowcount = 0;
        int aislecount = 0;


        //finds all ranges of reqs.length contiguous seats
        int[][] ranges = get_ranges(reqs.length);

        //no room in this row!
        if(ranges.length == 0)
                return false;

        //count number of aisle/window requests
        for(int i = 0; i < tokend.length;i++)
        {
            if(tokend[i].length > 3)
            {
                if(tokend[i][3].equals("A"))
                    aislecount += 1;
                else //if(tokend[i][3].equals("W"))
                    windowcount += 1;
            }
        }

        int[] mask = new int[tokend.length];      //marks which reqs have been placed
        int[] windows = new int[windowcount];   //pointers into reqs[] that are window requests
        int[] aisles = new int[aislecount];     //pointers into reqs[] that are aisle requests
        int[] rest = new int[reqs.length - windowcount - aislecount]; //pointers into reqs[] that have no pref
        int m=0,x=0,y=0,z=0; //pointers into each array

        //populate pointers
        for(int i = 0; i < tokend.length;i++)
        {
            if(tokend[i].length == 3)
            {
                rest[z++] = i;
            }
            else //window or aisle pref
            {
                if(tokend[i][3].equals("W"))
                {
                    windows[x++] = i;
                }
                else if(tokend[i][3].equals("A"))
                {
                    aisles[y++] = i;
                }
            }
        }
        x=0;y=0;z=0;

        int rp = 0;
        boolean placed = false;

        //this requires an explanation. Follow comments closely
        while(!placed && (rp < ranges.length))
        {
            //FOR EACH RANGE OF VALID SEATS, iterate through the range of seats, filling them
            //sequentially. rp is the pointer into the ranges, and i is the current seat
            for(int i=ranges[rp][0];i<ranges[rp][0];i++)
            {
                //if the seat is an aisle seat
                if(seats[i].is_aisle())
                {
                    //if we've already satisfied everyones' aisle requests
                    //place a regular person into the aisle seat by:
                    //take the next non-requesting person reqs[rest[z]] and place this person's
                    //index (rest[z]) into mask. This marks that this person has been seated.
                    //Set the value of mask[index] to i, where is is the seat he would be sitting in
                    //the end result is that mask[index] = seat tells us to seat the index'th person
                    //in the reqs array in the seat rows[seat]
                    //also increment z as we just filled another seat
                    if(y < aislecount)
                    {
                        mask[aisles[y++]] = i;
                    }
                    else if (z < rest.length)
                    {
                        mask[rest[z++]] = i;
                    }
                    //this means that we have to put a window person in an aisle seat
                    //therefore we cannot satisfy all requests using this range
                    else //if ( (y >= aislecount) && (z >= rest.length))
                    {
                        break; //stop checking this range and move on to the next range
                    }
                }
                else if(seats[i].is_window())
                {

                    if(x < windowcount)
                    {
                        mask[windows[x++]] = i;
                    }
                    else if(z < rest.length)
                    {
                        mask[rest[z++]] = i
                    }
                    //this means that we have to put an aisle person in the window seat
                    //therefore wec annot satisfy all requests using this range
                    else //if( (x >= windowcount) && (z >= rest.length))
                    {
                        break;
                    }
                }
                else
                {
                    if(z < rest.length)
                    {
                        mask[rest[z++]] = i;
                    }
                    //this means that we have to fill a normal seat with someone who has a preference.
                    //hence we cannot fulfill all requests
                    else
                    {
                        break;
                    }
                }
            }

            //this is the only way that everything is satisfied
            if(x == windowcount &&
               y == aislecount  &&
               z == rest.length)
            {
                placed = true;
            }
            else
            {
                x = 0;
                y = 0;
                z = 0;
                placed = false;
            }
        }
                    //the end result is that mask[index] = seat tells us to seat the index'th person
                    //in the reqs array in the seat rows[seat]
        if(placed)
        {
            for(int i=0;i<mask.length;i++)
            {
                String lname = tokend[i][0];
                String fname = tokend[i][1];
                String bday = tokend[i][2];
                boolean wind = false;
                boolean aisl = false;
                if(tokend[i].length > 3)
                {
                    wind = tokend[i][3].equals("W");
                    aisl = tokend[i][3].equals("A");
                }
                seats[mask[i]].seatPerson(lname, fname, bday, wind, aisl);
            }
            return true;
        }
        else
            return false;
    }