LCOV - code coverage report
Current view: top level - src/common/algorithm/include/autoware_auto_algorithm - quick_sort.hpp (source / functions) Hit Total Coverage
Test: lcov.total.filtered Lines: 26 26 100.0 %
Date: 2023-03-03 05:44:19 Functions: 2 2 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 52 108 48.1 %

           Branch data     Line data    Source code
       1                 :            : // Copyright 2019 Silexica GmbH, Lichtstr. 25, Cologne, Germany. All rights reserved.
       2                 :            : //
       3                 :            : // Licensed under the Apache License, Version 2.0 (the "License");
       4                 :            : // you may not use this file except in compliance with the License.
       5                 :            : // You may obtain a copy of the License at
       6                 :            : //
       7                 :            : //     http://www.apache.org/licenses/LICENSE-2.0
       8                 :            : //
       9                 :            : // Unless required by applicable law or agreed to in writing, software
      10                 :            : // distributed under the License is distributed on an "AS IS" BASIS,
      11                 :            : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12                 :            : // See the License for the specific language governing permissions and
      13                 :            : // limitations under the License.
      14                 :            : /// \file
      15                 :            : /// \brief This file provides an iterative quick sort implementation.
      16                 :            : #ifndef AUTOWARE_AUTO_ALGORITHM__QUICK_SORT_HPP_
      17                 :            : #define AUTOWARE_AUTO_ALGORITHM__QUICK_SORT_HPP_
      18                 :            : 
      19                 :            : #include <algorithm>
      20                 :            : #include <functional>
      21                 :            : #include <utility>
      22                 :            : #include <vector>
      23                 :            : 
      24                 :            : namespace autoware
      25                 :            : {
      26                 :            : 
      27                 :            : namespace common
      28                 :            : {
      29                 :            : 
      30                 :            : namespace algorithm
      31                 :            : {
      32                 :            : 
      33                 :            : /// \brief Iterative quick sort implementation based on a stack.
      34                 :            : template<typename Container, typename RandomIt = typename Container::iterator>
      35   [ +  -  -  -  :          9 : class QuickSorter
          +  -  -  -  +  
          -  -  -  +  -  
          -  -  +  -  -  
          -  +  -  -  -  
          +  -  -  -  +  
          -  -  -  -  +  
                   -  - ]
      36                 :            : {
      37                 :            : public:
      38                 :            :   QuickSorter(QuickSorter const &) = delete;
      39                 :            :   QuickSorter & operator=(QuickSorter const &) = delete;
      40                 :            :   QuickSorter(QuickSorter &&) = default;
      41                 :            :   /// \brief Move equals operator
      42                 :            :   QuickSorter & operator=(QuickSorter &&) = default;
      43                 :            : 
      44                 :            :   /// \brief Default constructor, do not reserve capacity for stack
      45                 :            :   QuickSorter() = default;
      46                 :            : 
      47                 :            :   /// \brief Construct and reserve capacity for stack
      48                 :            :   /// \param[in] capacity - The maximum capacity of the container to be sorted
      49                 :          8 :   explicit QuickSorter(::std::size_t capacity)
      50         [ +  - ]:          8 :   {
      51                 :            :     reserve(capacity);
      52                 :          8 :   }
      53                 :            : 
      54                 :            :   /// \brief Iterative quick sort implementation using a stack, sorts
      55                 :            :   /// range [first, last) using the given comparison function
      56                 :            :   /// \param[in] first Start of the range to sort
      57                 :            :   /// \param[in] last End of the range to sort (not included)
      58                 :            :   /// \param[in] comp The comparison function to base the sorting on
      59                 :            :   template<typename Compare>
      60         [ +  + ]:          9 :   void sort(RandomIt first, RandomIt last, Compare comp) const
      61                 :            :   {
      62         [ +  + ]:          9 :     if (::std::distance(first, last) < 2) {
      63                 :            :       return;
      64                 :            :     }
      65                 :            : 
      66                 :            :     // Make sure we do not accidently have an already partially filled stack,
      67                 :            :     // capacity does not change
      68         [ -  + ]:          7 :     m_stack.clear();
      69                 :            : 
      70                 :            :     // Add first interval to the stack for sorting, from here on last is really
      71                 :            :     // the last element and not the element after, i.e. not end
      72                 :          7 :     m_stack.push_back(first);
      73                 :          7 :     m_stack.push_back(last - 1);
      74                 :            : 
      75         [ +  + ]:         27 :     while (!m_stack.empty()) {
      76                 :         20 :       last = m_stack.back();
      77                 :            :       m_stack.pop_back();
      78                 :         20 :       first = m_stack.back();
      79                 :            :       m_stack.pop_back();
      80                 :            : 
      81                 :            :       auto part = QuickSorter::partition(first, last, comp);
      82                 :            : 
      83         [ +  + ]:         20 :       if (part > first + 1) {
      84                 :          8 :         m_stack.push_back(first);
      85                 :          8 :         m_stack.push_back(part - 1);
      86                 :            :       }
      87                 :            : 
      88         [ +  + ]:         20 :       if (part < last - 1) {
      89                 :          5 :         m_stack.push_back(part + 1);
      90                 :          5 :         m_stack.push_back(last);
      91                 :            :       }
      92                 :            :     }
      93                 :            :   }
      94                 :            : 
      95                 :            :   /// \brief Iterative quick sort implementation using a stack, sorts
      96                 :            :   /// range [first, last) using the default less operation
      97                 :            :   /// \param[in] first Start of the range to sort
      98                 :            :   /// \param[in] last End of the range to sort (not included)
      99                 :            :   void sort(RandomIt first, RandomIt last) const
     100                 :            :   {
     101   [ +  -  +  -  :          9 :     sort(first, last, ::std::less<const decltype(*first)>());
          +  -  +  -  +  
          -  +  -  +  -  
             +  -  +  - ]
     102                 :          9 :   }
     103                 :            : 
     104                 :            :   /// \brief Reserves helper stack capacity for the iterative quick sort
     105                 :            :   /// algorithm based on the capacity of the container to be sorted such that
     106                 :            :   /// no heap allocation is done during the algorithm.
     107                 :            :   /// \param[in] capacity - The maximum capacity of the container to be sorted
     108                 :            :   void reserve(::std::size_t capacity)
     109                 :            :   {
     110                 :            :     // The maximum partition depth is n/2 + 1, which means we need a maximum
     111                 :            :     // capacity of n + 2 to hold store the iterators in the stack.
     112         [ +  - ]:          8 :     m_stack.reserve(capacity + 2);
     113                 :          8 :   }
     114                 :            : 
     115                 :            :   /// \brief Returns the maximum capacity that is allowed for a container to be
     116                 :            :   /// sorted.
     117                 :            :   /// \return The maximum capacity that a container may have if it is to be sorted
     118                 :            :   /// using this sorter.
     119                 :            :   ::std::size_t capacity() const
     120                 :            :   {
     121   [ +  -  +  -  :         17 :     if (m_stack.capacity() < 2) {
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
             -  +  -  -  
                      + ]
     122                 :            :       return 0;
     123                 :            :     }
     124                 :         16 :     return m_stack.capacity() - 2;
     125                 :            :   }
     126                 :            : 
     127                 :            : private:
     128                 :            :   /// \brief Partition range [first, last], based on pivot element last. After
     129                 :            :   /// execution all elements smaller than the pivot element are left of it and
     130                 :            :   /// all bigger elements right of it.
     131                 :            :   /// \param[in] first Start of the range to partition
     132                 :            :   /// \param[in] last End (included) of the range to partition, used as pivot
     133                 :            :   /// \param[in] comp Element comparison function
     134                 :            :   /// \return Iterator to the pivot element in the range
     135                 :            :   template<typename Compare>
     136                 :            :   static RandomIt partition(RandomIt first, RandomIt last, Compare comp)
     137                 :            :   {
     138                 :            :     auto prev = first;
     139                 :            : 
     140                 :            :     // Iterate over range and swap whenever element is smaller than the pivot
     141                 :            :     // element.
     142         [ +  + ]:         71 :     for (auto it = first; it < last; it++) {
     143         [ +  + ]:         51 :       if (comp(*it, *last)) {
     144                 :            :         ::std::iter_swap(it, prev);
     145                 :            :         prev++;
     146                 :            :       }
     147                 :            :     }
     148                 :            : 
     149                 :            :     // Swap the pivot element into place
     150                 :            :     ::std::iter_swap(prev, last);
     151                 :            :     return prev;
     152                 :            :   }
     153                 :            : 
     154                 :            : private:
     155                 :            :   /// Helper stack used for sorting, needs to have capacity (last-first)+2
     156                 :            :   mutable ::std::vector<RandomIt> m_stack;
     157                 :            : };
     158                 :            : 
     159                 :            : }  // namespace algorithm
     160                 :            : 
     161                 :            : }  // namespace common
     162                 :            : 
     163                 :            : }  // namespace autoware
     164                 :            : 
     165                 :            : #endif  // AUTOWARE_AUTO_ALGORITHM__QUICK_SORT_HPP_

Generated by: LCOV version 1.14