Module: Philiprehberger::NaturalSort

Defined in:
lib/philiprehberger/natural_sort.rb,
lib/philiprehberger/natural_sort/version.rb,
lib/philiprehberger/natural_sort/comparator.rb

Defined Under Namespace

Modules: ArrayRefinement Classes: Error

Constant Summary collapse

VERSION = 
'0.13.0'

Class Method Summary collapse

Class Method Details

.between?(value, min, max, case_sensitive: false) ⇒ Boolean

Returns true if value falls within the natural sort range [min, max] inclusive.

Parameters:

  • value (String) —

    the value to check

  • min (String) —

    the lower bound (inclusive)

  • max (String) —

    the upper bound (inclusive)

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (Boolean) —

    true if value is between min and max in natural sort order



262
263
264
265
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 262

def self.between?(value, min, max, case_sensitive: false)
  compare(min, value, case_sensitive: case_sensitive) <= 0 &&
    compare(value, max, case_sensitive: case_sensitive) <= 0
end

.collate(a, b, case_sensitive: false) ⇒ Integer

Spaceship-style comparator returning -1, 0, or 1.

Suitable for use with Array#sort:

array.sort { |a, b| NaturalSort.collate(a, b) }

Parameters:

  • a (String, nil) —

    first string

  • b (String, nil) —

    second string

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (Integer) —

    -1, 0, or 1



251
252
253
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 251

def self.collate(a, b, case_sensitive: false)
  compare(a, b, case_sensitive: case_sensitive)
end

.comparator(case_sensitive: false) ⇒ Proc

Returns a Proc suitable for use with Array#sort.

Parameters:

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (Proc) —

    a comparison proc returning -1, 0, or 1



71
72
73
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 71

def self.comparator(case_sensitive: false)
  ->(a, b) { compare(a, b, case_sensitive: case_sensitive) }
end

.compare(a, b, case_sensitive: false) ⇒ Integer

Compares two strings using natural sort order.

Parameters:

  • a (String, nil) —

    first string

  • b (String, nil) —

    second string

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (Integer) —

    -1, 0, or 1



23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 23

def self.compare(a, b, case_sensitive: false)
  return 0 if a.nil? && b.nil?
  return -1 if a.nil?
  return 1 if b.nil?

  a_str = a.to_s
  b_str = b.to_s

  tokens_a = tokenize(a_str, case_sensitive: case_sensitive)
  tokens_b = tokenize(b_str, case_sensitive: case_sensitive)

  max_len = [tokens_a.length, tokens_b.length].max

  max_len.times do |i|
    chunk_a = tokens_a[i]
    chunk_b = tokens_b[i]

    # Shorter token list comes first
    return -1 if chunk_a.nil?
    return 1 if chunk_b.nil?

    # Both numeric
    if chunk_a.is_a?(Integer) && chunk_b.is_a?(Integer)
      cmp = chunk_a <=> chunk_b
      return cmp unless cmp.zero?

      next
    end

    # Both strings
    if chunk_a.is_a?(String) && chunk_b.is_a?(String)
      cmp = chunk_a <=> chunk_b
      return cmp unless cmp.zero?

      next
    end

    # Mixed: numbers sort before strings
    return chunk_a.is_a?(Integer) ? -1 : 1
  end

  0
end

.first(array, n: 1, case_sensitive: false) ⇒ String, ...

Returns the n naturally-smallest elements of an array.

With the default n: 1, returns the single smallest element (or nil for an empty array). With n > 1, returns an Array of up to n elements in natural sort order (small-to-large). When n exceeds the array size, the entire sorted array is returned.

Parameters:

  • array (Array<String, nil>) —

    the array to search

  • n (Integer) (defaults to: 1) —

    number of elements to return (must be a non-negative Integer)

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (String, Array<String, nil>, nil) —

    a single element when n == 1, otherwise an Array of up to n elements

Raises:

  • (ArgumentError) —

    when n is not a non-negative Integer



179
180
181
182
183
184
185
186
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 179

def self.first(array, n: 1, case_sensitive: false)
  raise ArgumentError, 'n must be a non-negative Integer' unless n.is_a?(Integer) && n >= 0

  sorted = sort(array, case_sensitive: case_sensitive)
  return sorted.first if n == 1

  sorted.first(n)
end

.group_by_prefix(array, case_sensitive: false) ⇒ Hash<String, Array<String>>

