VirtualBox

source: vbox/trunk/include/iprt/nocrt/algorithm@ 100339

Last change on this file since 100339 was 98103, checked in by vboxsync, 2 years ago

Copyright year updates by scm.

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

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette