DEV Community: agrem28

Anime.js

agrem28 — Tue, 19 Jan 2021 06:04:16 +0000

Anime.js is a lightweight JavaScript animation library with a simple, yet powerful API. It works with CSS properties, SVG, Dom attributes and JavaScript Objects. Anime.js has many customizable properties that can manipulate and transform anything you can put on a screen. Virtually everything is done within the single anime function which takes an object as its argument. This object is the basis for the abundance of customization options that anime.js offers. We will talk about a few important ones now.

Options

Targets

The first and most important property that every anime call should have is targets. It selects which DOM elements to apply the animation to. There are a few ways to select targets. First is to directly grab a single element from by using a string using CSS selector formats such as ’div’ or ’.className’. The next is to target a JavaScript object which is then used as data for an element. The final way is to target an array of elements, objects, or any combination thereof. For example you could grab all the div elements and apply the same animation to them by using document.querySelector(‘div’) and setting that to the target.

Properties

Whichever way you decide to target, you need to be able to manipulate it. This is where the rest of the props come in. If you target any normal DOM element, including SVG, you can set a prop as any CSS property or DOM attribute that applies to that element type. For example, sliding a square across the screen while doubling its size, rotating it 360 degrees and changing its color to red is as simple as:

Property Parameters

The next category of options are parameters which affect the way in which properties are transformed. The following are examples of such parameters:

duration: indicates how long the animation lasts (in milliseconds),
delay: indicates a wait time (in milliseconds) after which the animation starts,
endDelay: attaches extra time to the end of the animation (in milliseconds),
round: rounds up to the nearest decimal. A more complex parameter is easing. Easing refers to the rate of change of an object over time. In our case the changes are the transforming properties, so easing changes how fast or slowly they animate at a given moment. For more information check out this link. As well as setting these parameters to affect an entire animation, you can designate specific properties to behave differently from others. This is done by assigning the property to an object whose properties include a value, which is the normal value for the animation, and any of the parameters which you want to single out. For example: As you can see the box moved before starting to grow or spin which each had a different easing.

Animation Parameters

The last category of props consists of the types of parameters which affect the animation as a whole. These are the simplest types of parameters. They include direction, loop, and autoplay. Direction defines the direction in which the animation will play: ’normal’, ’reverse’, or ’alternate’. Normal plays the animation from 0% progress to 100%. Reverse plays it from 100% to 0%. Alternate will first play a normal animation then a reverse animation in sequence. Adding a delay will affect the time between the normal play and the reverse play. Loop defines the number of times an animation will play. Setting the value to true will cause the loop to play infinitely. Autoplay defines whether the animation will play automatically at render. This value is set to true by default.

Keyframes and Timelines

Keyframes and timelines serve the purpose of setting a sequence of animations to play one after the other. Keyframes set a sequence on a single element and will count as a single animation in the course of a timeline. Keyframes are defined using an array either within the keyframes property or as a value for a CSS property. By setting keyframes to CSS properties, you can overlap animations since each property has its own keyframes array. Here’s an example:

Timelines let you synchronize multiple animations together. By default each animation added to the timeline starts after the previous animation ends.

Conclusion

Anime.js is robust and easy to use framework for animations in web browsers. Check out their docs here and start creating amazing animations.

D3.js

agrem28 — Mon, 11 Jan 2021 13:18:59 +0000

Data-Driven Documents, or D3, is a JavaScript library for producing dynamic, interactive data visualizations in web browsers. D3 uses HTML, SVG, and CSS to accomplish this. D3 is built on the concept using functions to select elements, create SVG objects, style them, and add transitions, dynamic effects or tooltips to them. Large datasets can be bound to SVG objects using D3.js functions to generate text/graphic charts and diagrams.

Main Features

Selections

D3 has two simple functions to select the DOM elements you need: selectAll and select. Selections methods will accept strings as arguments such as div for div elements, .container for elements with the class name of “container,” or #submit for elements with the id of “submit.” selectAll will return all matches of the specified element, while select will only return the first element of the document. For example, to change all paragraph elements to have a red font, use:

