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);
+ }
+}
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
