XOR-связный спсок

/*
    Программа демонстрации циклического двунаправленного списка
    с использованием XOR-адресации.
*/

#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cstddef>

using namespace std;

typedef uintptr_t INT_P;
// INT_PTR уже был, но мы же хотим кросслпатформенно.
// да можно было сразу uintptr_t везде писать, но сейчас уже поздно.
// Пусть так остаётся.

#define K_NEXT 'n'
#define K_BACK 'b'
#define K_DEL 'd'
#define K_INS 'i'
#define K_END 'e'
#define K_NOTUSED 'u'
// Выше -- буквы для управления.

#define END_STR "end"
// Строка для прекращения ввода.


// Структура для хранения данных. Можно было сделать через шаблоны (лень).
// Можно было зашить её в класс списка (неуниверсально).
struct data_struct
    {
        char title[80]; // Заголовок элемента.
        int value; // Значение, с ним связанное. На самом деле тут будет идентификатор элемента (номер).
    };

// Структура элемента списка.
struct x_list_entry
    {
        void *data; // Указатель на данные. Что угодно. Здесь -- data_struct
        INT_P x_address; // XOR-адрес. Для определённости и нетавталогии будем называть его "ёж".
    };

// Класс списка -- x_list
class x_list
    {
        private:
            // Т.к. для навигации нужно знать два последовательных элемента, будем хранить оба.
            x_list_entry *entry1; // Первый. Считается "текущим элементом".
            x_list_entry *entry2; // Второй.
            unsigned int n; // Размер списка
        public:
            void next(void); // Прокрутить вперёд.
            void prev(void); // Прокрутить назад.
            void *get(void); // Получить адрес данных текущего элемента.
            void insert(void *data); // Вставить данные по адресу как новый элемент после текущего
            unsigned int erase(void); // Стереть текущий элемент.
            inline unsigned int size(void){return n;}; // Получить размер списка.
            x_list(void); // Конструктор.
            ~x_list(void); // Деструктор.
    };

// Конструктор класса x_list .
x_list::x_list()
    {
        // Создаём первые два элемента
        // (если в списке меньше двух элементов, происходит специальная обработка,
        // фактически хотя бы два элемента есть, но снаружи этого не видно).
        entry1=new x_list_entry;
        entry2=new x_list_entry;
        // Размер равен нулю.
        n=0;
        // Если у двух соседних элементов ежи равны нулю, то они ссылаются друг на друга.
        entry1->x_address=NULL;
        entry2->x_address=NULL;
    }

// Деструктор класса x_list .
x_list::~x_list()
    {
        // Удаляем пока есть что. Обратите внимание, указатели с данными должны быть
        // обработаны пользователем. Класс не знает какой там тип, поэтому не может
        // вызвать деструктор. Через шаблоны это можно было бы сделать.
        while(n>0)
            erase();
        // Удаляем последние два элемента (при обычном удалении их удалить нельзя,
        // там же спецобработка!
        delete entry1;
        delete entry2;
    }

// Перемещение вперёд по списку.
void x_list::next(void)
    {
        // Спецобработка: если 0 элементов, перемещаться некуда, если 1 элемент, мы на нём
        // и остаёмся.
        if(n<2)
            return;
        x_list_entry *temp; // Для временного хранения старого текущего элемента.
        temp=entry1; // Сохранили.
        entry1=entry2; // Теперь текущий -- второй (двигаемся вперёд).
        entry2=reinterpret_cast<x_list_entry*>((reinterpret_cast<INT_P>(temp))^(entry1->x_address));
        // Вычисляем, где новый второй, с использованием текущего и старого текущего.
    }

// Перемещение назад по списку.
void x_list::prev(void)
    {
        // Спецобработка: если 0 элементов, перемещаться некуда, если 1 элемент, мы на нём
        // и остаёмся.
        if(n<2)
            return;
        x_list_entry *temp; // Для временного хранения старого второго элемента.
        temp=entry2; // Сохранили.
        entry2=entry1; // Теперь второй -- текущий (двигаемся назад)
        entry1=reinterpret_cast<x_list_entry *>((reinterpret_cast<INT_P>(temp))^(entry2->x_address));
        // Вычиляем, где новый текущий, с использованием второго и старого второго.
    }

// Получение адреса данных.
void *x_list::get(void)
    {
        // Если пусто, возвращаем NULL.
        if(n==0)
            return NULL;
        // Если не пусто, возвращаем адрес на данные текущего элемента.
        return entry1->data;
    }

