void Floyd::calculate_APSP()
{
  int i, j, k;
  int dest_Rank = 0, curr_Done = 0;

  for (k = 0; k < nodes; k++, curr_Done++)
  {
    int tq = nodes / num_Proc + ((nodes - num_Proc * (nodes / num_Proc)) > dest_Rank);
    if (tq == curr_Done)
    {
      curr_Done = 0;
      dest_Rank++;
    }

    if (dest_Rank == global_Rank)
      MPI_Bcast(&(local_Matrix[k % q][0]), nodes, MPI_INT, dest_Rank, MPI_COMM_WORLD);
    else
      MPI_Bcast(&(local_Matrix_K[0]), nodes, MPI_INT, dest_Rank, MPI_COMM_WORLD);

    for (i = 0; i < q; i++)
      for (j = 0; j < nodes; j++)
        if (dest_Rank == global_Rank)
          relax(local_Matrix[i][j], local_Matrix[i][k], local_Matrix[k % q][j]);
        else
          relax(local_Matrix[i][j], local_Matrix[i][k], local_Matrix_K[j]);
  }
}

/* ------ WRITER ------ */
void writer_lock(rw_lock* rw)
{
    int success = 0;   // local var
    int mytid = nf_tid();
   
    while(!success)
    {
        while(rw->writer_pending && (mytid != rw->writer_id))
	  relax();
        while(rw->reader_cnt || rw->writing)
	  relax();
       
        nf_lock(rw->lock);
            if(!(rw->writer_pending)) {
                rw->writer_pending = 1;
                rw->writer_id = mytid;
            }
            if(!(rw->reader_cnt || rw->writing))
            {
                   rw->writing = 1;
                   success = 1;
            }
        nf_unlock(rw->lock);
    }
}

/*
   Funcao que implementa o algoritmo Bellman-Ford
        Recebe um array de vertices (um grafo)
        Recebe um inteiro que indica o numero de vertices existentes
*/
void BellmanFord(vertex graph, int max_vertex) {
    int i, v, changed;
    link adj;
    for (i = 1; i < max_vertex - 1; i++) {
        changed = 0;
        for (v = 0; v < max_vertex; v++) {
            if (graph[v].change != 1) {
                for (adj = graph[v].edges -> begin; adj != NULL; adj = adj -> next) {
                    relax(graph[v], adj -> vertex, adj);
                    changed = 1;
                }
                graph[v].change = 1;
            }
        }
        if (changed == 0) {break;}
    }
    for (v = 0; v < max_vertex; v++) {
        for (adj = graph[v].edges -> begin; adj != NULL; adj = adj -> next) {
            if ((relax(graph[v], adj -> vertex, adj) == 1) && (graph[v].cycle != 1)) {
                    graph[v].cycle = 1;
                    BFS(graph, graph + v);
            }
        }
    }
}

void split( int root, int div, int*L, int*R ){
    push( root );
    if( root == 0 ) {
       *R = *L = 0;
        return;
    }
    if( div == 0 ) {
       *L = 0;
       *R = root;
        relax( root );
        return;
    }
    if( ar[ar[root].l].sz >= div ) {
        split( ar[root].l, div, L, R );
        ar[root].l = *R;
       *R = root;
        relax( *R );
        relax( *L );
    } 
    else {
        split( ar[root].r, div - ar[ar[root].l].sz - 1, L, R );
        ar[root].r = *L;
       *L = root;
        relax( *L );
        relax( *R );
    }
}

int bellman_ford(struct Matrix_Graph *mat_graph, \
				struct Point_Graph *poi_graph, int source)
{
	int i, j;
	struct Edge *edge;

	for (i = 0; i < poi_graph->node_num; i++)
		for (j = 0; j < poi_graph->node_num; j++) {
			edge = poi_graph->node[j].start;
			if (mat_graph->shortest_matrix[source][j] == INT_MAX)
				continue;
			while (edge) {
				relax(mat_graph, source, j, edge);
				edge = edge->next;
			}
		}

	for (j = 0; j <= poi_graph->node_num; j++) {
		edge = poi_graph->node[j].start;
		while (edge) {
			if (relax(mat_graph, source, j, edge) != -1)
				return 0;
			edge = edge->next;
		}
	}
	return 1;
}

Node* insert(Node* t, Node* m) {
    if (t == null || m->y > t->y) {
        split(t, m->x, m->l, m->r);
        return relax(m);
    }
    if (m->x < t->x) t->l = insert(t->l, m);
    else t->r = insert(t->r, m);
    return relax(t);
}

