Студент

Волобой Борис

Задача

Двусвязный список

Состояние

Открыто

Дедлайн

Назначено

16.03.2020, 10:46

Реализовать на языке C модуль для работы с двусвязным списком элементов.

Строго заданный интерфейс:

// Файл 'dlist.h'
#include <stdbool.h> // bool
#include <stddef.h>  // size_t

static const size_t INVALID = ~((size_t)0);

void * dlist_create(size_t itemSize);
void dlist_destroy(void * dlist, void(*destroy)( void * ));
void * dlist_init(
    void * dlist, 
    size_t itemSize, 
    void(*destroy)( void * ));
void dlist_clear(void * dlist, void(*destroy)( void * ));
size_t dlist_count(const void * dlist);
void * dlist_item(void * dlist, size_t i);
void * dlist_append(void * dlist);
void * dlist_prepend(void * dlist);
void dlist_removeFirst(void * dlist, void(*destroy)( void * ));
void dlist_removeLast(void * dlist, void(*destroy)( void * ));

size_t dlist_first(const void * dlist);
size_t dlist_last(const void * dlist);
size_t dlist_next(const void * dlist, size_t item_id);
size_t dlist_prev(const void * dlist, size_t item_id);
size_t dlist_stop(const void * dlist);
void * dlist_current(const void * dlist, size_t item_id);
void * dlist_insertAfter(void * dlist, size_t item_id);
void * dlist_insertBefore(void * dlist, size_t item_id);
void dlist_erase(void * dlist, size_t item_id, void(*destroy)( void * ));

• INVALID -- код ошибки для не валидных ситуаций.
• dlist_create -- Создать новый пустой двусвязный список. Размер элемента -- itemSize байт.
• dlist_destroy -- Удалить существующий двусвязный список. Если указана функция destroy, то вызвать её для каждого удаляемого элемента.
• dlist_init -- Инициализировать двусвязный список. Размер элемента -- itemSize байт. Если dlist содержит элементы, то сначала удалить все элементы, потом инициализировать двусвязный список с учетом новых параметров. Если указана функция destroy, то вызвать её для каждого удаляемого элемента.
• dlist_clear -- Удалить все элементы из двусвязного списка. Если указана функция destroy, то вызвать её для каждого удаляемого элемента.
• dlist_count -- Количество элементов в списке. В случае, если dlist равен NULL, возвращает константу INVALID.
• dlist_item -- Получить элемент по индексу в списке.
• dlist_append -- Добавить элемент в хвост двусвязного списка. В случае успеха, функция возвращает указатель на добавленный элемент, иначе -- NULL.
• dlist_prepend -- Добавить элемент в голову двусвязного списка. В случае успеха, функция возвращает указатель на добавленный элемент, иначе -- NULL.
• dlist_removeFirst -- Удалить элемент из головы двусвязного списка. Если указана функция destroy, то вызвать её для удаляемого элемента.
• dlist_removeLast -- Удалить элемент из хвоста двусвязного списка. Если указана функция destroy, то вызвать её для удаляемого элемента.
• dlist_first -- Идентификатор для первого элемента из двусвязного списка. Идентификатор может стать не валидным при модификации списка.
• dlist_last -- Идентификатор для последнего элемента из двусвязного списка. Идентификатор может стать не валидным при модификации списка.
• dlist_next -- По идентификатору текущего элемента получить идентификатор следующего элемента списка.
• dlist_prev -- По идентификатору текущего элемента получить идентификатор предыдущего элемента списка.
• dlist_stop -- Идентификатор, получаемый при попытке обратиться к элементу за пределами списка.
• dlist_current -- Получить указатель на элемент списка по его идентификатору.
• dlist_insertAfter -- Вставка нового элемента списка после указанного по идентификатору. Когда список пустой, для успешной вставки элемента в качестве item_id должен указываться идентификатор, возвращаемый функцией dlist_stop. В остальных случаях, item_id должен однозначно соответствовать элементу списка. В случае успеха, функция возвращает указатель на вставленный элемент, иначе -- NULL.
• dlist_insertBefore -- Вставка нового элемента списка перед указанным по идентификатору. В случае успеха, функция возвращает указатель на вставленный элемент, иначе -- NULL.
• dlist_erase -- Удаление элемента по его идентификатору. Если указана функция destroy, то вызвать её для удаляемого элемента. После удаления элемента из списка, идентификаторы любых элементов из этого массива могут стать невалидным.

//Пример использования
#include <string.h>
#include <assert.h>
#include <math.h>

#include "dlist.h"

typedef struct {
    int array[8];
    float d_variable;
} Value;

int main(int argc, char* argv[])
{
    //Создаем двусвязный список с элементами типа Value;
    void* dlist = dlist_create(sizeof(Value));

    assert(0 == dlist_count(dlist));
    assert(dlist_stop(dlist) == dlist_first(dlist));

    //Создаем объект для двусвязного списока
    Value value = { {1, 2, 3, 4, 5, 6, 7, 8}, 0.f };

    //Добавляем новый элемент в двусвязный список
    Value* insertedValue = (Value*)dlist_prepend(dlist);

    //Инициализируем добавленный элемент
    *insertedValue = value;

    Value* item = (Value*)dlist_item(dlist, 0);

    for (size_t i = 0; 8 > i; ++i) {
        assert(item->array[i] == value.array[i]);
    }

    assert(fabsf(item->d_variable - value.d_variable) < 1e-10f);
    assert(NULL == dlist_item(dlist, 1));

    assert(dlist_next(dlist, dlist_first(dlist)) == dlist_stop(dlist));

    dlist_destroy(dlist, NULL);

    return 0;
}