cvrQuickMedian2.h

Go to the documentation of this file.

/*
 * Copyright (C) 1998 - 2005
 * Lehrstuhl fuer Technische Informatik, RWTH-Aachen, Germany
 *
 *
 * This file is part of the Computer Vision and Robotics Library (CVR-Lib)
 *
 * The CVR-Lib is free software; you can redistribute it and/or
 * modify it under the terms of the BSD License.
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * 3. Neither the name of the authors nor the names of its contributors may be
 *    used to endorse or promote products derived from this software without
 *    specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */



/**
 * \file   cvrQuickMedian2.h
 *         This file contains the functor quickMedian, which
 *         calculates the median quickly
 * \author Guy Wafo
 * \date   27.03.2001
 *
 * $Id: cvrQuickMedian2.h,v 1.3 2007/10/13 00:17:19 alvarado Exp $
 */

#ifndef _CVR_QUICKMEDIAN2_H_
#define _CVR_QUICKMEDIAN2_H_

#include "cvrFunctor.h"
#include "cvrVector.h"
#include "cvrMatrix.h"
#include "cvrQuickMedian.h"

namespace cvr {


  /**
   * Quick median for two vectors.
   *
   * This class is used to extract the median of the elements of a
   * given vector or matrix, partitioning at the same time a second
   * vector.  The median is defined as the element at the middle
   * position of the sorted vector.  The algorithm used is based on
   * the quick sort.
   *
   * The difference with the cvr::quickMedian functor is that you can
   * "sort" a second vector, which might contain for example the indices
   * of the elements.  This way, you can easily find out, which elements of the
   * original vector are under the median, and which ones above.
   *
   * @see cvr::quickMedian, cvr::sort, cvr::sort2
   *
   * For vectors (or matrices) with an even number n of elements, the
   * median will be the element at (n/2) or (n/2)-1 depending on the
   * parameter settings.
   *
   * The type of the vector elements (T) must accept the operators <
   * and >.
   *
   * @ingroup gStatistics
   */
  class quickMedian2 : public functor {
  public:

    typedef quickMedian::parameters parameters;

    /**
     * Default constructor
     */
    quickMedian2();

    /**
     * Constructor to set parameters
     */
    quickMedian2(const parameters& param);

    /**
     * Constructor with indicator what to do for even-sized vectors
     */
    quickMedian2(const eMedianEvenCase medianEvenCase);

    /**
     * copy constructor
     * @param other the object to be copied
     */
    quickMedian2(const quickMedian2& other);

    /**
     * Destructor
     */
    virtual ~quickMedian2();

    /**
     * Returns the name of this class.
     */
    const std::string& name() const;

    /**
     * Returns a pointer to a clone of this functor.
     */
    virtual quickMedian2* clone() const;

    /**
     * Returns a pointer to a new instance of this functor.
     */
    virtual quickMedian2* newInstance() const;

    /**
     * Returns used parameters
     */
    const parameters& getParameters() const;

    /**
     * Operates on the given arguments.
     *
     * Please note that the arguments will be both modified.
     *
     * The resulting keys vector contains the elements less or equal than the
     * median for the indexes <code>x</code> such that
     * <code>x < size()/2</code>, and higher or equal otherwise.
     *
     * Both vectors must have the same size.
     *
     * The types V and W, can be an cvr::genericVector
     * or its derived classes, or a std::vector.  In principle the container
     * type V,W just needs to support:
     * - the type definitions V::size_type and V::value_type,
     * - the operator[] returning elements of type V::value_type
     * - the V::value_type has to be comparable with the operator<.
     * - the method empty()
     * - the method size() returning a V::size_type
     *
     * @param keys vector with the key data.  The median of this data
     *             is partially sorted while looking for the median.
     * @param data vector with data to be sorted the same way as the keys.
     *             You can for example use a ivector initialized with the
     *             index values (i.e. data(i)=i), so that after the apply
     *             method you can check which elements are below the median
     *             and which above.
     * @param median the median value of keys.
     * @return bool upon success, false otherwise
     */
    template<class V,class W>
    bool apply(V& keys,W& data, typename V::value_type& median) const;

    /**
     * Operates on the given arguments.
     *
     * Please note that the arguments will be both modified.
     *
     * The resulting keys vector contains the elements less or equal than the
     * median for the indexes <code>x</code> such that
     * <code>x < size()/2</code>, and higher or equal otherwise.
     *
     * Both vectors must have the same size.
     *
     * @param keys V with the key data.  The median of this data
     *             is partially sorted while looking for the median.
     * @param data W with data to be sorted the same way as the keys.
     *             You can for example use a ivector initialized with the
     *             index values (i.e. data(i)=i), so that after the apply
     *             method you can check which elements are below the median
     *             and which above.
     * @return bool upon success, false otherwise
     */
    template<class V,class W>
    bool apply(V& keys,W& data) const;


  protected:
    /**
     * this method calculates the median in a recursively form
     */
    template<class V,class W>
    typename V::value_type findMedian(V& vct,
                                      W& data,
                                      const int begin,
                                      const int end,
                                      const int medianPos) const;

    /**
     * this method chooses a pivot-value and ensures that lower values lie
     * at the left and higher values at the right of its final position, which
     * will be returned.
     */
    template<class V,class W>
    int partition(V& vct,
                  W& data,
                  const int begin,
                  const int end) const;
  };

}

#include "cvrQuickMedian2_template.h"

#endif