d3.selectAll(‘p’).style(‘color’, ‘red’);

To select only the first paragraph tag and turn it red, use:

d3.select(‘p’).style(‘color’, ‘red’);

Selections can also be chained to select descendants of elements. For example, to return the first bold element of a paragraph:

d3.select(‘p’).select(‘b’);

Dynamic Properties

Unlike with other DOM frameworks like jQuery, D3 treats things like styles, attributes and other similar properties as functions of data rather than simple constants. For example, to randomly color paragraphs:

d3.selectAll(‘p’).style(‘color’, function() {
  return ‘hsl(‘ + Math.random() * 360 + ‘,100%,50%)’;
});

Or, alternate colors for even or odd divs:

d3.selectAll(‘div’).style(‘background-color’, function(d, i) {
  return i % 2 === 0 ‘#fff’ : ‘#eee’;
});

These callback functions often refer to our bound data. We can specify this data as an array with each value passed as the argument d to selection functions. The data is then matched to the correct node by matching the index. First node with the first data point, second node with the second data point, and so on. For example, given an array of numbers, we could use these numbers as font size for our paragraphs like so:

const fontSizes = [4, 8, 15, 16, 23, 42];
d3.selectAll(‘p’)
  .data(fontSizes)
    .style(‘font-size’, (d) => `${d}px`);

Enter and Exit

Earlier we said that data and nodes match up according to index. But what if there’s more elements of one than the other? The enter and exit functions handle this for us. Using the previous example, there were 6 numbers in the fontSizes array. If only 5 paragraph nodes exist, the last number 42 has nowhere to go. Using enter will create a new node which will use the extra data.

d3.selectAll(‘p’)
  .data(fontSizes)
    .enter().append(‘p’)
      .style(‘font-size’, (d) => `${d}px`);

exit has the opposite effect. It removes unnecessary nodes for which there is no data.

Transitions

Transitions gradually incorporate styles and attributes over time. For example, to fade the background of the page to black:

d3.select(‘body’).transition().
  .style(‘background-color’, ‘black’);

Or, to resize circles in a symbol map with a staggered delay:

d3.selectAll(‘circle’).transition()
  .duration(750)
  .delay((d, i) => i * 10;
  .attr(‘r’, (d) =>  Math.sqrt(d * scale)});

By modifying the attributes that actually change, D3 reduces overhead and allows greater graphical complexity at high frame rates.

Conclusion

These are just a few of the most used features of D3.js. Others include timers for managing when and for how long each animation will take place, shapes for creating unique elements used in charts and graphs, and zoom for panning and zooming using a mouse or touchpad. You can see plenty of amazing examples using all kinds of techniques here.

Phaser

agrem28 — Sat, 09 Jan 2021 01:27:57 +0000

Phaser 3 is an HTML 5 framework that is used to make games that easily run in the web browser. It is written entirely in either JavaScript or TypeScript (your choice) and makes use of the HTML 5 canvas element to create games that can run directly in your browser without the need of a plugin like Flash Player (which recently had its support dropped from Chrome). Phaser does all the heavy-lifting for you. It handles the DOM interaction while you worry about the look and feel of your game. The prepackaged tools like Physics engines, sprite handlers, audio features and more makes the development process simple.

Features

WebGL and Canvas

Phaser uses both a WebGL and Canvas renderer internally so that it can seamlessly swap between the two based on browser support. It does this through the use of a package builder such as Webpack or Parcel to check the browser first and choose the best choice for the job. This effortless transition is accomplished through the use of a few lines of codes in your webpack.config.js file.

Preloader

The preloader allows all the assets of your game to be loaded and stored in the Global Cache available for use by any child Game Objects. Images, sprite sheets, sounds, tilemaps, JSON, and XML are all parsed and handled automatically through the load function.

Physics

Phaser comes prepackaged with three physics engines to suit your needs. The Arcade Physics library supports funner, less realistic physics as you might see in a 2D arcade game or platformer. Matter JS is a more realistic physics engine with support for real-world systems such as springs, constraints, and tension, as well as polygon support for 3D rendering. Finally, Impact physics allows for the simulation of advanced collision physics when tile mapping.

