Mercator
RandCache.h
00001 // This file may be redistributed and modified only under the terms of
00002 // the GNU General Public License (See COPYING for details).
00003 // Copyright (C) 2004 Damien McGinnes, Ron Steinke, Alistair Riddoch
00004 
00005 #ifndef MERCATOR_RANDCACHE_H
00006 #define MERCATOR_RANDCACHE_H
00007 
00008 #include <vector>
00009 #include <cstdlib>
00010 #include <wfmath/MersenneTwister.h>
00011 
00012 // construct with something like:
00013 // RandCache r(seed, new MyOrdering(args));
00014 // where MyOrdering is derived from RandCache::Ordering.
00015 
00017 class RandCache
00018 {
00019  public:
00021   typedef WFMath::MTRand::uint32 uint32;
00023   typedef std::vector<uint32>::size_type size_type;
00024 
00026   struct Ordering {
00027     virtual ~Ordering() {}
00029     virtual size_type operator()(int x, int y) = 0;
00030   };
00031 
00036   RandCache(uint32 seed, Ordering* o) :
00037         m_rand(seed), m_ordering(o) {}
00043   RandCache(uint32* seed, uint32 seed_len, Ordering* o) :
00044         m_rand(seed, seed_len), m_ordering(o) {}
00045   ~RandCache() {delete m_ordering;}
00046 
00051   double operator()(int x, int y)
00052   {
00053     size_type cache_order = (*m_ordering)(x, y);
00054 
00055     // make sure we've cached the value
00056     if(cache_order >= m_cache.size()) {
00057       size_type old_size = m_cache.size();
00058       m_cache.resize(cache_order + 64); //do 64 at once
00059       while(old_size < m_cache.size())
00060         m_cache[old_size++] = m_rand.randInt();
00061     }
00062 
00063     return double(m_cache[cache_order] * (1.0/4294967295.0));
00064   }
00065 
00066  private:
00068   WFMath::MTRand m_rand;
00070   std::vector<uint32> m_cache;
00072   Ordering* m_ordering;
00073 };
00074 
00076 class ZeroSpiralOrdering : public RandCache::Ordering
00077 {
00078 public:
00079     RandCache::size_type operator () (int x, int y) 
00080     {
00081         if (x==0 && y==0) return 0;
00082         
00083         int d=std::max(std::abs(x), std::abs(y));
00084         int min=(2*d-1)*(2*d-1);
00085 
00086         if (y == d)  return min + 2*d - x;
00087         if (x == -d) return min + 4*d - y;
00088         if (y == -d) return min + 6*d + x;
00089         else { //if (x == d) {
00090             if (y >=0) return min + y;
00091             else return min + 8*d + y;
00092         }
00093     }
00094 };
00095 
00097 class SpiralOrdering : public ZeroSpiralOrdering
00098 {
00099 private:
00101     int m_x;
00103     int m_y;
00104 public:
00109     SpiralOrdering(int x, int y) : ZeroSpiralOrdering(), m_x(x), m_y(y) {}
00110     RandCache::size_type operator () (int x, int y) 
00111     {
00112         return ZeroSpiralOrdering::operator()(x-m_x, y-m_y);
00113     }
00114 };
00115 
00116 
00117 #endif
00118 
00119 
00120