vndmtrx / libadt

:vertical_traffic_light:libadt - an abstract data types library

libadt - an abstract data types library

Status

What is libadt?

Libadt is a C library for those who want to study a little more about Abstract Data Types. The library implements the most common types of structures of computer science and is extremely well documented.

ADTs are a theoretical concept in computer science, used in the design and analysis of algorithms, data structures, and software systems, and do not correspond to specific features of computer languages - mainstream computer languages do not directly support formally specified ADTs. However, various language features correspond to certain aspects of ADTs, and are easily confused with ADTs proper; these include abstract types, opaque data types, protocols, and design by contract. -- Wikipedia

Why?

Because in C we deal directly with memory, and the structures provided by the language are quite primitive. And since in higher level languages there are other structures (such as classes and objects) that implement many of the features of data structures, there would be no advantage (or learning) in implementing these structures on such languages.

What Structures do you have now?

• Singly-linked list (README);
• Doubly-linked list (README);
• Deque using doubly-linked list as infrastructure (README);
• Queues
  • using singly-linked list as infrastructure (README);
  • using deque as infrastructure (README);
• Stacks
  • using singly-linked list as infrastructure (README);
  • using deque as infrastructure (README);

But this repository is in its very beginning and another structures will come in time.

What structures do you plan to implement?

At the present time, the following structures are being implemented:

• Circular Linked List (README);

Once completed, the next to be implemented are as follows:

• Trees (Binary Search Tree, AVL Tree, Red-black Tree);
• Heaps;
• Priority Structures (P-Queue, P-Stack and P-Deque);
• Sets using sorted tree as infrastructure;
• Stack and Queue using tree as infrastructure;
• Priority Structures (P-Queue, P-Stack and P-Deque) using sorted tree as infrastructure;
• Associative Arrays;
• Sparse Matrixes;
• Graphs;

Other related algorithms

When we are dealing with data structures, certain code patterns appear in the form of specialized algorithms to work with each type of structure.

With that in mind, we will be adding these algorithms into another folder to avoid confusion between data structures and algorithms that operate on top of these.

Algorithms implemented:

• Infix to Postfix converter using Stack;
• Expression evaluator using Queue;
• Iterators for Lists;

Algorithms being implemented:

• Sorting
  • Quick Sort
  • Merge Sort

Naming structure

In some data structures, you may notice that there is a prefix the name of each function. The prefixes refer to the structures used to build each structure. For example, stacks and queues use the prefix "sl_" because they use a simple linked list internally, in its implementation. This notation is used because, in the future, there can be other implementations using different support structures such as heaps or trees.

Base Documentation

Dictionary of Algorithms

Future and beyond...

There is no future set. Getting to the point we implement all the most common and important structures, other focuses will be defined, always having its focus on the learning provided to the person who will use these structures.

Have fun!

libadt's Issues

Add sorting algorithms.

Add merge sort and quick sort for singy and doubly linked lists.

Fix header files to prevent import irrelevant symbols.

The current header import structure does import symbols that will not be used by user when importing a structure that uses another underlying structure.

Change destructor functions to resolve free pattern

Proposal to change function return values and error reporting

Since many data structures functionality makes use of function parameters to return data by a allocated pointer set earlier, and use 'return' to give an elementary error reporting, my proposal is to change functions behaviour to use 'return' to give the relevant data to the caller and, in case of error, return non valid value (NULL, -1, etc) and set errno in the way to permit newbie users a better experience when dealing with functions and its returnings.

Try to merge the two iterators for singly and doubly linked lists.

Change build chain to cmake

Due to increase on difficulties in write the build scripts, we decide to change them from make to cmake, to ease the construction, the tests and the integration among the other projects.

Fix awkward insert behavior on lists

Analyzing lists tests, strange behavior was detected when you add items when the current variable is not set. The functions that insert use the behavior to add the list of the head when they should offer an option to set the insertion default behavior in this case that the current variable is not set.

Rename examples section to algorithms

Since there are many functions that operate with the data structures, we need to catalog them in a folder more representative than "examples". Using "algorithms" we can classify they more easily by its function or structure usage.

Missing Queues README page.

Queues doesn't have a README page to explain the basic of the structure.

Remove unnecessary list verifications on list-dependent structures.

As we test if an passing object is NULL or not, We don't need to verify it again in subsequent uses. The messages should be the return codes to shorten code execution.

Fix mixed tabs and spaces into codebase

Due to the fact that library development has occurred in several code editors, several files have different tabulations, consisting of tabs or spaces, in different patterns.

Implement better test coverage

Memory leak when destroying lists.

When a list is destroyed with *_destroy and that list doesn't set a destroyfunc function, the *_destroy function leaks memory.

Change lists to work with list_node instead of data

Since the objective of this project is to work with abstract data types, the functions that deal with the structures must deal with the node elements instead coupling the node creation/destruction into its logic.

This way, it's needed to decouple node logic from structures logic to permit another types of node structures, like priority signaled nodes.

Lack of function to change item's position

Single linked list doesn't have a function to change a item's position inside the list.

Add code documentation on new files.

Some of the newly created files doesn't have a good code documentation.

Fix Makefiles to ease compilation

The actual Makefiles are inefficiente in the way that for every alteration on the project, is needed to create or change build targets. Those targets are almost the same across the various source files.

Add test coverage to code

The way test is performed don't actually guarantee that the code is right and make difficult to understand what is happening on the test code.

The tests should check the consistency of the code in the following situations: leak testing and stress testing.

This way, is proposed to use a test coverage tool to do the unit testing of the data structures using Unity (https://github.com/ThrowTheSwitch/Unity).

Missing Stacks README page.

Stacks doesn't have a README page to explain the basic of the structure.

Fix problems in build scripts

Some scripts fail to compile if you try to compile using make -f because the Makefile and its includes weren't developed to achieve compilation from outside the project root folder.

Prepare first release

For the first release be placed, we need to resolve the issues #7, #17, #18 and #19. After completion of these issues, we can continue generating a first version of the library.

After these, we will create a v0.1 release tag. For this, we will present the following structures:

• Singly-linked List;
• Doubly-linked List;
• Doubly-circular List;
• Singly-list-backed Queue;
• Singly-list-backed Stack;
• Doubly-list-backed Deque;
• Deque-backed Queue;
• Deque-backed Stack;
• Iterators to iterate through the structures;

Add iterators for lists.

In computer programming, an iterator is an object that enables a programmer to traverse a container, particularly lists. Various types of iterators are often provided via a container's interface. Though the interface and semantics of a given iterator are fixed, iterators are often implemented in terms of the structures underlying a container implementation and are often tightly coupled to the container to enable the operational semantics of the iterator. Note that an iterator performs traversal and also gives access to data elements in a container, but does not perform iteration.

Change list file and function names.

To create a standard name definition, the naming convention must be consistent across the project.