//
// Tools_Paletize.cpp
//
// Copyright (C) 2003 Rebellion, All Rights Reserved.
//

/*

Compute a palette using 
OcTrees.
Author: Jake Hotson

Based on Jamie's implementation of the 'Wu' algorithm,
and an idea I think he had to improve it, which I didn't understand at the time

However, the main goal of this program is to provide an algorithm which
can generate a part-palette given any number preset colours which define the rest.
It knows about the preset colours, so will use this knowledge
to complete the palette which gives the best spread over the input colours.

If the number of preset colours exceeds the desired palette size, then
the output palette will be the best representation of the preset colours.

The other advantage over Wu's algorithm is the ability to split
colour space boxes down to the unit level, though will only do
this when the boxes become sufficiently small.

I am using doubles for the statistics, because the sums of squares can easily
exceed the bound for a 32-bit integer, and floats do not provide enough precision
when small sumbers are added to or subtracted from much larger numbers.

On the negative side, the algorithm is slower (though still quite quick),
particularly so when the input data covers a lot of colour space.
The time taken varies logarithmically with the number of palette colours required.

'darken-flag' has to be implemented by the caller who inserts colours,
by inserting darker versions of colours into the tree in your desired manner.
There is no 'unique-flag' support, though this would be fairly easy to add.

There is potential for this to be adapted for more general purposes, such as
finite vector spaces of any dimension...

To use, first declare an object of type PG_ColourOcTree:

	PG_ColourOcTree t;

Insert image colours with a pixel count using the Insert member function:

	t.Insert(PG_Pixel(RED_VAL,GREEN_VAL,BLUE_VAL),COUNT);

Insert any preset colours using the constant PG_PRESETCOLOUR instead of a count:

	t.Insert(PG_Pixel(RED_VAL,GREEN_VAL,BLUE_VAL),PG_PRESETCOLOUR);

Allocate space for the palette, and fill it using Compute_Palette:

	PG_Pixel * p = new PG_Pixel[256];
	int palette_size = t.Compute_Palette(&p[1],255); // reserves colour 0 for transparency
	// palette_size will only be less than 255 if there were fewer than 255 original colours

Note:

The Insert function accumulates statistics each time it is called, and would perform
unnecessary calculations if the same colour pixel were inserted more than once.
One optimizing solution would be to build up some kind of Hash-table Histogram, and then
only call 'Insert' with the total count for each different colour pixel.

Alteranively the function Store could be used in place of Insert:

	t.Store(PG_Pixel(RED_VAL,GREEN_VAL,BLUE_VAL),COUNT);

And after all Store operations have been done,
the total statistics should be calculated with Correct_Statistics:

	t.Correct_Statistics();

If you want to include darker/brighter versions of colours, eg. for lighting effects,
I recommend adding only the original colours to one tree, using 'Store'.
Then create another PG_ColourOcTree, and unload the colours from the first tree,
using 'Remove_Any_Colour' which returns a PG_PixelCount structure with members r,g,b and n.
You can then manipulate the r,g,b values as required and add each new colour to the new
tree using 'Store'. You can use 'Num_Colours' to find out how many times you should call
'Remove_Any_Colour' and should also first call 'Correct_Counts' to correct the counts of
colours at nodes of the tree (otherwise Remove_Any_Colour will fail). 'Correct_Counts'
behaves similarly to 'Correct_Statistics' but does not aggregate the sums and sums of
squares, which is unncessary until the second tree has been built using 'Store'.

Here is an example:

	t.Correct_Counts();
	PG_ColourOcTree t2;
	for (int count = t.Num_Colours(); count; --count)
	{
		PG_PixelCount p = t.Remove_Any_Colour();

		for (int shades = NUM_SHADES; shades; --shades)
		{
			int r = TRANSFORM_R(p.r,shades);
			int g = TRANSFORM_G(p.g,shades);
			int b = TRANSFORM_B(p.b,shades);

			t2.Store(PG_Pixel(r,g,b),p.n);
		}
	}

	t2.Correct_Statistics();

You can include preset colours in t, before including darker/brighter colours,
though darker/brighter colours will be added as presets, as n in PG_PixelCount will
hold the constant PG_PRESETCOLOUR whenever a preset colour is obtained.

Alternatively, you can add the preset colours into t2 (recommended), just before calling
'Correct_Statistics' or after if you add them with 'Insert'.

*/

#include "Core/Asura.h"
#include "Debugging/Asura_Assert.h"



#include "ImageProcessing/Tools_Paletize.h"
#include "ImageProcessing/Tools_HeapTemplate.h"

//#include "timewait.h"
//#include "palette.h"


