DEV Community: Norbert Braun

Recap of Data Structures with Javascript Part 1

Norbert Braun — Wed, 17 Oct 2018 10:09:40 +0000

I decided to write an article about implementing common data structures. The focus is mainly on coding in javascript rather than on theoretical explanations.

Linkedlists

A linked list is a linear data structure that consists of nodes. Depending on the type of a linked list, nodes have different attributes.

Singly linked list: 2 attributes, the data and a pointer to the next node
Doubly linked list: 3 attributes, the data, a pointer to the next node, and another pointer to the previous one.

In order to loop through the list, we only need access to the starting node (head).

Tasks

Task 1: Create a simple linked list

//LinkedList.js
const Node = (value) => ({
    value,
    next: null
})

const LinkedList = (head = null) =>({
    length: 0,
    set head(node){
        head = node
    },
    get head(){ return head }
})

export default LinkedList

Initially, the head is null and the length equals 0. Let's append nodes to the list.

Task 2: add function

//LinkedList.js
...
add(value){
        if(!this.head){
            this.head = Node(value)
            this.length++
            return this
        }
        let current = this.head
        while(current.next){
            current = current.next
        }
        current.next = Node(value)
        this.length++
        return this
    },
...

First, we check if the head is null. If it is, we set the head to be the new node. If it's not null, we start to loop until we reach the last node in the list. After the while loop, current will point to the last node. Finally, we add the new node to the end of the list. I like to return this because that way I can chain function calls like this: list.add(5).add(6).

If you want some additional practice, you could implement an addTo function which takes a value and position parameters and puts the node to that position.

Task 3: remove function

//LinkedList.js
...
remove(value){
        let current = this.head
        let previous = null
        //deleting the head
        if(current.value === value){
            this.head = current.next
            this.length--
            return this
        }
        //delete from the middle
        while(current){
            if(current.value === value){
                previous.next = current.next
                this.length--
                return this
            }
            previous = current
            current = current.next
        }
        return this
    },
...

As you can see, we have 2 scenarios. If we want to delete the head itself we just have to change the head pointer and decrease the length. If we need to remove something from the middle or end of the list, we need to loop until we get the value. The trick is that in every iteration, we store the previous node as well.
previous.next = current.next is the key here. If we want to remove 2 from a list like this:
1 -> 2 -> 3 Once the control flow jumps into the if statement, the variable previous will be 1, current will be 2 and current.next will be 3. So all we need to do is to "connect" 1 with 3 instead of 2.

Task 4: Find out if the list contains an element or not

//LinkedList.js
...
contains(value){
        let current = this.head

        while(current){
            if(current.value === value){
                return true
            }
            current = current.next
        }
        return false
    }
...

Pretty straightforward. We loop through the list, and return true if we get a value that equals to the value parameter.

Test

I wanted to use mocha & chai to test the implementation of these functions but I am not sure how long this article will be, so I rather save space instead. I created an index.js file to check whether these functions work properly.

//index.js

import LinkedList from "./LinkedList"

const myList = LinkedList()

myList.add(1).add(2).add(3)

console.log(JSON.stringify(myList))

myList.remove(1)
myList.remove(2)
myList.remove(3)
console.log(JSON.stringify(myList))

console.log(myList.contains(1))
console.log(myList.contains(0))

Trees

A tree is a recursive data structure that consists of nodes just like a linked list. However, trees are much different. In this case, the starting node is called root. Every tree has at least one root node and every root has zero or more child nodes.
There are several types of trees out there, in this article I'll focus on binary trees.

Binary Tree

The binary tree is a special type of tree in which every node has zero, 1, or 2 children(left, right).

Binary Search Tree - BST

Okay, so another "sub-class". A binary search tree is a binary tree, but its nodes are ordered in the following way:

Every left node must be < than the current node.
Every right node must be > than the current node.

Tasks

Task 1: Create a simple Binary tree

//BinarySearchTree.js

export const Node = (value) => ({
    value,
    right: null,
    left: null
})

export const SimpleBinTree = (root = null) => ({
    get root() {return root},
    set root(node){ root = node},
})

