CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#сортировка пузырьком. (155083 hits)
#Работа с камерой. (36840 hits)
#Вычисление медианы заданной выборки. (50464 hits)
#Как посчитать одинаковые пары за 1 проход (самая быстрая версия!). (3485 hits)
#Постепенное затемнение. (52276 hits)
#Подключение. (28445 hits)
#Вычисление значения полинома. (63642 hits)
#Синус. (62383 hits)
#Найти максимальную сумму в последовательности. (141613 hits)
#Подсветка синтаксиса. (32470 hits)
#Вставка новой записи в таблицу БД. (37515 hits)
#Рисование прямоугольника. (32317 hits)
#Динамическое формирование выпадающего списка. (53394 hits)
#Рисование линии (по Брезенхэму). (34999 hits)
#Вычисление среднего, среднего отклонения, среднеквадратического отклонения и дисперсии заданной выборки. (47565 hits)
#Замена символа строки. (445230 hits)
#Доступ ко всем полям и методам. (59135 hits)
#Арктангенс. (46817 hits)
#Предварительная загрузка изображений. (48345 hits)
#Сглаживание кривой В-сплайном. (39906 hits)


Главная >> Каталог задач >> Паттерны >> Поведения >> Итератор (Iterator)

Итератор (Iterator)

Aвтор:
Дата:
Просмотров: 326522
реализации(javascript: 1шт...) +добавить

Имя

«Паттерн Iterator»

Итератор – паттерн поведения объектов, предоставляющий последовательный доступ ко всем элементам составного объекта, не раскрывая его внутреннего представления.
Известен также под именем Cursor (курсор).

Условия, Задача, Назначение

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

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

Мотивация

Составной объект, скажем список, должен предоставлять способ доступа к своим элементам, не раскрывая их внутреннюю структуру. Более того, иногда требуется обходить список по-разному, в зависимости от решаемой задачи. Но вряд ли вы захотите засорять интерфейс класса List операциями для различных вариантов обхода, даже если все их можно предвидеть заранее. Кроме того, иногда нужно, чтобы в один и тот же момент было определено несколько активных обходов списка.

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

Например, класс List мог бы предусмотреть класс Listlterator:

Прежде чем создавать экземпляр класса Listlterator, необходимо иметь список, подлежащий обходу. С объектом Listlterator вы можете последовательно посетить все элементы списка. Например, операция CurrentItem возвращает текущий элемент списка, операция First инициализирует текущий элемент первым элементом списка, Next делает текущим следующий элемент, a IsDone проверяет, не оказались ли мы за последним элементом, если да, то обход завершен.
Отделение механизма обхода от объекта List позволяет расширять итераторы, создавать новые, реализующие различные стратегии обхода, не перечисляя их в интерфейсе класса List. Например, FilteringListlterator мог бы предоставлять доступ только к тем элементам, которые удовлетворяют условиям фильтрации (которое предварительно задается на этапе инициализации например).
Заметим: между итератором и списком имеется тесная связь, клиент должен иметь информацию, что он обходит именно список, а не какую-то другую агрегированную структуру. Поэтому клиент привязан к конкретному способу агрегирования. Было бы лучше, если бы мы могли изменять класс агрегата, не трогая код клиента. Это можно сделать, обобщив концепцию итератора и рассмотрев полиморфную итерацию.
Например, предположим, что у нас есть еще класс SkipList, реализующий список. Список с пропусками (skiplist) - это вероятностная структура данных, по характеристикам напоминающая сбалансированное дерево. Нам нужно научиться писать код, способный работать с объектами как класса List, так и класса SkipList.
Определим класс AbstractList, в котором объявлен общий интерфейс для манипулирования списками. Еще нам понадобится абстрактный класс Iterator, определяющий общий интерфейс итерации. Затем мы смогли бы определить конкретные подклассы класса Iterator для различных реализаций списка. В результате механизм итерации оказывается не зависящим от конкретных агрегированных классов.

