Persistent Data Structures

Fully Persistent DS and Partially Persistent DS
Explore the repository»

View Problem Statement

tags : persistent data structure, full persistence, partial persistence, heterogeneous vector, stack, queue, map, dequeue, linked list

About The Project

This project implements a small library of persistent data structures in C. A persistent data structure is a data structure that always preserves the previous version of itself when it is modified. They are effectively immutable, in the sense that their operations do not (visibly) update the structure in-place, but always produce a new updated version. A data structure is partially persistent if all versions can be accessed but only the newest version can be modified. The data structure is fully persistent if every version can be both accessed and modified. In this program, each node contains a modification box with a timestamp to hold a single modification. If more than modification is applied to a node, the node is split to create a new node with the latest values. Amortized O(1) time and space can be achieved for access and updates using this method. This method was originally given by Sleator, Tarjan et al. Each node contains a modification box that can hold:

• One modification to the node (the modification could be of one of the pointers, or to the node’s key or to some other node-specific data)
• The time instance (or version number) when the mod was applied. The timestamp is essential for tracing the path to the version of the node we care about.

This library supports both partially and fully persistent versions of the data structures. The library includes the following data structures and all the usual operations on them.

1. Heterogeneous vector (supports elements of different types)
2. Map
3. Stack
4. Queue
5. Double-ended queue
6. Singly linked linked list
7. Doubly linked linked list

The library has separate directories for partial and full persistence. Within each directory, there are sub-directories --- each corresponding to a particular data structure. The program for each data structure is written in three files - client.c, header.c, and implement.c. Comments have been added frequently to help in understanding the logic behind implementation. Theclient.c files contains some basic testing of the the persistence for the data structures. Refer Problem statement file for detailed information.

Built With

This project was built with

• C
• Ubuntu 18.04.1
• gcc version 7.4.0

Getting Started

Clone the repository into a local machine using

git clone https://github.com/vineeths96/Persistent-Data-Structures

Instructions to run

Fully Persistent Data Structures

Open the terminal, and cd to the directory of the data structure within Fully Persistent Data Structures.

cd Fully Persistent Data Structures/<DataStructure>

Make the program and run it.

make
./a.out

Partially Persistent Data Structures

Open the terminal, and cd to the directory of the data structure within Partially Persistent Data Structures.

cd Partially Persistent Data Structures/<DataStructure>

Make the program and run it.

make
./a.out

License

Distributed under the MIT License. See LICENSE for more information.

Contact

Vineeth S - [email protected]

Project Link: https://github.com/vineeths96/Persistent-Data-Structures