Mainly reworked finding to use binary search and also did some smaller tweaks

3 files changed, 40 insertions, 32 deletions

diff --git a/Year 1/Object-oriented Programming/Solutions Sem. 08/ex3/DynStr.cpp b/Year 1/Object-oriented Programming/Solutions Sem. 08/ex3/DynStr.cpp
index 97a2fb4..a7499a8 100644
--- a/Year 1/Object-oriented Programming/Solutions Sem. 08/ex3/DynStr.cpp
+++ b/Year 1/Object-oriented Programming/Solutions Sem. 08/ex3/DynStr.cpp
@@ -50,9 +50,5 @@ const char* DynStr::get_str() const {
 }
 
 int DynStr::compare(const char* other) const {
-	int cmp = strcmp(str, other);
-	// On some compilers (gcc) strcmp returns the difference, but we want it to return -1, 0 or 1
-	if (cmp > 1) cmp = 1;
-	else if (cmp < -1) cmp = -1;
-	return cmp;
+	return strcmp(str, other);
 }
diff --git a/Year 1/Object-oriented Programming/Solutions Sem. 08/ex3/WordCollection.cpp b/Year 1/Object-oriented Programming/Solutions Sem. 08/ex3/WordCollection.cpp
index b0cd465..cd651b4 100644
--- a/Year 1/Object-oriented Programming/Solutions Sem. 08/ex3/WordCollection.cpp
+++ b/Year 1/Object-oriented Programming/Solutions Sem. 08/ex3/WordCollection.cpp
@@ -43,33 +43,42 @@ void WordCollection::resize() {
 	sortedPos = newSortMap;
 }
 
-void WordCollection::insertSortMapIndex(int position, int value) {
-	if (position == -1)
-		position = count;
+void WordCollection::insertSortedPos(int index, int value) {
+	if (index == -1)
+		index = count;
 
-	for (int i = count; i > position; i--)
+	for (int i = count; i > index; i--)
 		sortedPos[i] = sortedPos[i - 1];
-	sortedPos[position] = value;
+	sortedPos[index] = value;
 }
 
-void WordCollection::removeSortMapIndex(int position) {
-	for (int i = position; i <= count - 2; i++)
+void WordCollection::removeSortedPos(int index) {
+	for (int i = index; i <= count - 2; i++)
 		sortedPos[i] = sortedPos[i + 1];
 	sortedPos[count - 1] = 0;
 }
 
-int WordCollection::findSortMapIndexWhen(int condition, const char* str) {
-	if (condition < -1) condition = -1;
-	else if (condition > 1) condition = 1;
-
-	// TODO: replace with binary search
+int WordCollection::findSortedPosIndexFirstBigger(const char* str) const {
 	for (int i = 0; i < count; i++) {
-		if (words[sortedPos[i]].compare(str) == condition)
+		if (words[sortedPos[i]].compare(str) > 0)
 			return i;
 	}
 	return -1;
 }
 
+int WordCollection::findSortedPosIndex(const char* str) const {
+	int l = 0, r = count - 1;
+	while (l <= r) {
+		int m = (l + r) / 2;
+		int cmp = words[sortedPos[m]].compare(str);
+
+		if (cmp > 0) r = m - 1;
+		else if (cmp < 0) l = m + 1;
+		else return m;
+	}
+	return -1;
+}
+
 /* Public */
 
 WordCollection::WordCollection() {
@@ -95,8 +104,10 @@ WordCollection::~WordCollection() {
 }
 
 WordCollection& WordCollection::operator+=(const WordCollection& other) {
-	for (int i = 0; i < other.count; i++) {
-		(*this) *= other.words[other.sortedPos[i]].get_str();
+	if (this != &other) {
+		for (int i = 0; i < other.count; i++) {
+			(*this) *= other.words[other.sortedPos[i]].get_str();
+		}
 	}
 	return *this;
 }
@@ -107,9 +118,8 @@ WordCollection& WordCollection::operator-=(const WordCollection& other) {
 			(*this) /= other.words[other.sortedPos[i]].get_str();
 		}
 	}
-	else {
-		*this = WordCollection();
-	}
+	else *this = WordCollection();
+
 	return *this;
 }
 
@@ -118,7 +128,7 @@ WordCollection& WordCollection::operator*=(const char* str) {
 		if (count == length || storedWordsCount == length) resize();
 
 		words[storedWordsCount] = DynStr(str);
-		insertSortMapIndex(findSortMapIndexWhen(1, str), storedWordsCount);
+		insertSortedPos(findSortedPosIndexFirstBigger(str), storedWordsCount);
 		count++;
 		storedWordsCount++;
 	}
@@ -126,10 +136,10 @@ WordCollection& WordCollection::operator*=(const char* str) {
 }
 
 WordCollection& WordCollection::operator/=(const char* str) {
-	int ind = findSortMapIndexWhen(0, str);
+	int ind = findSortedPosIndex(str);
 	if (ind > -1) {
 		words[sortedPos[ind]] = DynStr();
-		removeSortMapIndex(ind);
+		removeSortedPos(ind);
 		count--;
 	}
 	return *this;
@@ -153,8 +163,8 @@ std::istream& operator>>(std::istream& istrm, WordCollection& collection) {
 	return istrm;
 }
 
-bool WordCollection::operator[](const char* str) {
-	return findSortMapIndexWhen(0, str) > -1;
+bool WordCollection::operator[](const char* str) const {
+	return findSortedPosIndex(str) > -1;
 }
 
 const WordCollection operator+(const WordCollection& lhs, const WordCollection& rhs) {
diff --git a/Year 1/Object-oriented Programming/Solutions Sem. 08/ex3/WordCollection.h b/Year 1/Object-oriented Programming/Solutions Sem. 08/ex3/WordCollection.h
index 18e1b1c..6731d85 100644
--- a/Year 1/Object-oriented Programming/Solutions Sem. 08/ex3/WordCollection.h
+++ b/Year 1/Object-oriented Programming/Solutions Sem. 08/ex3/WordCollection.h
@@ -13,9 +13,11 @@ class WordCollection {
 	void copyFrom(const WordCollection& other);
 
 	void resize();
-	void insertSortMapIndex(int position, int value);
-	void removeSortMapIndex(int position);
-	int findSortMapIndexWhen(int condition, const char* str);
+	void insertSortedPos(int index, int value);
+	void removeSortedPos(int index);
+
+	int findSortedPosIndexFirstBigger(const char* str) const;
+	int findSortedPosIndex(const char* str) const;
 
 public:
 	WordCollection();
@@ -32,7 +34,7 @@ public:
 	friend std::ostream& operator<<(std::ostream& ostrm, const WordCollection& collection);
 	friend std::istream& operator>>(std::istream& istrm, WordCollection& collection);
 
-	bool operator[](const char* str);
+	bool operator[](const char* str) const;
 };
 
 const WordCollection operator+(const WordCollection& lhs, const WordCollection& rhs);