//That's it. Our dummy binary tree is ready to use.
//index.js

import {SimpleBinTree, Node} from "./BinarySearchTree"

const root = Node(5)
root.left = Node(3)
root.right = Node(10)

const tree = SimpleBinTree(root)

So, tree looks like this:

Task 2: Travel through the tree and visit every node

//BinarySearchTree.js
//add these functions
//to the SimpleBinTree object under the
//getter and setter
inOrder (node) {
    if(node){
      this.inOrder(node.left)
      console.log(node)
      this.inOrder(node.right)
    }
},
preOrder (node) {
    if(node){
      console.log(node)
      this.preOrder(node.left)
      this.preOrder(node.right)
    }
},
postOrder (node) {
    if(node){
      this.postOrder(node.left)
      this.postOrder(node.right)
      console.log(node)
    }
}

There are 3 different ways to traverse a tree recursively. The inOrder approach first visits the left side of the tree, then the root and finally the right side. preOrder and postOrder should be straightforward, they are pretty much the same but they visit nodes in a different order.

//you can call these functions like this
//index.js
tree.inOrder(tree.root) // output should be 3,5,10 (left, root, right)

Task 3: Create a Binary Search Tree

Okay, let's create a more specific tree than the previous one. Let's call it BST. Since SimpleBinTree already has several functions that I do not want to implement again I'll make sure that my BST will "inherit" every function from SimpleBinTree.

//BinarySearchTree.js
export const BST = (root = null) => Object.assign(SimpleBinTree(root),{
    //binary search tree specific functions
})

First, we need the add functionality to populate the tree.

//BinarySearchTree.js
...
add(val){
   if(!this.root){
      this.root = Node(val)
   }else{
      searchTreeToAdd(val, this.root)
   }
},
...

//this function is not part of the object.
const searchTreeToAdd = (val, node) => {
    if(val <= node.value){
        //add to the left side
        node.left ? searchTreeToAdd(val, node.left) :  node.left = Node(val)
    }else{
        //add to the right side
        node.right ? searchTreeToAdd(val, node.right) : node.right = Node(val)
    }
}

First, we check if the root exists. If its null, our new node will be the root.
If there is already a root, then we need to check the value of the new node. If it's less than the current node, that means we need to put it to the left side of the tree. If the value of the node is bigger than the current, we place it somewhere to the right side.

Now, let's determine the minimum of the tree.

//BinarySearchTree.js
...

getMin(node = this.root){
   while(node.left){
      node = node.left
   }
   return node
},
...

It's a very easy function to implement, we iterate on the left side of the tree to find the minimum value.

Here comes the hard part. Removing a node from the tree.

//BinarySearchTree.js
...
remove(value){
   this.root = this.removeNode(value, this.root)
},
removeNode(value, node){
  if(node.value === value){
     if(!node.right && !node.left){
        //node got 0 child
        return null
      }else if(!node.left){
         //node doesn't have a left child so link the right to its parent
        return node.right
      }else if(!node.right){
         //node doesn't have a right child so link the left to its parent
         return node.left
      }else{
         //node has 2 children
         //get the minimum value on the right side
         const minNode = this.getMin(node.right)
         node.value = minNode.value
         node.right = this.removeNode(node.value, node.right)
         return node
      }

   }else if(value < node.value){
         //value is smaller, we search on the left side recursively
         node.left = this.removeNode(value, node.left)
         return node
   }else if(value > node.value){
         //value is bigger, we search on the right side recursively
         node.right = this.removeNode(value, node.right)
         return node
   }
}
...

First, we look for the value that we want to delete. If we got the value (node.value === value), then we need to check the number of children on that node. If it has 0 children, we just remove it. If it has a left or right child, we connect it to its parent. If the node has 2 children, we need to search for the smallest element on the right side, so we can replace the current node with that.

Test

Create an index.js file and import your Binary Search Tree.

//index.js
import {BST} from "./BinarySearchTree"

const myBST = BST()

myBST.add(10)
myBST.add(9)
myBST.add(16)

console.log(myBST.remove(10))
console.log(myBST.root)

