


from __future__ import annotations

import math
import random
from typing import Any

class   A__ :







    """simple docstring"""

    def __init__(	self   ):
         snake_case					=		[]
         snake_case					=		0
         snake_case					=		0
    def 		a_      (	self   ):
         return self.head == self.tail
    def 		a_      (	self      , __snake_case   ):
         self.data.append(__snake_case   )
         snake_case					=		self.tail + 1
    def 		a_      (	self   ):
         snake_case					=		self.data[self.head]
         snake_case					=		self.head + 1
         return ret
    def 		a_      (	self   ):
         return self.tail - self.head




    def 		a_      (	self   ):
         print(self.data   )
         print('''**************'''   )
         print(self.data[self.head : self.tail]   )






class   A__ :







    """simple docstring"""

    def __init__(	self      , __snake_case   ):
         snake_case					=		data
         snake_case					=		None
         snake_case					=		None
         snake_case					=		1
    def 		a_      (	self   ):
         return self.data
    def 		a_      (	self   ):
         return self.left
    def 		a_      (	self   ):
         return self.right
    def 		a_      (	self   ):
         return self.height
    def 		a_      (	self      , __snake_case   ):
         snake_case					=		data
    def 		a_      (	self      , __snake_case   ):
         snake_case					=		node
    def 		a_      (	self      , __snake_case   ):
         snake_case					=		node




    def 		a_      (	self      , __snake_case   ):
         snake_case					=		height






def       UpperCAmelCase__						(UpperCamelCase_    ):



     """simple docstring"""






     if node is None:
          return 0
     return node.get_height()
def       UpperCAmelCase__						(UpperCamelCase_							,UpperCamelCase_    ):



     """simple docstring"""






     if a > b:
          return a
     return b
def       UpperCAmelCase__						(UpperCamelCase_    ):



     """simple docstring"""






     print('''left rotation node:'''							,node.get_data()    )
     snake_case					=		node.get_left()
     assert ret is not None
     node.set_left(ret.get_right()    )
     ret.set_right(UpperCamelCase_    )
     snake_case					=		my_max(get_height(node.get_right()    )							,get_height(node.get_left()    )    ) + 1
     node.set_height(UpperCamelCase_    )
     snake_case					=		my_max(get_height(ret.get_right()    )							,get_height(ret.get_left()    )    ) + 1
     ret.set_height(UpperCamelCase_    )
     return ret
def       UpperCAmelCase__						(UpperCamelCase_    ):



     """simple docstring"""






     print('''right rotation node:'''							,node.get_data()    )
     snake_case					=		node.get_right()
     assert ret is not None
     node.set_right(ret.get_left()    )
     ret.set_left(UpperCamelCase_    )
     snake_case					=		my_max(get_height(node.get_right()    )							,get_height(node.get_left()    )    ) + 1
     node.set_height(UpperCamelCase_    )
     snake_case					=		my_max(get_height(ret.get_right()    )							,get_height(ret.get_left()    )    ) + 1
     ret.set_height(UpperCamelCase_    )
     return ret
def       UpperCAmelCase__						(UpperCamelCase_    ):



     """simple docstring"""






     snake_case					=		node.get_left()
     assert left_child is not None
     node.set_left(left_rotation(UpperCamelCase_    )    )
     return right_rotation(UpperCamelCase_    )
def       UpperCAmelCase__						(UpperCamelCase_    ):



     """simple docstring"""






     snake_case					=		node.get_right()
     assert right_child is not None
     node.set_right(right_rotation(UpperCamelCase_    )    )
     return left_rotation(UpperCamelCase_    )
def       UpperCAmelCase__						(UpperCamelCase_							,UpperCamelCase_    ):



     """simple docstring"""






     if node is None:
          return MyNode(UpperCamelCase_    )
     if data < node.get_data():
          node.set_left(insert_node(node.get_left()							,UpperCamelCase_    )    )
          if (
              get_height(node.get_left()    ) - get_height(node.get_right()    ) == 2
          ):  # an unbalance detected
               snake_case					=		node.get_left()
               assert left_child is not None
               if (
                   data < left_child.get_data()
               ):  # new node is the left child of the left child
                    snake_case					=		right_rotation(UpperCamelCase_    )
               else:
                    snake_case					=		lr_rotation(UpperCamelCase_    )
     else:
          node.set_right(insert_node(node.get_right()							,UpperCamelCase_    )    )
          if get_height(node.get_right()    ) - get_height(node.get_left()    ) == 2:
               snake_case					=		node.get_right()
               assert right_child is not None
               if data < right_child.get_data():
                    snake_case					=		rl_rotation(UpperCamelCase_    )
               else:
                    snake_case					=		left_rotation(UpperCamelCase_    )
     snake_case					=		my_max(get_height(node.get_right()    )							,get_height(node.get_left()    )    ) + 1
     node.set_height(UpperCamelCase_    )
     return node
def       UpperCAmelCase__						(UpperCamelCase_    ):



     """simple docstring"""






     while True:
          snake_case					=		root.get_right()
          if right_child is None:
               break
          snake_case					=		right_child
     return root.get_data()
