Untitled

/*
 
 
* @file: [E][H2350] [Pro] Image editor
 
 
* @brief: Sample Answer
 
 
* @copyright: All rights reserved (c) 2023 Samsung Electronics, Inc.
 
 
*/
 
 
const int MAX_COLOR = 128;
const int IMAGE_SIZE = 1000;
 
 
unsigned char Image[2][IMAGE_SIZE * IMAGE_SIZE];
 
 
int Cur, Next;
int Width, Height;
 
 
void copyImage(unsigned char* pDest, unsigned char* pSrc, int size)
{
    while (size--) *(pDest++) = *(pSrc++);
}
 
 
void init(int mWidth, int mHeight, unsigned char mInImage[]) 
{
    Cur = 0;
    Width = mWidth;
    Height = mHeight;
    copyImage(Image[Cur], mInImage, Width * Height);
}
 
 
void rect(int mX, int mY, int mW, int mH, unsigned char mColor, unsigned char mOutImage[])
{
    Next = Cur ^ 1;
    copyImage(Image[Next], Image[Cur], Width * Height);
    unsigned char* pLineStart = Image[Next] + mX + mY * Width;
    unsigned char* p;
    for (int j = 0; j < mH; j++){
        p = pLineStart;
        for (int i = 0; i < mW; i++) {
            *p = mColor;
            p++;
        }
        pLineStart += Width;
    }
    Cur = Next;
    copyImage(mOutImage, Image[Cur], Width * Height);
}
 
 
void rotate(unsigned char mOutImage[]) 
{
    Next = Cur ^ 1;
    unsigned char* pSrc = Image[Cur];
    unsigned char* pDestLineStart = Image[Next] + Height - 1;
    int next = Height;
    int lineJump = -1;
    unsigned char* pDest = Image[Next] + Width - 1;
    for (int j = 0; j < Height; j++) {
        pDest = pDestLineStart;
        for (int i = 0; i < Width; i++) {
            *pDest = *(pSrc++);
            pDest += next;            
        }
        pDestLineStart += lineJump;
    }
    Width ^= Height ^= Width ^= Height;
    Cur = Next;
    copyImage(mOutImage, Image[Cur], Width * Height);    
}
 
 
unsigned int Queue[IMAGE_SIZE * IMAGE_SIZE * 4];
int xx[] = { 1, 0, -1, 0 };
int yy[] = { 0, 1, 0, -1 };
 
 
void paintBucket(int mX, int mY, unsigned char mColor, unsigned char mOutImage[]) 
{
    Next = Cur ^ 1;
    copyImage(Image[Next], Image[Cur], Width * Height);    
    unsigned char* pCur = Image[Next] + mX + mY * Width;
    unsigned char preColor = *pCur;
    int qCount = 0;
    Queue[qCount++] = (mY << 10 | mX); 
    *pCur = mColor;
    for (int i = 0; i < qCount; i++) {
        int y = Queue[i] >> 10;
        int x = Queue[i] & 1023;
        for (int d = 0; d < 4; d++) {
            int ny = y + yy[d];
            int nx = x + xx[d];
            pCur = Image[Next] + nx + ny * Width;
            if (0 <= ny && ny < Height && 0 <= nx && nx < Width && *pCur == preColor) {
                *pCur = mColor;
                Queue[qCount++] = (ny << 10 | nx);
            }
        }
    }
    Cur = Next;
    copyImage(mOutImage, Image[Cur], Width * Height);
}
 
 
int huff(unsigned char* pImage, unsigned char* mOutImage);
 
 
int save(unsigned char mOutHuffData[]) {
    int bits = huff(Image[Cur], mOutHuffData);
    return bits;
}
 
 
 
 
#include <queue>
using namespace std;
 
 
struct SNode
{
    int count;
    int left;
    int right;
    int key;
    int isLeaf;
    int bit;
    unsigned int code;
};
 
 
SNode Node[MAX_COLOR * 2] = {};
 
 
struct cmp {
    bool operator()(int a, int b) {
        if (Node[a].count == Node[b].count) {
            return Node[a].key > Node[b].key;
        }
        return Node[a].count > Node[b].count;
    }
};
 
 
priority_queue<int, vector<int>, cmp> PQ;
 
 
void Go(int depth, int cur, int code) {
 
 
    if (Node[cur].isLeaf) {
        Node[Node[cur].key].bit = depth;
        Node[Node[cur].key].code = code;
        return;
    }
    Go(depth + 1, Node[cur].left, code << 1);
    Go(depth + 1, Node[cur].right, (code << 1) + 1);
}
 
 
int huff(unsigned char* pImage , unsigned char* mOutImage)
{
    int Index = 0;
    int Count[MAX_COLOR];
 
 
    for (int i = 0; i < MAX_COLOR; i++) {
        Count[i] = 0;
    }
    int size = Width * Height;
    unsigned char* p = pImage;
    while(size--) Count[*(p++)]++;    
 
 
    PQ = {};
    Index = 0;
 
 
    for (int i = 0; i < MAX_COLOR; i++) {
        Node[i].count = Count[i];
        Node[i].key = i;
        Node[i].isLeaf = 1;
        if (Count[i] > 0) PQ.push(i);
    }
    Index = MAX_COLOR;
 
 
    int a, b;
    while (PQ.size() > 1) {
        a = PQ.top(); PQ.pop();
        b = PQ.top(); PQ.pop();
        Node[Index].count = Node[a].count + Node[b].count;
        Node[Index].key = Node[a].key < Node[b].key ? Node[a].key : Node[b].key;
        Node[Index].left = a;
        Node[Index].right = b;
        Node[Index].isLeaf = 0;
        PQ.push(Index);
        Index++;
    }
 
 
    Go(0, Index - 1, 0);
 
 
    for (int i = 0; i < MAX_COLOR; i++) {
        Node[i].code <<= 32 - Node[i].bit;
    }
             
    int c;
    unsigned int code;
    int part = 0;
    int total = 0;
 
 
    unsigned char* pOut = mOutImage;
    unsigned char* pIn = Image[Cur];
 
 
    size = Width * Height;    
    while (size--) *(pOut++) = 0;
 
 
    size = Width * Height;
    pOut = mOutImage;
 
 
    while (size--) {
        c = *(pIn++);
        code = Node[c].code >> part;
        pOut[0] += (code >> 24) & 0xff;
        pOut[1] += (code >> 16) & 0xff;
        pOut[2] += (code >> 8) & 0xff;
         
        part += Node[c].bit;
        pOut += part >> 3;
        part &= 0x07;
        total += Node[c].bit;
    }
    return total;
}