NaturalSort.php 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142
  1. <?php
  2. /**
  3. * @copyright Copyright (c) 2016, ownCloud, Inc.
  4. *
  5. * @author AW-UC <git@a-wesemann.de>
  6. * @author Lukas Reschke <lukas@statuscode.ch>
  7. * @author Morris Jobke <hey@morrisjobke.de>
  8. * @author Robin McCorkell <robin@mccorkell.me.uk>
  9. * @author Thomas Müller <thomas.mueller@tmit.eu>
  10. * @author Vincent Petry <pvince81@owncloud.com>
  11. *
  12. * @license AGPL-3.0
  13. *
  14. * This code is free software: you can redistribute it and/or modify
  15. * it under the terms of the GNU Affero General Public License, version 3,
  16. * as published by the Free Software Foundation.
  17. *
  18. * This program is distributed in the hope that it will be useful,
  19. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  21. * GNU Affero General Public License for more details.
  22. *
  23. * You should have received a copy of the GNU Affero General Public License, version 3,
  24. * along with this program. If not, see <http://www.gnu.org/licenses/>
  25. *
  26. */
  27. namespace OC;
  28. use OCP\ILogger;
  29. class NaturalSort {
  30. private static $instance;
  31. private $collator;
  32. private $cache = array();
  33. /**
  34. * Instantiate a new \OC\NaturalSort instance.
  35. * @param object $injectedCollator
  36. */
  37. public function __construct($injectedCollator = null) {
  38. // inject an instance of \Collator('en_US') to force using the php5-intl Collator
  39. // or inject an instance of \OC\NaturalSort_DefaultCollator to force using Owncloud's default collator
  40. if (isset($injectedCollator)) {
  41. $this->collator = $injectedCollator;
  42. \OCP\Util::writeLog('core', 'forced use of '.get_class($injectedCollator), ILogger::DEBUG);
  43. }
  44. }
  45. /**
  46. * Split the given string in chunks of numbers and strings
  47. * @param string $t string
  48. * @return array of strings and number chunks
  49. */
  50. private function naturalSortChunkify($t) {
  51. // Adapted and ported to PHP from
  52. // http://my.opera.com/GreyWyvern/blog/show.dml/1671288
  53. if (isset($this->cache[$t])) {
  54. return $this->cache[$t];
  55. }
  56. $tz = array();
  57. $x = 0;
  58. $y = -1;
  59. $n = null;
  60. while (isset($t[$x])) {
  61. $c = $t[$x];
  62. // only include the dot in strings
  63. $m = ((!$n && $c === '.') || ($c >= '0' && $c <= '9'));
  64. if ($m !== $n) {
  65. // next chunk
  66. $y++;
  67. $tz[$y] = '';
  68. $n = $m;
  69. }
  70. $tz[$y] .= $c;
  71. $x++;
  72. }
  73. $this->cache[$t] = $tz;
  74. return $tz;
  75. }
  76. /**
  77. * Returns the string collator
  78. * @return \Collator string collator
  79. */
  80. private function getCollator() {
  81. if (!isset($this->collator)) {
  82. // looks like the default is en_US_POSIX which yields wrong sorting with
  83. // German umlauts, so using en_US instead
  84. if (class_exists('Collator')) {
  85. $this->collator = new \Collator('en_US');
  86. }
  87. else {
  88. $this->collator = new \OC\NaturalSort_DefaultCollator();
  89. }
  90. }
  91. return $this->collator;
  92. }
  93. /**
  94. * Compare two strings to provide a natural sort
  95. * @param string $a first string to compare
  96. * @param string $b second string to compare
  97. * @return int -1 if $b comes before $a, 1 if $a comes before $b
  98. * or 0 if the strings are identical
  99. */
  100. public function compare($a, $b) {
  101. // Needed because PHP doesn't sort correctly when numbers are enclosed in
  102. // parenthesis, even with NUMERIC_COLLATION enabled.
  103. // For example it gave ["test (2).txt", "test.txt"]
  104. // instead of ["test.txt", "test (2).txt"]
  105. $aa = self::naturalSortChunkify($a);
  106. $bb = self::naturalSortChunkify($b);
  107. for ($x = 0; isset($aa[$x]) && isset($bb[$x]); $x++) {
  108. $aChunk = $aa[$x];
  109. $bChunk = $bb[$x];
  110. if ($aChunk !== $bChunk) {
  111. // test first character (character comparison, not number comparison)
  112. if ($aChunk[0] >= '0' && $aChunk[0] <= '9' && $bChunk[0] >= '0' && $bChunk[0] <= '9') {
  113. $aNum = (int)$aChunk;
  114. $bNum = (int)$bChunk;
  115. return $aNum - $bNum;
  116. }
  117. return self::getCollator()->compare($aChunk, $bChunk);
  118. }
  119. }
  120. return count($aa) - count($bb);
  121. }
  122. /**
  123. * Returns a singleton
  124. * @return \OC\NaturalSort instance
  125. */
  126. public static function getInstance() {
  127. if (!isset(self::$instance)) {
  128. self::$instance = new \OC\NaturalSort();
  129. }
  130. return self::$instance;
  131. }
  132. }