#include <iostream>
#include <vector>
#include <string>

class Populated_locality {
private:
	std::string name;
	int population;
public:
	Populated_locality() {}

	Populated_locality(std::string name, int population) {
		this->name = name;
		this->population = population;
	}

	std::string get_name() {
		return name;
	}

	int get_population() {
		return population;
	}
};

class Locality_array {
private:
	std::vector<Populated_locality> p_l_array;
	int length;
public:
	Locality_array() {
		p_l_array = {};
		length = 0;
	}

	void add(Populated_locality obj) {
		p_l_array.push_back(obj);
		length++;
	}
	void delete_by_index(int index) {
		index--;
		p_l_array.erase(p_l_array.begin() + index);
	}
	void add_by_index(Populated_locality obj, int index) {
		index--;
		p_l_array.insert(p_l_array.begin() + index, obj);
	}
	Populated_locality get_by_index(int index) {
		if (index >= 0 && index <= this->length) {
			return p_l_array[index];
		}
		else {
			std::cout << "все плохо" << '/n';
		}

	}

	void print() {
		int i = 1;
		for (Populated_locality n : p_l_array) {
			std::cout << i << ' ';
			std::cout << n.get_name() << '\n';
			std::cout << n.get_population() << '\n';
			i++;
		}
	}
	void easy_selection_sort() {

		int min;
		Populated_locality tmp;

		for (int i = 0; i < length - 1; i++) {
			min = i;
			for (int j = i + 1; j < length; j++) {
				if (p_l_array[j].get_name() < p_l_array[i].get_name())
					min = j;
			}
			tmp = p_l_array[i];
			p_l_array[i] = p_l_array[min];
			p_l_array[min] = tmp;
		}
	}
	void quick_sort(int begin, int end) {

		int l = begin, r = end;
		std::string piv = p_l_array[(l + r) / 2].get_name();

		do {

			while (p_l_array[l].get_name() < piv)
				l++;
			while (p_l_array[r].get_name() > piv)
				r--;
			if (l <= r)
				std::swap(p_l_array[l++], p_l_array[r--]);



		} while (l <= r);
		if (begin < r) quick_sort(begin, r);
		if (end > l) quick_sort(l, end);

	}
	int simple_search(std::string str) {
		for (size_t i = 0; i < this->length; i++) {
			if(p_l_array[i].get_name() == str) {
				return i;
			}
		}
		return -1;

	}
	int binary_search(std::string str) {
		int midd = 0, left = 0, right = this->length;
		while (1) {
			midd = (left + right) / 2;

			if (str < p_l_array[midd].get_name())    // если искомое меньше значения в ячейке
				right = midd - 1;      // смещаем правую границу поиска
			else if (str > p_l_array[midd].get_name())  // если искомое больше значения в ячейке
				left = midd + 1;    // смещаем левую границу поиска
			else                       // иначе (значения равны)
				return midd;           // функция возвращает индекс ячейки

			if (left > right)          // если границы сомкнулись
				return -1;
		}

	}


	std::vector<Populated_locality> get_p_l_array() {
		return p_l_array;
	}
	int get_length() {
		return length;
	}
};

void main_menu(char *ch) {
	setlocale(LC_ALL, "Russian");
	std::cout << "1  (P)rint - Вывод коллекциина экран." << '\n';
	std::cout << "2  (A)dd - Вставка нового объекта." << '\n';
	std::cout << "3  (I)nsert - Вставка нового объекта по указанному индексу." << '\n';
	std::cout << "4  (D)elete - Удаление объекта по указанному индексу." << '\n';
	std::cout << "5  (G)et - Получение объекта поуказанному индексу." << '\n';
	std::cout << "6  (S)ize - Получение количества объектов в коллекции." << '\n';
	std::cout << "7  (F)ind - Простой поиск объекта по полю «Название населенного пункта»." << '\n';
	std::cout << "8  (B)inary find - Бинарный поиск объекта по полю «Название населенного пункта»." << '\n';

	std::cout << "9  (Q)uick Sort - Сортировка коллекции \"Быстрой сортировкой\"." << '\n';
	std::cout << "10  Simpl(e) Sort - Сортировка коллекции \"Сортировка простым выбором\"." << '\n';
	std::cin >> *ch;

}
void add_in_collection(Locality_array *data_base) {
	std::string name;
	int population;
	std::cout << "Введите название населенного пункта." << '\n';
	std::cin >> name;
	std::cout << "Введите количество жителей населенного пункта." << '\n';
	std::cin >> population;
	Populated_locality obj(name, population);
	data_base->add(obj);

}

void add_by_index(Locality_array *data_base) {
	std::string name;
	int population, index;
	std::cout << "Введите название населенного пункта." << '\n';
	std::cin >> name;
	std::cout << "Введите количество жителей населенного пункта." << '\n';
	std::cin >> population;
	std::cout << "Введите индекс." << '\n';
	std::cin >> index;
	Populated_locality obj(name, population);
	data_base->add_by_index(obj, index);
}

void delete_by_index(Locality_array *data_base) {
	int index;
	std::cout << "Введите индекс." << '\n';
	std::cin >> index;
	data_base->delete_by_index(index);
}

void binary_search(Locality_array *database) {
	int index;
	std::string str;
	std::cout << "Введите название населенного пункта" << '\n';
	std::cin >> str;
	index = database->binary_search(str);
	std::cout << index << '\n';
	std::cout << database->get_by_index(index).get_name() << '\n';
	std::cout << database->get_by_index(index).get_population() << '\n';
}
void simple_search(Locality_array *database) {
	int index;
	std::string str;
	std::cout << "Введите название населенного пункта" << '\n';
	std::cin >> str;
	index = database->simple_search(str);
	std::cout << index << '\n';
	std::cout << database->get_by_index(index).get_name() << '\n';
	std::cout << database->get_by_index(index).get_population() << '\n';
}


int main() {
	Locality_array data_base;
	char ch = 0;
	while (ch != 'x') {
		main_menu(&ch);
		switch (ch) {
		case 'p':
			data_base.print();
			break;
		case 'a':
			add_in_collection(&data_base);
			break;
		case 's':
			std::cout << data_base.get_length() << '\n';
			break;
		case 'i':
			add_by_index(&data_base);
			break;
		case 'q':
			data_base.quick_sort(0, data_base.get_length() - 1);
			break;
		case 'd':
			delete_by_index(&data_base);
			break;
		case 'b':
			binary_search(&data_base);
			break;
		case 'f':
			simple_search(&data_base);
			break;
		case 'e':
			data_base.easy_selection_sort();
			break;
		}

	}

	data_base.print();

	std::cout << '\n';

	data_base.print();
	int pause;
	std::cin >> pause;
	getchar();
}