Sprites

Sprite sheets allow for an animated character to look like it’s moving by capturing it in different positions and using each position one at a time at a certain framerate. Phaser does the animation for you by simply telling the anims function which frames you need and at what speed. Phaser also has a supply of ready-made sprite sheets and other assets like images, particles, sounds, and tile maps available for download from their website at labs.phaser.io/assets.

Particles

Phaser has a particle system built in, which allows for easy creation of particle effects such as sparks or lights. Persistent effects are also supported such as smoke, rain, or fire.

Input

Phaser supports every type of input there is: keyboard, mouse, touchscreen, gamepad. All of these are supported, even if you change mid-game. Any object can be clickable or touchable, and any object can be manipulated through the keyboard. Just supply the rules for the actions and you are good to go.

Sound

Sound effects are vital to any video game. Whether it be music, speech, bangs, pops, or blasts, the best games usually also have the best sound design. Phaser makes it easy to load your sound files into the game scene and use them at will. It also handles external factors such as volume control and mobile device silence.

Tilemaps

Tilemaps are the blueprints of how you want your play area to look. Each tile is designated a position on the canvas through a CSV or Tiled Map data format. Phaser can load, render, and collide with a tilemap with just a few lines of code. Tiles can then be deleted, swapped, or moved easily through the use of tilemap functions.

Community Support

Phaser has a robust and inclusive community which shares ideas and projects frequently. There is a Phaser forum for discussing tech issues, a Discord server for more casual discourse. The Phaser Twitter account also makes frequent posts showcasing incredible games made through their framework and are always available to answer questions. Tutorials ranging from beginner level to advanced content are free to browse and experiment with as well as open source templates and projects.

Learn more and discover new games by checking out the news section of the phaser website.

Continuous Integration

agrem28 — Tue, 05 Jan 2021 15:22:42 +0000

Continuous Integration is a development practice where developers integrate code into a shared repository as frequently as possible. Each integration can then be verified by an automated build and automated tests. The continuous integration process helps to answer several important questions for the software development team.

Do all the software components work together as they should?
Is the code too complex for integration purposes?
Does the code adhere to the established coding standards?
How much code is covered by automated tests?
Were the tests successful after the latest change?

The answers to these questions tell the developers whether the merged code is working properly with minimal complexity and best practice. One of the key benefits of integrating regularly is that you can detect errors quickly and locate them more easily. As each change that is introduced is typically small, pinpointing the specific change that introduced a defect can be done quickly. These questions, which relate to a step in the integration process, tell us what needs to be fixed to ensure a smooth integration into the shared codebase.

In addition to the questions posed throughout the integration process, CI is guided by a set of key principles. Among them are version control, build automation, and automated testing. Additionally, continuous deployment and continuous delivery have developed as best practices for keeping your application deployable at any point or even pushing your main codebase automatically into production whenever new changes are brought into it. This allows your team to move fast while keeping high quality standards that can be checked automatically.

Version Control

One of the key attributes of continuous integration is the practice of version control: the process of keeping multiple versions of files so that when a change is made it is possible to access previous revisions. All aspects related to the creation of the software should be under version control. In addition to the source code, database scripts, build and deployment scripts, documentation, libraries and configuration files, and compilers as well and many other aspects should all be under direct version control. By storing all these files, it becomes easier to recreate the testing environment and production environments that the application runs on. By having everything that could possibly change at any point in the life of the project stored in a controlled manner, it allows you to recover an exact snapshot of the state of the entire system should anything go wrong.

Build Automation

Build automation is the process of taking source code and other artifacts created by developers and turning them into a software product that can be executed and used by customers. The build may include the following steps:

Compiling source code
Compressing target files into archives
Generating software installers
Running automated tests on the build
Automatically deploying software on a target environment

The automated build process can help development teams by standardizing builds and documenting and codifying important aspects of a software project such as third-party dependencies, artifacts related to the build, tests, and deployment details.

