From 8527e903bb76856a16e0f68f73ac11e4e087dfc3 Mon Sep 17 00:00:00 2001
From: oetiker <oetiker@a5681a0c-68f1-0310-ab6d-d61299d08faa>
Date: Fri, 1 Jun 2012 10:04:59 +0000
Subject: [PATCH] rrd_graph_rpn: add a MEDIAN operator. -- Aaron Gallagher
 <_@habnab.it>

git-svn-id: svn://svn.oetiker.ch/rrdtool/trunk/program@2290 a5681a0c-68f1-0310-ab6d-d61299d08faa
---
 CONTRIBUTORS         |  1 +
 doc/rrdgraph_rpn.pod | 10 ++++++++++
 src/rrd_rpncalc.c    | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 src/rrd_rpncalc.h    |  2 +-
 4 files changed, 58 insertions(+), 1 deletion(-)

diff --git a/CONTRIBUTORS b/CONTRIBUTORS
index 6c651eb..5b004df 100644
--- a/CONTRIBUTORS
+++ b/CONTRIBUTORS
@@ -9,6 +9,7 @@ Alex van den Bogaerdt <alex with ergens.op.het.net> (rrd_resize.c and more)
 Amos Shapira <amos with gezernet.co.il>
 Andreas Kroomaa <andre with ml.ee>
 Andrew Turner <turner with mint.net> (LAST consolidator)
+Aaron Gallagher <_ with habnab.it> MEDIAN operator
 Benny Baumann <benbe with geshi.org) rrd_dump with callback support
 Bernard Fischer <bfischer with syslog.ch> 64bit stuff, --alt-autoscale-max
 Bernhard Fischer <rep dot dot dot nop with gmail.com> MMAP rewrite
diff --git a/doc/rrdgraph_rpn.pod b/doc/rrdgraph_rpn.pod
index 894fef1..87fc8e6 100644
--- a/doc/rrdgraph_rpn.pod
+++ b/doc/rrdgraph_rpn.pod
@@ -157,6 +157,16 @@ average, ignoring all UNKNOWN values in the process.
 
 Example: C<CDEF:x=a,b,c,d,4,AVG>
 
+B<MEDIAN>
+
+pop one element (I<count>) from the stack. Now pop I<count> elements and find
+the median, ignoring all UNKNOWN values in the process. If there are an even
+number of non-UNKNOWN values, the average of the middle two will be pushed on
+the stack.
+
+Example: C<CDEF:x=a,b,c,d,4,MEDIAN>
+
+
 B<TREND, TRENDNAN>
 
 Create a "sliding window" average of another data series.
diff --git a/src/rrd_rpncalc.c b/src/rrd_rpncalc.c
index 2bd1474..0677b30 100644
--- a/src/rrd_rpncalc.c
+++ b/src/rrd_rpncalc.c
@@ -387,6 +387,7 @@ rpnp_t   *rpn_parse(
             match_op(OP_AVG, AVG)
             match_op(OP_ABS, ABS)
             match_op(OP_ADDNAN, ADDNAN)
+            match_op(OP_MEDIAN, MEDIAN)
 #undef match_op
             else if ((sscanf(expr, DEF_NAM_FMT "%n", vname, &pos) == 1)
                      && ((rpnp[steps].ptr = (*lookup) (key_hash, vname)) !=
@@ -936,6 +937,51 @@ short rpn_calc(
             stackunderflow(0);
             rpnstack->s[stptr] = fabs(rpnstack->s[stptr]);
             break;
+        case OP_MEDIAN:
+            stackunderflow(0);
+            {
+                int elements = (int) rpnstack->s[stptr--];
+                int final_elements = elements;
+                double *element_ptr = rpnstack->s + stptr - elements + 1;
+                double *goodvals = element_ptr;
+                double *badvals = element_ptr + elements - 1;
+
+                stackunderflow(elements - 1);
+
+                /* move values to consolidate the non-NANs for sorting, keeping
+                 * track of how many NANs we encounter. */
+                while (goodvals < badvals) {
+                    if (isnan(*goodvals)) {
+                        *goodvals = *badvals--;
+                        --final_elements;
+                    } else {
+                        ++goodvals;
+                    }
+                }
+
+                stptr -= elements;
+                if (!final_elements) {
+                    /* no non-NAN elements; push NAN */
+                    rpnstack->s[++stptr] = DNAN;
+                } else {                   
+                    /* when goodvals and badvals meet, they might have met on a
+                     * NAN, which wouldn't decrease final_elements. so, check
+                     * that now. */
+                    if (isnan(*goodvals)) --final_elements;
+                    /* and finally, take the median of the remaining non-NAN
+                     * elements. */
+                    qsort(element_ptr, final_elements, sizeof(double),
+                          rpn_compare_double);
+                    if (final_elements % 2 == 1){
+                       rpnstack->s[++stptr] = element_ptr[ final_elements / 2 ];
+                    }
+                    else {
+                       rpnstack->s[++stptr] = 0.5 * ( element_ptr[ final_elements / 2 ] + element_ptr[ final_elements / 2 - 1 ] );
+                    }
+                }
+            }
+            break;
+       
         case OP_END:
             break;
         }
diff --git a/src/rrd_rpncalc.h b/src/rrd_rpncalc.h
index ab990b2..d27ff4c 100644
--- a/src/rrd_rpncalc.h
+++ b/src/rrd_rpncalc.h
@@ -19,7 +19,7 @@ enum op_en { OP_NUMBER = 0, OP_VARIABLE, OP_INF, OP_PREV, OP_NEGINF,
     OP_ATAN, OP_SQRT, OP_SORT, OP_REV, OP_TREND, OP_TRENDNAN,
     OP_ATAN2, OP_RAD2DEG, OP_DEG2RAD,
     OP_PREDICT,OP_PREDICTSIGMA,
-    OP_AVG, OP_ABS, OP_ADDNAN
+    OP_AVG, OP_ABS, OP_ADDNAN, OP_MEDIAN
 };
 
 typedef struct rpnp_t {
-- 
2.11.0