//C-  -*- C++ -*-

//C- -------------------------------------------------------------------

//C- DjVuLibre-3.5

//C- Copyright (c) 2002  Leon Bottou and Yann Le Cun.

//C- Copyright (c) 2001  AT&T

//C-

//C- This software is subject to, and may be distributed under, the

//C- GNU General Public License, either Version 2 of the license,

//C- or (at your option) any later version. The license should have

//C- accompanied the software or you may obtain a copy of the license

//C- from the Free Software Foundation at http://www.fsf.org .

//C-

//C- This program is distributed in the hope that it will be useful,

//C- but WITHOUT ANY WARRANTY; without even the implied warranty of

//C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

//C- GNU General Public License for more details.

//C- 

//C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library from

//C- Lizardtech Software.  Lizardtech Software has authorized us to

//C- replace the original DjVu(r) Reference Library notice by the following

//C- text (see doc/lizard2002.djvu and doc/lizardtech2007.djvu):

//C-

//C-  ------------------------------------------------------------------

//C- | DjVu (r) Reference Library (v. 3.5)

//C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.

//C- | The DjVu Reference Library is protected by U.S. Pat. No.

//C- | 6,058,214 and patents pending.

//C- |

//C- | This software is subject to, and may be distributed under, the

//C- | GNU General Public License, either Version 2 of the license,

//C- | or (at your option) any later version. The license should have

//C- | accompanied the software or you may obtain a copy of the license

//C- | from the Free Software Foundation at http://www.fsf.org .

//C- |

//C- | The computer code originally released by LizardTech under this

//C- | license and unmodified by other parties is deemed "the LIZARDTECH

//C- | ORIGINAL CODE."  Subject to any third party intellectual property

//C- | claims, LizardTech grants recipient a worldwide, royalty-free, 

//C- | non-exclusive license to make, use, sell, or otherwise dispose of 

//C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the 

//C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU 

//C- | General Public License.   This grant only confers the right to 

//C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to 

//C- | the extent such infringement is reasonably necessary to enable 

//C- | recipient to make, have made, practice, sell, or otherwise dispose 

//C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to 

//C- | any greater extent that may be necessary to utilize further 

//C- | modifications or combinations.

//C- |

//C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY

//C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED

//C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF

//C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

//C- +------------------------------------------------------------------

#ifdef HAVE_CONFIG_H

# include "config.h"

#endif

#if NEED_GNUG_PRAGMAS

# pragma implementation

#endif

/** @name csepdjvu

    {\bf Synopsis}

    \begin{verbatim}

        csepdjvu <....options-or-separated_files...> <outputdjvufile>

    \end{verbatim}

    {\bf Description}

    File #"csepdjvu.cpp"# demonstrates a complete back-end encoder that takes

    {\em separated files} as input and produces a djvu file as output.

    Each {\em separated file} contains a concatenation of pages. 

    Each page contains the following components:

    \begin{itemize}

    \item A run-length encoded file representing the foreground.

          Two kind of run-length encoded files are accepted.

          The Black-And-White RLE format is described in section

          \Ref{PNM and RLE file formats}.  The Color RLE format

          is described below.

    \item An optional PPM image representing the background.

          The size (width and height) of the PPM image must be obtained by

          rounding up the quotient of the foreground image size by

          an integer reduction factor ranging from 1 to 12.

    \item An arbitrary number of comment lines starting with 

          character '#'.

    \end{itemize}

    All the provided pages will be converted to Compound DjVu Images.

    Foreground colors will be encoded using a single solid color per component

    (see \Ref{DjVu Image files}).  Multiple pages will be gathered into a

    single bundled file.  Use \Ref{djvmcvt} or \Ref{djvujoin} to create an

    indirect file.

    {\bf Options}

    \begin{description}

    \item[-d n] Resolution written into the output file (default: 300).

    \item[-q <spec>] Quality level for background (default: 72+11+10+10).

                     See option #"-slice"# in program \Ref{c44} for details.

    \item[-v] Displays a brief message per page.

    \item[-vv] Displays lots of additional messages.

    \end{description}

    {\bf Color RLE Images}

    The Color RLE file format is a simple run-length encoding scheme for color

    images with a limited number of colors. Color RLE files always begin with

    a text header composed of:

    - the two characters #"R6"#,

    - the number of columns in decimal,\\

    - the number of rows in decimal,\\

    - the number of palette entries in decimal.\\

    These four items are separated by blank characters (space, tab, cr, or nl)

    or by comment lines introduced by character ``\#''.  The last number is

    followed by exactly one character (usually a nl character).  This header

    is followed by a palette containing three bytes per color.  The bytes

    represent the red, green, and blue components of the color.  

    The palette is followed by four bytes integers (MSB first) representing

    runs.  The twelve upper bits of this integer indicate the index of the run

    color in the palette entry.  The twenty lower bits of the integer indicate

    the run length.  Color indices greater than 0xff0 are reserved for pixels

    belonging to the background layer.  Color index 0xfff is used for

    transparent runs. Color index 0xffe is used for don't-care runs

    (i.e. pixels whose values should be taken by smoothly completing the

    background using the wavelet masking algorithm).  Each row is represented

    by a sequence of runs whose lengths add up to the image width.  Rows are

    encoded starting with the top row and progressing towards the bottom row.

    @memo

    Creates DjVu files from Separated files.

    @author

    L\'eon Bottou <leonb@research.att.com>

*/

