Три примера использования наборов[]
В этой главе дано три примера описаний классов. Каждый пример использует объекты числа и набора доступные в системе Смолток, каждый пример показывает способ добавления функциональности в систему.
Карточную игру можно создать в терминах случайного выбора из набора представляющего колоду карт. Класс пример Игральная карта представляет карту с какой-то мастью и достоинством. Колода карт представляет набор таких карт, Карты на руках это набор Игральных карт некоторого игрока. Выбор карты из Колоды карты или из Карт на руках производится классами которы представляют выбор и замену, Пространство выбора с заменой, и без замены, Пространство выбора без замены. Хорошо известная задача программирования, задача пьяного таракана, включающая подсчёт количества шагов необходимых таракану случайно ползающему по всем плиткам в комнате. Решение данное в этой главе представляет каждую плитку как экземпляр класса Плитка и таракана как экземпляр класса Пьяный таракан. Третий пример из данной главы это дерево подобная структура данный представляемая классами Дерево и Узел, Узел слово показывает способ которым дерево можно использовать для хранения цепей представляющий слова.
Случайный выбор и игральные карты[]
Класс системы Смолток Случайное число, который работает как генератор случайно выбранного числа между 0 и 1, был описан в восьмой главе. Случайная величина предоставляет основу для выбора из множества возможных значений, такое множество называется пространством выборок. Простейшую форма дискретного случайного выбора можно получить используя случайное число для выбора элемента из последовательного набора. Если выбранный элемент остаётся в наборе, то выбор производится "с заменой" - то есть каждый элемент набора доступен при каждом выборе. В противоположность этому, выбираемый элемент может удаляться из набора при каждом выборе, это называется выбором "без замены".
Класс Пространство выбора с заменой предоставляет случайный выбор с заменой из последовательного набора элементов. Экземпляр класса создаётся заданием набора элементов из которого буду случайно выбираться элементы. Это сообщение инициализатор имеет селектор данные:. Выбор из набора осуществляется при помощи сообщения экземпляру с селектором следующий. Или можно получить целое количество выборок послав сообщение следующий: целое.
Например, допустим что нужно выбрать элементы из Ряда Символов представляющих имена людей.
Каждый раз когда нужно выбрать имя из Ряда, выполняется предложение.
Ответ это один из Символов: sally, sam, sue, sarah или steve. Если выполнить предложение:
будет выбран Упорядоченный набор из пяти элементов. Экземпляры Пространства выбора с заменой отвечают на сообщения пустой и размер чтобы проверить есть ли элементы в пространстве выбора и сколько их. Поэтому ответ на
это ложь, и ответом на
будет 5.
Далее дана реализация класса Пространство выбора с заменой. Для пояснения назначения метода в каждом методе дан коментарий, коментарии записываются в двойных кавычках.
| имя класса Пространство выбора с заменой |
| суперкласс Объект |
| имена переменных экземпляра данные случ |
| методы класса |
| создание экземпляра |
| данные: набор последовательность "Создатёт экземпляр Пространства выбора с заменой такое что аргумент, набор последовательность, является пространством выбора." ↑ сам новый присвоить данные: набор последовательность. |
| методы экземпляра |
| доступ |
| следующий "Следующий элемент выбирается случайным образом из набора данные. Номер в наборе данные определяется при помощи случайного числа между 0 и 1, и его преобразовании к диапазону набора данные." сам пустой истина: [ сам ошибка: 'В пространтсве выбора нет значений'. ]. ↑ данные от: (случ следующий * данные размер) усечённый + 1. |
| проверки |
| пустой "Отвечает остались ли элементы для выбора." ↑ сам размер = 0. размер |
| собственные |
| присвоить данные: набор последовательность "Аргумент, набор последовательность, это пространство выбора. Создаёт генератор случайных чисел для выбора из пространства." данные ← набор последовательность. случ ← Случайное число новый. |
Описание класса указывает что у каждого экземпляра есть две переменные с именами данные и случ. Метод инициализации, данные:, посылает новому экземпляру сообщение присвоить данные: в котором данные связываются с Набором последовательностью (значением аргумента инициализирующего сообщения) а случ связывается с новым экземпляром класса Случайное число.
Пространство выбора с заменой не является подклассом Набора т.к. он реализует только малую часть сообщений на которые может отвечать Набор. В ответ на сообщения следующий и размер Пространство выбора с заменой посылает сообщения от: и размер переменной экземпляра данные. Это означает что любой набор отвечающий на сообщения от: и размер может быть использован в качестве данных из которые выбираются элементы. Все Наборы последовательности отвечают на эти два сообщения. Поэтому, например, в дополнение к Рядам как было показано ранее, данные могут быть Интервалом. Допустим нужно смоделировать the throw or die. Значит элементы пространства выбора это положительные число от 1 до 6.
A throw of the die is obtained by evaluating
Ответ этого сообщения это одно и целых: 1, 2, 3, 4, 5 или 6.
Можно выбирать карту из колоды таким же способом если набор связанный с экземпляров Пространства выбора с заменой содержит элементы представляющие игральные карты. Однако, чтобы играть в карточную игру, нужно работать с картами которые вынимаются из колоды и отдаются игроку. Поэтому здесь нужно использовать случайный выбор без замены.
Чтобы реализовать выбор без замены, нужно определить ответ на сообщение следующий с удалением выбранного элемента. Т.к. не все Наборы последовательности отвечают на сообщение удалить:, (например, Интервал не отвечает на это сообщение) нужно проверять аргумент в инициализирующем сообщении или преобразовывать аргумент к допустимому виду набора. Т.к. все Упорядоченные набора отвечают на эти два сообщения, и т.к. все наборы можно преобразовать в Упорядоченный набор, то можно использовать такое преобразование. Чтобы выполнить преобразование метод связанный с присвоить данные: посылает своему аргументу сообщение как упорядоченный набор.
Класс Пространство выбора без замены определено как подкласс Пространства выбора с заменой. Методы связанные с сообщениями следующий и присвоить данные переопределены, остальные сообщения наследуются без изменений.
| имя класса Пространство выбора без замены |
| имя суперкласса Пространство выбора с заменой |
| методы экземпляра |
| доступ |
| следующий ↑ данные удалить: супер следующий. |
| собственные |
| присвоить данные: набор данные ← набор как упорядоченный набор. случ ← Случайное число новый. |
Заметьте что метод для селектора следующий зависит от метода реализованного в суперклассе (супер следующий). Метод суперкласса проверяет не пусто ли пространство выбора и затем случайно выбирает элемент. После определения элемента, метод подкласса удаляет элемент из данных. Результат сообщения удалить: это аргумент, поэтому результат сообщения следующий посланного Пространству выбора без замены это выбранный элемент.
Давайте напишем простую карточную игру. Допустим что пространство выбора для карточной игры состоит из экземпляров класса Игральная карта, и каждая карта знает свою масть и достоинство. Экземпляр Игральной карты создаётся при помощи сообщения масть:достоинство:, определяющего с помощью двух аргументов масть (черви, буби, крести, пики) и достоинство (1, 2, ..., 13). Игральная карта отвечает на сообщения масть и достоинство.
| имя класса Игральная карта |
| имя суперкласса Объект |
| имена переменных экземпляра масть достоинство |
| методы класса |
| создание экземпляра |
| масть: символ достоинство: целое "Создаёт экземпляр Игральной карты чьи масть это аргумент, символ, и достоинство это аргумент, целое." ↑ сам новый присвоить масть: символ достоинство: целое. |
| методы экземпляра |
| доступ |
| масть "Возвращает масть получателя." ↑ масть. достоинство |
| собственные |
| присвоить масть: символ достоинство: целое масть ← символ. достоинство ← целое. |
Колода карт создаётся следующим предложением.
#( #крести #пики #буби #черви )
делать: [
:каждая масть |
1
до: 13
делать: [
:н |
колода карт
добавить: (Игральная карта масть: каждая масть достоинство: н). ]. ].
Первое предложение создаёт Упорядоченный набор из 52-х элементов. Второе предложение это перечисление достоинство от 1 до 13 для каждой из четырёх мастей: крести, пики, буби, черви. Каждый элемент Упорядоченного набора это Игральная карта с различным достоинством и мастью.
Можно получить возможность выбирать карты из колоды создав экземпляр Пространства выбора без замены с колодой карты в качестве набора из которого производится выбор.
Чтобы выбрать карту нужно выполнить предложение:
Ответом этого сообщения будит экземпляра класса Игральная карта.
Другой способ представления колоды игральных карт показан в описании класса-примера Колода карт. Основная идея заключаится в хранение линейного списка карт; следующий означает первую карту в списке. Карту можно вернуть обратно в колоду поместив её в конец или вставив её в некоторую случайную позицию. Линейный список делается случайным при помощи тасования, т.е. при помощи случайного упорядочивания карт.
В реализации представленной ниже для Колоды карты, начальный вариант колоды карты запоминается в переменной класса. Она создаётся при помощи предложений данных выше. Копия этой переменной становится переменной экземпляра при создании ного экземпляра; она тасуется перед взятием карты. Каждое следующее тасование колоды использует текущее состояние переменной экземпляра, а не переменной класса. Процесс тасования, конечно, достаточно однообразен т.к. он основан на использовании экземпляра Пространства выбора без замены. Моделирование реалного тасования включает разделение колоды примерно пополам и затем перемешивание двух частей. Перемешивание включает выбор последовательностей из одной части и затем из другой части. Всё же, такое моделирование может быть более случайно чем тасование человеком, тасование человеком может быть предсказуемым и наблюдаемым.
Сообщения к Колоде карт с селекторами: возвратить:, следующий и тасовать полезны при создании карточной игры.
| имя класса Колода карт |
| имя суперкласс Объект |
| имена переменных экземпляра карты |
| имена переменных класса Начальная колода карт |
| методы класса |
| инициализация класса |
| инициализировать "Создаёт колоду из 52 игральных карт." Начальная колода карт ← Упорядоченный набор новый: 52. #( #буби #пики #крести #черви ) делать: [ :масть | 1 до: 13 делать: [ :н | Начальная колода карт добавить: (Игральная карта масть: масть достоинство: н). ]. ]. |
| создание экземпляров |
| новый "Создаёт экземпляр Колоды карт с начальной колодой из 52-х игральных карт." ↑ супер новый карты: Начальная колода карт копия. |
| методы экземпляра |
| доступ |
| следующий "Выбирает слудеющую карту." ↑ карты удалить первый. вернуть: карта тасовать |
| проверки |
| пустой "Отвечаеть есть ли ещё карты в колоде." ↑ карты пустой. |
| собственные |
| карты: набор карты ← набор. |
Класс Колода карт нужно инициализировать выполнив предложение
В реализации Колоды карт, карты это переменная экземпляра and is therefore the deck of cards used in playing a game. Чтобы играть в карты создаётся экземпляр Колоды карт
и затем каждая карта вынимается при помощи сообщения следующий посылаемого данному новому экземпляру. Когда карта кладётся обратно в колоду, то Колоде карт посылается сообщение вернуть:. Тасование всегда перемешивает карты находящиеся в колоде в данный момент. Если вся колода карт будет использовать после завершение игры, то все карты взятые из колоды должны быть возвращены в колоду.
Обратите внимание на реализацию сообщения тасовать. Пространство выбора без замены, выбор, создаётся для копии текущей колоды карт. Новый Упорядоченный набор, временная колода, создаётся для хранения случайно выбранных карт из это пространства выбора. Выбор из пространства производится для каждой возможной карты; каждая выбранная карта добавляется к временной колоде. Когда все доступные карты перемещены во временную колоду, она присваивается текущей колоде.
Допустим создаётся простая карточная игра с тремя или четырьмя игроками и раздающим. Раздающий раздаёт карты каждому игроку. Если хотябы один из игроков имеет от 18 до 21 очка, игра заканчивается с разделением "приза" между всеми такими игроками. Очки считаются суммирование достоинства карт. Игрок у которого больше чем 21 очко не получает новых карт.
Каждый игрок представляется при помощи экземпляра класса Карты на руках. Карты на руках знает карты которые он держит и общее количество очков для них (отвечает на сообщение очки).
| имя класса Карты на руках |
| суперкласс Объект |
| имена переменных экземпляра карты |
| методы класса |
| создание экземпляра |
| новый ↑ супер новый присвоить карты. |
| методы экземпляра |
| доступ |
| взять: карта "Аргумент, карта, добавляется к получателю." карты добавить: карта. вернуть все карты в: колода карт |
| запросы |
| очки "Возвращает сумму достоинств карт получателя." ↑ карты ввести: 0 в: [ :значение :след карта | значение + след карта достоинство. ]. |
| собственные |
| присвоить карты карты ← Упорядоченный набор новый. |
Создадим Набор из четырёх игроков. Каждый игрок это экземпляр Карт на руках. Карты раздающего это игральные карты. Раздающий (здесь, программист) начинает с тасования колоды; ещё нет победителя. Может быть больше одного победителя; победители будут перечисляться в Наборе, победители.
4 раз повторить: [ игроки добавить: Карты на руках новый. ].
игральные карты ← Колода карт новый.
игральные карты тасовать.
До тех пор пока нет победителя, каждый игрок у которого меньше чем 21 очко получает следующую карти из колоды карт. Перед раздачей карт всем подходящим игрокам, раздающий проверяет есть ли победители проверяя количество очков у каждого игрока.
победители ← игроки выбрать: [ :каждый | каждый очки между: 18 и: 21. ].
победители пустой и: [ игральные карты пустой не. ]. ]
пока истина: [
игроки
делать: [
:каждый |
каждый очки < 21
истина: [ каждый взять: колода карт следующий. ]. ]. ].
Условие продолжения игры это блок с двумя предложениями. Первое находит победителей, если они есть. Второе проверяет если если нету победителей (победители пустой) и, если их нет, есть ли ещё карты для раздачи (игральные карты пустой не). Если победителей нету и есть карты, то игра продолжается. Игра состоит из перебора игроков; каждый игрок получает карту (каждый взять: игральные карты следующий) если только количество очков меньше чем 21 (каждый очки < 21). Чтобы сыграть ещё раз, все карты нужно вернуть в колоду, которая после этого тасуется.
игральные карты тасовать.
Игроки и раздающий готовы к новой игре.
Задача пьяного таракана[]
Можно использовать классы наборов для решения хорошо известной задачи программирования. Задача заключается в измерении времени требуемом пьяному таракану на посещение всех квадратных плиток на прямоугольном полу шириной Н и длиной М. Немного идеализируем задачу: на текущем шаге таракан с одинаковой вероятностью переходит на одну из девяти плиток, т.е. на плитку на которой он находился до шага и плитки вокруг неё. Конечно движения таракана будут ограничены если таракан попытается выйти из комнаты. Задача сводится к подсчёту шагов требуемых таракану чтобы пройти по каждой плитке хотя бы по разу.
Один из прямых алгоритмов решения этой задачи начать с пустого Множества и счётчика установленного в ноль. После каждого шага, ко множеству добавляется плитка на которую перешёл таракан и увеличивается счётчик количества шагов. Т.к. в Множестве не допускается дублирование элементов алгоритм заканчивает работу когда число элементов множества достигнет значения Н*М. При этом ответом будет значение счётчика.
Этот метод решает простейший вариант задачи, если дополнительно к этому нужно узнать некоторую дополнительную информацию, такую как - сколько раз была посещена каждая плитка. Чтобы запомнить эту информацию, можно использовать экземпляр класса Мешок. Размер мешка это общее количество шагов совершённых тараканом, размер мешка после преобразования его во множество это общее количество плиток посещённых тараканом. Когда это число достигает значения Н*М, решение задачи завершено. Количество вхождений каждой плитки в мешок это число посешений тараканом каждой плитки.
Каждуя плитку на полу можно пометить в соответствии с её рядом и столбцом. Объекты представляющие плитки будут экземплярами класса Плитка. Реализация класса Плитка:
| имя класса Плитка |
| суперкласс Объект |
| имена переменных экземпляра положение область пола |
| методы экземпляра |
| доступ |
| положение "Возвращает положение получателя на полу." ↑ положение. положение: точка область пола: прямоугольник |
| перемещение |
| ближайший к: точка дельта "Создаёт и возвращает новую Плитку находящуюся в положении получателя изменённом на икс и игрек аргумента, точка дельта. Новая плитка остаётся в пределах границ области пола." | новая плитка | новая плитка ← Плитка новый область пола: область пола. новая плитка положение: ((положение + точка дельта макс: область пола начало) мин: область пола угол). ↑ новая плитка. |
| сравнение |
| = плитка "Отвечает равен ли получатель аргументу, плитка." ↑ (плитка это разновидность: Плитка) и: [ положение = плитка положение. ]. хэш |
Плитка ссылается на свой ряд и столбец, каждый из которых должен быть больше либо равен 1 и не больше ширины и высоты пола. Поэтому в дополнение положению плитка должна помнить область пола в которой она может быть помещена. Плитке можно послать сообщение ближайший к: точка чтобы определить плитку наиболее близко лежащую к этой точке. Эта новая плитка должна находится в пределах области пола.
Способ которым будет моделироваться движение таракана это выбор направления в терминах изменения координат таракана икс и игрек. Для данного положения таракана (плитка икс, игрек) есть 9 плиток на которые насекомое может переползти если плитка не находится у границы. Возможные изменения координат будут храниться в Упорядоченном наборе который является данными для случайного выбора. Упорядоченный набор будет содержать в качестве элементов Точки, точки это векторы направления представляющие все возможные комбинации движений. Этот набор создаётся предложением:
(-1 до: 1)
делать: [
:икс |
(-1 до: 1) делать: [ :игрек | Направления добавить: икс @ игрек. ]. ].
Поэтому Направления это набор с элементами:
-1@-1, -1@0, -1@1, 0@-1, 0@0, 0@1, 1@-1, 1@0, 1@1
Как части задачи пьяного таракана, нужно будет генерировать случайные числа для выбора элемента из Упорядоченного набора возможных движений. Как альтернативный вариант прямого использования генератора случайных числе, можно использовать предыдущий пример Пространство выбора с заменой и Направления как пространство выбора.
Допустим таракан начинает двигаться с плитки с координатами 1 @ 1. Каждый раз таракан когда таракан делает шаг выбирается элемент из набора Направления. Этот элемент замет передаётся в качестве аргумента сообщения плитке, ближайший к:. Дальше предполагается что Случ это экземпляр класса Случайное число.
ближайший к: (Направления от: (Случ следующий * Направления размер) усечённый + 1).
Плитка результат это место где находится таракан.
Каждая плитка положение запоминается чтобы иметь информацию о то посещены ли все плитки и сколько на это потребовалось шагов. Если помещать каждую плитку в Мешок, то дубликаты будут указывать количество посещений каждого положений. Поэтому на каждом шаге создаётся копия плитки с предыдущего шага. Эта новая плитка изменяется в соответствии со случайно выбранным направлением и она добавляется в Мешок. Когда количество уникальных элементов в Мешке достигает общего количества плиток, решение задачи завершается.
В классе Пьяный таракан нужно только два сообщения. Одно сообщение это команда двигаться по заданной области до тех пор пока не будут посещены все плитки. Это сообщение ходить по:начиная с:. Второе сообщение это запрос о общем количестве шагов выполненных тараканом, это сообщение количество шагов. Также можно запросить количество посещений конкретной плитки послав Пьяному таракану сообщение количество посещений:. Набор векторов направлений (как было описано выше) создаётся как переменная класса Пьяного таракана, генератор случайных чисел Случ также является переменной класса Пьяного таракана.
| имя класса Пьяный таракан |
| суперкласс Объект |
| имена переменных экземпляра текущая плитка посещённые плитки |
| имена переменных класса Направления Случ |
| методы класса |
| инициализация класса |
| инициализировать "Создаёт набор векторов направлений и генератор случайных чисел." Направления ← Упорядоченный набор новый: 9. (-1 до: 1) делать: [ :икс | (-1 до: 1) делать: [ :игрек | Направления добавить: икс @ игрек. ]. ]. Случ ← Случайное число новый. |
| создание экземпляров |
| новый ↑ супер новый присвоить переменные. |
| методы экземпляра |
| моделирование |
| ходить по: прямоугольник начиная с: точка | количество плиток | посещённые плитки ← Мешок новый. текущая плитка положение: точка. текущая плитка область пола: прямоугольник. количество плиток ← прямоугольник ширина + 1 * (прямоугольник высота + 1). посещённые плитки добавить: текущая плитка. [ посещённые плитки как множество размер < количество плиток. ] пока истина: [ текущая плитка ← текущая плитка ближайший к: (Направления от: (Случ следующий * Направления размер) усечённый + 1). посещённые плитки добавить: текущая плитка. ]. |
| данные |
| количество шагов ↑ посещённые плитки размер. количество посещений: плитка |
| собственные |
| присвоить переменные текущая плитка ← Плитка новый. посещённые плитки ← Мешок новый. |
Сейчас можно послать следующие сообщения чтобы поэкспериментировать с пьяным тараканом. Инициализируем класс и создадим экземпляр.
таракан ← Пьяный таракан новый.
Получение результатов 10-ти экспериментов с комнатой 5 на 5.
10
раз повторить: [
таракан ходить по: (1 @ 1 угол: 5 @ 5) начиная с: 1 @ 1.
результаты добавить: таракан количество шагов. ].
Среднее этих 10-ти значений это среднее значение шагов требуемых пьяному таракану на решение задачи.
Заметьте что в реализации сообщения Пьяного таракана ходить по:начиная с: условие завершения это достижние количества элементов в множестве преобразованном из мешка величины Н*М. Больее быстрый способ проверить это условие - добавить сообщение уникальных элементов в класс Мешок чтобы не требовалось производить преобразования во Множество на каждой итерации.
(Для тех читателей которые хотят попробовать это добавление, метод которы нужно добавить в класс Мешок:
↑ содержимое размер.
Затем сообщение ходить по:начиная с: можно изменить так чтобы условие завершения было таким: посещённые плитки уникальных элементов < количество плиток.)
Обход бинарного дерева[]
Дерево это важная нелинейная структура данных которая полезна в компьютерных алгоритмах. Древовидная структура это такая структура в которой отношения между элементами это ветви. Есть один элемента называемый корнем дерева. Если существует только один элемент, то он является корнем. Если есть дополнительные элементы, то они разделяются на непересекающиеся поддеревья. Бинарное дерево это либо только корень, корень и одно бинарное поддерево, или корень с двумя бинарными поддеревьями. Полное описание древовидных структур есть в первом томе Искусства программирования Кнута. Здесь предполагается что читатель знаком с идеей деревьев поэтому здесь показывается как определить эту структуру данных как класс системы Смолток.
Мы определим класс Дерево способом подобным определению класса Связанный список. Элементами Дерева будут Узлы которые подобна Связям Связанного списка могут соединяться с другими элементами. Дерево ссылается только на корень.
Узел представляется как объект Смолтока с двумя переменными экземпляра, одна ссылается на левый узел а вторая на правый узел. Выбран симметричный порядок обхода дерева. Это значит что при переборе узлов сначала просматривается левое поддерево, вторым корень, и третьим правое поддерево. Если узел не имеет поддеревьев, то он называется листок. По определению размер узла это 1 плюс размер его поддеревьев, если они есть. Поэтому лист это узел размера 1, и узел с двумя листами имеет размер 3. Размер дерева это размер его корня. Это определение размера соответствует общему определению размера для наборов.
Сообщения Узла дают доступ к левому узле, правому узлу, и к последнему узлу. Также возможно удалить подузел (удалить:если нету:) и корень (остаток).
| имя класса Узел |
| суперкласс Объект |
| имена переменных экземпляра левый узел правый узел |
| методы класса |
| создание экземпляра |
| левый: лев узел правый: прав узел "Создаёт экземпляр Узла с аргументами л узел и п узел как левым и правым подузлом соответственно." | новый узел | новый узел ← сам новый. новый узел левый: лев узел. новый узел правый: прав узел. ↑ новый узел. |
| методы экземпляра |
| проверки |
| это лист "Отвечает является ли получатель листом, т.е. отсутствуют ли у узла подузлы." ↑ левый узел это пусто & правый узел это пусто. |
| доступ |
| левый ↑ левый узел. |
| левый: узел левый узел ← узел. |
| правый ↑ правый узел. |
| правый: узел правый узел ← узел. |
| размер ↑ 1 + (левый узел это пусто истина: [ 0. ] ложь: [ левый узел размер. ]) + (правый узел это пусто истина: [ 0. ] ложь: [ правый узел размер. ]). |
| последний | узел | узел ← сам. [ узел правый это пусто. ] пока ложь: [ узел ← узел правый. ]. ↑ узел. |
| удаление |
| удалить: подузел если нету: блок исключение "Предполагается что корень, сам, нельзя удалить." сам это лист истина: [ ↑ блок исключение значение. ]. левый узел = подузел истина: [ левый узел ← левый узел остаток. ↑ подузел. ]. правый узел = подузел истина: [ правый узел ← правый узел остаток. ↑ подузел. ]. левый узел это пусто истина: [ ↑ правый узел удалить: подузел если нету: блок исключение. ]. ↑ левый узел удалить: подузел если нету: [ правый узел это пусто истина: [ ↑ блок исключение значение. ] ложь: [ правый узел удалить: подузел если нету: блок исключение. ]. ]. остаток |
| перебор |
| делать: блок левый узел это пусто ложь: [ левый узел делать: блок. ]. блок значение: сам. правый узел это пусто ложь: [ правый узел делать: блок. ]. |
Перебор использует симметричный обход, сначала в качестве значения для блока применяется левый подузел, затем корень, и третьим правый подузел. Блок должен быть определён для аргумента являющегося Узлом.
Представим Дерево как вид Набора последовательности чьи элементы это Узлы. Дерево имеет одну переменную экземпляра с именем корень, корень это пусто или экземпляр Узла. Как подкласс Набора последовательности, класс Дерево реализует сообщения добавить: элемент, удалить: элемент если нету: блок исключение, и делать: блок. В основном эти методы проверяют пустое ли дерево (корень это пусто) и, если нет, посылают соответствующее сообщение корню. Проверка на пустоту наследуется от Набора. Это сделано для того чтобы программист использующий древовидную структуру обращался к элементам этой структуры только через экземпляры класса Дерево.
| имя класса Дерево |
| суперкласс Набор последовательность |
| имена переменных экземпляра корень |
| методы экземпляра |
| проверки |
| пустой ↑ корень это пусто. |
| доступ |
| первый | узел | сам проверить на пустоту. узел ← корень. [ узел левый это пусто. ] пока ложь: [ узел ← узел левый. ]. ↑ узел. последний размер |
| добавление |
| добавить: узел ↑ сам добавить последним: узел. добавить первым: узел добавить последним: узел |
| удаление |
| удалить: узел если нету: блок исключение "Сначала проверяется корень. Если узел не равен корню, то просматривается всё дерево." сам пустой истина: [ ↑ блок исключение значение. ]. корень = узел истина: [ корень ← корень остаток. ↑ узел. ] ложь: [ ↑ корень удалить: узел если нету: блок исключение. ]. удалить первый удалить последний |
| перебор |
| делать: блок сам пустой ложь: [ корень делать: блок. ]. |
Заметьте что удаляющее сообщение не удаляет поддерево начинающиеся с узла, а только сам узел.
Бинарное дерево слов[]
Определение Узла, подобно Связи, это структура без содержания. Содержание каждого узла определяется подклассом. Допустим нужно использовать вид Узла для хранения слов. Назовём этот класс Узел слово. Экземпляр Узла слова создаётся при помощи сообщения для:, если не задаются подузлы, или для:правый:левый: если задаётся два подузла. Поэтому Узел слово показываемое как:
создаётся при выполнение предложения
Узел слово выглядищее так:
создаётся при выполнении предложения
для: 'cat'
левый: (Узел слово для: 'dog')
правый: (Узел слово для: 'goat').
Ниже приведена реализация класса Узел слово. Заметьте что равенство (=) переопределено так чтобы означать равенство слов в Узле, это означает что унаследованное удаляющее сообщение будет удалять подузел если слово в нём такое же как в аргументе.
| имя класса Узел слово |
| суперкласс Узел |
| имена переменных экземпляра слово |
| методы класса |
| создание экземпляра |
| для: цепь ↑ сам новый слово: цепь. для: цепь левый: лев узел правый: прав узел |
| методы экземпляра |
| доступ |
| слово ↑ слово. слово: цепь |
| сравнение |
| = узел слово ↑ (узел слово это разновидность: Узел слово) и: [ слово = узел слово слово. ]. хэш |
Селдующая последовательность предложений иллюстрирует использование Узла слова. Заметьте что в определении Узла слова не было сделано ничего для поддержки вставки элементов так чтобы при обходе дерева они располагались в алфавитном порядке. Заинтересованный читатель может добавить сообщение вставить: узел слово в Узел слово которое сохраняет упорядоченность по алфавиту.
дерево добавить: (Узел слово для: 'cat').
добавить последним: (Узел слово для: 'horse' левый: (Узел слово для: 'monkey') правый: пусто).
