//ListMembers.java
//does all the hard work in the bicycle race simulation
//implements our bicycle race agents (the "agent" class does almost all the interesting
// simulation work; the agent.play routine incorporates the decision making heuristics and
// and agent.update_state() updates agent states after each turn;
//and implements spacers and terminal nodes on the linked list

//this whole program is implemented as a doubly linked list;  we add spacers between agents as gaps develop; and then swap elements of the list to allow motion.

// known sketchiness:  behavior of terminal nodes in reporting speeds, distances is perhaps not particularly smart and could cause problems if we changed the heuristics.

// people who are leading the race and run out of energy stop (by matching the speed of the non-rider in front of them) rather than slowing down normally (see the comment at the edgenode class definition)
// there appears to be a bugs in the leader heuristics:
//         -there may be something wrong with calculations of how much people are willing to sacrfice before they drop back from leading; it could be a rounding problem or could be a problem counting the number of people behind.

//Rob Letzler
//Leanne Ussher


import java.io.*;
import java.util.*;
import java.text.DecimalFormat;

//abstract class for members of the list -- this creates a template
//for what elements of the list know how to do and sets some default behaviors.
//individual subclasses redefine many of these functions
public abstract class ListMembers
	{
	    ListMembers prev_node, next_node;  //each node on the list has these links to the previous and next group members

	    public int get_speed ()  // house keeping nodes generally considered not moving; agents override this procedure
	    {
		return 0;
	    }



	    public ListMembers add_if_necessary () //all nodes except the tail return pointers to themselves; the tail returns a pointer to a new blank node
	    {
		return this;
	    }

	    public void play ()  // blanks and end_nodes just call the next mover's decision
	         {
	          next_node.play();
	         }

	    public void update_state ()  // blanks and end nodes have no state to update; they just call the next node; cyclist agents use this to calculate their energy level and otherwise update their states at the end of each round
	         {
	          next_node.update_state();
	         }

	    public void set_back_pointer(ListMembers new_prev) //used for swapping nodes in the list
	        {
		    prev_node = new_prev;
	        }

	    //	    public ListMembers get_own_pointer()
	    //	        {
	    //	    return this;
	    //    }

	    public void set_fwd_pointer(ListMembers new_fwd) //used for swapping nodes in the list
	        {
		    next_node = new_fwd;
	        }

	    public ListMembers get_next_pointer ()  //used for swapping nodes in the list
	    {
		return next_node;
	    }

	    public int num_of_ppl_behind_me_in_group ()
	    //terminal nodes and blanks use this to stop counting group members.
	    {
		return 0;
		    }



	    public int is_a_rider ()  //all nodes that are not rider agents return zero;
	    {
	    return 0;
	    }

	    // methods that subclasses redefine for doing calculations about the options
	    public abstract int dist_to_group_fwd();
	    public abstract int dist_to_group_back();
	    public abstract int get_speed_fwd();
	    public abstract int get_speed_back();

	    public abstract boolean print_energy();	    // returns whether there are more guys in the list.  a known bug:  the blank erasinglogic works on the wrong end of the list.
	    public abstract boolean print_ID();	    // returns whether there are more guys in the list.  a known bug:  the blank erasinglogic works on the wrong end of the list.
	    public abstract boolean print_speed();	    // returns whether there are more guys in the list.  a known bug:  the blank erasinglogic works on the wrong end of the list.
	    public abstract boolean print_comfort_speed();	    // returns whether there are more guys in the list.  a known bug:  the blank erasinglogic works on the wrong end of the list.
    			
	}


//agents are the bicycle riders;
//    this class's constructor "agent" creates them andendows them with random attributes
//    play defines their logic;
//    swap moves them forward in the list
//    update_state() updates their state after all players have made decisions that turn and
//    print_energy () / print_comfort_speed() / print_id()  print results at the end of each turn

class agent extends ListMembers
{
    int comfort_speed, //rider's speed at which he can move alone without losing energy 1-3
	speed,         //rider's speed this move; 1-5
	ID;            //rider's ID number -- ranges from 1 to number of agents (often 20)


    float 	energy, //rider's energy stock variable; how much energy do they currently have
	               //energy gets updated each turn in the update_state function
		energy_at_start_of_leading;  //rider's energy reference level which they use to determine when to stop leading.

