Creating queues with ES6

In my last post I discussed creating a binary search tree with ES6. In this post I’ll be discussing a different type of data structure: queues. Once again I’ll be leaning on Data Structures and Algorithms With JavaScript by Michael McMillan for insight.

What is a queue?

A queue is a linear data structure that stores items in the order in which they are generated. A queue is rather like a list where items are added to the end and removed from the beginning. This type of data structure is known as a “first-in, first-out” data structure. It may help to think of a queue as a line at a grocery store where customers join at the back and check out at the front.

Creating a queue

Creating a queue requires a single class. The class should have one property for storing the data along with several standard methods for working with the data, e.g., adding items to the queue, removing items from the queue and querying the queue. Exact property and method names may vary but such a class may be designed as follows:

// A basic queue
class Queue {
  // Creates the data store
  constructor(dataStore = []) {
    this.dataStore = dataStore;
  }
  // Adds an element to the back of the queue
  push(element) {
    this.dataStore.push(element);
  }
  // Removes an element from the front of the queue
  shift() {
    this.dataStore.shift();
  }
  // Inspects the first element in the queue
  peekFront() {
    return this.dataStore[0];
  }
  // Inspects the last element in the queue
  peekBack() {
    return this.dataStore[this.dataStore.length - 1];
  }
  // Checks to see if the queue is empty
  isEmpty() {
    return !this.dataStore.length;
  }
  // Outputs the contents of the queue
  toString() {
    let str = '';
    for (var i = 0; i < this.dataStore.length; i++) {
      str += `${this.dataStore[i]}\n`;
    }
    return str;
  }
}

This simple class essentially proxies native array properties and methods in order to work with the data. For example the push() method that adds items to the queue proxies Array.prototype.push(); the shift() method that removes items from the queue proxies Array.prototype.shift(); and the isEmpty() method that checks to see if the queue is empty proxies Array.length. The class also has methods for inspecting the first and last elements in the queue (peekFront() and peekBack()), and outputting the contents of the queue (toString()).

Let’s now create a queue and add some items to it:

const queue = new Queue();
queue.push('George Washington');
queue.push('John Adams');
queue.push('Thomas Jefferson');
queue.push('James Madison');
queue.push('James Monroe');

Outputting the contents of the queue should return the following:

George Washington
John Adams
Thomas Jefferson
James Madison
James Monroe

Notice how each new item has been added to the back of the queue?

Let’s now remove an element from the queue using queue.shift(); and see how this affects the output:

John Adams
Thomas Jefferson
James Madison
James Monroe

Notice how the first item has been removed from front of the queue?

Let’s now inspect the first and last items in the queue:

queue.peekFront(); // John Adams
queue.peekBack(); // James Monroe

So far, so predictable.

Creating a double-ended queue

A more specific kind of queue is called a double-ended queue or “deque” (pronounced “deck”). In a deque items can be added to and removed from both the front and the back of the queue. Creating a deque requires us to extend our basic queue with a couple of extra methods: an unshift() method for adding items to the front of the queue and a pop() method for removing items from the back of the queue. Again these methods proxy the native array methods Array.prototype.unshift() and Array.prototype.pop().

class Deque extends Queue {
  ...
  // Adds an element to the front of the queue
  unshift(element) {
    this.dataStore.unshift(element);
  }
  // Removes an element from the back of the queue
  pop() {
    this.dataStore.pop();
  }
  ...
}

Let’s now create a deque and add some items to it:

const deque = new Deque();
deque.unshift('George Washington');
deque.unshift('John Adams');
deque.unshift('Thomas Jefferson');
deque.unshift('James Madison');
deque.unshift('James Monroe');

Outputting the contents of the queue should return the following:

James Monroe
James Madison
Thomas Jefferson
John Adams
George Washington

Notice how adding the items to the front of the queue affects the order?

Let’s now remove an item from the queue with deque.pop(); and see how this affects the output:

James Monroe
James Madison
Thomas Jefferson
John Adams

Notice how the item has been removed from the back of the queue?