// Inserts node m at position x (0-based)
Node* insert(Node* t, Node* m, int x) {
    if (t == null || m->y > t->y) {
        split(t, x - 1, m->l, m->r);
        return relax(m);
    }
    // apply lazy propagation here to t
    propagate(t);
    if (x <= leftCount(t)) t->l = insert(t->l, m, x);
    else t->r = insert(t->r, m, x - 1 - leftCount(t));
    return relax(t);
}

// Puts all elements <= x in l and all elements > x in r.
void split(Node* t, int x, Node* &l, Node* &r) {
    if (t == null) l = r = null; else {
        if (t->x <= x) {
            split(t->r, x, t->r, r);
            l = relax(t);
        } else {
            split(t->l, x, l, t->l);
            r = relax(t);
        }
    }
}

Node* merge(Node* l, Node *r) {
    if (l == null) return relax(r);
    if (r == null) return relax(l);
    if (l->y > r->y) {
        l->r = merge(l->r, r);
        return relax(l);
    } else {
        r->l = merge(l, r->l);
        return relax(r);
    }
}

Node* erase(Node* t, int x) {
    if (t == null) return null;
    if (t->x == x) {
        Node *q = merge(t->l, t->r);
        delete t;
        return relax(q);
    } else {
        if (x < t->x) t->l = erase(t->l, x);
        else t->r = erase(t->r, x);
        return relax(t);
    }
}

void mgrid::LinearMultigrid::multigrid() {
    // Check that source array has been set  
    if (not(sourceIsSet)) return;
    
    // Constants
    const Level finestLevel = solution.finestLevel;
    const Level coarsestLevel = solution.coarsestLevel;
    
    // Initialise right-hand-side
    for (Level level=finestLevel; level>0; level--) {
        source.coarsen(level);     
        solution.coarsen(level);
    }

    // Solve on coarsest level
    relax(coarsestLevel, residualTolerance);

    // Full Multigrid loop
    for (Level fineLevel=1; fineLevel<=finestLevel; fineLevel++) {
        // V-cycle loop at each (successively finer) level
        solution.refine(fineLevel-1); // interpolate to next level    
        for (int cycle=0; cycle < cycleType; cycle++) {
            // Downstroke of cycle:    
            //  -- New residual: r(2h) = 0 (see note below)
            //  -- New rhs: f(2h) = R.f(h) - L.u(2h)    
            // Note that each sucessive level in the downstroke is calculating
            // a _residual_, not a coarser version of the solution. Each level
            // therefore needs to be set to zero on the way down.
            for (Level level=fineLevel; level>0; level--) {
                relax(level, preRelax);
                evaluate_residual(level, temp[level]); 
                temp.coarsen(level, source[level-1]);     
                solution[level-1] = 0; // initialise next level's residual
            }

            // Solve problem on coarsest level    
            relax(coarsestLevel, residualTolerance);

            // Upstroke of cycle:
            // -- Correction: u(h) <- u(h) + I.u(2h)
            for (Level level=1; level<=fineLevel; level++) {
                solution.refine(level-1, temp[level]);     
                solution[level] += temp[level];
                relax(level, postRelax); 
            } 
        }
    } 
    
    // Do final update 
    relax(finestLevel, postRelax);
    solution[finestLevel].update_boundaries();
}

void split(Node* t, int x, Node* &l, Node* &r) {
    if (t == null) l = r = null; else {
        // apply lazy propagation here to t
        propagate(t);
        if ( x < leftCount(t) ) {
            split(t->l, x, l, t->l);
            r = relax(t);
        } else {
            split(t->r, x - 1 - leftCount(t), t->r, r);
            l = relax(t);
        }
    }
}

Node* erase(Node* t, int x) {
    if (t == null) return null;
    // apply lazy propagation here to t
    propagate(t);
    if (leftCount(t) == x) {
        Node *q = merge(t->l, t->r);
        delete t;
        return relax(q);
    } else {
        if (x < leftCount(t)) t->l = erase(t->l, x);
        else t->r = erase(t->r, x - 1 - leftCount(t));
        return relax(t);
    }
}

/**
 * Wait a selected number of timer tick
 */
void timer_wait(uint_fast32_t ticks)
{
  uint_fast32_t cur_tick = timer_ticks;
  uint_fast32_t end_tick = cur_tick + ticks;
  
  /* Handle overflow at the 2147483648:th
     (slightly below 25 days at 1000 hz) tick! */
  if (unlikely(end_tick < cur_tick))
    while (timer_ticks >= cur_tick)
      relax();
  
  while (timer_ticks < end_tick)
    relax();
}

