TypeScript Library for Data Structure, Algorithms and Utilities

INTRODUCTION

This project is target to build a library (abbrv: lib) for Data Structures, algorithms and Utilities.

• The Data Structure part, including List, Tree, Graph, and others.
• The Algorithm part, including sorting, searching and others.
• The Utility part, including finance methods, string utility, number utility, HTML element related methods, etc.

The library written with TypeScript.

HOW TO USE

To use this library in your package, simply run following NPM command:

npm install actslib --save

to add this library into your own topic.

Code snippet 1: calculate the FV (further value) with interest rate 1% and 12 periods:

import { FinanceMethods } from 'actslib';

const rst = FinanceMethods.FV(100, 0.01, 12);
expect(rst).toEqual(112.68); // FV is 112.68

Code snippet 2: show the way to use the Matrix:

import { Matrix, MatrixPosIntf } from 'actslib';

let matrix: Matrix = new Matrix(10, 10);
let arpos = matrix.getSlashOutputPos();

Code snippet 3: show the way to use the Quick-Sorting algorithm:

import { QuickSort } from 'actslib';

let arArray: number[] = [10, 3, 26, 1, 35];
QuickSort(arArray);

REFERENCE

The library in the project actually based the understanding when learning the books below:

• Introduction to Algorithms, Third Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
• Programming Pearls, by Jon Bentley
• More Programming Pearls, By Jon Benley
• 数据结构 用面向对象方法与C++描述， Tsinghua University Press
• 编程之美, Publishing House of Electronics Industry
• More to come.

CONTENT

Folder lib (src\lib) contains the kernel part of the whole library. It consists with several sub folders, and it has been exported via index.ts respectively. Folder dist (dist) contains the compiled js files.

UNIT TESTS

Unit test is the mechanism to ensure the quality. It was supported by using Karam.

Run 'npm test' to trigger the unit tests.

HOW TO DEBUG UNIT TESTS

There ar two steps away to debug unit tests in VS Code.

• Step 1. Start the Karma Runner via the command below

npm run debugtest

• Step 2. In VS Code, click 'Debug Unit Tests'. VS Code now attach to the Chrome window and debugging is waiting.

DEMO APP

Demo app was located in another repository.

Try the demo app online now via a single click.

DATA STRUCTURE

LIST

Interface IList defines the generic operations supported by List.

• Class SequenceList implements the Sequence List.
• Class LinkList implements the Link List.
• Class StaticLinkList implements the static link list.

STACK AND QUEUE

Interface IStack and IQueue defines the generic operations for Stack and Queue respectively.

• Class SequenceStack implements the Sequence Stack.
• Class LinkStack implements the Link Stack.

TREE

Interface ITree defines the generic operations and attributes supported by Tree.

Interface IBinaryTree define the generic operations and attributes for Binary Tree.

• Class BinaryTree implements the Binary Tree.
• Class BinarySearchTree implements the Binary Search Tree.
• Class BinaryThreadTree implements the Binary Thread Tree.
• More to come.

GRAPH

Interface IGraph defines the generic operations and attributes supported by Graph, such as DFS, BFS, and so on.

Interface IGraphVertex defines the interface for Vertex in the graph.

Interface IGraphEdge defines the interface for the Edge in the graph.

• Class Graph defines the implementation for the Graph with Adjace Matrix.
• Class GraphAdjaceList defines the implementation for the Graph with Adjact List.
• More to come.

ALGORITHM

• The algorithm KMP which offer the functionality to search source string from the target string.
• The algorithm InsertionSort using the insertion sort upon the array.
• The algorithm BinaryInsertSort based on InsertionSort but improves the way to search for suitable position to insert.
• The algorithm BubbleSort using the bubble-sort on the array: pickup the biggest and move it to the tail of the array.
• The algorithm QuickSort based on BubbleSort but use recursive way to handle two parts of the array.
• The algorithm SelectionSort choose the min (or max) from the unsorted part and append it to the sorted part.
• The algorithm CountingSort give an item a n-th position because there are n-1 item less (or bigger) than it. This algorithm suits only for number based array.
• The algorithm MergeSort uses divide and consquer methology which try to split the arry and merge it to final results.
• The algorithm HeapSort try to build maximum (or minimum) heap for the unsorted part, and fetch the root node to the sorted part.
• More to come.

