Skip to content

Instantly share code, notes, and snippets.

@eqdw
Created January 11, 2010 00:13
Show Gist options
  • Save eqdw/273878 to your computer and use it in GitHub Desktop.
Save eqdw/273878 to your computer and use it in GitHub Desktop.
//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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment