shuffle.h

00001 // randgen.h (random number functions)
00002 //
00003 //  The WorldForge Project
00004 //  Copyright (C) 2002  The WorldForge Project
00005 //
00006 //  This program is free software; you can redistribute it and/or modify
00007 //  it under the terms of the GNU General Public License as published by
00008 //  the Free Software Foundation; either version 2 of the License, or
00009 //  (at your option) any later version.
00010 //
00011 //  This program is distributed in the hope that it will be useful,
00012 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 //  GNU General Public License for more details.
00015 //
00016 //  You should have received a copy of the GNU General Public License
00017 //  along with this program; if not, write to the Free Software
00018 //  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00019 //
00020 //  For information about WorldForge and its authors, please contact
00021 //  the Worldforge Web Site at http://www.worldforge.org.
00022 
00023 // Author: Ron Steinke
00024 // Created: 2002-5-23
00025 
00026 #ifndef WFMATH_SHUFFLE_H
00027 #define WFMATH_SHUFFLE_H
00028 
00029 #include <vector>
00030 
00031 #include <wfmath/const.h>
00032 #include <wfmath/MersenneTwister.h>
00033 
00034 namespace WFMath {
00035 
00037 
00040 template<class C>
00041 void Shuffle(std::vector<C>& v) // need vector for random access
00042 {
00043   typedef typename std::vector<C>::size_type size_type;
00044   size_type pos = v.size();
00045 
00046   if(!pos) // handle size() == 0 nicely
00047     return;
00048 
00049   // This swaps each element with one of the ones before
00050   // it, starting with the last element. Essentially,
00051   // this generates an operation from the permutation
00052   // group of size() elements, and applies it to the
00053   // vector. Note that the loop only executes size() - 1
00054   // times, as element 0 has nothing to swap with.
00055   while(--pos) {
00056     size_type new_pos = MTRand::instance.randInt(pos); // 0 <= new_pos <= pos
00057     if(new_pos == pos)
00058       continue;
00059     C tmp = v[pos];
00060     v[pos] = v[new_pos];
00061     v[new_pos] = tmp;
00062   }
00063 }
00064 
00065 } // namespace WFMath
00066 
00067 #endif  // WFMATH_SHUFFLE_H

Generated on Sun Aug 27 21:26:08 2006 for WFMath by  doxygen 1.4.7