DEV Community

Ali B
Ali B

Posted on

Typescript With a Simple Example

Typescript is an open-source programming language that compiles to Javascript. Typescript is developed and is supported by Microsoft.

Why Typescript

Typescript provides a lot of features that makes it a superior option to Javascript. To name a few,

  • It introduces type-safety
  • Supports namespaces, modules, interfaces and declaration files
  • Class methods and properties can be declared using private and protected keywords
  • Provides code completion and IntelliSense
  • Integrates with popular Javascript libraries (React, Angular, Vue, Express, etc.)

Example

The example we're going to be looking at is an implementation for a Heapsort. The requirements are as follows:

  • we want to be able to sort an array of any type
  • we want to be able to specify the order of sort (ascending or descending)
  • we want to be able to provide a our own comparison function as a callback

To lay the ground for our requirements, we start by defining an interface that represents the sort options.

We expect our compare function to take in two input parameters. Furthermore, we want it to return 0 if the values are equal, 1 if the first value is larger than the second value and -1 otherwise.

interface SortOptions{

  order: "asc" | "desc";
  compare: ICompareFunction;

}

// describes the input and output expected from a compare function
interface ICompareFunction {

    (a: any, b: any): number;

}

These are the main functions that will be used to implement our Heapsort.

function heapsort(data: any[], options?: SortOptions): void{}
function heapify(data: any[], length: number, options: SortOptions): void{}
function bubbleDown(data: any[], curr: number, length: number, options: SortOptions): void{}

We use a ? sign to denote optional input.

Implementation

heapsort

The function 'heapsort' takes in an array sorts it using the Heapsort algorithm.

If we are sorting in ascending order, we want to build a max heap, otherwise we build a min heap. We achieve this by calling our 'heapify' function.

Then, we swap the max or min with the last element of the heap and call the our 'bubbleDown' function on the root of the heap (first element in the array). We repeat this step for the length of the array.

If the 'options' parameter is not provided, we set the options manually to a default value.

  function sortHeap(data: any[], options?: SortOptions): void{

    //set default options if not provided
    if(!options){
      options =  {
        compare : defaultCompare,
        order: 'asc'
      };
    }   
    if(!options.order)
      options.order = 'asc';

    if(!options.compare)
      options.compare = defaultCompare;    

    //turn array into a heap
    heapify(data, data.length, options);

    swap(data, data.length - 1 , 0);

    for(let i = data.length - 2; i >= 0; i--){
      bubbleDown(data, 0, i + 1, options);

      //swap max or min with the last element in the heap
      swap(data, i, 0);
    }
  }

 //helper functions
 function swap(data: any[], i:number, j:number){
    let temp = data[i];
    data[i] = data[j];
    data[j] = temp;
 }

 //default compare
 function defaultCompare (a: number, b: number): number{
    if(a == b)
        return 0;
    return (a < b) ? -1 : 1;
 }

heapify

The 'heapify' function rearranges an array into in a min or max heap. We achieve this but bubbling down all non-leaf nodes of the heap, as in all nodes in the first half of the array.

function heapify(data: any[], length: number, options: SortOptions): void{

   for(let i = length/2; i >= 0; i--)
      this.bubbleDown(data, Math.floor(i), length, options);
}

bubbleDown

The function 'bubbleDown' takes in a heap and Recursively bubbles down the elements at index 'curr' until index 'length'. We also provide the sort options described above.

 private bubbleDown(data: any[], curr: number, length: number, options: SortOptions): void{

    const asc: boolean = (options && options.order == "desc") ? false : true;

    //base case
    if(!data || curr >= length)
        return;

    //indexes for left and right node 
    const l: number = (2 * curr + 1 >= length) ? null : 2 * curr + 1;
    const r: number = (2 * curr + 2 >= length) ? null : 2 * curr + 2;

    //find max or min element
    let maxmin: any;
    if(!data[l] && !data[r])
        return ;
    else if(!data[l])
      maxmin = data[r];
    else if(!data[r])
      maxmin = data[l];
    else{
      const result: number = options.compare(data[l], data[r]);
      maxmin = ((result < 0 && asc) || (result > 0 && !asc)) ? data[r] : data[l];
    }

    //compare max/min of child nodes with current element
    const result: number = options.compare(data[curr], maxmin);
    if((asc &&  result < 0) ||  (!asc && result > 0 )) {

      //swap with largest or smallest element (depending on asc) and swap index
      let temp = data[curr];
      data[curr] = maxmin ;

      //swap r or l with curr
      curr = options.compare(maxmin, data[l]) === 0 ? l : r;
      data[curr] = temp;
      return this.bubbleDown(data, curr, length, options);
    }

  }

Hopefully this article demonstrated that Typescript provides much needed sanity and structure that is generally lacking when developing large scale applications using Javascript.

The code above along with some other sorting algorithms is available on Github.

If you're sold on Typescript this is a good place to start.

Type-safely!

Discussion (0)