go_persistent_ds

README

persistent-data-structures

Курсовой проект по дисциплине "Современные методы программирования" - "Persistent data structures"

Installation

go get github.com/AleksandrMatsko/go-persistent-ds

Задание

Реализовать библиотеку со следующими структурами данных в persistent-вариантах (с единым API для всех структур)

Базовые требования

• Массив (константное время доступа, переменная длина)
• Двусвязный список
• Ассоциативный массив (на основе Hash-таблицы, либо бинарного дерева)
• Должен быть единый API для всех структур, желательно использовать естественный API для выбранной платформы

Дополнительные требования

• Обеспечить произвольную вложенность данных (по аналогии с динамическими языками), не отказываясь при этом полностью от типизации посредством generic/template;
• Реализовать универсальный undo-redo механизм для перечисленных структур с поддержкой каскадности (для вложенных структур);
• Реализовать более эффективное по скорости доступа представление структур данных, чем fat-node.
• Расширить экономичное использование памяти на операцию преобразования одной структуры к другой (например, списка в массив)
• Реализовать поддержку транзакционной памяти (STM)

Ответственные

• Вартазарян Эдуард Араевич, гр. 24221
• Мацько Александр Михайлович, гр. 24221

Реализация

Предполагаемый путь решения

1. Найти соответствующие алгоритмы с помощью изучения публикаций по теме Persistent Data Structures;
2. Изучив теорию по персистентным структурам данных, реализовать их в проекте с использованием выбранного стека технологий.

Календарный план

сроки	этап работы
до 25.11.2024	- создание репозитория на GitHub - настройка CI/CD - поиск подходящих алгоритмов
до 09.12.2024	Реализация базовой функциональности - Массив - Двусвязный список - Ассоциативный массив
до 23.12.2024 (что успеем)	Реализация дополнительной функциональности - Произвольная вложенность данных - undo-redo - Более эффективное по скорости доступа представление структур данных, чем fat-node - Экономичное использование памяти при преобразовании одной структуры в другую

Технологии

• Язык программирования - Go
• Система контроля версий - git
• CI/CD - GitHub Actions

Реализованные дополнительные требования

• Произвольная вложенность данных.
• Конвертация persistent структур в соответствующие структуры данных языка Go:
  • Map[TKey, TVal] -> map[TKey]TVal c помощью ToGoMap
  • Slice[TVal] -> []TVal c помощью ToGoSlice
  • DoubleLinkedList[TVal] -> list.List (из пакета container/list стандартной библиотеки языка Go) с помощью ToGoList
• Для Slice реализован метод Range (аналог slice[i:j] из Go), позволяющий создавать срез исходного Slice и далее работать с ним также, как и с обычным persistent Slice

Documentation

Overview

Package go_persistent_ds implements several fully persistent data structures.

Available data structures are:

• Map
• Slice
• DoubleLinkedList

All structures are base on FatNodes.

Note that every structure can perform total of 2^65-1 modifications, and will panic on attempt to modify it for 2^65 time. If you need to continue editing structure, the good idea is to use appropriate method to dump structure for special version.

Index

• Variables
• type DoubleLinkedList
  • func NewDoubleLinkedList[T any]() (*DoubleLinkedList[T], uint64)
  • func NewDoubleLinkedListWithAnyValues() (*DoubleLinkedList[any], uint64)
  • func (l *DoubleLinkedList[T]) Get(version uint64, index int) (T, error)
  • func (l *DoubleLinkedList[T]) Len(version uint64) (int, error)
  • func (l *DoubleLinkedList[T]) PushBack(version uint64, value T) (uint64, error)
  • func (l *DoubleLinkedList[T]) PushFront(version uint64, value T) (uint64, error)
  • func (l *DoubleLinkedList[T]) Remove(version uint64, index int) (uint64, error)
  • func (l *DoubleLinkedList[T]) ToGoList(version uint64) (*list.List, error)
  • func (l *DoubleLinkedList[T]) Update(version uint64, index int, value T) (uint64, error)
• type Map
  • func NewMap[TKey comparable, TVal any]() (*Map[TKey, TVal], uint64)
  • func NewMapWithAnyValues[TKey comparable]() (*Map[TKey, any], uint64)
  • func NewMapWithCapacity[TKey comparable, TVal any](capacity int) (*Map[TKey, TVal], uint64)
  • func (m *Map[TKey, TVal]) Delete(forVersion uint64, key TKey) (uint64, error)
  • func (m *Map[TKey, TVal]) Get(version uint64, key TKey) (TVal, error)
  • func (m *Map[TKey, TVal]) Len(forVersion uint64) (int, error)
  • func (m *Map[TKey, TVal]) Set(forVersion uint64, key TKey, val TVal) (uint64, error)
  • func (m *Map[TKey, TVal]) ToGoMap(version uint64) (map[TKey]TVal, error)