#ifdef COUNT_NODES_ALLOCATED
int PG_NodeData::num_allocated_nodes = 0;
size_t PG_NodeData::memory_allocated = 0;
#endif

void PG_ColourOcTree::Insert(PG_Pixel const & p, int const count)
{
	if (!count) return;

	if (ends[PG_RED] <= p.r)
	{
		ends[PG_RED] = p.r+1;
	}
	if (ends[PG_GREEN] <= p.g)
	{
		ends[PG_GREEN] = p.g+1;
	}
	if (ends[PG_BLUE] <= p.b)
	{
		ends[PG_BLUE] = p.b+1;
	}
	
	PG_Pixel bits(p.r<<PG_RED,p.g<<PG_GREEN,p.b<<PG_BLUE);

	PG_ColourOcTreeNode::Insert_Rc(p,count,PG_COLOURDEPTHBITS,bits);
}

int PG_ColourOcTreeNode::Insert_Rc(PG_Pixel const & p, int const count, int const depth, PG_Pixel & bits)
{
	if (!count) return 0;

	bits.r <<= 1;
	bits.g <<= 1;
	bits.b <<= 1;

	int child = (bits.r & (1<<PG_RED)<<PG_COLOURDEPTHBITS | bits.g & (1<<PG_GREEN)<<PG_COLOURDEPTHBITS | bits.b & (1<<PG_BLUE)<<PG_COLOURDEPTHBITS) >> PG_COLOURDEPTHBITS;

	Asura_Assert(child<1<<PG_N_PRIMARIES,"");

	if (!children[child])
	{
		if (depth > 2)
			children[child] = new PG_ColourOcTreeNode;
		else
			children[child] = new PG_ColourOcTreeLeaf;
	}
	if (!children[child]->Insert_Rc(p,count,depth-1,bits)) return 0;
	
	if (PG_PRESETCOLOUR == count)
	{
		if (!important)
		{
#ifdef COUNT_NODES_ALLOCATED
			memory_allocated += sizeof(PG_ColourStatistic);
#endif
			important = new PG_ColourStatistic;
		}
		important->Include(p,1);
	}
	else helpful.Include(p,count);
	return 1;
}

int PG_ColourOcTreeLeaf::Insert_Rc(PG_Pixel const & p, int const count, int const /* depth */, PG_Pixel & bits)
{
	if (!count) return 0;

	bits.r <<= 1;
	bits.g <<= 1;
	bits.b <<= 1;

	int child = (bits.r & (1<<PG_RED)<<PG_COLOURDEPTHBITS | bits.g & (1<<PG_GREEN)<<PG_COLOURDEPTHBITS | bits.b & (1<<PG_BLUE)<<PG_COLOURDEPTHBITS) >> PG_COLOURDEPTHBITS;

	Asura_Assert(child<1<<PG_N_PRIMARIES,"");

	if (PG_PRESETCOLOUR == count)
	{
		if (leafcounts[child] & PGL_IMPORTANT) return 0;
		leafcounts[child] |= PGL_IMPORTANT;
	}
	else
		leafcounts[child] += count;

	if (PG_PRESETCOLOUR == count)
	{
		if (!important)
		{
#ifdef COUNT_NODES_ALLOCATED
			memory_allocated += sizeof(PG_ColourStatistic);
#endif
			important = new PG_ColourStatistic;
		}
		important->Include(p,1);
	}
	else helpful.Include(p,count);
	return 1;
}


void PG_ColourOcTree::Store(PG_Pixel const & p, int const count)
{
	if (!count) return;

	if (ends[PG_RED] <= p.r)
	{
		ends[PG_RED] = p.r+1;
	}
	if (ends[PG_GREEN] <= p.g)
	{
		ends[PG_GREEN] = p.g+1;
	}
	if (ends[PG_BLUE] <= p.b)
	{
		ends[PG_BLUE] = p.b+1;
	}
	
	PG_Pixel bits(p.r<<PG_RED,p.g<<PG_GREEN,p.b<<PG_BLUE);

	PG_TreeNodeData * node = this;
	for (int depth = PG_COLOURDEPTHBITS-1; depth; --depth)
	{
		int child = bits.r>>depth & 1<<PG_RED | bits.g>>depth & 1<<PG_GREEN | bits.b>>depth & 1<<PG_BLUE;
		PG_TreeNodeData ** cptr = &((PG_ColourOcTreeNode *)node)->children[child];
		if (!*cptr)
		{
			if (depth > 1)
				*cptr = new PG_ColourOcTreeNode;
			else
				*cptr = new PG_ColourOcTreeLeaf;
		}
		node = *cptr;
	}
	int child = bits.r & 1<<PG_RED | bits.g & 1<<PG_GREEN | bits.b & 1<<PG_BLUE;
	
	if (PG_PRESETCOLOUR == count)
		((PG_ColourOcTreeLeaf *)node)->leafcounts[child] |= PGL_IMPORTANT;
	else
		((PG_ColourOcTreeLeaf *)node)->leafcounts[child] += count;
}

