Category: Algorithms

Angular 2 Intro - Pascal's Triangle

5/13/2016

With over 1.1 million developers world wide who use the Angular 1.x framework - it is a framework that undoubtedly became a major web technology used today. It's no surprise that upcoming Angular 2 raises lots of questions about its new features, enhancements and generally the framework itself.

In this article we will focus on a small Angular 2 project where we will take a closer look on Angular 2 development and its key changes. To kick off I would recommend an introduction video presented by AngularConnect

Pascal's Triangle

OK, let's start. First of all - we should start with Pascal's Triangle itself. For those who doesn't know what it is - I would recommend a wikipedia page. The core of Pascal's Triangle is the binomial theorem. Basically, we will construct the triangle by applying the binomial coefficient, according to expression:

The binomial formula itself looks like:

Hence, to determine the particular row of our pascal's triangle we can use the following construction (as stated on wikipedia example):

..and so on. Simple. The result should produce something as follows image:

That's for the pascal's triangle. Let's move on.

Coding options

Before we proceed to actual coding it's worth to mention the coding options we have. You're certainly aware of JavaScript's ES5, ES6, ES2015 or TypeScript. While it's perfectly valid to use ES5 I will stick with TypeScript because of its types and interface features. The Angular 2 itself is actually written in TypeScript.

Angular 1.x - factory, service or provider?

Generally speaking if you need to share your code on a single place (DRY) in multiple controllers in Angular 1 you've had a couple of options such as factory, service or provider. All of them used in specific scenarios.

Angular 2 is much more elegant and all you need to do is to just create a Class. The binomial calculations mentioned above are perfect example of a code that should be placed on a single place - in our example it is in binomial-service.ts. Fair enough. How to use it? Let's compare Angular 1 with Angular 2 by example.

angular.module('app').service('BinomialService', BinomialService);
 
function BinomialService() {
  //..some internal methods..
  this.getPascalTriangle = function(size) {
      var triangle = [];
          for (var i=0;i < size;i++) {
            triangle.push(this.calc(i))
          }
          return triangle;
    }
}

import { Injectable } from '@angular/core';

@Injectable()
export class BinomialService {
  //..some internal methods..
  getPascalTriangle = (size) => {
   var triangle = [];
   for (var i = 0; i < size; i++) {
      triangle.push(this.calc(i));
   }
   return triangle;
  }
}

Notice two things:

@Injectable
export keyword

While export keyword is pretty straightforward (the class simply behaves as a module and is not seen outside without setting it as external) the question comes to oddly looking @Injectable line. This is called a decorator and comes from TypeScript. Angular 2 uses a couple of decorators frequently used, such as:

@Component
@Injectable
@Directive
@Pipe

All of them are nicely described on Angular 2 Cheat Sheet. As documentation says:

Declares that a class has dependencies that should be injected into the constructor when the dependency injector is creating an instance of this class.

..and that's exactly what is happening. As mentioned - out service needs to actually be injected to the constructor of consuming component or class. As you can see in app.component.ts.

@Component({
  selector: 'pt-app',
  templateUrl: './pascal-triangle.html',
  directives: [TriangleParams],
  providers: [BinomialService]
})
export class AppComponent implements OnInits, AfterViewInit  {
  constructor(private _binomialService: BinomialService) { }
 
  // Methods
  refreshData(size: number){
    this.rows = this._binomialService.getPascalTriangle(size);  
  }
}

..couple of things to mention here. The first is the providers: [BinomialService] within the @Component decorator. This tells the Angular to consume the service class. Probably the most important is Dependency Injection part though. Generally speaking dependency injection is very important design pattern and as official Angular docs say: ..we really can't build an Angular application without it. Therefore this line with constructor is very important. Within the class is then accessed by this keyword since it sits on class itself.

Angular 2 basic differences

Before we move on let's just go through some basic differences

<input type="number" ng-model="sizeModel" />

<input type="number" [(ngModel)]="sizeModel" />

..just a note on model part. This annotation: [(ngModel)] is actually called a banana in a box :)

<div ng-bind="message" class="centered"></div>

<div [innerText]="message" class="centered"></div>

This actually is one of the thing I like the most. Instead of having plenty of directives for any particular property you simply use square brackets [] to define any HTML property itself. Dozens of directives from Angular 1 are hence not needed anymore.