int merge( int L, int R ) {
    push( L );
    push( R );
    if( L == 0 ) return R;
    if( R == 0 ) return L;
    if( ar[L].y < ar[R].y ) {
        ar[L].r = merge( ar[L].r, R );
        relax( L );
        return L;
    } else {
        ar[R].l = merge( L, ar[R].l );
        relax( R );
        return R;
    }
}

BellmanFordSP::BellmanFordSP(const EWDiGraph& graph, int source) : distances(graph.getVertexCount(), std::numeric_limits<double>::max()),
edges(graph.getVertexCount(), Edge(0, 0, 0.0))
{
	std::queue<int> considerVertecies;
	for (int i = 0; i < graph.getVertexCount(); i++)
	{
		considerVertecies.push(i);
	}
	distances[source] = 0.0;
	for (int i = 0; i < graph.getVertexCount(); i++)
	{
		std::queue<int> nextPassVertecies;
		while (!considerVertecies.empty())
		{
			if (i == graph.getVertexCount() - 1)
				findNegativeCycle(considerVertecies.front());
			EWDiGraph::EdgesList adjacent = graph.getAdjacentVertex(considerVertecies.front());
			for (auto k = adjacent.begin(); k != adjacent.end(); ++k)
			{
				relax(*k, nextPassVertecies);
			}
			considerVertecies.pop();
		}
		considerVertecies = nextPassVertecies;
	}
}

// Dijkstra's algorithim for computing shortest path
void Graph::computeShortestPaths(int aNodeId)
{
  initializeShortestPath(aNodeId);

  Heap<Node*> heap(numNodes());

  // Insert all the nodes into the heap
  for (const SLLNode<Node*>* curr = mNodes.head();
       curr != NULL; curr = curr->next()) {
    Node* currNode = curr->value();
    heap.insertIgnoringHeapOrder(currNode);
  }

  // Heapify into a min heap
  heap.bottomUpMinHeap();

  // You can call heap.removeMin() to extract the min
  while(!heap.isEmpty()){
    Node* u = heap.removeMin();
    SLinkedList<Edge*> edges = u->getEdges();
    for (SLLNode<Edge*>* curr = edges.head();
       curr != NULL; curr = curr->next()){
        Edge* e = curr->value();
        relax(e);
    }
    heap.bottomUpMinHeap();
  }

}

void
MCMultiGrid::relax (MultiFab& solL,
		    MultiFab& rhsL,
		    int       level,
		    Real      eps_rel,
		    Real      eps_abs,
		    MCBC_Mode bc_mode)
{
  //
  // Recursively relax system.  Equivalent to multigrid V-cycle.
  // At coarsest grid, call coarsestSmooth.
  //
  if (level < numlevels - 1 ) {
    for (int i = preSmooth() ; i > 0 ; i--) {
      Lp.smooth(solL, rhsL, level, bc_mode);
    }
    
    Lp.residual(*res[level], rhsL, solL, level, bc_mode);
    prepareForLevel(level+1);
    average(*rhs[level+1], *res[level]);
    cor[level+1]->setVal(0.0);
    for (int i = cntRelax(); i > 0 ; i--) {
      relax(*cor[level+1],*rhs[level+1],level+1,eps_rel,eps_abs,bc_mode);
    }
    interpolate(solL, *cor[level+1]);
    for (int i = postSmooth(); i > 0 ; i--) {
      Lp.smooth(solL, rhsL, level, bc_mode);
    }
  } else {
    coarsestSmooth(solL, rhsL, level, eps_rel, eps_abs, bc_mode);
  }
}

/* iterates over and relaxs all of node's edges */
void relaxEdges(Heap h, Node n){
	Edge e = n->head;
	while (e != NULL){
		relax(h,n,e);
		e = e->next;
	}
}

void solve2(int size, int* years, int* answer, int cap, int *iterations, int trueAns, float TL) {
    n = size; c = cap;
    bestAns = 0;

    for (int i = 0; i < n; ++i) {
        arr[i].first = years[i];
        arr[i].second = i;
    }
    int iters = 0;
    LL a = clock();
    while ((clock() - a) * 1.0 / CLOCKS_PER_SEC < TL) {
        relax();
        if (bestAns < trueAns) {
            iters++;
        } else if (bestAns == trueAns) {
            break;
        }
        std::random_shuffle(arr, arr + n);
    }

    *iterations = iters;
    sort(ALL(ans));
    for (int i = 0; i < ans.size(); ++i) {
        answer[ans[i]] = 1;
    }
}