/*expand(node input) this function takes a node and it expands it, by
 *that we mean that it finds where the zero element is and then 
 *it tries to see if it can move up, down, left and right. If so 
 *then it adds all these nodes into the templist list.
 */
void Astar::expand(node &input){
  cout << "We are in the expanding function. " << endl;
  node tempn;
  list<node> templist;
  input.find_zero();
  if ( input.can_move_up() ){
    tempn = input;
    tempn.move_up();
    tempn.inc_g();
    tempn.create_state(goal);
    templist.push_back(tempn);}
  if ( input.can_move_right() ){
    tempn = input;
    tempn.move_right();
    tempn.inc_g();
    tempn.create_state(goal);
    templist.push_back(tempn);}
  if ( input.can_move_bottom() ){
    tempn = input;
    tempn.move_bottom();
    tempn.inc_g();
    tempn.create_state(goal);
    templist.push_back(tempn);}
  if ( input.can_move_left() ){
    tempn = input;
    tempn.move_left();
    tempn.inc_g();
    tempn.create_state(goal);
    templist.push_back(tempn);}
  //let's print the templist elements
  print_list(templist,"Temporary");
  //let's add the nodes we just created into the openlist
  add_expanded(templist,input);
  //  add_expanded(tempq,input);}
}

  void build_tree(int L, int R) {
    if(L == R) return;

    int mid = (L + R)/2;
    left = new node(); left->build_tree(L, mid);
    right = new node(); right->build_tree(mid + 1, R);
  }

	void update(int x, ll v) {
		int m = (s+e)/2;
		if (s == e) val = v;
		else {
			if (x > m) {
				if (r == NULL) r = new node(x, x);
				else if (!r->inrange(x)) {
					node* tmp = r;
					pi nxt = lca(s, e, r->s, r->e, x);
					r = new node(nxt.first, nxt.second);
					if (tmp->e <= (r->s + r->e)/2 ) r->l = tmp;
					else r->r = tmp;
				}
				r->update(x, v);
			}
			else {
				if (l == NULL) l = new node(x, x);
				else if (!l->inrange(x)) {
					node* tmp = l;
					pi nxt = lca(s, e, l->s, l->e, x);
					l = new node(nxt.first, nxt.second);
					if (tmp->e <= (l->s + l->e)/2 ) l->l = tmp;
					else l->r = tmp;
				}
				l->update(x, v);
			}
			val = 0;
			if (l != NULL) val = __gcd(l->val, val);
			if (r != NULL) val = __gcd(r->val, val);
		}
	}

