#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;

/* MergeSort all characters by position */
static void MergeSort(int x, int y)
{
   int m = (x + y) / 2;
   int i, j, r, w;

   if( m == x )
      return;
   MergeSort(x, m);
   MergeSort(m, y);
   for(i = x, j = m, w = character_count + x; w < character_count + y; w++)
   {
      r = i >= m ||
          (j < y &&
           (characters[i].y > characters[j].y ||
            (characters[i].y == characters[j].y &&
             characters[i].x > characters[j].x))) ? j++ : i++;
      characters[w].x = characters[r].x;
      characters[w].y = characters[r].y;
      characters[w].code = characters[r].code;
   }
   for(w = x, r = character_count + x; w < y; r++, w++)
   {
      characters[w].x = characters[r].x;
      characters[w].y = characters[r].y;
      characters[w].code = characters[r].code;
   }
}

/* Add a single character to global buffer */
static void AddChar(int x, int y, int code)
{
   /* Since we always double the amount of memory allocated when the
      next character reaches capacity, we always have at least twice
      as much memory as number of characters loaded.  This means we
      already have the spare space needed for MergeSort.             */
   if( character_count + 1 >= character_capacity )
   {
      character_capacity *= 2;
      characters = (Char*)realloc(characters,
                                  character_capacity * 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 = code;
   character_count++;
   if( min_y > y ) min_y = y;
   if( max_y < y ) max_y = y;
}

/* Write UTF-8 bytes */
static void WriteUTF8(int code, FILE *outfile)
{
   int buffer[4], index = 0;

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

/* Get width of character, returns 1 for half width and 2 for full width */
static int GetCharWidth(int c)
{
   static const int ranges[11][2] =
   {
      {0x1100, 0x115f},
      {0x2329, 0x232a},
      {0x2e80, 0x303e},
      {0x3040, 0xa4cf},
      {0xac00, 0xd7a3},
      {0xf900, 0xfaff},
      {0xfe10, 0xfe19},
      {0xfe30, 0xfe6f},
      {0xff00, 0xff60},
      {0xffe0, 0xffe6},
      {0x1f000, 0x3fffd}
   };
   int i;

   for(i = 0; i < 11; i++)
   {
      if( c >= ranges[i][0] && c <= ranges[i][1] )
         return 2;
   }
   return 1;
}

/* Load input characters to global buffer */
static void LoadInput(FILE *infile)
{
   int c, x = 0, y = 0, param = 0;

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

   while( (c = fgetc(infile)) != EOF )
   {
      if( state > 0 )
      {
         if( c == '[' )
         {
            /* Second byte of escape sequence */
         }
         else
         {
            if( 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;
               state = 0;
            }
            else
            {
               /* Update escape parameter */
               param = param * 10 + c - '0';
            }
         }
      }
      else if( state < 0 )
      {
         /* Continue UTF-8 bytes */
         param = (param << 6) | (c & 0x3f);
         if( ++state == 0 )
         {
            /* End UTF-8 sequence */
            AddChar(x, y, param);
            x += GetCharWidth(param);
         }
      }
      else
      {
         /* Normal input state */
         if( (c & 0xe0) == 0xc0 )
         {
            state = -1;
            param = c & 0x1f;
         }
         else if( (c & 0xf0) == 0xe0 )
         {
            state = -2;
            param = c & 0x0f;
         }
         else if( (c & 0xf8) == 0xf0 )
         {
            state = -3;
            param = c & 0x07;
         }
         else if( c == '\x1b' )
         {
            /* Start of escape sequence */
            state = 1;
            param = 0;
         }
         else if( c == '\n' )
         {
            /* Newline: update cursor but don't buffer character */
            y++;
            x = 0;
         }
         else if( c == ' ' )
         {
            /* Space: update cursor but don't buffer character */
            x++;
         }
         else if( c == '\t' )
         {
            /* Tab: update cursor but don't buffer character */
            for(x++; x % 8; x++);
         }
         else if( c < 32 )
         {
            /* Other control characters (ignored) */
         }
         else
         {
            /* Single byte character */
            AddChar(x++, y, c);
         }
      }
   }
}

/* Output characters in sorted order */
static void OutputSorted(FILE *outfile)
{
   int i, x, y;

   /* 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(i = x = 0, y = min_y; i < character_count; i++)
   {
      while( y < characters[i].y )
      {
         WriteUTF8('\n', outfile);
         y++;
         x = 0;
      }
      while( x < characters[i].x )
      {
         WriteUTF8(' ', outfile);
         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[i + 1].y == characters[i].y &&
             characters[i + 1].x == characters[i].x )
      {
         i++;
      }
      WriteUTF8(characters[i].code, outfile);
      x += GetCharWidth(characters[i].code);
   }

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

/* Output characters in shuffled order */
static void OutputShuffled(int argc, char **argv)
{
   FILE *outfile = NULL;
   int i, x, y, index, layer_count = argc - 2;

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

   for(index = i = x = 0, y = max_y + 1;
       i < character_count && index < layer_count;
       index++)
   {
      if( index == 0 )
      {
         /* Preallocate vertical space for first layer */
         for(i = 0; i < max_y - min_y + 1; i++)
            WriteUTF8('\n', outfile);
         i = 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(; i < character_count; i++)
      {
         if( i >= character_count * (index + 1) / layer_count )
            break;
         if( y < characters[i].y )
         {
            fprintf(outfile, "\x1b[%dB", characters[i].y - y);
         }
         else if( y > characters[i].y )
         {
            fprintf(outfile, "\x1b[%dA", y - characters[i].y);
         }
         if( x < characters[i].x )
         {
            fprintf(outfile, "\x1b[%dC", characters[i].x - x);
         }
         else if( x > characters[i].x )
         {
            fprintf(outfile, "\x1b[%dD", x - characters[i].x);
         }
         WriteUTF8(characters[i].code, outfile);
         x = characters[i].x + GetCharWidth(characters[i].code);
         y = characters[i].y;
      }

      /* Move cursor to last line at the end of each layer */
      if( y < max_y )
         fprintf(outfile, "\x1b[%dB", max_y - y);
      WriteUTF8('\n', outfile);
      fclose(outfile);
      x = 0;
      y = max_y + 1;
   }
}

int main(int argc, char **argv)
{
   FILE *file = stdin;
   int i, j, tmp;

   if( argc > 1 && (argv[1][0] != '-' || argv[1][1] != '\0') )
   {
      if( (file = fopen(argv[1], "rb")) == NULL )
         return printf("Can not open %s for reading\n", argv[1]);
   }
   LoadInput(file);

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

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