Остается понять, как создается итератор. Поскольку мы хотим написать код, не зависящий от конкретных подклассов List, то нельзя просто инстанцировать конкретный класс. Вместо этого мы поручим самим объектам-спискам создавать для себя подходящие итераторы, вот почему потребуется операция Createlterator, посредством которой клиенты смогут запрашивать объект-итератор.
CreateIterator - это пример использования паттерна фабричный метод.
В данном случае он служит для того, чтобы клиент мог запросить у объекта-списка подходящий итератор. Применение фабричного метода приводит к появлению двух иерархий классов - одной для списков, другой для итераторов. Фабричный метод CreateIterator «связывает» эти две иерархии.

Признаки применения, использования паттерна Итератор (Iterator)

Используйте паттерн итератор:
  1. Для доступа к содержимому агрегированных объектов без раскрытия их внутреннего представления.
  2. Для поддержки нескольких видов активных обходов одного и того же агрегированного объекта.
  3. Для предоставления единообразного интерфейса с целью обхода различных агрегированных структур (то есть для поддержки полиморфной итерации).

Решение

Участники паттерна Итератор (Iterator)

  1. Iterator – итератор.
    Определяет общий интерфейс для доступа и обхода элементов.
  2. Concretelterator - конкретный итератор.
    Реализует интерфейс класса Iterator.
    Следит (хранит) за текущей позицией при обходе агрегата.
  3. Aggregate – интерфейс фабрике итераторов.
    Определяет интерфейс фабрики создания объектов-итераторов.
  4. ConcreteAggregate – конкретная фабрика итераторов.
    Реализует интерфейс создания итератора и возвращает экземпляр подходящего класса Concretelterator.

Схема использования паттерна Итератор (Iterator)

Клиент, пользуясь интерфейсом Aggregate, получает итератор Concretelterator для обхода определенного класса списков.

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

Вопросы, касающиеся реализации паттерна Итератор (Iterator)

