mymap

mymap.cpp

//mymap.cpp
#include "mymap.h"
#include <iostream>
Map::Unit* Map::operator[](int key) {
	int j = 0;
		for (auto i = begin; i != end->next; i = i->next, j++) {
			if(j==key)
				return i;
		}
	return 0;
}

bool Map::AddElement(int key_, int info_) {

	if (begin == 0) {
		begin = new Unit;
		begin->key = key_;
		begin->info = info_;
		end = begin;
		size++;
		return true;
	}
	else {
		end->next = new Unit;
		end = end->next;
		end->info = info_;
		end->key = key_;
		size++;
	}

	return true;
}

void Map::print() {
	std::cout << "{\n";
	for (auto temp = begin; temp != end->next; temp = temp->next) {
		std::cout <<"  "<< temp->key << ":" << temp->info;
		if (temp->next != end->next)
			std::cout<< ",\n";
		else std::cout << "\n";
	}
	std::cout << "}\n";
}



Map::Map() {
	begin = 0;
	end = 0;
	size = 0;
}

Map::~Map() {
	if (begin)
		delete begin;
	if (end)
		delete end;
}



void Map::sort() {
	Unit *new_root = NULL;
	while (begin != NULL)
	{
		Unit *node = begin;
		begin = begin->next;

		if (new_root == NULL || node->key < new_root->key)
		{
			node->next = new_root;
			new_root = node;
		}
		else
		{
			Unit *current = new_root;
			while (current->next != NULL && !(node->key < current->next->key))
			{
				current = current->next;
			}

			node->next = current->next;
			current->next = node;
		}
	}

	begin = new_root;
	for (Unit*temp = begin;; temp = temp->next) {
		if (temp->next == NULL) {
			end = temp;
			break;
		}
	}
}

//MyMap.h
#pragma once

class Map {
public:
	struct Unit {
		int key;
		int info;
		Unit*next;
		Unit() {next = 0;}
	};
public:
	Unit*begin;
	Unit*end;
	
public:
	int size;
	Map();
	~Map();
	bool AddElement(int key_, int info_);
	Unit* operator[](int n);
	void print();
	void sort();
};
//test.cpp
	#include "mymap.h"
	#include "windows.h"
	#include <iostream>

	void bad_sort(Map& map) {
		for (int i = 1; i < map.size; i++)
			for (int j = i; j > 0 && map[j - 1]->key > map[j]->key; j--) {
				int temp = map[j - 1]->key;
				map[j - 1]->key = map[j]->key;
				map[j]->key = temp;

				temp = map[j - 1]->info;
				map[j - 1]->info = map[j]->info;
				map[j]->info = temp;
			}
	}
	int bin_search(Map&map, int key, int l, int r) {
		int m;
		while (l < r - 1) {
			m = (l + r) / 2;
			if (map[m]->key < key) {
				l = m;
			}
			else {
				r = m;
			}
		}
		return r;
	}
	int good_bad_sort(Map&map) {
		int c = 0;
		int swaps=0;
		std::cout << "  ";
		for (int i = 1; i < map.size; i++) {
			int j = i;
			int k = bin_search(map, map[i]->key, -1, j);
		
			if (!(i%(map.size/100) )) {
				c++;
				if (c < 10)
					std::cout << "\b\b" << c<<"%";
				else if (c == 10) {
					std::cout << "\b\b\b";
					std::cout << c<<"%";
				}
				else {
					std::cout << "\b\b\b\b" << c<<"%";
					if (c == 99) {
						std::cout << "\b\b\b\b\bDone\n";
					}
				}
			}
			for (int m = j; m > k; m--) {
				auto mm1 = map[m - 1];
			
				int temp = mm1->key;
				mm1->key = mm1->next->key;
				mm1->next->key = temp;

				temp = mm1->info;
				mm1->info = mm1->next->info;
				mm1->next->info = temp;
				swaps++;
			}
		}
		return swaps;
	}
	void printAllByKey(Map map, int key) {
		int i = 0;
		Map::Unit*temp = NULL;
		while (i<map.size) {
			if (key == map[i]->key) {
				temp = map[i];
				break;
			}
			i++;
		}
		if (temp && i < map.size) {
			while (temp->key == key) {
				std::cout << temp->key << ": " << temp->info << std::endl;
				temp = temp->next;
			}
		}
	}
	void main() {
		Map map;
		for (int i = 1000; i > 0; i--) {
			if (i % 10==0)
				map.AddElement(5, i);
			map.AddElement(i, i);
		}
		std::cout<<"swaps: "<<good_bad_sort(map);
		//map.sort();
		int key;
		std::cout << "key: ";
		std::cin >> key;
		printAllByKey(map, key);
		system("pause>nul");
	}