Michael Spencer / Smoothie

Fork of Smoothie to port to mbed non-LPC targets.

Dependencies:   mbed

Fork of Smoothie by Stéphane Cachat

libs/Median.h@3:f151d08d335c, 2014-03-02 (annotated)

Committer:
Bigcheese
Date:
Sun Mar 02 06:33:08 2014 +0000
Revision:
3:f151d08d335c
Parent:
2:1df0b61d3b5a 
Bunch of stuff. Need to locally merge in updated USB changes.

Who changed what in which revision?

UserRevisionLine numberNew contents of line
Michael J. Spencer 2:1df0b61d3b5a 1 /*
Michael J. Spencer 2:1df0b61d3b5a 2 This file is part of Smoothie (http://smoothieware.org/). The motion control part is heavily based on Grbl (https://github.com/simen/grbl).
Michael J. Spencer 2:1df0b61d3b5a 3 Smoothie 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, either version 3 of the License, or (at your option) any later version.
Michael J. Spencer 2:1df0b61d3b5a 4 Smoothie 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.
Michael J. Spencer 2:1df0b61d3b5a 5 You should have received a copy of the GNU General Public License along with Smoothie. If not, see <http://www.gnu.org/licenses/>.
Michael J. Spencer 2:1df0b61d3b5a 6 */
Michael J. Spencer 2:1df0b61d3b5a 7
Michael J. Spencer 2:1df0b61d3b5a 8 template <typename T>
Michael J. Spencer 2:1df0b61d3b5a 9 void split(T data[], unsigned int n, T x, unsigned int& i, unsigned int& j)
Michael J. Spencer 2:1df0b61d3b5a 10 {
Michael J. Spencer 2:1df0b61d3b5a 11 do {
Michael J. Spencer 2:1df0b61d3b5a 12 while (data[i] < x) i++;
Michael J. Spencer 2:1df0b61d3b5a 13 while (x < data[j]) j--;
Michael J. Spencer 2:1df0b61d3b5a 14
Michael J. Spencer 2:1df0b61d3b5a 15 if (i <= j) {
Michael J. Spencer 2:1df0b61d3b5a 16 T ii = data[i];
Michael J. Spencer 2:1df0b61d3b5a 17 data[i] = data[j];
Michael J. Spencer 2:1df0b61d3b5a 18 data[j] = ii;
Michael J. Spencer 2:1df0b61d3b5a 19 i++; j--;
Michael J. Spencer 2:1df0b61d3b5a 20 }
Michael J. Spencer 2:1df0b61d3b5a 21 } while (i <= j);
Michael J. Spencer 2:1df0b61d3b5a 22 }
Michael J. Spencer 2:1df0b61d3b5a 23
Michael J. Spencer 2:1df0b61d3b5a 24 // C.A.R. Hoare's Quick Median
Michael J. Spencer 2:1df0b61d3b5a 25 template <typename T>
Michael J. Spencer 2:1df0b61d3b5a 26 unsigned int quick_median(T data[], unsigned int n)
Michael J. Spencer 2:1df0b61d3b5a 27 {
Michael J. Spencer 2:1df0b61d3b5a 28 unsigned int l = 0, r = n-1, k = n/2;
Michael J. Spencer 2:1df0b61d3b5a 29 while (l < r) {
Michael J. Spencer 2:1df0b61d3b5a 30 T x = data[k];
Michael J. Spencer 2:1df0b61d3b5a 31 unsigned int i = l, j = r;
Michael J. Spencer 2:1df0b61d3b5a 32 split(data, n, x, i, j);
Michael J. Spencer 2:1df0b61d3b5a 33 if (j < k) l = i;
Michael J. Spencer 2:1df0b61d3b5a 34 if (k < i) r = j;
Michael J. Spencer 2:1df0b61d3b5a 35 }
Michael J. Spencer 2:1df0b61d3b5a 36 return k;
Michael J. Spencer 2:1df0b61d3b5a 37 }