How To Use HTML Validation On Flatpickr

My go to date picker JavaScript library is flatpickr. It has a decent UI that can be customized easily, is lightweight, and is straight forward to implement. There is one particular flaw that I seek to address in this article, that is integrating it with the basic HTML validation.

Motivation

I want to be able to use basic HTML validation on my date inputs. A date input with a simple required attribute should trigger the HTML validation if it is empty upon form submission.

I also would like to prevent users from being able to enter free text in the text field which is meant for date input.

However, flatpickr comes with a flaw that would demand a hack to make it work the way I want.

The Read Only Problem

The cause of its flaw is that flatpickr disables itself by slapping the input with a readonly attribute. A readonly attribute will cause the input to elude the grasp of the basic HTML validation during form submission. This is so as HTML validation ignores readonly, disabled and hidden elements.

The Catch-22 Solution

The immediate solution is to initialize the flatpickr instance with the option allowInput set to true. However, this will allow users to be able to enter free text in the date input, which is what I would also like to guard against.

The Hack

Hence, my solution here is to implement a listener that will toggle the input’s readonly attribute when the date picker dropdown is active, and toggle it back when the user has moved on from date picking.

The Code

flatpickr("[data-behavior='flatpickr']", {
  altInput: true,
  altFormat: 'F j, Y',
  dateFormat: 'Y-m-d',
  allowInput: true,
  onOpen: function(selectedDates, dateStr, instance) {
    $(instance.altInput).prop('readonly', true);
  },
  onClose: function(selectedDates, dateStr, instance) {
    $(instance.altInput).prop('readonly', false);
    $(instance.altInput).blur();
  }
});

Line 1 initializes the flatpickr instance on elements specified by the selector.

Line 2 to 4 are my custom configuration options. I am placing it here to demonstrate the hack for a non default scenario.

Line 2 indicates my intention to display my date values in an alternative format.

Line 3 indicates the alternative format to display in.

Line 4 indicates the date format that will eventually submitted to the form’s action endpoint.

These configurations will tell flatpickr to create 2 inputs.

One is hidden and meant to be submitted to the backend. This input will inherit the attributes of the original input element that would matter during submission, like the name and id. Let’s call this the hidden input.

The other input is meant for display purpose. The value in it will be shown the desired alternative input format. And since it is display, it will inherit the relevant attributes from the original input element that matters for display. For example, the style, class and in particular, the readonly and required attributes. Let’s call this the display input.

Line 5 removes the default readonly attribute that flatpickr will place on its target input elements.

Line 7 defines a function that will be triggered when the dropdown is active. It will find the display input and set it to readonly. This will prevent users from being able to entering any text that will mess up the input value.

Line 10 undo the effect of line 7 in the likely scenario when the user has finished picking the date and the date dropdown closes.

Line 11 handles the behavior where the input cursor remains on the date input when the datepicker dropdown is deactivated. A possible scenario that this might happen is when the user presses the escape key when the dropdown is active. When that happens, the readonly attribute is gone and the user is able to enter any text on the input. Thus, the blur() function prevents this.

How To SSH Into Private Servers Via A Bastion Without Copying SSH Keys

This is a documentation on the the process of accessing the public EC2 instances from a bastion server that is created in the private subnet, as a follow up to the article on setting up a proper cloud infrastructure with basic security for applications on AWS.

Motivation

Once in a while, we need to communicate with the production servers to do checks. The proper way is to setup a bastion server in the public instance and ssh into them. However, setting the bastion server up with the proper configurations might be time consuming to get it right.

On top of that, once we are done, there is a financial incentive to shut the bastion server down to save cost. This will translate to more time consumed to spin it up and down.

Since we might not do this often, we would tend to forget how to set up or shut down the bastion server properly. This translates to more time debugging during each process should any steps be missed along the way.

Hence, it will be nice to have these processes recorded down in code.

Terraform Setup For Bastion Server

The terraform files to setup the bastion server is as shown below. This is a complete copy of the snippet in the article on setting up a standard AWS VPC using terraform. The explanation is there so I would not be covering that here.

# bastion
resource "aws_security_group" "bastion" {
  name = "${var.project_name}${var.env}-bastion"
  description = "For bastion server ${var.env}"
  vpc_id = aws_vpc.main.id

  tags = {
    Name = "${var.project_name}${var.env}"
  }
}

resource "aws_security_group_rule" "ssh-bastion-world" {
  type = "ingress"
  from_port = 22
  to_port = 22
  protocol = "tcp"
  # Please restrict your ingress to only necessary IPs and ports.
  # Opening to 0.0.0.0/0 can lead to security vulnerabilities
  # You may want to set a fixed ip address if you have a static ip
  security_group_id = aws_security_group.bastion.id
  cidr_blocks = ["0.0.0.0/0"]
}

resource "aws_security_group_rule" "ssh-bastion-web_server" {
  type = "egress"
  from_port = 22
  to_port = 22
  protocol = "tcp"
  security_group_id = aws_security_group.bastion.id
  source_security_group_id = aws_security_group.web_server.id
}

resource "aws_instance" "bastion" {
  ami = "ami-061eb2b23f9f8839c"
  associate_public_ip_address = true
  instance_type = "t2.nano"
  subnet_id = aws_subnet.public-ap-southeast-1a.id
  vpc_security_group_ids = ["${aws_security_group.bastion.id}"]
  key_name = aws_key_pair.main.key_name

  tags = {
    Name = "bastion-${var.project_name}${var.env}"
  }
}

resource "aws_key_pair" "main" {
  key_name = "${var.project_name}-${var.env}"
  public_key = "ssh-rsa something"
}

output "bastion_public_ip" {
  value = aws_instance.bastion.public_ip
}

Retrieving AWS EC2 Client

I will be using ruby to carry out the ssh process because I am really bad with shell script 🙁

These snippets here are translated from a rake task which is what I use for my projects. There may be errors here and there so do understand the process rather than just plain copy!

require 'aws-sdk'

aws_access_key_id = `aws --profile #{aws_profile} configure get aws_access_key_id`.chomp
aws_secret_access_key = `aws --profile #{aws_profile} configure get aws_secret_access_key`.chomp

ec2_client = Aws::EC2::Client.new(
  region: region,
  access_key_id: aws_access_key_id,
  secret_access_key: aws_secret_access_key
)

First, initialize an instance of EC2 client. That will require the correct access key id and secret access key. These can be easily retrieve by running the aws configure command in the shell.

Line 3 and 4 does this, given the desired aws_profile, and stores the value in respective ruby variables for use in the rest of the script.

