This is a sample post created to test the basic formatting features of the WordPress CMS.
You can use bold text, italic text, and combine both styles.
This content is only for demonstration purposes. Feel free to edit or delete it.
We use Google search, google maps, and social networks regularly nowadays. One of the things they all have in common is the fact they use a remarkable data structure – graphs under the hood to organize and manipulate data. You may have seen this data structure in college but don’t remember much about it. Or maybe it is a scary topic you avoid all the time. Either way, now is an excellent time to get familiar with it. In this blog, we will cover most of the concepts, and you should be comfortable to move on to work with algorithms related to graphs.
A graph is a non-linear data structure that organizes data in an interconnected network. It is very similar to trees. Actually, a tree is a connected graph with no cycles. We will talk about the cycles in a little.
Ignore the red stroke around the Trees box. It was supposed to be around the Graphs box. ?
Random graph
There are two primary components of any graph: Nodes and Edges.
Nodes are typically called Vertices (singular: vertex), and they can represent any data: integers, strings, people, locations, buildings, etc.
Edges are the lines that connect the nodes. They can represent roads, routes, cables, friendships, etc.
There is a lot of vocabulary to remember related to graphs. We will list the most common ones.
A graph can be directed or undirected. As you might have already guessed, directed graphs have edges that point to specific directions. Undirected graphs simply connect the nodes to each other, and there is no notion of direction or whatsoever.
Let’s say we are using a navigation application and trying to get the best route between point A and point B. Once we enter the details of the two points, the app does some calculations and shows us the fastest way to reach our goal. Typically, there are many ways to get from point A to point B. So to choose the best way, the app would need to differentiate the options by specific values. The obvious solution, in this case, is to calculate the distance each option entails and pick the one with the shortest distance. So assigning some value to the connection between two points is called adding weight to it. Weighted graphs have some values (distance, cost, time, etc.) attached to their edges.
Earlier, we have mentioned that a tree is actually a graph without cycles. So what is a cycle in a graph? We say a graph is cyclic when it has a continuous sequence of vertices that connects back to itself. Vertices or edges cannot be repeated. Acyclic graphs do not have cycles. Trees happen to be acyclic and directed graphs with a restriction that a child node can have only one parent node.
One of the main things that make graphs less intuitive and confusing is probably the way they are stored in computer memory. With the nodes being all over the place and flexible amounts of edges connecting them together, it can be challenging to find an obvious way to implement them. However, there are some widely accepted representations we can consider. Let’s store the following undirected graph in three different ways.
This representation stores a graph as a list of edges.
const graph = [['A', 'B'], ['A', 'E'], ['C', 'B'], ['C', 'E'], ['C', 'D']];
Edges are mentioned only once on the list. There is no need to state A and B, and also B and A. Additionally, the order of edges in the list does not matter.
Similar to the list of edges, we could also store the nodes as a list. But that is not what the Edge List representation is.
This method relies on the indexes when storing the connections to a particular node. In JavaScript, we would create an array of arrays, where each index indicates a node in the graph, and value at each index represents the adjacent (neighbor) nodes.
const graph = [
['B', 'E'],
['A', 'C'],
['B', 'D', 'E'],
['C'],
['A', 'C']
]
Again, the order of the nodes does not really matter, as long as we organize them without duplicates and with correct adjacent vertices.
Moreover, the graph could also be represented as an object. In that case, keys would represent the nodes and values would be the list of neighbor nodes:
const graph = {
'A': ['B', 'E'],
'B': ['A', 'C'],
'C': ['B', 'D', 'E'],
'D': ['C'],
'E': ['A', 'C']
}
This option is usually helpful when the vertices do not properly map to array indexes.
In this representation, we create an array of arrays in which each index indicates a node, and value at that node shows the list of nodes this particular node has connections with. A connection is denoted as 1, and a lack of connection is denoted as 0.
const graph = [
[0, 1, 0, 0, 1],
[1, 0, 1, 0, 1],
[0, 1, 0, 1, 1],
[0, 0, 1, 0, 0],
[1, 0, 1, 0, 0]
]
In this case, the order of the nodes in the list matters.
There are two main graph algorithms that we absolutely need to know when it comes to graphs:
Many graph-related problems can be solved with these two traversal methods.
Breadth-First Traversal
BFS algorithm traverses a graph by visiting the neighbor nodes instead of going down to the child nodes. And it uses a queue data structure to keep track of the visited vertices.
The structure given above looks like a tree, but it does not have to be a tree data structure for us to use the breadth-first search algorithm. Actually, a tree is a type of graph.
There are three main steps that these algorithms follows:
Depth-First Traversal
This algorithm visits the child vertices before traversing the sibling nodes. It tries to go as deep as possible before starting a new search on the graph. The significant difference of this algorithm from the previous breadth-first is the fact that it uses stack data structure instead of a queue.
DFS follows these steps to traverse through a graph:
Cheers!
Prerequisites: Basic knowledge of JavaScript
In the first part of the blog, we have introduced the notion of blockchain and covered the basic concepts. You could dig a lot deeper if you want, but that is the minimum knowledge we need to move on to the next step of the blockchain system of our own. In this part, we will make a blockchain system called USDevCoin. With the help of our system, users will be able to exchange USDev coins and every transaction will be securely stored as blocks in the chain. Now, by no means the system will be secure enough actually to perform the role of a blockchain, but it will be enough to demonstrate the infrastructure. There is a lot to do, so let’s dive right in!
Before getting started, we need to ensure that we have the latest version of Node installed on our machine. Once you confirm it, go ahead and create the main JavaScript file.
We will call the file chain.js and write the first class Block.
// chain.js
class Block {
constructor(index, payload, timestamp, previousHash = ""){
this.index = index;
this.payload = payload;
this.timestamp = timestamp;
this.previousHash = previousHash;
this.hash = "";
}
}
The are four arguments given in the constructor of the class Block. They have the following purposes:
index – it will be the index of the block in the chain
payload – data that the block holds. It could be anything. In our case, we will store the number of coins being transferred in this parameter
timestamp – date and time of the record when it was created
previousHash – since we are going to be chaining the blocks, this argument will refer to the hash of the previous block
If you have noticed, we initially set the hash value of the class to an empty string. Now we need a way to calculate the hash value of the block. Hash value entails taking a range of arguments for a digital record, and creating a unique signature. The important thing about this hash is that it always should return the exact same value when we provide identical parameters.
In JavaScript however, the hashing function is not included by default. So we have to use a third-party library called crypto-js.
So we need to run npm install --save crypto-js in our project folder and import the hashing function from the node module. We will specifically use the SHA256 algorithm for hashing.
// chain.js
const SHA256 = require("crypto-js/sha256");
class Block {
constructor(index, payload, timestamp, previousHash = ""){
this.index = index;
this.payload = payload;
this.timestamp = timestamp;
this.previousHash = previousHash;
this.hash = this.getHashValue;
}
getHashValue() {
return SHA256(
this.index +
this.previousHash +
this.timestamp +
JSON.stringify(this.payload)
).toString();
}
}
SHA256 algorithm processes the values and returns the hash value as a string. We also need to update the constructor with the new function, so that the hash automatically gets calculated upon creation of a block.
The next step is to add the USDevBlockchain class.
class USDevBlockchain {
constructor(){
// Chain is an array of blocks
this.chain = [this.getFirstBlock()];
}
// We have to create the first block manually
getFirstBlock() {
return new Block(0, "First Block (Genesis Block)", new Date(), "0");
}
// Returns the latest block in the array
getLastBlock(){
return this.chain[this.chain.length - 1];
}
// Adds new block
addNewBlock(newBlock){
newBlock.previousHash = this.getLastBlock().hash;
newBlock.hash = newBlock.getHashValue();
this.chain.push(newBlock);
}
// It checks if the blocks are chained properly and valid
validateChain(){
for(let i = 1; i < this.chain.length; i++){
let prevBlock = this.chain[i-1];
let currBlock = this.chain[i]
// Check if each block's hash value was not modified
if(currBlock.hash !== currBlock.getHashValue()){
return false;
}
// Check if the blocks are chained correctly
if(currBlock.previousHash !== prevBlock.hash){
return false;
}
}
return true;
}
}
Let’s go through all of the features of this class.
constructor defines the chain as an arraygetFirstBlock creates the initial block in the chain. This first block is usually called the Genesisblock. We need to create it at the beginning manuallygetLastBlock returns the latest block in the chain. We need to know this to connect the new block to the chainaddNewBlock is self-explanatory. It adds a new block to the chainvalidaChain checks if the chain is validWe can test our classes to make sure that we are not missing anything
const USDevCoin = new USDevBlockchain();
USDevCoin.addNewBlock(new Block(1, {amount: 2}, new Date()));
USDevCoin.addNewBlock(new Block(2, {amount: 5}, new Date()));
console.log(JSON.stringify(USDevCoin))
We can test the validation function as well.
const USDevCoin = new USDevBlockchain();
USDevCoin.addNewBlock(new Block(1, {amount: 2}, new Date()));
USDevCoin.addNewBlock(new Block(2, {amount: 5}, new Date()));
console.log(USDevCoin.validateChain()); // Prints "true"
USDevCoin.chain[1].payload = {amount: 290}; // Someone tampers with the chain
console.log(USDevCoin.validateChain()); // Prints "false"The current state of the application is not only incomplete but also fragile. Because it allows us to add new blocks to the chain very quickly, spammers can take advantage of this weakness and try to add a huge number of blocks at the same time and eventually break the system. Or the whole chain could be overwritten with a powerful machine. To prevent all of these from happening, we need to implement a method to enforce the system to wait for a certain amount of time before adding a new block to the chain.
For example, Bitcoin requires the hashes to have a specific number of zeros at the beginning. That number is also called the difficulty. It is hard for the machines to find the hash value with the exact amount of zeros at the beginning. So it will take time and tremendous computational power to come up with that value. Since the whole system is distributed, there are a bunch of networks competing against each other to find the correct value. The good thing about mining is that even though it takes a long time to process, it is swift and easy to verify if the work was completed correctly. The entire step is called proof-of-work. Now let us implement it in our code.
In order to add the proof of work step to the system, we need to add a new function to the Block class. This function basically has a while loop which does not stop until it matches the requirement we specify in the arguments.
class Block {
constructor(index, payload, timestamp, previousHash = ""){
this.index = index;
this.payload = payload;
this.timestamp = timestamp;
this.previousHash = previousHash;
this.hash = this.getHashValue;
this.nonce = 0;
}
// .........
mineNewBlock(difficulty){
while(this.hash.substr(0, difficulty) !== Array(difficulty + 1).join("0")){
this.nonce++;
this.hash = this.getHashValue();
}
}
}mineNewBlock function takes difficulty as a parameter. The difficulty is another term used in the blockchain world. In simple terms, it defines the level of difficulty to mine new blocks. Bitcoin for example is designed to take about 10 minutes to mine a new block. That timeframe could be increased or decreased by manipulating the difficulty parameter.
The while loop waits until the hash generated has the specified number of zeros at the beginning given in the difficulty property.
Then we have to modify the addNewBlock function to include the newly created function in the Block class. While calling the mineNewBlock function, we send the difficulty defined in the constructor.
class USDevBlockchain {
constructor(){
// Chain is an array of blocks
this.chain = [this.getFirstBlock()];
this.difficulty = 3;
}
// .....
// Adds new block
addNewBlock(newBlock){
newBlock.previousHash = this.getLastBlock().hash;
newBlock.mineNewBlock(this.difficulty);
this.chain.push(newBlock);
}
// ....
}
As the name of our blockchain USDevCoin indicates, we are going to use our system for making a cryptocurrency. The most critical part of the cryptocurrencies is the ledger of transactions. Coins get transferred from one user to another, and that action gets recorded as a single transaction. However, one transaction alone cannot be stored as a whole block in the chain. Because of the proof-of-work security layer we have in place.
Again, going back to Bitcoin. We earlier mentioned that it takes about 10 minutes to mine a single block. But in 10 minutes we cannot process only one transaction. That would be an incredibly useless system. So there are thousands of transactions happening within that timeframe. While the network waits for about 10 minutes, those transactions get added to a queue and stay as pending transactions. Once a new block gets mined, all of the pending transactions will be included in that new block and the block is added to the chain.
It means that we have to modify our Block class to include an array of transactions, instead of just a random data object.
// chain.js
const SHA256 = require("crypto-js/sha256");
class Transaction {
constructor(fromAddress, toAddress, amount){
this.fromAddress = fromAddress;
this.toAddress = toAddress;
this.amount = amount;
}
}
class Block {
constructor(transactions, timestamp, previousHash = ""){
this.previousHash = previousHash;
this.timestamp = timestamp;
this.transactions = transactions; // Data -> Transactions
this.hash = this.getHashValue();
this.nonce = 0;
}
getHashValue() {
return SHA256(
this.previousHash +
this.timestamp +
JSON.stringify(this.transactions) +
this.nonce
).toString();
}
//...
}
Then in our USDevBlockchain class we need to make some drastic modifications. Let’s write the code first and then we will go through each addition on by one.
class USDevBlockchain {
constructor(){
// Chain is an array of blocks
this.chain = [this.getFirstBlock()];
this.difficulty = 3;
this.pendingTransactions = [];
this.rewardForMiners = 20;
}
//....
mineBlockForPendingTransactions(minerAddress){
let newBlock = new Block(this.pendingTransactions, new Date(), this.getLastBlock().hash);
newBlock.mineNewBlock(this.difficulty);
this.chain.push(newBlock);
// When a new block is mined, reward the miner
// But the reward will be available with the next block
this.pendingTransactions = [
new Transaction(null, minerAddress, this.rewardForMiners)
];
}
addTransactionToList(transaction){
this.pendingTransactions.push(transaction);
}
getWalletBalance(address){
let bal = 0;
for(let block of this.chain){
for(let t of block.transactions){
if(t.fromAddress === address){
bal -+ t.amount;
}
if(t.toAddress === address){
bal += t.amount;
}
}
}
return bal;
}
// .....
}
pendingTransactions property, which will store an array of transactions that are still waiting to be included in a new blockrewardForMiners property defines the number of coins that will be given as a reward for mining the blocks. Since mining requires a lot of computations and machine power, the miners must be compensated for their work.addTransactionToList function takes a transaction record and adds it to the list of pending transactionsmineBlockForPendingTransactions function grabs the list of pending transactions and adds them into the newly mined block when it is completed. Also, once the block is mined, the reward coin for the miner will be stored as a pending transaction. Which means is not available right away. It will be given to the miner on the next completion of mining a new block.getWalletBalance returns the current balance of an addressCurrently, there is a massive problem with our cryptocurrency system: anyone can use any coin in the network. In other words, people can spend the coins that are not even theirs.
To fix this issue, we need to sign each transaction with a private key. By signing I mean adding a signature property to each transaction. So that when we do the calculations to get the wallet balance, we know whom that transaction belongs to. We can get the private key by utilizing the elliptic module.
Let’s get the public and private keys first. In the main project folder run npm i --save elliptic, create a new file called key.js and add the following code.
const EC = require("elliptic").ec;
const ec = new EC("secp256k1");
const keyPair = ec.genKeyPair();
const publicKey = keyPair.getPublic("hex");
const privateKey = keyPair.getPrivate("hex");
console.log("Public: " + publicKey); // Wallet address
console.log("Private: " + privateKey); // Used to sign
secp256k1 algorithm is actually used in Bitcoin to generate keys. Once we run node key.js we will see two keys on the console: one private and one public.
Public: 0419034253dc7f431983904da1adba98fb766a1669f7b8c55d03fb4d2381a1340b88d52c4f26936cab7ee6473285b2d891ad0552ceb1431fd7fab36ca4bfbf4769
Private: c6e9fb1a2b8954e3af2f92ba4ddfb7f8328f6288f4c53f93e7c6aca0a29148b9
Private key should never be shared with others because it is used to sign transactions. Public key serves as a wallet address, so it can be shared with the public.
Next we need to add a few modifications to the chain.js file.
First we need to change the Transaction class to reflect the signing process.
class Transaction {
constructor(fromAddress, toAddress, amount){
this.fromAddress = fromAddress;
this.toAddress = toAddress;
this.amount = amount;
}
getHashValue(){
return SHA256(
this.fromAddress +
this.toAddress +
this.amount
).toString();
}
signTransaction(key){
if(key.getPublic("hex") !== this.fromAddress){
throw new Error("Invalid signature");
}
this.signature = key.sign(this.getHashValue(), "base64").toDER("hex");
}
isTransactionValid(){
if(this.fromAddress === null) return true;
if(!this.signature || this.signature.length === 0){
throw new Error("No signature was found.");
}
const publicKey = ec.keyFromPublic(this.fromAddress, "hex");
return publicKey.verify(this.getHashValue(), this.signature);
}
}
signTransaction and isTransactionValid functions add a signature to each transaction, and verify the existing ones with the help of elliptic node module.
And in the Block class, we can add a new function to validate all the transactions that block holds.
class Block {
// ......
hasValidTransactions(){
for(const t of this.transactions){
if(!t.isTransactionValid){
return false;
}
}
return true;
}
}
Now, let’s create an index file to test all of the code.
Make sure to export the classes from the chain.js file.
const EC = require("elliptic").ec;
const ec = new EC("secp256k1");
const { USDevBlockchain, Transaction } = require("./chain");
const key = ec.keyFromPrivate("c6e9fb1a2b8954e3af2f92ba4ddfb7f8328f6288f4c53f93e7c6aca0a29148b9");
const walletAddress = key.getPublic("hex");
const USDevCoin = new USDevBlockchain();
const t1 = new Transaction(walletAddress, "someone else's wallet address", 2);
t1.signTransaction(key);
USDevCoin.addTransactionToList(t1);
USDevCoin.mineBlockForPendingTransactions(walletAddress);
const t2 = new Transaction(walletAddress, "someone else's wallet address", 2);
t2.signTransaction(key);
USDevCoin.addTransactionToList(t2);
USDevCoin.mineBlockForPendingTransactions(walletAddress);
console.log("My balance: " + USDevCoin.getWalletBalance(walletAddress));
//Prints: My balance: 96
Link to GitHub
In the next and last part of this blog, we will create a neat user interface that will implement the blockchain system we have built.
Cheers!
Prerequisites: Basic knowledge of JavaScript
You might be thinking, why would you even want to build a “Blockchain” system with JavaScript. Isn’t it a language to make websites? Well, it is. But it can also be used to explain the concepts of blockchain in a simple way. Blockchain is already way to big to ignore. Some people still think that blockchain is the same as Bitcoin. Although it may have started with cryptocurrencies, blockchain could be applied in many other areas of our lives, beyond the cryptos, that can change the way our societies function today. In this article, let us clear out the fog before the notion of blockchain and create a simple blockchain system of our own to see how it works under the hood.
In 1440, humanity invented one of the most essential tools in the history – printing press. The printing press allowed us to distribute knowledge to ordinary people, which was only available to a tiny percentage of the population before. Unlike carving or handwriting, printing machines copied and created educational materials much faster. This invention filled a massive gap in the development of human history. Let’s call that gap the “Knowledge Gap.”
Then, towards the end of the 1800s, we invented the first engine. It enabled us to run most of the devices and machines without the use of human labor. It was one of the reasons for abandoning slavery. We could say that this invention filled the “Power Gap“
In the 1980s, there was another invention, that changed the way we communicate, interact, and socialize today – the internet. It was the stepping stones of building the world where the meaning of distance would change completely. The Internet brought everyone closer regardless of their locations. This revolution filled one more gap in history, which is the Distance Gap
Now, you probably guessed where I am going with this. The blockchain technology is going to fill another gap – the Trust Gap. It may seem like people do not care that much about trust for it to be called a “gap in history”, but in many areas, such as business, trust is everything. Success in business heavily depends on trust. People are naturally inclined not to trust businesses. It is a normal thing to do. However, there is an underlying reason for that. The way transact today is not totally transparent. Exchange of goods and services relies on many layers of intermediaries (middlemen). Those middlemen differ from one another with they way keep records, conduct business, etc.
Let’s take buying a used car as an example. There are multiple ways to buy a used car: we could buy it from a dealership or from an individual. Either way, it can be really challenging to get the full history of the car, from the time it was manufactured, to the time it was put on the market for resale. People always try to sell their cars at the highest price. Even if that means hiding an accident or lying about some damages, it may not be possible to see the mechanical issues of the car at the time of testing or negotiation.
What if there was a system of records, where every single event in a car’s history would be captured and visible to everyone? What if it had a secure authentication process and ensured that the records could not be modified once it was added? This is where the blockchain comes in. A blockchain is a distributed, decentralized and immutable public ledger. It uses a reliable set of algorithms to add and keep records of anything we want and make them available to the public.
Before continuing with the article, we need to clarify the meaning of some words.
The first one is decentralized.
Decentralized – means power is delegated from a central authority to regional and local authorities. There is no single point for decision making. For example, look at the fast food franchise chains. Even though they have a parent restaurant that monitors the overall progress, chains are responsible for their own operations. Centralized refers to placing the power and authority in a center. For example, when you want to send a funny picture through Gmail, you log in to your Gmail account, upload the image and send it to a receiver. In this case, you have to trust that Google keeps your message private. You have to trust that they don’t decide to sell your data to someone one day. Also, if the Gmail servers are down, all of your data is gone.
A – Centralized | B – Decentralized
Distributed – refers to the differences of locations. In a non-distributed environment, all the parts of a system are in a single physical location. In a distributed environment, parts of the system are placed in separate locations. For example, say you create a powerpoint presentation and save it your computer. Currently, that document is stored only on your local machine and it is not distributed. Now, say you take a copy of the exact same material and send it to a few of your peers as a backup. Then your document would be stored in a distributed environment.
Immutable – means once a record is created, it can never be modified.
Ledger – is another name for a book or digital system that contains a list of records. For example, a financial accounts book of a company where they track debits and credits.
By the way, actually there are some services, such as Carfax, that keep track of changes to motor vehicles. However, they lack critical components of a trustworthy system: they can be tampered with, and only the company profits from selling information gathered by the community.
So a blockchain is a chain of information blocks stored in a distributed database that maintains a continuously increasing list of records (ledger).
There are three main components of a block:
The type of data in a block depends on the kind of blockchain system. Bitcoin for example stores the history of a transaction between the receiver and sender and the number of coins in a block.
Hash – is just like a digital signature of a block. Each block would have a unique hash value. In technical terms, a hash is a result of turning an arbitrarily large amount of data into a fixed-length key by running it through a hashing algorithm. Bitcoin, for example, uses SHA-256 hashing algorithm.
Furthermore, each block must be linked to the previous block by its hash key. It is critical to keep the chains connected; otherwise the whole system collapses. That is also one of the main advantages of blockchain technology. Even a small change in the chaining invalidates all of the previous blocks.
In order to prevent attacks or tampering on the chains, blockchains implement a mechanism called Proof-Of-Work. It basically slows down the process of adding new blocks. In bitcoin’s case, it takes about 10 minutes to add a new block.
Another vital element of a blockchain system is the Consensus. It means validating each new block by more 50% of the peers before adding it to the chain.
Blockchain is the next revolution that will change the foundation of trust in business. Even though it started out with the popular cryptocurrency – Bitcoin, people have realized that it can be applied in almost any field where the exchange of value occurs. Blockchain is a distributed, decentralized and immutable public ledger that is available for the public. It uses complex cryptographic algorithms to secure and maintain the system.
In the second part of the article, we will be building a simple blockchain system using JavaScript.
Whether we know it or not, trees are everywhere: our computer file systems, HTML DOM, XML/Markup parsers, PDF format, computer chess games, compilers, and others heavily rely on the tree data structure. More practical examples are company hierarchies, family trees, or comments section of any posts. Trees are found to be tricky when implementing in applications and during the coding interviews. How about we take a deep dive in the details of trees and learn the concepts in a more straightforward and fun way? In this article, we look at different types of trees and build a few of them from scratch to solidify our knowledge. Also, we use lots of visuals, which is the key to remembering. Let’s get started!
A tree is a non-linear data structure composed of nodes. It organizes values hierarchically. A node is an entry in a tree, and every node can have zero or more child nodes.
A typical company structure is an excellent example of a hierarchy. There is always a root node at the top of the tree (It looks like a tree when it is flipped upside down) and nodes are connected by edges.
Another example of a hierarchy is the HTML DOM (Document Object Module).
A node is an entry in a tree. It can contain any type of data. It may or may not have child nodes.
Root node is also a parent node to its children.
Nodes are connected by edges.
Siblings are the child nodes of the same parent.
A leaf node is a node that does not have any child nodes in the tree.
The number of links or edges from the root node to a selected node is called the depth of the selected node.
Height of a tree is equal to the maximum depth, or the number of edges from the root to the furthest leaf.
Trees are usually built-in with most of the programming languages. However, to understand it better, we can build one from scratch. Let’s use JavaScript to implement it.
First, we create the Node class that contains the necessary methods to manage the tree.
class Node {
constructor(data){
this.data = data;
this.children = [];
}
add(data){
this.children.push(new Node(data));
}
remove(data){
this.children = this.children.filter(node => node.data !== data);
}
}Then we make the Tree class that can use the Node class to create nodes.
class Tree {
constructor(){
this.root = null;
}
}We utilize both to create and manage a general tree.
const node = new Node(44);
const tree = new Tree();
tree.root = node;There are two major algorithms that we can use to traverse a general tree – Breadth-First and Depth-First.
Breadth-First method tries to stay as close to the root node as possible. Once it starts going through the nodes, it traverses siblings nodes in a row until it reaches that last row.
In DFS, we explore each branch until the end, before moving on to the next branch. It believes in going all the way down to the leaf nodes.
In order to check if a value exists in a tree, we could use either of these algorithms. Let us add these methods to the Tree class we have created earlier and see it in action.
class Tree {
constructor(){
this.root = null;
}
// Breadth-First Search
searchBF(value){
const queue = [this.root];
while(queue.length){
const node = queue.shift();
if(node.data === value){
return true;
} else {
queue.push(...node.children);
}
}
return false;
}
}Breadth-First method first creates a queue with the root element of the tree. It then utilizes a while loop as long as the queue is not empty. When it is empty, it stops. Inside the while loop, it removes the first element and assigns it to a variable. If the removed node contains the value we are looking for, it returns true confirming that the value exists in the tree. Otherwise, it just pushes the children of the removed node to the back of the queue and keeps doing this process until the queue is empty or the value is found.
class Tree {
constructor(){
this.root = null;
}
// Depth-First Search
searchDF(value){
const stack = [this.root];
while(stack.length){
const node = stack.shift();
if(node.data === value){
return true;
} else {
stack.unshift(...node.children);
}
}
return false;
}
}Depth-First method is very similar to the BFS. There is only one small difference. With non-recursive implementations, we use a stack to keep track of the nodes while exploring them instead of a queue. So instead of pushing the child nodes to the back of the array, we unshift them at the front.
Checkout the documentations for shift and unshift, if you are not familiar with them.
DFS and BFS are also commonly used on Graphs
Both of the methods perform the same task – traverse through a tree. It depends on the situation when to use which. Here are some points about the two approaches that can assist in determining the best option.
DFS and BFS Comparison
A binary tree is a very commonly used type of tree that has one distinctive feature – each node in a binary tree can have at most two children.
Also, there are different types of binary trees that we need to be aware of.
A balanced binary tree is a tree that has a “filled look” and can ensure O(log n) times for insertion and search. It does not have to have a perfectly equal number of nodes on each side. It just should not have really short branches or missing pieces.
If every single node in a tree has either two or zero children, we can call it a full binary tree. There cannot be a node with only one child in a full binary tree.
A complete binary tree needs to have almost all levels fully filled from left to right. Only the last level might be unfilled.
Perfect binary trees are the ones that are complete and full. There must be exactly 2^k – 1 nodes in a perfect binary tree (where k is the depth of the tree).
There are three main methods of traversing binary trees: Pre-Order, In-Order and Post-Order traversal.
Pre-order traversal visits the current node, then explores the left subtree, then right subtree. In this type of traversal, the root node is always the first node visited.
class Node {
constructor(data){
this.data = data;
this.right = null;
this.left = null;
}
}class Tree {
constructor(){
this.root = null;
}
preOrder(node){
if(node !== null){
console.log(node.data);
this.preOrder(node.left);
this.preOrder(node.right);
}
}
}With this method, we visit the left branch, then the current node and then the right branch nodes.
inOrder(node){
if(node !== null){
this.preOrder(node.left);
console.log(node.data);
this.preOrder(node.right);
}
}This method explores the node’s children first, left subtree, right subtree, and then the current node itself.
postOrder(node){
if(node !== null){
this.preOrder(node.left);
this.preOrder(node.right);
console.log(node.data);
}
}A tree is a common non-linear data structure that is a part of the applications and devices we use on a daily basis. It can be an extremely efficient way of organizing data when implemented correctly. Furthermore, trees are often discussed in coding interviews, and interviewees find it to be challenging to utilize. In this article, we simplify the tree data structure by looking at it from a high level and getting into details to demystify the tricky concepts.
NEXT: Tree Data Structure Simplified – Part 2
A binary search tree is a binary tree with a unique feature – all nodes to the left of the current node must be smaller than the current node and all nodes to the right must be larger. This rule must be valid for all of the nodes in the tree, not just for the root node.
In terms of performance, Binary Search Tree (BST) is a real competitor for an array. If it takes O(n) to perform an insertion/deletion operation with a sorted array, the same thing can be done in O(log \space n) with BST, if it is balanced.
It is important to note that BST is only useful when it is balanced. An unbalanced BST can be pretty slow – O(n), which defies the purpose of the data structure. There are some trees such as Red-Black Trees or AVL trees that rearrange the nodes during insertion to make sure the tree is always balanced.
Let us implement the Binary Search Tree in JavaScript from scratch.
First of all, we need to define the node class for our tree. Each node needs to have three properties: data, a link to the left child, and another link to the right child. Left and right children are set to null during the Node class implementation.
// Node class
class Node {
constructor(data){
this.data = data;
this.left = null;
this.right = null;
}
}Now we create the BST class with all the essentials functions needed to manage the data in the tree.
// BST class
class BST {
constructor(){
this.root = null;
}
// Methods to be implemented
// insert()
// remove()
}Insert method of the class is fairly simple. First, we create the main method, and then the helper method – insertNode. If the root node of the tree is equal to null on initial insertion, the root node will be initialized with the sent in value.
class BST {
constructor(){
this.root = null;
}
// Creates a new node and calls the insertNode method
insert(data){
const newNode = new Node(data);
if(this.root === null){
this.root = newNode;
} else {
// Finds the right spot to insert the new node
this.insertNode(this.root, newNode);
}
}
insertNode(node, newNode){
if(newNode.data < node.data && node.left){
this.insertNode(node.left, newNode);
} else if(newNode.data < node.data){
node.left = newNode;
} else if(newNode.data > node.data && node.right){
this.insertNode(node.right, newNode);
} else {
node.right = newNode;
}
}
}Remove method is little tricky because we have to consider the reorganization of the tree after the removal of a non-leaf node. Removing a leaf node is done by just assigning null to the parent link. But when the node to be deleted has one or two children, we have to take some additional actions.
To remove a node with one child, we set the pointer from the parent node to null.
In order to remove a node with two children, we have to do three things:
Here is how we implement it in code.
class BST {
constructor(){
this.root = null;
}
remove(data){
// Re-initialize the root node
this.root = this.removeNode(this.root, data);
}
removeNode(node, data){
if(node === null){
return null; // tree is empty
} else if(node.data > data){ // move left
node.left = this.removeNode(node.left, data);
return node;
} else if(node.data < data){ // move right
node.right = this.removeNode(node.right, data);
return node;
} else {
// Delete a leaf node
if(!node.left && !node.right){
return null;
}
// Delete a node with 1 child
if(!node.left){
return node.right;
} else if(!node.right){
return node.left;
}
// Delete a node with 2 children
const min = this.findMinimumValueNode(node.right);
node.data = min.data;
node.right = this.removeNode(node.right, min.data);
return node;
}
}
findMinimumValueNode(node){
// if left node is null, then this node is the minimum
// if not, we recursively find the minimum
return !node.left ? node : this.findMinimumValueNode(node.left);
}
inOrderPrint(node){
if(node !== null){
this.preOrder(node.left);
console.log(node.data);
this.preOrder(node.right);
}
}
getRoot(){
return this.root;
}
}Now we can use methods to create and manage a binary search tree.
const Tree = new BST();
Tree.insert(30);
Tree.insert(9);
Tree.insert(100);
Tree.insert(45);
Tree.insert(166);
Tree.inOrderPrint(Tree.getRoot());
/*
30
/ \
9 100
/ \
45 166
Print: 9 30 45 100 166
*/
Tree.remove(100);
Tree.inOrderPrint(Tree.getRoot());
/*
30
/ \
9 45
\
166
Print: 9 30 45 166
*/Binary heaps are just binary trees with unique features. There are two type of Binary Heaps – Min-Heaps and Max-Heaps.
Min-Heap is a binary tree which must have the following qualities:
Max-Heaps are almost the same as min-heaps except for the elements are in descending order instead of ascending order like in min-heaps.
There are two main methods used with min-heaps: insert and extract_minimum.
To insert a value into a min-heap, we place the new node at the rightmost bottom of the tree. That way we can always make sure that the tree stays complete. Then we need to re-organize the tree to bring the node with the minimum value to the top. The whole process takes about O(log n) to execute.
Extracting the minimum value from the min-heap is simple because the root node always holds the minimum element. The only thing to consider is the time when we need to remove the root node from the tree. In that case, we first remove the minimum element and then set the root equal to the rightmost bottom node. If after the swap the min-heap is out of order, we keep swapping the root node with its children until it is restored.
Heaps can also be stored as arrays. Add a new element to a tree is equivalent of pushing to the back of the array. Traversing the tree when it is an array can be little tricky though. Because it is difficult to know which element is the right child or left child of a node. Therefore, we need to use some indexing technique to accomplish this task. There are various formulas for indexing, but the following is used more often and easy to remember.
Left child: A node at index i has its left child at index 2 * i + 1 That means, node at index 0 would have its left child at index 2 * 0 + 1 => 1
Right child: A node at index i has its left child at index 2 * i + 2 Meaning right child comes after the left child.
Parent: A node’s parent node is located at index (i – 1)/2.
Trie, also called as prefix tree or radix tree, is another type of tree with a distinctive feature – it is designed to efficiently store and retrieve strings. In a trie, we store characters in each node, and each branch down the tree resembles a word.
Here is an example of a trie that stores “Simon”, “Simba” and “Lisa”:
A trie can save a lot of space when implemented correctly. As we can see from the trie above, the words Simon and Simba have the common prefix of “Sim”. So we store that prefix once and use it multiple times.
Tries are especially useful for predicting the possible words given some prefixes. For example, providing suggestions when we are trying to search for a state in a form. We type in “New ” in the form and it shows us what states are available in the dictionary that starts with the word “New “: “New York,” “New Mexico,” “New Hampshire,” etc.
Each node in a trie may have up to 26 children (English alphabet). And there must be a way of identifying the endings of words. Usually, the endings are indicated by adding a special character node to every word. Let’s say we add a node that contains a hashtag character “#” at the end of each valid word.
In the worst case scenario, it can take up to O(k) runtime to perform an insertion or a lookup in a trie. k being the number of nodes. Space complexity can be as bad as O(n*k). However, a trie is a great data structure to implement with applications that heavily rely on prefixes. It is even better than hash tables in this regard because hash tables cannot tell us if a string is a prefix of any word or not.
Hash table is a data structure designed for quick look ups and insertions. On average, its complexity is O(1) or constant time. The main component of a hash table is its hash function. The better the hash function, the more accurate and faster the hash table is. High level process of implementing a hash table is as follows: data is sent to a hash function where it gets evaluated and assigned an index number in an array. The hashing algorithm stores the data under the designated index with a pointer. When a lookup is requested for the same data, the algorithm sends the data to the same hash function and retrieves the index of the data in constant time.
A hash table which is also known as hash map, dictionary or just map is a data structure that arranges data for quickly looking up values with a given key.
Average run time complexity of a hash table is O(1) or constant time.
Hash tables are very similar to arrays. Arrays store values in sequential order and they have indices that can be used to look up values instantly. However, arrays have several restrictions: First of all, the indices are generated by the computer in sequential order. Second, if we want to add a value at the beginning or in the middle of the array, we need to move the rest of the values, which requires O(n) steps in the worst case scenario. And in some cases, when we are using non-dynamic arrays, their sizes are fixed.
Hash tables are like giving super powers to arrays. First, instead of relying on sequential indices, we use a function that turns keys into indices. That function is known as the hash function. Hash function is a special function that takes in a key and spits out an index. There are different ways of making hash function and we will look into them later. So then we store the values under that specific index. Later we can use the same function to get the indices and look up values in constant time just like with arrays.
Let’s look at an example case where using a hash table would be a good fit. Let’s say there is a list of students at a university with basic information. |Name|Major|Year| |-|-|-| |Bob|Math|2| |Sam|Biology|1| |Lisa|Art|3|
Now we are asked to organize this data for quick look ups and insertions. Using a hash table we can easily accomplish this task. First we have to pick a key from the list to identify each record. Typically, it is required to choose some value that is unique for each element. But for simplicity purposes we just pick the student names. So we have an array with 5 slots or buckets. Instead of assigning each record in order, we use a hash function to determine which slot each record goes to. We take Bob and give it to the hash function hash('Bob') and the function returns us an index value of 0, for example. We store Bob’s details under the index 0. Then we send Sam to the hash function, the functions tells us to store Sam’s details in slot 4. We do the same for Lisa and store her information in bucket 3.
Now let’s discuss what happens in our hash function. There are countless ways of making hash functions. It is usually preferred to use the ones on the internet which were tested by many people. However, for the sake of understanding the details under the hood, we can implement a simple one here.
Hash function logic We take ASCII value of each character and add them up.
| Total | %5 | ||||
|---|---|---|---|---|---|
| B | o | b | |||
| 66 | 111 | 98 | 275 | 0 | |
| S | a | m | |||
| 83 | 97 | 109 | 289 | 4 | |
| L | i | s | a | ||
| 76 | 105 | 115 | 97 | 393 | 3 |
For example, for Bob the sum of ASCII values would be 275. Since we have only 5 slots in our array we have to reduce the number to a smaller one. We can use a modulo operator to do that. 275 % 5 = 0
That means we store Bob’s details in slot 0.
Remember we said the run time complexity of a hash table is constant – O(1) earlier? Well, its not entirely true. In the worst case scenario, complexity can be as bad as O(n). Main reason for that is the collisions. Collision is a situation when hash function outputs a duplicate index number.
For example, if we send the name Mia to our previous hashing function, it returns index 4. However, that slot is already occupied.
So there are 2 common ways of handling this issue. First one is called Linear Probing. With linear probing, we look at the given index, and if its occupied we go to the next available slot. In our example, there is no next slot. So in this case, we have to wrap around. Meaning we start from the beginning looking for an empty spot. 0 is also taken. We move to slot 1. That place is empty. We insert Mia at index 1. We keep repeating this process for other values if any collisions occur.
Second method is called Chaining. Here we use Linked list to handle duplicate index issues. If you don’t know what a linked list is, here is a good source to read about it. For this method to work, the hash table needs to be properly implemented. All slots should be pointing to the head of the linked list. Then when there is a collision we store the value in the next chain of the linked list. During look ups we need to ensure to check for all nodes by iterating through the list. That is why run time complexity sometimes can be a O(n)
In JavaScript hash table is called Object.
const hash_map = {
'key':'value'
};Values in objects could be any type: string, array, integer or even another object. For example, to create an object for the data we had earlier we do the following
const map = {
Bob: {
name: 'Bob',
major:'Math',
year: 2,
},
Sam: {
name: 'Sam',
major:'Biology',
year: 1,
}
};If we want to insert new key value pairs in the object, we can do it in two ways. First we can use dot method. Second way is similar to **array look up
map['Lisa'] = {
name: 'Lisa',
major':'Art',
year: 3,
};
// OR
map.Lisa = {
name: 'Lisa',
major':'Art',
year: 3,
};delete map.Bob;
// OR
delete map['Bob']map.Lisa.year = 4;
// Or
map['Lisa']['year'] = 4;console.log(map.Sam.major);
// Output: 'Biology'
// OR
console.log(map['Sam']['major']);
// Output: 'Biology'Cheers
Strapi.js is the most advanced Node.js Framework and Headless CMS out there. Even though it is not as popular as Express.js, it has the power to save weeks of development time for teams working on Node.js applications. With built-in admin panel and Koa.js under the hood, strapi can help you build your next awesome product.
Pre-requisites:
Since the launch of Node.js in 2011, we have seen several frameworks that were built on top of this amazing JavaScript runtime environment. Node.js allowed devs to write fast and robust APIs in minutes. Frameworks gave it super powers. The most popular framework for Node.js is and has been Express.js. Main reason for its popularity is its simplicity and minimalistic style. It accelerates Node.js project development even more. Besides Express.js, there are other frameworks such as Hapi, Koa, Meteor and Sails which have found their way into the hearts of developers. In this article, I would like to write about one Node.js framework that has been immensely underrated in the Node community, but has the power to save weeks of development – Strapi.js. Just stick with me here and we will look at the features of this powerful framework and explore what we can do with it.
Strapi is an open source Headless CMS based on Node.js. It comes with a flexible and customizable admin panel to build fast and secure content APIs. And it is used by thousands of companies around the world such as IBM, Walmart, Discovery and others.
But what is a headless CMS in the first place?
Headless CMS is a type of content management system, such as WordPress, but without the view layer/front end (the head). It means we are not tied to one way of displaying data. We can just plug it into React, Angular or Vue alike view layers. It just provides the APIs and CRUD UI and it can be used with websites, mobile apps widgets, native apps etc. Strapi supports RESTful APIs and also GraphQL.
There are a lot of reasons why you should give Strapi a try on your next project. Below we will go through the main ones.
Strapi is actually built on top of Koa.js, another Node.js framework made by the team who created the Express.js. Koa is a small and more expressive tool which is predicted to be the next generation Node.js framework. Having Koa.js under the hood makes Strapi future proof.
Almost everything in Strapi is plugin. Some of the plugins are installed by default upon creation of the project. Others can be created based on user needs. The real advantage of plugin based framework is that everything is customizable and extensible. Don’t like how the Admin Panel looks, go ahead, customize it. Can’t find the right plugin you are looking for, just create one!
Strapi comes with a built-in content management plugin that allows to easily CRUD content, including media files. Admin user interface is super user friendly and anyone can get started with it within minutes. The fact that the content management feature is actually a plugin means that it can be extended to fit any business needs.
Strapi Admin Panel is built using React.js and the source code is right there inside the project for you to modify if need be. Advanced functionalities of React allows Strapi to deliver amazing user experience.
Designing content type structures is made easy by available field types in the Content Type Builder plugin of the Admin Panel. The following types are accessible right out of the box:
Similar to other plugins, content type builder plugin is also extensible. You can add your own field types to the list!
APIs in Strapi can be requested using GraphQL or REST. Calls to all endpoints are secured by default, utilizing the Authentication and Permissions plugin. More often than not, we want our websites or apps to be used by people with different roles. And developing your own RBAC (Role Based Authentication System) can take weeks of development. Strapi provides that functionality out of the box!
Before we get started with Strapi, make sure you have the latest version of Node (10.x and above)
To install Strapi globally on your machine run the following
npm install strapi@alpha -gNow we can start our new project.
We are going to build a backend for a simple bike rental shop using Strapi.js. We want to have APIs to manage clients, bike inventory and orders.
/users – to manage the client base/bikes – to manage the bike inventory/orders – to keep track of the ordersThe beauty of the framework comes with the “Out of the box” configurations. Once we set up the server and add new models, necessary endpoints for CRUD operations get generated automatically. We can just start using them. Indeed, the APIs can be modified depending on the requirements.
Run the following command to set up a new Strapi project
$ strapi new strapi_cycleWhen prompted with the options in the terminal, we can decide which database we want to use and the kind of configurations we want to have. For simplicity, we will be using a local MongoDB database.
- Choose your main database: MongoDB
- Database name: strapi_cycle
- Host: 127.0.0.1
- +srv connection: false
- Port (It will be ignored if you enable +srv): 27017
- Username: <empty>
- Password: <empty>
- Authentication database (Maybe "admin" or blank): strapi_cycle
- Enable SSL connection: falseNote: If you have any issues connecting to your database, make sure you are using correct username/password. Also, leaving the Authentication databasequery blank can cause problems.
Navigate to the project folder and run
$ strapi startCommand will start the server on port 1337. So if you navigate to localhost:1337 you should see a page similar to this:
In order to create the endpoints for our bike rental shop, we navigate to the built-in admin panel. Click on the /admin link on the welcome page and you should be redirected to registration page.
Since there are no users in the database initially, the user you register first on the this page will have an admin role. Later on when we add more users without specifying the role, they will have a Public role by default. New roles can be added in the Roles and Permissions menu of the sidebar.
Click on the Content Type Builder plugin and you will see that there are 3 content types already created by default. Those content types belong to the Roles & Permissions plugin. Since we do not need to use roles or permissions for our backend, we will just ignore the roles and permissions types for now. Lucky for us, the user content type is already there.
Click on the Add new content type button and enter the details for the model. First we create the bike model.
Once we create the content type, next we have to add new fields. Click on Add new field button and add new fields for our bike model.
| Name | Type | Value |
|---|---|---|
| model | String | |
| rate | Number | |
| status | Enumeration | Available,Taken,Broken |
Repeat steps 4 and 5 for Order model with the following fields
| Name | Type | |
|---|---|---|
| rental_start | Date | |
| rental_end | Number | |
| cost | Integer | |
| user | Relation with User | |
| bikes | Relation with Bike |
An important thing to note here is that creating relations between models is ridiculously easy with Strapi.js. When selecting the type of the field for a model, just select the Relation type and you will be given options on how 2 entities should be related to each other.
In our case, an order can belong to a single user and a many bikes belong to many orders. So their relationship will be as follows:
That’s it! We are pretty much done creating the APIs for users, bikes and orders. In order to see if they are working properly, let’s add some records and make calls to the newly created endpoints.
On the top of the sidebar, we have a list of our models. Click on each of them and add new records with dummy values.
Now we can test our APIs using Postman. If you do not have this awesome tool installed on your machine, please do yourself a favor and download it from here.
Before we can make calls to the endpoints, we need to acquire a token from server. In order to do that, we will send a POST message to localhost:1337/auth/login with the following payload in the body
{
"identifier":"sardor",
"password":"<your_password>"
}
After that we can use the token in the header of each API call
Response body for /orders
[
{
"rental_time": "2020-04-13T13:00:00.000Z",
"rental_due": "2020-04-12T16:00:00.000Z",
"cost": 30,
"bikes": [
{
"model": "M001",
"rate": 10,
"status": "Available",
"_id": "5cbb1f03f3dc0d992df68176",
"createdAt": "2019-04-20T13:30:43.846Z",
"updatedAt": "2019-04-20T13:30:43.965Z",
"__v": 0,
"id": "5cbb1f03f3dc0d992df68176",
"orders": null
}
],
"_id": "5cbb1f9cf3dc0d992df68177",
"createdAt": "2019-04-20T13:33:16.558Z",
"updatedAt": "2019-04-20T13:33:16.687Z",
"__v": 0,
"user": {
"confirmed": true,
"blocked": false,
"name": "",
"_id": "5cbb1eb7f3dc0d992df68173",
"username": "jbourne",
"email": "jbourne@jb.com",
"provider": "local",
"__v": 0,
"role": "5cbb19ea6369dd710e43a720",
"id": "5cbb1eb7f3dc0d992df68173"
},
"id": "5cbb1f9cf3dc0d992df68177"
}
]We are getting 200 status code, which means our APIs are working! If you pay attention to the body of the response, relation among the fields are implemented correctly as well.
Cheers!
Serverless technology is taking over the back-end development world. Some businesses are already dumping microservices infrastructure and switching to serverless. However, the learning curve for serverless is pretty steep and it comes with great complexity. Netlify is trying to solve that problem by providing create & drop functions. In this article, we learn about the main concepts of serverless technology and create a sample application using Netlify functions and React.js.
Pre-requisites:
Since the introduction of AWS Lambda functions in 2014, the word Serverless has been gaining great popularity among businesses and developers. It was told to be the next generation of DevOps after the explosion of containerization. Some people call it the real evolution and say that it will be the future of DevOps. However, the majority has been reluctant to adopt it. They claim that it is not secure enough or requires too much setting up. Which one is more accurate, is everything going to be “serverless” soon or is it just an unjustified hype that will fade away over time?
Either way, we cannot know what will happen in the future. What we can do is to learn about the technology as much as we can and decide if it is a good fit for our development needs or not. Below we will briefly discuss the concepts serverless methodologies and then build a sample application using Netlify functions and React.js.
Serverless is an execution model where cloud providers such as AWS or Azure are responsible for provisioning, maintaining and managing servers for running code. In simpler terms:
So there are servers involved in this model. The difference is – cloud providers handle everything related to servers for a fee, and businesses focus on writing functions.
How is this different from Monolithic way of building applications and Microservices?
As we can see from the picture, the monolithic way is usually the easiest way to setup and build, but it creates major issues when it comes to scaling. Microservices are widely used among many large companies nowadays. However, they require great effort to configure and maintain. Serverless can be a great option when implemented correctly.
Just like any stack, serverless has its own pros and cons. It is up to the businesses to consider all use cases and make an informed decision. Let us take a look at the pros of serverless model.
cron jobs. Which means setting up a script that gets triggered periodically and calls the function. So that the next time when real requests come in, the function will be “warm” and ready to execute.Netlify functions are serverless functions that can be deployed along with the rest of your site to create modern and scalable backend.
They are the real revolution in serverless world. Netlify functions are powered by AWS Lambda and require no setup or ops. Typically, when we want to setup an AWS Lambda function, we need to go through more than 20 steps. Such as creating an AWS account, managing service discovery, configuring API gateways and coordinating deployments and more. Netlify functions take care of the setting up part and allow us to just drop the folder with functions in our project and viola! We have a back-end!
Naturally, there is a certain limit set on the number of function calls we can make in a month for free (125k). But if going serverless is the best option for the business, it is totally worth paying extra money for more bandwidth.
All Netlify functions are version controlled and can be written in JavaScript or Go.
In this section we will be building a simple weather app with Netlify functions, ReactJS and Semantic-UI
Before we get started, make sure that you have the latest NodeJS, and create-react-app installed on your machine.
First we need to create a React application
$ create-react-app semantic_weatherThen navigate to the project folder and install the following npm modules
npm i --save semantic-ui-react semantic-ui-css node-fetch encoding npm-run-allAlso, the following development dependencies are necessary
npm i --save-dev netlify-lambda http-proxy-middleware dotenv Create separate folders in /src for components and css.
To get the icons for the weather app, download this set of icons. Copy the /fonts folder from the package into the /src folder of your project.
After you download the icons package, you should also see the css file named weather-icons.min.css in the there. Copy that file into the /css folder we have just created. Also, while you are inside the /css folder, create a new css file named Weather.css and paste the following code in it:
@media only screen and (max-width: 600px) {
#main-container {
width: 100%;
padding-top: 50px;
}
}
@media only screen and (min-width: 600px) {
#main-container {
width: 50%;
margin: auto;
padding-top: 50px;
}
}
.w-icon {
font-size: 4.5em;
color: #db3fe2;
}
.w-h1 {
font-size: 5em;
}
.w-p {
font-size: 2em;
margin: 20px;
}
.w-error {
color: darkred;
}To insure that our pages have access to Semantic-UI css files, we have to add the following line in src/index.js file of our React project:
import 'semantic-ui-css/semantic.min.css';Also, open your package.json file and make sure it looks similar to this:
// package.json
{
"name": "semantic_weather",
"version": "0.1.0",
"private": true,
"dependencies": {
"encoding": "^0.1.12",
"node-fetch": "^2.3.0",
"react": "^16.8.6",
"react-dom": "^16.8.6",
"react-scripts": "2.1.8",
"semantic-ui-css": "^2.4.1",
"semantic-ui-react": "^0.86.0"
},
"scripts": {
"start": "run-p start:**",
"start:app": "react-scripts start",
"start:lambda": "netlify-lambda serve src/lambda",
"build": "run-p build:**",
"build:app": "react-scripts build",
"build:lambda": "netlify-lambda build src/lambda",
"test": "react-scripts test",
"eject": "react-scripts eject"
},
"eslintConfig": {
"extends": "react-app"
},
"browserslist": [
">0.2%",
"not dead",
"not ie <= 11",
"not op_mini all"
],
"devDependencies": {
"dotenv": "^7.0.0",
"http-proxy-middleware": "^0.19.1",
"netlify-lambda": "^1.4.5",
"npm-run-all": "^4.1.5"
},
"proxy": "http://localhost:9000"
}Now we add the main part of the application – Weather component.
Inside the src/components folder, create a new file and name it Weather.js. Add the following code in it:
// src/components/Weather.js
import React, { useState } from "react";
import {
Header,
Segment,
Container,
Input,
Form,
Loader
} from "semantic-ui-react";
import "../css/Weather.css";
import "../css/weather-icons.min.css";
import { useFetchWeather } from '../customHooks';
const Weather = () => {
const [inputValue, setInputValue] = useState('');
const [searchValue, setSearchValue] = useState('dallas');
const { data, error, loading } = useFetchWeather(
'/.netlify/functions/getWeather',
searchValue
);
return (
<Container id="main-container">
<Segment raised>
<Header className="ui basic segment centered">Semantic Weather</Header>
<Segment>
<Form onSubmit={() => setSearchValue(inputValue)}>
<Input
fluid
action="Search"
autoFocus
placeholder="e.g. Dallas"
onChange={e => setInputValue(e.target.value)}
value={inputValue}
size="large"
/>
{error && <p className="w-error">Please enter a valid city name. (e.g. New York)</p>}
</Form>
</Segment>
<Segment textAlign="center">
{(!loading && data) ? (
<div>
<h1 className="w-h1">{data.temp} °F </h1>
<div>
<i className={`wi wi-owm-${data.weather[0].id} w-icon`}/>
<p className="w-p">{data.weather[0].main}</p>
</div>
<h1>{data.city}, {data.country}</h1>
</div>
) : <Loader active inline='centered' />}
</Segment>
</Segment>
</Container>
);
};
export default Weather;There is one thing missing in the Weather.js file that we have not created yet. useFetchWeather custom hook. This hook will allow us to make a call to the Netlify function we will be creating soon and get weather details for the city provided in the search bar. It is good practice to keep the custom hooks in a separate file. So we create a new file called customHooks.js in /src folder. If you would like to learn more about the React.js custom hooks, checkout this article
// src/customHooks.js
import { useState, useEffect } from "react";
export const useFetchWeather = (url, city) => {
const [data, setData] = useState(null);
const [loading, setLoading] = useState(true);
const [error, setError] = useState(false);
useEffect(() => {
setLoading(true);
fetch(url, {
method: "POST",
body: JSON.stringify({ city: city })
})
.then(r => r.json())
.then(res => {
if (res.cod === 404) {
setError(true);
setLoading(false);
}
return res;
})
.then(res => {
const data = {
temp: res.main.temp.toFixed(0),
city: res.name,
country: res.sys.country,
weather: res.weather
};
setData(data);
setLoading(false);
setError(false);
})
.catch(err => {
setError(true);
setLoading(false);
});
}, [city]);
return { data, error, loading };
};After we add the custom hooks and Weather component, our project folder structure should look like this:
We are pretty much done with the front end. In order for the useFetchWeather custom hook to work, we need to setup the back end. For back end we can take advantage of the Netlify functions. It may seem little confusing how all the pieces of Netlify functions work together. But after you set up your first function, it will be much easier to understand.
First thing is first, let us create the netlify.toml file in then main directory of the project, which will be used by Netlify to figure out where the functions are and how to run them.
// netlify.toml
[build]
Command = "npm run build"
Functions = "lambda"
Publish = "build"Now open App.js file of your project and add the following code to import the Weather.js file we have just created.
// App.js
import React from 'react';
import Weather from './components/Weather';
const App = () => <Weather/>;
export default App;Inside the /src folder create a new folder named lambda. Navigate to that folder and create the function file inside it – getWeather.js.
Add the following code in to the getWeather.js file
// src/lambda/getWeather.js
import fetch from "node-fetch";
require("dotenv").config();
const API_KEY = process.env.API_KEY; // Store your key in .env file
exports.handler = async (event, context) => {
const city = JSON.parse(event.body).city;
const url = `http://api.openweathermap.org/data/2.5/weather?q=${city}&units=imperial&appid=${API_KEY}`;
console.log(API_KEY);
return fetch(url, { headers: { "Accept": "application/json" } })
.then(response => response.json())
.then(data => ({
statusCode: 200,
body: JSON.stringify(data)
}))
.catch(error => ({ statusCode: 422, body: String(error) }));
};As you can see at the top of the function, we have an environment variable which stores the API key for making calls to OpenWeatherMap. To get your own API key, refer here: Get OpenWeatherMap API Key.
Once you get the API key, create a file named .env in the main directory of your project and inside the dotenv file, provide the API key:
API_KEY=XXXXXXXXXXXXXXXXXXXXXXXXXXXXDo not forget to add .env name in your .gitignore file. Otherwise your API key will be stored in your remote git repo along with other project files.
Before we move on to deploying our app to Netlify, you can run it locally to make sure it is working. In your terminal/command line run npm start to start the app in development mode. You should be able to open localhost:3000 and see the weather app.
Next step is it store the project in a remote repository. You can use whatever repository provider you like. I will be storing my project in GitHub.
Once you push the project to a remote repository, we can start the deployment to Netlify. If you do not have an account with Netlify, go ahead and create one!
In Netlify:
Thank you for taking your time to read the article!
If you’ve ever wanted to learn to create art and games with programming, you might have heard of Processing. Processing is a kind of coding sketchbook, used by programmers and artists alike. By using basic programming concepts, you can create beautiful visuals, games, and animations. It also can be used with different languages — you can use their own Java-based language, Python, or Javascript. You can even use it to create Android apps or Raspberry Pi projects.
It’s easy to jump straight in, even with very little coding experience. Today I’ll show you how to create color-shifting brush strokes. This will teach you the basics of drawing to the canvas, manipulating shapes, and adding color.
To start, you first need to download Processing. For this tutorial, I’m using the basic editor which is based on the Java language. Once you have it installed, go ahead and open it up.
We’re starting with a blank editor, but we’ll fill it in soon enough! To start, we need to get our canvas setup. Processing gives you a function for this, which is conveniently named setup. This will run once when our program starts and is used to create everything we initially need for our visual, such as our canvas size and background color. Let’s create a basic black canvas.
void setup () {
size(800, 800);
background(0);
}
What we’re doing here is setting the size of the canvas to 800px wide and 800px tall and giving it a black background color. If you click the play button in the top left corner, you should end up with something like this:
So now you have a basic Processing sketch! Let’s make it a little more interesting now.
We’ll start by drawing a red circle to the canvas. We need to create a draw function — this will loop forever until we stop the sketch, and it runs automatically when you run the sketch so there’s no need to call it. Drawing a red circle to the canvas only takes a few lines of code:
void draw () {
fill(255, 0, 0);
ellipse(50, 50, 50, 50);
}
We’re setting the color of the circle using fill which takes RGB values. So we have red set to 255, while blue and green are set to 0. We then draw the circle itself using ellipse and giving it the x position, y position, height, and width. In this case, it’ll be 50px to the right, 50px down, 50px tall, and 50px wide. When we run the sketch now, we get this:
You can play with the values of fill and ellipse to the change the color, size, and position of the circle. To make our brush strokes, we’re going to have fun with all three of these!
We’re going to let the user now interact with our sketch by letting them use the mouse to control the size and position of the mouse.
First, at the start of our file, we need to add an integer named circleSize and set its initial value to 0. Next, we need to update our draw function to do the following:
Luckily, Processing gives us a lot of tools to do this. Here’s the code to do this:
int circleSize = 0;
void setup () {
size(800, 800);
background(0);
}
void draw () {
if (mousePressed) {
fill(255, 0, 0);
ellipse(mouseX, mouseY, circleSize, circleSize);
circleSize++;
} else {
circleSize = 0;
}
}
In draw, we check if the mouse is pressed, then draw the circle at the x and y coordinate of the mouse. We continually increase the size of the circle while the mouse is pressed — remember, draw keeps looping so circleSize++ will keep increasing that variable. Finally, if the mouse is not pressed, we reset circleSize to 0.
Now run the program and hold down the mouse, and drag on the canvas. You should be able to do something like this:
Next, let’s try adding a little more color. There’s a lot of ways to do this (and I encourage you to play around with it!), but let’s make it so each time we click the mouse it’ll add either more red, green, or blue.
Start by adding three new integer values to the top of our file — one for red, green, and blue. Set them all to 0. We’ll also create an integer value called colorMode and set it to 1. We’ll use this to determine which of our three colors we want to add on a mouse click.
Now, we’ll edit our draw function to check our colorMode and determine which color value to increase.
void draw () {
if (mousePressed) {
fill(red, green, blue);
ellipse(mouseX, mouseY, circleSize, circleSize);
circleSize++;
if (colorMode == 1) {
red++;
}
if (colorMode == 2) {
green++;
}
if (colorMode == 3) {
blue++;
}
} else {
circleSize = 0;
}
}
As you can see, we’ll increase either the red, green, or blue values depending on how this is set. But we also need to reset it when the user releases the mouse. Luckily, processing makes this simple. We need to add a function called mouseReleased and add our logic there.
void mouseReleased() {
colorMode++;
if (colorMode > 3) {
colorMode = 1;
}
}
Now, whenever the mouse is released it’ll switch to the next color. If we go above 3, it’ll reset it back to one. So our order will be red, green, blue, repeat.
Try running the program and playing around with it. You should be able to see the circle expanding and changing color with each new click.
There is one problem though — what happens when all of the values reach 255? Well, with our logic now, they’ll just keep increasing. Which means, eventually we’ll just get a while circle and no more color. There’s a number of options to fix this issue. You could just reset the color back to 0 once it hits 255, but it’s a bit jarring of a change. I wanted something a little smoother, so I opted to make the color values decrease once they hit 255, and increase again when they hit zero. So we’ll oscillate between extremes.
To set this up, we need to set up three new integers again at the top of the value. I named mine redValue, greenValue, and blueValue and set them all to 1. We know that if our color value is equal to 255, we want to decrease it gradually back to 0. Once it hits 0, we want to increase it back up to 255. Let’s add this logic for our red color.
if (colorMode == 1) {
if (red == 255) {
redValue = -1;
} else if (red == 0) {
redValue = 1;
}
red += redValue;
}
Now, run the program and hold down the mouse button. The red should increase to its highest value, then start to decrease. It’ll look like it’s getting brighter and then darker.
Let’s add this to our blue and green now. We’ll end up with a draw function that looks like this:
void draw () {
if (mousePressed) {
fill(red, green, blue);
ellipse(mouseX, mouseY, circleSize, circleSize);
circleSize++;
if (colorMode == 1) {
if (red == 255) {
redValue = -1;
} else if (red == 0) {
redValue = 1;
}
red += redValue;
}
if (colorMode == 2) {
if (green == 255) {
greenValue = -1;
} else if (green == 0) {
greenValue = 1;
}
green += greenValue;
}
if (colorMode == 3) {
if (blue == 255) {
blueValue = -1;
} else if (blue == 0) {
blueValue = 1;
}
blue += blueValue;
}
} else {
circleSize = 0;
}
}
Now, let’s play around with it. Run the program and click and drag a few different times. Watch how the colors shift as we hold the mouse down:
And that’s it! You have a basic brush to play around with and an overview of how Processing works.
I ended up wanting to make more changes to mine. I decided to play around with the opacity of the colors and the stroke. I did that by adding an extra value to my fill method and adding a stroke method on the line above it.
stroke(0, 0, 0, 50); fill(red, green, blue, 50);
The stroke is just the outline around the shape — so you can set it to whatever color and opacity you want. I made mine black, with an alpha value of 50. You can set the alpha to anywhere between 0 and 255, where 0 is 0% opaque and 255 is 100% opaque. I also added this alpha value to my fill color, so my circles are more transparent. By doing that, I get an effect like this:
And that’s it! Take some time to play around with different values and shapes, and dig into the Processing documentation to get some inspiration and ideas. If you prefer using Javascript or Python, checkout P5JS and Processing.py to get started with those. Processing is a very powerful tool and you can make things as simple or complicated as you want, so be sure to have some fun with it!
Here’s the full code:
int circleSize = 0;
int red = 0;
int green = 0;
int blue = 0;
int redValue = 1;
int greenValue = 1;
int blueValue = 1;
int colorMode = 1;
void setup () {
size(800, 800);
background(0);
}
void draw () {
if (mousePressed) {
stroke(0, 0, 0, 50);
fill(red, green, blue, 50);
ellipse(mouseX, mouseY, circleSize, circleSize);
circleSize++;
if (colorMode == 1) {
if (red == 255) {
redValue = -1;
} else if (red == 0) {
redValue = 1;
}
red += redValue;
}
if (colorMode == 2) {
if (green == 255) {
greenValue = -1;
} else if (green == 0) {
greenValue = 1;
}
green += greenValue;
}
if (colorMode == 3) {
if (blue == 255) {
blueValue = -1;
} else if (blue == 0) {
blueValue = 1;
}
blue += blueValue;
}
} else {
circleSize = 0;
}
}
void mouseReleased() {
colorMode++;
if (colorMode > 3) {
colorMode = 1;
}
}