//

// Created by Alan Freitas on 20/07/20.

//

#include <string>

#include <algorithm>

#include <matplot/util/geodata.h>

#include <matplot/util/common.h>

namespace matplot {

// https://public.opendatasoft.com/explore/dataset/1000-largest-us-cities-by-population-with-geographic-coordinates/export/?sort=population

std::tuple<std::vector<double>, std::vector<double>, std::vector<std::string>>

prepare_world_cities() {

std::vector<double> y = {

9.55,

-54.283333,

-49.35,

31.766666666666666,

60.116667,

-0.5477,

18.0731,

-9.166667,

27.153611,

34.516666666666666,

41.31666666666667,

36.75,

-14.266666666666667,

42.5,

-8.833333333333334,

18.216666666666665,

17.116666666666667,

-34.583333333333336,

40.166666666666664,

12.516666666666667,

-35.266666666666666,

48.2,

40.38333333333333,

25.083333333333332,

26.233333333333334,

23.716666666666665,

13.1,

53.9,

50.833333333333336,

17.25,

6.483333333333333,

32.28333333333333,

27.466666666666665,

-16.5,

43.86666666666667,

-24.633333333333333,

-15.783333333333333,

18.416666666666668,

4.883333333333333,

42.68333333333333,

12.366666666666667,

16.8,

-3.3666666666666667,

11.55,

3.8666666666666667,

45.416666666666664,

14.916666666666666,

19.3,

4.366666666666666,

12.1,

-33.45,

39.916666666666664,

-10.416666666666666,

-12.166666666666666,

4.6,

-11.7,

-4.316666666666666,

-4.25,

-21.2,

9.933333333333334,

6.816666666666666,

45.8,

23.116666666666667,

12.1,

35.166666666666664,

50.083333333333336,

55.666666666666664,

11.583333333333334,

15.3,

18.466666666666665,

-0.21666666666666667,

30.05,

13.7,

3.75,

15.333333333333334,

59.43333333333333,

9.033333333333333,

-51.7,

62,

-18.133333333333333,

60.166666666666664,

48.86666666666667,

-17.533333333333335,

0.38333333333333336,

13.45,

41.68333333333333,

52.516666666666666,

5.55,

36.13333333333333,

37.983333333333334,

64.18333333333334,

12.05,

13.466666666666667,

14.616666666666667,

49.45,

9.5,

11.85,

6.8,

18.533333333333335,

41.9,

14.1,

47.5,

64.15,

28.6,

-6.166666666666667,

35.7,

33.333333333333336,

53.31666666666667,

54.15,

31.766666666666666,

41.9,

18,

35.68333333333333,

49.18333333333333,

31.95,

51.166666666666664,

-1.2833333333333332,

-0.8833333333333333,

39.016666666666666,

37.55,

42.666666666666664,

29.366666666666667,

42.86666666666667,

17.966666666666665,

56.95,

33.86666666666667,

-29.316666666666666,

6.3,

32.88333333333333,

47.13333333333333,

54.68333333333333,

49.6,

42,

-18.916666666666668,

-13.966666666666667,

3.1666666666666665,

4.166666666666667,

12.65,

35.88333333333333,

7.1,

18.066666666666666,

-20.15,

19.433333333333334,

6.916666666666667,

47,

43.733333333333334,

47.916666666666664,

42.43333333333333,

16.7,

34.016666666666666,

-25.95,

-22.566666666666666,

27.716666666666665,

52.35,

-22.266666666666666,

-41.3,

12.133333333333333,

13.516666666666667,

9.083333333333334,

-19.016666666666666,

-29.05,

15.2,

59.916666666666664,

23.616666666666667,

33.68333333333333,

7.483333333333333,

8.966666666666667,

-9.45,

-25.266666666666666,

-12.05,

14.6,

-25.066666666666666,

52.25,

38.71666666666667,

18.466666666666665,

25.283333333333335,

44.43333333333333,

55.75,

-1.95,

17.883333333333333,

-15.933333333333334,

17.3,

14,

46.766666666666666,

13.133333333333333,

-13.816666666666666,

43.93333333333333,

0.3333333333333333,

24.65,

14.733333333333333,

44.833333333333336,

-4.616666666666667,

8.483333333333333,

1.2833333333333332,

18.016666666666666,

48.15,

46.05,

-9.433333333333334,

2.066666666666667,

-25.7,

4.85,

40.4,

6.916666666666667,

15.6,

5.833333333333333,

78.21666666666667,

-26.316666666666666,

59.333333333333336,

46.916666666666664,

33.5,

25.033333333333335,

38.55,

-6.8,

13.75,

-8.583333333333334,

6.116666666666666,

-21.133333333333333,

10.65,

36.8,

39.93333333333333,

37.95,

21.466666666666665,

-8.516666666666667,

0.31666666666666665,

50.43333333333333,

24.466666666666665,

51.5,

38.88333333,

-34.85,

41.31666666666667,

-17.733333333333334,

10.483333333333333,

21.033333333333335,

18.35,

-13.95,

15.35,

-15.416666666666666,

-17.816666666666666,

38.883333,

0,

35.183333,

0,

0,

-7.3,

0,

};

std::vector<double> x = {

44.050000,

-36.500000,

70.216667,

35.233333,

19.900000,

166.920867,

-63.082200,

-171.833333,

-13.203333,

69.183333,

19.816667,

3.050000,

-170.700000,

1.516667,

13.216667,

-63.050000,

-61.850000,

-58.666667,

44.500000,

-70.033333,

149.133333,

16.366667,

49.866667,

-77.350000,

50.566667,

90.400000,

-59.616667,

27.566667,

4.333333,

-88.766667,

2.616667,

-64.783333,

89.633333,

-68.150000,

18.416667,

25.900000,

-47.916667,

-64.616667,

114.933333,

23.316667,

-1.516667,

96.150000,

29.350000,

104.916667,

11.516667,

-75.700000,

-23.516667,

-81.383333,

18.583333,

15.033333,

-70.666667,

116.383333,

105.716667,

96.833333,

-74.083333,

43.233333,

15.300000,

15.283333,

-159.766667,

-84.083333,

-5.266667,

16.000000,

-82.350000,

-68.916667,

33.366667,

14.466667,

12.583333,

43.150000,

-61.400000,

-69.900000,

-78.500000,

31.250000,

-89.200000,

8.783333,

38.933333,

24.716667,

38.700000,

-57.850000,

-6.766667,

178.416667,

24.933333,

2.333333,

-149.566667,

9.450000,

-16.566667,

44.833333,

13.400000,

-0.216667,

-5.350000,

23.733333,

-51.750000,

-61.750000,

144.733333,

-90.516667,

-2.533333,

-13.700000,

-15.583333,

-58.150000,

-72.333333,

12.450000,

-87.216667,

19.083333,

-21.950000,

77.200000,

106.816667,

51.416667,

44.400000,

-6.233333,

-4.483333,

35.233333,

12.483333,

-76.800000,

139.750000,

-2.100000,

35.933333,

71.416667,

36.816667,

169.533333,

125.750000,

126.983333,

21.166667,

47.966667,

74.600000,

102.600000,

24.100000,

35.500000,

27.483333,

-10.800000,

13.166667,

9.516667,

25.316667,

6.116667,

21.433333,

47.516667,

33.783333,

101.700000,

73.500000,

-8.000000,

14.500000,

171.383333,

-15.966667,

57.483333,

-99.133333,

158.150000,

28.850000,

7.416667,

106.916667,

19.266667,

-62.216667,

-6.816667,

32.583333,

17.083333,

85.316667,

4.916667,

166.450000,

174.783333,

-86.250000,

2.116667,

7.533333,

-169.916667,

167.966667,

145.750000,

10.750000,

58.583333,

73.050000,

134.633333,

-79.533333,

147.183333,

-57.666667,

-77.050000,

120.966667,

-130.083333,

21.000000,

-9.133333,

-66.116667,

51.533333,

26.100000,

37.600000,

30.050000,

-62.850000,

-5.716667,

-62.716667,

-61.000000,

-56.183333,

-61.216667,

-171.766667,

12.416667,

6.733333,

46.700000,

-17.633333,

20.500000,

55.450000,

-13.233333,

103.850000,

-63.033333,

17.116667,

14.516667,

159.950000,

45.333333,

28.216667,

31.616667,

-3.683333,

79.833333,

32.533333,

-55.166667,

15.633333,

31.133333,

18.050000,

7.466667,

36.300000,

121.516667,

68.766667,

39.283333,

100.516667,

125.600000,

1.216667,

-175.200000,

-61.516667,

10.183333,

32.866667,

58.383333,

-71.133333,

179.216667,

32.550000,

30.516667,

54.366667,

-0.083333,

-77.0000,

-56.166667,

69.250000,

168.316667,

-66.866667,

105.850000,

-64.933333,

-171.933333,

44.200000,

28.283333,

31.033333,

-77.0000,

0.000000,

33.366667,

0.000000,

0.000000,

72.400000,

0.000000

};

std::vector<std::string> z = {

"Hargeisa",

"King Edward Point",

"Port-aux-Français",

"Jerusalem",

"Mariehamn",

"Yaren",

"Marigot",

"Atafu",

"El-Aaiún",

"Kabul",

"Tirana",

"Algiers",

"Pago Pago",

"Andorra la Vella",

"Luanda",

"The Valley",

"Saint John's",

"Buenos Aires",

"Yerevan",

"Oranjestad",

"Canberra",

"Vienna",

"Baku",

"Nassau",

"Manama",

"Dhaka",

"Bridgetown",

"Minsk",

"Brussels",

"Belmopan",

"Porto-Novo",

"Hamilton",

"Thimphu",

"La Paz",

"Sarajevo",

"Gaborone",

"Brasilia",

"Road Town",

"Bandar Seri Begawan",

"Sofia",

"Ouagadougou",

"Rangoon",

"Bujumbura",

"Phnom Penh",

"Yaounde",

"Ottawa",

"Praia",

"George Town",

"Bangui",

"N'Djamena",

"Santiago",

"Beijing",

"The Settlement",

"West Island",

"Bogota",

"Moroni",

"Kinshasa",

"Brazzaville",

"Avarua",

"San Jose",

"Yamoussoukro",

"Zagreb",

"Havana",

"Willemstad",

"Nicosia",

"Prague",

"Copenhagen",

"Djibouti",

"Roseau",

"Santo Domingo",

"Quito",

"Cairo",

"San Salvador",

"Malabo",

"Asmara",

"Tallinn",

"Addis Ababa",

"Stanley",

"Torshavn",

"Suva",

"Helsinki",

"Paris",

"Papeete",

"Libreville",

"Banjul",

"Tbilisi",

"Berlin",

"Accra",

"Gibraltar",

"Athens",

"Nuuk",

"Saint George's",

"Hagatna",

"Guatemala City",

"Saint Peter Port",

"Conakry",

"Bissau",

"Georgetown",

"Port-au-Prince",

"Vatican City",

"Tegucigalpa",

"Budapest",

"Reykjavik",

"New Delhi",

"Jakarta",

"Tehran",

"Baghdad",

"Dublin",

"Douglas",

"Jerusalem",

"Rome",

"Kingston",

"Tokyo",

"Saint Helier",

"Amman",

"Astana",

"Nairobi",

"Tarawa",

"Pyongyang",

"Seoul",

"Pristina",

"Kuwait City",

"Bishkek",

"Vientiane",

"Riga",

"Beirut",

"Maseru",

"Monrovia",

"Tripoli",

"Vaduz",

"Vilnius",

"Luxembourg",

"Skopje",

"Antananarivo",

"Lilongwe",

"Kuala Lumpur",

"Male",

"Bamako",

"Valletta",

"Majuro",

"Nouakchott",

"Port Louis",

"Mexico City",

"Palikir",

"Chisinau",

"Monaco",

"Ulaanbaatar",

"Podgorica",

"Plymouth",

"Rabat",

"Maputo",

"Windhoek",

"Kathmandu",

"Amsterdam",

"Noumea",

"Wellington",

"Managua",

"Niamey",

"Abuja",

"Alofi",

"Kingston",

"Saipan",

"Oslo",

"Muscat",

"Islamabad",

"Melekeok",

"Panama City",

"Port Moresby",

"Asuncion",

"Lima",

"Manila",

"Adamstown",

"Warsaw",

"Lisbon",

"San Juan",

"Doha",

"Bucharest",

"Moscow",

"Kigali",

"Gustavia",

"Jamestown",

"Basseterre",

"Castries",

"Saint-Pierre",

"Kingstown",

"Apia",

"San Marino",

"Sao Tome",

"Riyadh",

"Dakar",

"Belgrade",

"Victoria",

"Freetown",

"Singapore",

"Philipsburg",

"Bratislava",

"Ljubljana",

"Honiara",

"Mogadishu",

"Pretoria",

"Juba",

"Madrid",

"Colombo",

"Khartoum",

"Paramaribo",

"Longyearbyen",

"Mbabane",

"Stockholm",

"Bern",

"Damascus",

"Taipei",

"Dushanbe",

"Dar es Salaam",

"Bangkok",

"Dili",

"Lome",

"Nuku'alofa",

"Port of Spain",

"Tunis",

"Ankara",

"Ashgabat",

"Grand Turk",

"Funafuti",

"Kampala",

"Kyiv",

"Abu Dhabi",

"London",

"Washington",

"Montevideo",

"Tashkent",

"Port-Vila",

"Caracas",

"Hanoi",

"Charlotte Amalie",

"Mata-Utu",

"Sanaa",

"Lusaka",

"Harare",

"Washington",

"Antarctica",

"North Nicosia",

"Hong Kong",

"Heard Island",

"Diego Garcia",

"Macau"

};

return std::make_tuple(x,y,z);

}

std::tuple<std::vector<double>, std::vector<double>, std::vector<std::string>>&

world_cities() {

static std::tuple<std::vector<double>, std::vector<double>, std::vector<std::string>> world_map_cities_ = prepare_world_cities();

return world_map_cities_;

}

std::tuple<std::vector<double>, std::vector<double>, std::vector<std::string>> world_cities(double min_x_distance_per_char, double min_y_distance) {

auto [x,y,names] = world_cities();

return clear_overlapping_labels(x,y,names,min_x_distance_per_char,min_y_distance);

}

std::tuple<std::vector<double>, std::vector<double>, std::vector<size_t>> greedy_tsp_with_idx(const std::vector<double>& x, const std::vector<double>& y, size_t starting_city) {

std::vector<size_t> route_idx = {starting_city};

while (route_idx.size() < x.size()) {

double x1 = x[route_idx.back()];

double y1 = y[route_idx.back()];

bool min_is_set = false;

double min_distance = 0;

size_t min_distance_idx = 0;

for (size_t i = 0; i < x.size(); ++i) {

bool not_there_yet =

std::none_of(route_idx.begin(), route_idx.end(),

[i](size_t idx) { return idx == i; });

if (not_there_yet) {

double x2 = x[route_idx.back()];

double y2 = y[route_idx.back()];

double d = distance(x1,y1,x2,y2);

if (!min_is_set || d < min_distance) {

min_distance = distance(x1,y1,x2,y2);

min_distance_idx = i;

}

}

}

route_idx.emplace_back(min_distance_idx);

}

std::vector<double> xstar;

std::vector<double> ystar;

for (const auto &idx : route_idx) {

xstar.emplace_back(x[idx]);

ystar.emplace_back(y[idx]);

}

return std::make_tuple(xstar, ystar, route_idx);

}

std::tuple<std::vector<double>, std::vector<double>> greedy_tsp(const std::vector<double>& x, const std::vector<double>& y, size_t starting_city) {

std::vector<size_t> route_idx = {starting_city};

while (route_idx.size() < x.size()) {

double x1 = x[route_idx.back()];

double y1 = y[route_idx.back()];

bool min_is_set = false;

double min_distance = 0;

size_t min_distance_idx = 0;

for (size_t i = 0; i < x.size(); ++i) {

bool not_there_yet =

std::none_of(route_idx.begin(), route_idx.end(),

[i](size_t idx) { return idx == i; });

if (not_there_yet) {

double x2 = x[route_idx.back()];

double y2 = y[route_idx.back()];

double d = distance(x1,y1,x2,y2);

if (!min_is_set || d < min_distance) {

min_distance = distance(x1,y1,x2,y2);

min_distance_idx = i;

}

}

}

route_idx.emplace_back(min_distance_idx);

}

std::vector<double> xstar;

std::vector<double> ystar;

for (const auto &idx : route_idx) {

xstar.emplace_back(x[idx]);

ystar.emplace_back(y[idx]);

}

return std::make_pair(xstar, ystar);

}

std::tuple<std::vector<double>, std::vector<double>, std::vector<std::string>> clear_overlapping_labels(const std::vector<double>& x, const std::vector<double>& y, const std::vector<std::string>& names, double min_x_distance_per_char, double min_y_distance) {

std::vector<size_t> pos_to_remove;

for (size_t i = 1; i < x.size(); ++i) {

double i_width = min_x_distance_per_char * names[i].size();

for (size_t j = 0; j < i; ++j) {

double j_width = min_x_distance_per_char * names[j].size();

bool x_overlap = x[i] < x[j] ? x[i] + i_width > x[j] : x[j] + j_width > x[i];

bool y_overlap = y[i] < y[j] ? y[i] + min_y_distance > y[j] : y[j] + min_y_distance > y[i];

if (x_overlap && y_overlap) {

pos_to_remove.emplace_back(i);

break;

}

}

}

auto x_line = x;

auto y_line = y;

auto names_line = names;

size_t i = pos_to_remove.size() - 1;

do {

x_line.erase(x_line.begin() + pos_to_remove[i]);

y_line.erase(y_line.begin() + pos_to_remove[i]);

names_line.erase(names_line.begin() + pos_to_remove[i]);

--i;

} while (i > 0);

return std::make_tuple(x_line,y_line,names_line);

}

}