    boolean played_this_turn = false;  //used to ensure that players do not play twice after rearranging the list; set true at the begining of decisions in play() and reset to false in update state
    boolean currently_leading = false; //used to determine whether to update energy ref state that tells leader when to drop back

    	
        //constructor:  sets initial random speed and energy endowment attributes
    public agent(int input_ID, ListMembers previous_node, int num_agents)
	    {  ID = input_ID;
                System.out.print(ID);

		    Random randomizer = new java.util.Random();
		    comfort_speed = randomizer.nextInt(3)+1;  //initialize random initial value of comfort speed to between 1 and 3; nextInt(X) returns a random integer between 0 and X-1.
		    energy = randomizer.nextInt(20)+1;   //initial random value of energy endowment

		    //initialize links to other nodes

		prev_node = previous_node;  //initialize pointer to previous node

		if (ID <  num_agents) //if we have not created all the agents, the next person in line should be a new agent
			      {next_node = new agent(ID+1, this, num_agents);}
		else {currently_leading = true;
		      next_node = new terminal_node(this);}  //if we're done, the next node is a terminal node
		}


    //implements heuristics for choosing moves;
    public void play ()
    {next_node.play();  //play begins with the leading rider; each trailing rider knows the next rider's choice before he chooses.
    if (!played_this_turn)  //if the line has been rearranged and I've already moved and been passed, this prevents moving again!
	    {
		played_this_turn  = true;  //set this to avoid running twice in a turn

		//begin heuristics

	    if (energy < 1)  	    //case:  if out of energy; then save energy
		{
		    if (next_node.get_speed() <= (comfort_speed + 1))
			{speed = next_node.get_speed();}
		    else if (comfort_speed > 1) {speed = comfort_speed - 1;}
		}
	    else if ((next_node.dist_to_group_fwd()> comfort_speed+1) && (prev_node.is_a_rider()==1)) //if leader then move at comf_speed + 1 unless I've used more than my fair share of energy in which case reduce speed.
		{
		    if ((energy_at_start_of_leading - energy) > energy_at_start_of_leading/prev_node.num_of_ppl_behind_me_in_group())
			{speed = comfort_speed;} // if I have used more than my fair share of energy leading that would keep us in steady state, slow down
		    else {speed  = comfort_speed + 1;} // otherwise go at optimal group speed
		}
	    else if (next_node.dist_to_group_fwd() <= comfort_speed +1) // if I'm a [potential] group member; move at group speed; note that the sequential logic means that the rider ahead will always open a gap; but I'm a group member if I can catch up with the guy this turn at group_comf_speed
		{speed = comfort_speed + 1;}
	    else if (next_node.is_a_rider() == 0 & prev_node.is_a_rider() == 0)  // case:  all alone:  then look for a good group to join ahead; failing that good group behind; failing that move at comfort speed.
		{
		    if ((next_node.dist_to_group_fwd() <= (energy+comfort_speed)) &  next_node.get_speed_fwd()<= (comfort_speed+1))
			{speed = 5;}
		    else if ((prev_node.get_speed_back() == comfort_speed) || (prev_node.get_speed_back() ==( comfort_speed + 1)))
		    {speed =  comfort_speed -1;}
			else speed = comfort_speed;
		}
	    else System.out.print("error:  no heuristic chosen!!" + dist_to_group_fwd() +prev_node.is_a_rider()); //if leader then move at comf_speed + 1 unless I've used more than my fair share of energy in which case reduce speed.);  //if we've gotten here, something's broken.  loner, follower, and leader should be mutally exclusive and exhaustive categories

	    //print out decisions to the console, 1 per line

	System.out.print(ID);
	System.out.print(" ");
	System.out.println(speed);

	// implements this rider's move by moving him speed units forward
		
	for (int i =1; i <= speed; i++)
	      {swap_forward();}
	
    	    }
    	}

    //this updates state variables for this player
    public void update_state ()
    {
	played_this_turn = false;  //allows the player to move again in the next turn

	if (leader()==1 & !currently_leading) //if I just became a leader
	    {currently_leading = true;       //start bookkeeping to enable me to decide when to drop back
	    energy_at_start_of_leading = energy;}

	if (leader() == 0) {currently_leading = false;}  //if I'm no longer a leader, reset bookkeeping

	energy += comfort_speed - speed + .5*leader()+1.2*next_node.is_a_rider();  //update energy state variable; add .5 if the person is a leader and 1.2 if there is a person ahead of me (which rules out being a leader, since I'm following someone)

	next_node.update_state();
    }


