# Data Structures¶

Implementing Data Structures purely in Python.

## Quick Start Guide¶

```# import the required data structure
from pygorithm.data_structures import stack

# create a stack with default stack size 10
myStack = stack.Stack()
myStack.push(2)

# print the contents of stack
print(myStack)
```

## Features¶

• Data Structures implementations available:
• Stack
• Stack (data_structures.stack.Stack)
• Infix to Postfix conversion (data_structures.stack.InfixToPostfix)
• Queue
• Queue (data_structures.queue.Queue)
• Deque (data_structures.queue.Deque)
• Tree
• Binary Tree (data_structures.tree.BinaryTree)
• Binary Seach Tree (data_structures.tree.BinarySearchTree)
• Graph
• Graph (data_structures.graph.Graph)
• Topological Sort (data_structures.graph.TopologicalSort)
• Check cycle in Directed Graph (data_structures.graph.CheckCycleDirectedGraph)
• Check cycle in Undirected Graph (data_structures.graph.CheckCycleUndirectedGraph)
• Heap
• Heap (data_structures.heap.Heap)
• Get the code used for any of the implementation
```from pygorithm.data_structures.stack import Stack

myStack = Stack()
print(myStack.get_code())
```
• To see all the available functions in a module, you can just type `help()` with the module name as argument. For example,
```>>> from pygorithm import data_structures
>>> help(data_structures)
Help on package pygorithm.data_structures in pygorithm:

NAME
pygorithm.data_structures

PACKAGE CONTENTS
graph
heap
modules
queue
stack
tree
```

## Stack¶

Author: OMKAR PATHAK Created On: 3rd August 2017

### Stack¶

class `pygorithm.data_structures.stack.``Stack`(limit=10)[source]

Stack object

`push`(data)[source]

pushes an item into the stack returns -1 if the stack is empty

`pop`()[source]

pops the topmost item from the stack returns -1 if the stack is empty

`peek`()[source]

returns the topmost element of the stack returns -1 if the stack is empty

`is_empty`()[source]

checks if the stack is empty returns boolean value, True or False

`size`()[source]

returns the current size of the stack

static `get_code`()[source]

returns the code for current class

### Infix to Postfix¶

class `pygorithm.data_structures.stack.``InfixToPostfix`(expression=None, stack=None)[source]

get the postfix of the given infix expression

`infix_to_postfix`()[source]

function to generate postfix expression from infix expression

static `get_code`()[source]

returns the code of the current class

## Queue¶

Author: OMKAR PATHAK Created On: 3rd August 2017

### Queue¶

class `pygorithm.data_structures.queue.``Queue`(limit=10)[source]

Queue implementation

`size`()[source]

returns the current size of the queue

`is_empty`()[source]

checks if the queue is empty

`enqueue`(data)[source]

inserts an item into the queue

`dequeue`()[source]

pops an item from the queue which was first inserted

`get_code`()[source]

Return source code for Queue class :return:

### Deque¶

class `pygorithm.data_structures.queue.``Deque`(limit=10)[source]

Deque implementation

`is_empty`()[source]

checks whether the deque is empty

`is_full`()[source]

checks whether the deque is full

`insert_rear`(data)[source]

inserts an element at the rear end of the deque

`insert_front`(data)[source]

inserts an element at the front end of the deque

`delete_rear`()[source]

deletes an element from the rear end of the deque

`delete_front`()[source]

deletes an element from the front end of the deque

static `get_code`()[source]

returns the code of the current class

Author: OMKAR PATHAK Created On: 5th August 2017

Linked l_list and Node can be accommodated in separate classes for convenience

### Node¶

class `pygorithm.data_structures.linked_list.``Node`(data, next_node=None)[source]

Node class for creating a node for linked list. Each node has its data and a pointer that points to next node in the Linked l_list

static `get_code`()[source]

return the code for the current class

class `pygorithm.data_structures.linked_list.``SinglyLinkedList`[source]

`get_data`()[source]

prints the elements in the linked list

`insert_at_start`(data)[source]

insert an item at the beginning of the linked list

`insert_after`(next_node_data, data)[source]

insert an item after an element in the linked list

`insert_at_end`(data)[source]

insert an item at the end of the linked list

`delete`(data)[source]

to delete specified element from the linked list

static `get_code`()[source]

return the code for the current class

class `pygorithm.data_structures.linked_list.``DoublyLinkedList`[source]

`get_data`()[source]

prints the elements in the linked list

