Homec4science

Add `msortv()`, a stable, well-behaved sort method

Authored by epriestley <git@epriestley.com> on Mar 6 2016, 16:42.

Description

Add msortv(), a stable, well-behaved sort method

Summary:
Ref T6861. We currently have three minor issues with sorting:

  • If types get mixed, PHP goes crazy. This is discussed in T6861.
  • The sort isn't guaranteed to be stable (identical input items are not reordered), but we'd probably always prefer a stable sort to a slightly more efficient one.
  • Interacting with sort keys is a mess of sprintf('~%020.020f', ...) nonsense.

Introduce msortv() and PhutilSortVector to solve these. The new msortv() is:

  • well-behaved (no craziness on mixed types); and
  • stable (input items with the same sort key are never reordered).

PhutilSortVector is a helper so you don't have to do the sprintf(...) garbage. Instead, classes will do this:

- return sprintf(
-   '~%020d%s',
-   $this->getOrder(),
-   $this->getName());

+ return id(new PhutilSortVector())
+   ->addInt($this->getOrder())
+   ->addString($this->getName());

This should be easier to read and much easier to get right, particularly for odd inputs at the edge of the range (like the most-negative integer).

Test Plan: Added and executed unit tests.

Reviewers: chad

Reviewed By: chad

Maniphest Tasks: T6861

Differential Revision: https://secure.phabricator.com/D15413

Details

Committed
epriestley <git@epriestley.com>Mar 6 2016, 18:27
Pushed
aubortMar 17 2017, 12:03
Parents
rPHUad3f475c8c13: Make the libphutil library map test failure more readable
Branches
Unknown
Tags
Unknown

Event Timeline

epriestley <git@epriestley.com> committed rPHU821cad811383: Add `msortv()`, a stable, well-behaved sort method (authored by epriestley <git@epriestley.com>).Mar 6 2016, 18:27