Let’s now inspect the first and last elements in the queue:

deque.peekFront(); // James Monroe
deque.peekBack(); // John Adams

Straightforward enough!

Creating a priority queue

Another more specific kind of queue is called a priority queue. In a priority queue items are removed based on a manually defined “priority” as opposed to an automatically defined position (first or last).

As an example let’s take the line of succession to the U.S. presidency, in which the successor to the office is based on a set order of priority. A simple data model for a successor could look like this:

office: String // office to which successor belongs
priority: Number // order of priority

Creating a line of succession class once again requires us to extend our basic queue with a few methods: a special implementation of the shift() method for removing items from the queue, a special implementation of the toString() method for outputting the contents of the queue, and a count() method for returning the number of items in the queue.

class LineOfSuccession extends Queue {
  // Removes an element from the queue based on priority 
  shift() {
    let order = 0;
    for (var i = 1; i < this.count(); ++i) {
      if (this.dataStore[i].order < this.dataStore[order].order) {
        order = i;
      }
    }
    return this.dataStore.splice(order, 1);
  }
  // Outputs the contents of the queue
  toString() {
    let retStr = ``;
    for (var i = 0; i < this.dataStore.length; i++) {
      retStr += `${this.dataStore[i].office}\n`;
    }
    console.log(retStr);
  }
}

The shift() method works by returning the item with the highest priority from the queue. It does this by looping through all the items in the queue and upon encountering a higher priority item than the current highest priority item making the former the new highest priority item.

Let’s now create a line of succession:

const los = new LineOfSuccession([
  {office: 'Speaker of the House of Representatives', order: 2},
  {office: 'Vice President', order: 1},
  {office: 'Secretary of the Treasury', order: 5},
  {office: 'Secretary of State', order: 4},
  {office: 'President pro tempore of the Senate', order: 3}
]);

Notice how this time we’re passing the data into the queue’s constructor rather than adding the items manually with queue.push()? Also notice how the data is in no particular order as it’s being passed in? Outputting the contents of the queue should return the following:

Speaker of the House of Representatives
Vice President
Secretary of the Treasury
Secretary of State
President pro tempore of the Senate

Now let’s create a successor variable and start pulling (removing) successors from the queue.

let successor;
successor = los.shift();
successor[0].office // Vice President;
successor = los.shift();
successor[0].office // Speaker of the House of Representatives;
successor = los.shift();
successor[0].office // President pro tempore of the Senate;
successor = los.shift();
successor[0].office // Secretary of State;
successor = los.shift();
successor[0].office // Secretary of the Treasury;

Notice how each successor is being removed from the queue based on priority?

Conclusion

In this post I’ve described the basic idea of the queue data structure and, to see how it works in practice, used ES6 to implement a few different kinds of queue: a basic queue, a double-ended queue and a priority queue. The main differences between these kinds of queue can be summarized as follows:

  • In a basic queue items are added to the back and removed from the front.
  • In a doubled-ended queue items can be added to and removed from both the front and the back.
  • In a priority queue items are removed based on a manually defined priority.

Creating a binary search tree with ES6

I recently started reading Data Structures and Algorithms With JavaScript by Michael McMillan. Not having an academic background in computer science I’ve tended to shy away from this subject. With front-end development becoming an ever more complex endeavor, however, I felt it was about time to dive in and see what I’ve been missing. This and somebody recently asked me a question about binary search trees, about which I was utterly clueless. Guilt can be a good motivator, I guess.

What are trees?

McMillan defines a tree as a “nonlinear data structure that is used to store data in a hierarchical manner.” In this context a nonlinear data structure can be defined as a data structure in which data is arranged randomly, while a hierarchical data structure can be defined as a data structure in which data is organized into levels. A specific terminology is used when discussing trees. Some terms I’ll be using in this post include:

  • Root
  • Child
  • Parent
  • Leaf
  • Edge
  • Path
  • Level
  • Depth
  • Key value

