#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

/* Global buffer of characters */
typedef struct
{
   int x, y;  /* Character position */
   int code;  /* Character code point */
} Char;
static Char *characters = NULL;
static int character_count = 0;
static int character_capacity = 1;
static int min_y = 0;
static int max_y = 0;

static int x, y, s, i, j, c;
static FILE *infile, *outfile;

/* MergeSort all characters by position */
static void MergeSort(int p, int q)
{
   int m = (p + q) / 2;

   assert(p >= 0);
   assert(q <= character_count);
   if( m == p )
      return;
   MergeSort(p, m);
   MergeSort(m, q);
   for(i = p, j = m, y = character_count + p; y < character_count + q; y++)
   {
      assert(i <= character_count);
      assert(j <= character_count);
      assert(y < character_capacity * 2);
      x = i >= m ||
          (j < q &&
           (characters[i].y > characters[j].y ||
            (characters[i].y == characters[j].y &&
             characters[i].x > characters[j].x))) ? j++ : i++;
      characters[y].x = characters[x].x;
      characters[y].y = characters[x].y;
      characters[y].code = characters[x].code;
   }
   for(y = p, x = character_count + p; y < q; x++, y++)
   {
      assert(y >= 0);
      assert(x < character_capacity * 2);
      characters[y].x = characters[x].x;
      characters[y].y = characters[x].y;
      characters[y].code = characters[x].code;
   }
}

/* Update x with width of character */
static void UpdateCharWidth()
{
   static const int offsets[22] =
   {
      0x1100,           0x115f - 0x1100,
      0x2329 - 0x115f,  0x232a - 0x2329,
      0x2e80 - 0x232a,  0x303e - 0x2e80,
      0x3040 - 0x303e,  0xa4cf - 0x3040,
      0xac00 - 0xa4cf,  0xd7a3 - 0xac00,
      0xf900 - 0xd7a3,  0xfaff - 0xf900,
      0xfe10 - 0xfaff,  0xfe19 - 0xfe10,
      0xfe30 - 0xfe19,  0xfe6f - 0xfe30,
      0xff00 - 0xfe6f,  0xff60 - 0xff00,
      0xffe0 - 0xff60,  0xffe6 - 0xffe0,
      0x1f000 - 0xffe6, 0x3ffff - 0x1f000
   };
   int q = 0;

   /* Note that the final index is incremented after the conditional
      expression, such that it's only incremented if the condition
      passes.  This is needed to check for characters that falls in
      the final range.                                               */
   for(i = 0;
       i < 22 &&
       (j = q + offsets[i++],
        q = j + offsets[i],
        c < j || c > q);
       i++);
   x += 1 + (i < 22);
}

/* Add a single character to global buffer */
static void AddChar()
{
   /* Need to reserve twice as much memory as maximum number of
      characters, to account for mergesort.  We only double when
      the number of characters reach capacity, so the amount
      allocated is character_capacity * 2.                       */
   if( character_count + 1 >= character_capacity )
   {
      character_capacity *= 2;
      characters = (Char*)realloc(characters,
                                  character_capacity * 2 * sizeof(Char));
      if( characters == NULL )
      {
         fputs("Out of memory\n", stderr);
         exit(EXIT_FAILURE);
      }
   }
   characters[character_count].x = x;
   characters[character_count].y = y;
   characters[character_count].code = c;
   character_count++;
   if( min_y > y ) min_y = y;
   if( max_y < y ) max_y = y;

   UpdateCharWidth();
}

/* Write UTF-8 bytes */
static void WriteUTF8(int code)
{
   int buffer[4];

   c = code;
   assert(code >= 0);
   j = 0;
   if( code < 0x80 )
   {
      buffer[0] = code;
   }
   else
   {
      while( code > (0x3f >> j) )
      {
         buffer[j++] = (code & 0x3f) | 0x80;
         code >>= 6;
      }
      buffer[j] = ((0x780 >> j) & 0xf0) | code;
   }
   for(; j >= 0; j--)
   {
      assert(buffer[j] >= 0);
      assert(buffer[j] <= 0xff);
      fputc(buffer[j], outfile);
   }
}