void PG_ColourOcTreeNode::Store_Rc(int const count, int const depth, PG_Pixel & bits)
{
	if (!count) return;

	bits.r <<= 1;
	bits.g <<= 1;
	bits.b <<= 1;

	int child = (bits.r & (1<<PG_RED)<<PG_COLOURDEPTHBITS | bits.g & (1<<PG_GREEN)<<PG_COLOURDEPTHBITS | bits.b & (1<<PG_BLUE)<<PG_COLOURDEPTHBITS) >> PG_COLOURDEPTHBITS;

	Asura_Assert(child<1<<PG_N_PRIMARIES,"");

	if (!children[child])
	{
		if (depth > 2)
			children[child] = new PG_ColourOcTreeNode;
		else
			children[child] = new PG_ColourOcTreeLeaf;
	}
	
	children[child]->Store_Rc(count,depth-1,bits);
}

void PG_ColourOcTreeLeaf::Store_Rc(int const count, int const /* depth */, PG_Pixel & bits)
{
	if (!count) return;

	bits.r <<= 1;
	bits.g <<= 1;
	bits.b <<= 1;

	int child = (bits.r & (1<<PG_RED)<<PG_COLOURDEPTHBITS | bits.g & (1<<PG_GREEN)<<PG_COLOURDEPTHBITS | bits.b & (1<<PG_BLUE)<<PG_COLOURDEPTHBITS) >> PG_COLOURDEPTHBITS;

	Asura_Assert(child<1<<PG_N_PRIMARIES,"");

	if (PG_PRESETCOLOUR == count)
		leafcounts[child] |= PGL_IMPORTANT;
	else
		leafcounts[child] += count;
}


void PG_ColourOcTreeNode::Correct_Statistics_Rc(PG_Pixel const & base,int depth)
{
	Reset();

	--depth;

	PG_TreeNodeData ** chptr = children;

	for (int i=0;i<1<<PG_N_PRIMARIES; ++i, ++chptr)
	{
		if (*chptr)
		{
			(*chptr)->Correct_Statistics_Rc
				(
					base +
					PG_Pixel
					(
						i & 1<<PG_RED ? 1<<depth : 0,
						i & 1<<PG_GREEN ? 1<<depth : 0,
						i & 1<<PG_BLUE ? 1<<depth : 0
					),
					depth
				);
			
			*this += **chptr;
		}
	}
}


void PG_ColourOcTreeLeaf::Correct_Statistics_Rc(PG_Pixel const & base,int /* depth */)
{
	Reset();

	unsigned int * lfptr = leafcounts;

	for (int i=0;i<1<<PG_N_PRIMARIES; ++i, ++lfptr)
	{
		if (*lfptr)
		{
			if (*lfptr & ~PGL_IMPORTANT)
			{
				helpful.Include(base + PG_Pixel(i>>PG_RED & 1, i>>PG_GREEN & 1, i>>PG_BLUE & 1), *lfptr & ~PGL_IMPORTANT);
			}
			if (*lfptr & PGL_IMPORTANT)
			{
				if (!important)
				{
#ifdef COUNT_NODES_ALLOCATED
					memory_allocated += sizeof(PG_ColourStatistic);
#endif
					important = new PG_ColourStatistic;
				}
				important->Include(base + PG_Pixel(i>>PG_RED & 1, i>>PG_GREEN & 1, i>>PG_BLUE & 1), 1);
			}
		}
	}
}


void PG_ColourOcTreeNode::Correct_Counts(void)
{
	Reset();

	PG_TreeNodeData ** chptr = children;

	for (int i=0;i<1<<PG_N_PRIMARIES; ++i, ++chptr)
	{
		if (*chptr)
		{
			(*chptr)->Correct_Counts();
			
			helpful.n += (*chptr)->helpful.n;
			if ((*chptr)->important)
			{
				if (!important)
				{
#ifdef COUNT_NODES_ALLOCATED
					memory_allocated += sizeof(PG_ColourStatistic);
#endif
					important = new PG_ColourStatistic;
				}
				important->n += (*chptr)->important->n;
			}
		}
	}
}


void PG_ColourOcTreeLeaf::Correct_Counts(void)
{
	Reset();

	unsigned int * lfptr = leafcounts;

	for (int i=0;i<1<<PG_N_PRIMARIES; ++i, ++lfptr)
	{
		if (*lfptr)
		{
			if (*lfptr & ~PGL_IMPORTANT)
			{
				helpful.n += *lfptr & ~PGL_IMPORTANT;
			}
			if (*lfptr & PGL_IMPORTANT)
			{
				if (!important)
				{
#ifdef COUNT_NODES_ALLOCATED
					memory_allocated += sizeof(PG_ColourStatistic);
#endif
					important = new PG_ColourStatistic;
				}
				++ important->n;
			}
		}
	}
}


