DEV Community: clusterO

Data Structures in JS

clusterO — Sun, 05 Sep 2021 22:42:57 +0000

Data Structures are a specialized means of organizing and storing data in computers in such a way that we can perform operations on the stored data more efficiently. Here we are going to explore different types of data structures by implementing them in JS, use comments to explore more about each DS.

export default class Data {
  getArray (length) {
    /* an array data structure, or simply an array, is a data structure consisting 
    of a collection of elements, each identified by at least one array index or key. 
    An array is stored such that the position of each element can be computed from its 
    index tuple by a mathematical formula. */

    let arr = new Array(length)
    return arr
  }

  /* a linked list is a linear collection of data elements whose order is not given 
  by their physical placement in memory. Instead, each element points to the next. 
  It is a data structure consisting of a collection of nodes which together represent 
  a sequence. */

  getLinkedList (data) {
    let list = new LinkedList()

    if (data.length == 1) {
      list.head = new Node(data[0])
      return list
    }


    let i = data.length - 1
    let lastNode = new Node(data[i])

    while (--i >= 0) {
      let node = new Node(data[i], lastNode)
      lastNode = node
      list.head = node
    }

    return list
  }

  /* a stack is an abstract data type that serves as a collection of elements, with 
  two principal operations: push, which adds an element to the collection, and pop, 
  which removes the most recently added element that was not yet removed */

  getStack () {
    let stack = new Stack()
    return stack
  }

  /* a queue is a collection of entities that are maintained in a sequence and 
  can be modified by the addition of entities at one end of the sequence and 
  the removal of entities from the other end of the sequence. */

  getQueue () {
    let stack = new Stack()
    return stack
  }

  /* a binary tree is a tree data structure in which each node has at most two children, 
  which are referred to as the left child and the right child. */

  getTree () {
    let binaryTree = new BinarySearchTree()
    return binaryTree
  }

  /* a heap is a specialized tree-based data structure which is essentially an almost 
  complete tree that satisfies the heap property */

  /* A dictionary is a general-purpose data structure for storing a group of objects. 
  A dictionary has a set of keys and each key has a single associated value. 
  Different languages enforce different type restrictions on keys and values 
  in a dictionary. Dictionaries are often implemented as hash tables. */

  HashTable (obj) {
    this.length = 0
    this.items = {}

    for (let p in obj) {
      if (obj.hasOwnProperty(p)) {
        this.items[p] = obj[p]
        this.length++
      }
    }

    this.setItem = function(key, value) {
      let previous = undefined
      if (this.hasItem(key)) {
        previous = this.items[key]
      } else {
        this.length++
      }

      this.items[key] = value
      return previous
    }

    this.getItem = function(key) {
      return this.hasItem(key) ? this.items[key] : undefined
    }

    this.hasItem = function(key) {
      return this.items.hasOwnProperty(key)
    }

    this.removeItem = function(key) {
      if (this.hasItem(key)) {
        previous = this.items[key]
        this.length--
        delete this.items[key]
        return previous
      } else {
        return undefined
      }
    }

    this.keys = function() {
      let keys = []
      for (let k in this.items) {
        if (this.hasItem(k)) {
            keys.push(k)
        }
      }
      return keys
    }

    this.values = function() {
      let values = []
      for (let k in this.items) {
        if (this.hasItem(k)) {
            values.push(this.items[k])
        }
      }
      return values
    }

    this.each = function(fn) {
      for (let k in this.items) {
        if (this.hasItem(k)) {
          fn(k, this.items[k])
        }
      }
    }

    this.clear = function() {
      this.items = {}
      this.length = 0
    }
  }

  getHash () {
    return new Hash('one',[1,10,5],'two', [2], 'three',[3,30,300]);
  }

  /* a graph is an abstract data type that is meant to implement the undirected 
  graph and directed graph concepts from the field of graph theory within 
  mathematics. */

  getGraph () {
    return new Graph()
  }

  /* Matrix is a way to store data in an organized form in the form of rows and columns. 
  Matrices are usually used in computer graphics to project 3-dimensional space onto a
  2-dimensional screen. Matrices in the form of arrays are used to store data in an 
  organized form */

