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.12.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



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

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



238
239
240
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 238

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



166
167
168
169
170
171
172
173
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 166

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



260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 260

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



350
351
352
353
354
355
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 350

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



188
189
190
191
192
193
194
195
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 188

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

.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



205
206
207
208
209
210
211
212
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 205

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



373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 373

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



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

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



285
286
287
288
289
290
291
292
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 285

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



322
323
324
325
326
327
328
329
330
331
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 322

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



300
301
302
303
304
305
306
307
308
 
# File 'lib/philiprehberger/natural_sort/comparator.rb', line 300

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