algorithm.cpp 3.5 KB
Newer Older
Kirill Terekhov's avatar
Kirill Terekhov committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
#include "inmost.h"
#if defined(USE_MESH)
namespace INMOST
{	
#define CUTOFF 8
	
	static void shortsort(char *lo, char *hi, unsigned width, int (*comp)(const void *, const void *, void *),void (*swap)(void *, void *, void *), void * user_data) 
	{
		char *p, *max;
		
		while (hi > lo) 
		{
			max = lo;
			for (p = lo + width; p <= hi; p += width) if (comp(p, max,user_data) > 0) max = p;
			if( max != hi ) swap(max, hi,user_data);
			hi -= width;
		}
	}
		
	void sort(void *pbase, unsigned num, unsigned width, int (*comp)(const void *, const void *,void *), void (*swap)(void *, void *, void *), void * user_data)
	{
		if( num == 0 ) return;
		char *base = static_cast<char *>(pbase);
		char *lo, *hi;
		char *mid;
		char *l, *h;
		unsigned size;
		char *lostk[30], *histk[30];
		int stkptr;
		
		if (num < 2 || width == 0) return;
		stkptr = 0;
		
		lo = base;
		hi = (char *) base + width * (num - 1);
		
	recurse:
Kirill Terekhov's avatar
Kirill Terekhov committed
38
		size = static_cast<unsigned>((hi - lo) / width) + 1;
Kirill Terekhov's avatar
Kirill Terekhov committed
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167
		
		if (size <= CUTOFF) 
		{
			shortsort(lo, hi, width, comp, swap, user_data);
		} 
		else 
		{
			mid = lo + (size / 2) * width;
			swap(mid, lo,user_data);
			
			l = lo;
			h = hi + width;
			
			while(true)
			{
				do { l += width; } while (l <= hi && comp(l, lo, user_data) <= 0);
				do { h -= width; } while (h > lo && comp(h, lo, user_data) >= 0);
				if (h <= l) break;
				swap(l, h,user_data);
			}
			
			if( lo != h ) swap(lo, h,user_data);
			
			if (h - 1 - lo >= hi - l) 
			{
				if (lo + width < h) 
				{
					lostk[stkptr] = lo;
					histk[stkptr] = h - width;
					++stkptr;
				}
				
				if (l < hi) 
				{
					lo = l;
					goto recurse;
				}
			} 
			else 
			{
				if (l < hi) 
				{
					lostk[stkptr] = l;
					histk[stkptr] = hi;
					++stkptr;
				}
				
				if (lo + width < h) 
				{
					hi = h - width;
					goto recurse;
				}
			}
		}
		
		--stkptr;
		if (stkptr >= 0) 
		{
			lo = lostk[stkptr];
			hi = histk[stkptr];
			goto recurse;
		}
	}
	int binary_search(void * pdata, unsigned num, unsigned width, int comp(const void *,void *), void * user_data)
	{
		if( num == 0 ) return -1;
		char * data = static_cast<char *>(pdata);
		unsigned imin = 0, imax = num-1;
		while (imin < imax)
		{
			int imid = (imax-imin)/2 + imin;
			if ( comp(data+imid*width,user_data) < 0 )
				imin = imid + 1;
			else
				imax = imid;
		}
		if (imax == imin && comp(data+imin*width,user_data) == 0)
			return imin;
		return -1;
	}	



	Mesh::Random::Random(unsigned int seed)
	{
		n = seed;
		a = 1103515245;
		c = 12345;
		m = 1u << (sizeof(unsigned int)*8-1);
	}
	Mesh::Random::Random(const Random & other)
	{
		n = other.n;
		a = other.a;
		c = other.c;
		m = other.m;
	}
	unsigned int Mesh::Random::Number()
	{
		n = (a*n + c)%m;
		return (n << 2) >> 18;
	}
	
	///////////////////////////////////////////////////////////////////////////////////////////////
	// HASH function 
	// detailed description: http://www.isthe.com/chongo/tech/comp/fnv/
	const size_t InitialFNV32 = 2166136261U;
	const size_t FNVMultiple32 = 16777619;
	size_t hashfunci32(const char * pos, int n)
	{
		size_t hash = InitialFNV32;
		for(int i = 0; i < n; i++)
			hash = (hash ^ pos[i]) * FNVMultiple32;
		return hash;
	}
	/*
	const uint64_t InitialFNV64 = 14695981039346656037U;
	const uint64_t FNVMultiple64 = 1099511628211;
	uint64_t hashfunci64(const char * pos, int n)
	{
		uint64_t hash = InitialFNV64;
		for(int i = 0; i < n; i++)
			hash = (hash ^ pos[i]) * FNVMultiple64;
		return hash;
	}
	*/
	///////////////////////////////////////////////////////////////////////////////////////////////
}
#endif