# PawLIB Core

The PawLIB Core contains the basic functions and classes that the rest of the library relies upon.

- Data Types
- Data Structures
- Standard Utilities (stdutils)

## Data Structures

Here is a list of proposed and implemented data structures.

### FlexArray (Base)

A contiguous memory array/deque, internally implemented with a contiguous memory circular buffer.

#### FlexArray

A resizable, vector-like array container. Replaces `std::vector`, and possibly `std::deque`.

#### FlexBit

A resizable bitwise array container. Replaces `std::vector<bool>`.

#### FlexStack

A LIFO model container, or stack, based on FlexArray. Replaces `std::stack`.

#### FlexQueue

A FIFO model container, or queue, based on FlexArray. Replaces `std::queue`.

### SpeedList (Base)

An ordered collection of elements not stored contiguously in memory, but rather linked together with pointers. Internally, an XOR doubly-linked list.

#### SpeedList

A doubly-linked list, based on SpeedList (base). Replaces `std::list`.

#### SpeedForwardList

A singly-linked list, based on SpeedList. Replaces `std::forward_list`.

#### SpeedStack

A LIFO model container, or stack, based on SpeedList. Replaces `std::stack`.

#### SpeedQueue

A FIFO model container, or queue, based on SpeedList. Replaces `std::queue`.

### Pool

A general-use implementation of the object pool design pattern.

### Iterators

### Proposed Containers

#### Map

A table of key-value pairs. A value can be "looked up" efficiently given the corresponding key. Replaces `std::map`.

#### Tree/Graph

**Tree**: A container in which elements are grouped hierarchically. Each element (node) has zero or one parent and zero or more children. A tree is a special case of a DAG (see below).**Binary search tree**: A tree in which each node has at most two children, with an order property to keep the nodes sorted by some well-defined criteria.**Binary heap**: A binary tree that maintains itself in sorted order, much like a binary search tree, via two rules: the*shape property*, which specifies that the tree must be fully filled and that the last row of the tree is filled from left to right; and the*heap property*, which states that every node is, by some user-defined criterion, "greater than" or "equal to" all of its children.**Graph**: A collection of nodes connected to one another by unidirectional or bidirectional pathways in an arbitrary pattern.**Directed acyclic graph [DAG]**: A collection of nodes with unidirectional (i.e.*directed*) interconnections, with no*cycles*(i.e. there is no non-empty path that starts and ends on the same node.

#### Others

**Priority queue**: A container that permits elements to be added in any order and then removed in any order defined by some property of the elements themselves (i.e. their*priority*).**Set**: A container that guarantees that all elements are unique according to some criteria. A set acts like a dictionary with only keys, but no values.

*None*

- Last Author
- jcmcdonald
- Last Edited
- Jul 16 2021, 5:24 PM