/*  merge.c
 *
 * Part of !Ispell.
 * Merge a collection of presorted files into a single sorted one.
 *
 * Copyright (C) 1995  David Bryan.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */


#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <ctype.h>


#define MAX 40
#define BUFFERING 4


void heapify   (void);
void reheapify (void);
int  triorder  (int, int, int);
int  comp      (const char *, const char *);

FILE *output;
FILE *input[MAX];
char word[MAX][100];
int  order[MAX], start, pownum;

enum bool {false, true};


int main (int argc, char *argv[])
{
  int i, files, levels;

  if (argc < 3)
  {
    fprintf (stderr, "Syntax: %s outfile infile1 infile2 ...\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  if (!(output = fopen (argv[1], "w")))
  {
    fprintf (stderr, "Cannot open output file '%s'.\n", argv[1]);
    exit(EXIT_FAILURE);
  }
  else
  {
    setvbuf (output, malloc (sizeof (char) * BUFFERING * BUFSIZ),
             _IOFBF, BUFFERING * BUFSIZ);
  }

  files = argc - 2;
  levels = (int) (log ((double) (files + 1)) / log(2.0));
  start  = (1 << levels) - 2;
  pownum = (1 << (levels+1)) -2;

  for (i=0; i < pownum; i++)
  {
    word[i][0] = CHAR_MAX;
    word[i][1] = 0;
    order[i] = i;
  }

  for (i=0; i < argc-2; i++)
    if (!(input[i] = fopen (argv[i+2], "r")))
    {
      fprintf (stderr, "Cannot open input file '%s'.\n", argv[i]);
      exit(EXIT_FAILURE);
    }
    else
      if (!feof(input[i]))
      {
        setvbuf (input[i], malloc (sizeof (char) * BUFFERING * BUFSIZ),
                 _IOFBF, BUFFERING * BUFSIZ);
        fscanf(input[i], "%s", word[i]);
      }

  heapify ();

  while (word[order[0]][0] != CHAR_MAX)
  {
    fprintf (output, "%s\n", word[i = order[0]]);
    if (!feof(input[i]))
      fscanf(input[i], "%s", word[i]);
    else
    {
      word[i][0] = CHAR_MAX;
      word[i][1] = 0;
    }
    reheapify ();
  }

  exit (EXIT_SUCCESS);
}


void heapify (void)
{
  int parent = start,
      child  = pownum;

  while (parent >= 0)
    {
      (void) triorder (parent, child-1, child);
      parent--;
      child -= 2;
    }
}


void reheapify (void)
{
  int parent = -1,
      next   = 0,
      diff   = 1;

  while (parent != next && next <= start)
  {
    parent = next;
    next = triorder (next, next+diff, next+diff+1);
    diff <<= 1;
  }
}


int triorder (int parent, int left, int right)
{
  int temp;

  if (comp (word[order[left]], word[order[right]]))
    {
      if (comp (word[order[left]], word[order[parent]]))
      {
        temp = order[left];
        order[left] = order[parent];
        order[parent] = temp;
        return left;
      }
    }
  else
    {
      if (comp (word[order[right]], word[order[parent]]))
      {
        temp = order[right];
        order[right] = order[parent];
        order[parent] = temp;
        return right;
      }
    }
  return parent;
}


int comp (const char *a, const char *b)
{
  char ca,cb;

  while (*a != 0 && *b != 0)
  {
    if ((ca = tolower(*a)) < (cb = tolower (*b)))
      return true;
    if (ca > cb)
      return false;
    a++;
    b++;
  }

  return *a == 0;
}





