7.7 Пример — List, Queue и Stack

Давайте посмотрим на несколько новых классов, реализованных с нуля с помощью ooc, чтобы можно было оценить сэкономленные силы. Начнём с List, реализованного в виде двухстороннего кругового буфера, который будет динамически увеличиваться по мере необходимости.

begin и end ограничивают используемую часть списка, dim это максимальный размер буфера, а count представляет количество элементов в данный момент находящихся в буфере. count позволяет легко различать полный и пустой буфер. Вот описание класса List.d:

% ListClass: Class List: Object {

    const void ** buf; // const void * buf [dim]

    unsigned dim;      // текущий размер массива

    unsigned count;    // количество элементов в буфере

    unsigned begin;    // индекс слота takeFirst, 0..dim

    unsigned end;      // индекс слота addLast, 0..dim

%

    Object @ addFirst (_self, const Object @ element);

    Object @ addLast (_self, const Object @ element);

    unsigned count (const _self);

    Object @ lookAt (const _self, unsigned n);

    Object @ takeFirst (_self);

    Object @ takeLast (_self);

%—                     // абстракция, для Queue/Stack

    Object @ add (_self, const Object @ element);

    Object @ take (_self);

%}

Реализация в List.dc не очень сложна. Конструктор создаёт буфер начального размера:

% List ctor {

    struct List * self = super_ctor(List, _self, app);

    if (! (self -> dim = va_arg(* app, unsigned)))

        self -> dim = MIN;

    self -> buf = malloc(self -> dim * sizeof * self -> buf);

    assert(self -> buf);

    return self;

}

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

% List dtor {

%casts

    free(self —> buf), self —> buf = 0;

    return super_dtor(List, self);

}

addFirst() и addLast() добавляют один элемент в начало, по адресу begin, или конец, по адресу end:

% List addFirst {

%casts

    if (! self -> count)

        return add1(self, element);

    extend(self);

    if (self -> begin == 0)

        self -> begin = self -> dim;

    self -> buf[-- self -> begin] = element;

    return (void *) element;

}

% List addLast {

%casts

    if (! self -> count)

        return add1(self, element);

    extend(self);

    if (self -> end >= self -> dim)

        self -> end = 0;

    self -> buf[self -> end ++] = element;

    return (void *) element;

}

Обе эти функции используют один и тот же код для добавления одного элемента:

static void * add1 (struct List * self, const void * element)

{

    self -> end = self -> count = 1;

    return (void *) (self -> buf[self -> begin = 0] = element);

}

Поведение, однако, отличается: если count не равен нулю, то есть если в буфере есть какие-либо элементы, begin указывает к элемент, в то время как end указывает на свободный слот для заполнения. Любое значение может быть только за пределами текущего диапазона буфера. Буфер круговой; таким образом, мы сначала устанавливаем соответствие переменных с кругом, прежде чем получаем доступ к буферу. extend() выполняет трудную работу: если места больше нет, мы используем realloc(), чтобы удвоить размер буфера:

static void extend (struct List * self) // добавление элемента

{

    if (self -> count >= self -> dim) {

        self -> buf =

                realloc(self -> buf, 2 * self -> dim

                        * sizeof * self -> buf);

        assert(self -> buf);

        if (self -> begin && self -> begin != self -> dim) {

            memcpy(self -> buf + self -> dim + self -> begin,

                self -> buf + self -> begin,

                (self -> dim - self -> begin)

                        * sizeof * self -> buf);

            self -> begin += self -> dim;

        }

        else

            self -> begin = 0;

    }

    ++ self -> count;

}

realloc() копирует указатели, хранящиеся в buf[], но если наш круг не начинается в начале буфера, мы должны использовать memcpy(), чтобы сдвинуть начало круга в конец нового буфера.

Остальные функции гораздо проще. count() это просто функция доступа к компоненту count. lookAt() использует арифметический трюк для возврата необходимого элемента из кругового буфера:

% List lookAt {

%casts

    return (void *) (n >= self -> count ? 0 :

        self -> buf[(self -> begin + n) % self -> dim]);

}

takeFirst() и takeLast() просто обратны вариантам соответствующих функций add. Вот один из примеров:

% List takeFirst {

%casts

    if (! self -> count)

        return 0;

    -- self -> count;

    if (self -> begin >= self -> dim)

        self -> begin = 0;

    return (void *) self -> buf[self -> begin ++];

}

takeLast() остаётся в качестве упражнения — как и все селекторы и инициализация.

List показывает, что ooc возвращает нас к занятию решения вопросов реализации класса как типу данных, а не особенностей в стиле объектно-ориентированного кодирования. Учитывая разумный базовый класс, мы можем легко унаследовать более проблемно-ориентированные классы. List ввёл динамически компонуемые методы add() и take(), поэтому подкласс может наложить дисциплину доступа. Stack производит операции с одной стороны:

Stack.d

% ListClass Stack: List {

%}

Stack.dc

% Stack add {

    return addLast(_self, element);

}

% Stack take {

    return takeLast(_self);

}

%init

Queue может быть наследником Stack и перезаписать take() или может быть подклассом List и определить оба метода. List сам по себе не определяет динамически скомпонованные методы и предпочтения; поэтому может быть назван абстрактным базовым классом. Наши селекторы достаточно надёжны, поэтому мы конечно же узнаем, если кто-то попытается использовать add() или take() для List, а не подкласса. Вот тестовая программа, демонстрирующая, что мы можем добавлять в Stack или Queue простые строки C, а не объекты:

#include "Queue.h"

int main (int argc, char ** argv) {

    void * q;

    unsigned n;

    initQueue();

    q = new(Queue, 1);

    while (* ++ argv)

        switch (** argv) {

        case ’+’:

            add(q, *argv + 1);

            break;

        case ’-’:

            puts((char *) take(q));

            break;

        default:

            n = count(q);

            while (n -- > 0) {

                const void * p = take(q);

                puts(p), add(q, p);

            }

        }

    return 0;

}

Если аргумент командной строки начинается с +, она добавляется в очередь; если с - , один элемент удаляется. Любой другой аргумент выводит на экран содержимое очереди:

$ queue +axel - +is +here . - . - .

axel

is

here

is

here

here

Заменив Queue на Stack мы можем увидеть разницу в порядке удаления:

$ stack +axel - +is +here . - . - .

axel

is

here

here

is

is

Поскольку Stack является подклассом List, есть разные способы неразрушающего вывода на экран содержимого стека, например:

n = count(q);

while (n -- > 0) {

    const void * p = takeFirst(q);

    puts(p), addLast(q, p);

}