Line data    Source code

       1             : /*
       2             :    This program is free software: you can redistribute it and/or modify
       3             :    it under the terms of the GNU General Public License as published by
       4             :    the Free Software Foundation, either version 3 of the License, or
       5             :    (at your option) any later version.
       6             : 
       7             :    This program is distributed in the hope that it will be useful,
       8             :    but WITHOUT ANY WARRANTY; without even the implied warranty of
       9             :    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      10             :    GNU General Public License for more details.
      11             : 
      12             :    You should have received a copy of the GNU General Public License
      13             :    along with this program.  If not, see <http://www.gnu.org/licenses/>.
      14             :  */
      15             : 
      16             : #include <stdint.h>
      17             : #include "sorting.h"
      18             : 
      19             : /*
      20             :   in-place insertion sort for small arrays of data. This is O(n) if
      21             :   already sorted and O(n^2) for worst case (elements are reversed)
      22             :   sort order is smallest first
      23             :  */
      24       68000 : void insertion_sort_uint16(uint16_t *data, uint16_t n)
      25             : {
      26     3463624 :     for (uint16_t i=1; i<n; i++) {
      27     3395624 :         uint16_t temp = data[i];
      28     3395624 :         int16_t j = i - 1;
      29             : 
      30    59505854 :         while (j >= 0 && data[j] > temp) {
      31    56110230 :             data[j+1] = data[j];
      32    56110230 :             j--;
      33             :                 }
      34     3395624 :         data[j+1] = temp;
      35             :     }
      36       68000 : }
      37             : 
      38             : /*
      39             :   remove duplicates from a sorted uint16_t array, returning the new
      40             :   count
      41             :  */
      42       20000 : uint16_t remove_duplicates_uint16(uint16_t *data, uint16_t n)
      43             : {
      44       20000 :     uint16_t removed = 0;
      45     1020800 :     for (uint16_t i=1; i<n; i++) {
      46     1000800 :         if (data[i-(1+removed)] == data[i]) {
      47      586394 :             removed++;
      48      414406 :         } else if (removed != 0) {
      49      392946 :             data[i-removed] = data[i];
      50             :         }
      51             :     }
      52       20000 :     return n - removed;
      53             : }
      54             : 
      55             : /*
      56             :   bisection search on a sorted uint16_t array to find an element
      57             :   return true if found
      58             : */
      59      121706 : bool bisect_search_uint16(const uint16_t *data, uint16_t n, uint16_t value)
      60             : {
      61      121706 :     if (n == 0) {
      62           0 :         return false;
      63             :     }
      64      121706 :     uint16_t low=0, high=n-1;
      65      667556 :     while (low < high) {
      66      590060 :         uint16_t mid = (low+high)/2;
      67      590060 :         if (value < data[mid]) {
      68      283302 :             high = mid;
      69      283302 :             continue;
      70             :         }
      71      306758 :         if (value > data[mid]) {
      72      262548 :             low = mid+1;
      73      262548 :             continue;
      74             :         }
      75       44210 :         return true;
      76             :     }
      77       77496 :     return data[low] == value;
      78             : }
      79             : 
      80             : /*
      81             :   remove elements in a 2nd sorted array from a sorted uint16_t array
      82             :   return the number of remaining elements
      83             :  */
      84        2000 : uint16_t remove_list_uint16(uint16_t *data, uint16_t n, const uint16_t *rem, uint16_t n2)
      85             : {
      86        2000 :     uint16_t removed = 0;
      87      103706 :     for (uint16_t i=0; i<n; i++) {
      88      101706 :         if (bisect_search_uint16(rem, n2, data[i])) {
      89       37654 :             removed++;
      90       64052 :         } else if (removed != 0) {
      91       55472 :             data[i-removed] = data[i];
      92             :         }
      93             :     }
      94        2000 :     return n - removed;
      95             : }
      96             : 
      97             : /*
      98             :   return number of common elements between two sorted uint16_t lists
      99             :  */
     100           0 : uint16_t common_list_uint16(uint16_t *data, uint16_t n, const uint16_t *data2, uint16_t n2)
     101             : {
     102           0 :     uint16_t common = 0;
     103           0 :     for (uint8_t i=0; i<n2; i++) {
     104           0 :         if (bisect_search_uint16(data, n, data2[i])) {
     105           0 :             common++;
     106             :         }
     107             :     }
     108           0 :     return common;
     109             : }