There are generally two types of build processes: the full build and the incremental build. The full build will build the entire software application from the source files. It takes in the full project, checks dependencies, compiles all source code and builds the target software components to create the complete build artifact. The incremental build takes an existing build, checks what has changed in the source code and artifacts since the last time the software was built, and compiles or rebuilds any file that has changed, or which depends on a resource that has changed. Other files will remain unchanged and will be reused from the previous build. Incremental builds are faster and more efficient, but less reliable.

An Intro to Artificial Intelligence

agrem28 — Tue, 05 Jan 2021 01:10:05 +0000

Artificial intelligence, or AI, refers to the ability for a computer to think like a human: to adapt and improvise in a new environment and to generalize its accumulated knowledge and apply it to unfamiliar scenarios.

This of course is nearly impossible for machines because humans are immensely complex creatures. We experience new things every second of our lives, with no filter as to what can be perceived. Humans are aware of time and space as a way of defining our existence. AIs define time as a sum of milliseconds. AIs only experience what we want them to experience. Computers experience intelligence through a series of ones and zeros. Humans aren’t binary thinkers. We can examine a wider scope of possibilities. The challenge is manipulating the ones and zeros into acting non-binary through the use of algorithms and neural networks.

Types of AI

AI can usually be split into two broad scopes: narrow AI and general AI.

Narrow AI

Narrow AIs are focused on specific tasks, such as voice recognition or shooting a basketball. Stepping out of that comfort zone would be impossible. For example, Siri on the iPhone would not be able to shoot a basketball and the shooter robot would not be able to hold a conversation. Narrow AIs can further be broken up into two types: Reactive and Limited Memory.

Reactive machines are the most basic type of AI having neither the ability to form memories nor to use past experiences to inform current decisions. For example, IBM’s chess-playing supercomputer Deep Blue is a reactive AI. It can identify the pieces on a chess board and has knowledge of how they move. It can consider the consequences of a move and the potential moves to be played after. But no previous moves from the current game are used when calculating what move to use next. No analysis of the player’s affinity or style is computed. In other words, Deep Blue focuses only on the future with no regard to the past.

Limited Memory AIs are machines that do look into the past. These machines can store memory and use it to make a decision. For example, Google’s self-driving cars detect other cars on the road and store values such as its speed and direction. These data points cannot be calculated in a single instant. Speed itself is a calculation of distance over time. Inherently, time must pass. These changing values are added to the preexisting representations of the world such as lane markings, traffic signs, and curves and included in the decision making process when changing lanes or making a turn.

General AI

General AI is the type of adaptable intellect found in humans, a flexible form of intelligence capable of learning how to carry out vastly different tasks. This is the type of AI found in science fiction movies, such as Skynet from “The Terminator”, which do not exist today, but may be a reality in the future. However, experts are divided over how soon. A survey conducted among four groups of experts in 2012/2013 by AI researchers Vincent C Muller and philosopher Nick Bostrom reported a 50% chance that Artificial General Intelligence would be developed between the years 2040 and 2050, that figure rising to a 90% chance by 2075. However, more recent assessments made by AI experts are much more cautious. They say that society is nowhere close to developing AGI. Rest easy; we won’t be seeing AI supervillains anytime soon. But these theoretical future AGIs also are divided into two types: “Theory of the Mind” and Self-Aware.

The so-called “Theory of the Mind” AIs get their name from the psychology term in which an individual can ascribe mental states to itself and others; mental states such as liking and disliking, knowledge, doubt, belief, happiness, etc. This capacity to at least acknowledge that other beings have their own thoughts, emotions, and experiences is what makes us human. This is the line that must be crossed for AIs to be considered General and Human-like.

The final step of AI evolution is the self-aware machine: the machine which has thoughts, emotions and experiences of its own and can communicate them to others. This leads to the most difficult barrier of all: the understanding of the human mind. Researchers are still understanding new things about how humans think and feel and how the brain makes it all possible. We may never know enough about ourselves to conquer this final hurdle.

Transpilers

