#include <time.h>

#define MAXINPUT        (10)                      /* max numbers as input */
#define ALLOCSIZE       (1024)                    /* # of elements to alloc */

#define MIN(a,b)        (((a)<(b))?(a):(b))
#define MAX(a,b)        (((a)>(b))?(a):(b))
#define ABS(a)          (((a)<0)?-(a):(a))

#define NANOSEC    1000000000.0
#define MILLISEC   1000

typedef enum {
    Nop='N',
    Add='+',
    Sub='-',
    Mul='*',
    Div='/',
    End='\0'                                      /* Only for "printf" */
} OPER;

typedef struct stack {
    char name[80];
    int size;
    int last;
    struct stack *next;
    int stack[MAXINPUT+1];
} STACK;

#define TREE_UNDEF      (-1)                      /* should not happen */
#define TREE_LEAF       0
#define TREE_NODE       1
#define TREE_LEFT       'L'
#define TREE_RIGHT      'R'
#define TREE_TOP        'T'

#define EMPTY           -1

typedef struct node {
    int type;                                     /* TREE_LEAF or TREE_NODE */
    int op;                                       /* operator (nodes only) */
    int val;                                      /* value (leafs only) */
    int eval;                                     /* eval (unused) */
    int prof;                                     /* max left/right profs */
    int left_prof;
    struct node *left;
    int right_prof;
    struct node *right;
    struct node *next;                            /* for transv walk and free nodes */
} NODE;

typedef struct tree {
    char name[80];
    NODE *head;
    struct tree *next;
    int nodes;                                    /* number of nodes */
    int leaves;                                   /* number of leaves */
    int depth;                                    /* max depth */
} TREE;

typedef struct best {
    int res;
    int diff;
    int nops;
    char *oper;
    NODE *root;
    int *values;
    struct timespec timer;
} BEST;

/* lceb.c */
extern void print_results();

/* signal.c */
extern void set_intr();
extern int stopped();
extern void set_alarm(int ms);

/* tree.c */
extern NODE *get_node();
extern int free_node(NODE *node);
extern int compare_nodes(NODE *node1, NODE *node2, int depth);
extern void print_node(NODE *node, char side, int depth, int details);
extern void print_tree(TREE *tree, int details);
extern void print_trees(int details);
extern TREE *new_tree(char *name);
extern NODE *dup_node(NODE *src);
//extern NODE *build_tree(int *desc, int size);
extern NODE *build_tree(char *desc, int size);
//extern void gen_tree(int *seq, int n, int nb1, int nb0);
extern void gen_reduced_trees(int n);
extern void gen_tree(char *seq, int n, int nb1, int nb0, int reduced);
extern TREE *nth_tree(int n);
extern int n_trees();

/* stack.c */
extern void print_stack(STACK *stack, int details);
extern void print_stacks();
//extern int keep_stack(STACK *stack);
//extern STACK *new_stack(int size, char *name, int keep);
extern STACK *new_stack(int size, char *name, int keep);
extern int *push_stack(STACK *stack, int val);
extern int *pop_stack(STACK *stack);
extern STACK *dup_stack(STACK *stack, char *name);
extern void swap_stack(int *elts, int i, int j);
extern int permute_stack(int *array, int n);
extern void gen_stacks(STACK *stack);
extern void mergesort_stack(int *array, int left, int right);
extern STACK *nth_stack(int n);
extern int n_stacks();
// extern STACKELT *set_op_stack(STACK *stack, int pos, OPER op);
// extern STACKELT *set_ops_stack(STACK *stack, char *ops);

/* oper.c */
extern void print_comb(int n);
extern void print_combs();
//extern unsigned n_combine(int nops, int len);
//extern char *combine(char *ops, int len, int n);
extern void gen_combinations(int nops);
extern int n_combs();
extern char *nth_comb(int n);

/* eval.c */
/* stack version */
//extern int eval_cell(STACKELT *pos);
//extern int eval_stack(STACK *stack);
/* tree version */
extern int eval_node(NODE *node, int depth, int *pvals, char *pops, int *ncalcs);
extern int get_totnodes();
extern int get_totleaves();

/* best.c */
extern void set_target (int n);
extern int check_best(int res, int nops, NODE *node, int *values, char *ops);
extern void print_best(NODE *node, int *values, char *pops, int depth);
extern void print_bests();

/* timer.c */
extern int sigint_received;
extern void start_timer();
extern void set_timer(struct timespec *timer);
extern double get_timer(struct timespec timer);