[Bf-blender-cvs] [b26a74c470e] functions: method to pop item from map

[Jacques Lucke]

Commit: b26a74c470efc8d564cc7ea3d03985b4781b2342
Author: Jacques Lucke
Date:   Sun Apr 7 20:22:06 2019 +0200
Branches: functions
https://developer.blender.org/rBb26a74c470efc8d564cc7ea3d03985b4781b2342

method to pop item from map

===================================================================

M	source/blender/blenlib/BLI_array_lookup.hpp
M	source/blender/blenlib/BLI_small_map.hpp
M	tests/gtests/blenlib/BLI_small_map_test.cc

===================================================================

diff --git a/source/blender/blenlib/BLI_array_lookup.hpp b/source/blender/blenlib/BLI_array_lookup.hpp
index 08741f9ff96..f185bd5ba0f 100644
--- a/source/blender/blenlib/BLI_array_lookup.hpp
+++ b/source/blender/blenlib/BLI_array_lookup.hpp
@@ -118,6 +118,17 @@ namespace BLI {
 			}
 		}
 
+		void update_index(
+			const Key &key, Index old_index, Index new_index)
+		{
+			ITER_SLOTS(key, slot, state) {
+				if (state == old_index) {
+					m_map[slot] = new_index;
+					break;
+				}
+			}
+		}
+
 		typename std::make_signed<Index>::type find(
 			Item *array, const Key &key) const
 		{
@@ -178,4 +189,4 @@ namespace BLI {
 #undef SLOT_EMPTY
 #undef SLOT_DUMMY
 #undef LOAD_FACTOR
-#undef PERTURB_SHIFT
\ No newline at end of file
+#undef PERTURB_SHIFT
diff --git a/source/blender/blenlib/BLI_small_map.hpp b/source/blender/blenlib/BLI_small_map.hpp
index bea14230212..7738ffa36d4 100644
--- a/source/blender/blenlib/BLI_small_map.hpp
+++ b/source/blender/blenlib/BLI_small_map.hpp
@@ -30,7 +30,18 @@ namespace BLI {
 
 		SmallMap() = default;
 
-		void add(const K &key, const V &value)
+		bool add(const K &key, const V &value)
+		{
+			if (this->contains(key)) {
+				return false;
+			}
+			else {
+				this->add_new(key, value);
+				return true;
+			}
+		}
+
+		void add_new(const K &key, const V &value)
 		{
 			BLI_assert(!this->contains(key));
 			uint index = m_entries.size();
@@ -44,6 +55,26 @@ namespace BLI {
 			return m_lookup.contains(m_entries.begin(), key);
 		}
 
+		V pop(const K &key)
+		{
+			BLI_assert(this->contains(key));
+			uint index = m_lookup.find(m_entries.begin(), key);
+			V value = m_entries[index].value;
+
+			uint last_index = m_entries.size() - 1;
+			if (index == last_index) {
+				m_entries.remove_last();
+				m_lookup.remove(key, index);
+			}
+			else {
+				m_entries.remove_and_reorder(index);
+				m_lookup.remove(key, index);
+				K &moved_key = m_entries[index].key;
+				m_lookup.update_index(moved_key, last_index, index);
+			}
+			return value;
+		}
+
 		V lookup(const K &key) const
 		{
 			return this->lookup_ref(key);
@@ -132,4 +163,4 @@ namespace BLI {
 			}
 		};
 	};
-};
\ No newline at end of file
+};
diff --git a/tests/gtests/blenlib/BLI_small_map_test.cc b/tests/gtests/blenlib/BLI_small_map_test.cc
index cbf873c9817..6f866e690c6 100644
--- a/tests/gtests/blenlib/BLI_small_map_test.cc
+++ b/tests/gtests/blenlib/BLI_small_map_test.cc
@@ -53,4 +53,35 @@ TEST(small_map, AddMany)
 	for (int i = 0; i < 100; i++) {
 		map.add(i, i);
 	}
-}
\ No newline at end of file
+}
+
+TEST(small_map, PopItem)
+{
+	IntFloatMap map;
+	map.add(2, 3.0f);
+	map.add(1, 9.0f);
+	EXPECT_TRUE(map.contains(2));
+	EXPECT_TRUE(map.contains(1));
+
+	EXPECT_EQ(map.pop(1), 9.0f);
+	EXPECT_TRUE(map.contains(2));
+	EXPECT_FALSE(map.contains(1));
+
+	EXPECT_EQ(map.pop(2), 3.0f);
+	EXPECT_FALSE(map.contains(2));
+	EXPECT_FALSE(map.contains(1));
+}
+
+TEST(small_map, PopItemMany)
+{
+	IntFloatMap map;
+	for (uint i = 0; i < 100; i++) {
+		map.add_new(i, i);
+	}
+	for (uint i = 25; i < 80; i++) {
+		EXPECT_EQ(map.pop(i), i);
+	}
+	for (uint i = 0; i < 100; i++) {
+		EXPECT_EQ(map.contains(i), i < 25 || i >= 80);
+	}
+}