Существует множество вариантов реализации итератора. Ниже перечислены наиболее употребительные. Решение о том, какой способ выбрать, часто зависит от управляющих структур, поддерживаемых языком программирования.
Некоторые языки (Java один из них) даже поддерживают данный паттерн напрямую (реализуя поддержку на уровне ядра языка).
  1. Какой участник управляет итерацией.
    Важнейший вопрос состоит в том, что управляет итерацией: сам итератор или клиент, который им пользуется.
    Если итерацией управляет клиент, то итератор называется внешним, в противном случае - внутренним. Клиенты, применяющие внешний итератор, должны явно запрашивать у итератора следующий элемент, чтобы двигаться дальше по списку (агрегату). Напротив, в случае внутреннего итератора клиент передает итератору некоторую операцию, а итератор уже сам применяет эту операцию к каждому посещенному во время обхода элементу агрегата.
    Внешние итераторы обладают большей гибкостью, чем внутренние. Например, сравнить две коллекции на равенство с помощью внешнего итератора очень легко, а с помощью внутреннего - практически невозможно. Слабые стороны внутренних итераторов наиболее отчетливо проявляются в таких языках, как C++, где нет анонимных функций, замыканий (closure) и продолжений (continuation), как в Java, Javascript или Smalltalk. Но, с другой стороны, внутренние итераторы проще в использовании, поскольку они вместо вас реализуют логику обхода.
  2. Что определяет алгоритм обхода.
    Алгоритм обхода можно определить не только в итераторе. Его может определить сам список (агрегат) и использовать итератор только для хранения состояния итерации (позиция текущего элемента, признак достижения конца). Такого рода итератор мы называем курсором, поскольку он всего лишь указывает на текущую позицию в агрегате. Клиент вызывает операцию Next агрегата, передавая ей курсор в качестве аргумента. Операция же Next изменяет состояние курсора.
    Если за алгоритм обхода отвечает итератор, то для одного и того же списка (агрегата) можно использовать разные алгоритмы итерации, и, кроме того, проще применить один алгоритм к разным агрегатам. С другой стороны, алгоритму обхода может понадобиться доступ к закрытым переменным агрегата. Если это так, то перенос алгоритма в итератор нарушает инкапсуляцию агрегата.
  3. Насколько итератор устойчив.
    Модификация агрегата в то время, как совершается его обход, может оказаться опасной. Если при этом добавляются или удаляются элементы, то не исключено, что некоторый элемент будет посещен дважды или вообще ни разу. Простое решение - скопировать агрегат и обходить копию, но обычно это слишком дорого.
    Устойчивый итератор (robust) гарантирует, что ни вставки, на удаления не помешают обходу, причем достигается это без копирования агрегата. Есть много способов реализации устойчивых итераторов. В большинстве из них итератор регистрируется в агрегате. При вставке или удалении агрегат либо подправляет внутреннее состояние всех созданных им итераторов, либо организует хранение дополнительной внутренней информации так, чтобы обход выполнялся правильно.
    В работе Томаса Кофлера (Thomas Kofler) приводится подробное обсуждение реализации итераторов в каркасе ЕТ++. Роберт Мюррей (Robert Murray) описывает реализацию устойчивых итераторов для класса List из библиотеки USL Standard Components.
  4. Дополнительные операции итератора.
    Минимальный интерфейс класса Iterator может состоять из операций First, Next, IsDone и CurrentItem. Этот интерфейс можно и еще уменьшить, если объединить операции Next, IsDone и Currentltem в одну, которая будет переходить к следующему объекту и возвращать его. Если обход завершен, то эта операция вернет специальное значение (например, 0), обозначающее конец итерации.
    Но могут оказаться полезными и некоторые дополнительные операции. Например, упорядоченные агрегаты могут предоставлять операцию Previous, позиционирующую итератор на предыдущий элемент. Для отсортированных или индексированных коллекций интерес представляет операция SkipTo, которая позиционирует итератор на объект, удовлетворяющий некоторому критерию.
  5. Использование полиморфных итераторов в C++.
    С полиморфными итераторами связаны определенные накладные расходы. Необходимо, чтобы объект-итератор создавался в динамической памяти фабричным методом. Поэтому использовать их стоит только тогда, когда есть необходимость в полиморфизме. В противном случае применяйте конкретные итераторы, которые вполне можно распределять в стеке.
    У полиморфных итераторов есть и еще один недостаток: за их удаление отвечает клиент. Здесь открывается большой простор для ошибок, так как очень легко забыть об освобождении распределенного из кучи объекта-итератора после завершения работы с ним. Особенно велика вероятность этого, если у операции есть несколько точек выхода. А в случае возбуждения исключения память, занимаемая объектом-итератором, вообще никогда не будет освобождена.
    Эту ситуацию помогает исправить паттерн заместитель. Вместо настоящего итератора мы используем его заместителя, память для которого выделена в стеке. Заместитель уничтожает итератор в своем деструкторе. Поэтому, как только заместитель выходит из области действия, вместе с ним уничтожается и настоящий итератор. Заместитель гарантирует выполнение надлежащей очистки даже при возникновении исключений. Это пример применения хорошо известной в C++ техники, которая называется «выделение ресурса - это инициализация».
  6. Внутренние, скрытые итераторы.
    Итератор можно рассматривать как расширение создавший его агрегат. Итератор и агрегат тесно связаны. В C++ такое отношение можно выразить, сделав итератор другом своего агрегата. Тогда не нужно определять в агрегате операции, единственная цель которых - позволить итераторам эффективно выполнить обход, потребуются только создать единственный метод, возвращающий этот самый объект итератора. Однако наличие такого привилегированного доступа может затруднить определение новых способов обхода, так как потребуется изменить интерфейс агрегата, добавив в него нового друга. Для того чтобы решить эту проблему, класс Iterator может включать защищенные операции для доступа к важным, но не являющимся открытыми членам агрегата. Подклассы класса Iterator (и только его подклассы) могут воспользоваться этими защищенными операциями для получения привилегированного доступа к агрегату.
  7. Итераторы для составных объектов.
    Реализовать внешние агрегаты для рекурсивно агрегированных структур (таких, например, которые возникают в результате применения паттерна компоновщик) может оказаться затруднительно, поскольку описание положения в структуре иногда охватывает несколько уровней вложенности. Поэтому, чтобы отследить позицию текущего объекта, внешний итератор должен хранить путь через составной объект Composite. Иногда проще воспользоваться внутренним итератором.
    Он может запомнить текущую позицию, рекурсивно вызывая себя самого, так что путь будет неявно храниться в стеке вызовов.
    Если узлы составного объекта Composite имеют интерфейс для перемещения от узла к его братьям, родителям и потомкам, то лучшее решение дает итератор курсорного типа. Курсору нужно следить только за текущим узлом, а для обхода составного объекта он может положиться на интерфейс этого узла.
    Составные объекты часто нужно обходить несколькими способами. Самые распространенные - это обход в прямом, обратном и внутреннем порядке, а также обход в ширину. Каждый вид обхода можно поддержать отдельным итератором.
  8. Пустые итераторы.
    Пустой итератор NullIterator - это вырожденный итератор, полезный при обработке граничных условий. По определению, NullIterator всегда считает, что обход завершен, то есть его операция IsDone неизменно возвращает истину. Применение пустого итератора может упростить обход древовидных структур (например, объектов Composite). В каждой точке обхода мы только лишь запрашиваем у текущего элемента итератор для его потомков, не проверяя есть ли у него потомки. Элементы-агрегаты, как обычно, возвращают конкретный итератор. Но листовые элементы возвращают экземпляр NullIterator. Это позволяет реализовать обход всей структуры единообразно.