Binary trees and binary search trees are special kinds of tree. In a binary tree, a node can have no more than two child nodes; in a binary search tree (BST), lesser values are stored in left nodes and greater values are stored in right nodes. The following diagram depicts a binary search tree.

A binary search tree with three levels. The root has a key value of 4 and has children with key values of 2 and 6. Both these nodes also have children of their own: The node with a key value of 2 is parent to nodes with key values of 1 and 3; the node with a key value of 6 is parent to nodes with key values of 5 and 7. All nodes on level 2 are leaves.

In this post I’ll be creating this BST using ES6 and adding some methods to it for adding and retrieving data. The code for my creation is available on CodePen.

Creating the BST

Creating the empty BST turns out to be relatively straightforward. All that’s needed is a class to represent a node and a class to represent the BST. A node holds references to the data it’s supposed to store as well as to its children (left and right nodes). The BST holds a reference to the root, which starts out as null. The basic classes end up looking like this:

class Node {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

class BST {
  constructor() {
    this.root = null;
  }
}

Notice how the values of a node’s children are initialized using ES6 default parameters. Creating the BST is a simple matter of instantiating the BST class: const bst = new BST();.

Adding nodes to the BST

So far so good but an empty tree isn’t much use to anyone. In order to add nodes to the tree we’re going to need a method for doing so. Following is the insert() method McMillan defines, translated to ES6 from his ES5:

class BST {
  ...
  insert(data) {
    const node = new Node(data);
    if (this.root === null) {
      this.root = node;
    } else {
      let current = this.root;
      let parent;
      while(true) {
        parent = current;
        if (data < current.data) {
          current = current.left;
          if (current === null) {
            parent.left = node;
            break;
          }
        } else {
          current = current.right;
          if (current === null) {
            parent.right = node;
            break;
          }
        }
      }
    }
  }
}

The insert() method works by creating a new node and passing any data it was passed into the new node’s constructor. The method then does one of two things:

  1. If the BST doesn’t have a root, it makes the new node the root.
  2. If the BST does have a root, it traces a path through the BST until it finds an insertion point for the new node. Essentially this involves determining whether the new node should be inserted as the left or right child of a given parent. This is based on whether the new node’s value is lesser or greater than the parent’s value.

So let’s go ahead and insert some nodes and see how this works in practice.

bst.insert(4);
bst.insert(2);
bst.insert(6);
bst.insert(1);
bst.insert(3);
bst.insert(5);
bst.insert(7);

Following is a table that illustrates the inner workings of the insert() method for each of the values we’re inserting. (A key to the column headings follows the table.)

1234567
4nulln/an/an/an/ainsert
244trueleftnullinsert
644falserightnullinsert
144trueleft2iterate
n/a42trueleftnullinsert
344trueleft2iterate
n/a42falserightnullinsert
544falseright6iterate
n/a46trueleftnullinsert
744falseright6iterate
n/a46falserightnullinsert
  1. New node value
  2. Root node value
  3. Current node value
  4. New node value < current node value?
  5. New node should be inserted to left or right?
  6. Value of node at insertion point
  7. Result

Retrieving the minimum and maximum values from the BST

Two important implications of the insert() method are that:

  • The minimum value in the BST is always the leftmost value in the BST.
  • The maximum value in the BST is always the rightmost value in the BST.

Given these rules, defining methods to retrieve these values becomes fairly trivial.

Retrieving the minimum value

Let’s define a getMin() method for retrieving the minimum value from the BST:

class BST {
  ...
  getMin() {
    let current = this.root;
    while(current.left !== null) {
      current = current.left;
    }
    return current;
  }
}

The method can be called with a simple bst.getMin();. The following table illustrates the method’s inner workings:

Current nodeLeft nodeResult
42iterate
21iterate
1nullreturn

Retrieving the maximum value

Let’s now define a getMax() method for retrieving the maximum value from the BST:

class BST {
  ...
  getMax() {
    let current = this.root;
    while(current.right !== null) {
      current = current.right;
    }
    return current;
  }
}

This method can be called with a simple bst.getMax();. The following table illustrates the method’s inner workings:

Current nodeRight nodeResult
46iterate
67iterate
7nullreturn

Finding a specific node in the BST

Finding a specific node in the BST is a matter of tracing a path through the BST until either a value is found that matches the requested value or a value of null is found, in which case it can be safely said that the BST does not contain the requested value. Following is the find() method McMillan defines, once again translated to ES6 from his ES5:

class BST {
  ...
  find(data) {
    let current = this.root;
    while (current.data !== data) {
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right;
      }
      if (current === null) {
        return null;
      }
    }
    return current;
  }
}

