Page MenuHomePhabricator

PawLIB Core
Updated 394 Days AgoPublic

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.
NOTE: Descriptions (mostly) from "Game Engine Architecture" by Jason Gregory, pg. 224.
Last Author
jcmcdonald
Last Edited
Jul 16 2021, 5:24 PM

Document Hierarchy

Event Timeline

jcmcdonald edited the content of this document. (Show Details)
jcmcdonald edited the content of this document. (Show Details)
jcmcdonald edited the content of this document. (Show Details)
ankush981 edited the content of this document. (Show Details)