agrem28 — Thu, 19 Nov 2020 00:14:43 +0000

Transpilers are wonderful tools for programmers. Code can be translated from one language to another. It can even be converted from one syntax or version to another. It can be useful in many different ways. It allows the programmer to always be able to code in his or her preferred language. Some
libraries and frameworks are incompatible with browsers as well, such as React, which is one of the most popular app frameworks available. Just load the files that are written in your preferred style into a transpiler. The output file can then be used as the reference script and tucked away into a dist folder while you focus on your own code.

In the above example, the code on the left is hand-written JavaScript in ES2015 format. The code on the right is code generated from a transpiler which is in ES5 format. Some browsers still do not recognize some ES2015 syntax, so it is useful to convert it to older versions which are universally accepted.

Implementation

Now that we understand why we use transpilers, it's useful to understand how they work. Work is accomplished in three distinct steps: parsing, transformation, and generation. Here is a nice graphical representation.

Parsing

Parsing is the process of the transpiler reading the code and interpreting that code. That interpretation is represented by an abstract syntax tree, which is a tree whose nodes represent actions or data in the program such as conditions and assignments.

The above image shows a short function and the corresponding AST. You can see that leaf nodes are used for variables and constants while branching nodes represent either operators or flow. By traversing the tree you can see the path the code will take in its execution.

Transformation and Generation

The nodes are then translated into equivalent nodes in the target language. This is done because it is easier for the transpiler to convert individual nodes instead of raw code.
This process may take one or many steps to complete, depending on the complexity and size of the code.

Once this is done, the final step is the new code generation. This is typically the easiest and quickest step because it is the simple matter of traversing the nodes of the tree and outputting the correct code.

After that, the new code will be stored on a new file which can be saved within your program and referenced as the main script. Some useful transpilers available for free use include:

Babel, a JS transpiler for converting from ES6 to ES5
Traceur, another similar JS compiler
Opal, a Ruby to JS compiler
TypeScript, a syntax more in line with an OO language like Java, but acts like JS
CoffeScript, a syntax similar to Python, but acts like JS

There are many more which can meet a variety of needs. Try them out and see how your work will be made much easier!

An Intro to React Recoil

agrem28 — Mon, 02 Nov 2020 15:43:20 +0000

Recoil is a state management library for ReactJS, made by the developers of React. React has the major limitation of components only sharing state through a common ancestor. Recoil allows state to be stored individually and separately from the components through the use of atoms and selectors. The components then call on the atoms as needed. This creates a data-flow graph going from the atoms through the selectors to the components.

Atoms

Atoms are individual units of shared state which are undateable and subscribable. When an atom is updated, each subscribed component is re-rendered with the new value. Components that read the value of the atom are automatically subscribed to the atom. Atoms are created using the atom function:

const textState = atom({
  key: ‘textState’, // must be a unique value among atoms and selectors
  default: ‘’,
});

To read the contents of this atom we use useRecoilState() which takes a passed atom and returns a two element array of a getter and a setter. The setter is a function which takes a value and returns a transformation which is then assigned to the default of the atom.

Selectors

Selectors represent derived state or a transformation of state. A way to conceptualize it is to imagine a derived state as the output of passing state into a pure function which then outputs an alteration of that state without modifying the original state.

const charCountState = selector({
  key: 'charCountState',
  get: ({get}) => {
    const text = get(textState);
    return text.length;
  },
});

This example uses the atom textState by getting the default and returning the length of the string. We can then use this value by calling the useRecoilValue() method which only returns a getter, since selectors are not updatable.

With this system of atoms and selectors, we can easily distribute state to whichever components might need it, while avoiding the ones that don't. This saves valuable time and memory when rendering components.

An Intro to AJAX: Asynchronous Javascript and XML

agrem28 — Mon, 26 Oct 2020 02:04:57 +0000

In the dark ages of the internet, web pages were built solely on HTML files. This means that each time the user made a change a completely new page must be loaded. Even if only a small change was made, all content must be rerendered and all data resent. This data transfer caused bandwidth to be an important factor in performance.

