1 | /** @file
|
---|
2 | * IPRT / No-CRT - Minimal C++ algorithm header.
|
---|
3 | */
|
---|
4 |
|
---|
5 | /*
|
---|
6 | * Copyright (C) 2022 Oracle Corporation
|
---|
7 | *
|
---|
8 | * This file is part of VirtualBox Open Source Edition (OSE), as
|
---|
9 | * available from http://www.alldomusa.eu.org. This file is free software;
|
---|
10 | * you can redistribute it and/or modify it under the terms of the GNU
|
---|
11 | * General Public License (GPL) as published by the Free Software
|
---|
12 | * Foundation, in version 2 as it comes in the "COPYING" file of the
|
---|
13 | * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
|
---|
14 | * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
|
---|
15 | *
|
---|
16 | * The contents of this file may alternatively be used under the terms
|
---|
17 | * of the Common Development and Distribution License Version 1.0
|
---|
18 | * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
|
---|
19 | * VirtualBox OSE distribution, in which case the provisions of the
|
---|
20 | * CDDL are applicable instead of those of the GPL.
|
---|
21 | *
|
---|
22 | * You may elect to license modified versions of this file under the
|
---|
23 | * terms and conditions of either the GPL or the CDDL or both.
|
---|
24 | */
|
---|
25 |
|
---|
26 | #ifndef IPRT_INCLUDED_nocrt_algorithm
|
---|
27 | #define IPRT_INCLUDED_nocrt_algorithm
|
---|
28 | #ifndef RT_WITHOUT_PRAGMA_ONCE
|
---|
29 | # pragma once
|
---|
30 | #endif
|
---|
31 |
|
---|
32 | #ifdef _MSC_VER
|
---|
33 | # pragma warning(push)
|
---|
34 | # pragma warning(disable: 4643) /* warning C4643: Forward declaring 'ios_base' in namespace std is not permitted by the C++ Standard */
|
---|
35 | #endif
|
---|
36 |
|
---|
37 | namespace std
|
---|
38 | {
|
---|
39 | /**
|
---|
40 | * Swap the values pointed to by the two references.
|
---|
41 | */
|
---|
42 | template<typename a_Type>
|
---|
43 | void swap(a_Type &a_rObj1, a_Type &a_rObj2)
|
---|
44 | {
|
---|
45 | a_Type Tmp(a_rObj1);
|
---|
46 | a_rObj1 = a_rObj2;
|
---|
47 | a_rObj2 = Tmp;
|
---|
48 | }
|
---|
49 |
|
---|
50 | /**
|
---|
51 | * Swap the values pointed to by two forward iterators.
|
---|
52 | */
|
---|
53 | template<typename a_ForwardIt1, typename a_ForwardIt2>
|
---|
54 | void iter_swap(a_ForwardIt1 a_It1, a_ForwardIt2 a_It2)
|
---|
55 | {
|
---|
56 | swap(*a_It1, *a_It2);
|
---|
57 | }
|
---|
58 |
|
---|
59 | template<typename a_RandomIt>
|
---|
60 | void sort(a_RandomIt a_ItBegin, a_RandomIt a_ItEnd)
|
---|
61 | {
|
---|
62 | /* Note! Using shell sort here because it's tiny and we've got code for it. */
|
---|
63 | /** @todo replace with faster code. */
|
---|
64 |
|
---|
65 | /* Anything worth sorting? */
|
---|
66 | std::size_t const cElements = a_ItEnd - a_ItBegin;
|
---|
67 | if (cElements >= 1)
|
---|
68 | {
|
---|
69 | /* Loop on decreasing gap, ending with 1: */
|
---|
70 | std::size_t cGap = (cElements + 1) / 2;
|
---|
71 | while (cGap > 0)
|
---|
72 | {
|
---|
73 | /* Iterate from cGap till the end: */
|
---|
74 | for (std::size_t i = cGap; i < cElements; i++)
|
---|
75 | {
|
---|
76 | /* Find the best suitable location for the item at 'i' comparing
|
---|
77 | backwards in steps of 'cGap', swapping the item at 'i' with the
|
---|
78 | one at '-cGap*j' if it's smaller, stopping if it's larger.
|
---|
79 |
|
---|
80 | Note! Original algorithm would make a copy of the item, this version
|
---|
81 | avoids extra copies of sorted items at the cost of extra copies
|
---|
82 | when dealing with unsorted ones a small cGaps values. */
|
---|
83 | a_RandomIt ItCur = a_ItBegin + i;
|
---|
84 | size_t j = i;
|
---|
85 | do
|
---|
86 | {
|
---|
87 | j -= cGap;
|
---|
88 | a_RandomIt ItAtGap = a_ItBegin + j;
|
---|
89 | if (*ItAtGap < *ItCur)
|
---|
90 | break;
|
---|
91 | std::iter_swap(ItAtGap, ItCur);
|
---|
92 | ItCur = ItAtGap;
|
---|
93 | } while (j >= cGap);
|
---|
94 | }
|
---|
95 |
|
---|
96 | /* This does not generate the most optimal gap sequence, but it has the
|
---|
97 | advantage of being simple and avoid floating point. */
|
---|
98 | cGap /= 2;
|
---|
99 | }
|
---|
100 | }
|
---|
101 | }
|
---|
102 |
|
---|
103 | template<typename a_RandomIt, typename a_FnCompareType>
|
---|
104 | void sort(a_RandomIt a_ItBegin, a_RandomIt a_ItEnd, a_FnCompareType a_fnComp)
|
---|
105 | {
|
---|
106 | /* Note! Using shell sort here because it's tiny and we've got code for it. */
|
---|
107 | /** @todo replace with faster code. */
|
---|
108 |
|
---|
109 | /* Anything worth sorting? */
|
---|
110 | std::size_t const cElements = a_ItEnd - a_ItBegin;
|
---|
111 | if (cElements >= 1)
|
---|
112 | {
|
---|
113 | /* Loop on decreasing gap, ending with 1: */
|
---|
114 | std::size_t cGap = (cElements + 1) / 2;
|
---|
115 | while (cGap > 0)
|
---|
116 | {
|
---|
117 | /* Iterate from cGap till the end: */
|
---|
118 | for (std::size_t i = cGap; i < cElements; i++)
|
---|
119 | {
|
---|
120 | /* Find the best suitable location for the item at 'i' comparing
|
---|
121 | backwards in steps of 'cGap', swapping the item at 'i' with the
|
---|
122 | one at '-cGap*j' if it's smaller, stopping if it's larger.
|
---|
123 |
|
---|
124 | Note! Original algorithm would make a copy of the item, this version
|
---|
125 | avoids extra copies of sorted items at the cost of extra copies
|
---|
126 | when dealing with unsorted ones a small cGaps values. */
|
---|
127 | a_RandomIt ItCur = a_ItBegin + i;
|
---|
128 | size_t j = i;
|
---|
129 | do
|
---|
130 | {
|
---|
131 | j -= cGap;
|
---|
132 | a_RandomIt ItAtGap = a_ItBegin + j;
|
---|
133 | if (a_fnComp(*ItAtGap, *ItCur))
|
---|
134 | break;
|
---|
135 | std::iter_swap(ItAtGap, ItCur);
|
---|
136 | ItCur = ItAtGap;
|
---|
137 | } while (j >= cGap);
|
---|
138 | }
|
---|
139 |
|
---|
140 | /* This does not generate the most optimal gap sequence, but it has the
|
---|
141 | advantage of being simple and avoid floating point. */
|
---|
142 | cGap /= 2;
|
---|
143 | }
|
---|
144 | }
|
---|
145 | }
|
---|
146 |
|
---|
147 | }
|
---|
148 |
|
---|
149 | #ifdef _MSC_VER
|
---|
150 | # pragma warning(pop)
|
---|
151 | #endif
|
---|
152 |
|
---|
153 | #endif /* !IPRT_INCLUDED_nocrt_algorithm */
|
---|
154 |
|
---|
155 |
|
---|