Результаты

Правильно реализовав паттерн-итератор, мы достигнем следующего:
  1. Поддержка различных видов обхода агрегата.
    Сложные агрегаты можно обходить по-разному. Например, для генерации кода и семантических проверок нужно обходить деревья синтаксического разбора. Генератор кода может обходить дерево во внутреннем или прямом порядке. Итераторы упрощают изменение алгоритма обхода - достаточно просто заменить один экземпляр итератора другим. Для поддержки новых видов обхода можно определить и подклассы класса Iterator.
  2. Итераторы упрощают интерфейс класса Aggregate.
    Наличие интерфейса для обхода в классе Iterator делает излишним дублирование этого интерфейса для каждого класса вида Aggregate. Тем самым интерфейс агрегата упрощается.
  3. Одновременно для данного агрегата может быть активно несколько обходов. Итератор следит за инкапсулированным в нем самом состоянием обхода. Поэтому одновременно разрешается осуществлять несколько обходов агрегата.

Пример

Для демонстрации итератора в языке Java достаточно просто посмотреть на Коллекции, а именно, на единый интерфейс Iterator, на реализацию абстрактного класса AbstractList, его внутреннего класса итератора, возвращаемого операцией iterator(). Каждая коллекция возвращает свой внутренний объект, реализующий интерфейс Iterator, поэтому проблема обхода любых списков(List), множеств (Set), хеш-таблиц (Map) – решается очень просто и совершенно независимо от фактического типа коллекции, т.к. в конце концов мы в любом случае имеем дело с общим интерфейсом Iterator, имеющим всего 3 метода: hasNext(), next() и remove().
Для более наглядной демонстрации рассмотрим задачу создания итераторов для обхода файлов по строкам. Чтобы пройтись по всем срокам файла приходится писать довольно однообразный и некомпактный код создания соответствующих InputStream-ов, их агрегации, манипулирования несколькими исключениями и т.д. Было бы разумно реализовать специальный список, строящийся по строкам конкретного файла и предоставляющего тот же единый интерфейс Iterator обхода.
Наш список (FileLineList) будет реализовывать интерфейс List, являться списком из строк и для простоты будет возможность лишь читать этот список, без возможности добавления, удаления его элементов (строк того же файла). На вход будет подаваться лишь путь к файлу в файловой системе.
Для реализации своего списка в языке Java пользуются средствами фреймворка коллекций: нужно лишь унаследоваться от абстрактной реализации AbstractList и реализовать всего 2 его ключевых метода: get(index) и size() – которые используются затем при реализации по-умалчанию многих других операций интерфейса List: FileLineList.
Как видно, реализация получается довольно незамысловатой: при создании списка мы делаем проверку на существование файла и возможность чтения, в методе size() – открываем, читаем каждую строку и считаем общее их количество и закрываем файл, в get(index) – каждый раз открываем, досчитываем до нужной строки, выдаем ее и тут же закрываем. Самое интересное заключается в том – что этого уже достаточно, наш список работает, из него можно получить любую строку файла и уже даже пройтись получив реализацию итератора по-умалчанию возвращаемого методом iterator():Client0.
Реализация метода iterator() по-умалчанию содержится в абстрактном классе AbstactCollection, от которого наследуется AbstractList. И по-умалчанию создается итератор, который использует метод списка get(index), а именно вызывает его при каждом обращении к Iterator.next(). Поскольку в нашем случае каждый раз при этом происходит открытие файла, чтение всех его строк до достижения нужного индекса, закрытие файла – то можно сказать, такая реализация является очень неоптимальной и случае большого файла – каждый вызов next() будет выполняться довольно продолжительное время.
Выход из этого, да и вообще можно сказать обычная практика – реализовать свой собственный итератор в виде внутреннего класса списка, а в операции iterator() – его возвращать: FileLineListOpt.
Как видно, для большей простоты мы просто унаследовались от FileLineList, чтобы не реализовывать заново операции get(index) и next(). Теперь возвращается итератор, объект класса FileLineIterator, который открывает файл единственный раз при своем создании, и далее при выполнении каждого next() просто читается очередная строка, после чтения последней строки – файл закрывается. Оптимизация – на лицо: теперь при итерации по всему списку мы лишь один раз открываем файл и последовательно читаем из него, а не каждый раз при обращении к следующему элементу.
Далее важно отметить, что при таком принципе реализации коллекций в языке Java – при работе со списками мы автоматически становимся независимыми ни от конкретных типов коллекций, списков и т.д., ни более того – от конкретных специфических реализаций итераторов. Фактически клиентский код может иметь дело с любым классом списка, а также получать любой вид итератора (по-умалчанию, оптимизированный, специфический и т.д.) – код работы с этим списком и его обхода не изменится: Client.
 
