// Source: "Software Design ...", John A Robinson, Newnes, 2004, page 324.
// Implementation for medianfilter class, created Thu Aug 28 12:42:56 2003
// Revised Aug 28 ... Corrected same day
// Version 0.1
// John Robinson

#include "medianfilter.h"
#include <cstdlib>
#include <iostream>
using namespace std;


// bufitem now defined in implementation file because not part of interface
class bufitem {
// All items private. Just used by friend medianfilter
	itemtype value;
	bufitem *smaller;	// Using pointers rather than indices means
				// bufitems can be collected into other DSs
				// than just arrays.
	bufitem *greater;
	bufitem () {
		value = 0;
		smaller = 0;
		greater = 0;
		}
	~bufitem() {
		}
	void set(const itemtype v) {
		value = v;
		}
	itemtype get() const {
		return value;
		}
	void initpointers(bufitem *const predecessor,bufitem *const successor) {
		smaller = predecessor;
		greater = successor;
		}
	void putafter(bufitem *predecessor) {
		// Break existing link from predecessor to its successor 
		// and insert this one
		bufitem *successor = predecessor->greater;
		predecessor->greater = this;
		if (successor)
			successor->smaller = this;
		smaller = predecessor;
		greater = successor;
		}
	void putbefore(bufitem *successor) {
		// Can't just use putafter(successor->before) because
		// this may be 0 on list
		bufitem *predecessor = successor->smaller;
		successor->smaller = this;
		if (predecessor)
			predecessor->greater = this;
		smaller = predecessor;
		greater = successor;
		}
	void removefromlists() {
		if (smaller) 
			smaller->greater = greater;
		if (greater)
			greater->smaller = smaller;
		}
	bufitem *next() const {
		return greater;
		}
	bufitem *prev() const {
		return smaller;
		}
	friend class medianfilter;
	};

medianfilter::medianfilter(const int len) {
	if (len < 0) {
	// Can add an upper limit later if necessary
		cout << "Specified length " << len << " is out of bounds\n";
		cout << "Using length = 15 instead\n";
		length = 15;
		}
	else
		length = len;
	buf = new bufitem[length];
	// Have to treat the items at each end differently to the others
	// because the are at the ends of the linked lists
	buf[0].set(0);
	buf[0].initpointers(0, &buf[1]);
	for (int i = 1; i < length-1; i++) {
		buf[i].set(0);
		buf[i].initpointers(&buf[i-1],&buf[i+1]);
		}
	buf[length-1].set(0);
	buf[length-1].initpointers(&buf[length-2],0);
	nextinsertion = 0;
	medianloc = &buf[length/2];// Actually doesn't matter because initial
				   // buf values are all equal to 0
}

medianfilter::~medianfilter() {
}

itemtype medianfilter::addnext(const itemtype newval) {
	int thisinsertion = nextinsertion++;
	if (nextinsertion == length)
		nextinsertion = 0;
	itemtype oldval = buf[thisinsertion].get();
	if (newval == oldval)	// Everything fine. Nothing to do
		return oldval;
	bufitem *p = &buf[thisinsertion];
	p->set(newval);
	int movedmedian = 0;
	if (newval > oldval) { // May need to move this node upwards
		if (!p->next() || p->next()->get() >= newval)	
		// Again, don't need to change
			return oldval;
		// Otherwise have to move upwards
		if (p == medianloc) {
			medianloc = p->next();
			movedmedian = 1;
			}
		p = p->next();
		while(p->next()) {
			if (p->next()->get() >= newval) {
				buf[thisinsertion].removefromlists();
				buf[thisinsertion].putafter(p);
				if ((p == medianloc)&&!movedmedian) 
					medianloc = medianloc->next();
				break;
				}
			if ((p == medianloc)&&!movedmedian) {
				medianloc = medianloc->next();
				movedmedian = 1;
				}
			p = p->next();
			}
		if (!p->next()) {
			buf[thisinsertion].removefromlists();
			buf[thisinsertion].putafter(p);
			}
		}
	else {
		if (!p->prev() || p->prev()->get() <= newval)
		// Again, don't need to change
			return oldval;
		// Otherwise have to move downwards
		if (p == medianloc) {
			medianloc = p->prev();
			movedmedian = 1;
			}
		p = p->prev();
		while(p->prev()) {
			if (p->prev()->get() <= newval) {
				buf[thisinsertion].removefromlists();
				buf[thisinsertion].putbefore(p);
				if ((p == medianloc)&&!movedmedian) 
					medianloc = medianloc->prev();
				break;
				}
			if ((p == medianloc)&&!movedmedian) {
				medianloc = medianloc->prev();
				movedmedian = 1;
				}
			p = p->prev();
			}
		if (!p->prev()) {
			buf[thisinsertion].removefromlists();
			buf[thisinsertion].putbefore(p);
			}
		}
	return oldval;
	}

itemtype medianfilter::getmedian() const {
	return medianloc->get();
	}
void medianfilter::print() const {
	for (int i = 0; i < length; i++) {
		cout << "buf[" << i << "] = " << buf[i].get();
		cout << " has address " << (void *) &buf[i];
		cout << ", prev pointer " << (void *) buf[i].prev();
		cout << ", next pointer " << (void *) buf[i].next() << endl;
		}
	cout << "Current buffer index is " << nextinsertion << endl;
	}