Then in 1998, Microsoft developed the XMLHttpRequest object, which allowed data to be sent and received from the server asynchronously from the page. This allows elements to be updated without the page needing to reload, reducing data transfer sizes. Google would use this new object in their implementations of their updated apps, namely Gmail and Google Maps. The term AJAX was first published in an article by Jesse James Garrett in 2005 titled “Ajax: A New Approach to Web Applications” about Google’s techniques used in Google Pages. Since then, XMLHttpRequest has become the official Web standard concerning asynchronous programming.

Components

It’s important to know that AJAX is not a language, library, or framework. It is simply a set of techniques that employ existing technologies in a unique way: namely, in a way that allows web apps to send and retrieve data to and from the server while not interfering with the page display. The component used are as follows:

HTML and CSS to build the page,
JSON or XML to store data (JSON has become the norm over XML in recent years),
The DOM which displays the page and allows interaction with data,
The XMLHttpRequest object which allows asynchronous communication with the server, and
Javascript to bring all the elements together.

The XMLHttpRequest Object

The most important of these components is the XMLHttpRequest object. It facilitates the transfer of data to and from the server asynchronously through its methods: open, setRequestHeader, send, and onreadystatechange.

HTTP and HTTPS requests must first be initialized using the open method.

open(method, url, asynchronous, userName, password)

The first parameter method refers to the HTTP request methods: GET, HEAD, POST, PUT, DELETE, etc. The url parameter refers to the server location. The third parameter is an optional boolean value referring to the synchronous nature of the request. This value is set to true by default. The final two parameters are set up for optional security measures.

After a request has been initialized, the setRequestHeader method can be used to change HTTP headers, effectively settings by which the request abides.

setRequestHeader(name, value)

name signifies the header and value represents the intended setting.

When ready to process the request, the send method is used to start the transfer.

send(data)

Data is always needed when sending a request such as with the HTTP methods GET and HEAD.

When open is called with the third parameter set to true, the onreadystatechange method will automatically be invoked on any call which changes the state of the readyState property of the XMLHttpRequest object. A state is determined by a number from 0-4:

0: a request has not been initialized
1: a request has been started by invoking the open method
2: a request has been set up and sent by invoking send after setRequestHeader
3: the sent data has begun to load server-side
4: the data has been fully received and processed

Once processed, the data can be accessed by invoking the responseXML or responseText properties of the XMLHttpRequest object.

This example shows a full request process using XMLHttpRequest methods.

var request = new XMLHttpRequest();
request.onreadystatechange = function () {
    if (this.readyState === 4){
        alert(this.readyState);
    }
};
request.open('GET', 'somepage.html', true);
request.setRequestHeader('Content-Type', 'application/json');
request.send(null);

By utilizing the HTTP request methods and the XMLHttpRequest object methods you can create some efficient and beautiful webpages and applications.

Tree Climbing: Using Depth First Search and Breadth First Search

agrem28 — Wed, 21 Oct 2020 02:22:33 +0000

Within the scope of tree data structures, traversal, or searching, is a way for users to efficiently visit every node of a tree or graph while usually executing a callback on the node's data. As humans, we could easily see the entire tree and know the values immediately. But how would a machine, which only reads line by line, know what to do? This is where search algorithms come into play.

Trees can be traversed in two main ways: branch by branch, or level by level. These two methods are called Depth First Search (DFS) and Breadth First Search (BFS) respectively. Using one method over the other depends on the shape of your tree. Since DFS works by diving down the length of a branch until you reach the bottom, it is particularly useful on trees with fewer levels. Transversely, BFS is useful on trees where there are fewer children per node.

Depth First Search: Branch by Branch

Just like a real tree, data trees have branches and leaves and roots. When traversing, you climb down a branch until you arrive at a leaf. Then, climb back up the branch until you reach a fork. At this point, travel down that branch until you find a leaf. This process repeats until every node has been visited.

This is good for visualization, but how can we get the computer to accomplish this? We do this by executing three steps:

Iterate the data using a callback
Check the left child
Check the right child