- какой бы список не возвращался методом GetList, а также, какой бы итератор этот список не предоставлял – код метода main() – не меняется. В данном случае, если аргумент командой строки не задан, либо “0” – то будет произведен обход списка FileLineList с помощью итератора по-умалчанию, который реализуется в AbstractCollection, если же аргумент = “1” – то мы проитерируем список FileLineListOpt, с помощью специального итератора FileListIterator.
 
На последок, можно привести пример внутреннего итератора, который упоминался ранее. Допустим для всех наших списков в нашей программе нужно лишь выполнять некоторую единую операцию для каждого элемента любого списка. Таким образом создается специальный класс итератора (неудовлетворяющий интерфейсу Iterator), ему передается на вход список и при запуске на выполнении этот итератор, получая внутренний итератор списка – производит обход и для каждого элемента выполняет требуемую итерацию.
Нерешенным остается вопрос о том, как параметризовать итератор той операцией, которую мы хотим применить к каждому элементу. Существует, по крайней мере, два варианта: передать ссылку на специальный объект обработчик (реализующий некоторый определенный интерфейс обработчика) или породить подклассы. В первом случае итератор вызывает переданную ему операцию в каждой точке обхода. Во втором случае итератор вызывает операцию, которая замещена в подклассе и обеспечивает нужное поведение.
Ни один из вариантов не идеален. Часто во время обхода нужно аккумулировать некоторую информацию, а конкретные объекты обработчики для этого плохо подходят — пришлось бы использовать статические переменные для запоминания в них состояния. Подкласс же предоставляет удобное место для хранения аккумулированного состояния - переменную экземпляра. Но создавать подкласс для каждого вида обхода слишком трудоемко.
Вот набросок реализации второго варианта с использованием подклассов.
Назовем внутренний итератор BypassIterator: BypassIterator
 