Splits each string at the first digit boundary, groups by the non-numeric prefix. Each group’s values are naturally sorted.

Parameters:

  • array (Array<String>) —

    the array to group

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (Hash<String, Array<String>>) —

    prefix => naturally sorted values



273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 273

def self.group_by_prefix(array, case_sensitive: false)
  groups = {}

  array.each do |str|
    s = str.to_s
    match = s.match(/\A([^\d]*)/)
    prefix = match ? match[1] : ''

    groups[prefix] ||= []
    groups[prefix] << str
  end

  groups.each_value do |values|
    values.replace(sort(values, case_sensitive: case_sensitive))
  end

  groups
end

.index(array, target, case_sensitive: false) ⇒ Integer?

Returns the position target would occupy in natural sort order within array, treating equality under natural comparison. Returns nil when no element compares equal to target. Equivalent to a natural-sort variant of Array#index that respects natural comparison semantics (e.g. ‘a1’ and ‘a01’ are equal).

When multiple elements compare equal, the smallest index of an equal element is returned.

Examples:

Philiprehberger::NaturalSort.index(['file10', 'file2', 'file1'], 'file2')
# => 1

Parameters:

  • array (Array<String, nil>) —

    the array to search

  • target (String, nil) —

    the value to locate

  • case_sensitive (Boolean) (defaults to: false) —

    whether comparison is case-sensitive

Returns:

  • (Integer, nil) —

    the first index whose value naturally equals target, or nil



363
364
365
366
367
368
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 363

def self.index(array, target, case_sensitive: false)
  array.each_with_index do |element, idx|
    return idx if compare(element, target, case_sensitive: case_sensitive).zero?
  end
  nil
end

.last(array, n: 1, case_sensitive: false) ⇒ String, ...

Returns the n naturally-largest elements of an array.

With the default n: 1, returns the single largest element (or nil for an empty array). With n > 1, returns an Array of up to n elements in reverse natural sort order (large-to-small). When n exceeds the array size, the entire reverse-sorted array is returned.

Parameters:

  • array (Array<String, nil>) —

    the array to search

  • n (Integer) (defaults to: 1) —

    number of elements to return (must be a non-negative Integer)

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (String, Array<String, nil>, nil) —

    a single element when n == 1, otherwise an Array of up to n elements

Raises:

  • (ArgumentError) —

    when n is not a non-negative Integer



201
202
203
204
205
206
207
208
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 201

def self.last(array, n: 1, case_sensitive: false)
  raise ArgumentError, 'n must be a non-negative Integer' unless n.is_a?(Integer) && n >= 0

  sorted = sort(array, case_sensitive: case_sensitive)
  return sorted.last if n == 1

  sorted.last(n).reverse
end

.max(array, case_sensitive: false) ⇒ String?

Finds the naturally largest element without full sort.

Parameters:

  • array (Array<String, nil>) —

    the array to search

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (String, nil) —

    the naturally largest element, or nil for empty arrays



147
148
149
150
151
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 147

def self.max(array, case_sensitive: false)
  return nil if array.empty?

  array.max { |a, b| compare(a, b, case_sensitive: case_sensitive) }
end

.min(array, case_sensitive: false) ⇒ String?

Finds the naturally smallest element without full sort.

Parameters:

  • array (Array<String, nil>) —

    the array to search

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (String, nil) —

    the naturally smallest element, or nil for empty arrays



136
137
138
139
140
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 136

def self.min(array, case_sensitive: false)
  return nil if array.empty?

  array.min { |a, b| compare(a, b, case_sensitive: case_sensitive) }
end

.minmax(array, case_sensitive: false) ⇒ Array<(String, String)>, Array<(nil, nil)>

Returns a two-element array ‘[min, max]` of the naturally-smallest and naturally-largest elements in a single Enumerable pass. Mirrors Ruby’s ‘Enumerable#minmax`. Returns `[nil, nil]` for empty arrays.

Parameters:

  • array (Array<String, nil>) —

    the array to search

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (Array<(String, String)>, Array<(nil, nil)>) —
    min, max

    pair



160
161
162
163
164
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 160

def self.minmax(array, case_sensitive: false)
  return [nil, nil] if array.empty?

  array.minmax { |a, b| compare(a, b, case_sensitive: case_sensitive) }
end

