Implement human sort utility function
This commit implements the ability to sort lists of strings that might
include numbers into "human" ordered lists. As an example of a problem
this solves, imagine a system with 12 dimms, today std::sort would net
you:
Dimm1
Dimm11
Dimm12
Dimm2
Dimm3
.....
This method breaks apart that string and sorts them in a way humans
would expect.
This code is originally inspired by the algorithm defined here:
http://www.davekoelle.com/alphanum.html. The site does include c++ code
that is MIT licensed, but is significantly more complex than what is
present in this commit. This commit also takes advantages in the form
of std::string_view to deduplicate overloads, as well as other c++17
features.
Tested:
Unit tests pass
Signed-off-by: Ed Tanous <edtanous@google.com>
Change-Id: Iac54c2e0d9998d4d622d74049b1dd957e4b3ca75
diff --git a/include/human_sort.hpp b/include/human_sort.hpp
new file mode 100644
index 0000000..5676994
--- /dev/null
+++ b/include/human_sort.hpp
@@ -0,0 +1,117 @@
+#pragma once
+
+#include <functional>
+#include <sstream>
+#include <string_view>
+
+namespace details
+{
+
+// This implementation avoids the complexity of using std::isdigit, which pulls
+// in all of <locale>, and likely has other consequences.
+inline bool simpleIsDigit(const char c)
+{
+ return c >= '0' && c <= '9';
+}
+
+} // namespace details
+
+inline int alphanumComp(const std::string_view left,
+ const std::string_view right)
+{
+ enum class ModeType
+ {
+ STRING,
+ NUMBER
+ } mode = ModeType::STRING;
+
+ std::string_view::const_iterator l = left.begin();
+ std::string_view::const_iterator r = right.begin();
+
+ while (l != left.end() && r != right.end())
+ {
+ if (mode == ModeType::STRING)
+ {
+ while (l != left.end() && r != right.end())
+ {
+ // check if this are digit characters
+ const bool lDigit = details::simpleIsDigit(*l);
+ const bool rDigit = details::simpleIsDigit(*r);
+ // if both characters are digits, we continue in NUMBER mode
+ if (lDigit && rDigit)
+ {
+ mode = ModeType::NUMBER;
+ break;
+ }
+ // if only the left character is a digit, we have a result
+ if (lDigit)
+ {
+ return -1;
+ } // if only the right character is a digit, we have a result
+ if (rDigit)
+ {
+ return +1;
+ }
+ // compute the difference of both characters
+ const int diff = *l - *r;
+ // if they differ we have a result
+ if (diff != 0)
+ {
+ return diff;
+ }
+ // otherwise process the next characters
+ l++;
+ r++;
+ }
+ }
+ else // mode==NUMBER
+ {
+ // get the left number
+ int lInt = 0;
+ while (l != left.end() && details::simpleIsDigit(*l))
+ {
+ lInt = lInt * 10 + static_cast<int>(*l) - '0';
+ ++l;
+ }
+
+ // get the right number
+ int rInt = 0;
+ while (r != right.end() && details::simpleIsDigit(*r))
+ {
+ rInt = rInt * 10 + static_cast<int>(*r) - '0';
+ ++r;
+ }
+
+ // if the difference is not equal to zero, we have a comparison
+ // result
+ const int diff = lInt - rInt;
+ if (diff != 0)
+ {
+ return diff;
+ }
+
+ // otherwise we process the next substring in STRING mode
+ mode = ModeType::STRING;
+ }
+ }
+ if (r == right.end() && l == left.end())
+ {
+ return 0;
+ }
+ if (r == right.end())
+ {
+ return 1;
+ }
+ return -1;
+}
+
+// A generic template type compatible with std::less that can be used on generic
+// containers (set, map, ect)
+template <class Type>
+struct AlphanumLess
+{
+ bool operator()(const Type& left, const Type& right) const
+ {
+ return alphanumComp(left, right) < 0;
+ }
+};
diff --git a/include/ut/human_sort_test.cpp b/include/ut/human_sort_test.cpp
new file mode 100644
index 0000000..7845f29
--- /dev/null
+++ b/include/ut/human_sort_test.cpp
@@ -0,0 +1,46 @@
+#include <human_sort.hpp>
+
+#include <set>
+
+#include "gmock/gmock.h"
+
+TEST(AlphaNum, NumberTests)
+{
+ // testcases for the algorithm
+ EXPECT_EQ(alphanumComp("", ""), 0);
+ EXPECT_LT(alphanumComp("", "a"), 0);
+ EXPECT_GT(alphanumComp("a", ""), 0);
+ EXPECT_EQ(alphanumComp("a", "a"), 0);
+ EXPECT_LT(alphanumComp("", "9"), 0);
+ EXPECT_GT(alphanumComp("9", ""), 0);
+ EXPECT_EQ(alphanumComp("1", "1"), 0);
+ EXPECT_LT(alphanumComp("1", "2"), 0);
+ EXPECT_GT(alphanumComp("3", "2"), 0);
+ EXPECT_EQ(alphanumComp("a1", "a1"), 0);
+ EXPECT_LT(alphanumComp("a1", "a2"), 0);
+ EXPECT_GT(alphanumComp("a2", "a1"), 0);
+ EXPECT_LT(alphanumComp("a1a2", "a1a3"), 0);
+ EXPECT_GT(alphanumComp("a1a2", "a1a0"), 0);
+ EXPECT_GT(alphanumComp("134", "122"), 0);
+ EXPECT_EQ(alphanumComp("12a3", "12a3"), 0);
+ EXPECT_GT(alphanumComp("12a1", "12a0"), 0);
+ EXPECT_LT(alphanumComp("12a1", "12a2"), 0);
+ EXPECT_LT(alphanumComp("a", "aa"), 0);
+ EXPECT_GT(alphanumComp("aaa", "aa"), 0);
+ EXPECT_EQ(alphanumComp("Alpha 2", "Alpha 2"), 0);
+ EXPECT_LT(alphanumComp("Alpha 2", "Alpha 2A"), 0);
+ EXPECT_GT(alphanumComp("Alpha 2 B", "Alpha 2"), 0);
+
+ std::string str("Alpha 2");
+ EXPECT_EQ(alphanumComp(str, "Alpha 2"), 0);
+ EXPECT_LT(alphanumComp(str, "Alpha 2A"), 0);
+ EXPECT_GT(alphanumComp("Alpha 2 B", str), 0);
+}
+
+TEST(AlphaNum, LessTest)
+{
+ std::set<std::string, AlphanumLess<std::string>> sorted{"Alpha 10",
+ "Alpha 2"};
+
+ EXPECT_THAT(sorted, ::testing::ElementsAreArray({"Alpha 2", "Alpha 10"}));
+}
diff --git a/meson.build b/meson.build
index bc492cd..8a9fcc2 100644
--- a/meson.build
+++ b/meson.build
@@ -356,6 +356,7 @@
srcfiles_unittest = [
'include/ut/dbus_utility_test.cpp',
'include/ut/http_utility_test.cpp',
+ 'include/ut/human_sort_test.cpp',
'redfish-core/ut/privileges_test.cpp',
'redfish-core/ut/lock_test.cpp',
'redfish-core/ut/configfile_test.cpp',