#ifndef _TABLE_ELEMENT_H_
#define _TABLE_ELEMENT_H_

struct s_table_element {
    char key[3];
    int val_size;
    char* val;
};

typedef struct s_table_element TableElement;


int cmp_elements(TableElement, TableElement);

int read_element(TableElement*);
int read_key(TableElement*);

void print_element(TableElement);
void print_key(TableElement e);

void clone_element(TableElement, TableElement*);

#endif

#include "table_element.h"
#include <stdio.h>
#include <stdlib.h>

int cmp_elements(TableElement a, TableElement b) {
    int i;
    for (i = 0; i < 3; i++) {
        if (a.key[i] < b.key[i]) {
            return -1;
        } else if (a.key[i] > b.key[i]) {
            return 1;
        }
    }
    return 0;
}

int is_space(char c) {
    return c == ' ' || c == '\n';
}

int read_key(TableElement* e) {
    int i;
    char c;

/* key does not begin with space */
    do {
        if (scanf("%c", &c) != 1) {
            return 0;
        }
    } while (is_space(c));
    
    e->key[0] = c;
/* read rest of key's symbols */
    for (i = 1; i < 3; i++) {
        if (scanf("%c", &(e->key[i])) != 1) {
            return 0;
        }
    }
    return 1;
}


int read_value(TableElement* e) {
    int i;
    char c;
    
    e->val_size = 8;
    e->val = malloc(sizeof(char)*e->val_size);
    
/* value can begin with anything */
    i = 0;
    while (1) {
        c = getchar();
        if (i == e->val_size) {
            e->val_size *= 2;
            e->val = realloc(e->val, sizeof(char)*e->val_size);
        }
        if (c == EOF || c == '\n' || c == '\0') {
            e->val[i] = '\0';
            e->val_size = i + 1;
            e->val = realloc(e->val, sizeof(char)*e->val_size);
            return i;
        }
        e->val[i] = c;
        i++;
    }
}

int read_element(TableElement* e) {
    /*Expect that key and value are divided with
        some space simbol, but only one*/
    return read_key(e) && getchar() && read_value(e);
}

void print_key(TableElement e) {
    int i;
    for (i = 0; i < 3; i++) {
        printf("%c", e.key[i]);
    }
}
void print_value(TableElement e) {
    printf("%s", e.val);
}
void print_element(TableElement e) {
    print_key(e);
    putchar(' ');
    print_value(e);
    printf("\n");
}


void clone_element(TableElement e, TableElement* new) {
    int i;
    for (i = 0; i < 3; i++) {
        new->key[i] = e.key[i];
    }
    new->val_size = e.val_size;
    new->val = malloc(sizeof(char)*new->val_size);
    for (i = 0; i < new->val_size; i++) {
        new->val[i] = e.val[i];
    }
}

#ifndef _TABLE_H_
#define _TABLE_H_

#include "table_element.h"

struct s_table {
    TableElement* elements;
    int size;
};

typedef struct s_table Table;

int read_table(Table*);
void print_table(Table);

int search_binary(Table, TableElement, TableElement*);

int sort_table(Table*, int* n_swaps, int* n_cmps);

#endif

#include "table.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int read_table(Table* t) {
    int i;
    if (scanf("%d", &(t->size)) != 1) {
        return 0;
    }
    if (t->size < 0) {
        return 0;
    }
    t->elements = malloc(sizeof(TableElement)*t->size);
    for (i = 0; i < t->size; i++) {
        read_element(&(t->elements[i]));
    }
    return t->size;
}

void print_table(Table t) {
    int i;
    for (i = 0; i < t.size; i++) {
        print_element(t.elements[i]);
    }
}


int search_binary(Table t, TableElement key, TableElement* result) {
    int l = 0;
    int r = t.size - 1;
    int m;
    int cmp;
    
    if (t.size < 1) {
        return 0;
    }
    
    while (l <= r) {
        m = (r + l) / 2;
        cmp = cmp_elements(key, t.elements[m]);
        if (cmp == 0) {
            clone_element(t.elements[m], result);
            return 1;
        } else if (cmp > 0) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return 0;
}

int is_sorted(Table* t, int* n_cmps) {
    int i;
    for (i = 0; i < t->size - 1; i++) {
        (*n_cmps)++;
        if (cmp_elements(t->elements[i], t->elements[i + 1]) == 1) {
            return 0;
        }
    }
    return 1;
}

int sort_table(Table* t, int* n_swaps, int* n_cmps) {
    srand ( time(NULL) );
    while (!is_sorted(t, n_cmps)) {
        int i1 = rand() % t->size;
        int i2 = rand() % t->size;
        TableElement e;
        (*n_swaps)++;
        /* swap random elements */
        clone_element(t->elements[i1], &e);
        clone_element(t->elements[i2], &(t->elements[i1]));
        clone_element(e, &(t->elements[i2]));
    }
    return 1;
}

#include "table.h"
#include "table_element.h"
#include <stdio.h>

int main() {
    Table t;
    int res;
    TableElement e;
    TableElement key;
    
    int swaps, cmps;
    swaps = cmps = 0;
    
    read_table(&t);
    printf("===Считанная таблица===\n");
    print_table(t);
    sort_table(&t, &swaps, &cmps);
    printf("===Отсортированная таблица===\n");
    print_table(t);
    printf("Sorted in %d cmps and %d swaps\n", cmps, swaps);
    printf("===Поиск ключей===\n");
    while (1) {
        res = read_key(&key);
        if (!res) {
            break;
        }
        res = search_binary(t, key, &e);
        if (res) {
            print_element(e);
        } else {
            printf("err\n");
        }
    }
    return 0;
}

CC = gcc
LD = gcc
CFLAGS = -ansi -Wall -pedantic -c
LFLAGS = -o $(PROGRAMM)

PROGRAMM = prog
FILES = main.o table.o table_element.o

all: $(PROGRAMM)

$(PROGRAMM): $(FILES)
	$(LD) $(LFLAGS) $(FILES)

clean:
	rm -f *.o $(PROGRAMM)

.c.o:
	$(CC) $(CFLAGS) $<

test: all
	./$(PROGRAMM) < test1
	./$(PROGRAMM) < test2

table.o: table.h table_element.h
table_element.o: table_element.h
main.o: table.h table_element.h

7                                       
123    ---
234   |   |
345    --- 
456   |   |
567    ---
678 факультет   
789    МЭИ
1__
123
234
345
456
567
678
789
890
346

7                                       
234   |   |
235    ---
456 факультет   
123    ---
125    --- 
789    МЭИ
124   |   |
1__
123
234
345
456
567
678
789
890
346