  getMatrix (n, m) {
    let matrix = new Array(m)

    for (let i = 0; i < matrix.length; i++) 
      matrix[i] = new Array(n)

    return matrix
  }

  /* Tensors are a type of data structure used in linear algebra, and like vectors 
  and matrices, you can calculate arithmetic operations with tensors. */

  getTensor (r, s, t) {
    return new Tensor(r, s, t)
  }
}

Cross-origin resource sharing (CORS)

clusterO — Thu, 10 Jun 2021 17:46:24 +0000

Cross-origin resource sharing" (CORS) is a mechanism that allows resources on a web page to be requested from another domain outside the domain from which the resource originated. This is useful for AJAX applications where JavaScript running in the browser may make requests to other domains (e.g. requesting JSON data from a server) or when web pages are served by a web server other than the one that generated them (e.g. when using content delivery networks). CORS is designed to allow safe cross-domain requests, while at the same time preventing malicious cross-domain requests.

In CORS, an HTTP request is made to a server in a different domain using an HTTP method other than GET or HEAD, and includes an Origin header field in the request. The server then checks whether the origin of the request matches any of the origins allowed by the Access-Control-Allow-Origin header field in the response. If so, it returns an Access-Control-Allow-Origin header field in the response containing the origin that was matched. The browser then checks this value against its list of domains and if it matches, allows the resource to be loaded. If it does not match, the resource is blocked from loading.

The following code snippet shows how to use CORS with PHP:

<?php header('Access-Control-Allow-Origin: *'); 
   header('Access-Control-Allow-Methods: GET, POST'); 
   header('Access-Control-Allow-Headers: Content-Type'); 
   header('Access-Control-Max-Age: 86400'); 
?> 

<script type="text/javascript"> // Set up headers for CORS 
   var xhr = new XMLHttpRequest(); 
   xhr.open("GET", "https://example.com/api/v1/user", true); 
   xhr.setRequestHeader("Accept", "application/json"); 
   xhr.setRequestHeader("Content-Type", "application/json"); 
   xhr.setRequestHeader("X-Requested-With", 
      "XMLHttpRequest"); 
   xhr.onload = function() { 
      console.log(this.responseText); 
   }; 
   xhr.send(); 
</script>

For more information about CORS, see What is Cross Origin Resource Sharing? on MDN Web Docs and Cross Origin Resource Sharing on HTML5 Rocks .

Note: In JavaScript, sending a preflight OPTIONS request to find out what origins are allowed for a given resource is not supported by all browsers

Service workers

clusterO — Thu, 10 Jun 2021 17:43:39 +0000

A service worker is a script that your browser runs in the background, separate from a web page, opening the door to features that don't need a web page or user interaction. This includes things like push notifications and background sync.

Note: Service workers are currently only supported in Chrome, Firefox Nightly, and Opera.

The Problem

When you're offline, you don't have access to your server. This means that if you try to send a push notification to a user while they're offline, it won't work. If you try to send an email while they're offline, it won't work. If you try to save a draft of a new message, it won't work.

Even worse, your service worker can't tell the difference between "the user is offline" and "the network is down". It's all the same to the service worker. So if you try to save a draft of a new message while the network is down, it won't work either. You'll end up with two drafts saved on your device: one that's never been sent, and one that's been sent but never delivered.

The Solution

Service workers give us the ability to respond to network conditions using the Offline API. When we detect that the user is offline, we can tell the service worker not to try to do anything that requires a network connection. In this case, that means saving drafts of new messages when we detect that the user is offline.

This also means that we can send push notifications and emails even when the user is offline! And even better: if we detect that the network is down, we can tell the service worker not to try sending any messages at all. We don't want our users to get frustrated by seeing drafts of messages they've already received!

In practice, this looks like this:

The code for detecting if the user is online or offline looks like this:

if (navigator.onLine) { 
   // show "online" indicator 
} else { 
   // show "offline" indicator 
} 
if ( navigator.onLine ) { 
   // show "online" indicator 
} 
else { 
   // show "offline" indicator 
}

