Persistent Set

(задание к пересдаче зачетов 8.10.2016 и 15.10.2016)

Введение

Persistent структурой данных называется структура данных, модификация которой не портит предыдущую версию, позволяя работать как со старой версией этой структуры данных, так и с новой.

Одной из самых простых в реализации persistent структурой данных является persistent дерево поиска. Со ссылкам: [1] и [2] можно прочитать как оно устроено.

Интерфейс к персистентной структуре данных можно сделать двумя способами:

1. Сделать так, чтобы все модифицирующие операции, возвращали новую версию структуры. В этом случае, пользователь имеет возможность пользоваться как старой версией структуры, так и новой. При необходимости старую версию можно удалить. Такой интерфейс имеет недостаток: сигнатуры всех модифицирующих операций в нем будут отличатся от сигнатур аналогичной не-persistent структуры данных.
2. Другим вариантом является оставить сигнатуры модифицирующих операций, как в не-persistent структуре данных, но предоставить O(1) операцию копирования. В этом случае если пользователю необходимо сохранить старую версию, он может сделать копию явно.

В этом задании применяется второй способ.

Чтобы поддержать возможность удаления разных версий дерева в произвольном порядке необходимо понимать какие ноды принадлежат лишь удаляемому дереву и не шарятся с другими деревьями. Наиболее простой способ это сделать — использовать счетчики ссылок. Для этого требуется похранить в каждой ноде счетчик количества родителей. Если у ноды появляется новый родитель счетчик увеличивается, если удаляется — уменьшается. Когда удаляется последний родитель ноды, сама нода тоже должна удалиться.

Задание

В этом задании необходимо реализовать класс со следующим интерфейсом:

struct persistent_set
{
    // Вы можете определить этот тайпдеф по вашему усмотрению.
    typedef ... value_type;

    // Bidirectional iterator.
    struct iterator;

    // Создает пустой persistent_set.
    persistent_set();

    // Создает копию указанного persistent_set-а.
    persistent_set(persistent_set const&);

    // Изменяет this так, чтобы он содержал те же элементы, что и rhs.
    // Инвалидирует все итераторы, принадлежащие persistent_set'у this, включая end().
    persistent_set& operator=(persistent_set const& rhs);

    // Деструктор. Вызывается при удалении объектов persistent_set.
    // Инвалидирует все итераторы ссылающиеся на элементы этого persistent_set
    // (включая итераторы ссылающиеся на элемент следующий за последним).
    ~persistent_set();

    // Поиск элемента.
    // Возвращает итератор на найденный элемент, либо end(), если элемент
    // с указанным значением отсутвует.
    iterator find(value_type);

    // Вставка элемента.
    // 1. Если такой ключ уже присутствует, вставка не производиться, возвращается итератор
    //    на уже присутствующий элемент и false.
    // 2. Если такого ключа ещё нет, производиться вставка, возвращается итератор на созданный
    //    элемент и true.
    // Если вставка произведена, инвалидирует все итераторы, принадлежащие persistent_set'у this, включая end().
    std::pair<iterator, bool> insert(value_type);

    // Удаление элемента.
    // Инвалидирует все итераторы, принадлежащие persistent_set'у this, включая end().
    void erase(iterator);

    // Возващает итератор на элемент с минимальный ключом.
    iterator begin() const;
    // Возващает итератор на элемент следующий за элементом с максимальным ключом.
    iterator end() const;
};

struct persistent_set::iterator
{
    // Элемент на который сейчас ссылается итератор.
    // Разыменование итератора end() неопределено.
    // Разыменование невалидного итератора неопределено.
    value_type const& operator*() const;

    // Переход к элементу со следующим по величине ключом.
    // Инкремент итератора end() неопределен.
    // Инкремент невалидного итератора неопределен.
    iterator& operator++();
    iterator operator++(int);

    // Переход к элементу с предыдущим по величине ключом.
    // Декремент итератора begin() неопределен.
    // Декремент невалидного итератора неопределен.
    iterator& operator--();
    iterator operator--(int);
};

// Сравнение. Итераторы считаются эквивалентными если они ссылаются на один и тот же элемент.
// Сравнение с невалидным итератором не определено.
// Сравнение итераторов двух разных контейнеров не определено.
bool operator==(persistent_set::iterator, persistent_set::iterator);
bool operator!=(persistent_set::iterator, persistent_set::iterator);

Обратите внимание, что все модифицирующие операции persistent_set-а инвалидируют все итераторы принадлежащие этому persistent_set-у.

Разрешается реализовывать persistent_set с помощью persistent несбалансированного дерева поиска. Операции поиска, вставки, удаления должны работать за O(h), где h — высота дерева.

Операции копирования и присваивания должны выполняться за O(1) и удовлетворять гарантии безопасности исключений nothrow.

Суммарный объем используемой памяти не должен превосходить сумму размеров существующих в данный момент деревьев.

В случаях когда это задание не предписывает определенного поведения, любое поведение конкретной реализации считается удовлетворяющим заданию. Предполагается, что не все случаи неопределенного поведения, указанные в этом задании, можно свести к assert-у, не жертвуя простотой или эффективностью реализации. В тех случаях, где это уместно, рекомендуемым поведением является срабатывание assert-а.