`insert_at_start`(data)[source]

insert an element at the beginning of the linked list

`insert_at_end`(data)[source]

insert an element at the end of the linked list

`delete`(data)[source]

to delete specified element from the linked list

static `get_code`()[source]

returns the code of the current class

## Tree¶

Author: OMKAR PATHAK Created On: 9th August 2017

Node class to create a node for binary tree

### Node¶

class `pygorithm.data_structures.tree.``Node`(data=None)[source]

Node class for creating a node for tree. Each node has its data and a pointer that points to next node in the Linked List

`set_left`(node)[source]

for setting the left child of the node

`set_right`(node)[source]

for setting the right child of the node

`get_left`()[source]

for getting the left child of the node

`get_right`()[source]

for getting the right child of the node

`set_data`(data)[source]

for setting the data of the node

`get_data`()[source]

for getting the data of the node

static `get_code`()[source]

returns the code of the current class

### Binary Tree¶

class `pygorithm.data_structures.tree.``BinaryTree`[source]

BinaryTree class to create a binary tree

`insert`(data)[source]

insert data to root or create a root node

`inorder`(root)[source]

in this we traverse first to the leftmost node, then print its data and then traverse for rightmost node :param root: Node object

`preorder`(root)[source]

in this we first print the root node and then traverse towards leftmost node and then to the rightmost node :param root: Node object

`postorder`(root)[source]

in this we first traverse to the leftmost node and then to the rightmost node and then print the data :param root: Node object

`number_of_nodes`(root)[source]

counting number of nodes

static `get_code`()[source]

returns the code of the current class

### Binary Search Tree Node¶

class `pygorithm.data_structures.tree.``BSTNode`(data)[source]

class for creating a node for binary Search tree

`set_left`(node)[source]

for setting the left child of the node

`set_right`(node)[source]

for setting the right child of the node

`get_left`()[source]

returns the left child of the current node

`get_right`()[source]

returns the right child of the current node

`set_data`(data)[source]

for setting the data of a node

`get_data`()[source]

returns the data of the current node

`insert`(data)[source]

For inserting the data in the Tree

static `min_val_bst_node`(bst_node)[source]

for returning the node with the lowest value

`delete`(data)[source]

For deleting the bst_node

`find`(data)[source]

This function checks whether the specified data is in tree or not

`inorder`(root)[source]

in this we first traverse to the leftmost node and then print the data and then move to the rightmost child :param root: Node object

`preorder`(root)[source]

in this we first print the root node and then traverse towards leftmost node and then to the rightmost node :param root: Node object

`postorder`(root)[source]

in this we first traverse to the leftmost node and then to the rightmost node and then print the data :param root: Node object

static `get_code`()[source]

returns the code of current class

### Binary Search Tree¶

class `pygorithm.data_structures.tree.``BinarySearchTree`[source]
`insert`(data)[source]

inserts a node in the tree

`delete`(data)[source]

deletes the node with the specified data from the tree

`preorder`()[source]

finding the preorder of the tree

`inorder`()[source]

finding the inorder of the tree

`postorder`()[source]

finding the postorder of the tree

`number_of_nodes`(root)[source]

counting number of nodes

static `get_code`()[source]

returns the code of the current class

## Graph¶

Author: OMKAR PATHAK Created On: 12th August 2017

### Graph¶

class `pygorithm.data_structures.graph.``Graph`[source]

Graph object Creates the graph

`print_graph`()[source]

Prints the contents of the graph

`add_edge`(from_vertex, to_vertex)[source]

Adds an edge in the graph

`get_code`()[source]

returns the code for the current class

### Weighted Graph¶

class `pygorithm.data_structures.graph.``WeightedGraph`[source]

WeightedGraph object A graph with a numerical value (weight) on edges

`get_weight`(u, v)[source]

Returns the weight of an edge between vertexes u and v. If there isnt one: return None.

`add_edge`(u, v, weight)[source]
Parameters: u – from vertex - type : integer v – to vertex - type : integer weight – weight of the edge - type : numeric
`print_graph`()[source]

Print the graph :return: None

`kruskal_mst`()[source]

Kruskal algorithm for finding the minimum spanning tree of a weighted graph. This version use a union-find data structure. More detailed info here: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm Author: Michele De Vita <mik3dev@gmail.com>

static `kruskal_time_complexity`()[source]

Return time complexity of kruskal :return: string

classmethod `kruskal_code`()[source]

Returns the code for current class

### Weighted Undirected Graph¶

