module tspmc

  !
  ! Monte-Carlo method for solving TSP (uniform random)
  !

  use tspglobals
  use tsputils

  implicit none

  contains

    subroutine run_monte_carlo
      real :: distance
      integer :: i1, i2, i3
      integer :: last_sample_trial
      real :: rand

      print *, 'Using Monte-Carlo method.'

      ! initial tour
      if (init_type == INIT_NUMERICAL) then
         call numerical_tour(city_order)
      
      else if (init_type == INIT_RANDOM) then
         call random_tour(city_order)
         
      else if (init_type == INIT_GREEDY) then
         call greedy_tour(city_order)
      end if

      ! more initialisation
      trials = 1
      last_sample_trial = 1
      distance = tour_len(city_order)
      city_order_min = city_order
      distance_min = distance

      print *, 'trials ', 'distance_min '
      print *, trials, distance_min

      do trials = 2, n_trials
         
         ! perturb tour
         if (perturb_type == PERTURB_SWAP) then
            call random_number(rand)
            i1 = rand * n_cities
            call random_number(rand)
            i2 = rand * n_cities
            distance = swapped_distance(city_order, distance, i1, i2)
            call swap_operator(city_order, i1, i2)

         else if (perturb_type == PERTURB_REVSHIFT) then
            call random_number(rand)
            i1 = rand * n_cities
            call random_number(rand)
            i2 = rand * n_cities
            ! reverse or shift?
            call random_number(rand)
            if (rand < 0.5) then
               ! reverse segment
               distance = reversed_distance(city_order, distance, i1, i2)
               call reverse_operator(city_order, i1, i2)
            else
               ! shift segment
               distance = shifted_distance(city_order, distance, i1, i2, i3)
               call shift_operator(city_order, i1, i2, i3)
            end if
         end if

         ! recalculate true distance occasionally to avoid rounding errors
         if (mod(trials, recalc_trials) == 0) then
            distance = tour_len(city_order)
         end if

         ! evaluate
         if (distance < distance_min) then
            distance_min = distance
            city_order_min = city_order
            if (show_chgs) then
               if (trials - last_sample_trial >= sampling_threshold) then
                  print *, trials, distance_min
                  last_sample_trial = trials
               end if
            end if
         end if

         ! print status out_samples times
         if (mod(trials, out_sample_trials) == 0) then
            print *, trials, distance_min
         end if

      end do

    end subroutine run_monte_carlo

end module tspmc