void SLList::Insert(int data)
{  
  
  SLNode* insert = new SLNode(data); //assigns data to new node 
  SLNode* current = head_; //assigns head to current
  SLNode* prev = current;
  if(!head_ || data <= current->contents()) //if there is a list or data is less than or equal to head_                                                          
  {
    InsertHead(data); 
  }
  else if(data > tail_->contents()) //if data is greater than tail
  {
    InsertTail(data);
  }
  else
  {
  while(current->contents()  < data) //while current is less than data
  {
    prev = current; //we assign prev to currents position
    current = current->next_node(); //then assign current to next position
  }
  insert->set_next_node(current); //set node at currents position
  prev->set_next_node(insert); //set data at proper position
  size_++;
  }
}

//New node addition to list
    void SList::insertHead(int newNodeContent){
        SLNode *n;
        n = new SLNode;
        n->setNextNode(NULL);
        n->setContents(newNodeContent);
        n->setNextNode(head);
        head = n;
        
        //SLNode *n = new SLNode();
        //n->setContents(newNodeContent);
        //n->setNextNode(head);
        //head = n;
        
        size++;
    }

/*!
SLGroup::buildAABB() loops over all child nodes and merges their AABB
to the axis aligned bounding box of the group.
*/
SLAABBox& SLGroup::buildAABB()
{  SLNode* current = _first;
   
   // empty the groups AABB    
   _aabb.minWS(SLVec3f( FLT_MAX, FLT_MAX, FLT_MAX));
   _aabb.maxWS(SLVec3f(-FLT_MAX,-FLT_MAX,-FLT_MAX));

   while (current)
   {  _aabb.merge(current->buildAABB());
      current = current->next();
   }
   
   _aabb.fromWStoOS(_aabb.minWS(), _aabb.maxWS(), _wmI);
   return _aabb;
}

string SList::toString() const {
    stringstream ss;
    if (head == NULL) {
        ss.str("");
    } else {
        int i = 1;
        for (SLNode* n = head; n != NULL; n = n->getNextNode()) {
            ss << n->getContents();
            if  (i < size)
                ss << ",";
            i++;
        }
    }
    return ss.str();
}

/*!
SLGroup::shapeInit loops over all child nodes and calls their init method with
an incremented depth. While looping it must be checked that all child nodes
have a depth equal the groups depth + 1.
*/
void SLGroup::shapeInit(SLSceneView* sv)
{  SLNode* current = _first;
   while (current)
   {  if (current->depth() && current->depth() != depth()+1) 
      {  SL_EXIT_MSG("Scenegraph is not directed acyclic. There is a loop.");
      }
      current->init(sv, depth()+1);
      
      // Set transparent flags of the group
      if (!_aabb.hasAlpha() && ((SLShape*)current)->aabb()->hasAlpha())
         _aabb.hasAlpha(true); 
         
      current = current->next();
   }
}

Object* SLQueue::dequeue() {
	if (isEmpty())
		return NULL;

	SLNode* rem = head;
	head = head->getNext();
	Object* retval = rem->getData();

	rem->setData(NULL);
	rem->setNext(NULL);
	delete rem;

	size--;
	return retval;
}

void SList::insertTail (int contents) {
	if (head == NULL) {
		insertHead(contents);
	}
	else {
		SLNode* i = head;
		SLNode* newNode = new SLNode(contents);
		
		while (i->getNextNode() != NULL) {
			i = i->getNextNode();
		}
		i->setNextNode(newNode);
		++numNodes;
	}
}

SLNode* SList::getTail() const {
	SLNode* currentNode = mHead;
	
	if(currentNode != 0) {
		while(true) {
			SLNode* const nextNode = currentNode->getNextNode();
			if(nextNode == 0) {
				return currentNode;
			}
			
			currentNode = nextNode;
		}
	}
	
	return currentNode;
}

string SList::toString () const {
	stringstream listStream;
	SLNode* current;
	current = head;
	
	if (head == NULL){
		cout << "" << endl;
	} else {
		while (current != NULL) {
			listStream << current->getContents() << ",";
			current = current->getNextNode();
		}
	}
	
	return(listStream.str().substr(0,listStream.str().length() - 1));
}

/*!
SLGroup::intersect loops over all child nodes of the group and calls their
intersect method.  
*/
SLbool SLGroup::shapeHit(SLRay* ray)
{  assert(ray != 0);

   SLNode* current = _first;
   SLbool wasHit = false;
   while (current)
   {  
      // do not test origin node for shadow rays 
      if (!(current==ray->originShape && ray->type==SHADOW))
      {  if (current->hit(ray) && !wasHit) wasHit = true;
      }
      
      if (ray->isShaded()) return true;
      current = current->next();
   }
   return wasHit;
}