def       UpperCAmelCase__						(UpperCamelCase_    ):



     """simple docstring"""






     while True:
          snake_case					=		root.get_left()
          if left_child is None:
               break
          snake_case					=		left_child
     return root.get_data()
def       UpperCAmelCase__						(UpperCamelCase_							,UpperCamelCase_    ):



     """simple docstring"""






     snake_case					=		root.get_left()
     snake_case					=		root.get_right()
     if root.get_data() == data:
          if left_child is not None and right_child is not None:
               snake_case					=		get_left_most(UpperCamelCase_    )
               root.set_data(UpperCamelCase_    )
               root.set_right(del_node(UpperCamelCase_							,UpperCamelCase_    )    )
          elif left_child is not None:
               snake_case					=		left_child
          elif right_child is not None:
               snake_case					=		right_child
          else:
               return None
     elif root.get_data() > data:
          if left_child is None:
               print('''No such data'''    )
               return root
          else:
               root.set_left(del_node(UpperCamelCase_							,UpperCamelCase_    )    )
     else:  # root.get_data() < data
          if right_child is None:
               return root
          else:
               root.set_right(del_node(UpperCamelCase_							,UpperCamelCase_    )    )

     if get_height(UpperCamelCase_    ) - get_height(UpperCamelCase_    ) == 2:
          assert right_child is not None
          if get_height(right_child.get_right()    ) > get_height(right_child.get_left()    ):
               snake_case					=		left_rotation(UpperCamelCase_    )
          else:
               snake_case					=		rl_rotation(UpperCamelCase_    )
     elif get_height(UpperCamelCase_    ) - get_height(UpperCamelCase_    ) == -2:
          assert left_child is not None
          if get_height(left_child.get_left()    ) > get_height(left_child.get_right()    ):
               snake_case					=		right_rotation(UpperCamelCase_    )
          else:
               snake_case					=		lr_rotation(UpperCamelCase_    )
     snake_case					=		my_max(get_height(root.get_right()    )							,get_height(root.get_left()    )    ) + 1
     root.set_height(UpperCamelCase_    )
     return root

class   A__ :







    """simple docstring"""

    def __init__(	self   ):
         snake_case					=		None
    def 		a_      (	self   ):
         return get_height(self.root   )
    def 		a_      (	self      , __snake_case   ):
         print('''insert:''' + str(__snake_case   )   )
         snake_case					=		insert_node(self.root      , __snake_case   )
    def 		a_      (	self      , __snake_case   ):
         print('''delete:''' + str(__snake_case   )   )
         if self.root is None:
              print('''Tree is empty!'''   )
              return
         snake_case					=		del_node(self.root      , __snake_case   )




    def __str__(	self      , ):  # a level traversale, gives a more intuitive look on the tree
         snake_case					=		''''''
         snake_case					=		MyQueue()
         q.push(self.root   )
         snake_case					=		self.get_height()
         if layer == 0:
              return output
         snake_case					=		0
         while not q.is_empty():
              snake_case					=		q.pop()
              snake_case					=		''' ''' * int(math.pow(2      , layer - 1   )   )
              output += space
              if node is None:
                   output += "*"
                   q.push(__snake_case   )
                   q.push(__snake_case   )
              else:
                   output += str(node.get_data()   )
                   q.push(node.get_left()   )
                   q.push(node.get_right()   )
              output += space
              snake_case					=		cnt + 1
              for i in range(1_0_0   ):
                   if cnt == math.pow(2      , __snake_case   ) - 1:
                        snake_case					=		layer - 1
                        if layer == 0:
                             output += "\n*************************************"
                             return output
                        output += "\n"
                        break
         output += "\n*************************************"
         return output






def       UpperCAmelCase__						():



     """simple docstring"""






     import doctest

     doctest.testmod()


if __name__ == "__main__":
 _test()
 _SCREAMING_SNAKE_CASE      :			List[Any]      				=   AVLtree()
 _SCREAMING_SNAKE_CASE      :			List[str]      				=   list(range(10))
 random.shuffle(lst)
 for i in lst:
  t.insert(i)
  print(str(t))
 random.shuffle(lst)
 for i in lst:
  t.del_node(i)
  print(str(t))








import argparse
import copy
def       UpperCAmelCase__						(UpperCamelCase_    ):



     """simple docstring"""






     snake_case					=    {}

     with open(UpperCamelCase_    ) as f:
          for line in f:
               if line.split()[0] not in dict_of_neighbours:
                    snake_case					=    []
                    _list.append([line.split()[1], line.split()[2]]    )
                    snake_case					=    _list
               else:
                    dict_of_neighbours[line.split()[0]].append(
                        [line.split()[1], line.split()[2]]    )
               if line.split()[1] not in dict_of_neighbours:
                    snake_case					=    []
                    _list.append([line.split()[0], line.split()[2]]    )
                    snake_case					=    _list
               else:
                    dict_of_neighbours[line.split()[1]].append(
                        [line.split()[0], line.split()[2]]    )

     return dict_of_neighbours