    //prints out results for this player

    public boolean print_energy()
    {		
	DecimalFormat one_place_fmt = new DecimalFormat("0.0");

	next_node.print_energy();  //moving this to the end would reverse the left to right order of print (which might be a good thing)


	//print data out; since we call this procedure recursively on the whole list of riders and blanks, this code repeatedly called will print one obs per rider in the current order of the list; one way to change the output would be to rewrite this section

	System.out.print(one_place_fmt.format(energy));
	System.out.print(" ");

	return true;  //blank nodes do not print anything unless there is an agent behind them
    }

    public boolean print_comfort_speed()
    {		
	next_node.print_comfort_speed();  //moving this to the end would reverse the left to right order of print (which might be a good thing)


	//print data out; since we call this procedure recursively on the whole list of riders and blanks, this code repeatedly called will print one obs per rider in the current order of the list; one way to change the output would be to rewrite this section

	System.out.print(comfort_speed);
	System.out.print(" ");

	return true;  //blank nodes do not print anything unless there is an agent behind them
    }

    public boolean print_ID()
    {		
	next_node.print_ID();  //moving this to the end would reverse the left to right order of print (which might be a good thing)


	//print data out; since we call this procedure recursively on the whole list of riders and blanks, this code repeatedly called will print one obs per rider in the current order of the list; one way to change the output would be to rewrite this section

	System.out.print(ID);
	System.out.print(" ");

	return true;  //blank nodes do not print anything unless there is an agent behind them
    }

    public boolean print_speed()
    {		
	next_node.print_speed();  //moving this to the end would reverse the left to right order of print (which might be a good thing)


	//print data out; since we call this procedure recursively on the whole list of riders and blanks, this code repeatedly called will print one obs per rider in the current order of the list; one way to change the output would be to rewrite this section

	System.out.print(speed+" ");

	return true;  //blank nodes do not print anything unless there is an agent behind them
    }

    private void swap_forward() //moves a rider 1 slot forward in the list
    {

	//If I'm against a terminal node, let it add a blank to swap backward and point my forward link at this new blank.
	next_node = next_node.add_if_necessary();

	ListMembers back_mover = next_node;  //move back blank forward

	ListMembers back_bookend = prev_node;  //bank of temporary variables for each of three other nodes involved in a swap
	ListMembers forward_mover = this;
	ListMembers front_bookend = next_node.get_next_pointer();

	//reset 6 links to reflect the swap from 1 2 3 4 to 1 3 2 4

	back_bookend.set_fwd_pointer (back_mover);
	front_bookend.set_back_pointer(forward_mover);
	back_mover.set_back_pointer(back_bookend);
	back_mover.set_fwd_pointer(forward_mover);
	prev_node = back_mover;
	next_node = front_bookend;
    }

    //the methods below access and calculate recursively values used in heuristics
    //other types of nodes -- like blanks and terminators have different versions of these functions
    public int speed () //reports the player's speed state
	    {		return speed;	    }

    public int num_of_ppl_behind_me_in_group() // this relies on polymorphism:  blanks and terminals will  return 0 and not recurse.
    {	return 1 + prev_node.num_of_ppl_behind_me_in_group();    }


    public int dist_to_group_fwd()
    {	return 0;    }

    public int dist_to_group_back()
    {	return 0;    }


    public int get_speed_fwd()  //foward and back need separate names b/c they're different in blank cells, which need to know where to look for the cell with the answer
    {	return speed;    }

    public int get_speed_back()
    {	return speed;    }


    private int leader() //return 1 if there's no one ahead, but someone behind; return zero otherwise
    {	return (1-next_node.is_a_rider())*prev_node.is_a_rider();    }

    public int is_a_rider ()  //does this node represent a rider?  blanks, and terminal nodes return zero
	{   return 1;	}

} //end of agent class


    // blanks represent spaces between riders
    // none exist at the beginning of the race; but the terminal node generates them as riders move ahead
class blank extends ListMembers
{