As an added bonus, you can also check navigator.onLine for error conditions:

if (navigator.onLine && navigator.onLine.error) { 
   // show error message 
} 

if (navigator.onLine && navigator.onLine.error ) { 
   // show error message 
}

You can use these values in your service worker script as well:

if (navigator.onLine) { 
   // show "online" indicator 
} else { 
   // show "offline" indicator 
}
if (navigator.onLine) { 
   // show "online" indicator 
} else { 
   // show "offline" indicator 
}

Then in your service worker script, you can respond accordingly:

self.addEventListener('fetch', function(event) { 
   var request = event.request; 
   var response = event.response; 
   var type = event.type; 
   switch(type) { 
      case 'fetch': // Note: fetch events don't always have 
         // responses, so check for both fetch and response 
         break; 
      case 'response': // Only do something if it's an HTTP 
         response if (response) { 
            var url = response.url; 
            console.log('Response from ' + url);  
         } 
         break; 
      case 'fetch': // Only do something if it's an HTTP 
         // fetch 
          if (request) {  
             console.log('Request for ' + request); 
             request = null; 
          } 
          break; 
      default: break; 
      } 
   });

Threading

clusterO — Thu, 10 Jun 2021 17:32:36 +0000

The best way to understand the problem is to take a look at the following example. We have two threads that both write to the same file.

// Thread 1 
file.write("Thread 1"); 
// Thread 2 
file.write("Thread 2");

Now, suppose that Thread 1 finishes first, but then Thread 2 is preempted by another thread and has to wait for a while before it can continue execution. If this happens, the operating system has to suspend Thread 2 so that it doesn't try to write to the file while Thread 1 is still writing to it. But what if Thread 1 is still writing to the file when Thread 2 gets preempted? In this case, Thread 2 will be suspended and then resumed again, at which point it will try to write to the file again, which will overwrite whatever was written by Thread 1!

This is called a race condition and it's an easy mistake to make in multi threaded programming. The solution is to make sure that only one thread writes to the file at a time by using a lock:

// Thread 1 
lock(file) { 
file.write("Thread 1"); 
} 
// Thread 2 
lock(file) { 
file.write("Thread 2"); 
}

This way, we ensure that only one thread can be writing to the file at any given time. This works fine as long as we only have two threads writing to the same file, but what if we have more than two threads? In this case, we need some way of ensuring that each thread gets its turn with the lock. This is where condition variables come in. A condition variable allows one thread to wait for another thread to release a lock, and vice versa. Here's how we would use them:

// Thread 1 
lock(file) { 
while (!fileIsWritable) 
wait(lock); 
file.write("Thread 1"); 
} 
// Thread 2 
lock(file) { 
while (!fileIsWritable) 
wait(lock); 
file.write("Thread 2"); 
} 
// Wait until Thread 1 has finished waiting 
bool done = false; 
while (!done) { 
if (signalAndWait(lock)) 
done = true; 
}

The signalAndWait function takes a condition variable and a mutex and releases the mutex so that another thread can acquire it while simultaneously signaling the condition variable so that any threads waiting on it can wake up and continue execution. The signalAndWait function returns true if it was able to release the mutex, false otherwise (for example, if no other threads were waiting on the mutex). The code above shows how we would use signalAndWait in practice: we call signalAndWait on a mutex locked by another thread and then loop until it returns true . The signalAndWait function will release the mutex and then wait on the condition variable until another thread calls signalAndWait or until a timeout occurs (in which case it returns false ).

This ensures that every thread gets its turn with the mutex. If all threads are able to acquire the mutex without having to wait for any other threads, then there are no race conditions and everything works fine. However, if one of the threads has to wait for another thread before acquiring the mutex, then there's a race condition since another thread might acquire the mutex before our waiting thread does and overwrite our data! Note that signalAndWait is not available in Visual Studio 2005 or earlier versions of Visual C++, but you can get it from Boost.