console.log(myBST.getMin())

Hashtables

A hashtable is a very powerful key-value data structure. People mostly use it because of its highly efficient lookups. Let me show you a picture for better understanding.

You provide a key, which goes through a hash function that returns an index for that key. After that, you can look up the value in constant time in the array since you know its index.
However, you might have collisions. It means that your hash function returns the same index for different keys. In that case, you have to loop through the array and find the value associated with that key. (This is less efficient takes O(N) where N is the number of collisions for that particular index).

Tasks

Task 1: Create a simple hashtable

//HashTable.js
const HashTable = () => ({
    storage: [],
    storageLen: 4,
})

That's it, we have a HashTable with a storage property, where [key, value] pairs will be stored and a storageLen. Right now it has a value of 4 but if you want to avoid collisions you need to assign a bigger number to it.

Task 2: Create the hash function that returns the index for a key

//HashTable.js
//this function is private. Not part of the HashTable, and I do not export it.
const hashKey = (key, len) => {
    const hash = key
        .split("")
        .reduce( (a, b, index) => a + b.charCodeAt(), "")

    return hash % len
}

It's a really simple hash function producing a lot of collisions if len is small. The function's len parameter will always be the storageLen attribute of HashTable. So every time we call this function, it will give us an index between 0 and 4 (return hash % len). If you change the storageLen attribute to be 15, then it will give us an index from 0 to 15.

Task 3: add values to the hashtable

//HashTable.js
...
//place this function inside the HashTable object
add(key, value){
        //base case. index is unique, just push the key/value pair to the storage
        const index = hashKey(key, this.storageLen)
        if(!this.storage[index]){
            this.storage[index] = [[key, value]]
            return this
        }
        //index already exists
        const isKeyExists = this.storage[index].some(x => key === x[0])

        if(isKeyExists){
            //key already exists, overwrite the previous value
            this.storage[index] = [[key, value]]
        }else{
            //key doesn't exists, but index is not unique -> we have a collision here
            this.storage[index].push([key, value])
        }
    }
...

I tried to comment as much as I can so I hope this function is straightforward.

Task 4: get function (lookup)

//HashTable.js
...
get(key){
        const index = hashKey(key, this.storageLen)
        const keyIndex = 0
        const valueIndex = 1
        const hasCollision = this.storage[index].length > 1
        //base scenario: index is unique so we got O(1) lookup
        if(!hasCollision){
            return this.storage[index][keyIndex][valueIndex]
        }

        //if we have a collision O(n)
        for(const item of this.storage[index]){
            if(item[keyIndex] === key){
                return item[valueIndex]
            }
        }
    }
...

We can pretty easily find out if we have a collision on a particular index const hasCollision = this.storage[index].length > 1. If yes, we need to iterate on that array, and return the item immediately if the keys are the same.

Tests

To test these functions create an index.js and import our HashTable.

import HashTable from "./HashTable"

const hm = HashTable()

hm.add("Goji", "Cica")
hm.add("Pici Bear", 6)
hm.add("Pici Bear", 1)
hm.add("Pici", 8)

console.log(hm.get("Pici Bear"))
console.log(hm)

The End

Thanks for reading. In the second part, I plan to implement data structures like Queues, Graphs, Stacks, Bloom filters :O and other stuff like that.

Async React Basics with Redux-thunk & Redux-saga

Norbert Braun — Mon, 08 Oct 2018 13:43:22 +0000

I have lots of free time lately so I decided to play around a bit with React & Redux. If you want to write maintainable asynchronous code using Redux, you need to pick a middleware like redux-thunk or redux-saga.

What we're building

I love cats, so the functionality of the application is based on the Cat API. You can clone/fork the GitHub repo from here.

The application looks something like this:

If you click the "Fetch cats" button, it sends an HTTP GET request which returns a random cat image. If you click on "Fetch more cats" it returns an array of 5 random cats.
I know it's ugly and stuff but I don't really want to waste time with css. If you are interested in the full "project" and the css files as well, check out the github repo that I have already mentioned above.

