FastRunningMedian.h
Go to the documentation of this file.
00001 //
00002 // Released to the public domain
00003 //
00004 // Remarks:
00005 // This is a lean but fast version.
00006 // Initially, the buffer is filled with a "default_value". To get real median values
00007 // you have to fill the object with N values, where N is the size of the sliding window.
00008 // For example: for(int i=0; i < 32; i++) myMedian.addValue(readSensor());
00009 //
00010 // Constructor:
00011 // FastRunningMedian<datatype_of_content, size_of_sliding_window, default_value>
00012 // maximim size_of_sliding_window is 255
00013 // Methods:
00014 // addValue(val) adds a new value to the buffers (and kicks the oldest)
00015 // getMedian() returns the current median value
00016 //
00017 //
00018 // Usage:
00019 // #include "FastRunningMedian.h"
00020 // FastRunningMedian<unsigned int,32, 0> myMedian;
00021 // ....
00022 // myMedian.addValue(value); // adds a value
00023 // m = myMedian.getMedian(); // retieves the median
00024 //
00025 
00026 #include <inttypes.h>
00027 
00028 template <typename T, uint8_t N, T default_value> class FastRunningMedian {
00029 
00030   public:
00031     FastRunningMedian() {
00032       _buffer_ptr = N;
00033       _window_size = N;
00034       _median_ptr = N / 2;
00035 
00036       // Init buffers
00037       uint8_t i = _window_size;
00038       while ( i > 0 ) {
00039         i--;
00040         _inbuffer[i] = default_value;
00041         _sortbuffer[i] = default_value;
00042       }
00043     };
00044 
00045     T getMedian() {
00046       // buffers are always sorted.
00047       return _sortbuffer[_median_ptr];
00048     }
00049 
00050 
00051     void addValue(T new_value) {
00052       // comparision with 0 is fast, so we decrement _buffer_ptr
00053       if (_buffer_ptr == 0)
00054         _buffer_ptr = _window_size;
00055 
00056       _buffer_ptr--;
00057 
00058       T old_value = _inbuffer[_buffer_ptr]; // retrieve the old value to be replaced
00059       if (new_value == old_value)                 // if the value is unchanged, do nothing
00060         return;
00061 
00062       _inbuffer[_buffer_ptr] = new_value;  // fill the new value in the cyclic buffer
00063 
00064       // search the old_value in the sorted buffer
00065       uint8_t i = _window_size;
00066       while (i > 0) {
00067         i--;
00068         if (old_value == _sortbuffer[i])
00069           break;
00070       }
00071 
00072       // i is the index of the old_value in the sorted buffer
00073       _sortbuffer[i] = new_value; // replace the value
00074 
00075       // the sortbuffer is always sorted, except the [i]-element..
00076       if (new_value > old_value) {
00077         //  if the new value is bigger than the old one, make a bubble sort upwards
00078         for (uint8_t p = i, q = i + 1; q < _window_size; p++, q++) {
00079           // bubble sort step
00080           if (_sortbuffer[p] > _sortbuffer[q]) {
00081             T tmp = _sortbuffer[p];
00082             _sortbuffer[p] = _sortbuffer[q];
00083             _sortbuffer[q] = tmp;
00084           } else {
00085             // done ! - found the right place
00086             return;
00087           }
00088         }
00089       } else {
00090         // else new_value is smaller than the old one, bubble downwards
00091         for (int p = i - 1, q = i; q > 0; p--, q--) {
00092           if (_sortbuffer[p] > _sortbuffer[q]) {
00093             T tmp = _sortbuffer[p];
00094             _sortbuffer[p] = _sortbuffer[q];
00095             _sortbuffer[q] = tmp;
00096           } else {
00097             // done !
00098             return;
00099           }
00100         }
00101       }
00102     }
00103 
00104   private:
00105     // Pointer to the last added element in _inbuffer
00106     uint8_t _buffer_ptr;
00107     // sliding window size
00108     uint8_t _window_size;
00109     // position of the median value in _sortbuffer
00110     uint8_t _median_ptr;
00111 
00112     // cyclic buffer for incoming values
00113     T _inbuffer[N];
00114     // sorted buffer
00115     T _sortbuffer[N];
00116 };
00117 
00118 
00119 // --- END OF FILE ---


ric_mc
Author(s): RoboTiCan
autogenerated on Fri May 20 2016 03:48:55