Let’s try to find the node with a value of 3 by calling the method with bst.find(3);. Following is a table that illustrates the method’s inner workings. (A key to the column headings follows the table.)

123456
4falsetrueleft2iterate
2falsefalseright3iterate
3truen/an/an/areturn
  1. Current node value
  2. Is the current node value equal to the requested node value equal?
  3. Is the requested node value less than the current node value?
  4. Is the new current node to the left or right of the existing current node?
  5. New current node value
  6. Result

Conclusion

In this post we learned to differentiate between trees, binary trees and binary search trees (BSTs). We also created a BST using ES6 and added some methods to it for adding and retrieving data. Unfortunately we didn’t have time to cover some more advanced BST topics such as tree traversal and removing nodes–maybe this can be the subject of a future post.

Organizing Passwords, PII and Email

As I prepare to start a new job on Monday, the first new job I’ll have started for more than seven years (God, please don’t let me get beaten up behind the bike sheds on my first day!), I’ve been making an effort to organize the detritus of my online life.

Loyal readers of this blog—if indeed such emotionally troubled individuals are currently blessed with reading privileges in the various jailhouses and detention centers they occupy—will recall my inaugural post about a password manager application I’ve been using called 1Password, made by a Canadian software company called AgileBits. As the name “1Password” suggests, the (IMO truly magnificent) app allows you to create one strong, memorable password that gives you access to a database into which you can enter all your other Web site log-in credentials, the passwords for which can be as strong and unmemorable as you wish. As if this functionality were not useful enough, the app also gives you the ability to log in to your favorite Web sites automatically, which in effect frees you from the very 21st-century hassle of entering slight variants of the same credentials into Web-based log-in forms time after tedious time.

In more recent days I’ve also been exploring some of 1Password’s additional capabilities, such as the way it allows you to store personal information (e.g., bank account, credit card and driver’s license information), in what the app calls “Wallet items.” Given my increasing reliance on the Web for performing financial and commercial transactions, having this information stored centrally in such a fashion has been proving pretty useful. Now, for instance, I don’t have to search my coat pockets for my actual wallet whenever I need my credit card for Turnov’s Small and Short men’s shop, a card whose number, expiry date and security code have escaped—or indeed have never been stored in—my memory. This liberating upshot is all the more satisfying given the numerous types of coat I’ve had to wear this winter here in the environs of Alexandria, Va., where the weather has been changing as much as a chameleon with multiple personality disorder in a dressing room.

To turn to, or at least look askance at, the subject of email organization, I’ve also been striving to exert a measure of control over my hitherto untamed Gmail inbox. This effort has necessitated creating a large number of labels and a not small number of filters. I now have as many as 17 top-level labels for my received mail, each of which has sub-labels that allow for more specific content characterization. Without wishing to give you too much insight into my personal life, here are the top-level labels I’ve settled on to-date:

  • Banking
  • Car (“Pollution-Spewing Heap of Rust” would be more accurate)
  • Credit Cards
  • Entertainment
  • Health & Fitness (just the one email under this label so far)
  • Home
  • Insurance
  • Investments
  • Local Government
  • Meetups (nice to get out of Chez Smith from time to time)
  • Personal
  • Personal Finance
  • Shopping
  • Taxes (would “Death and Taxes” last longer?)
  • Travel & Transit
  • Web Services
  • Work