void PG_ColourOcTree::Remove(PG_Pixel const & p)
{
	PG_Pixel bits(p.r<<PG_RED,p.g<<PG_GREEN,p.b<<PG_BLUE);

	PG_ColourOcTreeNode::Remove_Rc(p,bits);
}

void PG_ColourOcTreeNode::Remove_Rc(PG_Pixel const & p, PG_Pixel & bits)
{
	bits.r <<= 1;
	bits.g <<= 1;
	bits.b <<= 1;

	int child = (bits.r & (1<<PG_RED)<<PG_COLOURDEPTHBITS | bits.g & (1<<PG_GREEN)<<PG_COLOURDEPTHBITS | bits.b & (1<<PG_BLUE)<<PG_COLOURDEPTHBITS) >> PG_COLOURDEPTHBITS;

	Asura_Assert(child<1<<PG_N_PRIMARIES,"");

	if (!children[child])
	{
		Asura_Assert(0,"");
		//your_printf("Unable to remove (%d,%d,%d)\n",p.r,p.g,p.b);
		//wait_seconds(0.1);
		return;
	}

	*this -= *children[child];
	children[child]->Remove_Rc(p,bits);

	if (*children[child]) *this += *children[child];
	else
	{
		delete children[child];
		children[child] = 0;
	}
}


void PG_ColourOcTreeLeaf::Remove_Rc(PG_Pixel const & p, PG_Pixel & bits)
{
	bits.r <<= 1;
	bits.g <<= 1;
	bits.b <<= 1;

	int child = (bits.r & (1<<PG_RED)<<PG_COLOURDEPTHBITS | bits.g & (1<<PG_GREEN)<<PG_COLOURDEPTHBITS | bits.b & (1<<PG_BLUE)<<PG_COLOURDEPTHBITS) >> PG_COLOURDEPTHBITS;

	Asura_Assert(child<1<<PG_N_PRIMARIES,"");

	if (!leafcounts[child])
	{
		Asura_Assert(0,"");
		//your_printf("Unable to remove (%d,%d,%d)\n",p.r,p.g,p.b);
		//wait_seconds(0.1);
		return;
	}

	if (leafcounts[child] & PGL_IMPORTANT)
	{
		Asura_Assert(important,"");
		PG_ColourStatistic subtract;
		subtract.Include(p,1);
		*important -= subtract;
		if (!important->n)
		{
#ifdef COUNT_NODES_ALLOCATED
			memory_allocated -= sizeof(PG_ColourStatistic);
#endif
			delete important;
			important = 0;
		}
	}
	if (leafcounts[child] & ~PGL_IMPORTANT)
	{
		PG_ColourStatistic subtract;
		subtract.Include(p,leafcounts[child] & ~PGL_IMPORTANT);
		helpful -= subtract;
	}
	leafcounts[child] = 0;
}


int PG_ColourOcTreeNode::Num_Colours(void) const
{
	int count = 0;

	for (int i=0; i<1<<PG_N_PRIMARIES; ++i)
	{
		if (children[i]) count += children[i]->Num_Colours();
	}

	return count;
}


int PG_ColourOcTreeLeaf::Num_Colours(void) const
{
	int count = 0;

	for (int i=0; i<1<<PG_N_PRIMARIES; ++i)
	{
		if (leafcounts[i]) ++count;
	}

	return count;
}


PG_PixelCount PG_ColourOcTreeNode::Remove_Any_Colour_Rc(PG_Pixel const & base, int depth)
{
	--depth;
	
	for (int i=0; i<1<<PG_N_PRIMARIES; ++i)
	{
		if (children[i])
		{
			*this -= *children[i];

			PG_PixelCount retval
				(
					i & 1<<PG_RED ? 1<<depth : 0,
					i & 1<<PG_GREEN ? 1<<depth : 0,
					i & 1<<PG_BLUE ? 1<<depth : 0,
					0
				);
			retval += children[i]->Remove_Any_Colour_Rc(base + retval, depth);

			if (*children[i]) *this += *children[i];
			else
			{
				delete children[i];
				children[i] = 0;
			}
			return retval;
		}
	}

	return PG_PixelCount(0,0,0,0);
}