• type Slice
  • func NewSlice[TVal any]() (*Slice[TVal], uint64)
  • func NewSliceWithAnyValues() (*Slice[any], uint64)
  • func NewSliceWithCapacity[TVal any](capacity int) (*Slice[TVal], uint64)
  • func (s *Slice[TVal]) Append(version uint64, val TVal) (uint64, error)
  • func (s *Slice[TVal]) Get(version uint64, index int) (TVal, error)
  • func (s *Slice[TVal]) Len(version uint64) (int, error)
  • func (s *Slice[TVal]) Range(forVersion uint64, startIndex, endIndex int) (uint64, error)
  • func (s *Slice[TVal]) Set(forVersion uint64, index int, val TVal) (uint64, error)
  • func (s *Slice[TVal]) ToGoSlice(forVersion uint64) ([]TVal, error)

Variables

var (
	// ErrMapInitialize is returned then there is a problem in creating new tree.
	ErrMapInitialize = errors.New("failed to init Map because version tree is damaged")
	// ErrNotFound is returned then value by key or for version is not found.
	ErrNotFound = errors.New("not found")
)

var (
	// ErrSliceInitialize is returned then there is a problem in creating new slice because of tree problems.
	ErrSliceInitialize = errors.New("failed to init Slice because version tree is damaged")
	// ErrIndexOutOfRange is returned then index is greater than len array for the version.
	ErrIndexOutOfRange = errors.New("array index out of range")
)

var ErrListIndexOutOfRange = errors.New("index out of range")

Types

type DoubleLinkedList

type DoubleLinkedList[T any] struct {
	// contains filtered or unexported fields
}

DoubleLinkedList is a persistent implementation of double linked list. While working with list you can add to the start and to the end, access elements by index and modify. Each change of the list creates new version. Versions can be retrieved by their number. Also, there is an opportunity to convert this list into Go list using ToGoList.

DoubleLinkedList can perform total of 2^65-1 modifications, and will panic on attempt to modify it for 2^65 time. If you need to continue editing DoubleLinkedList, the good idea is to use ToGoList method to dump list for special version.

Note that DoubleLinkedList implementation is not thread safe.

func NewDoubleLinkedList

func NewDoubleLinkedList[T any]() (*DoubleLinkedList[T], uint64)

NewDoubleLinkedList creates new empty DoubleLinkedList.

func NewDoubleLinkedListWithAnyValues

func NewDoubleLinkedListWithAnyValues() (*DoubleLinkedList[any], uint64)

NewDoubleLinkedListWithAnyValues creates DoubleLinkedList that can store values of any type.

func (*DoubleLinkedList[T]) Get

func (l *DoubleLinkedList[T]) Get(version uint64, index int) (T, error)

Get retrieves value from the specified DoubleLinkedList version by index.

Complexity: O(n * log(m)), where n - DoubleLinkedList size and m - is number of changes in FatNode.

func (*DoubleLinkedList[T]) Len

func (l *DoubleLinkedList[T]) Len(version uint64) (int, error)

Len returns DoubleLinkedList size.

Complexity: O(1).

func (*DoubleLinkedList[T]) PushBack

func (l *DoubleLinkedList[T]) PushBack(version uint64, value T) (uint64, error)

PushBack adds new element to the tail of the DoubleLinkedList. Returns list's new version. Note: head->[1][2][3]<-tail.

Complexity: O(1).

func (*DoubleLinkedList[T]) PushFront

func (l *DoubleLinkedList[T]) PushFront(version uint64, value T) (uint64, error)

PushFront adds new element to the head of the DoubleLinkedList. Returns list's new version. Note: head->[1][2][3]<-tail.

Complexity: O(n).

func (*DoubleLinkedList[T]) Remove

func (l *DoubleLinkedList[T]) Remove(version uint64, index int) (uint64, error)

Remove removes element from specified version of DoubleLinkedList by index and returns new list's version. By removal, we mean delete of connection between specified element and his "neighbours".

Complexity: O(n * log(m)), where n - DoubleLinkedList size and m - is number of changes in FatNode.

func (*DoubleLinkedList[T]) ToGoList

func (l *DoubleLinkedList[T]) ToGoList(version uint64) (*list.List, error)

ToGoList converts DoubleLinkedList into Go List.

Complexity: O(Get) * n, where n - DoubleLinkedList size.

func (*DoubleLinkedList[T]) Update

func (l *DoubleLinkedList[T]) Update(version uint64, index int, value T) (uint64, error)

Update updates element of specified DoubleLinkedList version by index. Returns list's new version.

