From 66e25549aabed323c6dbd0640658eeb8373ec9c7 Mon Sep 17 00:00:00 2001
From: grumbel <grumbel@837edb03-e0f3-0310-88ca-d4d4e8b29345>
Date: Sun, 22 Nov 2009 01:04:27 +0000
Subject: [PATCH] Added numeric string compare

git-svn-id: http://supertux.lethargik.org/svn/supertux/trunk/supertux@6082 837edb03-e0f3-0310-88ca-d4d4e8b29345
---
 src/util/string_util.cpp               | 60 +++++++++++++++++++++++++++++++++
 src/util/string_util.hpp               |  4 +++
 test/string_util_numeric_sort_test.cpp | 61 ++++++++++++++++++++++++++++++++++
 test/string_util_numeric_sort_test.txt | 10 ++++++
 4 files changed, 135 insertions(+)
 create mode 100644 test/string_util_numeric_sort_test.cpp
 create mode 100644 test/string_util_numeric_sort_test.txt

diff --git a/src/util/string_util.cpp b/src/util/string_util.cpp
index b68193006..d3cb8ab43 100644
--- a/src/util/string_util.cpp
+++ b/src/util/string_util.cpp
@@ -14,6 +14,8 @@
 //  You should have received a copy of the GNU General Public License
 //  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
+#include <algorithm>
+
 #include "string_util.hpp"
 
 bool
@@ -29,4 +31,62 @@ StringUtil::has_suffix(const std::string& data, const std::string& suffix)
   }
 }
 
+bool
+StringUtil::numeric_less(const std::string& lhs, const std::string& rhs)
+{
+  std::string::size_type i = 0;
+  std::string::size_type min_len = std::min(lhs.size(), rhs.size());
+
+  while(i < min_len)
+  {
+    if (isdigit(lhs[i]) && isdigit(rhs[i]))
+    {
+      // have two digits, so check which number is smaller
+      std::string::size_type li = i+1;
+      std::string::size_type ri = i+1;
+
+      // find the end of the number in both strings
+      while(li < lhs.size() && isdigit(lhs[li])) { li += 1; }
+      while(ri < rhs.size() && isdigit(rhs[ri])) { ri += 1; }
+
+      if (li == ri)
+      {
+        // end is at the same point in both strings, so do a detaile
+        // comparism of the numbers
+        for(std::string::size_type j = i; j < li; ++j)
+        {
+          if (lhs[j] != rhs[j])
+          {
+            return lhs[j] < rhs[j];
+          }
+        }
+
+        // numbers are the same, so jump to the end of the number and compare
+        i = li;
+      }
+      else
+      {
+        // numbers have different numbers of digits, so the number
+        // with the least digits wins
+        return li < ri;
+      }
+    }
+    else
+    {
+      // do normal character comparism
+      if (lhs[i] != rhs[i])
+      {
+        return lhs[i] < rhs[i];
+      }
+      else
+      {
+        // strings are the same so far, so continue
+        i += 1;
+      }
+    }
+  }
+
+  return lhs.size() < rhs.size();
+}
+
 /* EOF */
diff --git a/src/util/string_util.hpp b/src/util/string_util.hpp
index d5f9ae13c..5e2b56b31 100644
--- a/src/util/string_util.hpp
+++ b/src/util/string_util.hpp
@@ -23,6 +23,10 @@ class StringUtil
 {
 public:
   static bool has_suffix(const std::string& data, const std::string& suffix);
+
+  /** Compare two strings according to their numeric value, similar to
+      what 'sort -n' does. */
+  static bool numeric_less(const std::string& lhs, const std::string& rhs);
 };
 
 #endif
diff --git a/test/string_util_numeric_sort_test.cpp b/test/string_util_numeric_sort_test.cpp
new file mode 100644
index 000000000..c6ba1bb34
--- /dev/null
+++ b/test/string_util_numeric_sort_test.cpp
@@ -0,0 +1,61 @@
+//  SuperTux
+//  Copyright (C) 2009 Ingo Ruhnke <grumbel@gmx.de>
+//
+//  This program 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, either version 3 of the License, or
+//  (at your option) any later version.
+//
+//  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/>.
+
+#include <algorithm>
+#include <fstream>
+#include <iostream>
+#include <vector>
+
+#include "util/string_util.hpp"
+
+int main(int argc, char** argv)
+{
+  std::vector<std::string> lines;
+  
+  // read files from stdin or files
+  std::string line;
+  if (argc > 1)
+  {
+    for(int i = 1; i < argc; ++i)
+    {
+      std::ifstream in(argv[i]);
+      while(std::getline(in, line))
+      {
+        lines.push_back(line);
+      }
+    }
+  }
+  else
+  {
+    while(std::getline(std::cin, line))
+    {
+      lines.push_back(line);
+    }
+  }
+  
+  // sort lines
+  std::sort(lines.begin(), lines.end(), StringUtil::numeric_less);
+
+  // output the sorted text
+  for(std::vector<std::string>::iterator i = lines.begin(); i != lines.end(); ++i)
+  {
+    std::cout << *i << std::endl;
+  }
+
+  return 0;
+}
+
+/* EOF */
diff --git a/test/string_util_numeric_sort_test.txt b/test/string_util_numeric_sort_test.txt
new file mode 100644
index 000000000..c6b6849ed
--- /dev/null
+++ b/test/string_util_numeric_sort_test.txt
@@ -0,0 +1,10 @@
+B1235
+A123
+A123
+A12
+B12323423A233
+B12323423A1231
+Z1
+A1A123
+A1A1
+A1A12
-- 
2.11.0