Coverage Report

Created: 2025-12-18 07:52

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/serenity/AK/InsertionSort.h
Line
Count
Source
1
/*
2
 * Copyright (c) 2022, Marc Luqué <marc.luque@outlook.com>
3
 *
4
 * SPDX-License-Identifier: BSD-2-Clause
5
 */
6
7
#pragma once
8
9
#include <AK/Concepts.h>
10
#include <AK/StdLibExtras.h>
11
12
namespace AK {
13
14
// Standard Insertion Sort, with `end` inclusive!
15
template<typename Collection, typename Comparator, typename T = decltype(declval<Collection>()[declval<int>()])>
16
void insertion_sort(Collection& col, ssize_t start, ssize_t end, Comparator comparator)
17
requires(Indexable<Collection, T>)
18
31.1M
{
19
53.4M
    for (ssize_t i = start + 1; i <= end; ++i) {
20
45.0M
        for (ssize_t j = i; j > start && comparator(col[j], col[j - 1]); --j)
21
22.7M
            swap(col[j], col[j - 1]);
22
22.3M
    }
23
31.1M
}
void AK::insertion_sort<AK::Vector<Gfx::ColorStop, 4ul>, Gfx::GradientPaintStyle::add_color_stop(Gfx::ColorStop, bool)::{lambda(auto:1&, auto:2&)#1}, Gfx::ColorStop&>(AK::Vector<Gfx::ColorStop, 4ul>&, long, long, Gfx::GradientPaintStyle::add_color_stop(Gfx::ColorStop, bool)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<Gfx::ColorStop, 4ul>, Gfx::ColorStop&>
Line
Count
Source
18
57.5k
{
19
86.2k
    for (ssize_t i = start + 1; i <= end; ++i) {
20
28.7k
        for (ssize_t j = i; j > start && comparator(col[j], col[j - 1]); --j)
21
0
            swap(col[j], col[j - 1]);
22
28.7k
    }
23
57.5k
}
Unexecuted instantiation: DCTNaturalOrder.cpp:void AK::insertion_sort<AK::Vector<Gfx::Point<unsigned int>, 0ul>, Gfx::JPEGXL::compute_natural_ordering()::$_0, Gfx::Point<unsigned int>&>(AK::Vector<Gfx::Point<unsigned int>, 0ul>&, long, long, Gfx::JPEGXL::compute_natural_ordering()::$_0) requires Indexable<AK::Vector<Gfx::Point<unsigned int>, 0ul>, Gfx::Point<unsigned int>&>
Unexecuted instantiation: DCTNaturalOrder.cpp:void AK::insertion_sort<AK::Vector<Gfx::Point<unsigned int>, 0ul>, Gfx::JPEGXL::compute_natural_ordering()::$_1, Gfx::Point<unsigned int>&>(AK::Vector<Gfx::Point<unsigned int>, 0ul>&, long, long, Gfx::JPEGXL::compute_natural_ordering()::$_1) requires Indexable<AK::Vector<Gfx::Point<unsigned int>, 0ul>, Gfx::Point<unsigned int>&>
Unexecuted instantiation: FontDatabase.cpp:void AK::insertion_sort<AK::Vector<AK::RefPtr<Gfx::Font>, 0ul>, Gfx::FontDatabase::for_each_font(AK::Function<void (Gfx::Font const&)>)::$_0, AK::RefPtr<Gfx::Font>&>(AK::Vector<AK::RefPtr<Gfx::Font>, 0ul>&, long, long, Gfx::FontDatabase::for_each_font(AK::Function<void (Gfx::Font const&)>)::$_0) requires Indexable<AK::Vector<AK::RefPtr<Gfx::Font>, 0ul>, AK::RefPtr<Gfx::Font>&>
Unexecuted instantiation: FontDatabase.cpp:void AK::insertion_sort<AK::Vector<AK::RefPtr<Gfx::Font>, 0ul>, Gfx::FontDatabase::for_each_fixed_width_font(AK::Function<void (Gfx::Font const&)>)::$_0, AK::RefPtr<Gfx::Font>&>(AK::Vector<AK::RefPtr<Gfx::Font>, 0ul>&, long, long, Gfx::FontDatabase::for_each_fixed_width_font(AK::Function<void (Gfx::Font const&)>)::$_0) requires Indexable<AK::Vector<AK::RefPtr<Gfx::Font>, 0ul>, AK::RefPtr<Gfx::Font>&>
void AK::insertion_sort<AK::Vector<unsigned long, 0ul>, AK::quick_sort<AK::Vector<unsigned long, 0ul> >(AK::Vector<unsigned long, 0ul>&)::{lambda(auto:1&, auto:2&)#1}, unsigned long&>(AK::Vector<unsigned long, 0ul>&, long, long, AK::quick_sort<AK::Vector<unsigned long, 0ul> >(AK::Vector<unsigned long, 0ul>&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<unsigned long, 0ul>, unsigned long&>
Line
Count
Source
18
3.40k
{
19
13.6k
    for (ssize_t i = start + 1; i <= end; ++i) {
20
19.7k
        for (ssize_t j = i; j > start && comparator(col[j], col[j - 1]); --j)
21
9.52k
            swap(col[j], col[j - 1]);
22
10.2k
    }
23
3.40k
}
Unexecuted instantiation: AST.cpp:void AK::insertion_sort<AK::Vector<JS::ImportAttribute, 0ul>, JS::ModuleRequest::ModuleRequest(AK::DeprecatedFlyString, AK::Vector<JS::ImportAttribute, 0ul>)::$_0, JS::ImportAttribute&>(AK::Vector<JS::ImportAttribute, 0ul>&, long, long, JS::ModuleRequest::ModuleRequest(AK::DeprecatedFlyString, AK::Vector<JS::ImportAttribute, 0ul>)::$_0) requires Indexable<AK::Vector<JS::ImportAttribute, 0ul>, JS::ImportAttribute&>
Unexecuted instantiation: Generator.cpp:void AK::insertion_sort<AK::Vector<JS::Bytecode::Executable::ExceptionHandlers, 0ul>, JS::Bytecode::Generator::compile(JS::VM&, JS::ASTNode const&, JS::FunctionKind, JS::GCPtr<JS::ECMAScriptFunctionObject const>, JS::Bytecode::Generator::MustPropagateCompletion, AK::Vector<AK::DeprecatedFlyString, 0ul>)::$_2, JS::Bytecode::Executable::ExceptionHandlers&>(AK::Vector<JS::Bytecode::Executable::ExceptionHandlers, 0ul>&, long, long, JS::Bytecode::Generator::compile(JS::VM&, JS::ASTNode const&, JS::FunctionKind, JS::GCPtr<JS::ECMAScriptFunctionObject const>, JS::Bytecode::Generator::MustPropagateCompletion, AK::Vector<AK::DeprecatedFlyString, 0ul>)::$_2) requires Indexable<AK::Vector<JS::Bytecode::Executable::ExceptionHandlers, 0ul>, JS::Bytecode::Executable::ExceptionHandlers&>
Unexecuted instantiation: void AK::insertion_sort<AK::Vector<unsigned int, 0ul>, AK::quick_sort<AK::Vector<unsigned int, 0ul> >(AK::Vector<unsigned int, 0ul>&)::{lambda(auto:1&, auto:2&)#1}, unsigned int&>(AK::Vector<unsigned int, 0ul>&, long, long, AK::quick_sort<AK::Vector<unsigned int, 0ul> >(AK::Vector<unsigned int, 0ul>&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<unsigned int, 0ul>, unsigned int&>
Unexecuted instantiation: void AK::insertion_sort<AK::Vector<AK::String, 0ul>, AK::quick_sort<AK::Vector<AK::String, 0ul> >(AK::Vector<AK::String, 0ul>&)::{lambda(auto:1&, auto:2&)#1}, AK::String&>(AK::Vector<AK::String, 0ul>&, long, long, AK::quick_sort<AK::Vector<AK::String, 0ul> >(AK::Vector<AK::String, 0ul>&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<AK::String, 0ul>, AK::String&>
Unexecuted instantiation: void AK::insertion_sort<AK::Vector<AK::StringView, 0ul>, AK::quick_sort<AK::Vector<AK::StringView, 0ul> >(AK::Vector<AK::StringView, 0ul>&)::{lambda(auto:1&, auto:2&)#1}, AK::StringView&>(AK::Vector<AK::StringView, 0ul>&, long, long, AK::quick_sort<AK::Vector<AK::StringView, 0ul> >(AK::Vector<AK::StringView, 0ul>&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<AK::StringView, 0ul>, AK::StringView&>
Unexecuted instantiation: ModuleNamespaceObject.cpp:void AK::insertion_sort<AK::Vector<AK::DeprecatedFlyString, 0ul>, JS::ModuleNamespaceObject::ModuleNamespaceObject(JS::Realm&, JS::Module*, AK::Vector<AK::DeprecatedFlyString, 0ul>)::$_0, AK::DeprecatedFlyString&>(AK::Vector<AK::DeprecatedFlyString, 0ul>&, long, long, JS::ModuleNamespaceObject::ModuleNamespaceObject(JS::Realm&, JS::Module*, AK::Vector<AK::DeprecatedFlyString, 0ul>)::$_0) requires Indexable<AK::Vector<AK::DeprecatedFlyString, 0ul>, AK::DeprecatedFlyString&>
Unexecuted instantiation: SourceTextModule.cpp:void AK::insertion_sort<AK::Vector<JS::module_requests(JS::Program&)::RequestedModuleAndSourceIndex, 0ul>, JS::module_requests(JS::Program&)::$_0, JS::module_requests(JS::Program&)::RequestedModuleAndSourceIndex&>(AK::Vector<JS::module_requests(JS::Program&)::RequestedModuleAndSourceIndex, 0ul>&, long, long, JS::module_requests(JS::Program&)::$_0) requires Indexable<AK::Vector<JS::module_requests(JS::Program&)::RequestedModuleAndSourceIndex, 0ul>, JS::module_requests(JS::Program&)::RequestedModuleAndSourceIndex&>
void AK::insertion_sort<AK::Vector<regex::Detail::Block, 0ul>, regex::Regex<regex::PosixBasicParser>::split_basic_blocks(regex::ByteCode const&)::{lambda(auto:1&, auto:2&)#1}, regex::Detail::Block&>(AK::Vector<regex::Detail::Block, 0ul>&, long, long, regex::Regex<regex::PosixBasicParser>::split_basic_blocks(regex::ByteCode const&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<regex::Detail::Block, 0ul>, regex::Detail::Block&>
Line
Count
Source
18
29.7M
{
19
50.4M
    for (ssize_t i = start + 1; i <= end; ++i) {
20
43.1M
        for (ssize_t j = i; j > start && comparator(col[j], col[j - 1]); --j)
21
22.4M
            swap(col[j], col[j - 1]);
22
20.7M
    }
23
29.7M
}
void AK::insertion_sort<AK::Vector<regex::Regex<regex::PosixBasicParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock, 0ul>, regex::Regex<regex::PosixBasicParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::{lambda(auto:1&, auto:2&)#1}, regex::Regex<regex::PosixBasicParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock&>(AK::Vector<regex::Regex<regex::PosixBasicParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock, 0ul>&, long, long, regex::Regex<regex::PosixBasicParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<regex::Regex<regex::PosixBasicParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock, 0ul>, regex::Regex<regex::PosixBasicParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock&>
Line
Count
Source
18
1.47k
{
19
1.47k
    for (ssize_t i = start + 1; i <= end; ++i) {
20
0
        for (ssize_t j = i; j > start && comparator(col[j], col[j - 1]); --j)
21
0
            swap(col[j], col[j - 1]);
22
0
    }
23
1.47k
}
void AK::insertion_sort<AK::Vector<regex::Detail::Block, 0ul>, regex::Regex<regex::PosixExtendedParser>::split_basic_blocks(regex::ByteCode const&)::{lambda(auto:1&, auto:2&)#1}, regex::Detail::Block&>(AK::Vector<regex::Detail::Block, 0ul>&, long, long, regex::Regex<regex::PosixExtendedParser>::split_basic_blocks(regex::ByteCode const&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<regex::Detail::Block, 0ul>, regex::Detail::Block&>
Line
Count
Source
18
600k
{
19
1.36M
    for (ssize_t i = start + 1; i <= end; ++i) {
20
875k
        for (ssize_t j = i; j > start && comparator(col[j], col[j - 1]); --j)
21
110k
            swap(col[j], col[j - 1]);
22
765k
    }
23
600k
}
void AK::insertion_sort<AK::Vector<regex::Regex<regex::PosixExtendedParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock, 0ul>, regex::Regex<regex::PosixExtendedParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::{lambda(auto:1&, auto:2&)#1}, regex::Regex<regex::PosixExtendedParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock&>(AK::Vector<regex::Regex<regex::PosixExtendedParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock, 0ul>&, long, long, regex::Regex<regex::PosixExtendedParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<regex::Regex<regex::PosixExtendedParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock, 0ul>, regex::Regex<regex::PosixExtendedParser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock&>
Line
Count
Source
18
150
{
19
150
    for (ssize_t i = start + 1; i <= end; ++i) {
20
0
        for (ssize_t j = i; j > start && comparator(col[j], col[j - 1]); --j)
21
0
            swap(col[j], col[j - 1]);
22
0
    }
23
150
}
void AK::insertion_sort<AK::Vector<regex::Detail::Block, 0ul>, regex::Regex<regex::ECMA262Parser>::split_basic_blocks(regex::ByteCode const&)::{lambda(auto:1&, auto:2&)#1}, regex::Detail::Block&>(AK::Vector<regex::Detail::Block, 0ul>&, long, long, regex::Regex<regex::ECMA262Parser>::split_basic_blocks(regex::ByteCode const&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<regex::Detail::Block, 0ul>, regex::Detail::Block&>
Line
Count
Source
18
739k
{
19
1.50M
    for (ssize_t i = start + 1; i <= end; ++i) {
20
961k
        for (ssize_t j = i; j > start && comparator(col[j], col[j - 1]); --j)
21
198k
            swap(col[j], col[j - 1]);
22
762k
    }
23
739k
}
void AK::insertion_sort<AK::Vector<regex::Regex<regex::ECMA262Parser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock, 0ul>, regex::Regex<regex::ECMA262Parser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::{lambda(auto:1&, auto:2&)#1}, regex::Regex<regex::ECMA262Parser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock&>(AK::Vector<regex::Regex<regex::ECMA262Parser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock, 0ul>&, long, long, regex::Regex<regex::ECMA262Parser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<regex::Regex<regex::ECMA262Parser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock, 0ul>, regex::Regex<regex::ECMA262Parser>::attempt_rewrite_loops_as_atomic_groups(AK::Vector<regex::Detail::Block, 0ul> const&)::CandidateBlock&>
Line
Count
Source
18
299
{
19
299
    for (ssize_t i = start + 1; i <= end; ++i) {
20
0
        for (ssize_t j = i; j > start && comparator(col[j], col[j - 1]); --j)
21
0
            swap(col[j], col[j - 1]);
22
0
    }
23
299
}
Unexecuted instantiation: Locale.cpp:void AK::insertion_sort<AK::Vector<AK::Variant<Locale::LocaleExtension, Locale::TransformedExtension, Locale::OtherExtension>, 0ul>, Locale::transform_unicode_locale_id_to_canonical_syntax(Locale::LocaleID&)::$_3, AK::Variant<Locale::LocaleExtension, Locale::TransformedExtension, Locale::OtherExtension>&>(AK::Vector<AK::Variant<Locale::LocaleExtension, Locale::TransformedExtension, Locale::OtherExtension>, 0ul>&, long, long, Locale::transform_unicode_locale_id_to_canonical_syntax(Locale::LocaleID&)::$_3) requires Indexable<AK::Vector<AK::Variant<Locale::LocaleExtension, Locale::TransformedExtension, Locale::OtherExtension>, 0ul>, AK::Variant<Locale::LocaleExtension, Locale::TransformedExtension, Locale::OtherExtension>&>
Unexecuted instantiation: Locale.cpp:void AK::insertion_sort<AK::Vector<Locale::Keyword, 0ul>, Locale::transform_unicode_locale_id_to_canonical_syntax(Locale::LocaleID&)::$_0::operator()(Locale::LocaleExtension&) const::{lambda(auto:1 const&, auto:2 const&)#1}, Locale::Keyword&>(AK::Vector<Locale::Keyword, 0ul>&, long, long, Locale::transform_unicode_locale_id_to_canonical_syntax(Locale::LocaleID&)::$_0::operator()(Locale::LocaleExtension&) const::{lambda(auto:1 const&, auto:2 const&)#1}) requires Indexable<AK::Vector<Locale::Keyword, 0ul>, Locale::Keyword&>
Unexecuted instantiation: Locale.cpp:void AK::insertion_sort<AK::Vector<Locale::TransformedField, 0ul>, Locale::transform_unicode_locale_id_to_canonical_syntax(Locale::LocaleID&)::$_1::operator()(Locale::TransformedExtension&) const::{lambda(auto:1 const&, auto:2 const&)#1}, Locale::TransformedField&>(AK::Vector<Locale::TransformedField, 0ul>&, long, long, Locale::transform_unicode_locale_id_to_canonical_syntax(Locale::LocaleID&)::$_1::operator()(Locale::TransformedExtension&) const::{lambda(auto:1 const&, auto:2 const&)#1}) requires Indexable<AK::Vector<Locale::TransformedField, 0ul>, Locale::TransformedField&>
Unexecuted instantiation: void AK::insertion_sort<AK::Vector<AK::ByteString, 0ul>, AK::quick_sort<AK::Vector<AK::ByteString, 0ul> >(AK::Vector<AK::ByteString, 0ul>&)::{lambda(auto:1&, auto:2&)#1}, AK::ByteString&>(AK::Vector<AK::ByteString, 0ul>&, long, long, AK::quick_sort<AK::Vector<AK::ByteString, 0ul> >(AK::Vector<AK::ByteString, 0ul>&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<AK::ByteString, 0ul>, AK::ByteString&>
Unexecuted instantiation: void AK::insertion_sort<AK::Vector<Shell::Shell::RunnablePath, 256ul>, AK::quick_sort<AK::Vector<Shell::Shell::RunnablePath, 256ul> >(AK::Vector<Shell::Shell::RunnablePath, 256ul>&)::{lambda(auto:1&, auto:2&)#1}, Shell::Shell::RunnablePath&>(AK::Vector<Shell::Shell::RunnablePath, 256ul>&, long, long, AK::quick_sort<AK::Vector<Shell::Shell::RunnablePath, 256ul> >(AK::Vector<Shell::Shell::RunnablePath, 256ul>&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<Shell::Shell::RunnablePath, 256ul>, Shell::Shell::RunnablePath&>
Unexecuted instantiation: Shell.cpp:void AK::insertion_sort<AK::Vector<Line::CompletionSuggestion, 0ul>, Shell::Shell::complete_path(AK::StringView, AK::StringView, unsigned long, Shell::Shell::ExecutableOnly, Shell::AST::Node const*, Shell::AST::Node const*, Shell::Shell::EscapeMode)::$_0, Line::CompletionSuggestion&>(AK::Vector<Line::CompletionSuggestion, 0ul>&, long, long, Shell::Shell::complete_path(AK::StringView, AK::StringView, unsigned long, Shell::Shell::ExecutableOnly, Shell::AST::Node const*, Shell::AST::Node const*, Shell::Shell::EscapeMode)::$_0) requires Indexable<AK::Vector<Line::CompletionSuggestion, 0ul>, Line::CompletionSuggestion&>
Unexecuted instantiation: void AK::insertion_sort<AK::Vector<float, 0ul>, AK::quick_sort<AK::Vector<float, 0ul> >(AK::Vector<float, 0ul>&)::{lambda(auto:1&, auto:2&)#1}, float&>(AK::Vector<float, 0ul>&, long, long, AK::quick_sort<AK::Vector<float, 0ul> >(AK::Vector<float, 0ul>&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<float, 0ul>, float&>
Unexecuted instantiation: Builtin.cpp:void AK::insertion_sort<AK::Vector<Shell::Shell::builtin_set(Main::Arguments)::Variable, 0ul>, Shell::Shell::builtin_set(Main::Arguments)::$_0, Shell::Shell::builtin_set(Main::Arguments)::Variable&>(AK::Vector<Shell::Shell::builtin_set(Main::Arguments)::Variable, 0ul>&, long, long, Shell::Shell::builtin_set(Main::Arguments)::$_0) requires Indexable<AK::Vector<Shell::Shell::builtin_set(Main::Arguments)::Variable, 0ul>, Shell::Shell::builtin_set(Main::Arguments)::Variable&>
Unexecuted instantiation: Builtin.cpp:void AK::insertion_sort<AK::Vector<AK::String, 0ul>, Shell::Shell::builtin_set(Main::Arguments)::$_1, AK::String&>(AK::Vector<AK::String, 0ul>&, long, long, Shell::Shell::builtin_set(Main::Arguments)::$_1) requires Indexable<AK::Vector<AK::String, 0ul>, AK::String&>
Unexecuted instantiation: Image.cpp:void AK::insertion_sort<AK::Vector<ELF::Image::SortedSymbol, 0ul>, ELF::Image::sort_symbols() const::$_1, ELF::Image::SortedSymbol&>(AK::Vector<ELF::Image::SortedSymbol, 0ul>&, long, long, ELF::Image::sort_symbols() const::$_1) requires Indexable<AK::Vector<ELF::Image::SortedSymbol, 0ul>, ELF::Image::SortedSymbol&>
Unexecuted instantiation: void AK::insertion_sort<AK::Vector<Web::Painting::ColorStop, 4ul>, Web::Painting::SVGGradientPaintStyle::add_color_stop(Web::Painting::ColorStop, bool)::{lambda(auto:1&, auto:2&)#1}, Web::Painting::ColorStop&>(AK::Vector<Web::Painting::ColorStop, 4ul>&, long, long, Web::Painting::SVGGradientPaintStyle::add_color_stop(Web::Painting::ColorStop, bool)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<Web::Painting::ColorStop, 4ul>, Web::Painting::ColorStop&>
Unexecuted instantiation: Parser.cpp:void AK::insertion_sort<AK::Vector<Web::CSS::ValueComparingNonnullRefPtr<Web::CSS::CSSStyleValue const>, 0ul>, Web::CSS::Parser::Parser::parse_font_feature_settings_value(Web::CSS::Parser::TokenStream<Web::CSS::Parser::ComponentValue>&)::$_0, Web::CSS::ValueComparingNonnullRefPtr<Web::CSS::CSSStyleValue const>&>(AK::Vector<Web::CSS::ValueComparingNonnullRefPtr<Web::CSS::CSSStyleValue const>, 0ul>&, long, long, Web::CSS::Parser::Parser::parse_font_feature_settings_value(Web::CSS::Parser::TokenStream<Web::CSS::Parser::ComponentValue>&)::$_0) requires Indexable<AK::Vector<Web::CSS::ValueComparingNonnullRefPtr<Web::CSS::CSSStyleValue const>, 0ul>, Web::CSS::ValueComparingNonnullRefPtr<Web::CSS::CSSStyleValue const>&>
Unexecuted instantiation: Parser.cpp:void AK::insertion_sort<AK::Vector<Web::CSS::ValueComparingNonnullRefPtr<Web::CSS::CSSStyleValue const>, 0ul>, Web::CSS::Parser::Parser::parse_font_variation_settings_value(Web::CSS::Parser::TokenStream<Web::CSS::Parser::ComponentValue>&)::$_0, Web::CSS::ValueComparingNonnullRefPtr<Web::CSS::CSSStyleValue const>&>(AK::Vector<Web::CSS::ValueComparingNonnullRefPtr<Web::CSS::CSSStyleValue const>, 0ul>&, long, long, Web::CSS::Parser::Parser::parse_font_variation_settings_value(Web::CSS::Parser::TokenStream<Web::CSS::Parser::ComponentValue>&)::$_0) requires Indexable<AK::Vector<Web::CSS::ValueComparingNonnullRefPtr<Web::CSS::CSSStyleValue const>, 0ul>, Web::CSS::ValueComparingNonnullRefPtr<Web::CSS::CSSStyleValue const>&>
Unexecuted instantiation: StyleComputer.cpp:void AK::insertion_sort<AK::Vector<Web::CSS::MatchingRule, 0ul>, Web::CSS::sort_matching_rules(AK::Vector<Web::CSS::MatchingRule, 0ul>&)::$_0, Web::CSS::MatchingRule&>(AK::Vector<Web::CSS::MatchingRule, 0ul>&, long, long, Web::CSS::sort_matching_rules(AK::Vector<Web::CSS::MatchingRule, 0ul>&)::$_0) requires Indexable<AK::Vector<Web::CSS::MatchingRule, 0ul>, Web::CSS::MatchingRule&>
Unexecuted instantiation: StyleComputer.cpp:void AK::insertion_sort<AK::Vector<Web::CSS::StyleComputer::MatchingFontCandidate, 0ul>, Web::CSS::StyleComputer::font_matching_algorithm(Web::CSS::FontFaceKey const&, float) const::$_3, Web::CSS::StyleComputer::MatchingFontCandidate&>(AK::Vector<Web::CSS::StyleComputer::MatchingFontCandidate, 0ul>&, long, long, Web::CSS::StyleComputer::font_matching_algorithm(Web::CSS::FontFaceKey const&, float) const::$_3) requires Indexable<AK::Vector<Web::CSS::StyleComputer::MatchingFontCandidate, 0ul>, Web::CSS::StyleComputer::MatchingFontCandidate&>
Unexecuted instantiation: Animatable.cpp:void AK::insertion_sort<AK::Vector<JS::NonnullGCPtr<Web::Animations::Animation>, 0ul>, Web::Animations::Animatable::get_animations_internal(Web::Animations::GetAnimationsOptions)::$_0, JS::NonnullGCPtr<Web::Animations::Animation>&>(AK::Vector<JS::NonnullGCPtr<Web::Animations::Animation>, 0ul>&, long, long, Web::Animations::Animatable::get_animations_internal(Web::Animations::GetAnimationsOptions)::$_0) requires Indexable<AK::Vector<JS::NonnullGCPtr<Web::Animations::Animation>, 0ul>, JS::NonnullGCPtr<Web::Animations::Animation>&>
Unexecuted instantiation: KeyframeEffect.cpp:void AK::insertion_sort<AK::Vector<Web::Animations::BaseKeyframe, 0ul>, Web::Animations::process_a_keyframes_argument(JS::Realm&, JS::GCPtr<JS::Object>)::$_0, Web::Animations::BaseKeyframe&>(AK::Vector<Web::Animations::BaseKeyframe, 0ul>&, long, long, Web::Animations::process_a_keyframes_argument(JS::Realm&, JS::GCPtr<JS::Object>)::$_0) requires Indexable<AK::Vector<Web::Animations::BaseKeyframe, 0ul>, Web::Animations::BaseKeyframe&>
Unexecuted instantiation: Document.cpp:void AK::insertion_sort<AK::Vector<Web::DOM::Document::PendingAnimationEvent, 0ul>, Web::DOM::Document::update_animations_and_send_events(AK::Optional<double> const&)::$_0, Web::DOM::Document::PendingAnimationEvent&>(AK::Vector<Web::DOM::Document::PendingAnimationEvent, 0ul>&, long, long, Web::DOM::Document::update_animations_and_send_events(AK::Optional<double> const&)::$_0) requires Indexable<AK::Vector<Web::DOM::Document::PendingAnimationEvent, 0ul>, Web::DOM::Document::PendingAnimationEvent&>
Unexecuted instantiation: Document.cpp:void AK::insertion_sort<AK::Vector<JS::NonnullGCPtr<Web::Animations::Animation>, 0ul>, Web::DOM::Document::remove_replaced_animations()::$_0, JS::NonnullGCPtr<Web::Animations::Animation>&>(AK::Vector<JS::NonnullGCPtr<Web::Animations::Animation>, 0ul>&, long, long, Web::DOM::Document::remove_replaced_animations()::$_0) requires Indexable<AK::Vector<JS::NonnullGCPtr<Web::Animations::Animation>, 0ul>, JS::NonnullGCPtr<Web::Animations::Animation>&>
Unexecuted instantiation: URLSearchParams.cpp:void AK::insertion_sort<AK::Vector<Web::DOMURL::QueryParam, 0ul>, Web::DOMURL::URLSearchParams::sort()::$_0, Web::DOMURL::QueryParam&>(AK::Vector<Web::DOMURL::QueryParam, 0ul>&, long, long, Web::DOMURL::URLSearchParams::sort()::$_0) requires Indexable<AK::Vector<Web::DOMURL::QueryParam, 0ul>, Web::DOMURL::QueryParam&>
Unexecuted instantiation: Headers.cpp:void AK::insertion_sort<AK::Vector<AK::Detail::ByteBuffer<32ul>, 0ul>, Web::Fetch::Infrastructure::convert_header_names_to_a_sorted_lowercase_set(AK::Span<AK::Span<unsigned char const> >)::$_0, AK::Detail::ByteBuffer<32ul>&>(AK::Vector<AK::Detail::ByteBuffer<32ul>, 0ul>&, long, long, Web::Fetch::Infrastructure::convert_header_names_to_a_sorted_lowercase_set(AK::Span<AK::Span<unsigned char const> >)::$_0) requires Indexable<AK::Vector<AK::Detail::ByteBuffer<32ul>, 0ul>, AK::Detail::ByteBuffer<32ul>&>
Unexecuted instantiation: void AK::insertion_sort<AK::Vector<Web::Bindings::KeyUsage, 0ul>, AK::quick_sort<AK::Vector<Web::Bindings::KeyUsage, 0ul> >(AK::Vector<Web::Bindings::KeyUsage, 0ul>&)::{lambda(auto:1&, auto:2&)#1}, Web::Bindings::KeyUsage&>(AK::Vector<Web::Bindings::KeyUsage, 0ul>&, long, long, AK::quick_sort<AK::Vector<Web::Bindings::KeyUsage, 0ul> >(AK::Vector<Web::Bindings::KeyUsage, 0ul>&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<Web::Bindings::KeyUsage, 0ul>, Web::Bindings::KeyUsage&>
Unexecuted instantiation: HTMLFormElement.cpp:void AK::insertion_sort<AK::Vector<Web::HTML::HTMLFormElement::supported_property_names() const::SourcedName, 0ul>, Web::HTML::HTMLFormElement::supported_property_names() const::$_0, Web::HTML::HTMLFormElement::supported_property_names() const::SourcedName&>(AK::Vector<Web::HTML::HTMLFormElement::supported_property_names() const::SourcedName, 0ul>&, long, long, Web::HTML::HTMLFormElement::supported_property_names() const::$_0) requires Indexable<AK::Vector<Web::HTML::HTMLFormElement::supported_property_names() const::SourcedName, 0ul>, Web::HTML::HTMLFormElement::supported_property_names() const::SourcedName&>
Unexecuted instantiation: SourceSet.cpp:void AK::insertion_sort<AK::Vector<Web::HTML::ImageSource, 0ul>, Web::HTML::SourceSet::select_an_image_source()::$_0, Web::HTML::ImageSource&>(AK::Vector<Web::HTML::ImageSource, 0ul>&, long, long, Web::HTML::SourceSet::select_an_image_source()::$_0) requires Indexable<AK::Vector<Web::HTML::ImageSource, 0ul>, Web::HTML::ImageSource&>
Unexecuted instantiation: void AK::insertion_sort<AK::Vector<int, 0ul>, AK::quick_sort<AK::Vector<int, 0ul> >(AK::Vector<int, 0ul>&)::{lambda(auto:1&, auto:2&)#1}, int&>(AK::Vector<int, 0ul>&, long, long, AK::quick_sort<AK::Vector<int, 0ul> >(AK::Vector<int, 0ul>&)::{lambda(auto:1&, auto:2&)#1}) requires Indexable<AK::Vector<int, 0ul>, int&>
Unexecuted instantiation: WindowOrWorkerGlobalScope.cpp:void AK::insertion_sort<AK::Vector<JS::Handle<Web::PerformanceTimeline::PerformanceEntry>, 0ul>, Web::HTML::WindowOrWorkerGlobalScopeMixin::filter_buffer_map_by_name_and_type(AK::Optional<AK::String>, AK::Optional<AK::String>) const::$_0, JS::Handle<Web::PerformanceTimeline::PerformanceEntry>&>(AK::Vector<JS::Handle<Web::PerformanceTimeline::PerformanceEntry>, 0ul>&, long, long, Web::HTML::WindowOrWorkerGlobalScopeMixin::filter_buffer_map_by_name_and_type(AK::Optional<AK::String>, AK::Optional<AK::String>) const::$_0) requires Indexable<AK::Vector<JS::Handle<Web::PerformanceTimeline::PerformanceEntry>, 0ul>, JS::Handle<Web::PerformanceTimeline::PerformanceEntry>&>
Unexecuted instantiation: IntersectionObserver.cpp:void AK::insertion_sort<AK::Vector<double, 0ul>, Web::IntersectionObserver::IntersectionObserver::construct_impl(JS::Realm&, JS::GCPtr<Web::WebIDL::CallbackType>, Web::IntersectionObserver::IntersectionObserverInit const&)::$_0, double&>(AK::Vector<double, 0ul>&, long, long, Web::IntersectionObserver::IntersectionObserver::construct_impl(JS::Realm&, JS::GCPtr<Web::WebIDL::CallbackType>, Web::IntersectionObserver::IntersectionObserverInit const&)::$_0) requires Indexable<AK::Vector<double, 0ul>, double&>
Unexecuted instantiation: FlexFormattingContext.cpp:void AK::insertion_sort<AK::Vector<int, 0ul>, Web::Layout::FlexFormattingContext::generate_anonymous_flex_items()::$_1, int&>(AK::Vector<int, 0ul>&, long, long, Web::Layout::FlexFormattingContext::generate_anonymous_flex_items()::$_1) requires Indexable<AK::Vector<int, 0ul>, int&>
Unexecuted instantiation: FlexFormattingContext.cpp:void AK::insertion_sort<AK::Vector<int, 0ul>, Web::Layout::FlexFormattingContext::generate_anonymous_flex_items()::$_2, int&>(AK::Vector<int, 0ul>&, long, long, Web::Layout::FlexFormattingContext::generate_anonymous_flex_items()::$_2) requires Indexable<AK::Vector<int, 0ul>, int&>
Unexecuted instantiation: GridFormattingContext.cpp:void AK::insertion_sort<AK::Vector<int, 0ul>, Web::Layout::GridFormattingContext::place_grid_items()::$_1, int&>(AK::Vector<int, 0ul>&, long, long, Web::Layout::GridFormattingContext::place_grid_items()::$_1) requires Indexable<AK::Vector<int, 0ul>, int&>
Unexecuted instantiation: Dump.cpp:void AK::insertion_sort<AK::Vector<Web::dump_tree(AK::StringBuilder&, Web::Layout::Node const&, bool, bool, bool)::NameAndValue, 0ul>, Web::dump_tree(AK::StringBuilder&, Web::Layout::Node const&, bool, bool, bool)::$_2, Web::dump_tree(AK::StringBuilder&, Web::Layout::Node const&, bool, bool, bool)::NameAndValue&>(AK::Vector<Web::dump_tree(AK::StringBuilder&, Web::Layout::Node const&, bool, bool, bool)::NameAndValue, 0ul>&, long, long, Web::dump_tree(AK::StringBuilder&, Web::Layout::Node const&, bool, bool, bool)::$_2) requires Indexable<AK::Vector<Web::dump_tree(AK::StringBuilder&, Web::Layout::Node const&, bool, bool, bool)::NameAndValue, 0ul>, Web::dump_tree(AK::StringBuilder&, Web::Layout::Node const&, bool, bool, bool)::NameAndValue&>
Unexecuted instantiation: StackingContext.cpp:void AK::insertion_sort<AK::Vector<Web::Painting::StackingContext*, 0ul>, Web::Painting::StackingContext::sort()::$_0, Web::Painting::StackingContext*&>(AK::Vector<Web::Painting::StackingContext*, 0ul>&, long, long, Web::Painting::StackingContext::sort()::$_0) requires Indexable<AK::Vector<Web::Painting::StackingContext*, 0ul>, Web::Painting::StackingContext*&>
Unexecuted instantiation: TableBordersPainting.cpp:void AK::insertion_sort<AK::Vector<Web::Painting::BorderEdgePaintingInfo, 0ul>, Web::Painting::paint_collected_edges(Web::PaintContext&, AK::Vector<Web::Painting::BorderEdgePaintingInfo, 0ul>&)::$_0, Web::Painting::BorderEdgePaintingInfo&>(AK::Vector<Web::Painting::BorderEdgePaintingInfo, 0ul>&, long, long, Web::Painting::paint_collected_edges(Web::PaintContext&, AK::Vector<Web::Painting::BorderEdgePaintingInfo, 0ul>&)::$_0) requires Indexable<AK::Vector<Web::Painting::BorderEdgePaintingInfo, 0ul>, Web::Painting::BorderEdgePaintingInfo&>
Unexecuted instantiation: PerformanceObserverEntryList.cpp:void AK::insertion_sort<AK::Vector<JS::Handle<Web::PerformanceTimeline::PerformanceEntry>, 0ul>, Web::PerformanceTimeline::filter_buffer_by_name_and_type(AK::Vector<JS::NonnullGCPtr<Web::PerformanceTimeline::PerformanceEntry>, 0ul> const&, AK::Optional<AK::String>, AK::Optional<AK::String>)::$_0, JS::Handle<Web::PerformanceTimeline::PerformanceEntry>&>(AK::Vector<JS::Handle<Web::PerformanceTimeline::PerformanceEntry>, 0ul>&, long, long, Web::PerformanceTimeline::filter_buffer_by_name_and_type(AK::Vector<JS::NonnullGCPtr<Web::PerformanceTimeline::PerformanceEntry>, 0ul> const&, AK::Optional<AK::String>, AK::Optional<AK::String>)::$_0) requires Indexable<AK::Vector<JS::Handle<Web::PerformanceTimeline::PerformanceEntry>, 0ul>, JS::Handle<Web::PerformanceTimeline::PerformanceEntry>&>
Unexecuted instantiation: XMLHttpRequest.cpp:void AK::insertion_sort<AK::Vector<Web::Fetch::Infrastructure::Header, 0ul>, Web::XHR::XMLHttpRequest::get_all_response_headers() const::$_0, Web::Fetch::Infrastructure::Header&>(AK::Vector<Web::Fetch::Infrastructure::Header, 0ul>&, long, long, Web::XHR::XMLHttpRequest::get_all_response_headers() const::$_0) requires Indexable<AK::Vector<Web::Fetch::Infrastructure::Header, 0ul>, Web::Fetch::Infrastructure::Header&>
24
25
template<typename Collection, typename Comparator, typename T = decltype(declval<Collection>()[declval<int>()])>
26
void insertion_sort(Collection& collection, Comparator comparator)
27
requires(Indexable<Collection, T>)
28
0
{
29
0
    if (collection.size() == 0)
30
0
        return;
31
0
    insertion_sort(collection, 0, collection.size() - 1, move(comparator));
32
0
}
Unexecuted instantiation: Document.cpp:void AK::insertion_sort<AK::Vector<Web::DOM::Document::PendingAnimationEvent, 0ul>, Web::DOM::Document::update_animations_and_send_events(AK::Optional<double> const&)::$_0, Web::DOM::Document::PendingAnimationEvent&>(AK::Vector<Web::DOM::Document::PendingAnimationEvent, 0ul>&, Web::DOM::Document::update_animations_and_send_events(AK::Optional<double> const&)::$_0) requires Indexable<AK::Vector<Web::DOM::Document::PendingAnimationEvent, 0ul>, Web::DOM::Document::PendingAnimationEvent&>
Unexecuted instantiation: URLSearchParams.cpp:void AK::insertion_sort<AK::Vector<Web::DOMURL::QueryParam, 0ul>, Web::DOMURL::URLSearchParams::sort()::$_0, Web::DOMURL::QueryParam&>(AK::Vector<Web::DOMURL::QueryParam, 0ul>&, Web::DOMURL::URLSearchParams::sort()::$_0) requires Indexable<AK::Vector<Web::DOMURL::QueryParam, 0ul>, Web::DOMURL::QueryParam&>
33
34
template<typename Collection, typename T = decltype(declval<Collection>()[declval<int>()])>
35
void insertion_sort(Collection& collection)
36
requires(Indexable<Collection, T>)
37
{
38
    if (collection.size() == 0)
39
        return;
40
    insertion_sort(collection, 0, collection.size() - 1, [](auto& a, auto& b) { return a < b; });
41
}
42
43
}
44
45
using AK::insertion_sort;