def       UpperCAmelCase__						(UpperCamelCase_							,UpperCamelCase_    ):



     """simple docstring"""






     with open(UpperCamelCase_    ) as f:
          snake_case					=    f.read(1    )
     snake_case					=    start_node

     snake_case					=    []

     snake_case					=    start_node

     snake_case					=    0
     while visiting not in first_solution:
          snake_case					=    1_00_00
          for k in dict_of_neighbours[visiting]:
               if int(k[1]    ) < int(UpperCamelCase_    ) and k[0] not in first_solution:
                    snake_case					=    k[1]
                    snake_case					=    k[0]

          first_solution.append(UpperCamelCase_    )
          snake_case					=    distance_of_first_solution + int(UpperCamelCase_    )
          snake_case					=    best_node

     first_solution.append(UpperCamelCase_    )

     snake_case					=    0
     for k in dict_of_neighbours[first_solution[-2]]:
          if k[0] == start_node:
               break
          position += 1

     snake_case					=    (
         distance_of_first_solution
         + int(dict_of_neighbours[first_solution[-2]][position][1]    )
         - 1_00_00
     )
     return first_solution, distance_of_first_solution
def       UpperCAmelCase__						(UpperCamelCase_							,UpperCamelCase_    ):



     """simple docstring"""






     snake_case					=    []

     for n in solution[1:-1]:
          snake_case					=    solution.index(UpperCamelCase_    )
          for kn in solution[1:-1]:
               snake_case					=    solution.index(UpperCamelCase_    )
               if n == kn:
                    continue

               snake_case					=    copy.deepcopy(UpperCamelCase_    )
               snake_case					=    kn
               snake_case					=    n

               snake_case					=    0

               for k in _tmp[:-1]:
                    snake_case					=    _tmp[_tmp.index(UpperCamelCase_    ) + 1]
                    for i in dict_of_neighbours[k]:
                         if i[0] == next_node:
                              snake_case					=    distance + int(i[1]    )
               _tmp.append(UpperCamelCase_    )

               if _tmp not in neighborhood_of_solution:
                    neighborhood_of_solution.append(_tmp    )

     snake_case					=    len(neighborhood_of_solution[0]    ) - 1

     neighborhood_of_solution.sort(key=lambda UpperCamelCase_    : x[index_of_last_item_in_the_list]    )
     return neighborhood_of_solution
def       UpperCAmelCase__						(UpperCamelCase_							,UpperCamelCase_							,UpperCamelCase_							,UpperCamelCase_							,UpperCamelCase_    ):



     """simple docstring"""






     snake_case					=    1
     snake_case					=    first_solution
     snake_case					=    []
     snake_case					=    distance_of_first_solution
     snake_case					=    solution

     while count <= iters:
          snake_case					=    find_neighborhood(UpperCamelCase_							,UpperCamelCase_    )
          snake_case					=    0
          snake_case					=    neighborhood[index_of_best_solution]
          snake_case					=    len(UpperCamelCase_    ) - 1

          snake_case					=    False
          while not found:
               snake_case					=    0
               while i < len(UpperCamelCase_    ):
                    if best_solution[i] != solution[i]:
                         snake_case					=    best_solution[i]
                         snake_case					=    solution[i]
                         break
                    snake_case					=    i + 1

               if [first_exchange_node, second_exchange_node] not in tabu_list and [
                   second_exchange_node,
                   first_exchange_node,
               ] not in tabu_list:
                    tabu_list.append([first_exchange_node, second_exchange_node]    )
                    snake_case					=    True
                    snake_case					=    best_solution[:-1]
                    snake_case					=    neighborhood[index_of_best_solution][best_cost_index]
                    if cost < best_cost:
                         snake_case					=    cost
                         snake_case					=    solution
               else:
                    snake_case					=    index_of_best_solution + 1
                    snake_case					=    neighborhood[index_of_best_solution]

          if len(UpperCamelCase_    ) >= size:
               tabu_list.pop(0    )

          snake_case					=    count + 1

     return best_solution_ever, best_cost
def       UpperCAmelCase__						(UpperCamelCase_=None    ):



     """simple docstring"""






     snake_case					=    generate_neighbours(args.File    )

     snake_case			,  snake_case					=    generate_first_solution(
         args.File							,UpperCamelCase_    )

     snake_case			,  snake_case					=    tabu_search(
         UpperCamelCase_							,UpperCamelCase_							,UpperCamelCase_							,args.Iterations							,args.Size							,)

     print(F'''Best solution: {best_sol}, with total distance: {best_cost}.'''    )


if __name__ == "__main__":
 _SCREAMING_SNAKE_CASE      :			Optional[Any]      				=   argparse.ArgumentParser(description="Tabu Search")
 parser.add_argument(
     "-f",
     "--File",
     type=str,
     help="Path to the file containing the data",
     required=True,
 )
 parser.add_argument(
     "-i",
     "--Iterations",
     type=int,
     help="How many iterations the algorithm should perform",
     required=True,
 )
 parser.add_argument(
     "-s", "--Size", type=int, help="Size of the tabu list", required=True
 )

 # Pass the arguments to main method
 main(parser.parse_args())