BypassIterator принимает экземпляр List в качестве параметра. Внутри себя он использует внешний итератор Iterator для выполнения обхода. Операция Bypass() начинает обход и вызывает для каждого элемента операцию Processltem(). Внутренний итератор может закончить обход, вернув false из ProcessItem(). Bypass() сообщает о преждевременном завершении обхода.
Воспользуемся итератором BypassIterator для очищения от пробелов каждого элемента списка. С этой целью надо породить подкласс от BypassIterator и переопределить в нем операцию ProcessItem. Подсчитывать число «очищенных» элементов будем в поле экземпляра count: SpaceKillerBypassIterator.
 
В результате всего этого в коде клиента ну будет цикла итерации: Client2.
 
Всю логику обхода можно использовать повторно. В этом и состоит основное преимущество внутреннего итератора. Работы, правда, немного больше, чем для внешнего итератора, так как нужно определять новый класс. Главное то, что внутренние итераторы могут прозрачно выполнять любые виды обхода элементов списка в соответствии с получаемым видом внешнего итератора. Т.е. здесь мы также можем и прозрачно «подменить» любой другой способ обхода (например, обходить элементы «через один», либо только по некоторому условию), незаметно ни для BypassIterator-а, ни для клиентского кода (Client2), его использующего: для этого нужно лишь, чтобы передаваемый во внутренний итератор (SpaceKillerBypassIterator) список (spaces) реализовывал другой тип внешнего итератора (возвращал его в своей операции iterator)!

Известные применения паттерна Итератор (Iterator)

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

Вот пример из библиотеки компонентов Грейди Буча, популярной библиотеки, поддерживающей классы коллекций. В ней имеется реализация очереди фиксированной (ограниченной) и динамически растущей длины (неограниченной). Интерфейс очереди определен в абстрактном классе Queue. Для поддержки полиморфной итерации по очередям с разной реализацией итератор написан с использованием интерфейса абстрактного класса Queue. Преимущество такого подхода очевидно - отсутствует необходимость в фабричном методе, который запрашивал бы у очереди соответствующий ей итератор. Однако, чтобы итератор можно было реализовать эффективно, интерфейс абстрактного класса Queue должен быть мощным.

В языке Smalltalk необязательно определять итераторы так явно. В стандартных классах коллекций (Bag, Set, Dictionary, OrderedCollection, String и т.д.) определен метод do:, выполняющий функции внутреннего итератора, который принимает блок (то есть замыкание). Каждый элемент коллекции привязывается к локальной переменной в блоке, а затем блок выполняется.Smalltalk также включает набор классов Stream, которые поддерживают похожий на итератор интерфейс. ReadStream - это, по существу, класс Iterator и внешний итератор для всех последовательных коллекций. Для непоследовательных коллекций типа Set и Dictionary нет стандартных итераторов.

Полиморфные итераторы и выполняющие очистку заместители находятся в контейнерных классах ЕТ++. Курсороподобные итераторы используются в классах каркаса графических редакторов Unidraw.

В системе ObjectWindows 2.0 имеется иерархия классов итераторов для контейнеров. Контейнеры разных типов можно обходить одним и тем же способом. Синтаксис итераторов в ObjectWindows основан на перегрузке постфиксного оператора инкремента ++ для перехода к следующему элементу.

Родственные паттерны

Компоновщик: итераторы довольно часто применяются для обхода рекурсивных структур, создаваемых компоновщиком.

Фабричный метод: полиморфные итераторы поручают фабричным методам инстанцировать подходящие для клиента подклассы класса Iterator.

Итератор может использовать хранитель для сохранения состояния итерации и при этом содержит его внутри себя.

Реализации:

java(7), javascript(1)   +добавить

1) Итератор на javascript, прототипнаяверсия на javascript, code #557[автор:-]