Readers who take their mobility for granted might argue that going to such organizational lengths as these evinces a certain anal-retentiveness in me. And while I wouldn’t render them entirely unable to walk for arguing this way, I would suggest that if the feeling one gets from having an organized inbox is preferable to the feeling one gets from having a disorganized inbox, then the better feeling alone justifies the effort one has made in organizing it. So there, with highly polished brass knobs on!

In conclusion, I think “personal information architecture” projects like these will increase in importance as our weird, wired world becomes more data-centric and IT-reliant. Instead of finishing with a supposition, however, I’ll finish with a question: Do you—my loyal, incarcerated readers—attempt to organize your inboxes? Or do you allow them to grow untamed, like the tangled hair of an aging hippie?

1Password: The Summit of Password Managers?

If I were to suggest to you that global warming, population growth and password management were among the 21st century’s greatest problems, you would of course be perfectly justified in observing that only two of these topics deserve such weighty description: As we all know, the dangers to mankind of global warming are vastly overstated and in fact may be apocryphal.

Before any partisan bickering that my previous assertion might have provoked descends into outright violence, allow me to raise my voice above the din for a moment to plead, “I was only joking!” Compared to the mountainous environmental and demographic issues already identified, the personal tech problem of managing one’s Web site login credentials seems molehill-like indeed. Modest though its heights may be, however, they still must be scaled. It pleases me to report that with the aid of a trusty Sherpa I have in recent days been able to scale them!

Playing Tenzing Norgay to my Edmund Hillary is 1Password, a desktop password-management application from the privately held Canadian company AgileBits. According to the manufacturer’s Web site, versions for Mac, Windows, iPhone, iPad and Android are available. This discussion concerns 1Password 3 for Mac, which requires OS X Snow Leopard and higher. (Tiger and Leopard users, the manufacturer mollifies, can use 1Password 2 and sync their data with Snow Leopard or Lion.) A single-user license cost me $49.99 from the manufacturer’s Web site.

The central idea of 1Password is straightforward:

  1. You create a single, master password to the app.
  2. You enter your login credentials for any given Web site into the app’s database.
  3. The app, upon entry of the correct master password, gives you access to all the credentials you’ve entered.

The upshot is that you only have to remember one password (hence the name, duh!) in order to have access to your login credentials for any given site. This comes in especially handy if, like me, you have accumulated several variations of usernames and passwords since Web time (Berners-Lee time?) began. I, for instance, have amassed as many as 20 unique usernames!

Having only one password to remember also enables you to practice good Web security and create a strong, unique password for each of your stored sites. 1Password conveniently includes a random-password generator for the purpose. The generator features several password-customization options, including the number of characters the password should contain, the number of digits or special characters it should contain, whether it can contain the same character more than once, and even whether it should be pronounceable!

1Password also includes a delightfully time-saving auto-login feature, which alone justifies the app’s license fee IMHO. Double-click the name of any given Web site from within the app to be instantly directed to and logged into that site. For even quicker, one-click access, install the app’s Web browser extension, in which you can also perform other common tasks, such as data entry.

What happens if a Web site requires you to enter your username on one screen and your password on another? Simply create two records in the database: one for the username screen and one for the password screen, taking care to name each record meaningfully. Then simply choose the relevant record from the app or browser extension.

Do you use a Mac at home and a PC at work? Combine 1Password with the built-in 1PasswordAnywhere and the file-hosting service Dropbox for access to your login credentials from wherever you happen to be doing your Web browsing. In addition to login credentials, 1Password also promises the ability to store other types of sensitive information, such as software licenses, free-form text, and personal and financial information. I’m looking forward to trying these features out in the coming days.

In the meantime you can color me impressed. Although there may be freely available alternatives that perform just as well, I feel as though my money has been well-spent on 1Password. A piece of software that saves me time and makes me feel a bit more organized seems to me invaluable in this time-crunched era of ours. If these do not strike you as reasons enough to reach for the summit of your own password management mountain (or molehill), then why not turn to the sentiments of another celebrated Everest assaulter: Do it because it’s there!