/* -*- mode: C++; indent-tabs-mode: nil; -*-

 /* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  *

  * Permission to use, modify and distribute this software is granted

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * provided that this copyright notice appears in all copies. For

           {

           {

             // Compute insertion cost and position for the unused nodes

             // Compute insertion cost and position for the unused nodes

             for (unsigned int i=0; i<_notused.size(); ++i) {

             for (unsigned int i=0; i<_notused.size(); ++i) {

               Node u = _notused[i];

               Node u = _notused[i];

               Cost min_cost = costDiff(_tour.back(), _tour.front(), u);

               Cost min_cost = costDiff(_tour.back(), _tour.front(), u);

               for (unsigned int j=1; j<_tour.size(); ++j) {

               for (unsigned int j=1; j<_tour.size(); ++j) {

                 Cost curr_cost = costDiff(_tour[j-1], _tour[j], u);

                 Cost curr_cost = costDiff(_tour[j-1], _tour[j], u);

                 if (curr_cost < min_cost) {

                 if (curr_cost < min_cost) {

                   min_cost = curr_cost;

                   min_cost = curr_cost;

                   min_pos = j;

                   min_pos = j;

             // Remove the selected node from the unused vector

             // Remove the selected node from the unused vector

             Node sn = _notused[min_node];

             Node sn = _notused[min_node];

             _notused[min_node] = _notused.back();

             _notused[min_node] = _notused.back();

             _notused.pop_back();

             _notused.pop_back();

             // Insert the selected node into the tour

             // Insert the selected node into the tour

             const int ipos = _ins_pos[sn];

             const int ipos = _ins_pos[sn];

             _tour.insert(_tour.begin() + ipos, sn);

             _tour.insert(_tour.begin() + ipos, sn);

             // Update the insertion cost and position of the remaining nodes

             // Update the insertion cost and position of the remaining nodes

               int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1;

               int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1;

               int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1;

               int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1;

               Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u);

               Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u);

               Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u);

               Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u);

               if (nc1 <= curr_cost || nc2 <= curr_cost) {

               if (nc1 <= curr_cost || nc2 <= curr_cost) {

                 // A new position is better than the old one

                 // A new position is better than the old one

                 if (nc1 <= nc2) {

                 if (nc1 <= nc2) {

                   curr_cost = nc1;

                   curr_cost = nc1;

                   curr_pos = ipos;

                   curr_pos = ipos;

               }

               }

               else {

               else {

                 if (curr_pos == ipos) {

                 if (curr_pos == ipos) {

                   // The minimum should be found again

                   // The minimum should be found again

                   curr_cost = costDiff(_tour.back(), _tour.front(), u);

                   curr_cost = costDiff(_tour.back(), _tour.front(), u);

                   for (unsigned int j=1; j<_tour.size(); ++j) {

                   for (unsigned int j=1; j<_tour.size(); ++j) {

                     Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u);

                     Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u);

                     if (tmp_cost < curr_cost) {

                     if (tmp_cost < curr_cost) {

                       curr_cost = tmp_cost;

                       curr_cost = tmp_cost;

                       curr_pos = j;

                       curr_pos = j;

                 }

                 }

                 else if (curr_pos > ipos) {

                 else if (curr_pos > ipos) {

                   ++curr_pos;

                   ++curr_pos;

                 }

                 }

               }

               }

               _ins_cost[u] = curr_cost;

               _ins_cost[u] = curr_cost;

               _ins_pos[u] = curr_pos;

               _ins_pos[u] = curr_pos;

             }

             }

             return min_cost;

             return min_cost;