The fetchCats function will be implemented using redux-thunk and fetchMoreCats will be written using redux-saga so that we can compare them.

Getting started

create-react-app catapi_app

Let's install some dependencies first.

npm i --save react-redux redux redux-logger redux-saga redux-thunk

Next, we need to setup redux in index.js.

//index.js
import React from 'react'
import ReactDOM from 'react-dom'
import { Provider } from 'react-redux'
import thunkMiddleware from 'redux-thunk'
import { createLogger } from 'redux-logger'
import { createStore, applyMiddleware } from 'redux'
import rootReducer from './reducers/index'

const loggerMiddleware = createLogger()

const store = createStore(
    rootReducer,
    applyMiddleware(
        thunkMiddleware,
        loggerMiddleware ))

ReactDOM.render(
    <Provider store={store}>
        <App/>
    </Provider>, 
    document.getElementById('root')
);

This code will fail, because we do not have our rootReducer. So let's continue with that.

// ./reducers/index.js

import { combineReducers } from 'redux'
import fetchCatReducer from './fetchCatReducer'

export default combineReducers({
    cats: fetchCatReducer
})

We have only one reducer so far, but I like to use combineReducer because if I need to add another one, it's much easier.

This code will still fail because now, we are missing the fetchCatReducer.

// ./reducers/fetchCatReducer.js

const fetchCatReducer = (state = [], action) => {
    switch(action.type) {
        case "FETCH_CATS_SUCCESS":
            return [
                ...action.payload,
                ...state
            ]
        case "FETCH_CATS_START":
            return state
        case "FETCH_CATS_ERROR":
            return state
        default:
        return state
    }
}

export default fetchCatReducer

Whenever we dispatch an action, that action goes through fetchCatReducer and it updates our state accordingly.

"FETCH_CATS_SUCCESS": HTTP request was successful, we must update the state.
"FETCH_CATS_START": HTTP request has been started, this is the right place to for example display a busy indicator to the user. (Loading screen or something)
"FETCH_CATS_ERROR": HTTP request has failed. You can show an error component or something.

To keep the app simple, in case of "FETCH_CATS_START" or "FETCH_CATS_ERROR" I do nothing but returning the previous state.

Redux-thunk

Currently, our app does nothing, because we need an action creator, to fire an action that our reducer handles.

//./actions/fetchCats.js

/*Helper functions. remember, we have 3 action types so far,
 these functions return a plain object that has a 
type attribute that our reducer can handle.
in case of success request, 
the action has a payload property as well. 
That's the response cat from the server 
that we have requested*/

const fetchCatsError = () =>{
    return {type: "FETCH_CATS_ERROR"}
}

const fetchCatsStarted = () =>{
    return {type: "FETCH_CATS_START"}
}

const fetchCatsSuccess = (cat) => {
    return {type: "FETCH_CATS_SUCCESS", payload: cat}
}

// fetching a random cat starts now
const fetchCats = () => dispatch => {
    dispatch(fetchCatsStarted())

    fetch("https://api.thecatapi.com/v1/images/search",{
        headers: {
            "Content-Type": "application/json",
            "x-api-key": "YOUR_API_KEY"
        }
    })
    .then( catResponse => catResponse.json()) 
    .then( cat => dispatch(fetchCatsSuccess(cat)) )
    .catch( err => dispatch(fetchCatsError()))
}

Ye, in order to use this endpoint on CAT API, you need an api key.
fetchCats might look strange at first, its basically a function that returns another function that has a parameter dispatch. Once you call dispatch, the control flow will jump to your reducer to decide what to do. In our case, we only update our application state, if the request has been successful. Btw, that's why I have installed redux-logger. It constantly logs the changes of your state, and actions so its much easier to follow what's happening.

If you prefer the Async/await syntax, then you can implement the above function like this:

const fetchCats =  () => async dispatch => {
    dispatch(fetchCatsStarted())
    try{
        const catResponse = await fetch("https://api.thecatapi.com/v1/images/search",{
            headers: {
                "Content-Type": "application/json",
                "x-api-key": "YOUR_API_KEY"
            }
        })

        const cat = await catResponse.json()
        dispatch(fetchCatsSuccess(cat))
    }catch(exc){
        dispatch(fetchCatsError())
    }
}