Note that the back ticks (`), among other shell execution commands in ruby, should be used here as it is the only one the returns the output that we need to use. The chomp method removes the line break that is returned along with the output in the shell.

Retrieving The Bastion Server Instance

results = ec2_client.describe_instances(
  filters: [
    {
      name: 'instance.group-name',
      values: ["#{project_name}#{env}-bastion"]
    }
  ]
)

raise 'There are more than 1 reservations. Please check!' if results.reservations.count > 1

raise 'There are no reservations. Please check!') if results.reservations.count.zero?

instances = results.reservations.first.instances

raise 'There are more than 1 bastion servers. Please check!' if instances.count > 1

bastion = instances.first

Next we retrieve the bastion instance via the describe_instances method as shown on line 1.

On line 4 and 5, we narrow down our instances to search for using the filter instance.group-name. This filter refers to the security group that we have attached to the bastion instance (see the terraform files).

The next few lines handle the unexpected scenarios of having multiple reservations and instances. I do not know the difference between these 2 entities, but I guess that is trivial to our mission here.

Eventually, we will have the access to the bastion instance.

Retrieving The Private Web Server Instance

results = ec2_client.describe_instances(
  filters: [
    {
      name: 'instance.group-name',
      values: ["#{project_name}#{env}-web-servers"]
    }
  ]
)

raise 'There are no reservations' if results.reservations.count.zero?

private_ip_addresses = results.reservations.map do |reservation|
  reservation.instances.map(&:private_ip_address)
end.flatten

raise 'There are no private_ip_addresses.' if private_ip_addresses.count.zero?

instance_ip = private_ip_addresses.first

Next, we retrieve web server instances using the same method by filtering their security group’s name. Our target here is the private ip address of any one of the instances. Adjust accordingly if there is a particular private instance you are trying to access.

SSH Into Private Web Server Via Bastion Server

Here comes the main event, the ssh operation.

sh 'ssh-add -D'
sh "ssh-add -K #{Rails.root}/#{project_name}-#{env}"
sh('ssh ' \
'-tt ' \
'-A ' \
"-i #{Rails.root}/#{project_name}-#{env} " \
"ec2-user@#{bastion.public_ip_address} " \
'-o StrictHostKeyChecking=no ' \
"-o 'UserKnownHostsFile /dev/null' " \
"\"ssh ec2-user@#{instance_ip} " \
"-o 'UserKnownHostsFile /dev/null' " \
'-o StrictHostKeyChecking=no"')
sh 'ssh-add -D'

Use the sh utility command in ruby to execute shell script. We are not going to use the output of the commands here, so using back ticks is not necessary.

In this bash session, line 1 clears all ssh identities present if any with the -D option. Note that this bash session is decoupled from the bash session of the current terminal. Hence, at this point of time, there should not be any since it is a new session. We also do not need to worry about erasing the ssh agents that we have added. I am keeping it here for hygiene sake.

Line 2 adds the RSA identity of the key pair, which is used to create the bastion instance, to the ssh agent in the current session.

This step is extremely pivotal. It allows us to forward our ssh agent along with the required RSA identity to the bastion server. The bastion server will subsequently be able to authenticate with the web server due to the forwarded identity.

And realise this. All this is done without the bastion server actually possessing the ssh keys at all! This is immensely beneficial on the security side of things because the bastion server, as a server on the public subnet that is exposed to the Internet, is a point of vulnerability for your private instances. It poses a security risk if attackers are able to access the private instances using the ssh keys in the bastion server. But since the keys are not there, we can make sure Gandalf sees to them.

The command from line 3 onwards is the actual main ssh command.

Line 4 forces a pseudo-terminal allocation for us to interact with the web server once we have established the connection. Multiple t option ensures that the interactive session will be forced even if the ssh did not have a local tty for interaction purpose.

Line 5 forwards the ssh agent through the tunneling. And since we have added the RSA identity to the our ssh agent in this session, the authentication keys are also forwarded in the process, without make a copy in the bastion server itself.

Line 6 points to the identity file required to access the bastion server from our local machine. You would not need this line if you have created your bastion server and your web instances using the same key pair. For this case, this is an extra step that is not necessary as I have set up the web and bastion servers to use the same key pair.

Line 7 states the endpoint of the bastion server and where to ssh into.

Line 8 prevents the ssh mechanism to ask for our confirmation to carry out the operation.

Line 9 prevents our bastion’s ip address to be registered a known host on our ssh known_hosts file. As these bastion servers are meant to be shut down after use, their ip addresses will be different each time we spin them up. Hence, this option will prevent the unnecessary and unmonitored bulging of our known_hosts file.

Line 10 is the command to run after we have successfully ssh into the bastion server. In this case, we are running the a subsequent ssh command to ssh into the web server instance via its private ip address that we found earlier. Note that this command is wrapped in quotes.

To reiterate a few pointers here:

  • This subsequent ssh command does not require any identity file due to the RSA identity that is forwarded
  • The bastion server can access the private instances due to the setup of the security groups
  • The shell interaction session between the bastion server and the web instance is available to use on our local machine due to the -tt option mentioned in line 4.

Line 11 and 12 serve the same purpose as line 8 and, but this time for the bastion server’s ssh operation into the web servers.

Line 13 for hygiene sake, clear the RSA identity from the ssh agent.

Conclusion

There you have it, an ssh session via a bastion server without copying the security keys into it to ensure minimum vulnerability and maximum security!

How To Setup And Debug Google App Script

This is a quick start guide on setting up Google App Script and using it in G Suite applications. Mainly, I will go through Google Sheets and Google Drive since they are the most widely used services.

Motivation

This is meant to remove the layer of repetitive mundane house keeping tasks via automation. In my side hustle, we have shifted our files from dropbox to Google Drive recently, bestowing us the ability to automate our tasks with Google App Scripts.

Setup

Head to your Google App Scripts console. There are many functions you can explore here. I will touch on just 3. Mainly the projects, executions and triggers.

Every project holds the script to execute based on a trigger. It is up to your jurisdiction to decide if a project should uphold a Single Responsibility Principle or do multiple task as part of a bigger singular operation.

Clicking on the ‘New Project’ button near the top left of the screen will bring you to the code editor where you can code your script.

In a script, you can define any number of functions. The exact function to run can be chosen during the trigger selection process. The usual setup is to have a main function, and the other functions are helpers.

Debug

The most important thing in coding is debugging. After all, it makes up most of our time as software developers.

In App Script, there is no luxury to debug the code interactively. You will need to rely on the usual logger. To print a log, write the code as such:

function main() {
  Logger.log('Hello World!');
}

There are 2 ways to view the logs.

First, within the script editor, go to View -> Logs. A dialog box will popup to show you the logs. A shortcut on mac is cmd + enter.

Second, is from the “My Executions” page back in the App Script console. I personally prefer looking at the logs through there because it does not only show its output but also other details like whether it is even running in the first place.

Click on the play arrow button to execute the function for debugging purposes.

Triggers

In the App Script editor, click on the clock icon to bring yourself to the function’s triggers page.

Add a trigger by clicking the bottom right button. A dialog box will popup and you can select the conditions of the trigger.

You can select the function in the script to run, as mentioned earlier, and the type of trigger. For Google Sheets, there are more options for triggering the script. More on that later.

Basics

Before you begin, it is good to know that every entity in G Suite have an id. This id is the gibberish string that you see in the URL of an opened Google Sheets, Google Docs or even a folder in Google Drive. It is highlighted in yellow in the image below.

Google Docs ID

Knowing the id of the particular file or folder allow you to carry out your operations without having to write the code to search for it. Then again, you can search them by name.

The entities that can be called and utilized in the App Script are documented here. Let’s take a look at DriveApp for example.

Example With Google Drive On Time Driven Trigger

Let’s say you want to remove editors you previously gave access to in your files. You want them to be removed when the files are moved into a particular folder.

function removeEditors() {
  var folder = DriveApp.getFolderById(ID_OF_FOLDER);

  iterateFiles(folder);
}

function iterateFiles(folder) {
  var files = folder.getFiles();
  while (files.hasNext()) {
    var file = files.next();
    Logger.log(`Looking at file ${file.getName()}`);

    var editors = file.getEditors();
    editors.forEach(function(editor) {
      var email = editor.getEmail();
      var approvedEmails = [
        'luffy@gmail.com',
        'zoro@gmail.com',
        'sanji@gmail.com',
        'usopp@gmail.com',
        'nami@gmail.com',
        'chopper@gmail.com',
        'robin@gmail.com',
        'franky@gmail.com',
        'brooks@gmail.com',
        'jinbei@gmail.com'
      ];

      if (!approvedEmails.includes(email)) {
        Logger.log(`Removing editor: ${email} from ${file.getName()}`);
        file.removeEditor(email);
      }
    })
  }
}

Given the ID_OF_FOLDER, this script will iterate through all the files in that folder, and for each file it will check if its editors’ emails are under the list of approved emails. If their email is not in the list, they are stripped of the editor role in the file.

Note the way the files variable is being looped. The loop is carried out if hasNext() returns true, and the next file in line is retrieved via next(). This is different from how the editors are looped with forEach, which is, I believe, the usual way developers loop through iterators in JavaScript.

The last step is to setup the time driven trigger to your liking.

The code, unfortunately, cannot be optimized by checking the lastUpdatedDate() of the file and sparing the need to loop through editors for files that were moved into this folder eons ago. This is because moving files into different folders does not update the file’s lastUpdatedDate().

Albeit a small inconvenience, I do expect more features and attributes in the future in App Script to be developed for us to utilize and optimize our codes. Until then, I sincerely hope that it stays free, as it already it right now, without any usage limitation or tiering. In fact, I hope it stays free forever!

Example With Google Sheet OnEdit Trigger

Let’s look at another example with Google Sheet. In a spreadsheet, we want to compile the values entered in a sheet into another sheet in the same spreadsheet in real time. Simple and straightforward. Let’s see how we can work on it.

Before that, take note of an extremely crucial step. Make sure the spreadsheet is a Google Sheet. If you uploaded a Microsoft Excel sheet and opened it using Google Spreadsheet, you will not be able to run any App Script until you convert it to a Google Sheet. If this applies to you, go to File -> Save as Google Sheet as shown below to make this necessary change.

Save as Google Sheets

The function is as shown below.

function compile(event) {
  var row = event.range.getRow();
  var column = event.range.getColumn();
  var value = event.range.getValue();
  var spreadsheet = SpreadsheetApp.getActiveSpreadsheet();
  var targetSheet = spreadsheet.getSheetByName("Target Sheet")
  targetSheet.getRange(row, column).setValue(value * 2)
}

We get the row and column that the user was editing on, whichever sheet that was, and multiply its value by 2 before saving it in the same row and column in the desired sheet with the name Target Sheet.

Now to add the trigger. In the script editor, click on the clock icon. It will bring you to the triggers of this project. Click on the button to add trigger on the bottom right of the page. Under Select event source, you will now see a new option From spreadsheet, and when you select it, you can select the event type to kickstart the function. We are looking for the onEdit event type for this case.

As you can see, this project is associated to only 1 spreadsheet – the spreadsheet it was created from. Additionally, each spreadsheet can have only 1 project as well.

Hence, you cannot have the same script running on different spreadsheet. At least if you did it this way. There may be another way to do so and overcome this restriction but I have yet to explore it.

Potential

The potential of App Scripts does not end here. Other than scripts, you can even code out html views to present visual dashboard based on real time changes.

On top of that, you can publish you own app scripts, as well as use the scripts other developers have made. This forms a community can supercharge automation to increase productivity.

Conclusion

Make use of App Script and automate away!

Customize Devise Forgot Password Token In Rails

This is a documentation on how to change the user flow of forgot password using the devise gem.

Motivation

I often work on projects that are purely API based and are served only on mobile devices as apps. This poses a problem when using devise because its main audience is web application. The user flow that it has set up thus assumes the presence and usage of web pages. That is absent for this case, and setting it up is troublesome to say the least.

In the case of forgot and resetting password flow, the user will receive an email with a link to reset their password. This link leads to a webpage and they will reset their password there and then.

For a pure API environment, this translates to an immense amount of extraneous work required. We need to setup the hosting of the webpages, prepare the styling assets, tweak css codes, wire up the SSL certificate, validate the input fields, and properly redirect from the website into the app once the password has been reset.

And the frustrating thing is that this is a small but essential function in a typical application. We cannot do away with it, but it is often neglected, or should I say taken for granted. And the disproportionally large effort it takes to set it up 1 web page just for this seemingly insignificant function is often overlooked.

I see the need to implement a way devise can allow user to change passwords without the use of webpage.

Project Specifications

The UX flow in my projects will look like this.

The reset password flow will send an email with a token that the users will enter in their app upon submitting the form on forgot password.

The user will enter their new password as well as the token in their app to change their password.

How Reset Password Work In Devise?

Before we can get to work, we need to understand how reset password flow runs in devise.

By default when the user submits his/her email in the forgot password flow, this controller method in the Devise::PasswordsController is called.

# POST /resource/password
def create
  self.resource = resource_class.send_reset_password_instructions(resource_params)
  yield resource if block_given?

  if successfully_sent?(resource)
    respond_with({}, location: after_sending_reset_password_instructions_path_for(resource_name))
  else
    respond_with(resource)
  end
end

The send_reset_password_instructions method is called on the class of the resource. The main code snippet is as shown below, retrieved from the source code in devise github repository.

module Devise
  module Models
    module Recoverable
      extend ActiveSupport::Concern
      protected
        def set_reset_password_token
          raw, enc = Devise.token_generator.generate(self.class, :reset_password_token)

          self.reset_password_token   = enc
          self.reset_password_sent_at = Time.now.utc
          save(validate: false)
          raw
        end
      module ClassMethods
        def send_reset_password_instructions(attributes={})
          recoverable = find_or_initialize_with_errors(reset_password_keys, attributes, :not_found)
          recoverable.send_reset_password_instructions if recoverable.persisted?
          recoverable
        end
      end
    end
  end
end

Eventually, the function set_reset_password_token function will be called to generate the reset_password_token. This method will eventually become one of the User model’s instance methods when it includes the recoverable module.

The logic of generating the reset_password_token is wrapped in the TokenGenerator class of the Devise module as shown below.

module Devise
  class TokenGenerator
    def generate(klass, column)
      key = key_for(column)

      loop do
        raw = Devise.friendly_token
        enc = OpenSSL::HMAC.hexdigest(@digest, key, raw)
        break [raw, enc] unless klass.to_adapter.find_first({ column => enc })
      end
    end
  end
end

As I want user to generate a token that they will need to enter together when they submit their new password after receiving it from an email, I definitely want to dictate the number of characters the token has for the sake of humane user experience. We will see how to tweak this method to generate a token of suitable length.

The function send_reset_password_instructions will also be triggered thereafter to send an email. By default, the reset password token that was generated will be appended to a url that is sent along in that email. That url meant for the users to click and go to a webpage to change their password. For my case, I will not be presenting the url to be clicked in the email, but just the the token string instead.

Generate Custom Reset Password Token

Here we will change the set_reset_password_token for the User model. This will only affect the User model and not other models, which may be crucial for you.

In my projects, I usually have another devise model, ie. the AdminUser model who needs to access to a CMS system. The CMS system is authenticated by none other than devise in the usual devise way. Hence, I do not want to do a site way change to all my models due to this sort of “hybrid”.

Hence, the new code will look like this.

protected
def set_reset_password_token
  raw, enc = Devise.token_generator.custom_generate(self.class, :reset_password_token)

  self.reset_password_token   = enc
  self.reset_password_sent_at = Time.now.utc
  save(validate: false)
  raw
end

The only line that was change is line 3. I am using the custom_generate method, which I define below.

module Devise
  class TokenGenerator
    def custom_generate(klass, column)
      key = key_for(column)

      loop do
        raw = SecureRandom.alphanumeric(Rails.configuration.confirmation_token_length)
        enc = OpenSSL::HMAC.hexdigest(@digest, key, raw)
        break [raw, enc] unless klass.to_adapter.find_first({ column => enc })
      end
    end
  end
end

Compared to the above, the only line that is changed in this case is line 7. The default method uses Devise.friendly_token, the source code of which can be found here.

I replaced it with a custom method of mine to generate and alphanumeric string of a custom desired length.

Seeing that I change so little for each part of the code, I could have just redefined the Devise.friendly_token and save some effort in copying and pasting codes. However, due to the fact that I am still going to have an AdminUser that will make use of the default configuration of devise as it, I cannot apply it site wide. Of course, if I have only 1 Devise model to work with, that will be a plausible route to take.

Send Email With Customized Reset Password Token

So now that the reset_password_token has been generated, it is time to send it out in the email.

There’s nothing to change on the Devise::Mailerclass here. All we need to change is the email view under reset_password_instructions.html.erb. Below is the default view from devise repository.

<p>Hello <%= @resource.email %>!</p>

<p>Someone has requested a link to change your password. You can do this through the link below.</p>

<p><%= link_to 'Change my password', edit_password_url(@resource, reset_password_token: @token) %></p>

<p>If you didn't request this, please ignore this email.</p>
<p>Your password won't change until you access the link above and create a new one.</p

We now have the @token that we can just display for users as a string, and we do not need edit_password_url link to be generated.

Conclusion

This is how we can modify the reset_password_token using devise with the least possible code changes. It involves understanding the flow of logic throughout the different components in devise, as well as the role each component play, so that you know what can and should be modified. The same can be applied to the confirmation flow as well.

This can be integrated with doorkeeper and devise on top of this guide that I wrote on integrating these 2 gems without hiccups since the amount of changes is little and not show stopping.

Class And Instance Methods in Ruby Metaprogramming

This is my own summary on the class and instance methods in relation to metaprogramming in ruby.

Motivation

Many articles out there have already given a detailed write up on this topic. Here I am giving my 2 cents, partly to help me revise when I stumble on this concept again. Because this is how I understand it.

The articles written by various other experienced developers are by no means inadequate. I guess it just people having different learning styles and so here I am documenting mine intending to serve only 1 audience, ie me 🙂

Start With The Syntax

I stumbled on this topic because of the various different syntaxes I have seen in various ruby code bases. And they are nothing like ruby. Weird symbols that go against ruby’s English like syntax and blocks with deep implicit meaning that brings about confusion when reading the code are some examples.

So I thought it is best to come clear with the syntaxes first.

Instance Methods

So there are a couple of ways to define instance methods in ruby.

class Instance1
  def hello
    p "self inside hello is #{self}"
  end

  class_eval do
    def hello
      p "self inside class_eval hello is #{self}"
    end
  end
end

class Instance2
  class_eval do
    def hello
      p "self inside class_eval hello is #{self}"
    end
  end

  def hello
    p "self inside hello is #{self}"
  end
end

Here are 2 classes Instance1 and Instance2 with the same method names and definitions. The only difference is the order which they are defined. And if we take a look at their output:

instance1 = Instance1.new
instance2 = Instance2.new

instance1.hello # "self inside class_eval hello is #<Instance1:0x00007ff17da771c0>"
instance2.hello # "self inside hello is #<Instance2:0x00007ff17d7bbb98>"

The method that is defined later will run. The significance here is that these 2 definitions are in fact the same thing. They are both legit but different ways to define instance methods, and the methods defined later will override the one defined initially as expected.

Class Methods

There are 3 different ways based on my research.

class Class1
  def self.hello
    p "self inside self.hello is #{self}"
  end

  instance_eval do
    def hello
      p "self inside instance_eval hello is #{self}"
    end
  end

  class << self
    def hello
      p "self inside class << self is #{self}"
    end
  end
end

class Class2
  instance_eval do
    def hello
      p "self inside instance_eval hello is #{self}"
    end
  end

  class << self
    def hello
      p "self inside class << self is #{self}"
    end
  end

  def self.hello
    p "self inside self.hello is #{self}"
  end
end

class Class3
  class << self
    def hello
      p "self inside class << self is #{self}"
    end
  end

  def self.hello
    p "self inside self.hello is #{self}"
  end

  instance_eval do
    def hello
      p "self inside instance_eval hello is #{self}"
    end
  end
end

The same thing here. 3 classes with the same 3 methods defined in different order. And yes, the output will be dictated by last one that is defined.

Class1.hello # "self inside class << self is Class1"
Class2.hello # "self inside self.hello is Class2"
Class3.hello # "self inside instance_eval hello is Class3"

No shit. They are just different ways to do the same thing.

Best Practices

So now with the confusion over different syntaxes out of the way, let’s refer to a single class for the rest of the article.

class MyClass
  class_eval do
    def hello
      p "self inside class_eval hello is #{self}"
    end
  end

  instance_eval do
    def hello
      p "self inside instance_eval hello is #{self}"
    end
  end
end

MyClass.hello # "self inside instance_eval hello is MyClass"
MyClass.new.hello # "self inside class_eval hello is #<MyClass:0x00007ff188369ad0>"

These are the best practices to define a class method and an instance method in the metaprogramming way. The instance_eval method is especially important, in my humble opinion, in replacing the class << self syntax that is so baneful in ruby linguistics.

Reading ruby code is like reading English

Why The Need For a Different Way To Define A Method?

One of the purpose of metaprogramming derives from the need to define methods during runtime. They are often used in conjunction with the method define_method to define new methods based on variables that are only available during run time.

An example would be the current_user method in the authentication related devise gem. If you have multiple models, like AdminUser and Player on top of User, you can easily access an instance of them in the context of the controller via current_admin_user and current_player respectively. This is done without you having to copy paste the content of current_user into these “new” methods.

This is made possible due to metaprogramming. devise defines these new methods at runtime, looking at all the models that require its involvement, and generate these helper methods all without writing extra code.

The robustness of metaprogramming is clearly crucial and essential.

The Essence of Instance and Class of a Class

So there is this whole confusion about a hidden class in a class in ruby. This all stems from 1 fact: everything in ruby is an object. That includes a class.

Everything is an object in ruby

So how can a class as we know it, with all its inheritance and class method and instance method properties, be an instance of a ruby object?

This is made possible with the existence of a hidden metaclass whenever a class is defined in ruby. This hidden class holds the common properties of classes as we know them and allow us to use mere ruby objects like a class. There’s a lot of confusion in this sentence due to the overlapping usage of the word class. Be sure to read it again.

Hence class methods are in fact instance methods of this metaclass. These methods of the metaclass are not inherited by the instances of the class, just like how a class method should be.

Singleton Class In Ruby

Another name for these hidden metaclasses is singleton class (‘eigenclass’ is another). I find this naming more apt in the context of ruby (And I will refer to it as singleton class from here onwards). Allow me to explain.

Classes should have a unique namespace in its codebase. Therefore when a class is defined, and so for its corresponding metaclass, it will not be defined again. Its one and only instance of itself will thus exist for the lifetime of the application with no duplicate. This gives the term ‘singleton’ so much more sense.

In fact, I perceive it as the official definition in ruby because of the method singleton_class which gives an object instance access to its “metaclass” instance. Here is an example.

MyClass.new.singleton_class.hello # "self inside instance_eval hello is #<Class:#<MyClass:0x00007faa7a3bb448>>"

Note the memory address of the singleton class. It indicates that this singleton class is in fact an instance.

instance_eval and class_eval

With a better concept of a class, a singleton class and an instance, let’s look at instance_eval and class_eval block.

Initially, it came across to me as unintuitive that a class method is defined under instance_eval, and an instance method is defined under class_eval. Why make life so difficult?

However, once we understand the concept, everything will fall into place.

Under instance_eval, we are looking at the MyClass under the context that it is an instance. We are evaluating it as an instance. And an instance of a class can only refer to the singleton class that will hold anything that should possess the properties of a typical class that we know in computing.

Under class_eval, we are evaluating MyClass as a class, where we define methods to be applied on instances of MyClass as usual.

These 2 methods determine the context in which the methods in it are defined. In particular, it dictates what the variable self refers to in each scope. This article has a much detailed explanation on that.

Conclusion

There’s definitely more to metaprogramming that to define methods during runtime. This idea of using code to generate code has immense potential and this may just be only the tip of the iceberg.

Integrating reCaptcha V3 With Turbolinks In Rails

Google has published the latest new version of reCaptcha V3 and I had to integrate it into my recent Rails projects. The greatest difference between the old version is its improvement in user experience. It removes the user friction where users are required to click on the notorious “I am not a robot” check box and at times take some spontaneous image verification quiz. In its place, the new reCaptcha observes the user’s actions on the website to determine if he/she is a genuine human user. It generates a score which the backend of the website will need to verify against to decide if the score is above the threshold of what is considered a real user. On the frontend, there’s no more extra step required to submit the form. Pretty neat!

In the midst of integrating it to my project, I had some problems, as usual, with turbolinks. The biggest of them is navigating between pages. Hence, this article seeks to document the process.

Initializing

Due to the use of turbolinks, the initialization process is different from what was documented. In fact, there is little to no documentation on the alternative way to initialize the recaptcha library. With reference to this blog, the initialization step is as such.

Note that I am using the slim template engine to generate my HTML views.

// in the < head >
script src='https://www.google.com/recaptcha/api.js?render=explicit&onload=renderCaptcha'
= javascript_pack_tag 'recaptcha', 'data-turbolinks-track': 'reload'

I insert this snippet at the head of the pages that requires reCaptcha using the content_for helper.

This method of requiring the file allow us to use a custom function to initialize the grecaptcha object. This thus provide us control as to when we want to initialize the object so as to prevent reinitialization when navigating between pages in a turbolinks environment.

This method is documented in an obscure area in the recaptcha V3 docs and is also usable in V2 as documented here.

The javascript function renderCaptcha will be called when the file has loaded, and it is constructed in the recaptcha.js.erb file.

Note that this file is given the attribute data-turbolinks-track with a value of reload. This implies that when we navigate between pages where the tracked assets required are different, the site will do a full reload instead of going through turbolinks. In particular for this case when navigating from a page with recaptcha to another without recaptcha, there will be a full reload of the page as the tracked asset, recaptcha.js.erb is no longer present.

This ensures that the recaptcha library is downloaded again and the renderCaptcha function is called when the script is loaded for initialization.

Let’s take a look at the content of the renderCaptcha function.

The Javascript

// recaptcha.js.erb
window.renderCaptcha = function() {
  document.grecaptchaClientId = grecaptcha.render('recaptcha_badge', {
    sitekey: "<%= Rails.application.credentials.dig(Rails.env.to_sym, :recaptcha, :site_key) %>",
    badge: 'inline', // must be inline
    size: 'invisible' // must be invisible
  });
  window.pollCaptchaToken();
}
window.pollCaptchaToken = function() {
  getCaptchaToken();
  setTimeout(window.pollCaptchaToken, 90000);
}
window.getCaptchaToken = function() {
  grecaptcha.execute(document.grecaptchaClientId).then(function(token) {
    document.getElementById('recaptcha_token').value = token;
  });
}
document.addEventListener("turbolinks:load", () => {
  $('#contact-form').on('ajax:success', event => {
    ...
    $('#contact-form').trigger('reset');
    window.getCaptchaToken();
  });
});

Firstly, note that this is an erb file. This allows us to render ruby variables into javascript and compiled by Webpacker during build time. Refer to this documentation on installing erb with Webpacker or my article on setting up bootstrap with Rails 6 and Webpacker on how to set this up. In this case, I am storing my recaptcha site key using the new Rails way since 5.2 and parsing it in the javascript file during build time for consumption.

The renderCaptcha() initializes the recaptcha script and renders the recaptcha badge on an HTML element with the id recaptcha_badge. Once initialized, the getCaptchaToken() will then retrieve the recaptcha token and utilize it in its callback function. I will be setting the value of the an input element with the id recaptcha_token. This input will be sent along to the backend for the backend to use for verification. More on the views in a bit.

My logic is to poll the new token every 1.5 minutes as the token expires every 2 minutes. The 30 seconds buffer should be sufficient for my backend, which will receive the recaptcha token, to verify with the recaptcha server before the token expires. I have split up pollCaptchaToken() with the actual function getCaptchaToken() to get the token because I will be using getCaptchaToken() explicitly after I submit the form to refresh the token.

Note the use of window and document here. These objects persist in between page navigations in a turbolinks environment. Hence, they provide us a way to keep track of data so we do not initialize the function multiple times while navigating back and forth. And the key data to track here is the grecaptchaClientId on the document object. It tracks whether we have initialized the recaptcha script already or not.

That said, remember the data-turbolinks-track attribute with the value reload added to the script? Once again, it ensures the page fully reloads should the tracked assets be any different in between page navigations. This ensures 2 things:

  1. Prevents multiple initilizations occurring while navigating between pages because grecaptchaClientId is not null
  2. Ensures initialization will occur when traversing from a page without the recaptcha script due to a full reload. Otherwise, we will have to wait for the polling function to happened before we can get our token, and that will be disastrous should the user submit the form with a blank token before that.

Lastly, I add an ajax:success event listener on the form to handle a successful remote javascript call to my Rails backend. Note that I cannot add the listener on the document object as such:

$(document).on('#contact-form', 'ajax:success', function() { ... })

As the document object persist between navigation, it will result in the event listener being added each time a page navigation occurs, hence causing undesirable effects.

The View

#recaptcha_badge.d-none data-turbolinks-permanent=''
= hidden_field_tag :recaptcha_token, '', data: { turbolinks_permanent:'' }

The #recaptcha_badge object will hold the badge of the reCaptcha. You can add styling in whatever way you want, but I am using the bootstrap d-none css class to hide it totally as I do not need it.

The hidden_field_tag renders a hidden input field where I will store the recaptcha token.

These elements are given the data-turbolinks-permanent attribute. This is a crucial step. It ensures that the elements with the same id are not re-rendered in between page navigations in a turbolinks environment. Persisting the form element across page loads prevents the input from losing the recaptcha token. Without it, we will need to wait for the polling function to occur again after navigation before we are able to get a new recaptcha token for submission.

That said, the data-turbolinks-permanent on the #recaptcha_badge may not be necessary. But I am just persisting it across pages as well for trivial reasons.

Of course, make sure the input is within the form element so that it gets passed to the backend upon submission.

Conclusion

This new recaptcha user experience is a definitely a good step towards improving conversion. But integrating with turbolinks is troublesome as always. I hope this article helped to address it, and provide enough explanation on why each step are required adequately.

Sort Algorithms Cheatsheet

This is a summary of the key features that make up an algorithm.

Motivation

While it is easy to understand the concept of each sort algorithm, I find it difficult for me to remember the key steps that define an algorithm or is characteristic of that algorithm. That key step may prove to be pivotal in solving the algorithm but may come in as insignificant from the macro view of its concept.

Hence, I decided that it will be better for me to jot the key pointers down.

Quicksort

Key Steps

  • Gist: Using a pivot value, recursively split the array (or segments of array) and its resultant halves, where all the elements in left half is smaller than the pivot and all the elements in the right half is larger
  • 3 steps: stop condition, partition, recursion
    • Stop condition
      • Check if the given left index is strictly smaller than the given right index
      • If they are equal, it means we are dealing with 1 element and there’s nothing to sort
      • Left index should not and will not be more than the right index
    • Partition
      • The key here is to return a partition index
      • Randomly select element and use element value as pivot (pivot index is ignored)
      • Left and right index will traverse towards center
      • Stop incrementing left index when its value is greater than or equal pivot value
      • Stop decrementing right index when its value is smaller than or equal pivot value
      • Swap the values and continue traversing
      • Ensure left <= right (this logic should be hoisted to the top)
      • Return the left index as the partition index
      • This partition index will be the eventual midpoint of this subarray
    • Recursion
      • Call itself twice
      • One will use the given left index and partition index – 1
      • The other will the given right index the partition index + 1

Discussions

  • Each iteration frees up 1 element
  • For each element freed, quicksort is executed lg n times on average
  • Average time complexity is n lg n
  • Worst case is n^2, if the pivot is always the smallest/largest value, so need to be careful when choosing pivot
  • Randomize selection of pivot to effectively reduce probability of hitting worst case
  • In place sorting algorithm where no extra memory is needed and the operation can be carried out on the array itself

Mergesort

Key Steps

  • Gist: first recursively halve array until we are dealing with 1 element, then recursively merge the elements back in a sorted order until we get back the array of the same size, and now it will be sorted
  • A recursive function that consist of 3 parts in order: split, recursion, merge
  • We will mutate the array, but it will not be an in place sorting. This is because it is difficult to do so.
  • So first create an empty arrayCopy of same size to temporarily hold the values of  sections of the original array that are already sorted to be overwritten into the corresponding section in the original array.
  • Split
    • Given a subarray array, the arrayCopy, the leftStart and rightEnd of the subarray to be split
    • Continue splitting and duplicate a copy of the left half and the right half
    • Stop condition: Stop the current iteration if the given array is only 1 element and just return
  • Recursion
    • Call itself on the left half
    • Then call itself on the right half
    • So the splitting will continue until we are dealing with 1 element to kick start the merge
  • Merge
    • Dealing with the same subarray from the split step, provided with the leftStart and rightEnd of the subarray
    • The leftEnd and the rightStart are at the midpoint of this subarray
    • These 4 key indices mirror the indices in the original array
    • Traverse from leftStart to leftEnd together from rightStart to rightEnd
    • Fill up the arrayCopy in ascending order
    • Ensure the indices do not overshoot its respective end
    • Eventually, one half will have all its elements filled up in the arrayCopy, while the other half can simply append the remaining elements to the arrayCopy from where it left off
    • The arrayCopy is sorted for that exact portion  of the original array, so we will overwrite that portion of the original array with the same portion of the arrayCopy
    • That portion of the original array may not be sorted in contemplation of its whole, but that will be addressed and its values overwritten in the subsequent merge steps.

Discussions

  •  Time complexity of n lg neven in worst case
  • Need extra n space for the array copy

Insertion sort

Key Steps

  • Gist: insert elements one by one from unsorted part of array into sorted part of array
  • Divide the array into sorted portion and unsorted portion
  • Sorted partition always starts from the first element, as array of 1 element is always sorted
  • First element of unsorted array will shift forward until the start of the sorted portion of the array OR until it meets an element bigger than itself
  • Order of the sorted portion is maintained
  • The last element of the sorted array takes its place
  • The next iteration start on the next element of the unsorted portion, which is now the first element of the current unsorted portion
  • The loop mutates the array

Discussions

  • Best case is an already sorted array, so no shifting of elements from the unsorted to the sorted portion of the array, resulting in a time complexity of n
  • The worst case is a reverse sorted array, which results in the whole sorted array having to shift for each iteration. The first element of the unsorted portion of array is always at the the smallest and need to go to the front of the sorted portion. Time complexity is n^2

Selection sort

Key Steps

  • Gist: scan array to find the smallest element and eliminate it for the next iterations
  • Swap smallest element with the front most element
  • Scan the array in the next iteration excluding the smallest element(s)
  • Last remaining single element will be of the largest value, so iterations take place until n - 2

Discussions

  • Time complexity is n^2

Bubble sort

Key Steps

  • Gist: keep swapping adjacent elements if left is larger than right down the array, and repeat this iteration for as many time as there are elements in the array
  • End before the 2nd last index so that we do not go out of bound when comparing the current element with the next for swapping
  • The largest elements starts forming at the end of the array
  • Subsequent iterations can end before the already sorted section of the array at the end as optimization
  • A flag reseted at each iteration can be used to end the function early if no swap is detected for the current iteration, which would mean the array is already sorted

Discussions

  • Time complexity is n^2

Connecting MSSQL Database Using Ruby On Rails

This is a documentation on how to connect to a MSSQL database in a Rails application. We will use FreeTDS as the main toolkit to establish the connection.

Motivation

I came across a gig that requires me to connect to a MSSQL database to extract the data via the application that I was building in Ruby On Rails. I spend quite some time experimenting  and playing with it before I can manage to get it to work.

It will be good to document my steps and reasons in case I come across another such request and my memory fails me.

Installation

While Ruby on Rails has a gem that serves as a wrapper around the FreeTDS library of files, it requires the FreeTDS binaries to be installed natively on the machine that is running the application.

This presents a number of challenges. First, the local machine used may be different for different users. Second, the operating system used in the servers and local machine may be different too.

For my case, I use macOS for my development work, and the Amazon flavored linux for my staging and production sites.

Installing FreeTDS on macOS

The steps listed here follows this guide closely.

First, install using these files locally in the kernel using homebrew.

​
brew update
brew install unixodbc freetds

ODBC is an API that is meant for database access across different platforms. unixODBC is the driver manager that allows unix systems to connect to ODBC-capable databases.

MSSQL is one such database. However, while it uses ODBC for connection, it uses the TDS protocol on the application layer for communication. Hence, a ODBC driver alone is insufficient for the machine to process the data in the database. This is where FreeTDS comes in.

FreeTDS is a set of libraries that will do the translation and allow our application to connect to the database and retrieve the data.

Installing TDS on Amazon Linux

Credits to this answer on stackoverflow. He even gave the steps required to install the packages via Elastic Beanstalk, which is convenient for me as I also use Elastic Beanstalk for deployment.

[ ! -e /home/ec2-user/freetds-1.00.86.tar.gz ] && \
wget -nc ftp://ftp.freetds.org/pub/freetds/stable/freetds-1.00.86.tar.gz -O /home/ec2-user/freetds-1.00.86.tar.gz || \
true

The first section of the code that is enclosed within a pair of square bracket is a unix command to check the existence of the zip file, which contains the necessary libraries, in the home path of the server. In the Amazon Linux system, the home path is /home/ec2-user by default. Adjust accordingly if you are installing in a linux local machine.

Should the file exist, the subsequent command to download the file will not be executed due to the logical && operation.

The last || operation with a true ensures the command returns a true, and the whole Elastic Beanstalk process will continue even if the file already exist. Of course, this step is not necessary if we are installing the libraries manually on our local linux machine.

[ ! -e /home/ec2-user/freetds-1.00.86 ] && \
tar -xvf /home/ec2-user/freetds-1.00.86.tar.gz -C /home/ec2-user/ || \
true

Similarly this step check for the presence of the unzipped file to prevent repeated and unnecessary unzipping of the compressed library.

[ ! -e /usr/local/etc/freetds.conf ] && cd /home/ec2-user/freetds-1.00.86 && \
sudo ./configure --prefix=/usr/local --with-tdsver=7.4 || \
true

[ ! -e /usr/local/etc/freetds.conf ] && \
( cd /home/ec2-user/freetds-1.00.86 && sudo make && sudo make install ) || \
true

The next 2 commands set up the configurations for FreeTDS and start finally installing its libraries. Upon installation, the config file freetds.conf will be produced, which explains the checks against its existence to prevent duplicate installation operations.

Application in Ruby on Rails

With the FreeTDS libraries installed in the kernel, we can look at how to use the tiny_tds gem to communicate with the MSSQL database. After installing it via bundler, we can sue the following commands to connect.

client = TinyTds::Client.new(
  username: Rails.application.credentials.dig(Rails.env.to_sym, :deltek, :username),
  password: Rails.application.credentials.dig(Rails.env.to_sym, :deltek, :password),
  host: Rails.application.credentials.dig(Rails.env.to_sym, :deltek, :host),
  port: Rails.application.credentials.dig(Rails.env.to_sym, :deltek, :port),
  database: Rails.application.credentials.dig(Rails.env.to_sym, :deltek, :database)
)

Following the new practice of using credential file to store secrets, I have stored all the database credentials in the encrypted credential.yml.enc file.

client.execute("
  SET ANSI_WARNINGS ON;
  SET ANSI_PADDING ON;
  SET ANSI_NULLS ON;
  SET QUOTED_IDENTIFIER ON;
  SET ANSI_NULL_DFLT_ON ON;
  SET CONCAT_NULL_YIELDS_NULL ON;
  SELECT @@OPTIONS;
").each

This next snippet sets the settings of the connection. I would not pretend to understand the reasons for the settings made here. However, this is the final settings that worked for me to make the subsequent queries to the database tables. I came to this final configurations after googling around for the different errors that were thrown at me while getting TDS to work.

result = client.execute("SELECT TOP 1 * FROM SOME_TABLE").each

This is an example of executing a query in SQL language. The result variable will be an array of hashes, where each hash represent 1 row of record.

result = client.execute("SELECT TOP 1 * FROM SOME_TABLE").each

Last but not least, make sure to close the client’s connection. This is not active record that “automagically” does that for you.

Data Structures Cheatsheet

This is a concise glossary of the concepts, features and applications of various data structures.

Motivation

Due to the coronavirus outbreaks, the major lockdowns in Europe that ensued, and the stay home quarantine I have to undergo upon return to my country, I am ceasing my digital nomad life, which I have recorded in my Instagram account. So here I am, refreshing my memory on data structures as I prepare to welcome a new phase of my life.

I have a problem finding a good concise cheatsheet that can properly remind me of the concepts of all the data structures, their key features and their runtime performance for various operations. More importantly, when to use them and, as I am a rubyist, how are they applied in ruby.

Each section will talk about 1 data structure. It will consist of the main concept behind how they are constructed, some key features that are unique to them, when it is the best use case for them, and if there is something similar in ruby. These concept follows the HackerRank’s youtube channel’s playlist on Data Structures.

ArrayList

An arraylist is a dynamic array that will expand its capacity when it reached its maximum. An array requires pre allocated memory to be created. That means we need to establish the size of each element in the array and their total count.

Typically, when the arraylist reaches capacity, its size will be doubled by some complicated built-in algorithm in one of the library files of the language. It also has methods that can be called manually to ensureCapacity of the array.

Array and arrayList are used interchangeably in this article.

Key Features

  • Expands capacity when required

Runtime

  • Access: O(1) with use of known index of element in array
  • Search: O(n)
  • Insert
    • prepend: O(n) due to need to shift all elements
    • append: O(1)
  • Deletion: O(n) due to need for search to destroy

Applications

  • List of items of any kind of order

Ruby Alternative

In ruby, everything is an object. That includes arrays. Arrays in ruby are made dynamic to behave like ArrayList, like in most other dynamic languages. The array object has some operation to ensure capacity for the array.

It is also heterogenous, which allows for different data types exists together as elements of the same array (since all of them are objects anyway).

Binary (Search) Tree

Trees are most of the time referring to binary trees. Each node in binary tree can have a maximum of 2 nodes. This “tree” is kind of like a linked list of objects. It is not an array.

And for binary search tree (BST), it has to have an increasing order in relation to a node from its left to right nodes. Based on this rule, the binary search can be carried out by propagating through the nodes by asking the deterministic question: Is the left node more or less than the right node. With a known sort order, each iteration can, probably, halve the total nodes to search. This results in a faster search time.

This is only  “probably” achievable if the BST is balanced. If the tree is lopsided on the right side for example, each iteration does not exactly halve the number of nodes to search. The worst case scenario would be to comb through all the nodes if they are all existing on the right node of one another.

There are many self balancing trees, one of them is the AVL tree named after its inventors. It involves changing the root node when it becomes unbalanced to ensure that “the heights of the two child subtrees of any node differ by at most one“.

Duplicates are allowed in some BST, meaning the there can be 2 nodes with the same value. It should always be obey the rule that the left node is <= to the current node. Duplicates introduce complexity in the search algorithms to determine the correct node to pick.

Key Features

  • A node and its left and right nodes has to be sorted in a specific order that can be classified as ascending or descending
  • Needs to be balanced to be useful
  • Traversal is always from left node then right node, with the current node hoping between and around the left and right to define the 3 different methods of traversal, ie.
    • inorder
    • preorder
    • postorder

Runtime

  • Balanced
    • Access: O(log n)
    • Search: O(log n)
    • Insert: O(log n)
    • Deletion: O(log n)
  • Imbalanced (worst case scenario)
    • Access: O(n)
    • Search: O(n)
    • Insert: O(n)
    • Deletion: O(n)

Applications

  • Database like CouchDB
  • Huffman Coding Algorithm for file compression
  • Generally large data with sortable characteristic, and its size should be large enough to justify the use of BST over arrays

Ruby Alternative

There is no native implementation of BST in ruby. However, there are gems out there that implement it. RubyTree by evolve75 is my favorite as it allows for content payload to be added to each node.

BST is quite an old and establish concept. Hence, these gems might appear old and unmaintained.

Min/Max Heap​

This tree always populated from the left to right across each level. It is considered minimum or maximum depending on whether the smallest or largest value is at the root node respectively.

After insertion, the new node is “bubbled” up to the correct node by a series of swapping with its parent node until it reaches the root node, if it reaches the root node.

If root node is deleted, the last node replaces it and “bubbled” down to the correct position.

Because of the way it is data is populated, there will be no gaps in between nodes, hence this tree can be stored as an array (no need for linked list)! One can simply use the index of the node in the array to access itself, and some formula to get the index of its neighbouring nodes and access them as well:

  • parent: (index – 1) / 2 (rounded down)
  • left: 2 * index + 1
  • right: 2 * index + 2

Key Features

  • Essentially an array
  • Root node is always the minimum or maximum, the last node is always the opposite
  • Nodes in between does not necessarily obey  the order.
  • Root node is usually the one being removed in application, replaced by the last node, and bubbled to the correct position accordingly
  • Min heap always look to find the smallest value among its children to swap down, opposite for max heap

Runtime

  • Access: O(1) with use of known index of element in array
  • Search: O(n)
  • Insert
    • append/prepend: O(1)
    • ordered insert: O(log n)
  • Deletion: O(log n)

Applications

  • Priority queues (eg. for elderly and disabled then healthy adults using weighted representation)
  • Hospital queues for coronavirus victims based on age and, therefore, savableness
  • Schedulers (eg task with higher priority will have higher weightage and will be bubbled to the correct position when added to the queue)
  • Continuous median problem

Ruby Alternative

There is no native heap implementation in Ruby. Gems are available.

Hash Table

Interestingly, a hash table consist of a hashing function and an array of linked lists. Together, they form a key value datastore.

The key to map to the value to store undergoes a hashing function to get an integer. This integer will represent the index in the array in which to store the data, that is the value corresponding to the key in the hash table. It will be added to the linked list behind the index of that array.

The data is saved as a linked list instead of an element in the array due to the probability of collisions from the hashing function. This allows multiple values to be stored in the same index of the array, but only if their key is different. Otherwise, they will overwrite the old data, as hash tables do no allow duplicate keys.

It is crucial for the hashing function to have a good key distribution. This is to prevent any of the linked list from being overwhelmingly long, resulting in long search time hopping through the linked list. Murmur hash is a good hashing function for this purpose.

Key Features

  • Hash function maps keys to index of array
  • Array is made up of linked list to store data while avoiding collisions from the hashing
  • Hash function with good distribution crucial to performance
  • No order

Runtime

  • Access: O(1)
  • Search: O(1)
  • Insert: O(1)
  • Deletion: O(1)

Applications

  • Anything that does not require order

Ruby Alternative

Murmur hash seems to be used in the native ruby hash. Note that it is easily reversible. Hence while it can be used for maintaining good key distribution, it is not ideal for cryptographic purposes.

Linked List

Each node will point to the next node. The last node will point to null. Accessing elements can be slow as the pointer need to jump through nodes, unlike array which can access instantly via the index. The advantage of linked list over array is that you do not need to allocate the required memory at the start. You will only use the memory that you need without wastage. It is very space efficient.

Another advantage is its speed during prepending elements or inserting them in the middle. Unlike the array where every element thereafter has to be shifted, it can be done in constant time in a linked list.

A variation, the doubly linked list, gives bearing to adjacent node on both ends. It allows traversal in both direction as its biggest advantage. The maintenance needed to maintain that the 2nd neighbouring node in all operations may be costly.

Last variation is the circular linked list. That said, there;s a classic linked list question on how to detect if a linked list has a cycle (not necessarily circular). The solution is to use a fast pointer and a slow pointer to loop through the link list until they point to the same node in a linked list with a cycle, or null for a non circular linked list. This is simple cycle detection algorithm known as Floyd’s tortoise and hare, and is entertainingly portrait in the video below.

Side note for me: the distance of the loop, not coincidentally but mathematically, equals to the start of the linked list to the location where the hare and tortoise meet. Again, not coincidentally but mathematically, the distance from the start of the linked list to the start of the loop equals to the distance from location where the hare and tortoise met to the start of the loop (continuing in the direction that the tortoise was originally moving in).

Key Features

  • Head node may be null
  • Last node will point to null
  • Doubly linked list is another variation, where each node points to its previous and next node

Runtime

  • Access: O(n)
  • Search: O(n)
  • Insert
    • append/prepend: O(1)
    • ordered insert: O(n)
  • Deletion: O(n)

Applications

  • Anything that requires order and needs to save on memory

Ruby Alternative

There is not native linked list in ruby. However, there are gems and this by spectator is still pretty active.

Queue

Queue is a collection of data that obeys the First In First Out (FIFO) principle.

Theoretically, as traversal is not suppose to happen in a queue, I believe that it is best implemented with linked list rather than an array. There is no resizing overheads, and no need to shift all the elements every time an element is taken out of the front of the queue.

Addition to the queue might mean having to hop through the whole link list to add the element at the back. However, I would solve this by using a circular linked list to have a grip on the first and last element, which is actually all the queue would care about. Of course, things will be different if it is a not-so-simple queue like a least recently used (LRU) implementation.

However, there are certain advantages we should consider implementing with arrays. Arrays can be cached more easily as they are consist of memory units adjacent to one another. On the other hand, a linked list consist of memory units that exist sparsely in the memory pool which hurts its caching capabilities. The reason is a TODO for me when I go beyond data structures during this revision weeks.

Nonetheless, cache engines like Redis has their own implementation of a linked list (Redis List) in their cache database. I do not know if this is the same caching mechanism that is affected by the sparse memory locations of a linked list, but it is probably good to know. 

Key Features

  • FIFO

Runtime

  • Insert (prepend): O(1)
  • Deletion (shift): O(1)

Applications

  • Restaurant queues

Ruby Alternative

Arrays are usually used as queues in ruby. It, however, does have a native Queue class, which is meant for multi threaded operations. On top of that, it has a SizedQueue class to ensure the size is within capacity.

Stacks

Stack are like the brother of queues. The only difference is they obey the Last In First Out (LIFO) principle.

Again as traversals are not supposed to happen, we can use linked list for the same advantages and considerations as explained in the “Queue” section above. And instead of appending to the end of the linked list, we will prepend to the linked list instead, where the head of the linked list represents the top of the stack. It will be constantly changing and where all the action will take place.

This ensures there is no overhead from resizing from using the array when the data gets too big, but it will need to take the need and performance in caching into consideration.

Arrays will be more suited to implement a stack than a queue. This is because all the push and pop will take place at the end of the array, unlike the queue which need to remove element from the front of the array and cause shifting of all elements forward.

Two stacks can be used to implement a queue with minimal performance overhead as well, as shown in the video below.

Key Features

  • LIFO

Runtime

  • Insert (push): O(1)
  • Deletion (pop): O(1)

Applications

  • Matching balanced parenthesis problems
  • Anagram / palindrome problems
  • Backtracking in maze
  • Reversals

Ruby Alternative

No native stack in Ruby. A simple array will suffice. Linked list gems are available too.

Graph

A graph is a superset of linked list. Unlike a linked list where it needs to be associated to a next element, and its previous element for a doubly linked list, a graph can have links to multiple nodes, not just to the adjacent ones.

The link between each node of a graph contains data to give more meaning to the relationship between nodes. In graph terminology, this link is called an “edge” (as a matter of fact, “nodes” are termed “vertices“). An edge can be directed or undirected. Think being friends (undirected) versus being a follower (directed) between users in a social network.

2 common ways to search a graph is the Depth First Search (DFS) and Breadth First Search (BFS). DFS has a weakness where it will search the full depth from one edge before moving on to the next. This translates to inefficiency if the vertex that we are searching for is on the other edge. Hence BFS is preferred.

Typically in BFS, a queue is used to store the next vertices to search.

There can be cycles of vertices having an edge to one another, hence during the search, it is imperative to check if a vertex has been visited or not to prevent going round in circles during the search. Unless we are talking about a Directed Acyclic Graph (DAG) where there are no directed cycles.

Key Features

  • Nodes are termed vertices
  • Edges contain data to describe the relation between vertices
  • BFS preferred
  • Flag to check if visited the vertex before in a search algorithm to prevent looping inside a cyclic relationship among vertices.

Runtime

Time complexity of a graph depends on how the edges and vertices are stored. The optimal choice of storage depends on any prior knowledge of how the graph might look like.

Applications

Ruby Alternative

There is no native graph data type in ruby. Gems are available.

Set

The data structure of a set is the same as that of a hash table. The difference is that set is not really concerned with the mapped value of a key. It just tracks whether the key is present.

This implies that there can be no duplicates in the keys just like a hash table. And unlike a hash table where a key can be mapped to a null value, the key will be removed if nullifed for the case of a set.

Key Features

  • No order
  • No duplicates

Runtime

  • Access: O(1)
  • Search: O(1)
  • Insert: O(1)
  • Deletion: O(1)

Applications

  • Attendance

Ruby Alternative

Ruby has a native data type for a set.

Rails select helper with default selected option disabled and prompt

This is a documentation once and for all on how to render a select tag in rails view with a disabled option that is preselected.

Motivation

I find myself having to refer to stackoverflow often for the solution because it just isn’t intuitive. It requires some sort hacking before it can be rendered the way I needed it. Often, I would not understand the purpose of writing the code that way unless I can remember the purpose and  see the end goal of what it is trying to achieve.

Code that is not self-explanatory is a sign of code smell. That is so not Rails.

The Old Way Of Coding

<= tweet_form.select :user_id,
	options_for_select(
		@users.map { |user| [user.name, user.id] },
      selected: tweet_form.object.user_id || 'Please select user',
      disabled: 'Please select user'
    ),
	{},
	{ class: 'form-control' }
%>

The way I used to code out the list of options is to create an array that contains yet another array as shown above. In the inner array, the first value will be the label that users will see when selecting the option from the list, while the second value is the actual value to be passed to the backend.

Here is the part that raises question. In line 3, I prepend the array of users using the + operator with an array containing Please select user. This is meant to be the first value to be selected so that it can act as a prompt for the select tag.

I use the options_for_select helper to make it a little easier to set the with the selected and disabled options. The selected key will select the prepended array’s value as the default value for the select tag, and the disabled key will set it as disabled so that users cannot choose it and send an invalid value to the backend.

Hence, without knowing the end goal, the code from line 3 to 5 will raise eyebrows. There has to be a better way and indeed there is. But first, let me touch on the remaining lines for completion sake.

Line 7 is for other options for the Rails select helper, like include_blank which we are not using.

Line 8 is for additional HTML attributes.

The New Way Of Coding

Rails 6 has added the prompt helper in the Rails select tag to achieve exactly this purpose. Let’s compare the new way of writing that snippet.

<= tweet_form.select :user_id,
	@users.map { |user| [user.name, user.id] },
	{
      selected: tweet_form.object.user_id || "",
      disabled: "",
      prompt: 'Please select user'
    },
	{ class: 'form-control' }
%>

We are no longer using the options_for_select helper as we do not need its selected and disabled options for any more unsettling hackery.

In its place, we use the prompt key in the line 6 under the options argument for the Rails select helper to give achieve the same result.

The disabled key here makes the prompt an unselectable option. Leave it out if your UX allow selection of nil value. You may need to engage the include_blank key here as well.

The selected key sets the selected value conditionally to be the prompt’s unless the form object already has a user_id value. This part is a little quirky; the concept of selecting the value of the form object should already be implemented by default without having to write out the conditional code as in line 4. I believe this is constructed to fit all scenarios for all UX requirements, but I can’t really be sure. I’ll check it out someday.

Note that by using prompt, the prompt will not be present as one of the options if the form object already has a value.

Conclusion

This is a lot neater and much more like the Rails we know. There is no more questionable code and every line and option has a clear purpose.