PG_PixelCount PG_ColourOcTreeLeaf::Remove_Any_Colour_Rc(PG_Pixel const & base, int /* depth */)
{
	for (int i=0; i<1<<PG_N_PRIMARIES; ++i)
	{
		if (leafcounts[i])
		{
			PG_PixelCount retval
				(
					i >> PG_RED & 1,
					i >> PG_GREEN & 1,
					i >> PG_BLUE & 1,
					0
				);

			if (leafcounts[i] & ~PGL_IMPORTANT)
			{
				PG_ColourStatistic subtract;
				subtract.Include(base + retval,leafcounts[i] & ~PGL_IMPORTANT);
				helpful -= subtract;
				retval.n = leafcounts[i] & ~PGL_IMPORTANT;
			}
			if (leafcounts[i] & PGL_IMPORTANT)
			{
				Asura_Assert(important,"");
				PG_ColourStatistic subtract;
				subtract.Include(base + retval,1);
				*important -= subtract;
				if (!important->n)
				{
#ifdef COUNT_NODES_ALLOCATED
					memory_allocated -= sizeof(PG_ColourStatistic);
#endif
					delete important;
					important = 0;
				}
				retval.n = (unsigned int)PG_PRESETCOLOUR;
			}
			leafcounts[i] = 0;

			return retval;
		}
	}
	return PG_PixelCount(0,0,0,0);
}


PG_PixelCount PG_ColourOcTreeNode::Any_Colour_Rc(int depth) const
{
	--depth;

	for (int i=0; i<1<<PG_N_PRIMARIES; ++i)
	{
		if (children[i])
		{
			return
				PG_PixelCount (
					i & 1<<PG_RED ? 1<<depth : 0,
					i & 1<<PG_GREEN ? 1<<depth : 0,
					i & 1<<PG_BLUE ? 1<<depth : 0,
					0
				)
				+ children[i]->Any_Colour_Rc(depth);
		}
	}
	return PG_PixelCount(0,0,0,0);
}


PG_PixelCount PG_ColourOcTreeLeaf::Any_Colour_Rc(int /* depth */) const
{
	for (int i=0; i<1<<PG_N_PRIMARIES; ++i)
	{
		if (leafcounts[i])
		{
			return
				PG_PixelCount (
					i >> PG_RED & 1,
					i >> PG_GREEN & 1,
					i >> PG_BLUE & 1,
					leafcounts[i] & PGL_IMPORTANT ? PG_PRESETCOLOUR : leafcounts[i]
				);
		}
	}
	return PG_PixelCount(0,0,0,0);
}


void PG_ColourOcTree::MakeBySplitting( PG_Pixel const & base, PG_ColourOcTree & tree, PG_Primary const p, int const split, int depth )
{
	DeleteChildren();

	Reset();

	for (int q=0; q<PG_N_PRIMARIES; ++q)
	{
		ends[q] = tree.ends[q];
		starts[q] = tree.starts[q];
	}

	tree.ends[p] = split;
	starts[p] = split;

	if (split>=ends[p]) return;
	if (split<=tree.starts[p])
	{
		PG_TreeNodeData * * srcP = tree.children;
		PG_TreeNodeData * * destP = children;
		for (int i=1<<PG_N_PRIMARIES; i; --i, ++srcP, ++destP)
		{
			if (*srcP)
			{
				*destP = *srcP;
				*srcP = 0;
			}
		}
		PG_TreeNodeData::operator = (tree);
		tree.Reset();
		return;
	}

	PG_ColourOcTreeNode::MakeBySplitting(base,tree,p,split,depth);
}


