# abstract-data-types

The future of this module is that it will be able to return instances of the following abstract data types:

**Queue***This is currently implemented***Linked List***This is currently implemented***Stack***This is currently implemented***Binary Tree***This is currently implemented***Binary Search Tree***This is currently implemented***Graph****Hash Table****Heap**

# Installation

```
$ npm install abstract-data-types
```

# Getting Started

The individual abstract data types are instantiated from factory functions that exist as properties of the *abstract-data-types* module. The module can be accessed as follows.

```
var adt = require('abstract-data-types');
```

The individual factory functions can be used to create instances of the abstract data types like this.

```
var q = adt.createQueue(); // To create an empty Queue
var ll = adt.createLinkedList(); // To create an empty Linked List
var s = adt.createStack(); // To create an empty Stack
var bt = adt.createBinaryTree(); // To create an empty Binary Tree
var bst = adt.createBinarySearchTree(); // To create an empty Binary Search Tree
var g = adt.createGraph(); // To create an empty Graph
var ht = adt.createHashTable(); // To create an empty Hash Table
var h = adt.createHeap(); // To create an empty Heap
```

The rest of this document explains each of the operations that can be performed these abstract data type instances.

## Queue

This *Queue* is implements all the standard Queue operations. These are:

**enqueue**adds a new item to the back of the queue**dequeue**returns the item at the front of the queue and removes it from the queue**front**returns the item at the front of the queue**size**returns the number of items in the queue**isEmpty**determines whether the queue is empty and returns true if it is and false otherwise

#### Enqueue

The *enqueue* operation adds a new item to the back of the queue. To do this call the *enqueue* method on a Queue instance passing it the data item you wish to add to the Queue.

```
q.enqueue(item);
```

#### Dequeue

The *dequeue* method returns the item at the front of the queue and removes that item from the queue. To do this call *dequeue* on a queue object.

```
var frontItem = q.dequeue();
```

If *dequeue* is called on an empty queue, the following error is thrown.

```
new Error('adt-queue.dequeue(): Tried to dequeue an empty queue!');
```

#### Front

The *front* method returns the item at the front of the queue, but unlike *dequeue* it does not remove it from the queue.

```
var frontItem = q.front();
```

If *front* is called on an empty queue, the following error is thrown.

```
new Error('adt-queue.front(): Tried to get the front of an empty queue!');
```

#### IsEmpty

The *isEmpty* method is a boolean function that, when called on a queue, returns *true* if the queue is empty and false otherwise.

```
q.isEmpty();
```

## Linked List

The *Linked List* implements all of the standard Linked List functions. These are given below:

**add**adds a new item to the list at a specific position**remove**removes an item from the list at a specific position**get**returns the item at at a specific position in the list**size**returns the number of items in the List**isEmpty**determines whether the List is empty and returns true if it is and false otherwise

The postion index starts from 0.

#### Add

The add method takes the item to be added to the list and the position that the item should be added in. If the position is less than or equal to 0, the item is added to the front of the list. If the position is greater than or equal to the size of the list, the item is added to the end of the list.

```
ll.add(position, item);
```

#### Remove

The remove method removes the item at a specific position in the list. If the position requested is less than 0 or geater then or equal to the length of the list, an error is thrown.

```
ll.remove(position);
```

#### Get

The get method returns the item at a specific position in the list. If the position requested is less than 0 or geater then or equal to the length of the list, an error is thrown.

```
ll.get(position);
```

#### Size

The size method returns the number of items in the list.

```
ll.size();
```

#### IsEmpty

The *isEmpty* method is a boolean function that, when called on a list, returns *true* if the list is empty and false otherwise.

```
ll.isEmpty();
```

## Stack

The *Stack* implements all of the standard Stack functions. These are given below:

**push**adds a new item to the top of the stack**pop**returns the item at the top of the stack and removes it from the stack**top**returns the item at the top of the stack and leaves it on the stack**size**returns the number of items in the stack**isEmpty**determines whether the stack is empty and returns true if it is and false otherwise

#### Push

The push method adds a new item to the top of the stack. It also returns the stack so that push opertations can be chained.

```
s.push(item);
```

#### Pop

The pop method returns the item at the top of the stack and removed it from the stack.

```
s.pop();
```

#### Top

The pop method returns the item at the top of the stack and leaves it on the stack.

```
s.top();
```

#### Size

The size method returns the number of items in the stack.

```
s.size();
```

#### IsEmpty

The *isEmpty* method is a boolean function that, when called on a stack, returns *true* if the stack is empty and false otherwise.

```
s.isEmpty();
```

## Binary Tree

The *Binary Tree* in this module implements the standard methods of the Binary Tree abstract data type. These methods are:

**isEmpty**determines whether the tree is empty and returns true if it is and false otherwise**getRootItem**returns the item at the root of the tree**setRootItem**updates the item at the root of the tree**getLeftTree**returns the left sub tree**getRightTree**returns the Right sub tree**attachLeft**attaches at tree or an item as the left sub tree**attachRight**attaches at tree or an item as the right sub tree**detachLeft**removes the left sub tree**detachRight**removes the right sub tree**count**returns the number of nodes in the tree

#### Creation

The factory function used to create a new *Binary Tree* can be called in the following 2 ways:

**By passing in no arguments**- this will create an empty tree.var bt = adt.createBinaryTree();

**By passing in and item**- this will create a single node tree with the item at the root.var bt = adt.createBinaryTree(item);

#### Is Empty

The *isEmpty* method is a boolean function that, when called on a tree, returns *true* if the tree is empty and false otherwise.

```
bt.isEmpty();
```

#### Get Root Item

This method returns the item at the root of the tree and is called as follows.

```
bt.getRootItem();
```

If this method is called on an empty tree it throws an error as follows.