/* Load input characters to global buffer */
static void LoadInput()
{
   int param = 0;

   /* 0 = normal, 1 = seen \e, -1 = expect 1 more UTF-8 byte */
   s = 0;

   x = y = 0;
   while( (c = fgetc(infile)) != EOF )
      s = s > 0
         ?  c - '['
            ? c < '0' || c > ';'
               ?  /* End escape sequence */
                  param = c % 4 < 2 ? -param : param,
                  c >= 'A' && c <= 'D'
                     ? c > 'B' ? (x += param) < 0 ? x = 0
                                                  : 0
                               : (y += param),
                       0
                     : 0
               :  /* Update escape parameter */
                  (param = param * 10 + c - '0',
                   s)
            :  /* Second byte of escape sequence */
               s
         :  s < 0
            ?  /* Continue UTF-8 bytes */
               (c = param = (param << 6) | (c & 0x3f),
                !++s)
                  ? /* End UTF-8 sequence */
                    AddChar(),
                    s
                  : s
            :  /* Normal input state */
               (c & 0xe0) - 0xc0
                  ? (c & 0xf0) - 0xe0
                     ? (c & 0xf8) - 0xf0 
                        ? c - '\x1b'
                           ? c - '\n'
                              ? c - ' '
                                 ? c - '\t'
                                    ? c > 32
                                        ? AddChar(), s
                                        : s
                                    : (x += 8,
                                       x -= x % 8)
                                 : x++
                              : (y++, x = 0),
                             s
                           : /* Start of escape sequence */
                             (param = 0,
                              1)
                        : (param = c & 0x07,
                           -3)
                     : (param = c & 0x0f,
                        -2)
                  : (param = c & 0x1f,
                     -1);
}

/* Output characters in sorted order */
static void OutputSorted()
{
   /* Write one sentinel character to mark the end.  This for seeking
      one character ahead when checking duplicates.  We don't have to
      worry about out of bounds writes since the buffer is always at
      least twice as large as number of characters.                   */
   characters[character_count].x = -1;
   for(s = x = 0, y = min_y; s < character_count; s++)
   {
      while( y < characters[s].y )
      {
         WriteUTF8('\n');
         y++;
         x = 0;
      }
      while( x < characters[s].x )
      {
         WriteUTF8(' ');
         x++;
      }

      /* Seek ahead in case if there are overlaps.  We want to take
         the last character that is drawn at this position to simulate
         overlaps.                                                     */
      while( characters[s + 1].y == characters[s].y &&
             characters[s + 1].x == characters[s].x )
      {
         s++;
      }
      WriteUTF8(characters[s].code);
      UpdateCharWidth();
   }

   /* Always end with newline */
   if( x > 0 )
      WriteUTF8('\n');
}

/* Write a single escape sequence */
static void WriteEscape(int offset, int code)
{
   if( offset )
      fprintf(outfile, "\x1b[%d%c", abs(offset), code + (offset > 0));
}

/* Output characters in shuffled order */
static void OutputShuffled(int argc, char **argv)
{
   int index;

   if( !(argc -= 2) )
   {
      argc = 1;
   }
   else
   {
      if( (outfile = fopen(argv[2], "wb")) == NULL )
      {
         printf("Can not open %s for writing\n", argv[2]);
         return;
      }
   }

   for(index = s = x = 0, y = max_y + 1;
       s < character_count && index < argc;
       index++)
   {
      if( index == 0 )
      {
         /* Preallocate vertical space for first layer */
         for(s = 0; s < max_y - min_y + 1; s++)
            WriteUTF8('\n');
         s = 0;
      }
      else
      {
         /* Open output file for new layer */
         if( (outfile = fopen(argv[index + 2], "wb")) == NULL )
         {
            printf("Can not open %s for writing\b", argv[index + 2]);
            return;
         }
      }

      for(; s < character_count * (index + 1) / argc; s++)
      {
         WriteEscape(characters[s].y - y, 'A');
         WriteEscape(x - characters[s].x, 'C');
         WriteUTF8(characters[s].code);
         x = characters[s].x;
         UpdateCharWidth();
         y = characters[s].y;
      }

      /* Move cursor to last line at the end of each layer */
      WriteEscape(max_y - y, 'A');
      WriteUTF8('\n');
      fclose(outfile);
      x = 0;
      y = max_y + 1;
   }
}

int main(int argc, char **argv)
{
   infile = stdin;
   outfile = stdout;
   if( argc > 1 && (argv[1][0] != '-' || argv[1][1] != '\0') )
   {
      if( (infile = fopen(argv[1], "rb")) == NULL )
         return printf("Can not open %s for reading\n", argv[1]);
   }
   LoadInput();
   if( characters == NULL )
      return 0;

   if( argc == 1 )
   {
      /* Assemble stdin to stdout */
      MergeSort(0, character_count);
      OutputSorted();
   }
   else
   {
      /* Shuffle input */
      srand(time(NULL));
      for(j = character_count; --j > 0;)
      {
         i = rand() % (j + 1);
         s = characters[i].x;
         characters[i].x = characters[j].x;
         characters[j].x = s;
         s = characters[i].y;
         characters[i].y = characters[j].y;
         characters[j].y = s;
         s = characters[i].code;
         characters[i].code = characters[j].code;
         characters[j].code = s;
      }

      OutputShuffled(argc, argv);
   }
   return 0;
}