From 7b2b3572406adaef8cc0097c93a965c11c4f9f1f Mon Sep 17 00:00:00 2001
From: Jakub Pawlowicz <contact@jakubpawlowicz.com>
Date: Thu, 5 Jan 2017 12:35:17 +0100
Subject: [PATCH] See #425 - adds natural sorting algorithm.

Why:

* We need it to sort selectors accordingly.
---
 lib/utils/natural-compare.js       | 31 ++++++++++++++++++++
 test/utils/natural-compare-test.js | 46 ++++++++++++++++++++++++++++++
 2 files changed, 77 insertions(+)
 create mode 100644 lib/utils/natural-compare.js
 create mode 100644 test/utils/natural-compare-test.js

diff --git a/lib/utils/natural-compare.js b/lib/utils/natural-compare.js
new file mode 100644
index 00000000..da828f40
--- /dev/null
+++ b/lib/utils/natural-compare.js
@@ -0,0 +1,31 @@
+// adapted from http://nedbatchelder.com/blog/200712.html#e20071211T054956
+
+var NUMBER_PATTERN = /([0-9]+)/;
+
+function naturalCompare(value1, value2) {
+  var keys1 = ('' + value1).split(NUMBER_PATTERN).map(tryParseInt);
+  var keys2 = ('' + value2).split(NUMBER_PATTERN).map(tryParseInt);
+  var key1;
+  var key2;
+  var compareFirst = Math.min(keys1.length, keys2.length);
+  var i, l;
+
+  for (i = 0, l = compareFirst; i < l; i++) {
+    key1 = keys1[i];
+    key2 = keys2[i];
+
+    if (key1 != key2) {
+      return key1 > key2 ? 1 : (key1 === key2 ? 0 : -1);
+    }
+  }
+
+  return keys1.length > keys2.length ? 1 : -1;
+}
+
+function tryParseInt(value) {
+  return ('' + parseInt(value)) == value ?
+    parseInt(value) :
+    value;
+}
+
+module.exports = naturalCompare;
diff --git a/test/utils/natural-compare-test.js b/test/utils/natural-compare-test.js
new file mode 100644
index 00000000..b2eb40bd
--- /dev/null
+++ b/test/utils/natural-compare-test.js
@@ -0,0 +1,46 @@
+var assert = require('assert');
+
+var vows = require('vows');
+
+var naturalCompare = require('../../lib/utils/natural-compare');
+
+vows.describe(naturalCompare)
+  .addBatch({
+    'numbers': {
+      'topic': [2, 3, 1, 5, 4, 11, 22],
+      'are sorted': function (list) {
+        assert.deepEqual(list.sort(naturalCompare), [1, 2, 3, 4, 5, 11, 22]);
+      }
+    },
+    'numbers and strings': {
+      'topic': ['2', 3, 1, 5, '4', '11', '22'],
+      'are sorted': function (list) {
+        assert.deepEqual(list.sort(naturalCompare), [1, '2', 3, '4', 5, '11', '22']);
+      }
+    },
+    'strings': {
+      'topic': ['2', '3', '1', '5', '4', '11', '22'],
+      'are sorted': function (list) {
+        assert.deepEqual(list.sort(naturalCompare), ['1', '2', '3', '4', '5', '11', '22']);
+      }
+    },
+    'strings with same prefix': {
+      'topic': ['x2', 'x3', 'x1', 'x5', 'x4', 'x11', 'x22'],
+      'are sorted': function (list) {
+        assert.deepEqual(list.sort(naturalCompare), ['x1', 'x2', 'x3', 'x4', 'x5', 'x11', 'x22']);
+      }
+    },
+    'strings with different prefixes': {
+      'topic': ['x2', 'x3', 'x1', 'y5', 'y4', 'y11', 'y22'],
+      'are sorted': function (list) {
+        assert.deepEqual(list.sort(naturalCompare), ['x1', 'x2', 'x3', 'y4', 'y5', 'y11', 'y22']);
+      }
+    },
+    'strings with different prefixes and suffixes of different length': {
+      'topic': ['x2a1', 'x3', 'x1b2', 'x2a2', 'x3a1', 'x33', 'x1b21'],
+      'are sorted': function (list) {
+        assert.deepEqual(list.sort(naturalCompare), ['x1b2', 'x1b21', 'x2a1', 'x2a2', 'x3', 'x3a1', 'x33']);
+      }
+    }
+  })
+  .export(module);
-- 
2.34.1