1  /** @file


2  * IPRT / NoCRT  Minimal C++ algorithm header.


3  */


4 


5  /*


6  * Copyright (C) 20222023 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  * SPDXLicenseIdentifier: GPL3.0only OR CDDL1.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 


47  namespace 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 

