#include "TrueBASIC.h"

void assign(int site[][65], int np[], int L);
void neighbor(int site[][65], int np[], int x, int y);
void label_min(int site[][65], int np[], int x, int y, int left, int down);
int proper(int np[], int label);

void assign(int site[][65], int np[], int L)
// 占有された格子点にクラスター番号を割り付ける
{
    int down, left, ncluster, x, y, Itmp1_;

    for(Itmp1_ = 0; Itmp1_ <= 1000; ++Itmp1_)
        np[Itmp1_] = 0;
    ncluster = 0;                           // クラスター番号
    for(y = 1; y <= L; ++y)
    {
        for(x = 1; x <= L; ++x)
        {
            if(site[x][y] < 0)              // 占有された格子点
            {
                down = y - 1;               // 正方格子
                left = x - 1;
                if(site[x][down] + site[left][y] == 0)
                {
                    ncluster = ncluster + 1; // 新しいクラスター
                    site[x][y] = ncluster;
                    np[ncluster] = ncluster; // 本来のラベル
                }
                else
                    neighbor(site, np, x, y);
            }
        }
    }
    // クラスターの配列に本来のラベルを割り付ける
    for(y = 1; y <= L; ++y)
        for(x = 1; x <= L; ++x)
            site[x][y] = proper(np, site[x][y]);
}

void neighbor(int site[][65], int np[], int x, int y)
// 隣接格子点が占有されているかどうかを調べる
{
    int down, left;

    down = y - 1;
    left = x - 1;
    if(site[x][down]*site[left][y] > 0)     // 両隣接格子点とも占有されている
        label_min(site, np, x, y, left, down);
    else if(site[x][down] > 0)              // 下の隣接格子点が占有されている
        site[x][y] = site[x][down];
    else                                    // 左の隣接格子点が占有されている
        site[x][y] = site[left][y];
}

void label_min(int site[][65], int np[], int x, int y, int left, int down)
// 両隣接格子点が占有されているので，小さい方のクラスター番号を求める
{
    int cl_down, cl_left, nmax, nmin;

    if(site[left][y] == site[x][down])
    {
        // 両隣接格子点とも同じクラスター番号を持つ
        site[x][y] = site[left][y];
    }
    else
    {
        // 小さい方のクラスター番号を求める
        cl_left = proper(np, site[left][y]);
        cl_down = proper(np, site[x][down]);
        nmax = max(cl_left, cl_down);
        nmin = min(cl_left, cl_down);
        site[x][y] = nmin;
        if(nmin != nmax)
            np[nmax] = nmin;            // 不適当なラベルでは nmax = nmin とする
    }
}

int proper(int np[], int label)
{
    int proper_;

    if(np[label] == label)
        proper_ = label;
    else
        proper_ = proper(np, np[label]);
    return proper_;
}