Тестирование софта - статьи

       

Итераторы


В определении элементарного ограничения указано, что для него нужно задать способ вычисления множества допустимых значений. Мы будем использовать для этого технику итераторов.

В самом общем виде итератор - это объект, имеющий несколько последовательных состояний. Итератор может перевести себя в начальное состояние; находясь в каком-то состоянии, он может перевести себя в следующее состояние, а также ответить на вопрос, имеется ли у него следующее состояние. Итератором значений называется итератор, связанный с некоторым упорядоченным множеством. Итератор значений можно рассматривать как "указатель" на элемент множества. Для него имеются три операции: встать в начало множества, передвинуться на следующий элемент множества и выдать текущий элемент множества (вместо "выдачи" текущего элемента итератор значений может проделать с ним любую другую операцию).

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

Пример. Пусть имеются итераторы значений i1, i2, связанные с множествами {a,b,c},{d,e} соответственно. И пусть мы хотим построить итератор значений декартова произведения этих множеств.

Используем для этого такой комбинатор (рис.8): его состояния - это тройка состояний итераторов i1, i2. Начальное состояние - тройка начальных состояний итераторов i1, i2. Таким образом, чтобы перейти к начальному состоянию, наш комбинатор переводит итераторы i1, i2 в начальное состояние. Чтобы перейти к следующему состоянию, комбинатор смотрит, в каком положении находится итератор i2. Если у этого итератора есть следующее состояние, то итератор в него переводится - получается новая пара состояний итераторов i1, i2, то есть новое состояние для комбинатора. Если у итератора i2 нет следующего состояния, то комбинатор смотрит, есть ли следующее состояние у итератора i1; если есть, то итератор i1 переводится в следующее состояние, а итератор i2 - в начальное, снова получается новая пара состояний итераторов i1, i2, а значит и новое состояние комбинатора.
Если же следующего состояния нет ни у итератора i1, ни у итератора i2, то это означает, что и комбинатор не имеет следующего состояния. Другой важный пример - это комбинатор системы зависимых итераторов. Пусть нам нужно проитерировать пары букв и цифр, при этом для каждой буквы есть своё множество цифр, с которыми она может быть в паре. Пусть для буквы a - это множество {0, 1}, для буквы b - множество {2, 3, 5}, для буквы c - множество {4}. Заведём итераторы для множеств цифр и букв: итератор i1 для множества {a, b, c}, итераторы i2, i3, i4 - для множеств {0, 1}, {2, 3, 5}, {4} соответственно. Состоянием комбинатора теперь будет пара состояний двух других итераторов: итератора i1 и итератора, соответствующего состоянию итератора i1. Работа комбинатора проиллюстрирована рис. 9. При переходе итератора букв в следующее состояние в зависимости от этого состояния выбирается итератор цифр. При переходе к другой букве итератор цифр будет другим.

Можно определить комбинатор системы зависимых итераторов для итерации кортежей длины n. Точно так же, как было в примере с парами буква-цифра, итератор первого компонента кортежа последовательно проходит все свои состояния. В зависимости от его состояния выбирается итератор второго компонента кортежа, который также проходит все свои состояния (в это время состояние итератора первой компоненты кортежа менять нельзя). В зависимости от состояний итераторов первого и второго компонентов выбирается итератор третьего компонента кортежа и т.д. Итераторы, от которых зависит выбор других итераторов, будем называть осями зависимости. Так, итератор первого компонента кортежа - это первая ось зависимости, итератор второго компонента - это вторая ось зависимости и т.д. В приведенном выше примере одна ось зависимости - итератор букв.

Содержание раздела