If a child exists, go to step one and repeat the checklist on the child while remembering your spot in the checklist. This order of operations is referred to as DLR, standing for data, left, right.

The order in which the steps are executed also matters when using DFS. There are three different combinations that are useful to mention:

Preorder: data is iterated first
Inorder: data is iterated between each check of the children
Postorder: data is iterated last

With preorder, data is iterated in the order it was visited. Inorder allows us to visit the leftmost node before iteration. This way items will be iterated in order by magnitude. With postorder, the root node is read last because children will always be iterated before the parent.

A neat way to think about DFS is as a stack. When first visiting a node, push it onto the stack. Then execute the checklist on the top of the stack. After all three steps are done, pop it off. By doing this you never lose track of what node you should be on.

depthFirstSearch(callback, node) {
  callback(node.value);
  if (node.left !== null) {
    depthFirstSearch(callback, node.left);
  }
  if (node.right !== null) {
    depthFirstSearch(callback, node.right);
  }
}

By using recursion we can utilize the call stack to keep track of the nodes for us. The recursive call will also hold
our place in the DLR checklist until we reach the end of the branch.

Breadth First Search: Level by Level

Unlike DFS which dives deep into the tree then resurfaces, BFS is more like a cautious swimmer carefully wading his way to the deep end of the pool. First we start in the shallow end -- the root node and its children -- then move deeper and deeper until we hit the bottom.

A simple way to execute this is to make a list of all the items in the order they will be executed. Then it’s as simple as calling an iterator on every node in the list. But what if we have an especially large tree? It would be quite memory intensive to put every node in a list. We can avoid this issue by iterating as we populate the list, using a queue.

Start with a queue consisting of only the root node. Then start a loop in which the children of the head of the queue are enqueued. Then use the iterator on the head and dequeue it. The queue will hold the correct order while minimizing storage.

breadthFirstSearch(callback) {
  const queue = [];
  queue.push(this);
  while (queue.length > 0) {
    const currentNode = queue[0];
    if (currentNode.left !== null) {
      queue.push(currentNode.left);
    }
    if (currentNode.right !== null) {
      queue.push(currentNode.right);
    }
    callback(currentNode.value);
    queue.shift();
  }
}

As you can see the loop will only stop executing once the queue is empty. Meanwhile the head will be checked, (its children being added to the queue), called, and finally dequeued before moving on to the new head.

Time-Space Complexity

The time taken to execute each search increases with the amount of nodes in the tree since every node must be visited once. The memory space taken during BFS increases as the size of the queue does. Therefore the worst case scenario is that every node is in the queue at once. This makes the space complexity linear as well. The space complexity of DFS depends on the amount of recursive calls running at one time. Thus the complexity is linear with respect to the longest branch of the tree.

By comparing the two search algorithms we can see the similarities and also the differences. Stack vs queue, recursion vs loops, width vs length. But the complexities are essentially the same, so it all comes down to situation when choosing which traversal to use.

Recursion in Javascript

agrem28 — Thu, 24 Sep 2020 02:13:48 +0000

Functions are the cornerstone of Javascript programming. Nearly all applications of Javascript code are chock full of functions of all kinds. One type of function structure is the recursive function.

By definition, a recursive function is a function that calls itself within it. This way the function creates a loop.

function printRecursive(x) {
  console.log(x);
  printRecursive(x);
}
recursion(3);

This example will keep printing 3. But how do we end the loop? We do this by using a test. When calling the function recursively, change the arguments such that the test will eventually be passed. Then return the function and the loop will be broken. This test is called the base case.


function printRecursive(x, times) {
  if (times === 0) { // base case
    return;
  }
  console.log(x);
  printRecursive(x, times-1);
}
printRecursive(3, 3);

This example will print 3 three times. When printRecursive(3, 3) is called, the test fails because 5 does not equal 0 and 3 is printed. Then printRecursive is called again with the arguments (x, times-1). Once again the test fails because 4 does not equal 0 and 3 is printed. This continues until times is 0 in which case the loop is broken.