discrete.h

/* MLPACK 0.2
 *
 * Copyright (c) 2008, 2009 Alexander Gray,
 *                          Garry Boyer,
 *                          Ryan Riegel,
 *                          Nikolaos Vasiloglou,
 *                          Dongryeol Lee,
 *                          Chip Mappus, 
 *                          Nishant Mehta,
 *                          Hua Ouyang,
 *                          Parikshit Ram,
 *                          Long Tran,
 *                          Wee Chin Wong
 *
 * Copyright (c) 2008, 2009 Georgia Institute of Technology
 *
 * This program 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 2 of the
 * License, or (at your option) any later version.
 *
 * This program 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.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA.
 */
#ifndef MATH_DISCRETE_H
#define MATH_DISCRETE_H

#include "fastlib/base/base.h"
#include "fastlib/col/arraylist.h"

#include <math.h>

namespace math {
  COMPILER_FUNCTIONAL
  double Factorial(int d);
  
  COMPILER_FUNCTIONAL
  double BinomialCoefficient(int n, int k);

  void MakeIdentityPermutation(index_t size, index_t *array);
  
  inline void MakeIdentityPermutation(
      index_t size, ArrayList<index_t> *result) {
    result->Init(size);
    MakeIdentityPermutation(size, result->begin());
  }
  
  void MakeRandomPermutation(index_t size, index_t *array);
  
  inline void MakeRandomPermutation(
      index_t size, ArrayList<index_t> *result) {
    result->Init(size);
    MakeRandomPermutation(size, result->begin());
  }

  void MakeInversePermutation(index_t size,
      const index_t *original, index_t *reverse);

  inline void MakeInversePermutation(
      const ArrayList<index_t>& original, ArrayList<index_t> *reverse) {
    reverse->Init(original.size());
    MakeInversePermutation(original.size(), original.begin(), reverse->begin());
  }
  
  template<typename TAnyIntegerType>
  inline bool IsPowerTwo(TAnyIntegerType i) {
    return (i & (i - 1)) == 0;
  }
  
  inline unsigned IntLog2(unsigned i) {
    unsigned l;
    for (l = 0; (unsigned(1) << l) != i; l++) {
      DEBUG_ASSERT_MSG(l < 1024, "Taking IntLog2 of a non-power-of-2: %u.", i);
    }
    return l;
  }
};

#endif