bool At(void* key, void*& value); void RemoveEntry(void* key);

typedef void* Slot; Настоящее объявление надежно спрятано Slot First(); Возвращает Slot для перебора

Эквивалент нашей функции Peek

bool GetCurrent(Slot slot, void*& key, void*& value);

Эквивалент нашей функции Next

bool GetNext(Slot& slot, void*& key, void*& value);

Функция AddEntry() заносит в словарь новое значение с заданным ключом. Если ключ уже существует для другого значения, значение заменяется новым. Функция At() возвращает логический код, который показывает, присутствует ли ключ в словаре; если присутствует, функция возвращает true и value (значение, соответствующее данному ключу). Функция RemoveEntry() удаляет ключ и связанное с ним значение. Функция First() возвращает пассивный итератор, направленный таким образом, чтобы первый вызов GetNext() возвратил первый элемент словаря. Функция GetCurrent() возвращает пару ключ/значение, находящуюся в текущей позиции Slot. Функция GetNext() возвращает пару ключ/значение и перемещает итератор к следующему элементу. Единственное отличие между этими функциями заключается в перемещении логической позиции после получения объекта.

Мы воспользуемся словарем следующим образом: ключом будет объект, хранящийся в нашем наборе, а значением этого ключа - журнал вставок/удалений для данного объекта.

Класс журнала

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

class History { public:

History(); Пустой журнал

void Insert(Timestamp); Вставка в заданное время void Remove(Timestamp); Удаление в заданное время bool Exists(Timestamp); В заданное время bool Exists(); В настоящий момент

Функция Exists(Timestamp) возвращает true, если в заданное время последней операцией была вставка, и false - если последней операцией было удаление или до этого времени вообще не было операций. Безаргументная функция Exists() является синонимом для Exists(Timestamp) с очень большим значением времени - то есть до настоящего момента.

Абстрактный базовый класс

Класс набора делится на две части: абстрактный базовый класс, работающий с void*, и производный параметризованный класс, в который добавлена безопасность типов. Абстрактный базовый класс выглядит так:

В файле Set.h

class SetBase : private Dictionary { friend class InternalIterator; protected:

SetBase(); Чтобы класс был абстрактным

public:

class Iterator { Базовый класс внешнего итератора public:

virtual bool More() = 0;

virtual Type* Next() = 0;

Iterator* SetBase::ProvideIterator()

return new InternalIterator(this);

void SetBase::AddObject(void* entry)

void* v; History* h;

if (At(entry, v)) { Уже есть - проверить время h = (History*)v;

if (!h->Exists()) Необходимо выполнить вставку h->Insert(Timestamp());

else { Еще нет h = new History; h->Insert(Timestamp()); AddEntry(entry, h);

void SetBase::RemoveObject(void* entry)

void* v; History* h;

if (At(entry, v)) { Уже есть - проверить время h = (History*)v;

if (h->Exists()) Необходимо выполнить удаление h->Remove(Timestamp());

bool SetBase::Exists(void* entry, Timestamp ts) void* v;

return At(entry, v) && ((History*)v)->Exists(ts); bool SetBase::Exists(void* entry) void* v;

return At(entry, v) && ((History*)v)->Exists();

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

Внутренний итератор

Чтобы реализовать функцию ProvideIterator() , мы создаем как нетипизированный внутренний итератор, ограниченный файлом .cpp и производный от SetBase::Iterator , так и внешний - в виде параметризованной, безопасной по отношению к типам оболочки. Ниже приведен код внутреннего итератора, объявленного статически (то есть локального по отношению к файлу .cpp). Вся логика временных пометок спрятана в реализации этого класса.

В файле set.cpp

class InternalIterator : public SetBase::Iterator { private:

Dictionary* dictionary;

Dictionary::Slot* slot; Текущая позиция Timestamp my time; Время рождения данного итератора

public:

InternalIterator(Dictionary* d)

: dictionary(d), s1ot(d->First()), my time() {} virtual bool More(); virtual void* Next();

bool InternalIterator::More()

void* key; void* h;

if (!dictionary->GetCurrent(s1ot, key, h))

return false; позиция выходит за текущие границы

if (((History*)h)->Exists(my time)) return true; while (dictionary->GetNext(s1ot, key, h)); return false;

void* InternalIterator::Next()

void* key; void* keyl; void* h;

Предполагается, что клиент сначала вызвал More(), поэтому объект GetNext() не устарел dictionary->GetCurrent(s1ot, key, h); dictionary->GetNext(s1ot, keyl, h); return key;

Параметризованная оболочка, безопасная по отношению к типам

Наконец, в приведенном ниже параметризованном классе все становится безопасным по отношению к типам и начинает радовать глаз. Внешний итератор представляет собой параметризованную оболочку для внутреннего итератора, предоставляемого SetBase.

template <c1ass Type>

class Set : private SetBase {