//@{

//@}

#include "DjVuGlobal.h"

#include "GException.h"

#include "GSmartPointer.h"

#include "GContainer.h"

#include "ByteStream.h"

#include "IFFByteStream.h"

#include "GRect.h"

#include "GBitmap.h"

#include "JB2Image.h"

#include "DjVuPalette.h"

#include "IW44Image.h"

#include "DjVuInfo.h"

#include "DjVmDoc.h"

#include "DjVmNav.h"

#include "GOS.h"

#include "GURL.h"

#include "DjVuMessage.h"

#include "DjVuText.h"

#include "BSByteStream.h"

#include "miniexp.h"

#include "jb2tune.h"

#include "common.h"

#undef MIN

#undef MAX

inline int MIN(int a, int b) { return ( a

inline int MAX(int a, int b) { return ( a>b ?a :b); }

// --------------------------------------------------

// OPTIONS

// --------------------------------------------------

struct csepdjvuopts

{

  int dpi;                  // resolution

  int verbose;              // verbosity level

  DjVuTXT::ZoneType text;   // level of text detail

  unsigned char slice[16];  // background quality spec

  csepdjvuopts();

};

csepdjvuopts::csepdjvuopts()

{

      dpi = 300;

      verbose = 0;

      text = DjVuTXT::WORD;

      slice[0] =  72;

      slice[1] =  83;      

      slice[2] =  93;

      slice[3] = 103;

      slice[4] =   0;

}

// --------------------------------------------------

// BUFFERED BYTESTREAM

// --------------------------------------------------

// -- A bytestream that performs buffering and 

//    offers a stdio-like interface for parsing files.

class BufferByteStream : public ByteStream 

{

public:

  enum {bufsize=512};

private:

  ByteStream &bs;

  unsigned char buffer[bufsize];

  int bufpos;

  int bufend;

public:

  BufferByteStream(ByteStream &lbs;;

  size_t read(void *buffer, size_t size);

  size_t write(const void *buffer, size_t size);

  virtual long tell(void) const;

  int eof(void);

  int unget(int c);

  inline int get(void);

  // parsing helpers

  bool skip(const char *s = " \t\n\r");

  bool expect(int &c, const char *s); 

  bool read_integer(int &x);

  bool read_pair(int &x, int &y);

  bool read_geometry(GRect &r);

  bool read_ps_string(GUTF8String &s);

};

BufferByteStream::BufferByteStream(ByteStream &bs)

  : bs(bs), bufpos(1), bufend(1)

{ 

}

int 

BufferByteStream::eof(void) // aka. feof

{

  if (bufpos < bufend) 

    return false;

  bufend = bufpos = 1;

  bufend += bs.read(buffer+bufend, bufsize-bufend);

  return (bufend == bufpos);

}

size_t 

BufferByteStream::read(void *buf, size_t size)

{

  if (size < 1)

    return 0;

  if (bufend == bufpos) 

    {

      if (size >= bufsize)

        return bs.read(buf, size);

      if (eof())

        return 0;

    }

  if (bufpos + (int)size > bufend)

    size = bufend - bufpos;

  memcpy(buf, buffer+bufpos, size);

  bufpos += size;

  return size;

}

size_t 

BufferByteStream::write(const void *, size_t )

{

  G_THROW("Cannot write into a BufferByteStream");

  return 0;

}

long 

BufferByteStream::tell(void) const

{ 

  return bs.tell() + bufpos - bufend; 

}

inline int 

BufferByteStream::get(void) // aka. getc()

{

  if (bufpos < bufend || !eof())

    return buffer[bufpos++];

  return EOF;

}

int  

BufferByteStream::unget(int c) // aka. ungetc()

{

  if (bufpos > 0 && c != EOF) 

    return buffer[--bufpos] = (unsigned char)c;

  return EOF;

}

bool 

BufferByteStream::expect(int &c, const char *s)

{

  c = get();

  if (strchr(s, c))

    return true;

  unget(c);

  return false;

}

bool

BufferByteStream::skip(const char *s)

{

  int c;

  while (expect(c, s)) { }

  return true;

}

bool 

BufferByteStream::read_integer(int &x)

{

  x = 0;

  int c = get();

  if (c<'0' || c>'9')

    return false;

  while (c>='0' && c<='9') 

    {

      x = x*10 + c - '0';

      c = get();

    }

  unget(c);

  return true;

}

bool 

BufferByteStream::read_pair(int &x, int &y)

{

  int c;

  x = y = 0;

  expect(c, "-");

  if (! read_integer(x)) 

    return false;

  if (c == '-') 

    x = -x;

  if (! expect(c, ":"))

    return false;

  expect(c, "-");

  if (! read_integer(y)) 

    return false;

  if (c == '-')

    y = -y;

  return true;

}

bool 

BufferByteStream::read_geometry(GRect &r)

{

  int x,y,w,h,c;

  x = y = w = h = 0;

  if (read_integer(w) && expect(c, "x") && read_integer(h))

    {

      if (expect(c,"+-"))

        {

          if (c == '+')

            expect(c,"-");

          if (! read_integer(x))

            return false;

          if (c == '-')

            x = -x;

        }

      if (expect(c,"+-"))

        {

          if (c == '+')

            expect(c,"-");

          if (! read_integer(y))

            return false;

          if (c == '-')

            y = -y;

        }

      r = GRect(x,y,w,h);

      return true;

    }

  return false;

}

static void

add_to_string(GUTF8String &s, char *buffer, int len, int &bom)

{

  if (!s && !bom && len>=2)

    {

      if (buffer[0]==(char)0xfe && buffer[1]==(char)0xff)

        bom = 0xfeff;

      if (buffer[0]==(char)0xff && buffer[1]==(char)0xfe)

        bom = 0xfffe;

      if (bom)

        {

          buffer += 2; 

          len -= 2;

        }

    }

  if (bom == 0xfeff)

    for (int i=0; i

      *(uint16_t*)(buffer+i) = ((buffer[i]<<8) | buffer[i+1]);

  if (bom == 0xfffe)

    for (int i=0; i

      *(uint16_t*)(buffer+i) = ((buffer[i+1]<<8) | buffer[i]);

  if (bom)

    s += GUTF8String((const uint16_t*)buffer, len/2);

  else

    s += GUTF8String((const char*)buffer, len);

}

bool 

BufferByteStream::read_ps_string(GUTF8String &s)

{

  int bom = 0;

  unsigned int pos = 0;

  char buffer[512];

  if (get() != '(') 

    return false;

  s = "";

  for(;;)

    {

      int c = get();

      if (c == '\n' || c == '\r')

        return false;

      if (c == ')')

        break;

      if (c == '\\')

        {

          c = get();

          switch (c) 

            {

            case 'n': 

              c='\n' ; break;

            case 'r': 

              c='\r' ; break;

            case 't': 

              c='\t' ; break;

            case 'b': 

              c='\b' ; break;

            case 'f': 

              c='\f' ; break;

            default:

              if (c>='0' && c<='7') 

                {

                  int n = 0;

                  int x = 0;

                  while (c>='0' && c<='7' && n<3)

                    {

                      x = (x * 8) + c - '0';

                      c = get();

                      n++;

                    }

                  unget(c);

                  c = x;

                }

              break;

            }

        }

      if (c == EOF)

        return false;

      if (pos >= (int)sizeof(buffer))

        {

          add_to_string(s, buffer, pos, bom);

          pos = 0;

        }

      buffer[pos++] = c;

    }

  add_to_string(s, buffer, pos, bom);

  return true;

}

// --------------------------------------------------

// COLOR CONNECTED COMPONENT ANALYSIS

// --------------------------------------------------

// -- A run of pixels with the same color

struct Run    

{ 

  short y;       // vertical coordinate

  short x1;      // first horizontal coordinate

  short x2;      // last horizontal coordinate

  short color;   // color id

  int ccid;      // component id

};

// -- Compares runs for y-x sorting

static inline bool

operator <= (const Run &a, const Run &b)

{

  return (a.y

}

// -- Color component descriptor

struct CC    

{

  GRect bb;      // bounding box

  int npix;      // number of black pixels

  int nrun;      // number of runs

  int frun;      // first run in cc ordered array of runs

  int color;     // color id

};

// -- An image composed of runs

class CRLEImage 

{

public:

  int height;            // Height of the image in pixels

  int width;             // Width of the image in pixels

  GP<DjVuPalette> pal;   // Color palette

  GTArray<Run>    runs;  // Array of runs

  GTArray<CC>     ccs;   // Array of component descriptors

  int  nregularccs;      // Number of regular ccs (set by merge_and_split_ccs)

  char bg_flags;         // Comment flags about background.

  char fg_flags;         // Comment flags about foreground.

  CRLEImage(BufferByteStream &bs);

  GP<GBitmap> get_bitmap_for_cc(int ccid) const;

  void make_ccids_by_analysis();

  void make_ccs_from_ccids();

  void merge_and_split_ccs(int smallsize, int largesize);

  void sort_in_reading_order(); 

private:

  unsigned int read_integer(BufferByteStream &bs);

  void insert_runs(int y, const short *x1x2color, int nruns);

};

// -- Helper for CRLEImage::CRLEImage(ByteStream &bs)

unsigned int 

CRLEImage::read_integer(BufferByteStream &bs)

{

  int c, x;

  while (bs.skip() && bs.expect(c, "#"))

    {

      char buffer[256];

      char *s = buffer;

      while (c != EOF && c != '\n' && c != '\r')

        {

          if (s - buffer < (int)sizeof(buffer) - 1)

            *s++ = c;

          c = bs.get();

        }

      *s = 0;

      for(s = buffer; *s; s++)

        {

          if (!strncmp(s, "bg-", 3))

            {

              if (!strncmp(s+3,"bw",2)   ||

                  !strncmp(s+3,"gray",4) ||

                  !strncmp(s+3,"color",5)  )

                bg_flags = s[3];

            }

          if (!strncmp(s, "fg-", 3))

            {

              if (!strncmp(s+3,"bw",2)   ||

                  !strncmp(s+3,"gray",4) ||

                  !strncmp(s+3,"color",5)  )

                fg_flags = s[3];

            }

        }

    }

  if (! bs.read_integer(x) )

    G_THROW("csepdjvu: corrupted input file (bad file header)");

  return x;

}

// -- Helper for CRLEImage::CRLEImage(ByteStream &bs)

void

CRLEImage::insert_runs(int y, const short *x1x2color, int count)

{

  if (count > 0)

    {

      int index = runs.lbound() - count;

      runs.resize(index, runs.hbound());

      Run *run = &runs[index];

      while (--count>=0) {

        run->y     = y;

        run->x1    = *x1x2color++;

        run->x2    = *x1x2color++;

        run->color = *x1x2color++;

        run->ccid  = 0;

        run++;

      }

      runs.shift(-index);

    }

}

// -- Constructs CRLEImage from a run lenght encoded file,

//    making sure that runs are properly sorted.

CRLEImage::CRLEImage(BufferByteStream &bs)

  : height(0), width(0), nregularccs(0), bg_flags(0), fg_flags(0)

{

  unsigned int magic = bs.read16();

  width = read_integer(bs);

  height = read_integer(bs);

  if (width<1 || height<1)

    G_THROW("csepdjvu: corrupted input file (bad image size)");

  // An array for the runs and the buffered data

  GTArray<short> ax(3*width+3);

  // File format switch

  if (magic == 0x5234) // Black&White RLE data

    {

      // Skip one character

      bs.get(); 

      // Setup palette with one color

      pal = DjVuPalette::create();

      static char zeroes[4];

      GP<ByteStream> gzbs=ByteStream::create_static(zeroes,4);

      ByteStream &zbs=*gzbs;

      pal->decode_rgb_entries(zbs, 1);

      // RLE format

      int x, c, n;

      unsigned char p = 0;

      short *px = ax;

      n = height - 1;

      c = 0;

      while (n >= 0)

        {

          if (bs.eof())

            G_THROW( ByteStream::EndOfFile );

          x = bs.get();

          if (x >= 0xc0)

            x = (bs.get()) + ((x - 0xc0) << 8);

          if (c+x > width)

            G_THROW("csepdjvu: corrupted input file (lost RLE sync.)");

          if (p)

            {

              px[0] = c;

              px[1] = c+x-1;

              px[2] = 0;

              px += 3;

            }

          c += x;

          p = 1 - p;

          if (c >= width)

            {

              insert_runs(n, ax, (px-ax)/3);

              c = 0;

              p = 0;

              n -= 1; 

              px = ax;

            }

        }

    } else if (magic == 0x5236) { // Color-RLE data 

      // Read ncolors and skip one character.

      int ncolors = read_integer(bs);

      bs.get();

      // Setup palette 

      if (ncolors<1 || ncolors>4095) 

        G_THROW("csepdjvu: corrupted input file (bad number of colors)");

      pal = DjVuPalette::create();

      pal->decode_rgb_entries(bs, ncolors);

      // RLE format

      int x, c, n, p;

      n = height - 1;

      c = 0;

      short *px = ax;

      while (n >= 0)

        {

          if (bs.eof())

            G_THROW( ByteStream::EndOfFile );

          x  = (bs.get() << 24);

          x  |= (bs.get() << 16);

          x  |= (bs.get() << 8);

          x  |= (bs.get());

          p = (x >> 20) & 0xfff;

          x = (x & 0xfffff);

          if (c+x > width)

            G_THROW("csepdjvu: corrupted input file (lost RLE sync.)");

          if (p >= 0 && p < ncolors)

            {

              px[0] = c;

              px[1] = c+x-1;

              px[2] = p;

              px += 3;

            }

          c += x;

          if (c >= width)

            {

              insert_runs(n, ax, (px-ax)/3);

              c = 0;

              p = 0;

              n -= 1; 

              px = ax;

            }

        }

    } else { // Unrecognized file

      G_THROW("csepdjvu: corrupted input file (bad file header)");

    }

}

// -- Performs color connected component analysis

//    assuming that runs are already y-x sorted.

void

CRLEImage::make_ccids_by_analysis()

{

  // runs.sort(); (we know that runs are 

  // Single Pass Connected Component Analysis (with unodes)

  int n;

  int p=0;

  GTArray<int> umap;

  for (n=0; n<=runs.hbound(); n++)

    {

      int y = runs[n].y;

      int x1 = runs[n].x1 - 1;

      int x2 = runs[n].x2 + 1;

      int color = runs[n].color;

      int id = (umap.hbound() + 1);

      // iterate over previous line runs

      if (p>0) p--;

      for(;runs[p].y < y-1;p++);

      for(;(runs[p].y < y) && (runs[p].x1 <= x2);p++ )

        {

          if ( runs[p].x2 >= x1 )

            {

              if (runs[p].color == color)

                {

                  // previous run touches current run and has same color

                  int oid = runs[p].ccid;

                  while (umap[oid] < oid)

                    oid = umap[oid];

                  if ((int)id > umap.hbound()) {

                    id = oid;

                  } else if (id < oid) {

                    umap[oid] = id;

                  } else {

                    umap[id] = oid;

                    id = oid;

                  }

                  // freshen previous run id

                  runs[p].ccid = id;

                }

              // stop if previous run goes past current run

              if (runs[p].x2 >= x2)

                break;

            }

        }

      // create new entry in umap

      runs[n].ccid = id;

      if (id > umap.hbound())

        {

          umap.touch(id);

          umap[id] = id;

        }

    }

  // Update umap and ccid

  for (n=0; n<=runs.hbound(); n++)

    {

      Run &run = runs[n];

      int ccid = run.ccid;

      while (umap[ccid] < ccid)

        ccid = umap[ccid];

      umap[run.ccid] = ccid;

      run.ccid = ccid;

    }

}

// -- Constructs the ``ccs'' array from run's ccids.

void

CRLEImage::make_ccs_from_ccids()

{

  int n;

  Run *pruns = runs;

  // Find maximal ccid

  int maxccid = -1;

  for (n=0; n<=runs.hbound(); n++)

    if (pruns[n].ccid > maxccid)

      maxccid = runs[n].ccid;

  GTArray<int> armap(0,maxccid);

  int *rmap = armap;

  // Renumber ccs 

  for (n=0; n<=maxccid; n++)

    armap[n] = -1;

  for (n=0; n<=runs.hbound(); n++)

    if (pruns[n].ccid >= 0)

      rmap[ pruns[n].ccid ] = 1;

  int nid = 0;

  for (n=0; n<=maxccid; n++)

    if (rmap[n] > 0)

      rmap[n] = nid++;

  // Adjust nregularccs (since ccs are renumbered)

  while (nregularccs>0 && rmap[nregularccs-1]<0)

    nregularccs -= 1;

  if (nregularccs>0)

    nregularccs = 1 + rmap[nregularccs-1];

  // Prepare cc descriptors

  ccs.resize(0,nid-1);

  for (n=0; n

    ccs[n].nrun = 0;

  // Relabel runs

  for (n=0; n<=runs.hbound(); n++)

    {

      Run &run = pruns[n];

      if (run.ccid < 0) continue;  // runs with negative ccids are destroyed

      int oldccid = run.ccid;

      int newccid = rmap[oldccid];

      CC &cc = ccs[newccid];

      run.ccid = newccid;

      cc.nrun += 1;

    }

  // Compute positions for runs of cc

  int frun = 0;

  for (n=0; n

    {

      ccs[n].frun = rmap[n] = frun;

      frun += ccs[n].nrun;

    }

  // Copy runs

  GTArray<Run> rtmp;

  rtmp.steal(runs);

  Run *ptmp = rtmp;

  runs.resize(0,frun-1);

  pruns = runs;

  for (n=0; n<=rtmp.hbound(); n++)

    {

      int id = ptmp[n].ccid;

      if (id < 0) continue;

      int pos = rmap[id]++;

      pruns[pos] = ptmp[n];

    }

  // Finalize ccs

  for (n=0; n

    {

      CC &cc = ccs[n];

      int npix = 0;

      runs.sort(cc.frun, cc.frun+cc.nrun-1);

      Run *run = &runs[cc.frun];

      int xmin = run->x1;

      int xmax = run->x2;

      int ymin = run->y;

      int ymax = run->y;

      cc.color = run->color;

      for (int i=0; i

        {

          if (run->x1 < xmin)  xmin = run->x1;

          if (run->x2 > xmax)  xmax = run->x2;

          if (run->y  < ymin)  ymin = run->y;

          if (run->y  > ymax)  ymax = run->y;

          npix += run->x2 - run->x1 + 1;

        }

      cc.npix = npix;

      cc.bb.xmin = xmin;

      cc.bb.ymin = ymin;

      cc.bb.xmax = xmax + 1;

      cc.bb.ymax = ymax + 1;

    }

}

// -- Helper for merge_and_split_ccs

struct Grid_x_Color 

{

  short gridi;

  short gridj;

  int color;

};

// -- Helper for merge_and_split_ccs

static inline unsigned int

hash(const Grid_x_Color &x) 

{

  return (x.gridi<<16) ^ (x.gridj<<8) ^ x.color;

}

// -- Helper for merge_and_split_ccs

static inline bool

operator==(const Grid_x_Color &x, const Grid_x_Color &y)

{

  return (x.gridi==y.gridi) && (x.gridj==y.gridj) && (x.color==y.color);

}

// -- Helper for merge_and_split_ccs

static int

makeccid(const Grid_x_Color &x, GMap<Grid_x_Color,int> &map, int &ncc)