001package org.openimaj.demos.sandbox.tldcpp.tracker;
002
003/**
004 * Fast array median computation
005 * 
006 * @author Sina Samangooei (ss@ecs.soton.ac.uk)
007 * 
008 */
009public class FastMedian {
010        private static void ELEM_SWAP(float[] a, int ai, float[] b, int bi)
011        {
012                final float t = a[ai];
013                a[ai] = b[bi];
014                b[bi] = t;
015        }
016
017        /**
018         * Returns median of the array. Changes array!
019         * <p>
020         * This Quickselect routine is based on the algorithm described in
021         * "Numerical recipes in C", Second Edition, Cambridge University Press,
022         * 1992, Section 8.5, ISBN 0-521-43108-5
023         * <p>
024         * This code by Nicolas Devillard - 1998. Public domain.
025         * 
026         * @param arr
027         *            the array
028         * @param n
029         *            length of array
030         * @return the median of the array
031         */
032        public static float getMedianUnmanaged(float arr[], int n)
033        {
034                int low, high;
035                int median;
036                int middle, ll, hh;
037
038                low = 0;
039                high = n - 1;
040                median = (low + high) / 2;
041                for (;;)
042                {
043                        if (high <= low) /* One element only */
044                                return arr[median];
045
046                        if (high == low + 1)
047                        { /* Two elements only */
048                                if (arr[low] > arr[high])
049                                        ELEM_SWAP(arr, low, arr, high);
050                                return arr[median];
051                        }
052
053                        /* Find median of low, middle and high items; swap into position low */
054                        middle = (low + high) / 2;
055                        if (arr[middle] > arr[high])
056                                ELEM_SWAP(arr, middle, arr, high);
057                        if (arr[low] > arr[high])
058                                ELEM_SWAP(arr, low, arr, high);
059                        if (arr[middle] > arr[low])
060                                ELEM_SWAP(arr, middle, arr, low);
061
062                        /* Swap low item (now in position middle) into position (low+1) */
063                        ELEM_SWAP(arr, middle, arr, low + 1);
064
065                        /* Nibble from each end towards middle, swapping items when stuck */
066                        ll = low + 1;
067                        hh = high;
068                        for (;;)
069                        {
070                                do
071                                        ll++;
072                                while (arr[low] > arr[ll]);
073                                do
074                                        hh--;
075                                while (arr[hh] > arr[low]);
076
077                                if (hh < ll)
078                                        break;
079
080                                ELEM_SWAP(arr, ll, arr, hh);
081                        }
082
083                        /* Swap middle item (in position low) back into correct position */
084                        ELEM_SWAP(arr, low, arr, hh);
085
086                        /* Re-set active partition */
087                        if (hh <= median)
088                                low = ll;
089                        if (hh >= median)
090                                high = hh - 1;
091                }
092        }
093
094        /**
095         * Calculates the median of the array. Doesn't change the array (operates on
096         * a copy internally).
097         * 
098         * @param arr
099         *            the array
100         * @param n
101         *            length of array
102         * @return the median
103         */
104        public static float getMedian(float arr[], int n)
105        {
106                final float[] temP = new float[n];
107                System.arraycopy(arr, 0, temP, 0, n);
108                ;
109                float median;
110                median = getMedianUnmanaged(temP, n);
111                return median;
112        }
113}