Итерация
Итерация - это еще один архитектурный шаблон нашей библиотеки. В главе 3 уже отмечалось, что итератор представляет собой операцию, обеспечивающую последовательный доступ ко всем частям объекта. Оказывается, такой механизм нужен не только пользователям, он необходим и при реализации самой библиотеки, в частности, ее базовых классов.
При этом перед нами стоял выбор: можно было определять итерации как часть протокола объектов или создавать отдельные объекты, ответственные за итеративный опрос других структур. Мы выбрали второй подход по двум причинам:
Наличие выделенного итератора классов позволяет одновременно проводить несколько просмотров одного и того же объекта.
Наличие итерационного механизма в самом классе несколько нарушает его инкапсуляцию; выделение итератора в качестве отдельного механизма поведения способствует достижению большей ясности в описании класса.
Для каждой структуры определены две формы итераций. Активный итератор требует каждый раз от клиента явного обращения к себе для перехода к следующему элементу. Пассивный итератор применяет функцию, предоставляемую клиентом, и, таким образом, требует меньшего участия клиента. Чтобы обеспечить безопасность типов, для каждой структуры создаются свои итераторы.
Рассмотрим в качестве примера активный итератор для класса Queue:
template <class Item>
class QueueActiveIterator {
public: QueueActiveIterator(const Queue<Item>&);
~QueueActiveIterator();
Пассивный итератор реализует "применяемую" функцию. Эта идиома обычно используется в функциональных языках программирования. void reset();
int next();
int isDone() const;
const Item* currentItem() const;
protected: const Queue<Item>& queue;
int index;
};
Каждому итератору в момент создания ставится в соответствие определенный объект. Итерация начинается с "верха" структуры, что бы это ни значило для данной абстракции.
С помощью функции currentItem клиент может получить доступ к текущему элементу; значение возвращаемого указателя может быть нулевым в случае, если итерация завершена или если массив пуст.
Переход к следующему элементу последовательности происходит после вызова функции next (которая возвращает 0, если дальнейшее движение невозможно, как правило, из-за того, что итерация завершена). Селектор isDone служит для получения информации о состоянии процесса: он возвращает 0, если итерация завершена или структура пуста. Функция reset позволяет осуществлять неограниченное количество итерационных проходов по объекту.
Например, при наличии следующего объявления:
BoundedQueue<NetworkEvent> eventQueue;
фрагмент кода, использующий активный итератор для захода в каждый элемент очереди, будет выглядеть так:
QueueActiveIterator<NetworkEvent> iter(eventQueue);
while (!iter.isDone()) { iter.currentItem()->dispatch();
iter.next();
}
Итерационная схема, приведенная на рис. 9-9, иллюстрирует данный сценарий работы и, кроме того, раскрывает некоторые детали реализации итератора. Рассмотрим их более подробно.
Конструктор класса QueueActiveIterator сначала устанавливает связь между итератором и конкретной очередью. Затем он вызывает защищенную функцию cardinality, которая определяет количество элементов в очереди. Таким образом, конструктор можно описать следующим образом:
template<class Item>
QueueActiveIterator<Item>::QueueActiveIterator(const Queue<Item>& q)
:queue(q), index(q.cardinality() ? 0 : -1) {}
Класс QueueActiveIterator имеет доступ к защищенной функции cardinality класса Queue, поскольку числится в дружественных ему.
Операция итератора isDone проверяет принадлежность текущего индекса допустимому диапазону, который определяется количеством элементов очереди:
Рис. 9-9. Механизм итерации.
template<class Item>
int QueueActiveIterator<Item>::isDone() const
{ return ((index < 0) || (index >= queue.cardinality()));
}
Функция currentItem возвращает указатель на элемент, на котором остановился итератор. Реализация итератора в виде индекса объекта в очереди дает возможность в процессе итераций без труда добавлять и удалять элементы из очереди:
template<class Item>
const Item* QueueActiveIterator<Item>::currentItem() const
{ return isDone() ? 0 : &queue.itemAt(index);
}
При выполнении данной операции итератор снова вызывает защищенную функцию очереди, на сей раз itemAt. Кстати, currentItem можно использовать для работы как с ограниченной, так и с неограниченной очередью. Для ограниченной очереди itemAt просто возвращает элемент массива по соответствующему индексу. Для неограниченной очереди операция itemAt будет осуществлять проход по связному списку. Правда, как мы помним, класс Unbounded хранит информацию о последнем элементе, к которому было обращение, поэтому переход к следующему за ним элементу очереди (что и происходит при продвижении итератора) будет достаточно простым.
Операция next увеличивает значение текущего индекса на единицу, что соответствует переходу к следующему элементу очереди, а затем проверяет допустимость нового значения индекса:
template<class Item>
int QueueActiveIterator<Item>::next()
{ index++;
return !isDone();
}
Итератор, таким образом, в процессе своей работы вызывает две защищенные функции класса Queue: cardinality и itemAt. Определив эти функции как чисто виртуальные, мы передали ответственность за их конкретную оптимальную реализацию классам, производным от Queue.
Ранее отмечалось, что одна из основных задач наших архитектурных решений заключается в том, чтобы дать возможность клиенту копировать, присваивать и проверять на равенство экземпляры абстрактного базового класса, даже если они имеют различное представление. Эта возможность достигается за счет использования итераторов и некоторых служебных функций, позволяющих просматривать структуры независимо от их представления. Например, оператор присваивания для класса Queue можно определить следующим образом:
template<class Item>
Queue<Item>& Queue<Item>::operator=(const Queue<Item>& q)
{ if (this == &q) return *this;
((Queue<Item>&)q).lock();
purge();
QueueActiveIterator<Itea> iter(q);
while (!iter.isDone()) { add(*iter.currentItem());
iter.next();
}
((Queue<Item>&)q).unlock();
return *this;
}
В данном алгоритме используется идиома блокирования, которая более подробно рассмотрена в следующем разделе.
Присваивание осуществляется в порядке просмотра активным итератором структуры, определяемой аргументом q. Сначала защищенная служебная функция purge очищает очередь, а затем к ней с помощью другой защищенной служебной функции add последовательно добавляются новые элементы. Тот факт, что процесс итерации осуществляется с помощью полиморфных функций, дает возможность копировать, присваивать и проверять на равенство объекты, имеющие одинаковую структуру, но с разными представлениями.
Пассивный итератор, который также называют аппликатором, характеризуется тем, что он применяет определенную функцию к каждому элементу структуры. Для класса Queue пассивный итератор можно определить следующим образом:
template <class Item>
class QueuePassiveIterator {
public: QueuePassiveIterator(const Queue<Item>&);
~QueuePassiveIterator();
int apply(int (*)(const Item&));
protected: const Queue<Item>& queue;
};
Пассивный итератор действует на все элементы структуры за (логически) одну операцию. Таким образом, функция apply последовательно производит одну и ту же операцию над каждым элементом структуры, пока передаваемая итератору функция не возвратит нулевое значение или пока не будет достигнут конец структуры (в первом случае функция apply сама возвратит нулевое значение в знак того, что итерация не была завершена).