// Добавление элемента.
void x_list::insert(void *data)
    {
        // Эта операция выполняется всегда, даже в случае спецобработки, поэтому делаем
        // её с начала: увеличиваем размер списка.
        n++;
        if(n==1) // Если размер стал равен одному, список был пустым.
            {
                entry1->data=data; // Пишем данные в текущий элемент.
                return;
            }
        if(n==2) // Если размер стал равен двум, был один элемент.
            {
                entry2->data=data; // Пишем данные во второй элемент.
                next(); // Прокручиваем список, делая новый текущим.
                return;
            }

        x_list_entry *temp; // Временный элемент, который скоро войдёт в список
        temp=new x_list_entry; // Выделяем ему память.
        temp->data=data; // Пишем данные.
        // Определяем ёж нового элемента.
        temp->x_address=(reinterpret_cast<INT_P>(entry1))^(reinterpret_cast<INT_P>(entry2));
        // Теперь надо пересчитать ежи соседних.
        entry2->x_address=(reinterpret_cast<INT_P>(temp))^((entry2->x_address)^(reinterpret_cast<INT_P>(entry1)));
        entry1->x_address=(reinterpret_cast<INT_P>(temp))^((entry1->x_address)^(reinterpret_cast<INT_P>(entry2)));
        entry2=temp; // Новый элемент теперь вместо второго.
        next(); // Прокручиваем список, делая новый текущим.
    }

// Удаление элемента из списка.
unsigned int x_list::erase()
    {
        // Спецобработка.
        if(n==0)
            return 0; // Пустой список пуще не станет.
        if(n==1) // Если оставался 1 элемент, просто говорим, что стало 0.
            return --n;
        if(n==2) // Если оставалось 2 элемента, прокручиваем список и говорим что осталось 1.
            {
                next();
                return --n;
            }
        // Тут спецобработка заканчивается и надо уже что-то удалять.
        x_list_entry *temp; // Тут будем хранить предыдущий элемент
        temp=reinterpret_cast<x_list_entry*>((entry1->x_address)^(reinterpret_cast<INT_P>(entry2)));
        temp->x_address=(temp->x_address^(reinterpret_cast<INT_P>(entry1)))^(reinterpret_cast<INT_P>(entry2));
        // Нашли элемент, пересчитали его ёж с учётом что текущего элемента больше нет.
        entry2->x_address=(entry2->x_address^(reinterpret_cast<INT_P>(entry1)))^(reinterpret_cast<INT_P>(temp));
        // Пересчитали ёж второго элемента с учётом того же.
        delete entry1; // Удаляем текущий, нас ничто не держит.
        entry1=temp; // Теперь текущий -- предыдущий.
        next(); // Прокрутим, чтобы текущим стал второй, так логичнее.
        return --n; // Уменьшили размер и вернули новый.

    }

// Программа-демонстрация. Тут уже почти без пояснений.

int main(int argc, char* argv[])
    {
        x_list list;
        char user_input[80];
        char key=K_NOTUSED;
        bool exit_flag=false;
        data_struct *d;
        int id=0;

        // ФАЗА 1. Заполнение списка.

        cout << "Enter list entries, one per line, \"" << END_STR << "\" to stop.\n";
        do
            {
                cout << "("<<list.size()<<"):";
                cin >> user_input;
                d=new data_struct;
                strcpy(d->title,user_input);
                d->value=id++;
                list.insert(d);
            }
        while(strcmp(user_input,END_STR)!=0); // Пока не введут условное кодовое слово. Слово добавляется в список.

        // ФАЗА 2. Управление списком.

        cout << "List control: " << K_NEXT << "=NEXT, " << K_BACK << "=BACK, " << K_DEL << "=DELETE CURRENT, " << K_INS << "=INSERT NEW, " << K_END << "=EXIT.\n";
        while(!exit_flag) // Цикл работы со списком.
            {
                if(isalpha(key))
                    if(!list.get())
                        cout << "EMPTY LIST\n";
                    else
                        cout <<"("<<key<<") Size="<<list.size()<<";["<<((data_struct *)list.get())->value<<"]:"<<((data_struct *)list.get())->title<<"\n";
                key=getchar();
                switch(key) // Обработка команд.
                    {
                        case K_NEXT:
                            list.next();
                            break;
                        case K_BACK:
                            list.prev();
                            break;
                        case K_DEL:
                            delete ((data_struct *)list.get());
                            list.erase();
                            break;
                        case K_INS:
                            cout << "Enter new element:";
                            cin >> user_input;
                            d=new data_struct;
                            strcpy(d->title,user_input);
                            d->value=id++;
                            list.insert(d);
                            break;
                        case K_END:
                            exit_flag=true;
                            break;
                        default:
                            if(isalpha(key))
                                cout << "List control: " << K_NEXT << "=NEXT, " << K_BACK << "=BACK, " << K_DEL << "=DELETE CURRENT, " << K_INS << "=INSERT NEW, " << K_END << "=EXIT.\n";
                            break;
                    }
            }
        return 0;
    }