void PG_ColourOcTreeNode::MakeBySplitting( PG_Pixel const & base, PG_ColourOcTreeNode & tree, PG_Primary const p, int const split, int depth )
{
	DeleteChildren();

	Reset();

	if (split>=1<<depth) return;
	if (split<=0)
	{
		PG_TreeNodeData * * srcP = tree.children;
		PG_TreeNodeData * * destP = children;
		for (int i=1<<PG_N_PRIMARIES; i; --i, ++srcP, ++destP)
		{
			if (*srcP)
			{
				*destP = *srcP;
				*srcP = 0;
			}
		}
		PG_TreeNodeData::operator = (tree);
		tree.Reset();
		return;
	}

	Asura_Assert(0<split && split<1<<depth,"");

	--depth;

	int const midpt = 1<<depth;
	int const primary_mask = 1<<p;

	if (split < midpt)
	{
		PG_TreeNodeData * * srcP = tree.children;
		PG_TreeNodeData * * destP = children;
		for (int i=0; i<1<<PG_N_PRIMARIES; ++i, ++srcP, ++destP)
		{
			if (*srcP)
			{
				if (i & primary_mask)
				{
					tree -= **srcP;
					*destP = *srcP;
					*srcP = 0;
					*this += **destP;
				}
				else
				{
					tree -= **srcP;
					if (depth>1)
						*destP = new PG_ColourOcTreeNode(base + PG_Pixel(i & 1<<PG_RED ? midpt : 0, i & 1<<PG_GREEN ? midpt : 0, i & 1<<PG_BLUE ? midpt : 0),*(PG_ColourOcTreeNode *)*srcP,p,split,depth);
					else
						*destP = new PG_ColourOcTreeLeaf(base + PG_Pixel(i & 1<<PG_RED ? midpt : 0, i & 1<<PG_GREEN ? midpt : 0, i & 1<<PG_BLUE ? midpt : 0),*(PG_ColourOcTreeLeaf *)*srcP,p,split);
					tree += **srcP;
					*this += **destP;
				}
			}
		} 
	}
	else if (split == midpt)
	{
		PG_TreeNodeData * * srcP = tree.children;
		PG_TreeNodeData * * destP = children;
		for (int i=0; i<1<<PG_N_PRIMARIES; ++i, ++srcP, ++destP)
		{
			if (i & primary_mask && *srcP)
			{
				tree -= **srcP;
				*destP = *srcP;
				*srcP = 0;
				*this += **destP;
			}
		} 
	}
	else // split > midpt
	{
		PG_TreeNodeData * * srcP = tree.children;
		PG_TreeNodeData * * destP = children;
		for (int i=0; i<1<<PG_N_PRIMARIES; ++i, ++srcP, ++destP)
		{
			if (i & primary_mask && *srcP)
			{
				tree -= **srcP;
				if (depth>1)
					*destP = new PG_ColourOcTreeNode(base + PG_Pixel(i & 1<<PG_RED ? midpt : 0, i & 1<<PG_GREEN ? midpt : 0, i & 1<<PG_BLUE ? midpt : 0),*(PG_ColourOcTreeNode *)*srcP,p,split-midpt,depth);
				else
					*destP = new PG_ColourOcTreeLeaf(base + PG_Pixel(i & 1<<PG_RED ? midpt : 0, i & 1<<PG_GREEN ? midpt : 0, i & 1<<PG_BLUE ? midpt : 0),*(PG_ColourOcTreeLeaf *)*srcP,p,split-midpt);
				tree += **srcP;
				*this += **destP;
			}
		} 
	}
}


void PG_ColourOcTreeLeaf::MakeBySplitting( PG_Pixel const & base, PG_ColourOcTreeLeaf & tree, PG_Primary const p, int const split)
{
	Reset();

	if (split>=2) return;
	if (split<=0)
	{
		unsigned int * srcP = tree.leafcounts;
		unsigned int * destP = leafcounts;
		for (int i=1<<PG_N_PRIMARIES; i; --i, ++srcP, ++destP)
		{
			if (*srcP)
			{
				*destP = *srcP;
				*srcP = 0;
			}
			PG_TreeNodeData::operator = (tree);
			tree.Reset();
		}
		return;
	}

	int const primary_mask = 1<<p;

	unsigned int * srcP = tree.leafcounts;
	unsigned int * destP = leafcounts;
	for (int i=0; i<1<<PG_N_PRIMARIES; ++i, ++srcP, ++destP)
	{
		if (i & primary_mask && *srcP)
		{
			if (*srcP & PGL_IMPORTANT)
			{
				Asura_Assert (tree.important,"");
				PG_ColourStatistic move;
				move.Include(base + PG_Pixel(i>>PG_RED & 1, i>>PG_GREEN & 1, i>>PG_BLUE & 1),1);
				*tree.important -= move;
				if (!tree.important->n)
				{
#ifdef COUNT_NODES_ALLOCATED
					memory_allocated -= sizeof(PG_ColourStatistic);
#endif
					delete tree.important;
					tree.important = 0;
				}
				if (!important)
				{
#ifdef COUNT_NODES_ALLOCATED
					memory_allocated += sizeof(PG_ColourStatistic);
#endif
					important = new PG_ColourStatistic;
				}
				*important += move;
			}
			if (*srcP & ~PGL_IMPORTANT)
			{
				PG_ColourStatistic move;
				move.Include(base + PG_Pixel(i>>PG_RED & 1, i>>PG_GREEN & 1, i>>PG_BLUE & 1),*srcP & ~PGL_IMPORTANT);
				tree.helpful -= move;
				helpful += move;
			}
			
			*destP = *srcP;
			*srcP = 0;
		}
	} 
}



PG_NodeData PG_ColourOcTree::StatisticForRange(PG_Primary const p, int const start, int const end) const
{
	if (start<=starts[p] && end>=ends[p])
		return *this;

	return PG_ColourOcTreeNode::StatisticForRange_Rc(PG_Pixel(0,0,0),p,start,end,PG_COLOURDEPTHBITS);
}

