/* Sortowanie wierszy: Wersja 3 (z drzewem binarnym) */ 
/* AR, 2018-23 + elementy: Kernighan-Ritchie, 1994 */


#include <stdio.h>
#include <stdlib.h>  /* tutaj: malloc */
#include <string.h>


struct tnode {   /* wezel drzewa */
  char *line;   /* wiersz tekstu */
  int count;   /* licznik wystapien */
  struct tnode *left;    /* lewy potomek */
  struct tnode *right;  /* prawy potomek */
};


struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int treesize(struct tnode *);
int treedepth(struct tnode *);



#define MAXLINE 2000  /* dopuszczalna dlugosc wiersza */

/* porzadkowanie wierszy tekstu */
int main()
{
  struct tnode *root = NULL;  /* korzen drzewa */
  char line[MAXLINE+1];
  int size;
  
  while (fgets(line, MAXLINE+1, stdin)) 
    root = addtree(root, line);
  size = treesize(root);
  fprintf(stderr, "==> Wprowadzono %d rozn%s. "
	  "Glebokosc drzewa: %d <==\n", size,
	  (2<=(size%10) && (size%10)<=4) ?
	  "e wiersze" : "ych wierszy",
	  treedepth(root));
  treeprint(root);
  return 0;
}



/* treeprint: wypisz uporzadkowane drzewo */
void treeprint(struct tnode *p)
{
  int i;
  
  if (p != NULL) {
    treeprint(p->left);
    for (i=0; i < p->count; i++)
      printf("%s", p->line);  /*  ==> p->line zawiera '\n'! */
    treeprint(p->right);
  }
}


/* treesize:  liczba wezlow drzewa */
int treesize(struct tnode *p)
{
  if (NULL == p)
    return 0;
  else
    return treesize(p->left) + 1 + treesize(p->right);
}


#define max(a,b) ((a) > (b) ? (a) : (b))

/* treedepth:  glebokosc drzewa */
int treedepth(struct tnode *p)
{
  int ldep, rdep;
  
  if (NULL == p)
    return 0;
  else {
    ldep = treedepth(p->left);
    rdep = treedepth(p->right);
    return 1 + max(ldep, rdep);
    /*  
	A dlaczego nie napisac: 
	1 + max(treedepth(p->left), treedepth(p->right)) ??  
    */
  }
}


/* addtree: dodaj wezel dla s; ... */
struct tnode *addtree(struct tnode *p, char *s)
{
  int len, cond;

  if (NULL == p) {   /* nowy wiersz */
    len = strlen(s);   /* zawiera '\n' */
    p = (struct tnode *)malloc(sizeof(struct tnode));
    if (!(p) || !(p->line = strndup(s, len))) {
      fprintf(stderr, "ERROR: INPUT TOO BIG TO SORT\n");
      exit(1);
    }
    p->count = 1;
    p->left = p->right = NULL;
  }
  else if ((cond = strcmp(s, p->line)) == 0 ) {
    p->count++;   /* powtorzony wiersz  */
  }

  /* wiersz (s) inny niz (p->line)  ==> sprawdzamy poddrzewa:  */  

  else if (cond < 0 ) {  /* wiersz leksykalnie MNIEJSZY */
    p->left = addtree(p->left, s);
  }
  else {  /* wiersz leksykalnie WIEKSZY */
    p->right = addtree(p->right, s);
  }

  return p;
}