<span ng-bind="num" class="num-box" ng-mouseenter="hoverNum = num"
                                    ng-mouseleave="hoverNum = ''"> </span>

<span [innerText]="num" class="num-box" (mouseenter)="hoverNum = num"
                                        (mouseleave)="hoverNum = ''"> </span>

Where square brackets [] define any HTML property then classic brackets () define any HTML element events. Very elegant.

<span ng-repeat="num in row" ng-bind="num" class="num-box"
      ng-mouseenter="hoverNum = num" ng-mouseleave="hoverNum = ''">
</span>

<span *ngFor="let num of row"  [innerText]="num" class="num-box"
      (mouseenter)="hoverNum = num" (mouseleave)="hoverNum = ''">
</span>

Here it's very important to notice a star * before ngFor. Any star represents a structural directive. Structural directive means it actually changes or defines the DOM structure itself. There are couple of other structural directives such as:

*ngFor
*ngIf
*ngSwitch

As mentioned earlier - it's highly recommended to check the Angular 2 cheat sheet which nicely summarizes features.

Unidirectional Data Flow

The data binding in Angular 1 was based on well known digest cycles. Angular 2 uses something called unidirectional data flow. Forget about $apply, repeated digest cycle, $watch.

Facebook's Flux is also based on an idea of unidirectional data flow. Basically it says that you can no longer update the view after it has been composed. This process is much better when it comes to performance since it avoids repeated $digest cycles.

Component life cycle hooks

As stated in official documentation:

"A Component has a lifecycle managed by Angular itself. Angular creates it, renders it, creates and renders its children, checks it when its data-bound properties change, and destroys it before removing it from the DOM.
Angular offers component lifecycle hooks that give us visibility into these key moments and the ability to act when they occur."

When you look at the app.component.ts:

@Component({
  selector: 'pt-app',
  templateUrl: './pascal-triangle.html',
  directives: [TriangleParams],
  providers: [BinomialService]
})
export class AppComponent implements OnInits, AfterViewInit  {

@Component itself is a decorator that provides meta data for its class which is actually being exported.

The OnInits and AfterViewInit are our "hook" moments. Angular follows its internal sequence of specific moments which forms its life cycle and hooks allow you to tap into these moments to actually build a project.

Here we have a code of our main component where we also need to access the child component params.component.ts and also the binomial-service.ts:

import { Component, OnChanges, Input, Output, 
         View, EventEmitter, OnInit } from '@angular/core';
import { BinomialService } from './binomial-service';
import { ViewChild, AfterViewInit } from '@angular/core';
import { TriangleParams } from './params.component';

@Component({
  selector: 'pt-app',
  templateUrl: './pascal-triangle.html',
  directives: [TriangleParams],
  providers: [BinomialService]
})
export class AppComponent implements OnInits, AfterViewInit  {
  constructor(private _binomialService: BinomialService) { }
  @ViewChild(TriangleParams) triangleParams:TriangleParams;
  
  rows: [];
  // Methods
  refreshData(size: number){
    this.rows = this._binomialService.getPascalTriangle(size);  
  }
  // Lifecycle hooks
  ngOnInit(){
    this.rows = [];
  }
  
  ngAfterViewInit() {
    this.refreshData(this.triangleParams.triangleSize); 
  }
}

Notice that to access the params component we have to:

import { TriangleParams } from './params.component';
Set it in directives array - directives: [TriangleParams],
Inherit specific hooks to access our child component - implements AfterViewInit
Define @ViewChild(TriangleParams) triangleParams:TriangleParams;
..and finally use it by this.triangleParams.triangleSize

Change Detection

While the official documentation still leaves the change detection section empty it is pretty natural to follow property setter as you can see here:

get sizeModel() {
      return this.triangleSize;
  }