We've seen how we can use locks and condition variables together to ensure that there are no race conditions when multiple threads access shared data. However, locks and condition variables aren't always easy or convenient to use in practice. Locks take up a lot of space in your code because they require you to put code inside critical sections (code blocks surrounded by locks), so you often have many locks scattered throughout your code. It's also easy to accidentally forget to lock a critical section, which can lead to subtle bugs.

About WebSocket

clusterO — Thu, 10 Jun 2021 17:25:21 +0000

WebSocket is a computer communications protocol, providing full-duplex communication channels over a single TCP connection. The WebSocket protocol was standardized by the IETF as RFC 6455 in 2011, and the WebSocket API specification was standardized by the W3C as an extension to the HTML5 specification.

WebSocket is designed to be implemented in web browsers and web servers, but it can be used by any client or server application. For example, a desktop browser can use a WebSocket server as a proxy to send requests to another server.

The WebSocket protocol is based on the HTTP protocol. The WebSocket protocol enables two-way communication between a client (e.g., a web browser) and a server (e.g., a web server). It provides full-duplex communication channels over a single TCP connection. The WebSocket protocol does not rely on opening multiple HTTP connections (e.g., TCP connections) for message passing.

The WebSocket protocol uses the HTTP/1.1 Upgrade mechanism, but it is not restricted to HTTP/1.1 requests and responses. A WebSocket connection is established by opening a TCP connection to port 80 (or port 443) at the originating endpoint, which is then used for two-way communication with the remote endpoint. A WebSocket connection through an HTTP proxy can be established by using an HTTP CONNECT method request.

The WebSocket protocol is layered on top of TCP, so it inherits all of TCP's features, such as its flow control mechanisms and security features (such as TLS). In addition, the WebSocket protocol provides many new features that are not present in HTTP/1.1, such as binary message framing and compression of data using message frames.

WebSocket protocols are implemented in various software libraries that are available for different programming languages and platforms, including JavaScript libraries like SockJS and Node.js libraries like Socket.IO and Faye, Ruby libraries like Faye and EventMachine, Python libraries like Twisted and Tornado, Java libraries like Jetty and Ratpack, PHP libraries like PHP-WebSocket and Pusher, C# libraries like Newtonsoft's WebSocket implementation for .NET Framework 4 or SocketRocket, Objective-C libraries like SocketRocket or SocketStream, Scala libraries like Scalatra or Akka HTTP and many others.

The WebSocket protocol has also been implemented in C using libwebsockets or in Erlang using websocket-erlang; both are available on GitHub.

Async/Await in depth

clusterO — Tue, 17 Nov 2020 14:59:35 +0000

Here we are again, continuing our in-depth series, we are going to talk about a powerful programming concept that every programmer should understand well, let's dive in.

This article is about asynchronicity, i know that this subject is wildly covered in blog posts, YouTube tutorials, and many other places, but it is always approached from one angle and rarely when it gives us a view on the big picture of the matter, that's what we are going to do here, so, we are not going to spend much time on what's already available on the internet, but we are going to say a word about it for the completeness.

Let's start with some definitions, what we mean when we say that a program is synchronous is that it runs in a sequential manner, the program executes every instruction in the order in which it is written when the instruction is totally processed it passes to the next one, and so on. In contrast, an asynchronous program, mildly put, doesn't necessarily respect this rule, it just launches the execution of an instruction and immediately passes to the next one without waiting for the processing of the previous instruction to finish.

The main purpose of this concept becomes clear when we talk in the context of single-thread programming languages, the trade of omitting multi-thread management in favor of less complexity comes with some pitfalls, contrary to multi-threaded programming languages which can launch multiple threads to process different tasks like I/O or a time-consuming function and process them in parallel to the main program, a single thread programming language will hang, waiting for a task to finish so it can get back the control of the thread to run the next task, this result a poor performance, and waste of available processing time.

For that matter, asynchronicity comes to the rescue, as it gives a sense of parallelism to a single thread programming language, the program still runs in a single thread but not in an ordered, sequential manner, it implements some mechanisms that we are going to dig into later, that allow the program to continue its execution while waiting for the results from other tasks.