.natural_key(str, case_sensitive: false) ⇒ Array

Returns a sort key array usable with Ruby’s built-in sort_by, min_by, max_by, etc.

The key is an array of [type_flag, value] pairs where type_flag ensures correct ordering between numeric and string chunks (numbers sort before strings).

Parameters:

  • str (String, nil) —

    the string to generate a key for

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (Array) —

    a comparable sort key



218
219
220
221
222
223
224
225
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 218

def self.natural_key(str, case_sensitive: false)
  return [[-1, '']] if str.nil?

  tokens = tokenize(str.to_s, case_sensitive: case_sensitive)
  tokens.map do |chunk|
    chunk.is_a?(Integer) ? [0, chunk] : [1, chunk]
  end
end

.position(sorted_array, target, case_sensitive: false) ⇒ Integer?

Binary-search variant of index that assumes sorted_array is already in natural sort order. Returns the index of an element that compares equal to target, or nil when no such element exists. O(log n) lookup.

Behaviour is undefined when sorted_array is not actually sorted.

Examples:

sorted = Philiprehberger::NaturalSort.sort(['file10', 'file2', 'file1'])
Philiprehberger::NaturalSort.position(sorted, 'file2')
# => 1

Parameters:

  • sorted_array (Array<String, nil>) —

    an array already in natural sort order

  • target (String, nil) —

    the value to locate

  • case_sensitive (Boolean) (defaults to: false) —

    whether comparison is case-sensitive

Returns:

  • (Integer, nil) —

    index of an element that naturally equals target, or nil



386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 386

def self.position(sorted_array, target, case_sensitive: false)
  lo = 0
  hi = sorted_array.length - 1
  while lo <= hi
    mid = (lo + hi) / 2
    cmp = compare(sorted_array[mid], target, case_sensitive: case_sensitive)
    return mid if cmp.zero?

    if cmp.negative?
      lo = mid + 1
    else
      hi = mid - 1
    end
  end
  nil
end

.sort(array, case_sensitive: false, reverse: false, ignore_case: false) ⇒ Array<String, nil>

Sorts an array of strings in natural order.

Parameters:

  • array (Array<String, nil>) —

    the array to sort

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

  • reverse (Boolean) (defaults to: false) —

    when true, reverses the natural order

  • ignore_case (Boolean) (defaults to: false) —

    when true, downcases sort keys before comparison

Returns:

  • (Array<String, nil>) —

    a new sorted array



82
83
84
85
86
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 82

def self.sort(array, case_sensitive: false, reverse: false, ignore_case: false)
  effective_case_sensitive = ignore_case ? false : case_sensitive
  result = array.sort { |a, b| compare(a, b, case_sensitive: effective_case_sensitive) }
  reverse ? result.reverse : result
end

.sort!(array, case_sensitive: false, reverse: false) ⇒ Array<String, nil>

Sorts an array of strings in place using natural ordering.

Mirrors Ruby’s ‘Array#sort!` for callers who want to mutate the receiver rather than copy. Returns the same array.

Parameters:

  • array (Array<String, nil>) —

    the array to sort in place

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

  • reverse (Boolean) (defaults to: false) —

    when true, reverses the natural order

Returns:

  • (Array<String, nil>) —

    the same array, now sorted in place



97
98
99
100
101
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 97

def self.sort!(array, case_sensitive: false, reverse: false)
  array.sort! { |a, b| compare(a, b, case_sensitive: case_sensitive) }
  array.reverse! if reverse
  array
end

.sort_by(array, case_sensitive: false, reverse: false, ignore_case: false) {|element| ... } ⇒ Array

Sorts an array by the natural order of values returned by the block.

Parameters:

  • array (Array) —

    the array to sort

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

  • reverse (Boolean) (defaults to: false) —

    when true, reverses the natural order

  • ignore_case (Boolean) (defaults to: false) —

    when true, downcases sort keys before comparison

Yields:

  • (element) —

    block that returns the string to compare

Returns:

  • (Array) —

    a new sorted array



111
112
113
114
115
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 111

def self.sort_by(array, case_sensitive: false, reverse: false, ignore_case: false, &block)
  effective_case_sensitive = ignore_case ? false : case_sensitive
  result = array.sort { |a, b| compare(block.call(a), block.call(b), case_sensitive: effective_case_sensitive) }
  reverse ? result.reverse : result
end