  set sizeModel(value) {
    this.triangleSize = value;
    
    if ((this.valid = this.validate()) == false) return;
    
    this.sizeChange.emit({
      value: this.triangleSize
    });
  }

and a view which looks like this:

<nav class="centered">
  Triangle size = <input type="number" [(ngModel)]="sizeModel" />
</nav>

As you can see - every time model changes the property setter is triggered. You can also notice the event emitter being triggered which is going to be described on the following lines.

Communication between components

You've surely came across a need to communicate between controllers in Angular 1. Features such as $broadcast or $emit. These do not exist anymore in Angular 2. We have couple of other options though and they are well described on official documentation.

In our demo we just need to notify a parent component about changes in child component. For which we will EventEmitters. So basically within the child component:

import { Component, OnChanges, Input, Output, View, 
         EventEmitter, OnInit } from '@angular/core';

@Component({
  selector: 'triangle-params',
  templateUrl: './triangle-params.html'
})
export class TriangleParams {
  @Input() triangleSize;
  @Output() sizeChange = new EventEmitter(); 
  //..
  set sizeModel(value) {
    //..
    this.sizeChange.emit({
      value: this.triangleSize
    });
  }

}

..we have to define the target property by which the communication will be performed. That's the @Output() line. Again it is worth reading through the official documentation. To quote:

Input properties usually receive data values. Output properties expose event producers, such as EventEmitter objects.

..which is exactly what we do here. We are exposing an event procedure. So in the parent component's view we can define the (sizeChange) event:

<triangle-params [triangleSize]="6" 
                 (sizeChange)="sizeChanged($event);"></triangle-params>

..which triggers our sizeChanged method within the parent component class and passes $event as an argument which we emitted from the child component including the new value.

@Component({
  selector: 'pt-app',
  templateUrl: './pascal-triangle.html',
  directives: [TriangleParams],
  providers: [BinomialService]
})
export class AppComponent implements OnInits, AfterViewInit  {
  //..
  sizeChanged(event) {
    this.refreshData(event.value);
  }
  //..
}

As mentioned above. This process is well described on the official documentation.

Summary

Angular 2 introduces lots of changes. It requires some time to "digest" them and be able to actually develop a project. It's all worth it though. It is much more elegant and faster. Check out the GitHub project and play with plunker where you can test and experiment.

0 Comments

Simple Math Evaluator: Infix to Postfix Converter and calculator (Reverse polish notation)

3/28/2016

2 Comments

A common way to express a mathematical expression is usually consisted by operators being placed between operands. For example:

f(x) = 2 * 5 + 3 - 2 * (8 / (4 / 2)) + (3 * 3)

This form of defining the expression is called Infix notation. As stated on wikpedia:

Infix notation is the notation commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands – "infixed operators" – such as the plus sign in "2 + 2".

Another way of defining the expression is called Reverse Polish notation (or commonly Postfix notation) where every operator follows all its operands.

For example:

2 * 5 + 3 - 2 * (8 / (4 / 2)) + (3 * 3)

equals to:

2 5 * 3 + 2 8 4 2 / / * - 3 3 * +

Notice that as long as every operator has a fix number of operands there's no need for parenthesis. Also it is more difficult to parse an Infix expression by computers than postfix. What I really like the most on Postfix notation is how nicely it fits the usage of Stack.

This article shows how to convert a classic infix notation to the postfix notation so it can subsequently be evaluated by postfix math parser. Our JavaScript project consists of 3 modules:

common.js
infix.js
postfix.js

..and main.js which just handles the modules. All of these can of course be found on GitHub repository.

The algorithm for conversion the infix to postfix is very nicely described by Shunting-yard algorithm on the Wikipedia. Invented by famous Edsger Wybe Dijkstra. Very nice article can also be found on this page including the examples in Python. Generally speaking you iterate through the postfix tokens and perform a given task for a given operator, operand, parenthesis, function etc. An example from my simple JavaScript code:

Each JavaScript module is responsible for a given task. The infix.js exposes a single method toPostfix() which takes only a single argument containing the infix expression. Common.js contains just a simple functions commonly used in the project and postfix.js is responsible for evaluating the postfix expression.

One thing to mention from the JavaScript perspective is the following line:

If you're not sure why exactly I use the not operator please check out my previous blog article explaining this topic.

Plunker and GitHub

As usual all is available on my GitHub repository and also accessible to play with on Plunker.

2 Comments

Animated Heap-Sort with AureliaJS

2/20/2016

0 Comments

If you're not aware about AureliaJS it's time to be aware about this amazing framework. Like Angular, Meteor, Polymer, Knockout and others it is a MV* framework for building the next generation web applications. To quote the authors:

Aurelia is a next generation UI framework. Whether you're building apps for the browser, mobile or desktop, Aurelia can enable you to not only create amazing UI, but do it in a way that is maintainable, testable and extensible.

..and not only that. It gets even more interesting here:

Aurelia is just JavaScript. However, it's not yesterday's JavaScript, but the JavaScript of tomorrow. By using modern tooling we've been able to write Aurelia from the ground up in ECMAScript 2016. This means we have native modules, classes, decorators and more at our disposal...and you have them too.

You can find more interesting facts and docs on the official page. This article shows how to present the Heap-Sort algorithm in an animated way in JavaScript built upon the AureliaJS framework.

Heap Sort

I believe I don't have to introduce the heap sort. It is notoriously known sorting algorithm. The wikipedia page speaks for all and if you're a beginner I would recommend you the MIT course about Heaps and Heap Sort which is very nicely explained:

Nice thing about heap sort is that it's relative fast and runs in O(n + n*log(n)) = O(n*log(n)).

In our example it's being implemented inside the engine.js file. Notice the ES6 way of defining the module where we export only those parts we want to:

..which is later on imported by calling the:

In the current ES5 way you would write something like this instead:

The animation itself is being done using CSS3 transitions. It is easy and very fast way how to animate css properties. The key here are the following css lines:

The main application class is pretty straightforward. We have just a constructor that initializes the properties and then two methods generate and heapSort that corresponds with buttons on view layer. The heap sort itself with a bunch of helper functions is located in the engine module.

Result

Now the funny part. See and play with the result. As usual you can play with Plunker and see the complete sources on GitHub.

0 Comments

ReactJS & Sieve of Eratosthenes - Prime Numbers

12/27/2015

0 Comments

The Sieve of Eratosthenes is an ancient algorithm for finding prime numbers up to a given limit. As stated in Wikipedia.

It is quite simple but awesome. As always I like simple solutions. It is not the fastest though - runs in O(NLog(LogN)) but it's robust enough. By the way, the fastest prime numbers generator is currently the Sieve of Atkin.

So what do we in this article? We're going to create a simple page with one input that represents a given limit N and marks all prime numbers P (so that P <= N) on a sequence of numbers that is rendered using ReactJS.

Why React? Well, one of the key React's feature is the Virtual DOM. Basically, once you update the model the engine renders only what's necessary and skips the elements that have not been updated. This is very powerful feature. For those folks who haven't heard much about React I recommend following video to make a better picture.

The code

OK, let's get to coding. The algorithm itself is pretty straightforward.

When you check the project on GitHub you'll also notice the ugly initial array fill

I know I could use the Array.prototype.fill() as part of ECMAScript 6 but since this particular function is not yet supported by all browser I'm gonna stick up with old loop method.

The React's part is quite simple. We're gonna create 2 classes. One that represents the whole view elements and one that represents the dynamic array being rendered as a sequence of spans.

The key method is handleSubmit. Notice the setState function that sets the model list array to a newly created array of booleans. If you start with limit of e.g. 100 and later increase the limit to e.g. 130 you'll nicely see how the previously rendered elements are staying intact. Only newly inserted prime numbers are being signalized by color animation. That's because React knows what changed in the model list array.

The array view class is then very simple.

Check it out

As usual the whole project is at your disposal on plunker and also GitHub. Enjoy. By the way - a good tip for online JSX compiling service - Babeljs.io.

0 Comments

<<Previous

Angular 2 Intro - Pascal's Triangle

Pascal's Triangle

Coding options

Angular 1.x - factory, service or provider?

Angular 2 basic differences

Unidirectional Data Flow

Component life cycle hooks

Change Detection

Communication between components

Summary

Simple Math Evaluator: Infix to Postfix Converter and calculator (Reverse polish notation)

Plunker and GitHub

Animated Heap-Sort with AureliaJS

Heap Sort

Result

ReactJS & Sieve of Eratosthenes - Prime Numbers

The code

Check it out

About

Categories

Archives

Ivan Sivak

Stack overflow

LinkedIn

Email

GitHub

Angular 2 Intro - Pascal's Triangle﻿

Pascal's Triangle

Coding options

Angular 1.x - factory, service or provider?

Angular 2 basic differences

Unidirectional Data Flow

Component life cycle hooks

Change Detection

Communication between components

Summary

Simple Math Evaluator: Infix to Postfix Converter and calculator (Reverse polish notation)

Plunker and GitHub

Animated Heap-Sort with AureliaJS

Heap Sort

Result

ReactJS & Sieve of Eratosthenes - Prime Numbers

The code

Check it out

About

Categories

Archives

Ivan Sivak

Stack overflow

LinkedIn

Email

GitHub

Angular 2 Intro - Pascal's Triangle