/* I'm somehow unable to make a diff with just these 2 functions, this one goes in source\blender\blenlib\intern\math_vector_inline.c */
MINLINE float len_squared_v4v4(const float a[4], const float b[4])
{
	float d[4];

	sub_v4_v4v4(d, b, a);
	return dot_v4v4(d, d);
}

/* this one in colorband.c */
void BKE_colorband_init_from_table_rgba(
        ColorBand *coba,
        const float (*array)[4], const int array_len)
{
	if (!array_len) {
		/* coba is empty, set 1 black stop */
		zero_v3(&coba->data[0].r);
		coba->data[0].a = 1.0f;
		coba->cur = 0;
		coba->tot = 1;
                return;
	}

	float *stops = MEM_mallocN(sizeof(float)*array_len, "Colorband_stop_table");
	bool *active = MEM_mallocN(sizeof(bool)*array_len, "colorband_active_table");

	/* Step 1, assign every color it's stop so it won't change the sampling distribution */
	/* later on when we remove colors */
	float step = 1.0f / max_ff(array_len - 1, 1);
	for (int i = 0; i < array_len; i++) {
		stops[i] = i * step;
		active[i] = true;
	}

	int current_array_len = 1; /* first color is always active */
	
	/* step 2,even if we have less than MAXCOLORBAND stops de-activate any color that */
	/* has the same color as *both* it's neighbors */
	for (int i = 1; i < array_len-1; i++) {
		float distance_left = len_squared_v4v4(array[i], array[i - 1]);
		float distance_right = len_squared_v4v4(array[i], array[i + 1]);
		active[i] = distance_left > 0 || distance_right > 0;
		if (active[i])
			current_array_len++;
	}

	/*  step 3 loop though all stops and eliminate the one closest to its neighbors until */
	/*  we have reached the number of stops needed */
	while (current_array_len >= MAXCOLORBAND) {
		float min_distance = FLT_MAX;
		int current_elimination_target = -1;
		for (int i = 1; i < array_len - 1; i++) {
			if (active[i]) {
				int left_neighbor, right_neighbor;

				/* this can surely be optimzed a little further, but given the array size */
				/* will be rather small most of the time and this code will run rather */
				/* infrequently guess this will have to do for now */

				for (left_neighbor = i - 1; left_neighbor >= 0; left_neighbor--) {
					if (active[left_neighbor])
						break;
				}
				
				for (right_neighbor = i + 1; right_neighbor < array_len; right_neighbor++) {
					if (active[right_neighbor])
						break;
				}
				BLI_assert(active[left_neighbor]);
				BLI_assert(active[right_neighbor]);
				float distance_left = len_squared_v4v4(array[i], array[left_neighbor]);
				float distance_right = len_squared_v4v4(array[i], array[right_neighbor]);
				float total_distance = distance_left + distance_right;
				if (total_distance < min_distance) {
					min_distance = total_distance;
					current_elimination_target = i;
				}
			}
		}
		BLI_assert(current_elimination_target != -1);
		active[current_elimination_target] = false;
		current_array_len--;
	}

	/* step 3 , we have guaranteed less than MAXCOLORBAND stops now, apply the colorband */
	int current_stop = 0;
	coba->tot = current_array_len;
	for (int i = 0; i < array_len; i++) {
		if (active[i]) {
			copy_v4_v4(&coba->data[current_stop].r, array[i]);
			coba->data[current_stop].pos = stops[i];
			coba->data[current_stop].cur = current_stop;
			current_stop++;
		}
	}
	coba->tot = current_stop;
	coba->cur = 0;

	MEM_freeN(stops);
	MEM_freeN(active);
}

void BKE_colorband_init_from_table_rgba(
        ColorBand *coba,
        const float (*array)[4], const int array_len)
{
	if (!array_len) {
		/* coba is empty, set 1 black stop */
		zero_v3(&coba->data[0].r);
		coba->data[0].a = 1.0f;
		coba->cur = 0;
		coba->tot = 1;
	}

	float *stops = MEM_mallocN(sizeof(float)*array_len, "Colorband_stop_table");
	bool *active = MEM_mallocN(sizeof(bool)*array_len, "colorband_active_table");

	/* Step 1, assign every color it's stop so it won't change the sampling distribution */
	/* later on when we remove colors */
	float step = 1.0f / max_ff(array_len - 1, 1);
	for (int i = 0; i < array_len; i++) {
		stops[i] = i * step;
		active[i] = true;
	}

	int current_array_len = 1; /* first color is always active */
	
	/* step 2,even if we have less than MAXCOLORBAND stops de-activate any color that */
	/* has the same color as *both* it's neighbors */
	for (int i = 1; i < array_len-1; i++) {
		float distance_left = len_squared_v4v4(array[i], array[i - 1]);
		float distance_right = len_squared_v4v4(array[i], array[i + 1]);
		active[i] = distance_left > 0 || distance_right > 0;
		if (active[i])
			current_array_len++;
	}

	/*  step 3 loop though all stops and eliminate the one closest to its neighbors until */
	/*  we have reached the number of stops needed */
	while (current_array_len >= MAXCOLORBAND)
	{
		float min_error = FLT_MAX;
		int current_elimination_target = -1;
		for (int i = 1; i < array_len - 1; i++) {
			if (active[i]) {
				int left_neighbor, right_neighbor;

				/* this can surely be optimzed a little further, but given the array size */
				/* will be rather small most of the time and this code will run rather */
				/* infrequently guess this will have to do for now */

				for (left_neighbor = i - 1; left_neighbor >= 0; left_neighbor--) {
					if (active[left_neighbor])
						break;
				}
				
				for (right_neighbor = i + 1; right_neighbor < array_len; right_neighbor++) {
					if (active[right_neighbor])
						break;
				}
				BLI_assert(active[left_neighbor]);
				BLI_assert(active[right_neighbor]);
				
				/* if we were to remove this stop, the error introduced would be the size of the tringle in 3d space between all 3 points involved */
				float error = area_tri_v3(array[i], array[left_neighbor], array[right_neighbor]);

				/* in theory this should have done the trick, but somehow if we fudge it like this, it visually looks better */
				error = fabs(error - len_v3v3(array[left_neighbor], array[right_neighbor]));

				/* adjust the error for distance between stops, ie stops closer together have a smaller error */
				error = error * (stops[right_neighbor] - stops[left_neighbor]);

				if (error < min_error) {
					min_error = error;
					current_elimination_target = i;
				}
			}
		}
		BLI_assert(current_elimination_target != -1);
		active[current_elimination_target] = false;
		current_array_len--;
	}

	/* step 3 , we have guaranteed less than MAXCOLORBAND stops now, apply the colorband */
	int current_stop = 0;
	coba->tot = current_array_len;
	for (int i = 0; i < array_len; i++) {
		if (active[i]) {
			copy_v4_v4(&coba->data[current_stop].r, array[i]);
			coba->data[current_stop].pos = stops[i];
			coba->data[current_stop].cur = current_stop;
			current_stop++;
		}
	}
	coba->tot = current_stop;
	coba->cur = 0;

	MEM_freeN(stops);
	MEM_freeN(active);
}