Move stdalgo::map::difference to its own utility header.

1 files changed, 84 insertions, 0 deletions

diff --git a/include/utility/map.h b/include/utility/map.h
new file mode 100644
index 000000000..efbca18b8
--- /dev/null
+++ b/include/utility/map.h
@@ -0,0 +1,84 @@
+/*
+ * InspIRCd -- Internet Relay Chat Daemon
+ *
+ *   Copyright (C) 2021 Sadie Powell <sadie@witchery.services>
+ *
+ * This file is part of InspIRCd.  InspIRCd is free software: you can
+ * redistribute it and/or modify it under the terms of the GNU General Public
+ * License as published by the Free Software Foundation, version 2.
+ *
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+
+#pragma once
+
+
+namespace insp::map
+{
+	/** Compares two maps and returns a list of the differences.
+	 * @param first The first map to compare.
+	 * @param second The second map to compare.
+	 * @param out The map to store the differences in.
+	 */
+	template<typename Key, typename Value, typename Compare, template<typename...> typename Map>
+	void difference(const Map<Key, Value, Compare>& first, const Map<Key, Value, Compare>& second,
+		Map<Key, std::pair<std::optional<Value>, std::optional<Value>>, Compare>& out)
+	{
+		auto fiter = first.cbegin();
+		auto siter = second.cbegin();
+
+		while (fiter != first.end())
+		{
+			if (siter == second.end())
+			{
+				// Store the remaining from the first.
+				while (fiter != first.end())
+				{
+					out[fiter->first] = { fiter->second, std::nullopt };
+					fiter++;
+				}
+				return;
+			}
+
+			if (fiter->first < siter->first)
+			{
+				// The key in first is not in second.
+				out[fiter->first] = { fiter->second, std::nullopt };
+				fiter++;
+			}
+			else if (siter->first < fiter->first)
+			{
+				// The key in second is not in first.
+				out[siter->first] = { std::nullopt, siter->second };
+				siter++;
+			}
+			else if (fiter->second != siter->second)
+			{
+				// The key exists in both but the value differs.
+				out[fiter->first] = { fiter->second, siter->second };
+				fiter++;
+				siter++;
+			}
+			else
+			{
+				// The key/value is identical in both.
+				fiter++;
+				siter++;
+			}
+		}
+
+		// Store the remaining from the second.
+		while (siter != second.end())
+		{
+			out[siter->first] = { std::nullopt, siter->second };
+			siter++;
+		}
+	}
+}