PG_NodeData PG_ColourOcTreeNode::StatisticForRange_Rc(PG_Pixel const & base, PG_Primary const p, int const start, int const end, int depth) const
{
	if (start<=0 && end>=1<<depth) return *this;

	PG_NodeData stats;

	--depth;

	int const midpt = 1<<depth;
	int const primary_mask = 1<<p;

	if (start<midpt)
	{
		PG_TreeNodeData * const * cptr = children;
		for (int i=0; i<1<<PG_N_PRIMARIES; ++i, ++cptr)
			if (!(i & primary_mask) && *cptr)
				stats += (*cptr)->StatisticForRange_Rc(base + PG_Pixel(i & 1<<PG_RED ? midpt : 0, i & 1<<PG_GREEN ? midpt : 0, i & 1<<PG_BLUE ? midpt : 0),p,start,end,depth);
	}
	if (end>midpt)
	{
		PG_TreeNodeData * const * cptr = children;
		for (int i=0; i<1<<PG_N_PRIMARIES; ++i, ++cptr)
			if (i & primary_mask && *cptr)
				stats += (*cptr)->StatisticForRange_Rc(base + PG_Pixel(i & 1<<PG_RED ? midpt : 0, i & 1<<PG_GREEN ? midpt : 0, i & 1<<PG_BLUE ? midpt : 0),p,start-midpt,end-midpt,depth);
	}

	return stats;
}


PG_NodeData PG_ColourOcTreeLeaf::StatisticForRange_Rc(PG_Pixel const & base, PG_Primary const p, int const start, int const end, int /* depth */) const
{
	if (start<=0 && end>=2) return *this;

	PG_NodeData stats;

	int const primary_mask = 1<<p;

	if (start<1)
	{
		unsigned int const * cptr = leafcounts;
		for (int i=0; i<1<<PG_N_PRIMARIES; ++i, ++cptr)
			if (!(i & primary_mask) && *cptr)
			{
				if (*cptr & PGL_IMPORTANT)
				{
					if (!stats.important)
					{
#ifdef COUNT_NODES_ALLOCATED
						memory_allocated += sizeof(PG_ColourStatistic);
#endif
						stats.important = new PG_ColourStatistic;
					}
					stats.important->Include(base + PG_Pixel(i>>PG_RED & 1, i>>PG_GREEN & 1, i>>PG_BLUE & 1),1);
				}
				if (*cptr & ~PGL_IMPORTANT)
					stats.helpful.Include(base + PG_Pixel(i>>PG_RED & 1, i>>PG_GREEN & 1, i>>PG_BLUE & 1),*cptr & ~PGL_IMPORTANT);
			}
	}
	if (end>1)
	{
		unsigned int const * cptr = leafcounts;
		for (int i=0; i<1<<PG_N_PRIMARIES; ++i, ++cptr)
			if (i & primary_mask && *cptr)
			{
				if (*cptr & PGL_IMPORTANT)
				{
					if (!stats.important)
					{
#ifdef COUNT_NODES_ALLOCATED
						memory_allocated += sizeof(PG_ColourStatistic);
#endif
						stats.important = new PG_ColourStatistic;
					}
					stats.important->Include(base + PG_Pixel(i>>PG_RED & 1, i>>PG_GREEN & 1, i>>PG_BLUE & 1),1);
				}
				if (*cptr & ~PGL_IMPORTANT)
					stats.helpful.Include(base + PG_Pixel(i>>PG_RED & 1, i>>PG_GREEN & 1, i>>PG_BLUE & 1),*cptr & ~PGL_IMPORTANT);
			}
	}

	return stats;
}