.sort_by_stable(array, case_sensitive: false) {|element| ... } ⇒ Array

Stable sort by block result, preserving original order for equal elements.

Parameters:

  • array (Array) —

    the array to sort

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Yields:

  • (element) —

    block that returns the string to compare

Returns:

  • (Array) —

    a new sorted array with stable ordering



233
234
235
236
237
238
239
240
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 233

def self.sort_by_stable(array, case_sensitive: false, &block)
  array.each_with_index
       .sort_by do |element, index|
    key_str = block.call(element)
    [natural_key(key_str, case_sensitive: case_sensitive), index]
  end
       .map(&:first)
end

.sort_index(array, case_sensitive: false, reverse: false) ⇒ Array<Integer>

Returns an array of original indices representing the natural-sort permutation.

Parameters:

  • array (Array<String, nil>) —

    the array to sort

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

  • reverse (Boolean) (defaults to: false) —

    when true, reverses the natural order

Returns:

  • (Array<Integer>) —

    indices into the original array in natural sort order



298
299
300
301
302
303
304
305
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 298

def self.sort_index(array, case_sensitive: false, reverse: false)
  return [] if array.empty?

  result = array.each_with_index
                .sort { |(a, _), (b, _)| compare(a, b, case_sensitive: case_sensitive) }
                .map(&:last)
  reverse ? result.reverse : result
end

.sort_paths(paths, separator: '/', case_sensitive: false, reverse: false) ⇒ Array<String>

Natural sort for separator-delimited paths.

Splits each path on separator, naturally sorts the resulting segment arrays lexicographically, then returns the original path strings in sorted order. Trailing separators are preserved in the output; the split segments (with an empty trailing element) are used for comparison.

Parameters:

  • paths (Array<String>) —

    paths to sort

  • separator (String) (defaults to: '/') —

    the path separator (default ‘/’)

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

  • reverse (Boolean) (defaults to: false) —

    when true, reverses the final output order

Returns:

  • (Array<String>) —

    a new array of paths in natural-sort order



335
336
337
338
339
340
341
342
343
344
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 335

def self.sort_paths(paths, separator: '/', case_sensitive: false, reverse: false)
  decorated = paths.map do |path|
    segments = path.to_s.split(separator, -1)
    key = segments.map { |seg| natural_key(seg, case_sensitive: case_sensitive) }
    [key, path]
  end

  sorted = decorated.sort_by(&:first).map(&:last)
  reverse ? sorted.reverse : sorted
end

.sort_stable(array, case_sensitive: false) ⇒ Array<String, nil>

Stable sort that preserves original order for equal elements.

Parameters:

  • array (Array<String, nil>) —

    the array to sort

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (Array<String, nil>) —

    a new sorted array with stable ordering



122
123
124
125
126
127
128
129
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 122

def self.sort_stable(array, case_sensitive: false)
  array.each_with_index
       .sort_by do |element, index|
    [tokenize(element.nil? ? '' : element.to_s, case_sensitive: case_sensitive), element.nil? ? 0 : 1,
     index]
  end
       .map(&:first)
end

.tokenize(str, case_sensitive: false) ⇒ Array<String, Integer>

Splits a string into chunks of text and numbers for natural comparison.

Parameters:

  • str (String) —

    the string to tokenize

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (Array<String, Integer>) —

    alternating text and numeric chunks



10
11
12
13
14
15
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 10

def self.tokenize(str, case_sensitive: false)
  normalized = case_sensitive ? str : str.downcase
  normalized.scan(/\d+|[^\d]+/).map do |chunk|
    chunk.match?(/\A\d+\z/) ? chunk.to_i : chunk
  end
end

.uniq(array, case_sensitive: false) ⇒ Array<String, nil>

Deduplicates an array preserving first-occurrence order, treating elements as equal when natural comparison returns 0.

Parameters:

  • array (Array<String, nil>) —

    the array to deduplicate

  • case_sensitive (Boolean) (defaults to: false) —

    whether text comparison is case-sensitive

Returns:

  • (Array<String, nil>) —

    a new array with duplicates removed



313
314
315
316
317
318
319
320
321
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 313

def self.uniq(array, case_sensitive: false)
  result = []
  array.each do |element|
    next if result.any? { |kept| compare(kept, element, case_sensitive: case_sensitive).zero? }

    result << element
  end
  result
end