App component

I don't want this post to be too long, so I skip the implementations of the components. I'll show you how the App.js looks like, if you are interested in the complete code, check it out on GitHub.


//./components/App.js

import React, { Component } from 'react'
import Button from './proxy/Button'
import CatList from './CatList'
import '../css/App.css'
import { connect } from 'react-redux'
import fetchCats from '../actions/fetchCats'

class App extends Component {
    render() {
        return (
            <div className="App">
                <Button className="primary" text="Fetch cats" onClick={this.props.fetchCats}/>
                <Button className="secondary" text="Fetch more cats"/>
                <header className="App-header">
                    <CatList cats={this.props.cats}/>
                </header>
            </div>
        )
    }
}

const mapStateToProps = (state, ownProps) => ({
        cats: state.cats
})

export default connect(mapStateToProps, { fetchCats })(App);

Redux-saga

Redux-saga is a redux middleware that allows us to easily implement asynchronous code with redux.

To initialize it, we need to adjust our index.js a bit.

//./index.js
...
import createSagaMiddleware from 'redux-saga'
import watchFetchMoreCatsSaga from './saga/fetchMoreCats'

//init
const sagaMiddleware = createSagaMiddleware()

//run
sagaMiddleware.run(watchFetchMoreCatsSaga)
...

In the saga folder, create a new file called fetchMoreCats.

//./saga/fetchMoreCats

import { takeLatest, put } from "redux-saga/effects";

//Every time we dispatch an action 
//that has a type property "FETCH_MORE_CATS"
// call the fetchMoreCatsSaga function
export default function* watchFetchMoreCatsSaga(){
    yield takeLatest("FETCH_MORE_CATS", fetchMoreCatsSaga)
}

//query 5 cat image at the same time
function* fetchMoreCatsSaga(){
    yield put({type: "FETCH_MORE_CATS_SAGA_START"})

   const catResponse = yield fetch("https://api.thecatapi.com/v1/images/search?limit=5",{
        headers: {
            "Content-Type": "application/json",
            "x-api-key": "YOUR_API_KEY"
        }
    })

    const cats = yield catResponse.json()

    yield put({type: "FETCH_MORE_CATS_SAGA_SUCCESS", payload: cats})
}

Those function* thingies are called generator functions. If you want to know more about them, click here.

The takeLatest function can be replaced by takeEvery for example, but one cool feature of takelatest is that it only takes the last "event". In our case, if we rapidly click the button like 100 times, then our app sends 100 requests pretty much DDOSing the API :D. So instead of disabling the button every time it's getting clicked, we can use takeLatest.

As you can see, by calling the put function we can fire actions just like we did with dispatch. So let's adjust our ./reducers/fetchCatReducer.js to handle our new saga actions.

//./reducers/fetchCatReducer.js

...
case "FETCH_MORE_CATS_SAGA_SUCCESS":
            return [
                ...action.payload,
                ...state
            ]
        case "FETCH_MORE_CATS_SAGA_START":
            return state
        case "FETCH_MORE_CATS_SAGA_ERROR":
            return state
...

The watchFetchMoreCatsSaga generator function is constantly listening to the "FETCH_MORE_CATS" action and calls our fetchMoreCatsSaga. So in order to make this work, we need to first fire that action.

//./actions/fetchMoreCats.js

const fetchMoreCats = () => dispatch =>{
    dispatch({type: "FETCH_MORE_CATS"})
}

export default fetchMoreCats

That's it. Every time we call fetchMoreCats, it dispatches {type: "FETCH_MORE_CATS"} which "invokes" our watchFetchMoreCatsSaga that calls fetchMoreCatsSaga.

So we need to import fetchMoreCats in our App.js and call it when the user clicks that button.

//App.js

...
import fetchMoreCats from '../actions/fetchMoreCats'

//put this button in the render method
<Button className="secondary" text="Fetch more cats" onClick={this.props.fetchMoreCats}/>