Complexity: O(n * log(m)), where n - DoubleLinkedList size and m - is number of changes in FatNode.

type Map

type Map[TKey comparable, TVal any] struct {
	// contains filtered or unexported fields
}

Map is a persistent implementation of go map. While working with map you can access and/or modify each previous version. Note that modifying version creates new one.

Map can perform total of 2^65-1 modifications, and will panic on attempt to modify it for 2^65 time. If you need to continue editing Map, the good idea is to use ToGoMap method to dump Map for special version.

Note that Map is not thread safe.

func NewMap

func NewMap[TKey comparable, TVal any]() (*Map[TKey, TVal], uint64)

NewMap creates empty Map.

func NewMapWithAnyValues

func NewMapWithAnyValues[TKey comparable]() (*Map[TKey, any], uint64)

NewMapWithAnyValues creates a Map, that can store values of any type.

func NewMapWithCapacity

func NewMapWithCapacity[TKey comparable, TVal any](capacity int) (*Map[TKey, TVal], uint64)

NewMapWithCapacity creates empty Map with given capacity.

func (*Map[TKey, TVal]) Delete

func (m *Map[TKey, TVal]) Delete(forVersion uint64, key TKey) (uint64, error)

Delete the value from Map for given key for given version.

Complexity: same as for Get.

func (*Map[TKey, TVal]) Get

func (m *Map[TKey, TVal]) Get(version uint64, key TKey) (TVal, error)

Get returns a pair of value and error for provided version and key. If error is nil then the value for such key and version exists.

Complexity: O(log(m) * k) there:

• m - amount of modifications for current key from map creation.
• k - amount of modifications visible from current branch.

func (*Map[TKey, TVal]) Len

func (m *Map[TKey, TVal]) Len(forVersion uint64) (int, error)

Len returns the len of Map.

Complexity: O(1).

func (*Map[TKey, TVal]) Set

func (m *Map[TKey, TVal]) Set(forVersion uint64, key TKey, val TVal) (uint64, error)

Set value for given key and version in Map.

Complexity: same as for Get.

func (*Map[TKey, TVal]) ToGoMap

func (m *Map[TKey, TVal]) ToGoMap(version uint64) (map[TKey]TVal, error)

ToGoMap converts persistent Map for specified version into go map.

Complexity: O(Get) * n, there:

• n - amount of different keys in map from creation.

type Slice

type Slice[TVal any] struct {
	// contains filtered or unexported fields
}

Slice is a persistent implementation of go slice. While working with slice you can access and/or modify each previous version. Note that modifying version creates new one.

Slice can perform total of 2^65-1 modifications, and will panic on attempt to modify it for 2^65 time. If you need to continue editing Slice, the good idea is to use ToGoSlice method to dump Slice for special version.

Note that Slice is not thread safe.

func NewSlice

func NewSlice[TVal any]() (*Slice[TVal], uint64)

NewSlice creates empty Slice.

func NewSliceWithAnyValues

func NewSliceWithAnyValues() (*Slice[any], uint64)

NewSliceWithAnyValues creates a Slice, that can store values of any type.

func NewSliceWithCapacity

func NewSliceWithCapacity[TVal any](capacity int) (*Slice[TVal], uint64)

NewSliceWithCapacity creates empty Slice with given capacity.

func (*Slice[TVal]) Append

func (s *Slice[TVal]) Append(version uint64, val TVal) (uint64, error)

Append adds the value to the end of Slice of given version.

Complexity: O(1).

func (*Slice[TVal]) Get

func (s *Slice[TVal]) Get(version uint64, index int) (TVal, error)

Get returns a pair of value and error for provided version and index. If error is nil then value for such index and version exists.

Complexity: O(log(m) * k) there:

• m - amount of modifications for value by the index from slice creation.
• k - amount of modifications visible from current branch.

func (*Slice[TVal]) Len

func (s *Slice[TVal]) Len(version uint64) (int, error)

Len returns the len of Slice.

Complexity: O(1).

func (*Slice[TVal]) Range

func (s *Slice[TVal]) Range(forVersion uint64, startIndex, endIndex int) (uint64, error)

Range takes the range of Slice for given version from startIndex (inclusive) to endIndex (not inclusive).

Complexity: O(1).

func (*Slice[TVal]) Set

func (s *Slice[TVal]) Set(forVersion uint64, index int, val TVal) (uint64, error)

Set value for given index and version in Slice.

Complexity: O(1).

func (*Slice[TVal]) ToGoSlice

func (s *Slice[TVal]) ToGoSlice(forVersion uint64) ([]TVal, error)

ToGoSlice converts persistent Slice for specified version into go slice.

Complexity: O(Get) * n, there:

• n - size of Slice for version.