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

/** @file
 * IPRT / No-CRT - Minimal C++ algorithm header.
 */

/*
 * Copyright (C) 2022-2023 Oracle and/or its affiliates.
 *
 * This file is part of VirtualBox base platform packages, as
 * available from https://www.virtualbox.org.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation, in version 3 of the
 * License.
 *
 * This program 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.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, see <https://www.gnu.org/licenses>.
 *
 * The contents of this file may alternatively be used under the terms
 * of the Common Development and Distribution License Version 1.0
 * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included
 * in the VirtualBox distribution, in which case the provisions of the
 * CDDL are applicable instead of those of the GPL.
 *
 * You may elect to license modified versions of this file under the
 * terms and conditions of either the GPL or the CDDL or both.
 *
 * SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0
 */

#ifndef VBOX_INCLUDED_SRC_nocrt_algorithm
#define VBOX_INCLUDED_SRC_nocrt_algorithm
#ifndef RT_WITHOUT_PRAGMA_ONCE
# pragma once
#endif

#ifdef _MSC_VER
# pragma warning(push)
# pragma warning(disable: 4643) /* warning C4643: Forward declaring 'ios_base' in namespace std is not permitted by the C++ Standard */
#endif

namespace std
{
    /**
     * Swap the values pointed to by the two references.
     */
    template<typename a_Type>
    void swap(a_Type &a_rObj1, a_Type &a_rObj2)
    {
        a_Type Tmp(a_rObj1);
        a_rObj1 = a_rObj2;
        a_rObj2 = Tmp;
    }

    /**
     * Swap the values pointed to by two forward iterators.
     */
    template<typename a_ForwardIt1, typename a_ForwardIt2>
    void iter_swap(a_ForwardIt1 a_It1, a_ForwardIt2 a_It2)
    {
        swap(*a_It1, *a_It2);
    }

    template<typename a_RandomIt>
    void sort(a_RandomIt a_ItBegin, a_RandomIt a_ItEnd)
    {
        /* Note! Using shell sort here because it's tiny and we've got code for it. */
        /** @todo replace with faster code.   */

        /* Anything worth sorting? */
        std::size_t const cElements = a_ItEnd - a_ItBegin;
        if (cElements >= 1)
        {
            /* Loop on decreasing gap, ending with 1: */
            std::size_t cGap = (cElements + 1) / 2;
            while (cGap > 0)
            {
                /* Iterate from cGap till the end: */
                for (std::size_t i = cGap; i < cElements; i++)
                {
                    /* Find the best suitable location for the item at 'i' comparing
                       backwards in steps of 'cGap', swapping the item at 'i' with the
                       one at '-cGap*j' if it's smaller, stopping if it's larger.

                       Note! Original algorithm would make a copy of the item, this version
                             avoids extra copies of sorted items at the cost of extra copies
                             when dealing with unsorted ones a small cGaps values. */
                    a_RandomIt ItCur = a_ItBegin + i;
                    size_t     j     = i;
                    do
                    {
                        j -= cGap;
                        a_RandomIt ItAtGap = a_ItBegin + j;
                        if (*ItAtGap < *ItCur)
                            break;
                        std::iter_swap(ItAtGap, ItCur);
                        ItCur = ItAtGap;
                    } while (j >= cGap);
                }

                /* This does not generate the most optimal gap sequence, but it has the
                   advantage of being simple and avoid floating point. */
                cGap /= 2;
            }
        }
    }

    template<typename a_RandomIt, typename a_FnCompareType>
    void sort(a_RandomIt a_ItBegin, a_RandomIt a_ItEnd, a_FnCompareType a_fnComp)
    {
        /* Note! Using shell sort here because it's tiny and we've got code for it. */
        /** @todo replace with faster code.   */

        /* Anything worth sorting? */
        std::size_t const cElements = a_ItEnd - a_ItBegin;
        if (cElements >= 1)
        {
            /* Loop on decreasing gap, ending with 1: */
            std::size_t cGap = (cElements + 1) / 2;
            while (cGap > 0)
            {
                /* Iterate from cGap till the end: */
                for (std::size_t i = cGap; i < cElements; i++)
                {
                    /* Find the best suitable location for the item at 'i' comparing
                       backwards in steps of 'cGap', swapping the item at 'i' with the
                       one at '-cGap*j' if it's smaller, stopping if it's larger.

                       Note! Original algorithm would make a copy of the item, this version
                             avoids extra copies of sorted items at the cost of extra copies
                             when dealing with unsorted ones a small cGaps values. */
                    a_RandomIt ItCur = a_ItBegin + i;
                    size_t     j     = i;
                    do
                    {
                        j -= cGap;
                        a_RandomIt ItAtGap = a_ItBegin + j;
                        if (a_fnComp(*ItAtGap, *ItCur))
                            break;
                        std::iter_swap(ItAtGap, ItCur);
                        ItCur = ItAtGap;
                    } while (j >= cGap);
                }

                /* This does not generate the most optimal gap sequence, but it has the
                   advantage of being simple and avoid floating point. */
                cGap /= 2;
            }
        }
    }

}

#ifdef _MSC_VER
# pragma warning(pop)
#endif

#endif /* !VBOX_INCLUDED_SRC_nocrt_algorithm */