//we need to map that function to the props of the App


export default connect(mapStateToProps, { fetchCats, fetchMoreCats })(App);

The end

If you want to know more: Saga documentation

If you have any questions, please let me know in the comment section or feel free to email me.

My Node.js Setup (Mocha & Chai, Babel7, ES6)

Norbert Braun — Mon, 01 Oct 2018 17:53:08 +0000

Me and Gojira writing unit tests

Every time I want to code something I try to build a decent development environment for my projects. I usually install Babel to compile ES6/ES7 back to ES5, Mocha & Chai for unit testing purposes, and Nodemon to automatically restart the app.

So I decided to share my experience of setting up node environments from scratch. I hope you may find this information useful.

First, let’s generate an empty package.json for our project.

npm init -y

Now, we can add some development dependencies.

npm install --save-dev @babel/cli @babel/core @babel/node @babel/register @babel/preset-env chai mocha nodemon

After the installation our package.json should look like this:

package.json

Babel 7 packages are now “scoped” so the old babel-cli became @babel/cli.

ES6 & Node

Create an index.js file with a simple function that returns a string so we can test if everything is correct. I always put my index file to the root of a src folder. If you place it somewhere else remember to adjust the path in your package.json scripts accordingly.

./src/index.js


const sayHello = _ => "Hello guys!"

console.log(sayHello())

To see the result, copy and paste the following script to your package.json.

"start": "nodemon ./src/index.js",

After typing npm start in the console/terminal, you will see something like this:

nodemon running

Nodemon monitors every change in your code and automatically starts the application again if you change something. Place an ES6 export statement to the end of the index.js file and run the app again.

export default sayHello

The result is:

Node can’t recognize ES6 export/import keywords. To fix that, we need babel to compile our export default sayHello to something like exports.default = sayHello.

To do that, we need a file in our project root called .babelrc. Copy and paste the following code into it.

{

"presets": ["@babel/preset-env"]

}

Next, we need to adjust our start script as well.

"start": "nodemon --exec babel-node ./src/index.js"

Testing

Okay, let’s write a quick test to see if it works. Remember we have already installed chai and mocha so we can use them without any further configuration.

./test/index.spec.js


import { expect } from "chai"
import sayHello from "../src/index"

describe("index test", () => {
    describe("sayHello function", () => {
        it("should say Hello guys!", () => {

            const str = sayHello();
            expect(str).to.equal("Hello guys!")
        })
    })
})

Also, we need a test script in our package.json:

"test": "./node_modules/.bin/mocha --compilers js:@babel/register"

Three important facts about the test script:

If you install mocha globally with npm install -g you can use "mocha --compilers js:@babel/register" instead.
Since our test file is located in the test folder, mocha finds our index.spec.js automatically.
The --compilers js:@babel/register tells mocha that we use ES6 so it should take care of it. That’s why we installed @babel/register.

Type npm test in your console/terminal and you will see the test passing.

Compiling to the Dist Folder

If you are curious how your compiled ES5 compatible code looks like you can add the following scripts to your package.json.

"build": "babel src --out-dir ./dist --source-maps",

"serve": "node ./dist/index.js",

The npm run build command will create a compiled index.js file in the dist folder and the npm run serve will run that instead of the original in the src folder. We also use --source-maps so that when we debug our ./dist/index.js we can see the actual ES6 code that we wrote.

Debugging

I am a JS developer so I rather debug my code using a browser than an IDE.

Fortunately, node allows us to debug our applications in a browser. Here’s another script for your package.json.

"debug": "node --inspect-brk ./dist/index.js"

After npm run debug you can see the following message.

node debug

Take the highlighted string that was generated for you and append it to this url:chrome-devtools://devtools/bundled/inspector.html?experiments=true&v8only=true&ws=127.0.0.1:9229/.

Then, paste it to the browser and you are done.

Happy debugging!

The End

So, that’s it. Next time, I’ll dig deeper into interesting JS/Python/Rust programming concepts as well.

If you get stuck or know a better way to do this don’t hesitate to leave a comment.

Thanks for reading. Feel free to clone the repository from here.