The first mechanism that implements this concept is CALLBACKS, a function that does something asynchronously should provide a callback argument where you put the code to run after it's complete. I'm not going to spend much time explaining this concept as there are unlimited resources and examples all over the internet, but i think the idea is clear, the problem emerges when a series of functions depend on each other results, we have many nested functions that become a callback hell.

The next mechanism that emerges from this hell called promises, built on callbacks but it allows a much cleaner implementation, as the name suggests, it is a function that promises to return the result whenever it is available, when it finishes the task, it should call one of these callbacks, 'resolve' if the code success, 'reject' if an error occurred, the callbacks are internal to the promise, so you don't have to deal with them directly in the code, that avoids the CB hell, and you just base your code on the promise if it's a success then you execute some task if not you handle the error, besides this it allows a natural order of code, many calls and chaining of CBs hell with the possibility to pass the result value.

Better isn't it?!

Well, the community doesn't stop here, the current implementation of the asynchronicity is much cleaner and straight forward, async/await, a special syntax to work with promises, async before a function means a function always return a promise, other values are wrapped in a resolved promise automatically, await work inside an async function, it makes the program wait until that promise settles.

Now that we covered the big picture of this subject, you know the context in which this works and the different implementations that exist, we can explore how this stuff works.

In reality, it always boils down to callbacks as they are the main mechanism to implement asynchronicity, so we may consider, both, promises and async/await as syntactic sugar and clever CBs implementations that allows your code to be clean and readable, for instance, the async/await uses Generators to achieve its functionality, a generator is a function that can return multiple values instead of just one final return, it uses yield to return many times one after another and on-demand, the await statement is just yielded statement under the hood to pause execution, that allows the async function to pull out the value of a promise even though it is nested inside a callback function.

From an execution angle, you have to know how single thread languages work, a language like JavaScript work with an event loop that decides which code to execute next, an event is fired due to some trigger, and consecutive functions are fired after that until there is nothing to call.

For that matter, it uses some data structures to keep track of the execution timeline, a call-stack (LIFO), a message queue (FIFO), and a job queue (FIFO), you can imagine the event loop as a continuous job that loops on those data structure to execute waiting tasks (messages).

So when a program start, it goes through lines of code in an asynchronous manner, every function call in the way is added to the call-stack to keep track of the execution, what function is currently being run, and what functions are called from within that function, while events (onClick, onLoad, callbacks) are queued in the message queue, with promises, a special queue is implemented to keep track of their execution (job queue).

You can think of this as follow, a message queue is a macro-tasks queue and call-stack is the micro-tasks queue, the event loop check if there is any macro-task, if yes, it takes the oldest one, it executes the correspondent micro-tasks then it goes back in another round to the macro-task and continues this way until its empty.

I hope this article clarifies some concept for you, thanks.

Markdown in-depth

clusterO — Mon, 19 Oct 2020 12:43:52 +0000

Hi there, if you are looking to get familiar with markdown language, or to clear the confusion between markup, markdown, common-mark... and all that jazz, or even go a bit deeper about the subject, you are in the right spot, i hope you enjoy the ride and you take something useful with you from this post.

So, what is all that about, an easy answer is, it's just a text formatting thing, which is not something new, almost every text editor have a text formatting mechanism no matter how rich it is, even with a sticky note now you can make your text bold, italic change the color and make a list, but there are differences between them.

The old well-known system for that matter is WYSIWYG, an abbreviation for what you see is what you get, this one is used in MS word and most texts editors, easy to use and very rich, you can buttons to formats words and phrases, but it's not suitable for all kinds of documents, especially for a web page where you need the syntax to add to the text to indicate which words and phrases should look different, that's where HTML comes to play.

HTML stands for Hypertext Markup Language is the standard markup language for documents designed to be displayed in a web browser, it's a syntax sugar where you add elements to your text to change its look, here is a basic example of that.

<h1>This is a title</h1>

<strong>This text should look bold</strong>

You can add attributes to those elements for further specification and you can apply some styling like CSS for even more formatting, HTML now is fundamental in web development, very rich and very expressive, but with great power comes great fall downs, when applying many elements and attributes the text becomes unreadable, also with the huge number of elements and attributes it becomes challenging to write a document without switching back and forth between the text editor and the HTML interpreter, this opens the doors for markdown language to kick in.