    //constructor; tracks nodes in front and behind
	public blank(ListMembers sent_prev_node, ListMembers sent_next_node)
	    {
		prev_node = sent_prev_node;
		next_node = sent_next_node;
	    }

    //a blank represents 1 unit of distance that is unoccupied by a rider / group.
public int dist_to_group_fwd()
    {
    return next_node.dist_to_group_fwd()+1;
    }
public int dist_to_group_back()
    {
    return prev_node.dist_to_group_back()+1;
    }

    //blanks are not moving, so this asks the next node how fast it is going
public int get_speed_fwd()
    {
    return next_node.get_speed_fwd();
    }

public int get_speed_back()
    {
    return prev_node.get_speed_back();
    }

    //prints a "_" to denote a blank; then calls the next node
public boolean print_energy()
    {		
	boolean another_agent_is_in_the_list = next_node.print_energy();
	if (another_agent_is_in_the_list)
	    {
		System.out.print("_");
		
	    }
	return another_agent_is_in_the_list;
    }

public boolean print_comfort_speed()
    {		
	boolean another_agent_is_in_the_list = next_node.print_comfort_speed();
	if (another_agent_is_in_the_list)
	    {
		System.out.print("_");
		
	    }
	return another_agent_is_in_the_list;
    }

public boolean print_ID()
    {		
	boolean another_agent_is_in_the_list = next_node.print_ID();
	if (another_agent_is_in_the_list)
	    {
		System.out.print("_");
		
	    }
	return another_agent_is_in_the_list;
    }

public boolean print_speed()
    {		
	
	boolean another_agent_is_in_the_list = next_node.print_speed();
	if (another_agent_is_in_the_list)
	    {
		System.out.print("_");
		
	    }
	return another_agent_is_in_the_list;
    }
}  //end class blank


//this abstract class specifies the shared behaviors of the first and last nodes on the list
//I'm not sure if their speed and dist_to_group responses are the smartest possible approaches.
//they lead to one known quirk:  people who are leading the race and run out of energy stop
//rather than dropping to a more normal speed.  we could handle this as a special case in play


abstract class EdgeNode extends ListMembers
{


public int dist_to_group_fwd()
    {
	return 10000;
    }
public int dist_to_group_back()
    {
	return 10000;
    }


public int get_speed_fwd()
    {
    return -1;
    }

public int get_speed_back()
    {
    return -1;
    }

}  // end class edge_node

//specifies behavior of the last node on the list (Next.next.NEXT....)
class terminal_node extends EdgeNode
{
    public terminal_node(ListMembers prev)
            {
		System.out.println();
	    prev_node = prev;
	    //by definition, there is no next node
	    }


    //if someone swaps with this node, it adds a new blank node
    //not sure this is the cleanest solution -- may instead want swap to pass the moved node to the next node.
    public ListMembers add_if_necessary ()
    {
	ListMembers newBlankCell = new blank (prev_node, this);
	prev_node = newBlankCell;
	return newBlankCell;
    }

    public ListMembers get_next_pointer ()
    {
	System.err.println("Tried to get next pointer on end of list!");
	return null;
    }

public boolean print_energy()
    {		
	return false;
    }

public void play()
   {
       //play does nothing and thus ends recursion
   }

public void update_state()
    {
	//end recursion
    }

public boolean print_ID()
    {		

	return false;
    }

public boolean print_speed()
    {		

	return false;
    }

public boolean print_comfort_speed()
    {		
	return false;
    }


}  // end class terminal_node

//this is the node at the begining of the list; the node previous to all other nodes
//it gets created first and then tells the appropriate number of agents
//to create themselves and a terminal node
//it also begins play (throught the default play() defined in ListMembers) and orders printing

class front_node extends EdgeNode
{
    public front_node(int num_players)
	{
	    next_node = new agent(1, this, num_players);
	}



public boolean print_energy()
    {		
	boolean temp = next_node.print_energy();
	System.out.println();
	return temp;
    }

public boolean print_ID()
    {		
	boolean temp = next_node.print_ID();
	System.out.println();
	return temp;
    }

public boolean print_speed()
    {		
	boolean temp = next_node.print_speed();
	System.out.println();
	return temp;
    }

public boolean print_comfort_speed()
    {		
	boolean temp = next_node.print_comfort_speed();
	System.out.println();
	return temp;
    }
} // end class front_node