Add some more info on map/set

3 files changed, 124 insertions, 6 deletions

diff --git a/README.md b/README.md
index 0b95e93..54a1087 100644
--- a/README.md
+++ b/README.md
@@ -7,4 +7,6 @@
 * Тема 6: Двойно свързани списъци. Задачи върху списъци. [Упражнение - реализирайте двойно свързан списък](Seminar06/DLLSkeleton.cpp)
 * Тема 7: Сортиращи алгоритми.
 * Тема 8: Дървета. Двоични дървета. Двоични наредени дървета.
-* Тема 9: Дървета 2. Балансирани дървета. Ротации. Задачи върху дървета.
\ No newline at end of file
+* Тема 9: Дървета 2. Балансирани дървета. Ротации. Задачи върху дървета.
+* Тема 10: Самобалансиращи се дървета. AVL дървета. std::set, std::multiset, std::map, std::multimap
+* Тема 11: Графи. BFS и DFS.
\ No newline at end of file
diff --git a/Seminar10/README.md b/Seminar10/README.md
index f83973c..25b431e 100644
--- a/Seminar10/README.md
+++ b/Seminar10/README.md
@@ -369,9 +369,7 @@ int main() {
 Сега вече всичко работи. Ами ако ни трябват повторения?
 
 ## std::multiset
-std::multiset е мултимножество. Освен стандартните функции multiset може да ни каже колко обекта от този тип имаме чрез метода count. Тук метода erase премахва **всички** елементи с подадена стойност! Ако искаме да премахнем един елемент използваме метода extract.
-
- extract връща елемент от тип node handle който държи в себе си стойността на извадения елемент.
+std::multiset е мултимножество. Освен стандартните функции multiset може да ни каже колко обекта от този тип имаме чрез метода count. Тук метода erase премахва **всички** елементи с подадена стойност! Ако искаме да премахнем един елемент използваме метода extract. extract връща елемент от тип node handle който държи в себе си стойността на извадения елемент.
 
 ```cpp
 #include<set>
@@ -388,8 +386,71 @@ int main() {
 	std::cout << k.value() << " " << s.count(10);
 }
 ```
-## Предшественици и наследници в множество
 
 ## std::map
+std::map е сортиран контейнер, който реализира Key-Value двойки. Какво ще рече това? Примерно, даден ми е някакъв текст и искам да си направя хистограма (за всяка негова буква пазя по колко пъти се среща). Също така, на стандартния изход искам да изведа за всеки символ, колко пъти се среща, но буквите трябва да са в сортиран ред.
+
+Следния код ще свърши работа:
+```cpp
+#include<iostream>
+#include<map>
+#include<string>
+
+int main() {
+	std::string str;
+	std::getline(std::cin, str, '\n');
+	
+	std::map<char, int> hist;
+
+	for (const char& c : str) {
+		hist[c]++;
+	}
+
+    // Всеки елемент от hist e наредена двойка <Key, Value>
+	for (const auto& elem : hist) {
+		std::cout << elem.first << "x" << elem.second << std::endl;
+	}
+	/*
+	zbbzaaz
+	ax2
+	bx2
+	zx3
+	*/
+}
+```
+В случай ключовете са елементи от тип char е стойностите са колко пъти се среща този char с текста. std::map отново се реализира чрез червено черно дърво. Ключовете са елементите по които строим това дърво (логично, понеже по тях търсим). Забележете, че не е нужно да правим insert. Самото индексиране създава възел за нас. 
 
-## std::multimap
\ No newline at end of file
+```
+T& std::map<K, V>::operator[](const Key&):
+
+Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion if such key does not already exist.
+```
+
+Какво е важно за ключовете? Отново, както при std::set, трябва да имаме operator<() дефиниран за типа, представляващ ключ.
+
+## std::multimap
+std::multimap също реализира Key-Value двойка, но този път можем да имаме повторение на ключовете. 
+Този път вече нямаме operator[], понеже ключът не е единствен.
+
+```
+Multimap is an associative container that contains a sorted list of key-value pairs, while permitting multiple entries with the same key.
+```
+
+## Логаритмичен wordle
+Играта е следната. В началото си намисляме някаква дума, след това потребителя се опитва да я познае. Потребителя въвежда някаква дума, като знае дължината на намислената от нас дума, и за всяка буква от думата му трябва да му кажем дали я има и ако я има дами е на правилното място.
+
+Да предположим, че ще извеждаме 2 ако е на правилното място, 1 ако се съдържа но не е на правилното място и 0 ако я няма.
+
+Примерно:
+``` 
+Дума: access
+Опит: arrest
+Изход:
+a 2
+r 0
+r 0
+e 2
+s 2
+t 0
+```
+Как това ще стане с multimap? Примера е качен в wordle.cpp.
\ No newline at end of file
diff --git a/Seminar10/wordle.cpp b/Seminar10/wordle.cpp
new file mode 100644
index 0000000..967e807
--- /dev/null
+++ b/Seminar10/wordle.cpp
@@ -0,0 +1,55 @@
+#include<iostream>
+#include<map>
+#include<string>
+
+int determineChar(const std::multimap<char, int>& mp, size_t idx, char currChar) {
+    // find връща end ако не го намери
+	auto currentIterator = mp.find(currChar);
+
+	if (currentIterator == mp.end())
+		return 0;
+
+    // Докато не стигнем края, което е възможно, 
+    // и докато все още сме на този символ
+	while (currentIterator != mp.end() && currentIterator->first == currChar) {
+		if (currentIterator->second == idx)
+			return 2;
+		++currentIterator;
+	}
+
+	return 1;
+}
+
+int main() {
+	std::string word;
+	std::cout << "Enter word to guess: " << std::endl;
+	
+    std::getline(std::cin, word, '\n');
+	std::multimap<char, int> wordle;
+
+	for (size_t i = 0; i < word.size(); i++)
+		wordle.insert({ word[i], i });
+	
+	bool guessed = false;
+
+	while (!guessed) {
+		std::cout << "Enter guess with length: " << wordle.size() << std::endl;
+		std::getline(std::cin, word, '\n');
+
+		if (word.length() != wordle.size()) {
+			std::cout << "Invalid length" << std::endl;
+			continue;
+		}
+
+		guessed = true;
+
+		for (size_t i = 0; i < word.size(); i++) {
+			int result = determineChar(wordle, i, word[i]);
+			
+			std::cout << word[i] << " " << result << std::endl;
+
+			if (result != 2)
+				guessed = false;
+		}
+	}
+}
\ No newline at end of file