#include 
#include 
#include 

#define SEED 1001
#define EL_COUNT 4

using namespace std;

typedef class Item Item;

class Item {
	void *data;
	int data_length;
	Item *next;
	int index;
public:
	Item(int _index, void *_data, int l) 
	{
		data = malloc(l);
		memcpy(data,_data,l);
		index = _index;
		data_length = l;
	}
	~Item() {
		free(data);
		if (next != NULL) delete next;
	}
	void* get_data() {
		void *tmp = data;
		return tmp;
	}
	int get_length() {
		return data_length;
	}
	void set_next(Item *_next) {
		if (next != NULL) _next->set_next(next);
		next = _next;
	}
	Item* get_next() {
		return next;
	}
};

class item_array {
	Item **items;
	int index, alloced, used;
public:
	void add(Item *item) {
		if (alloced == used) {
			alloced = alloced + alloced/2;
			realloc(items, sizeof(*item)*alloced);
		}
		items[index] = item;
		index++;
		used++;
	}
	item_array() 
	{
		alloced = 4;
		used = 1;
		index = 1;
		items = (Item**)malloc(alloced*(sizeof(Item*)));
	} 
	Item** get_POD() 
	{
		items[0] = (Item*)(new int);
		memcpy(items[0],&used,sizeof(int));
		return items;
	}
};

typedef class TList {
	Item *first;
	int cur_index;
	int get_next_index() {return ++cur_index;};
public:
	~TList() {delete first;}
	Item* add_item(void *data, int l, Item *prev) {
		Item *cur_item = new Item(get_next_index(), data, l);
		if (first == NULL)
			first = cur_item;
		else {
			if (prev == NULL && first != cur_item) {
				cur_item->set_next(first);
				first = cur_item;
			} else 
				prev->set_next(cur_item);
		}

		return cur_item;
	}
	Item** find_items(void *data) {
		if (first == NULL) return NULL;
		item_array arr;
		Item *cur_item = first;
		do { 
			if (!memcmp(data,cur_item->get_data(),cur_item->get_length()))
				arr.add(cur_item);
		} while ((cur_item = cur_item->get_next()) != NULL);
		return arr.get_POD();
	}

	int add_after(void *data, int l, Item** list)
	{
		int *count = (int*)list[0];
		for (int i = 1; i < *count; i++)
			add_item(data, l, list[i]);
		free(list);
		return 0;
	}

	Item* get_head() {return first;}

};

void fill_list(TList *K, char L)
{
	srand(SEED);
	Item *prev = NULL;
	char *LL = new char;
	memcpy(LL,&L,1);
	for (int i = 0; i < EL_COUNT; i++) {
		if (rand()%3) 
			prev = K->add_item(LL,1,prev);
		else {
			char c = 'a'+rand()%25;
			prev = K->add_item(&c, 1, prev);
		}
	}
}

void print_list(TList *K)
{
	if (K->get_head() == NULL) {
		printf("List empty\n");
		return;
	}
	printf("--------List contents-------\n");
	Item *item = K->get_head();
	char *c = (char*)item->get_data(); 
	while (1) {
		printf("%c\n",(*c));
		item = item->get_next();
		if (item == NULL) break;
		c = (char*)item->get_data();
	}
	printf("----------------------------\n");
}

int main(int argc, char* argv[])
{
	TList *K = new TList;
	char L, L1;
	cout << "Input L" << endl;
	cin >> L;
	fill_list(K,L);
	print_list(K);
	cout << "Input L1" << endl;
	cin >> L1;
	K->add_after(&L1,1,K->find_items(&L));
	print_list(K);
	delete K;
	return 0;
}