class `pygorithm.data_structures.graph.``WeightedUndirectedGraph`[source]

WeightedUndirectedGraph object A graph with a numerical value (weight) on edges, which is the same for both directions in an undirected graph.

`add_edge`(u, v, weight)[source]

Adds the specified edge to this graph. If the edge already exists, this will only modify the weight (not create duplicates). :param u: from vertex :param v: to vertex :param weight: weight of the edge - type : numeric

`get_edge_weight`(u, v)[source]

Gets the weight between u and v if such an edge exists, or None if it does not. :param u: one edge :param v: the other edge :return: numeric or None

`remove_edge`(edge, other_edge_or_none=None)[source]

Removes the specified edge from the grid entirely or, if specified, the connection with one other edge. Behavior is undefined if the connection does not exist. :param edge: the edge to remove :param other_edge_or_none: an edge connected to edge or none

`gridify`(size, weight)[source]

Constructs connections from a square grid starting at (0, 0) until (size-1, size-1) with connections between adjacent and diagonal nodes. Diagonal nodes have a weight of weight*sqrt(2) :param size: the size of the square grid to construct - type : integer :param weight: the weight between orthogonal nodes. - type: numeric :return: None

### Topological Sort¶

class `pygorithm.data_structures.graph.``TopologicalSort`[source]
`topological_sort`()[source]

function for sorting graph elements using topological sort

`get_code`()[source]

returns the code for the current class

### Check Cycle in Directed Graph¶

class `pygorithm.data_structures.graph.``CheckCycleDirectedGraph`[source]

Class to check cycle in directed graph

`print_graph`()[source]

for printing the contents of the graph

`add_edge`(from_vertex, to_vertex)[source]

function to add an edge in the graph

`check_cycle`()[source]

This function will return True if graph is cyclic else return False

static `get_code`()[source]

returns the code for the current class

### Check Cycle in Undirected Graph¶

class `pygorithm.data_structures.graph.``CheckCycleUndirectedGraph`[source]

Class to check cycle in undirected graph

`print_graph`()[source]

for printing the contents of the graph

`add_edge`(from_vertex, to_vertex)[source]

for adding the edge between two vertices

`check_cycle`()[source]

This function will return True if graph is cyclic else return False

static `get_code`()[source]

returns the code for the current class

## Heap¶

Author: ALLSTON MICKEY Contributed: OMKAR PATHAK Created On: 11th August 2017

### Heap¶

class `pygorithm.data_structures.heap.``Heap`(limit=10)[source]

min-heap implementation as queue

static `parent_idx`(idx)[source]

retrieve the parent

static `left_child_idx`(idx)[source]

retrieve the left child

static `right_child_idx`(idx)[source]

retrieve the right child

`insert`(data)[source]

inserting an element in the heap

`heapify_up`()[source]

Start at the end of the tree (last enqueued item).

Compare the rear item to its parent, swap if the parent is larger than the child (min-heap property). Repeat until the min-heap property is met.

Best Case: O(1), item is inserted at correct position, no swaps needed Worst Case: O(log n), item needs to be swapped throughout all levels of tree

`pop`()[source]

Removes the lowest value element (highest priority, at root) from the heap

`favorite`(parent)[source]

Determines which child has the highest priority by 3 cases

`heapify_down`()[source]

Select the root and sift down until min-heap property is met.

While a favorite child exists, and that child is smaller than the parent, swap them (sift down).

Best Case: O(1), item is inserted at correct position, no swaps needed Worst Case: O(logn), item needs to be swapped throughout all levels of tree

`get_code`()[source]

returns the code for the current class

## Trie¶

Author: MrDupin

### Trie¶

class `pygorithm.data_structures.trie.``Trie`[source]
`insert`(word)[source]

Inserts a word in the trie. Starting from the root, move down the trie following the path of characters in the word. If the nodes for the word characters end, add them. When the last char is added, mark it as a word-ending node.

`search`(word)[source]

Searches for given word in trie. We want to find the last node for the word. If we can’t, then it means the word is not in the trie.

`find_words`(prefix)[source]

Find all words with the given prefix

`find_final_node`(word)[source]

Returns the last node in given word. The process goes like this: Start from the root. For every char in word, go down one level. If we can’t go down a level, then the word doesn’t exist. If we do, and the current char is the last char of the word and the node we are currently at is a word, then we have found the given word.

`build_word_list`(v, cWord)[source]
Recursively builds the list of words.
• v: Node to check
• cWord : The word built up to v

Author: Timothy Moore Created On: 31th August 2017

Defines a two-dimensional quadtree of arbitrary depth and bucket size.

class `pygorithm.data_structures.quadtree.``QuadTreeEntity`(aabb)[source]

This is the minimum information required for an object to be usable in a quadtree as an entity. Entities are the things that you are trying to compare in a quadtree.

Variables: aabb – the axis-aligned bounding box of this entity
`__init__`(aabb)[source]

Create a new quad tree entity with the specified aabb

Parameters: aabb (`pygorithm.geometry.rect2.Rect2`) – axis-aligned bounding box
`__repr__`()[source]

Create an unambiguous representation of this entity.

Example:

```from pygorithm.geometry import (vector2, rect2)

# prints quadtreeentity(aabb=rect2(width=5, height=5, mincorner=vector2(x=0, y=0)))
print(repr(_ent))
```
Returns: unambiguous representation of this quad tree entity string
`__str__`()[source]

Create a human readable representation of this entity

Example:

```from pygorithm.geometry import (vector2, rect2)

# prints entity(at rect(5x5 at <0, 0>))
print(str(_ent))
```
Returns: human readable representation of this entity string
`__weakref__`

list of weak references to the object (if defined)

class `pygorithm.data_structures.quadtree.``QuadTree`(bucket_size, max_depth, location, depth=0, entities=None)[source]

A quadtree is a sorting tool for two-dimensional space, most commonly used to reduce the number of required collision calculations in a two-dimensional scene. In this context, the scene is stepped without collision detection, then a quadtree is constructed from all of the boundaries

Caution

Just because a quad tree has split does not mean entities will be empty. Any entities which overlay any of the lines of the split will be included in the parent of the quadtree.

Tip

It is important to tweak bucket size and depth to the problem, but a common error is too small a bucket size. It is typically not reasonable to have a bucket size smaller than 16; A good starting point is 64, then modify as appropriate. Larger buckets reduce the overhead of the quad tree which could easily exceed the improvement from reduced collision checks. The max depth is typically just a sanity check since depth greater than 4 or 5 would either indicate a badly performing quadtree (too dense objects, use an r-tree or kd-tree) or a very large world (where an iterative quadtree implementation would be appropriate).

Variables: bucket_size – maximum number objects per bucket (before `max_depth`) max_depth – maximum depth of the quadtree depth – the depth of this node (0 being the topmost) location – where this quad tree node is situated entities – the entities in this quad tree and in NO OTHER related quad tree children – either None or the 4 `QuadTree` children of this node
`__init__`(bucket_size, max_depth, location, depth=0, entities=None)[source]

Warning

Passing entities to this quadtree will NOT cause it to split automatically! You must call `think()` for that. This allows for more predictable performance per line.

Parameters: bucket_size (int) – the number of entities in this quadtree max_depth (int) – the maximum depth for automatic splitting location (`pygorithm.geometry.rect2.Rect2`) – where this quadtree is located depth (int) – the depth of this node entities (list of `QuadTreeEntity` or None for empty list) – the entities to initialize this quadtree with
`think`(recursive=False)[source]

Call `split()` if appropriate

Split this quad tree if it has not split already and it has more entities than `bucket_size` and `depth` is less than `max_depth`.

If recursive is True, think is called on the `children` with recursive set to True after splitting.

Parameters: recursive (bool) – if think(True) should be called on `children` (if there are any)
`split`()[source]

Caution

A call to split will always split the tree or raise an error. Use `think()` if you want to ensure the quadtree is operating efficiently.

Caution

This function will not respect `bucket_size` or `max_depth`.

Raises: ValueError – if `children` is not empty
`get_quadrant`(entity)[source]

Calculate the quadrant that the specified entity belongs to.

Touching a line is considered overlapping a line. Touching is determined using `math.isclose()`

• -1: None (it overlaps 2 or more quadrants)
• 0: Top-left
• 1: Top-right
• 2: Bottom-right
• 3: Bottom-left

Caution

This function does not verify the entity is contained in this quadtree.

This operation takes O(1) time.

Parameters: entity (`QuadTreeEntity`) – the entity to place quadrant int
`insert_and_think`(entity)[source]

Insert the entity into this or the appropriate child.

This also acts as thinking (recursively). Using `insert_and_think()` iteratively is slightly less efficient but has more predictable performance than initializing with a large number of entities then thinking is slightly faster but may hang. Both may exceed recursion depth if `max_depth` is too large.