```
throw new Error('adt-binary-tree.getRootItem(): Tried to get the root item of an empty tree');
```

#### Set Root Item

This method puts an item at the root of the tree and is called as follows.

```
bt.setRootItem(item);
```

#### Get Left Tree

This method returns the left sub tree.

```
bt.getLeftTree();
```

If this method is called on an empty tree it throws an error as follows.

```
throw new Error('adt-binary-tree.getLeftTree(): Tried to get the left tree of an empty tree');
```

#### Get Right Tree

This method returns the right sub tree.

```
bt.getRightTree();
```

If this method is called on an empty tree it throws an error as follows.

```
throw new Error('adt-binary-tree.getLeftTree(): Tried to get the left tree of an empty tree');
```

#### Attach Left Tree

This method can be called by either passing in another *Binary Tree*, or by passing in an item that is not a *Binary Tree*.

If a *Binary Tree* is passed in, that tree will be attached as the left sub tree. The method is called like this.

```
bt.attachLeft( tree );
```

If a non *Binary Tree* item is passed in, a new single node tree is created out of that item and this new tree is attached as the left sub tree.

```
bt.attachLeft( item );
```

If this method is called on an empty tree it throws an error as follows.

```
throw new Error('adt-binary-tree.attachLeft(): Attempt to attach a left sub tree to an empty tree');
```

#### Attach Right Tree

This method can be called by either passing in another *Binary Tree*, or by passing in an item that is not a *Binary Tree*.

If a *Binary Tree* is passed in, that tree will be attached as the right sub tree. The method is called like this.

```
bt.attachRight( tree );
```

If a non *Binary Tree* item is passed in, a new single node tree is created out of that item and this new tree is attached as the right sub tree.

```
bt.attachRight( item );
```

If this method is called on an empty tree it throws an error as follows.

```
throw new Error('adt-binary-tree.attachRight(): Attempt to attach a right sub tree to an empty tree');
```

#### Detach Left Tree

This method is used to remove the left sub tree from the main tree. It also returns the tree that it detaches. it is called as follows.

```
bt.detachLeft();
```

If this method is called on an empty tree it throws an error as follows.

```
throw new Error('adt-binary-tree.detachLeft(): Attempt to detach the left sub tree of an empty tree');
```

#### Detach Right Tree

This method is used to remove the right sub tree from the main tree. It also returns the tree that it detaches. it is called as follows.

```
bt.detachRight();
```

If this method is called on an empty tree it throws an error as follows.

```
throw new Error('adt-binary-tree.detachRight(): Attempt to detach the right sub tree of an empty tree');
```

#### Count

This method returns the number of nodes in the tree.

```
bt.count();
```

## Binary Search Tree

The *Binary Search Tree* implements the following Binary Search Tree methods.

**insert**inserts a new item into the search tree in the correct position, maintaining the validity of the binary search tree**delete**removes an item from the tree maintaining the validity of the binary search tree**retrieve**returns a specific item in the tree**isEmpty**determines whether the tree is empty and returns true if it is and false otherwise**getRootItem**returns the item at the root of the tree**getLeftTree**returns the left sub tree**getRightTree**returns the Right sub tree**count**returns the number of nodes in the tree

#### Insert

This method inserts an item into the tree and makes sure that the validity of the binary seach tree is maintained.

```
bst.insert(item);
```

The search key used to determine the position of an item within the binary search tree as it is being inserted is derived from the item in the following way.

If the item is null, the item is not inserted into the tree and the following error is thrown.

throw new Error('adt-binary-search-tree utils.getKey(): item is null');

If the item is an object that does not have a property named 'key', the item is not inserted into the tree and the following error is thrown.

throw new Error('adt-binary-search-tree utils.getKey(): item has no key');

If the item is an object with a property named 'key' and that key property is null, the item is not inserted into the tree and the following error is thrown

throw new Error('adt-binary-search-tree utils.getKey(): item is null');

If the item is an object with a property named 'key' and that key property is an object, the item is not inserted into the tree and the following error is thrown

throw new Error('adt-binary-search-tree utils.getKey(): item.key is an object');

If the item is an object with a property named 'key' and this key property is not an object and is not null, the value of this key property is used as the item's search key within the tree.

If the item is not an object and is not null, the item value is used as the item's search key within the tree.

#### Delete

This method removes the item identified by the parameter 'key' from the tree and makes sure that the validity of the binary seach tree is maintained.

```
bst.delete(key);
```

If the key does not exist in the tree, the following error is thrown.

```
throw new Error('adt-binary-search-tree.delete(): The key is not in the tree');
```

#### Retrieve

This method returns the item identified by the parameter 'key' from the tree and leaves the tree unchanged.

```
bst.retieve(key);
```

The method returns *null* if the key does not exist in the tree.

#### Is Empty

The *isEmpty* method is a boolean function that, when called on a tree, returns *true* if the tree is empty and false otherwise.

```
bst.isEmpty();
```

#### Get Root Item

This method returns the item at the root of the tree and is called as follows.

```
bst.getRootItem();
```

If this method is called on an empty tree it throws an error as follows.

```
throw new Error('adt-binary-search-tree.getRootItem(): Tried to get the root item of an empty tree');
```

#### Get Left Tree

This method returns the left sub tree.

```
bst.getLeftTree();
```

If this method is called on an empty tree it throws an error as follows.

```
throw new Error('adt-binary-search-tree.getLeftTree(): Tried to get the left tree of an empty tree');
```

#### Get Right Tree

This method returns the right sub tree.

```
bts.getRightTree();
```

If this method is called on an empty tree it throws an error as follows.

```
throw new Error('adt-binary-search-tree.getLeftTree(): Tried to get the left tree of an empty tree');
```

#### Count

This method returns the number of nodes in the tree.

```
bst.count();
```