<commit_before># This file is part of NIT ( http://www.nitlanguage.org ).
#
# Copyright 2005-2008 <NAME> <<EMAIL>>
#
# This file is free software, which comes along with NIT.  This software is
# distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
# without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
# PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
# is kept unaltered, and a notification of the changes is added.
# You  are  allowed  to  redistribute it and sell it, alone or is a part of
# another product.

# This module contains classes used to compare things and sorts arrays.
#
# In order to provide your own sort class you should define a subclass of `Comparator` with
# a custom `Comparator::compare` function and a specific `COMPARED` virtual type.
module sorter

import range
import array

# This abstract class generalizes ways to sort an array
interface Comparator
	# What to compare to
	type COMPARED: nullable Object

	# Compare `a` and `b`.
	#
	# Returns:
	#
	# * -1 if a < b
	# * 0  if a = b
	# * 1  if a > b
	fun compare(a: COMPARED, b: COMPARED): Int is abstract

	# Is `seq` sorted?
	#
	#     assert default_comparator.is_sorted([1,2,2,3])   == true
	#     assert default_comparator.is_sorted([1,10,2,3])  == false
	#     assert alpha_comparator.is_sorted([1,10,2,3])    == true
	fun is_sorted(seq: SequenceRead[COMPARED]): Bool
	do
		if seq.length <= 1 then return true
		var prev = seq.first
		for e in seq do
			if compare(prev, e) > 0 then return false
			prev = e
		end
		return true
	end

	# Returns the minimum between `a` and `b`.
	#
	#     assert default_comparator.min(2,10) == 2
	#     assert alpha_comparator.min(2,10)   == 10
	#
	# If both are equivalent, then returns `a`.
	#
	#     var m = alpha_comparator.min(1, "1")
	#     assert m == 1
	#     assert m != "1"
	fun min(a,b: COMPARED): COMPARED
	do
		if compare(a,b) > 0 then return b else return a
	end

	# Returns the maximum between `a` and `b`.
	#
	#     assert default_comparator.max(2,10) == 10
	#     assert alpha_comparator.max(2,10)   == 2
	#
	# If both are equivalent, then returns `a`.
	#
	#     var m = alpha_comparator.max(1, "1")
	#     assert m == 1
	#     assert m != "1"
	fun max(a,b: COMPARED): COMPARED
	do
		if compare(a,b) < 0 then return b else return a
	end

	# Sort `array` using the `compare` function.
	#
	#     var a = [10, 2, 3, 1, 4]
	#     default_comparator.sort(a)
	#     assert a == [1, 2, 3, 4, 10]
	#     alpha_comparator.sort(a)
	#     assert a == [1, 10, 2, 3, 4]
	fun sort(array: Array[COMPARED]) do sub_sort(array, 0, array.length-1)

	# Sort `array` between `from` and `to` indices
	private fun sub_sort(array: Array[COMPARED], from: Int, to: Int)
	do
		if from >= to then
			return
		else if from + 7 < to then
			quick_sort(array, from, to)
		else
			bubble_sort(array, from, to)
		end
	end

	# Quick-sort `array` between `from` and `to` indices
	# Worst case: O(n^2), Average case: O(n lg n)
	#
	#     var a = [5, 2, 3, 1, 4]
	#     default_comparator.quick_sort(a, 0, a.length - 1)
	#     assert a == [1, 2, 3, 4, 5]
	fun quick_sort(array: Array[COMPARED], from: Int, to: Int) do
		var pivot = array[from]
		var i = from
		var j = to
		while j > i do
			while i <= to and compare(array[i], pivot) <= 0 do i += 1
			while j > i and compare(array[j], pivot) >= 0 do j -= 1
			if j > i then
				var t = array[i]
				array[i] = array[j]
				array[j] = t
			end<commit_msg>Fixed quick_sort when array is length 0 or 1<commit_after># This file is part of NIT ( http://www.nitlanguage.org ).
#
# Copyright 2005-2008 <NAME> <<EMAIL>>
#
# This file is free software, which comes along with NIT.  This software is
# distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
# without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
# PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
# is kept unaltered, and a notification of the changes is added.
# You  are  allowed  to  redistribute it and sell it, alone or is a part of
# another product.

