Page MenuHomePhabricator
Files F13228050

D15413.id37160.diff
No OneTemporary
Actions

D15413.id37160.diff
View Options

diff --git a/src/__phutil_library_map__.php b/src/__phutil_library_map__.php
--- a/src/__phutil_library_map__.php
+++ b/src/__phutil_library_map__.php
@@ -341,6 +341,7 @@
'PhutilSimpleOptionsLexerTestCase' => 'lexer/__tests__/PhutilSimpleOptionsLexerTestCase.php',
'PhutilSimpleOptionsTestCase' => 'parser/__tests__/PhutilSimpleOptionsTestCase.php',
'PhutilSocketChannel' => 'channel/PhutilSocketChannel.php',
+ 'PhutilSortVector' => 'utils/PhutilSortVector.php',
'PhutilSprite' => 'sprites/PhutilSprite.php',
'PhutilSpriteSheet' => 'sprites/PhutilSpriteSheet.php',
'PhutilSymbolLoader' => 'symbols/PhutilSymbolLoader.php',
@@ -424,6 +425,7 @@
'mgroup' => 'utils/utils.php',
'mpull' => 'utils/utils.php',
'msort' => 'utils/utils.php',
+ 'msortv' => 'utils/utils.php',
'newv' => 'utils/utils.php',
'nonempty' => 'utils/utils.php',
'phlog' => 'error/phlog.php',
@@ -876,6 +878,7 @@
'PhutilSimpleOptionsLexerTestCase' => 'PhutilTestCase',
'PhutilSimpleOptionsTestCase' => 'PhutilTestCase',
'PhutilSocketChannel' => 'PhutilChannel',
+ 'PhutilSortVector' => 'Phobject',
'PhutilSprite' => 'Phobject',
'PhutilSpriteSheet' => 'Phobject',
'PhutilSyntaxHighlighter' => 'Phobject',
diff --git a/src/utils/PhutilSortVector.php b/src/utils/PhutilSortVector.php
new file mode 100644
--- /dev/null
+++ b/src/utils/PhutilSortVector.php
@@ -0,0 +1,47 @@
+<?php
+
+final class PhutilSortVector
+ extends Phobject {
+
+ private $parts = array();
+
+ public function addInt($value) {
+ // We need to produce strings for each integer which sort naturally. This
+ // requires some careful manipulation.
+
+ if ($value === ~PHP_INT_MAX) {
+ // For the minimum integer value (usually -9223372036854775808 on 64
+ // bit systems) we just give it a special "A" prefix to make sure it
+ // sorts first.
+ $prefix = 'A';
+ } else if ($value < 0) {
+ // For all other negative values, we give them a "B" prefix, then
+ // subtract the value from the maximum integer. This sorts values
+ // in ascending order when printed.
+ $prefix = 'B';
+ $value = PHP_INT_MAX + $value;
+ } else {
+ // For zero and positive values, we give them a "C" prefix.
+ $prefix = 'C';
+ }
+
+ $this->parts[] = sprintf('%s%020u', $prefix, $value);
+ return $this;
+ }
+
+ public function addString($value) {
+ if (strlen($value) && (strpos("\0", $value) !== false)) {
+ throw new Exception(
+ pht(
+ 'String components of a sort vector must not contain NULL bytes.'));
+ }
+
+ $this->parts[] = $value;
+ return $this;
+ }
+
+ public function __toString() {
+ return implode("\0", $this->parts);
+ }
+
+}
diff --git a/src/utils/__tests__/PhutilUtilsTestCase.php b/src/utils/__tests__/PhutilUtilsTestCase.php
--- a/src/utils/__tests__/PhutilUtilsTestCase.php
+++ b/src/utils/__tests__/PhutilUtilsTestCase.php
@@ -817,5 +817,64 @@
}
}
+ public function testVectorSortInt() {
+ $original = array(
+ ~PHP_INT_MAX,
+ -2147483648,
+ -5,
+ -3,
+ -1,
+ 0,
+ 1,
+ 2,
+ 3,
+ 100,
+ PHP_INT_MAX,
+ );
+
+ $items = $this->shuffleMap($original);
+
+ foreach ($items as $key => $value) {
+ $items[$key] = (string)id(new PhutilSortVector())
+ ->addInt($value);
+ }
+
+ asort($items, SORT_STRING);
+
+ $this->assertEqual(
+ array_keys($original),
+ array_keys($items));
+ }
+
+ public function testVectorSortString() {
+ $original = array(
+ '',
+ "\1",
+ 'A',
+ 'AB',
+ 'Z',
+ "Z\1",
+ 'ZZZ',
+ );
+
+ $items = $this->shuffleMap($original);
+
+ foreach ($items as $key => $value) {
+ $items[$key] = (string)id(new PhutilSortVector())
+ ->addString($value);
+ }
+
+ asort($items, SORT_STRING);
+
+ $this->assertEqual(
+ array_keys($original),
+ array_keys($items));
+ }
+
+ private function shuffleMap(array $map) {
+ $keys = array_keys($map);
+ shuffle($keys);
+ return array_select_keys($map, $keys);
+ }
}
diff --git a/src/utils/utils.php b/src/utils/utils.php
--- a/src/utils/utils.php
+++ b/src/utils/utils.php
@@ -406,6 +406,50 @@
/**
+ * Sort a list of objects by a sort vector.
+ *
+ * This sort is stable, well-behaved, and more efficient than `usort()`.
+ *
+ * @param list List of objects to sort.
+ * @param string Name of a method to call on each object. The method must
+ * return a @{class:PhutilSortVector}.
+ * @return list Objects ordered by the vectors.
+ */
+function msortv(array $list, $method) {
+ $surrogate = mpull($list, $method);
+
+ $index = 0;
+ foreach ($surrogate as $key => $value) {
+ if (!($value instanceof PhutilSortVector)) {
+ throw new Exception(
+ pht(
+ 'Objects passed to "%s" must return sort vectors (objects of '.
+ 'class "%s") from the specified method ("%s"). One object (with '.
+ 'key "%s") did not.',
+ 'msortv()',
+ 'PhutilSortVector',
+ $method,
+ $key));
+ }
+
+ // Add the original index to keep the sort stable.
+ $value->addInt($index++);
+
+ $surrogate[$key] = (string)$value;
+ }
+
+ asort($surrogate, SORT_STRING);
+
+ $result = array();
+ foreach ($surrogate as $key => $value) {
+ $result[$key] = $list[$key];
+ }
+
+ return $result;
+}
+
+
+/**
* Sort a list of arrays by the value of some index. This method is identical to
* @{function:msort}, but operates on a list of arrays instead of a list of
* objects.

File Metadata

Mime Type
text/plain
Expires
Tue, May 21, 6:38 AM (1 w, 6 d ago)
Storage Engine
blob
Storage Format
Encrypted (AES-256-CBC)
Storage Handle
6297809
Default Alt Text
D15413.id37160.diff (5 KB)

Event Timeline

Phabricator · Built by Phacility