/**
 * returns a string representation of the contents
 * of all nodes in the list, in the format
 * NUM1, NUM2, ..., LASTNUM
 * returns the empty string on an empty list (i.e. returns "")
 */
string SLList::ToString() const
{
    if (head_ == NULL)
    return "";
    stringstream ss;
        SLNode* temp = head_;
        
            while (temp != NULL)
            {
                ss << temp->contents();
                if (temp->next_node() != NULL)
                ss << ", ";
                temp = temp->next_node();
            }
    
    
    return ss.str();
}

void SList::removeTail () {
    if(head == NULL){
    
    }
    else if (head->getNextNode()==NULL) {
        removeHead();
    } else {
    SLNode* i = head;
    SLNode* j=NULL;
    while (i->getNextNode() !=NULL) {
        j=i;
        i=i->getNextNode();
    }
    delete i;
    j->setNextNode(NULL);
size--;
         }
}

void SList::removeTail () {
	if (head != NULL) {
		if (head->getNextNode() == NULL) {
			delete head;
			head = NULL;
		} else {
			SLNode* nextToTail = head;
			SLNode* tail = head->getNextNode();
				while (tail->getNextNode() != NULL) {
					nextToTail = tail;
					tail = tail->getNextNode();
				}
			delete tail;
			nextToTail->setNextNode(NULL);
		}
		size--;
	}
}

void SList::insertTail (int newContents)
{
    SLNode* newNode = new SLNode(newContents);
    SLNode* temp = head;
    if(head == NULL)
    {
        head = newNode;
    }
    else
    {
        while(temp->getNextNode() != NULL)
        {
            temp = temp -> getNextNode();
        }
        temp -> setNextNode(newNode);
    }
    size++;
}

void SList::insertTail(int value)
{
    if(head == NULL)
    {
        insertHead(value);
    }
    else
    {
        SLNode* newNode = new SLNode(value);
        SLNode* temp = head;
        while(temp->getNextNode() != NULL)
        {
            temp = temp->getNextNode();
        }
        temp->setNextNode(newNode);
        size++;
    }
}// create a new SLNode and attach at the end of list

void SList::removeTail () {
	if (head != NULL) {
		SLNode* i = head;
		SLNode* trailer = NULL;
		
		while (i->getNextNode() != NULL) {
			trailer = i;
			i = i->getNextNode();
		}
		delete i;
		--numNodes;
		if (trailer == NULL) {
			head = NULL;
		}
		else {
			trailer->setNextNode(NULL);
		}
	}
}

string SList::toString()
{
    stringstream list;
    SLNode* temp = head;
    if(head == NULL)
    {
        return list.str();
    }
    else
    {
        while(temp->getNextNode() != NULL)
        {
            list << temp->getContents() << ",";
            temp = temp->getNextNode();
        }
        list << temp->getContents();
    }
    return list.str();
}

void SList::insertTail (int contents){
     
	if(head != NULL) {
		//Finds the tail. 
		SLNode* i = head;
		while (i->getNextNode() != NULL) {
			//Starts at head and moves it over to the last node. 
			i = i->getNextNode();
		}
		SLNode* node = new SLNode(contents);
		//points at the end and inserts the new node that was just created. 
		i->setNextNode(node);
		size++;
	} else {
		//Empty list - make it to insert head as it's the same thing. 
		insertHead(contents);
	}
 
}

/*! 
Copies the nodes meshes and children recursively.
*/ 
SLNode* SLNode::copyRec()
{
    SLNode* copy = new SLNode(name());
    copy->_om = _om;
    copy->_depth = _depth;
    copy->_isAABBUpToDate = _isAABBUpToDate;
    copy->_isAABBUpToDate = _isWMUpToDate;
    copy->_drawBits = _drawBits;
    copy->_aabb = _aabb;

    if (_animation) 
         copy->_animation = new SLAnimation(*_animation);
    else copy->_animation = 0;

    for (auto mesh : _meshes) copy->addMesh(mesh);
    for (auto child : _children) copy->addChild(child->copyRec());
   
    return copy;
}

/**
 * removes the tail node from the list,
 * or does nothing if the list is empty
 */
void SLList::RemoveTail()
{
    if (head_ != NULL)
    {
         if (head_ == tail_)
         {
             RemoveHead();
         } else 
         {
             SLNode* temp = head_;
             while (temp->next_node() != tail_)
             temp = temp->next_node();
             temp->set_next_node(NULL);
             delete tail_;
             tail_ = temp;
             size_ -= 1;
         }
    }
}