# This module contains classes used to compare things and sorts arrays.
#
# In order to provide your own sort class you should define a subclass of `Comparator` with
# a custom `Comparator::compare` function and a specific `COMPARED` virtual type.
module sorter

import range
import array

# This abstract class generalizes ways to sort an array
interface Comparator
	# What to compare to
	type COMPARED: nullable Object

	# Compare `a` and `b`.
	#
	# Returns:
	#
	# * -1 if a < b
	# * 0  if a = b
	# * 1  if a > b
	fun compare(a: COMPARED, b: COMPARED): Int is abstract

	# Is `seq` sorted?
	#
	#     assert default_comparator.is_sorted([1,2,2,3])   == true
	#     assert default_comparator.is_sorted([1,10,2,3])  == false
	#     assert alpha_comparator.is_sorted([1,10,2,3])    == true
	fun is_sorted(seq: SequenceRead[COMPARED]): Bool
	do
		if seq.length <= 1 then return true
		var prev = seq.first
		for e in seq do
			if compare(prev, e) > 0 then return false
			prev = e
		end
		return true
	end

	# Returns the minimum between `a` and `b`.
	#
	#     assert default_comparator.min(2,10) == 2
	#     assert alpha_comparator.min(2,10)   == 10
	#
	# If both are equivalent, then returns `a`.
	#
	#     var m = alpha_comparator.min(1, "1")
	#     assert m == 1
	#     assert m != "1"
	fun min(a,b: COMPARED): COMPARED
	do
		if compare(a,b) > 0 then return b else return a
	end

	# Returns the maximum between `a` and `b`.
	#
	#     assert default_comparator.max(2,10) == 10
	#     assert alpha_comparator.max(2,10)   == 2
	#
	# If both are equivalent, then returns `a`.
	#
	#     var m = alpha_comparator.max(1, "1")
	#     assert m == 1
	#     assert m != "1"
	fun max(a,b: COMPARED): COMPARED
	do
		if compare(a,b) < 0 then return b else return a
	end

	# Sort `array` using the `compare` function.
	#
	#     var a = [10, 2, 3, 1, 4]
	#     default_comparator.sort(a)
	#     assert a == [1, 2, 3, 4, 10]
	#     alpha_comparator.sort(a)
	#     assert a == [1, 10, 2, 3, 4]
	fun sort(array: Array[COMPARED]) do sub_sort(array, 0, array.length-1)

	# Sort `array` between `from` and `to` indices
	private fun sub_sort(array: Array[COMPARED], from: Int, to: Int)
	do
		if from >= to then
			return
		else if from + 7 < to then
			quick_sort(array, from, to)
		else
			bubble_sort(array, from, to)
		end
	end

	# Quick-sort `array` between `from` and `to` indices
	# Worst case: O(n^2), Average case: O(n lg n)
	#
	#     var a = [5, 2, 3, 1, 4]
	#     default_comparator.quick_sort(a, 0, a.length - 1)
	#     assert a == [1, 2, 3, 4, 5]
	#     var a2 = new Array[Int]
	#     default_comparator.quick_sort(a2, 0, a2.length - 1)
	#     assert a2 == new Array[Int]
	#     var a3 = [1]
	#     default_comparator.quick_sort(a3, 0, a3.length - 1)
	#     assert a3 == [1]
	fun quick_sort(array: Array[COMPARED], from: Int, to: Int) do
		if from >= to then return
		var pivot = array[from]
		var i = from
		var j = to
		while j > i do
			while i <= to and compare(array[i], pivot) <= 0 do i += 1
			while j > i and compare(array[j], pivot) >= 0 do j -= 1
			if j > i then
				var t = array[i]
				array[i] = array[j]
				array[j] = t
			end
{'fraction_non_alphanumeric': 0.11927494119274941, 'fraction_numerical': 0.0279507402795074, 'mean_word_length': 2.969247666117518, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 26, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3688299', 'n_tokens_mistral': 2862, 'n_tokens_neox': 2664, 'n_words': 970}