Markdown is a lightweight version of markup, a simpler syntax to add to format a text, and it could be converted to HTML and other formats, it focuses on readability and ease of use, so anyone can work with it without any learning curve. It is mainly used for documentation files, GitHub readme, forum, and blog posts, and with the rise of static site generators, markdown becomes a big player in the web, as almost all the big SSG, from Gatsby to Hugo to Jekyll uses it as the formatting language for their output.

Now that we are familiar with the context let's get a bit practical and see how easy it is to learn how to work with markdown.

<!-- Heading : you only add a # before the text -->
# Heading 1
## Heading 2
### Heading 3
#### Heading 4
##### Heading 5
###### Heading 6

<!-- Italics -->
*This part is in italc* this is not
_This part is in italc_ this is not

<!-- Strong  -->
**This part is in strong** this is not
__This part is in strong__ this is not

<!-- Strikethrough -->
~~Strikethrough this~~ not this

<!-- Separator -->
---
___

<!-- Blockquote -->
> This is a quote

<!-- Links -->
[Some text](Some link)
[Some text](Some link "Some tag")
![Image title](Image link)

<!-- UL -->
* Item 1
* Item 2
  * Nested item

<!-- OL -->
1. Item 1
1. Item 2
1. Item 3

<!-- Inline code bloc -->
`<p>This is a paragraph</p>`

This is it, you can now go to the wild fearing nothing.

After noticing the potential for this easy way to write for the web, many flavors of the language start to appear, the important ones to know about are GFM or GitHub Flavored Markdown which is a superset of commonmark the markdown specification, a standardization effort aims to document various tools and resources available to document authors and developers, as well as implementors of the various markdown implementations, it's basically the same thing with some more capabilities and small variation, the second flavor is Markdown Extra as the name said, it adds features not available with plain Markdown syntax such as

markdown markup inside HTML blocks
elements with id/class attribute
fenced code blocks that span multiple lines of code
definition lists
footnotes
abbreviations

By now you are capable of writing markdown documents, you know the context in which all this jazz is happening, and you can extend your skills by looking at commonmark, GFM, or markdown extra, all of them are well documented and easy to digest. If you are not tired yet, we can dive a bit more here.

The obvious question now is, how markdown works? well, not because it is easy there is not much happening under the hood, it's the opposite, it is easy because it hides the stuff happening behind the scenes. When you write markdown the text is stored in a plain text file with .md or .markdown extension, then you will need a markdown application to process the file by converting it to an HTML so it can be displayed in a web browser or to a print-ready document, for that matter they use a markdown processor called parser, the various implementation of the parser gives you the ability to do almost everything with the language:

Websites
It is essentially designed for the web, so there are a lot of applications for that, for a simple way to do that you can check, blot.im, and smallvictori.es, you only need to signup and have a Dropbox to host your files and boom, you have a website, for more advanced stuff, you can use one of the SSG mentioned above, the advantage to this approach is that GitHub pages provide free hosting for those websites, you can add a CMS to manage your content, easy and free from services like Ghost.
Documents
It doesn't have all the fancy stuff of MS word processors but for basic documents you can do pretty much anything, you can use some authoring application to create and export to PDF then do whatever you want with the PDF, for the authoring part you can use, iA Writer, Ulysses for Mac, iOS and Android, MarkdownPad for Windows and Dillinger or StackEdit for the web.
Notes
Unfortunately, Evernote and OneNote don't support the language yet, there are some other solutions such as SimpleNote, Bear, and BoostNote which can do the work pretty well.
Books
If you are looking to self-publish, Try Leanpub, it's a nice service that takes your markdown files and converts them into an electronic book, it has many output format, it can produce PDF, EPUB, or MOBI.
Documentation
Markdown is a natural fit for technical documentation, if you write documentation for a product or service, you should check these, Read the Docs which generates a documentation website from your open-source markdown, MkDocs, Docusaurus, VuePress those are SSG oriented toward documentation generation.

That's it for now, i hope you get something for this post.