int PG_ColourOcTree::BestSplit(PG_Primary const p, int start, int end, PG_SplitNodeData const * start_stats, PG_SplitNodeData const * end_stats)
{
	if (start==end) return start;

	Asura_Assert(start<end,"");
	
	if (start+1==end)
	{
		// ensure we have statistics for start and end
		PG_SplitNodeData sn_start, sn_end;
		if (!start_stats)
		{
			if (end_stats)
			{
				// this might be quicker...
				sn_start.cumul_high = StatisticForRange(p,start,end);
				sn_start.cumul_high += end_stats->cumul_high;
			}
			else
				// ...than this
				sn_start.cumul_high = StatisticForRange(p,start,ends[p]);
			sn_start.cumul_low = *this;
			sn_start.cumul_low -= sn_start.cumul_high;
			start_stats = &sn_start;
		}
		if (!end_stats)
		{
			sn_end.cumul_low = StatisticForRange(p,start,end);
			sn_end.cumul_low += start_stats->cumul_low;
			sn_end.cumul_high = *this;
			sn_end.cumul_high -= sn_end.cumul_low;
			end_stats = &sn_end;
		}
		// decide whether start or end is the best split
		PG_Variance var_start(start_stats->cumul_low);
		var_start += PG_Variance(start_stats->cumul_high);
		
		PG_Variance var_end(end_stats->cumul_low);
		var_end += PG_Variance(end_stats->cumul_high);

		if (var_end < var_start)
			return end;
		//else
		//(else removed to get rid of stupid unreachable code warning)
		return start;
	}	

	int midpt = (start+end)>>1;

	PG_SplitNodeData sn_mid;

	if (start_stats)
	{
		// this...
		sn_mid.cumul_low = StatisticForRange(p,start,midpt);
		sn_mid.cumul_low += start_stats->cumul_low;
		sn_mid.cumul_high = *this;
		sn_mid.cumul_high -= sn_mid.cumul_low;
	}
	else if (end_stats)
	{
		// ...and this might be quicker...
		sn_mid.cumul_high = StatisticForRange(p,midpt,end);
		sn_mid.cumul_high += end_stats->cumul_high;
		sn_mid.cumul_low = *this;
		sn_mid.cumul_low -= sn_mid.cumul_high;
	}
	else
	{
		// ...than this
		sn_mid.cumul_low = StatisticForRange(p,starts[p],midpt);
		sn_mid.cumul_high = *this;
		sn_mid.cumul_high -= sn_mid.cumul_low;
	}

	PG_Variance var_low(sn_mid.cumul_low);
	PG_Variance var_high(sn_mid.cumul_high);

	if (var_low < var_high)
		return BestSplit(p,midpt,end,&sn_mid,end_stats);
	//else
	//(else removed to get rid of stupid unreachable code warning)
	return BestSplit(p,start,midpt,start_stats,&sn_mid);
}


PG_Variance::PG_Variance(PG_NodeData const & s) : cnt_imp(s.important ? s.important->n : 0)
{
	PG_RGBData<double> temp_var;

	if (!cnt_imp)
		temp_var = s.helpful.Sum_D_Sq();
	else if	(1==cnt_imp)
		temp_var = s.helpful.Sum_D_Sq(s.important->sum);
	else
		temp_var = s.important->Sum_D_Sq();

	vari = temp_var.r + temp_var.g + temp_var.b;

	if (temp_var.r > temp_var.g && temp_var.r >= temp_var.b)
	{
		var_worst = PG_RED;
	}
	else if (temp_var.g >= temp_var.b)
	{
		var_worst = PG_GREEN;
	}
	else
	{
		var_worst = PG_BLUE;
	}
}

int PG_Variance::operator < (PG_Variance const & g) const
{
	if (cnt_imp > 1)
	{
		if (g.cnt_imp > 1)
		{
			return vari < g.vari;
		}
		return 0;
	}
	if (g.cnt_imp > 1) return 1;
	return vari < g.vari;
}


//////////////////

unsigned PG_ColourOcTree::Compute_Palette(PG_Pixel * palette, unsigned const ncols)
{
	unsigned total_ncols = Num_Colours();
	
	Ordered_Heap<PG_Pixel> out_cols; // we can sort by luminosity
	
	if (total_ncols > ncols)
	{
		Ordered_Heap<PG_ColourOcTree_Header> boxes(this);

		#if cencon
		while (boxes.size() < ncols && !twCancel)
		#else
		while (boxes.size() < ncols)
		#endif
		{
			PG_ColourOcTree_Header worst_box = boxes.highest_entry();
			boxes.delete_highest();
			PG_ColourOcTree * tree = (PG_ColourOcTree *) worst_box;
			PG_Primary split_primary = (PG_Primary) worst_box;
			int split_value = tree->BestSplit(split_primary);
			boxes.add_entry(new PG_ColourOcTree(*tree,split_primary,split_value));
			boxes.add_entry(tree);
			#ifdef PROGRESS_COMPUTE
			if (!(boxes.size() & 15) && palette_verbose) your_printf("%d ",boxes.size());
			#endif
		}
		#ifdef PROGRESS_COMPUTE
		if (palette_verbose) your_printf("\n",boxes.size());
		#endif

		for (OHIF<PG_ColourOcTree_Header> output(&boxes); !output.done(); output.next())
		{
			PG_ColourOcTree * tree = (PG_ColourOcTree *) output();
			out_cols.add_entry(tree->Mean());
			if (tree != this) delete tree;
		}
	}
	else
	{
		for (unsigned i = total_ncols; i; --i)
			out_cols.add_entry(Remove_Any_Colour());
	}

	for (OHIF<PG_Pixel> write(&out_cols); !write.done(); write.next(), palette++)
		*palette = write();

	return out_cols.size();
}


