Fw/DataStructures: Basic Data Structures

Fw/DataStructures contains a library of basic data structures. All the definitions in this directory are in the namespace Fw.

The data structures defined here use the following concepts:

size: The number of elements currently stored in a data structure.
capacity: The maximum number of elements stored in a data structure.

For a fixed-size array, the size and the capacity are the same. For other data structures, the size and the capacity are not in general the same. For example, a map has a capacity C and a size S between 0 and C.

The data structures in this directory are sequential data structures, i.e., they do not support direct concurrent access by multiple threads. To use these data structures in a multithreaded context, you need to provide separate concurrency control. The most common way to do this is to make the data structure a member of an active or queued component and to use the component queue to guard the access to the structure.

1. Arrays

An array A stores S elements for S > 0 at indices 0, 1, ..., S - 1. The elements are stored in backing memory M. An array provides bounds-checked access to the array elements stored in M.

Fw/DataStructures provides the following array templates:

Name	Description
`Array`	A bounds-checked array with internal memory for storing the array elements
`ExternalArray`	A bounds-checked array with external memory for storing the array elements

2. Stacks

A stack is a data structure that provides push and pop operations in last-in-first-out (LIFO) order.

2.1. Templates

Fw/DataStructures provides the following stack templates:

Name	Description
`ExternalStack`	A stack with external memory for storing the stack items
`Stack`	A stack with internal memory for storing the stack items
`StackBase`	The abstract base class for a stack

2.2. Class Diagram

mermaid

classDiagram
    SizedContainer <|-- StackBase
    StackBase <|-- ExternalStack
    StackBase <|-- Stack

StackBase is a derived class of SizedContainer, which represents a generic container with a capacity and a size.

3. FIFO Queues

A FIFO queue is a data structure that provides enqueue and dequeue operations in first-in-first-out (FIFO) order.

3.1. Templates

Fw/DataStructures provides the following FIFO queue templates:

Name	Description
`ExternalFifoQueue`	A FIFO queue with external memory for storing the queue items
`FifoQueue`	A FIFO queue with internal memory for storing the queue items
`FifoQueueBase`	The abstract base class for a FIFO queue

The queue implementations use a template called CircularIndex for representing a circular index, i.e., an index that wraps around modulo an integer. You can use this template to represent any circular index.

3.2. Class Diagram

mermaid

classDiagram
    SizedContainer <|-- FifoQueueBase
    FifoQueueBase <|-- ExternalFifoQueue
    FifoQueueBase <|-- FifoQueue

FifoQueueBase is a derived class of SizedContainer, which represents a generic container with a capacity and a size.

4. Maps

A map is a data structure that associates keys to values. It provides insert, remove, and find operations.

4.1. Templates

Fw/DataStructures provides the following map templates:

Name	Description
`ArrayMap`	An array-based map with internal memory for storing the array
`ExternalArrayMap`	An array-based map with external memory for storing the array
`ExternalRedBlackTreeMap`	A red-black tree with external memory for storing the tree
`MapBase`	The abstract base class for a map
`RedBlackTreeMap`	A red-black tree with internal memory for storing the tree

4.2. Class Diagram

mermaid

classDiagram
    SizedContainer <|-- MapBase
    MapBase <|-- ArrayMap
    MapBase <|-- ExternalArrayMap
    MapBase <|-- ExternalRedBlackTreeMap
    MapBase <|-- RedBlackTreeMap

MapBase is a derived class of SizedContainer, which represents a generic container with a capacity and a size.

5. Sets

A set is a data structure that contains elements. It provides insert, remove, and find operations.

5.1. Templates

Name	Description
`ArraySet`	An array-based set with internal memory for storing the array
`ExternalArraySet`	An array-based set with external memory for storing the array
`ExternalRedBlackTreeSet`	A red-black tree with external memory for storing the tree
`RedBlackTreeSet`	A red-black tree with internal memory for storing the tree
`SetBase`	The abstract base class for a set

5.2. Class Diagram

mermaid

classDiagram
    SizedContainer <|-- SetBase
    SetBase <|-- ArraySet
    SetBase <|-- ExternalArraySet
    SetBase <|-- ExternalRedBlackTreeSet
    SetBase <|-- RedBlackTreeSet

SetBase is a derived class of SizedContainer, which represents a generic container with a capacity and a size.