#ifndef _OCTTREE_H
#define _OCTTREE_H
#include"image.h"
 

/// Maximum octree reduction level
static const int O_MaxDepth = 7;

// Number of quantized colors
static const int O_NumColor = 256;

class OctNode           // Octree node
{                       	
  private:
    int level;          // Node level
    BOOL leaf_flag;     // Leaf flag
    BOOL mark_flag;     // Marked flag
    DWORD count;        // Pixel count
    
	ImgRGBColor sum;

    int index;          // Color palette index
    int children;       // Number of child nodes
    OctNode *pchild[8]; // Children node pointers
    OctNode *pnext;     // Next reducible node pointer
    OctNode *pprev;     // Previous reducible node pointer

    int TestBit(BYTE val, int index)
    { return ((val & (1 << index)) > index) ? 1 : 0; }

  public:
    OctNode( int node_level, BOOL leaf )
    {
      int i;    // Loop index

      level = node_level;
      leaf_flag = leaf;
      mark_flag = FALSE;
      count = 0L;
      index = 0;
      children = 0;
      sum=0;

      for (i=0;i<8;i++) pchild[i]=NULL;

      pnext=pprev=NULL;
    };

    BOOL     IsLeaf()   { return leaf_flag; }
    BOOL     IsMark()   { return mark_flag; }    
    DWORD    GetCount() { return count; }
    ImgRGBColor GetColor() { return sum/count; }
    int      GetIndex() { return index; }
    int      GetLevel() { return level; }

    // Determine child node according to color
    int FindChild( ImgRGBColor &c )
    {
      int index;    // Child node pointer index

      // Determine child node pointer index
      index = TestBit((unsigned char)c.r, O_MaxDepth - level) << 2 |
          TestBit((unsigned char)c.g, O_MaxDepth - level) << 1 |
          TestBit((unsigned char)c.b, O_MaxDepth - level);

      return index;
    }

    OctNode *GetChild( int i ) { return pchild[i]; }
    OctNode *GetNext() { return pnext; }
    OctNode *GetPrev() { return pprev; }
    int GetNumChild() { return children; }

    // Add RGB color to node
    void AddColor( ImgRGBColor &c ) { sum+=c; count++; }
    void DecNumChild() { children--; }
    void IncNumChild() { children++; }
    void SetChild( int i, OctNode *pc ) { pchild[i] = pc; }
    void SetIndex( int i ) { index = i; }
    void SetLeaf( BOOL flag ) { leaf_flag = flag; }
    void SetMark( BOOL flag ) { mark_flag = flag; }
    void SetNext( OctNode *pn ) { pnext = pn; }
    void SetPrev( OctNode *pn ) { pprev = pn; }
};

class OctQuant          // Octree color quantization
{
  private:
    int leaf_level;     // Leaf level
    int num_leaf;       // Number of leaf nodes

    // Reducible node list pointers
    OctNode *prnl[O_MaxDepth +1];

  protected:
    int height;         // Bitmap height
    int width;          // Bitmap width
    int max_color;      // Maximum number of colors

    OctNode *proot;     // Octree root node pointer

	Image *image;
	BYTE  *newdata,*olddata;

    BOOL InsertNode( OctNode *, ImgRGBColor & );

    OctNode *MakeNode( int level )
    {
      BOOL leaf;    // Leaf node flag
      leaf=(level>=leaf_level)?TRUE:FALSE;
      if (leaf == TRUE) num_leaf++;
	  return new OctNode(level,leaf);
    }

    OctNode *GetReducible();

    // Quantize color
    int QuantizeColor( OctNode *pn, ImgRGBColor &c )
    {
      int c_index;      // Child node pointer index
	if ((pn->IsLeaf()==TRUE) || pn->GetLevel()==leaf_level) return pn->GetIndex();
    c_index=pn->FindChild(c);
    if(!pn->GetChild(c_index)) return pn->GetIndex();
    return QuantizeColor(pn->GetChild(c_index), c);
    }

    void DeleteNode( OctNode * );
    void DeleteTree() { DeleteNode(proot); }
    void FillPalette( OctNode *, int * );

    // Add node to reducible list
    void MakeReducible( OctNode *pn )
    {
      int level;        // Node level
      OctNode *phead;   // List head node
      
      level = pn->GetLevel();
      phead = prnl[level];
      pn->SetNext(phead);
      if (phead != NULL)
        phead->SetPrev(pn);
      prnl[level] = pn;

      pn->SetMark(TRUE);
    }
    
    void ReduceTree();

  public:
    OctQuant()
    {
      int i;    // Loop index

      width = height = 0;
      num_leaf = 0;
      max_color = O_NumColor;
      leaf_level = O_MaxDepth + 1;

      // Clear the reducible node list pointers
      for (i = 0; i < leaf_level; i++) prnl[i] = NULL;
      // Clear the color palette
      proot = NULL;
    }

    BOOL BuildTree();  
    BOOL MapColors();
    BOOL Quantize(Image *img);
  
};
	
#endif