SUBJECT

• The subject MaximumSubArray try to fetch out the maxium sub array from an existing array.
• The subject PriorityQueue try to define a priority queue which can be simulated the real scenario.
• The subject Matrix defines the matrix object.
• The subject Polynomial defines the polynomial object.
• The subject SparseMatrix defines the Sparse Matrix object.
• The subject ChineseChessGeneralsProblem provides several solutions to the Generals issue in Chinese Chess.
• The subject PanCakeSort provides the solution to sort the pan cakes.
• The subject Formula provides the Math Expression Parser.
• The subject RPN provides the support of Reverse Polish Notation.
• The subject FinanceMethods provides the support of methods used in Finance area, including Further Value, Present Value, FV of Annity, etc.
• More to come.

UTILITIES

• The utility DateUtility provides some helpful methods on Date part, including days between, serialize/deserialize with string, etc.
• The uitlity UIUtility provides some helpful methods operation on HTML element, including add/remove CSS classes, etc.
• The uitlity StringUtility provides some helpful methods operation on strings, including check password length, check duplications, etc.
• The uitlity NumberUtility provides some helpful methods operation on numbers, including adding prefixes, rounding with specified digitals, etc.

PROGRESS

The progress of the project shown in the table below.

#|Content|Status|UT Status|Comment ----:|:----|:-----|:-----|:----- 1|SequenceList|Finished|Passed|Question left: search? 2|LinkList|Finished|Passed|Question left: search? 3|SequenceStack|In Process|Passed|Question left: search? 4|Matrix|Finished|Passed|Question left: search? 5|Set|Finished|2 Cases failed|Question left: search? 6|SequenceQueue|Finished|Passed|Question left: search? 7|PriorityQueue|Finished|Passed|Question left: search? 8|Dictionary|Finished|Passed|Question left: search? 10|Graph|In Process|In Process|Question left: how to demonstrate the Graph for demo? 11|Graph with Adjace List|In Process|In Process|Question left: how to demonstrate the Graph for demo? 12|Binary Search Tree|n/a|n/a|Not started yet 13|B Tree|n/a|n/a|Not started yet| 14|Red Black Tree|n/a|n/a|Not started yet| 15|Strassen Algorithm|n/a|n/a|Not started yet| 16|Birthday Theory|n/a|n/a|Not started yet| 17|Ball and Box|n/a|n/a|Not started yet| 18|Hire on-line|n/a|n/a|Not started yet| 19|Priority Queue|n/a|n/a|Not started yet| 20|Hash algorithms|n/a|n/a|Not started yet| 21|van Emde Boas Tree|n/a|n/a|Not started yet| 22|Kruskal Algorithm|n/a|n/a|Not started yet| 23|Prim Algorithm|n/a|n/a|Not started yet 24|Bellman-Ford Algorithm|n/a|n/a|Not started yet| 25|Dijkstra Algorithm|n/a|n/a|Not started yet| 26|Floyd-Warshall Algorithm|n/a|n/a|Not started yet| 27|Radix sort|n/a|n/a|Not started yet| 28|Bucket sort|n/a|n/a|Not started yet| 40|Formula|DONE|DONE|Formula.evaluate can be used to workout the figures| 41|Finance Methods|In Process|n/a|FV, FVIF, PV, PVIF, FV of ordinary annity; FV of deferred annity; FV of annity in advance; n/a|

CONTRIBUTORS

• Alva Chien(Hongjun Qian) | 钱红俊 Contact me via Mailbox: [email protected] if necessary;

Licence

MIT