duktape-nspire/floodfill.h

#ifndef __FLOOD_FILL_H__
#define __FLOOD_FILL_H__ 1

// Floodfill algorithm for drawing module
// Copyright (C) 2015 fgalliat (Xtase)
//
// This file is part of Duktape-nspire.
//
// Duktape-nspire is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Duktape-nspire is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with Duktape-nspire. If not, see <http://www.gnu.org/licenses/>.



/***************************************
 * Flood fill : non recursive algorithm *
 ***************************************/

// later look at : http://www.codeproject.com/Articles/6017/QuickFill-An-efficient-flood-fill-algorithm

typedef struct ffnode_ { void* next; int x, y; } ffnode_t;
typedef struct queue_ { ffnode_t* head; ffnode_t* last; } queue_t;

bool _isEmpty(queue_t* queue) {
	return queue->head == NULL;
}

void _add(queue_t* queue, ffnode_t* node) {
	if ( queue->head == NULL ) { queue->head = node; }
	if ( queue->last != NULL ) { queue->last->next = node; }
	queue->last = node;
}

ffnode_t* _remove(queue_t* queue) {
	if ( queue->head == NULL ) { return NULL; }
	ffnode_t* rem = queue->head;
	queue->head = queue->head->next;
	return rem;
}


queue_t* new_queue() {
	queue_t *queue = (queue_t*)malloc(sizeof(queue_t));
	queue->head = NULL;
	queue->last = NULL;
	return queue;
}

ffnode_t* new_ffnode(int x, int y) {
	ffnode_t *node = (ffnode_t*)malloc(sizeof(ffnode_t));
	node->x = x; node->y = y;
	node->next = NULL;
	return node;
}

// beware w/ memeroy hole
void flood_fill(uint16_t* image, int imageWidth, int imageHeight, int startx, int starty, uint16_t color) {
	ffnode_t *node = NULL;
	ffnode_t *w = NULL;
	ffnode_t *e = NULL;
	ffnode_t *n = NULL;
	ffnode_t *s = NULL;

	queue_t* q = new_queue();

	node = new_ffnode(startx, starty);
	_add(q,node);

	while ( !_isEmpty(q) ) {
		node = _remove(q);
		if ( node->x >= 0 && node->x < imageWidth && node->y >= 0 && node->y < imageHeight ) {
			if (image[ (node->y*imageWidth)+node->x ] != color) {

				image[ (node->y*imageWidth)+node->x ] = color;

				e=new_ffnode( node->x+1, node->y );
				_add(q,e);

				w=new_ffnode( node->x-1, node->y );
				_add(q,w);

				s=new_ffnode( node->x, node->y+1 );
				_add(q,s);

				n=new_ffnode( node->x, node->y-1 );
				_add(q,n);
			}
		}
		//node = NULL;
		free(node);
	}
	//q = NULL;
	free(q);
}

#endif