bool LocalBiconnectedMerger::canMerge( Graph &G, node parent, node mergePartner, int testStrength )
{
	if ( parent->degree() <= 2 || mergePartner->degree() <= 2 || m_isCut[parent] || m_isCut[mergePartner] ) {
		return true;
	}

	unsigned int nodeLimit = (int)log((double)G.numberOfNodes()) * 2 + 50;
	unsigned int visitedNodes = 0;
	m_realNodeMarks.clear();
	HashArray<node, int> nodeMark(-1);

	HashArray<node, bool> seen(false);
	seen[parent] = true;
	seen[mergePartner] = true;

	HashArray<node, int> neighborStatus(0);
	neighborStatus[parent] = -1;
	neighborStatus[mergePartner] = -1;

	List<node> bfsQueue;
	List<node> neighbors;
	int minIndex = numeric_limits<int>::max();
	adjEntry adj;
	forall_adj(adj, parent) {
		node temp = adj->twinNode();
		bfsQueue.pushBack(temp);
		nodeMark[temp] = temp->index();
		if(neighborStatus[temp] == 0) {
			neighbors.pushBack(temp);
			neighborStatus[temp] = 1;
			if (temp->index() < minIndex) {
				minIndex = temp->index();
			}
		}
	}

//insert a copy for original node v
void SimpleIncNodeInserter::insertCopyNode(node v, Graph::NodeType vTyp)
{
	OGDF_ASSERT(m_planRep->copy(v) == 0)

	//insert a new node copy
	node vCopy = m_planRep->newCopy(v, vTyp);
	if (v->degree() == 0) return;
	//insert all adjacent edges to already inserted nodes
	adjEntry adjOrig = v->firstAdj();
	do
	{
		node wOrig = adjOrig->twinNode();
		node wCopy = m_planRep->copy(wOrig);
		edge e = adjOrig->theEdge();
		if (wCopy && (m_planRep->chain(e).size() == 0))
		{
			//inserted edge copy
			//edge eCopy;
			//newCopy can cope with zero value for adjEntry
			if (v == e->source())
				/* eCopy = */ m_planRep->newCopy(vCopy, wCopy->firstAdj(), e);
			else
				/* eCopy = */ m_planRep->newCopy(wCopy, vCopy->firstAdj(), e);

			//TODO: update component number in planrepinc

		}//if edge to be inserted
		adjOrig = adjOrig->cyclicSucc();
	} while (adjOrig != v->firstAdj());
}//insertCopyNode

void include_file(node<Interface>& n)
{
    if (oven::equals(n.name(), pstade::ustring("include"))) {
        std::string path = oven::sequence_cast<std::string>(n.att("href"));
        lime::load_file(n, path);
    }
}

    bool reservation(int from, int to, int num) {
        if (flag) {
            free -= flag;
            if (!leaf) {
                left->add_flag(flag);
                right->add_flag(flag);
            }
            flag = 0;
        }

        if (f == from && t == to) {
            if (free >= num)
                return true;
            return false;
        }

        bool left_node = true, right_node = true;
        if (left->t > from) {
            int left_t = left->t < to ? left->t : to;
            left_node = left->reservation(from, left_t, num);
        }
        if (right->f < to) {
            int right_f = right->f > from ? right->f : from;
            right_node = right->reservation(right_f, to, num);
        }

        return (left_node && right_node);
    }

bool node::operator<(const node& n) const
{
	if(type() != n.type()) {
		return type_ < n.type();
	}
	switch(type()) {
	case NODE_TYPE_NULL:
		return true;
	case NODE_TYPE_BOOL:
		return b_ < n.b_;
	case NODE_TYPE_INTEGER:
		return i_ < n.i_;
	case NODE_TYPE_FLOAT:
		return f_ < n.f_;
	case NODE_TYPE_STRING:
		return s_ < n.s_;
	case NODE_TYPE_MAP:
		return m_.size() < n.m_.size();
	case NODE_TYPE_LIST:
		for(unsigned i = 0; i != l_.size() && i != n.l_.size(); ++i) {
			if(l_[i] < n.l_[i]) {
				return true;
			} else if(l_[i] > n.l_[i]) {
				return false;
			}
		}
		return l_.size() < n.l_.size();
	case NODE_TYPE_FUNCTION:
	default: break;
	}
	ASSERT_LOG(false, "operator< unknown type: " << type_as_string());
	return false;
}

	maplayer::maplayer(node source)
	{
		node tilesrc = nx::nodes["Map"]["Tile"][source["info"]["tS"] + ".img"];
		node objsrc = nx::nodes["Map"]["Obj"];
		for (node layernode = source.begin(); layernode != source.end(); layernode++)
		{
			if (layernode.name() == "obj")
			{
				for (node objnode = layernode.begin(); objnode != layernode.end(); ++objnode)
				{
					vector2d position = vector2d(objnode["x"], objnode["y"]);
					node bmpnode = objsrc[objnode["oS"] + ".img"][objnode["l0"]][objnode["l1"]][objnode["l2"]];
					int z = objnode["z"];
					objs[z].push_back(sprite(animation(bmpnode), position, true, objnode.resolve("f").get_bool()));
				}
			}
			else if (layernode.name() == "tile")
			{
				for (node tilenode = layernode.begin(); tilenode != layernode.end(); ++tilenode)
				{
					node bmpnode = tilesrc[tilenode["u"]][to_string(tilenode["no"].get_integer())];

					tile toadd;
					toadd.pos = vector2d(tilenode["x"], tilenode["y"]);
					toadd.txt = texture(bmpnode);
					int z = bmpnode["z"].istype(integernode) ? bmpnode["z"] : tilenode["zM"];

					tiles[z].push_back(toadd);
				}
			}
		}

	}

		int inserting(node* element, tree<T, Ref>* structure){
			if(element->key <= this->key){
				if(ptrleft){
					level_left = 1 + ptrleft->inserting(element, structure);
				} // Inclui a esquerda
				else{
					ptrleft = element;
					element->ptrtop = this;
					level_left = 1;
				} // Insere a esquerda
			}
			else{
				if(ptrright){
					level_right = 1 + ptrright->inserting(element, structure);
				} // Inclui a direita
				else{
					ptrright = element;
					element->ptrtop = this;
					level_right = 1;
				} // Insere a direita
			}
			if(level_left - level_right > 1){
				return ptrleft->leftrotate(structure);
			} // Avalia se é necessário efetuar uma rotação a esquerda
			if(level_right - level_left > 1){
				return ptrright->rightrotate(structure);
			} // Avalia se é necessário efetuar uma rotação a direita
			if (level_right > level_left){return level_right;}
			else {return level_left;}
		}

	template < typename...Args > void emplace_back(Args && ... args)
	{
		node *newdat = new node(mBack.backward(), new T(args...), &mBack);
		mBack.backward()->forward(newdat);
		mBack.backward(newdat);
		++mSize;
	}

	template < typename...Args > void emplace_front(Args && ... args)
	{
		node *newdat = new node(&mFront, new T(args...), mFront.forward());
		mFront.forward()->backward(newdat);
		mFront.forward(newdat);
		++mSize;
	}

	void push_back(const T & dat)
	{
		node *newdat = new node(mBack.backward(), new T(dat), &mBack);
		mBack.backward()->forward(newdat);
		mBack.backward(newdat);
		++mSize;
	}

/**
 * @brief Reconnect the edge e to have the new given ends
 */
void GraphStorage::setEnds(const edge e, const node newSrc, const node newTgt) {
  assert(isElement(e));
  std::pair<node, node>& eEnds = edges[e.id];
  node src = eEnds.first;
  node tgt = eEnds.second;

  // nothing to do if same ends
  if (src == newSrc && tgt == newTgt)
    return;

  node nSrc = newSrc;
  node nTgt = newTgt;

  if (newSrc.isValid() && src != newSrc) {
    assert(isElement(newSrc));
    eEnds.first  = newSrc;
    EdgeContainer& sCtnr = nodes[src.id];
    EdgeContainer& nCtnr = nodes[newSrc.id];
    sCtnr.outDegree -= 1;
    nCtnr.outDegree += 1;
    nCtnr.edges.push_back(e);
    removeFromEdgeContainer(sCtnr, e);
  }
  else
    nSrc = src;

  if (newTgt.isValid() && tgt != newTgt) {
    assert(isElement(newTgt));
    eEnds.second = newTgt;
    nodes[newTgt.id].edges.push_back(e);
    removeFromEdgeContainer(nodes[tgt.id], e);
  }
  else
    nTgt = tgt;
}

	void push_front(const T & dat)
	{
		node *newdat = new node(&mFront, new T(dat), mFront.forward());
		mFront.forward()->backward(newdat);
		mFront.forward(newdat);
		++mSize;
	}

/** Checks wheter a path from source to target
 *  does exist by traversing the graph.
 */
bool pathExists(const Graph &graph, const node source, const node target)
{
	OGDF_ASSERT(source != target);
	OGDF_ASSERT(source->graphOf() == &graph);
	OGDF_ASSERT(target->graphOf() == &graph);

	List<node> queue;
	NodeArray<bool> visited(graph, false);
	visited[source] = true;
	queue.pushBack(source);

	bool result = false;
	while(!queue.empty() && !result) {
		node v = queue.popFrontRet();
		for(adjEntry adj : v->adjEntries) {
			node w = adj->theEdge()->target();
			if(!visited[w]) {
				result |= w == target;
				visited[w] = true;
				queue.pushBack(w);
			}
		}
	}

	return result;
}

	node* clone() {
		node* t = new node(s, e);
		t->val = val;
		if (l != NULL) t->l = l->clone();
		if (r != NULL) t->r = r->clone();
		return t;
	}

pathfinder::const_iterator::const_iterator (pathfinder& _pf, node n) : 
	pf (_pf) 
{
    if (!pf.back[n].empty()) {
	edge back = pf.back[n].front();
	curr = n.opposite (back);
	pf.used[curr] = 1;
	pf.back[n].pop_front();
	pf.forward[curr].erase (pf.pos[back].first);
	state = END;
		
    } else if (!pf.tree[n].empty()) {
	curr = n.opposite (pf.tree[n].front());
	pf.used[curr] = 1;
	pf.tree[n].pop_front();
	state = DOWN;
		
    } else if (!pf.forward[n].empty()) {
	edge forward = pf.forward[n].front();
	curr = n.opposite (forward);
	pf.forward[n].pop_front();
	pf.back[curr].erase (pf.pos[forward].second); 
		
	if (pf.used[curr]) {
	    state = END;
	} else {
	    pf.used[curr] = 1;
	    state = UP;
	}
    }
}

	rod(node d1,node d2,float EA=1){
		nodes.first=d1;
		nodes.second=d2;
		fi = d1.angle(d2);
		
		float l=d1.dist(d2);
		float EAl=EA/l;
		float c = cos(fi) * pow(EAl,0.5);
		float s = sin(fi) * pow(EAl,0.5);
		
		k[0][0] = c*c;
		k[0][1] = s*c;
		k[0][2] = -c*c;
		k[0][3] = -c*s;

		k[1][0] = c*s;
		k[1][1] = s*s;
		k[1][2] = -c*c;
		k[1][3] = -s*s;
		
		k[2][0] = -c*c;
		k[2][1] = -c*s;
		k[2][2] = c*c;
		k[2][3] = c*s;
		
		k[3][0] = -c*s;
		k[3][1] = -s*s;
		k[3][2] = c*c;
		k[3][3] = s*s;
	}

std::size_t node_hasher::hash(const node& v) {
    std::size_t seed(0);

    combine(seed, v.content());
    combine(seed, hash_std_list_neurite_swc_node(v.children()));

    return seed;
}