Parameters: entity (`QuadTreeEntity`) – the entity to insert
`retrieve_collidables`(entity, predicate=None)[source]

Find all entities that could collide with the specified entity.

Warning

If entity is, itself, in the quadtree, it will be returned. The predicate may be used to prevent this using your preferred equality method.

The predicate takes 1 positional argument (the entity being considered) and returns False if the entity should never be returned, even if it might collide with the entity. It should return True otherwise.

Parameters: entity (`QuadTreeEntity`) – the entity to find collidables for predicate (`types.FunctionType` or None) – the predicate potential collidables (never `None) list of `QuadTreeEntity`
`find_entities_per_depth`()[source]

Calculate the number of nodes and entities at each depth level in this quad tree. Only returns for depth levels at or equal to this node.

This is implemented iteratively. See `__str__()` for usage example.

Returns: dict of depth level to number of entities dict int: int
`find_nodes_per_depth`()[source]

Calculate the number of nodes at each depth level.

This is implemented iteratively. See `__str__()` for usage example.

Returns: dict of depth level to number of nodes dict int: int
`sum_entities`(entities_per_depth=None)[source]

Sum the number of entities in this quad tree and all lower quad trees.

If entities_per_depth is not None, that array is used to calculate the sum of entities rather than traversing the tree. Either way, this is implemented iteratively. See `__str__()` for usage example.

Parameters: entities_per_depth (dict int: (int, int) or None) – the result of `find_entities_per_depth()` number of entities in this and child nodes int
`calculate_avg_ents_per_leaf`()[source]

Calculate the average number of entities per leaf node on this and child quad trees.

In the ideal case, the average entities per leaf is equal to the bucket size, implying maximum efficiency. Note that, as always with averages, this might be misleading if this tree has reached its max depth.

This is implemented iteratively. See `__str__()` for usage example.

Returns: average number of entities at each leaf node `numbers.Number`
`calculate_weight_misplaced_ents`(sum_entities=None)[source]

Calculate a rating for misplaced entities.

A misplaced entity is one that is not on a leaf node. That weight is multiplied by 4*remaining maximum depth of that node, to indicate approximately how many additional calculations are required.

The result is then divided by the total number of entities on this node (either calculated using `sum_entities()` or provided) to get the approximate cost of the misplaced nodes in comparison with the placed nodes. A value greater than 1 implies a different tree type (such as r-tree or kd-tree) should probably be used.

This is implemented iteratively. See `__str__()` for usage example.

Parameters: sum_entities (int or None) – the number of entities on this node weight of misplaced entities `numbers.Number`
`__repr__`()[source]

Create an unambiguous representation of this quad tree.

This is implemented iteratively.

Example:

```from pygorithm.geometry import (vector2, rect2)

# create a tree with a up to 2 entities in a bucket that
# can have a depth of up to 5.

# add a few entities to the tree

# prints quadtree(bucket_size=1, max_depth=5, location=rect2(width=100, height=100, mincorner=vector2(x=0, y=0)), depth=0, entities=[], children=[quadtree(bucket_size=1, max_depth=5, location=rect2(width=50.0, height=50.0, mincorner=vector2(x=0, y=0)), depth=1, entities=[quadtreeentity(aabb=rect2(width=2, height=2, mincorner=vector2(x=5, y=5)))], children=None), quadtree(bucket_size=1, max_depth=5, location=rect2(width=50.0, height=50.0, mincorner=vector2(x=50.0, y=0)), depth=1, entities=[quadtreeentity(aabb=rect2(width=2, height=2, mincorner=vector2(x=95, y=5)))], children=None), quadtree(bucket_size=1, max_depth=5, location=rect2(width=50.0, height=50.0, mincorner=vector2(x=50.0, y=50.0)), depth=1, entities=[], children=None), quadtree(bucket_size=1, max_depth=5, location=rect2(width=50.0, height=50.0, mincorner=vector2(x=0, y=50.0)), depth=1, entities=[], children=None)])
```
Returns: unambiguous, recursive representation of this quad tree string
`__str__`()[source]

Caution

Because of the complexity of quadtrees it takes a fair amount of calculation to produce something somewhat legible. All returned statistics have paired functions. This uses only iterative algorithms to calculate statistics.

Example:

```from pygorithm.geometry import (vector2, rect2)

# create a tree with a up to 2 entities in a bucket that
# can have a depth of up to 5.

# add a few entities to the tree
static `get_code`()[source]
`__weakref__`