Line data    Source code

       1              : /*
       2              :  *
       3              :  *    Copyright (c) 2020-2021 Project CHIP Authors
       4              :  *    Copyright (c) 2013-2017 Nest Labs, Inc.
       5              :  *    All rights reserved.
       6              :  *
       7              :  *    Licensed under the Apache License, Version 2.0 (the "License");
       8              :  *    you may not use this file except in compliance with the License.
       9              :  *    You may obtain a copy of the License at
      10              :  *
      11              :  *        http://www.apache.org/licenses/LICENSE-2.0
      12              :  *
      13              :  *    Unless required by applicable law or agreed to in writing, software
      14              :  *    distributed under the License is distributed on an "AS IS" BASIS,
      15              :  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      16              :  *    See the License for the specific language governing permissions and
      17              :  *    limitations under the License.
      18              :  */
      19              : 
      20              : #pragma once
      21              : 
      22              : #include <algorithm>
      23              : #include <stdint.h>
      24              : #include <stdlib.h>
      25              : 
      26              : namespace chip {
      27              : namespace Sorting {
      28              : 
      29              : /**
      30              :  *
      31              :  * Impements the insertion sort algorithm to sort an array
      32              :  * of items of size 'n'.
      33              :  *
      34              :  * The provided comparison function SHALL have the following signature:
      35              :  *
      36              :  *      bool Compare(const T& a, const T& b);
      37              :  *
      38              :  * If a is deemed less than (i.e is ordered before) b, return true.
      39              :  * Else, return false.
      40              :  *
      41              :  * This is a stable sort.
      42              :  *
      43              :  */
      44              : template <typename T, typename CompareFunc>
      45           26 : void InsertionSort(T * items, size_t n, CompareFunc f)
      46              : {
      47          110 :     for (size_t i = 1; i < n; i++)
      48              :     {
      49           84 :         const T key = items[i];
      50           84 :         int j       = static_cast<int>(i) - 1;
      51              : 
      52          209 :         while (j >= 0 && f(key, items[j]))
      53              :         {
      54          125 :             items[j + 1] = items[j];
      55          125 :             j--;
      56              :         }
      57           84 :         items[j + 1] = key;
      58              :     }
      59           26 : }
      60              : 
      61              : } // namespace Sorting
      62              : 
      63              : } // namespace chip