erode.cpp

#include <queue>
#include <cstdlib>
#include <iostream>
 
static const int n_log2 = 3;		//length of the array log2
static const int n = 1 << n_log2;	//length of the array
static const int ker = 3;			//length of the kernel
 
int abs(int x)
{
	return ((x > 0) ? x : -x);
}

//val is a local max on the intervale[min, max]
//get in the priority queue
struct Intervale
{
	int min;
	int max;
	int val;
 
	Intervale() : min(0), max(n - 1), val(abs(a[0])) {};

	Intervale(const Intervale& rhs) {*this = rhs;}
 
	Intervale next()
	{
		Intervale s;
		int idx = (2 * n + (max + min)) / (2 * (max - min + 1));
		s.val = abs(a[idx]);
		if (a[idx] < 0)
		{
			s.min = min;
			s.max = (max + min) / 2;
			min = s.max + 1;
		} else 
		{
			s.max = max;
			s.min = (max + min) / 2 + 1;
			max = s.min - 1;
		}
		return s;
	}

	Intervale& operator=(const Intervale& rhs)
	{
		min = rhs.min;
		max = rhs.max;
		val = rhs.val;
		return *this;
	}

	static int* a;
	static int n;
};
 
bool operator==(const Intervale& lhs, const Intervale& rhs)
{
	return (lhs.val == rhs.val);
}
 
bool operator!=(const Intervale& lhs, const Intervale& rhs)
{
	return (lhs.val != rhs.val);
}
 
bool operator<=(const Intervale& lhs, const Intervale& rhs)
{
	return (lhs.val <= rhs.val);
}
bool operator>=(const Intervale& lhs, const Intervale& rhs)
{
	return (lhs.val >= rhs.val);
}
 
bool operator<(const Intervale& lhs, const Intervale& rhs)
{
	return (lhs.val < rhs.val);
}
 
bool operator>(const Intervale& lhs, const Intervale& rhs)
{
	return (lhs.val > rhs.val);
}
 
int* Intervale::a;
int Intervale::n;
 
int main()
{
	int* x = (int*)malloc(n * sizeof(int)); //contains the data
	int* a = (int*)malloc(n * sizeof(int));	//contains the wavelet transform
	 
	//fill the array
	for (int i = 0; i < n; i++)
	{
		x[i] = i + 1;
	}
	
	//perform the wavelet transform in O(N)
	for (int j = n_log2 - 1; j >= 0; j--)
	{
		for (int i = 0; i < (1 << j); i++)
		{
			const int xe = x[2 * i];
			const int xo = x[2 * i + 1];
			if (xe > xo)
			{
				x[i] = xe;
				a[i + (1 << j)] = xo;
			} else {
				x[i] = xo;
				a[i + (1 << j)] = -xe;
			}
		}
	}
	 
	a[0] = x[0];
	Intervale::a = a;
	Intervale::n = n;
	Intervale cutter;

	for (int j = 0; j < n; j++)
	{
		
		std::priority_queue<Intervale> queue;
		queue.push(cutter);

		cutter = Intervale();
		//find the local max in O(1)
		while ((queue.top().min < j ||
			    queue.top().max > j + ker - 1) && queue.top().max != queue.top().min)
		{
			if ((queue.top().min < j + 2 &&
				 queue.top().max > j + ker - 1))
				cutter = queue.top();

			queue.push(queue.top().next());

			if (queue.top().min > j + ker - 1 ||
				queue.top().max < j)
			{
				queue.pop();
			}
		}
		x[j] = queue.top().val;
	}
	
	//print the resulting array
	for (int i = 0; i < n; i++)
	{
		std::cout << x[i] << std::endl;
	}

	return 0;
}