Forem: Georgi Serev

Virtual scrolling of content with variable height with Angular

Georgi Serev — Mon, 08 May 2023 18:41:23 +0000

It has taken you precious time to develop your carefully crafted list of items with variable height with Angular. Now, your only remaining task is to add virtual scroll support. You install and integrate @angular/cdk/scrolling, but then you reach a dead end – Angular CDK virtual scroll can only handle items with fixed size. After some searching, you've came across this article. Hopefully, by the end of it, you should have a flawlessly-working list that supports virtual scrolling.

Harnessing @angular/cdk

Obviously, we are not going to reinvent the wheel by implementing our own virtual scroll. Surely, that's an option, but we would like to use the existing tools that have proven to work and Angular CDK actually offers a very capable instruments for that. What we are going to do is to implement a custom VirtualScrollStrategy. But before we start ...

@angular/cdk-experimental

It's worth mentioning that the CDK team is currently developing an autosize strategy which is part of the experimental version of the Angular CDK. You might achieve very good results with it but be aware that the strategy is not ready for production yet (official documentation) as of the time of writing this article. So, you might potentially experience unexpected behavior. In short, you could give it a try, in case it achieves the results you desire. Anyhow, without further ado, let's move our focus to the custom strategy.

Chapters

Since I thought that it makes logical sense, I separated the article in several chapters. If I have to summarize, we are going to:

Present our problem
Explain what a VirtualScrollStrategy is and how to harness it
Employ the strategy
Focus on the implementation of the internals

We'll try to skim throught some of these matters as quickly as possible, as granularity might not be important, but having a grasp of them would be essential for you to understand how things stitch together in the final product. The actual strategy implementation is going to be examined in the final chapter as the list suggests.

⚠️ NOTE: By just having a quick glance at the chapters and blindly copying the code examples, you might end up with a non-functional solution. If you are short on time and don't plan reading the text, you can head to the Final code section and explore the repository directly (the code is documented).

For the sake of convenience, here is a handy content:

I. Case study – Hero Feed
II. VirtualScrollStrategy – What is that?
III. Setting up the custom strategy
- Data source
- Infinite scrolling
IV. Strategy implementation
- Determining the height of the messages (list items)
- Incorporating height prediction
- Complementary methods
- Improving height measurement
- Final code
Conclusion

I. Case study – Hero Feed

It is very likely that, if you develop Angular apps, you have came across the Hero tutorials in the official documentation. So, in order to be inline with that, I am going to build a Hero feed. In essence, it's just a hypothetical feed with randomly generated data that is trying to mimic a real-world example.

For that purpose, let's introduce the HeroMessage interface. The message will represent our list item:

export interface HeroMessage {
  id: string;
  name: string;
  date: Date;
  text: string;
  tags: string[];
}

... and this is how it will look in the app:

Respectively, I am going to create a component that renders that data which I'll name HeroMessageComponent. For the sake of saving time, I am going to omit the details as they are not very relevant to our main goal.

💾: You can check the full component code at GitHub

Now, let's move on to the strategy interface.

II. `VirtualScrollStrategy` – What is that?

VirtualScrollStrategy represents an interface that we should implement in order to describe our desired scrolling behavior, or more specifically, define which items should be rendered in the viewport. Actually, if you've noticed, the standard cdk-virtual-scroll-viewport component, as already mentioned, works with fixed-size items, the experimental CDK – variable-size items. These two modes are separate VirtualScrollStrategy-ies – FixedSize and Autosize, respectively. Let's take a look at the methods:

interface VirtualScrollStrategy {
  /** Emits when the index of the first element visible in the viewport changes. */
  scrolledIndexChange: Observable<number>;

  /**
   * Attaches this scroll strategy to a viewport.
   * @param viewport The viewport to attach this strategy to.
   */
  attach(viewport: CdkVirtualScrollViewport): void;

  /** Detaches this scroll strategy from the currently attached viewport. */
  detach(): void;

  /** Called when the viewport is scrolled (debounced using requestAnimationFrame). */
  onContentScrolled(): void;

  /** Called when the length of the data changes. */
  onDataLengthChanged(): void;

  /** Called when the range of items rendered in the DOM has changed. */
  onContentRendered(): void;

  /** Called when the offset of the rendered items changed. */
  onRenderedOffsetChanged(): void;

  /**
   * Scroll to the offset for the given index.
   * @param index The index of the element to scroll to.
   * @param behavior The ScrollBehavior to use when scrolling.
   */
  scrollToIndex(index: number, behavior: ScrollBehavior): void;
}

Generally, we won't have to implement all of them, unless you want any of the omitted behavior. I'll hold off the details for now. First, let's implement the interface and name our custom strategy "HeroMessageVirtualScrollStrategy":

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  // [...]
}

In order to provide our custom strategy to the viewport component, we should use the VIRTUAL_SCROLL_STRATEGY injection token. We can achieve this by introducing a new directive:

@Directive({
  selector: '[appHeroMessageVirtualScroll]',
  providers: [
    {
      provide: VIRTUAL_SCROLL_STRATEGY,
      /* We will use `useFactory` and `deps` approach for providing the instance  */
      useFactory: (d: HeroMessageVirtualScrollDirective) => d._scrollStrategy,
      deps: [forwardRef(() => HeroMessageVirtualScrollDirective)],
    },
  ],
})
export class HeroMessageVirtualScrollDirective {
  /* Create an instance of the custom scroll strategy that we are going to provide  */
  _scrollStrategy = new HeroMessageVirtualScrollStrategy();
}

After we are done, we would like to add some additional flavor – provide the list of messages, as an @Input, that we are going to use later in the scroll strategy. You will notice that the scroll strategy has one additional method called updateMessages. It will be added later by us but bare with me for now.

export class HeroMessageVirtualScrollDirective {
  // [...]

  private _messages: HeroMessage[] = [];

  @Input()
  set messages(value: HeroMessage[] | null) {
    if (value && this._messages.length !== value.length) {
      this._scrollStrategy.updateMessages(value);
      this._messages = value;
    }
  }
}

What we've just done is to add a _messages property that is going to be updated and respectively sent to the scroll strategy when it changes*

* A change can be very subjective. The current check is very primitive but it can be altered depending on the use case.

💾: You can check the final file at GitHub

Summary

To summarize what we've done so far:

Got familiar with the VirtualScrollStrategy interface
Created our own strategy (although it's not implemented yet)
Built a directive that will be used along with the virtual scroll component in order to plug our strategy, which bring us to the next chapter

III. Setting up the custom strategy

Since we now have the custom strategy, or at least the wireframe, let's plug it into the cdk-virtual-scroll-viewport in the template of our desired host component. In my case, I am going to use app.component.html.

  <cdk-virtual-scroll-viewport
    appHeroMessageVirtualScroll
    [messages]="heroMsgs.messages$ | async"
  >
    <!-- We'll use the HeroMessageComponent in order to render our list items -->
    <app-hero-message
      *cdkVirtualFor="let msg of heroMsgs.messages$ | async"
      [message]="msg"
      [attr.data-hm-id]="msg.id"
    ></app-hero-message>
  </cdk-virtual-scroll-viewport>

Data source

Because the generation of data is not a point of interest for this article, you can check the mocked API service that performs this task at GitHub. I prefer not to clutter the article with unnecessary source code. The mocked data is provided to the app.component.ts via the service and respectively the template.

💾: Check the app component at GitHub

💾: Check the mocked API at GitHub

Infinite scrolling

Finally, since we want to be as close as possible to a real-world app, the mocked data is going to be continuously loaded while the user scrolls down the list. For this purpose, we will need to introduce infinite scrolling.

💾: You can check the final file at GitHub.

Summary

In this chapter we managed to:

Plug the custom strategy to CdkVirtualScrollViewport
Briefly showcase our data generation
Add some infinite scrolling for the sake of real-world-ness

IV. Strategy implementation

We reached the point where we can start the implementation of the strategy. Logically, let's start with the attach and detach methods:

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  private _viewport!: CdkVirtualScrollViewport | null;

  attach(viewport: CdkVirtualScrollViewport): void {
    this._viewport = viewport;
  }

  detach(): void {
    this._viewport = null;
  }
}

As a next step, let's add the updateMessages custom method that will serve the HeroMessage-s to the strategy class:

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  private _messages: HeroMessage[] = [];

  // [...]

  updateMessages(messages: HeroMessage[]) {
    this._messages = messages;

    if (this._viewport) {
      this._viewport.checkViewportSize();
    }
  }
}

Now, it is time to introduce our main method which will dictate the rest of the implementation. The _updateRenderedRange must contain our core logic for determining the range of hero messages that should be rendered in the viewport. In short, we should be able to tell few things in order to implement it:

Measure the total height of the scrollable container
Determine the scroll position (or offset)
Determine the number of list items

As you can see, there is one key take here – we have to be able to distinguish and measure the size of the different list items. Of course, this task might become very tricky. This is why, we will go with a rough estimation. How will this happen? Let's examine the UI of the HeroMessage.

Determining the height of the messages (list items)

As you can see, the UI is not that complex – we have a hero, a date, some text, labels. The message has a minimal height determined by the existing elements (i.e. a hero message with a single line of text). Nevertheless, the height is unconstrained when it comes to growth (unless we introduce max. size for the text but this is not what we want in this article). Since we've already mentioned that we need a rough estimation, not a precise one, we can examine the styled component and its child elements and write down their rough sizes. Without further ado, let's introduce our height predictor.

// hero-message-height-predictor.ts

const Padding = 24 * 2;
const NameHeight = 21;
const DateHeight = 14;
const MessageMarginTop = 14;
const MessageRowHeight = 24;
const MessageRowCharCount = 35;
const TagsMarginTop = 16;
const TagsRowHeight = 36;
const TagsPerRow = 3;

export const heroMessageHeightPredictor = (m: HeroMessage) => {
  const textHeight =
    Math.ceil(m.text.length / MessageRowCharCount) * MessageRowHeight;

  const tagsHeight = m.tags.length
    ? TagsMarginTop + Math.ceil(m.tags.length / TagsPerRow) * TagsRowHeight
    : 0;

  return (
    Padding +
    NameHeight +
    DateHeight +
    MessageMarginTop +
    textHeight +
    tagsHeight
  );
};

As you can see, it is a fairly simple function which estimates/predicts the height of a HeroMessage based on its data. The text and tags height estimation is pretty much a ballpark figure based on an approximate row length. However, this is more than enough for our needs at this stage. I guess it's needless to mention, and obvious, that for your own particular case you will have to develop a similar function that matches your own UI. Now, let's go back to the strategy implementation.

💾: You can check the file at GitHub.

Incorporating height prediction

Due to the need of a height estimation, we can directly start with a new private method which uses the predictor:

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  private _heightCache = new Map<string, number>();

  // [...]

  private _getMsgHeight(m: HeroMessage): number {
    let height = 0;
    const cachedHeight = this._heightCache.get(m.id);

    if (!cachedHeight) {
      height = heroMessageHeightPredictor(m);
      this._heightCache.set(m.id, height);
    } else {
      height = cachedHeight;
    }

    return height;
  }
}

You can notice that we've also added a cache property. Basically, our method will be memoized so we can avoid recalculations. We might have a lot of them when the user scrolls.

Next, let's introduce several other methods that are going to be based on/use this particular one. As mentioned above, for the _updateRenderedRange we will have to know things like total scroll height, message offset, etc. We will start with calculating the height of a set of messages, which is a fairly simple operation:

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  // [...]

  private _measureMessagesHeight(messages: HeroMessage[]): number {
    return messages
      .map((m) => this._getMsgHeight(m))
      .reduce((a, c) => a + c, 0);
  }
}

After that we can introduce the following private methods:

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  // [...]

  /**
   * Returns the total height of the scrollable container
   * given the size of the elements.
   */
  private _getTotalHeight(): number {
    return this._measureMessagesHeight(this._messages);
  }

  /**
   * Returns the offset relative to the top of the container
   * by a provided message index.
   *
   * @param idx
   * @returns
   */
  private _getOffsetByMsgIdx(idx: number): number {
    return this._measureMessagesHeight(this._messages.slice(0, idx));
  }

  /**
   * Returns the message index by a provided offset.
   *
   * @param offset
   * @returns
   */
  private _getMsgIdxByOffset(offset: number): number {
    let accumOffset = 0;

    for (let i = 0; i < this._messages.length; i++) {
      const msg = this._messages[i];
      const msgHeight = this._getMsgHeight(msg);
      accumOffset += msgHeight;

      if (accumOffset >= offset) {
        return i;
      }
    }

    return 0;
  }
}

We are getting pretty close to the implementation of _updateRenderedRange. In the code section above, we've added a method for measuring the total height, getting the scroll offset of a message index, and the reverse method – getting a message index by a scroll offset.

What is next is a method that determines the number of messages in the viewport given a start index of a message:

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  // [...]

  private _determineMsgsCountInViewport(startIdx: number): number {
    if (!this._viewport) {
      return 0;
    }

    let totalSize = 0;
    // That is the height of the scrollable container (i.e. viewport)
    const viewportSize = this._viewport.getViewportSize();

    for (let i = startIdx; i < this._messages.length; i++) {
      const msg = this._messages[i];
      totalSize += this._getMsgHeight(msg);

      if (totalSize >= viewportSize) {
        return i - startIdx + 1;
      }
    }

    return 0;
  }
}

After this short sprint of method implementations we are finally ready to introduce our key method that we've been mentioning since the beginning of this chapter – _updateRenderedRange. Its purpose is to build a range object composed by a start and end indices which is then provided to the viewport object via its API. You will also notice the existence of two constants called PaddingAbove and PaddingBelow. What they do is to instruct the virtual scroll to render some more messages before and after the scroll viewport. This way, we will have some rendered content that is not visible but needed for a better scrolling experience (i.e. the items won't have to be rendered at the last moment):

const PaddingAbove = 5;
const PaddingBelow = 5;

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  _scrolledIndexChange$ = new Subject<number>();
  scrolledIndexChange: Observable<number> = this._scrolledIndexChange$.pipe(
    distinctUntilChanged(),
  );

  // [...]

  private _updateRenderedRange() {
    if (!this._viewport) {
      return;
    }

    const scrollOffset = this._viewport.measureScrollOffset();
    const scrollIdx = this._getMsgIdxByOffset(scrollOffset);
    const dataLength = this._viewport.getDataLength();
    const renderedRange = this._viewport.getRenderedRange();
    const range = {
      start: renderedRange.start,
      end: renderedRange.end,
    };

    range.start = Math.max(0, scrollIdx - PaddingAbove);
    range.end = Math.min(
      dataLength,
      scrollIdx + this._determineMsgsCountInViewport(scrollIdx) + PaddingBelow,
    );

    this._viewport.setRenderedRange(range);
    this._viewport.setRenderedContentOffset(
      this._getOffsetByMsgIdx(range.start),
    );
    this._scrolledIndexChange$.next(scrollIdx);
  }
}

So far, so good. You may remember the attach method that we implemented, right? We must update it now with the newly introduced _updateRenderedRange:

attach(viewport: CdkVirtualScrollViewport): void {
  this._viewport = viewport;

  // New code
  if (this._messages) {
    this._viewport.setTotalContentSize(this._getTotalHeight());
    this._updateRenderedRange();
  }
}

We can now also add and onDataLengthChanged to the strategy class which is very similar in terms of code:

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  // [...]

  onDataLengthChanged(): void {
    if (!this._viewport) {
      return;
    }

    this._viewport.setTotalContentSize(this._getTotalHeight());
    this._updateRenderedRange();
  }
}

And finally, we need to update the rendered range when the user scrolls. This is simply managed by onContentScrolled:

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  // [...]

  onContentScrolled(): void {
    if (this._viewport) {
      this._updateRenderedRange();
    }
  }
}

At this stage we should have the internals of our new strategy ready. As a next step, we can implement some of the other methods – that are not so crucial for the operation of the virtual scroll – which are part of the VirtualScrollStrategy interface.

Complementary methods

This section will be very short. We will focus on 3 methods from which only one will be implemented.

For our purposes, we won't benefit from onContentRendered and onRenderedOffsetChanged. We don't need to perform actions when the content is rendered or the offset has changed. So:

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  // [...]

  onContentRendered(): void {
    /** no-op */
  }

  onRenderedOffsetChanged(): void {
    /** no-op */
  }
}

On the other hand, having scrollToIndex functionality supported by the virtual scroll strategy might be desired, so we can quickly implement it with the existing private methods that we added earlier in the process:

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  // [...]

  scrollToIndex(index: number, behavior: ScrollBehavior): void {
    if (!this._viewport) {
      return;
    }

    const offset = this._getOffsetByMsgIdx(index);
    this._viewport.scrollToOffset(offset, behavior);
  }
}

With this final addition we can mark the implementation of the VirtualScrollStrategy completed. In essence, we should now have a functional virtual scroll that is very likely sufficient for our needs. Anyway, this doesn't mean that we can't do some improvements.

Improving height measurement

With its current design, our virtual scroll strategy relies heavily on the message height predictor that we introduced for measuring the approximate height of the list item. This is fine, and will probably work good enough in a lot of situations. Nevertheless, there is an inherent flaw in this design – since the approximated heights of the list items are almost the same as – if not the same as in some cases – the real heights but never the same in all situations, the more items the virtual scroll renders, the more imprecise the measurement of the total height will become due to these small deviations. While they are insignificant when observed individually, their accumulation results in a significant height difference.

Our goal, of course, is to make these measurements as precise as possible. This can only happen, if we take the height of the already rendered list items – at least this is the easiest way unless we want to dwelve into more concrete calculations – and, if you think more about it, we actually already have the list items rendered at some point of the virtual scroll usage. To summarize: what will do is to update the approximate heights (predicted) with the real heights (actual) of the list items when they get rendered.

Let's start by modifying our existing code. First, we'll update the type of the _heightCache map:

private _heightCache = new Map<string, MessageHeight>();

where the MessageHeight is defined by a new interface:

interface MessageHeight {
  value: number;
  source: 'predicted' | 'actual';
}

We will need to differentiate between a predicted height and an actual height; hence, the change.

Next, let's fix _getMsgHeight since the updated type will result in some errors.

private _getMsgHeight(m: HeroMessage): number {
  // [...]

  if (!cachedHeight) {
    height = heroMessageHeightPredictor(m);

    // Values from the height predictor will be marked as `predicted`
    this._heightCache.set(m.id, { value: height, source: 'predicted' });
  } else {
    height = cachedHeight.value;
  }

  // [...]
}

Now, since we need to get the actual heights from the DOM somehow, we will have to obtain a reference of the scroll wrapper. It makes sense to do that in the attach method of the strategy because that's the starting point of our code and that is where we set our viewport which can be used for that purpose.

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  private _wrapper!: ChildNode | null;

  // [...]

  attach(viewport: CdkVirtualScrollViewport): void {
    this._viewport = viewport;
    this._wrapper = viewport.getElementRef().nativeElement.childNodes[0];

    // [...]
  }
}

We are now getting even closer to the completion, but we need to add one additional private method to the strategy. We can name it _updateHeightCache:

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  // [...]

  private _updateHeightCache() {
    if (!this._wrapper || !this._viewport) {
      return;
    }

    // Get a reference of the child nodes/list items
    const nodes = this._wrapper.childNodes;
    let cacheUpdated: boolean = false;

    for (let i = 0; i < nodes.length; i++) {
      const node = nodes[i] as HTMLElement;

      // Check if the node is actually an app-hero-message component
      if (node && node.nodeName === 'APP-HERO-MESSAGE') {
        // Get the message ID
        const id = node.getAttribute('data-hm-id') as string;
        const cachedHeight = this._heightCache.get(id);

        // Update the height cache, if the existing height is predicted
        if (!cachedHeight || cachedHeight.source !== 'actual') {
          const height = node.clientHeight;

          this._heightCache.set(id, { value: height, source: 'actual' });
          cacheUpdated = true;
        }
      }
    }

    // Reset the total content size only if there has been a cache change
    if (cacheUpdated) {
      this._viewport.setTotalContentSize(this._getTotalHeight());
    }
  }
}

The method is a bit long but generally straightforward to grasp. You have probably noticed the existance of the data-hm-id attribute. Actually, this attribute has been part of our code since the beginning of chapter III but I intentionally decided to not point to its existance until now when you should hopefully realize its relevance and importance to our implementation. If not – it's there to help us easily distinguish the different messages in the DOM.

Finally, we will have to call that method somewhere. A good place is actually _updateRenderedRange, at the end after the rest of the statements.

export class HeroMessageVirtualScrollStrategy implements VirtualScrollStrategy {
  // [...]

  private _updateRenderedRange() {
    // [...]

    this._updateHeightCache();
  }
}

At this point, we can now conclude that our implementation is complete. 🎉

💾: Check the implemented custom strategy at GitHub

Final code

Throughout this article, I've given some links to the GitHub repository containing the example code which is based on this article. To make it even easier for you, here is the link of the whole repository:

hawkgs/hero-feed-virtual-scroll

Conclusion

The presented problem in this article can be abstracted for a lot of other use cases. The height predictor can be injected instead. All of that can result in a fairly generic implementation. I intentionally decided to not approach the problem that way. Anyhow, in reality, this implementation can be further improved or tailored for other needs; hence, it probably does not take into account more specific use cases.

What I really hope though is that by reading this piece of text you now have a good understanding how to implement your own VirtualScrollStrategy.

Transitioning from React class components to function components with hooks

Georgi Serev — Tue, 10 Mar 2020 23:53:50 +0000

It has been approximately one year since React v16.8 was released, marking the introduction of Hooks. Yet, there are still people used to React class components who still haven't experienced the full potential of this new feature, along with functional components, including myself. The aim of this article is to summarize and encompass the most distinguishable features of the class components, and respectively show their alternatives when using React hooks.

Functional components

Before we start with Hooks examples, we will shortly discuss functional components in case you aren't familiar. They provide an easy way to create new units without the need of creating a new class and extending React.Component.

Note: Keep in mind that functional components have been part of React since it's creation.

Here is a very simple example of a functional component:

const Element = () => (
  <div className="element">
    My Element
  </div>
);

And just like class components, we can access the properties. They are provided as the first argument of the function.

const Element = ({ text }) => (
  <div className="element">
    {text}
  </div>
);

However, these type of components--while very convenient for simple UI elements--used to be very limited in terms of life cycle control, and usage of state. This is the main reason they had been neglected until React v16.8.

Component state

Let's take a look at the familiar way of how we add state to our object-oriented components. The example will represent a component which renders a space scene with stars; they have the same color. We are going to use few utility functions for both functional and class components.

createStars(width: number): Star[] - Creates an array with the star objects that are ready for rendering. The number of stars depends on the window width.
renderStars(stars: Star[], color: string): JSX.Element - Builds and returns the actual stars markup.
logColorChange(color: string) - Logs when the color of the space has been changed.

and some less important like calculateDistancesAmongStars(stars: Star[]): Object.

We won't implement these. Consider them as black boxes. The names should be sufficient enough to understand their purpose.

Note: You may find a lot of demonstrated things unnecesary. The main reason I included this is to showcase the hooks in a single component.

And the example:

Class components

class Space extends React.Component {
  constructor(props) {
    super(props);

    this.state = {
      stars: createStars(window.innerWidth)
    };
  }

  render() {
    return (
      <div className="space">
        {renderStars(this.state.stars, this.props.color)}
      </div>
    );
  }
}

Functional components

The same can be achieved with the help of the first React Hook that we are going to introduce--useState. The usage is as follows: const [name, setName] = useState(INITIAL_VALUE). As you can see, it uses array destructuring in order to provide the value and the set function:

const Space = ({ color }) => {
  const [stars, setStars] = useState(createStars(window.innerWidth));

  return (
    <div className="space">
      {renderStars(stars, color)}
    </div>
  );
};

The usage of the property is trivial, while setStars(stars) will be equivalent to this.setState({ stars }).

Component initialization

Another prominent limitation of functional components was the inability to hook to lifecycle events. Unlike class components, where you could simply define the componentDidMount method, if you want to execute code on component creation, you can't hook to lifecycle events. Let's extend our demo by adding a resize listener to window which will change the number of rendered stars in our space when the user changes the width of the browser:

Class components

class Space extends React.Component {
  constructor(props) { ... }

  componentDidMount() {
    window.addEventListener('resize', () => {
      const stars = createStars(window.innerWidth, this.props.color);
      this.setState({ stars });
    });
  }

  render() { ... }
}

Functional components

You may say: "We can attach the listener right above the return statement", and you will be partially correct. However, think about the functional component as the render method of a class component. Would you attach the event listener there? No. Just like render, the function of a functional component could be executed multiple times throughout the the lifecycle of the instance. This is why we are going to use the useEffect hook.

It is a bit different from componentDidMount though--it incorporates componentDidUpdate, and componentDidUnmount as well. In other words, the provided callback to useEffect is executed on every update. Anyhow, you can have certain control with the second argument of useState - it represents an array with the values/dependencies which are monitored for change. If they do, the hook is executed. In case the array is empty, the hook will be executed only once, during initialization, since after that there won't be any values to be observed for change.

const Space = ({ color }) => {
  const [stars, setStars] = useState(createStars(window.innerWidth));

  useEffect(() => {
    window.addEventListener('resize', () => {
      const stars = createStars(window.innerWidth, color);
      setStars(stars);
    });
  }, []); // <-- Note the empty array

  return (
    ...
  );
};

Component destruction

We added an event listener to window, so we will have to remove it on component unmount in order to save us from memory leaks. Respectively, that'll require keeping a reference to the callback:

Class components

class Space extends React.Component {
  constructor(props) { ... }

  componentDidMount() {
    window.addEventListener('resize', this.__resizeListenerCb = () => {
      const stars = createStars(window.innerWidth, this.props.color);
      this.setState({ stars });
    });
  }

  componentDidUnmount() {
    window.removeEventListener('resize', this.__resizeListenerCb);
  }

  render() { ... }
}

Functional component

For the equivalent version of the class component, the useEffect hook will execute the returned function from the provided callback when the component is about to be destroyed. Here's the code:

const Space = ({ color }) => {
  const [stars, setStars] = useState(createStars(window.innerWidth));

  useEffect(() => {
    let resizeListenerCb;

    window.addEventListener('resize', resizeListenerCb = () => {
      const stars = createStars(window.innerWidth, color);
      setStars(stars);
    });

    return () => window.removeEventListener('resize', resizeListenerCb);
  }, []); // <-- Note the empty array

  return (
    ...
  );
};

An important remark

It is worth mentioning that, when you work with event listeners or any other methods that defer the execution in the future of a callback/function, you should take into account that the state provided to them is not mutable.

Taking the window listener we use in our demo as an example; if we used thestars state inside the callback, we would get the exact value at the moment of the definition (callback), which means that, when the callback is executed, we risk having a stale state.

There are various ways to handle that, one of which is to re-register the listener every time the stars are changed, by providing the stars value to the observed dependency array of useEffect.

Changed properties

We already went through useEffect in the sections above. Now, we will briefly show an example of componentDidUpdate. Let's say that we want to log the occurances of color change to the console:

Class components

class Space extends React.Component {
  ...

  componentDidUpdate(prevProps) {
    if (this.props.color !== prevProps.color) {
      logColorChange(this.props.color);
    }
  }

  ...
}

Functional components

We'll introduce another useEffect hook:

const Space = ({ color }) => {
  ...

  useEffect(() => {
    logColorChange(color);
  }, [color]); // <-- Note that this time we add `color` as observed dependency

  ...
};

Simple as that!

Changed properties and memoization

Just as an addition to the example above, we will quickly showcase useMemo; it provides an easy way to optimize your component when you have to perform a heavy calculation only when certain dependencies change:

const result = useMemo(() => expensiveCalculation(), [color]);

References

Due to the nature of functional components, it becomes hard to keep a reference to an object between renders. With class components, we can simply save one with a class property, like:

class Space extends React.Component {
  ...

  methodThatIsCalledOnceInALifetime() {
    this.__distRef = calculateDistancesAmongStars(this.state.stars);
  }

  ...
}

However, here is an example with a functional component that might look correct but it isn't:

const Space = ({ color }) => {
  ...

  let distRef; // Declared on every render.

  function thatIsCalledOnceInALifetime() {
    distRef = caclulateDistancesAmongStars(stars);
  }

  ...
};

As you can see, we won't be able to preserve the output object with a simple variable. In order to do that, we will take a look at yet another hook named useRef, which will solve our problem:

const Space = ({ color }) => {
  ...
  const distRef = useRef();

  function thatIsCalledOnceInALifetime() {
    // `current` keeps the same reference
    // throughout the lifetime of the component instance
    distRef.current = caclulateDistancesAmongStars(stars);
  }

  ...
}

The same hook is used when we want to keep a reference to a DOM element.

Conclusion

Hopefully this should give you a starting point when it comes to using React Hooks for the things that you are already used to doing with class components. Obviously, there are more hooks to explore, including the definition of custom ones. For all of that, you can head to the official docs. Give them a try and experience the potential of functional React!

5-minute introduction to Cypher query language

Georgi Serev — Tue, 28 Jan 2020 22:24:04 +0000

The aim of this article is to get you up to speed with the basics of Cypher(the query language used for the Neo4j graph database) in just 5 minutes! So, without further ado, let's get started!

What is a graph data structure? How is it applied in database systems?

Since we are going to show the capabilities of a graph query language, we should get familiar with what a graph is first. If you already know what it is, you can simply move to the next section.

We will skip the formal mathematical definition of a graph intentionally, and just proceed with the graphic below.

As you can see, we have a very simple map of some imaginary cities. They are marked with points or circles, and the distances between are represented by lines. This is actually a graph -- the cities are the nodes , the distances -- edges. Another way to think about it: if you know what a tree is, you can imagine the graph as a tree with loops where there is the possibility for its leafs to be connected.

Graph databases are just harnessing this data structure. Instead of tables, they make use of nodes and edges for modelling the relationship among the available data. Respectively, using a conventional query language won't be sufficient or relevant for such a database. That's where Cypher comes into play.

Our data

Since we need something to work on first, we will introduce the following graph database:

We'll use the relationship between a few of the main characters of Star Wars as an example. The blue circles represent the jedi, whereas green are non-jedi characters. Yellow, on the other hand, are the robots. All of the edges describe the relationship between these characters. As you can see, they can be both uni- and bidirectional.

Writing queries in Cypher

After having a basic understanding of what a graph is, and how the data is composed in the database, you'll find the syntax of Cypher very simple and intuitive to read and write. It is inspired by ASCII art, so you actually model your queries in a some graphical manner. Let's get started.

Nodes and relationships

Let’s start with the core structures of the graph -- nodes and relationships -- they are represented by () and [] plus < or >. For example, let's take a look at the relationship between Anakin and Padme, and how it can be represented with Cypher:

(:Jedi)-[:LOVES]->(:NonJedi)

Simple, isn't it? The arrows show how the nodes relate based on the relationship type that we have. Also, we have labels (or tags), which indicate the type of the nodes and the relationship.

Getting data with `MATCH`

We'll start with some basic examples of fetching data. I'll re-use the query from the previous section. Along with the MATCH keyword, we will be able to ask the database whether there are nodes that match our provided pattern, or subgraph.

The following query will return all jedi that are in love with non-jedi characters.

MATCH (j:Jedi)-[:LOVES]->(:NonJedi)
RETURN j

You probably noticed that we introduced a j in the query. This is simply a variable used for referring to the jedi node. Note that we can use these for relationships as well.

Going back to the query, you might have guessed that, in the case of our current database, we'll end up with Anakin's node being returned. That being said, we can be a bit more specific when creating the pattern:

MATCH (j:Jedi)-[:LOVES]->(:NonJedi)-[:LOVES]->(j)
RETURN j

With it, we can get not only the jedi that are in love with a non-jedi, but all jedi who are in a romantic relationship with a non-jedi (i.e. both sides love each other).

Moving forward, let's try a different query:

MATCH (Jedi)--(Jedi)

You may ask whether it's a valid one, but it completely is. We don't have to necessarily specify the relationship, nor the direction (unless we want to). That being said, this will return every pair of jedis who have a relationship between them like Yoda and Obi-Wan, Obi-Wan and Anakin, and Yoda and Anakin.

Same applies to relationship types. We can specify the type of a relationship while abstracting from node type, like:

()-[:MENTORING]->()

Conditional fetching

Just like in a conventional relational database, we can specify some criteria when fetching data. With Cypher, we have two ways to do that:

1. Inlined JSON-like object

Let's take a look at the following query:

MATCH
  (j1:Jedi { rank: 'master' })-[:MENTORING]->(j2:Jedi)
RETURN
  j2.name

_ Note: Both single and double quotes are valid._

We can describe it as: "Return the names of all jedis who are mentored by a jedi master. Again, this results in getting Anakin's name, but not Ahsoka. Now, we'll write the same query but a bit differently:

2. Using `WHERE`

MATCH
  (j1:Jedi)-[:MENTORING]->(j2:Jedi)
WHERE
  j1.rank = 'master'
RETURN
  j2.name

Using the WHERE clause is equivalent to inlining the JSON-like object in a node. However, it is a fuller and more powerful way of specifying our desired criteria compared to the latter. For example, we can perform a boundary check of a numerical data, whereas that would be impossible with the first approach:

MATCH
  (j1:Jedi)-[:MENTORING]->(j2:Jedi)
WHERE
  j1.age < 100
RETURN
  j2.name

This will return all mentees' names whose mentors are less than 100 years old (i.e. Ahsoka and Anakin).

Keep in mind that we can apply all of these for the relationships as well!

Updating the existing data

After we have a good perception of how data is fetched from the database, we can spend a minute on how it can be updated. This happens with the help of the SET keyword:

MATCH
  (j:Jedi { name: 'Anakin' })
SET
  j.placeOfBirth = 'Tatooine'
  j.dateOfBirth = '41 BBY'
RETURN
  j

The explanation is obvious -- based on the provided search criteria, we perform an update via SET on the returned results. That's it!

Creating new data

In this sub-section, we will introduce two more keywords needed for adding new data to our database. These are CREATE and MERGE. Let's start with a simple example of "create":

CREATE (:Jedi { name: 'Qui-Gon' })

As you might have guessed, it simply adds a new node to our database. But what if we want to create a relation with this node? Well, here, MERGE comes in handy. It is intended for ensuring that the provided pattern exists in the database, which means that if it doesn't, it will be created.

Using the example we have, we can extend it so that Obi-Wan is an apprentice of Qui-Gon:

CREATE
  (qg:Jedi { name: 'Qui-Gon Jinn' })
MERGE
  (qg)-[:MENTORING]->(:Jedi { name: 'Obi-Wan' })

That'll ensure that the non-existent Qui-Gon node will be created, whereas the existing Obi-Wan node will be reused in the specified relation, or created if unavailable.

There are a lot more other use cases. For example, you can perform different updates on creation or on match when using MERGE:

MERGE
  (j:Jedi { name: 'Qui-Gon' })
ON CREATE SET
  j.created = timestamp()
ON MATCH SET
  j.updated = timestamp()
RETURN
  j

Removing data

Finally, we'll briefly go through removing of data from our database. There isn't a lot that needs to be explained, so let's move directly to the examples that we have:

Properties and labels

This is possible using REMOVE. We first search for a pattern, then we provide a property via a variable that has to be removed:

MATCH (r:Robot { name: 'C-3PO' })
REMOVE r.age

We can do the same for labels:

MATCH (r:Robot { name: 'C-3PO' })
REMOVE r:Robot

Deleting nodes and relationships

Let’s introduce yet another keyword called DELETE. With it, we can remove single nodes, like:

MATCH (j:Jedi { name: 'Anakin' })
DELETE j

or relationships:

MATCH (:Jedi { name: 'Anakin' })-[l:LOVES]->()
DELETE l

or a node with all of its relationships altogether, using the additional DETACH keyword:

MATCH (r:Robot { name: 'C-3PO' })
DETACH DELETE r

Further information

This is a simplified article, meant as an introduction. You can always get a deeper understanding of the query language from its official docs. Anyway, hopefully you were able to get an insight of how basic CRUD queries are being created, and how intuitive Cypher is!

This Dot Inc. is a consulting company which contains two branches : the media stream, and labs stream. This Dot Media is the portion responsible for keeping developers up to date with advancements in the web platform. This Dot Labs provides teams with web platform expertise, using methods such as mentoring and training.

Implementing a primitive OCR using k-NN

Georgi Serev — Thu, 07 Nov 2019 01:19:46 +0000

In this article, we are going to implement a really primitive optical character recognition using the k-nearest neighbor classification algorithm. Our language of choice will be JavaScript. Before we move on, we will take a look at what k-NN is, and how it actually works.

k-NN—quick introduction

Let's imagine that we have a forest with three animal species: bears, wolves and foxes. Now consider that we are wildlife researchers who have information about the position of every animal in this forest via GPS trackers. Our data shows that the different species occupy different areas of the forest.

However, one day, our low-quality thermal cameras detect an unknown animal at coordinates M and N in that forest. We should classify that animal.

Hope you liked the short story, but it's time for us to look at the data we have. We will represent the forest as a 2-dimensional Euclidean space:

Seeing the diagram, you might say "Well, the closest animal is a bear, so it must be a bear" and you won't be exactly wrong. But, what if we take the two closest animals, the bear and the wolf? In that case, we can't say for sure what the unknown animal is. What about three? Then it's most likely a wolf.

You probably get where we are going. k-NN, or as its name says, "nearest neighbor," determines which are the k closest neighbors to the object we are attempting to classify. In the case of k = 1 we are actually performing nearest neighbor search which is a special case of k-NN. k = 2 results in an ambiguous output*. However, when k is 3, we receive a satisfactory result. So, as you might have guessed, picking an appropriate k is important for the accuracy of the algorithm.

* In case we have an even k, and ambiguous result, we are comparing the distances of the k-closest neighbors. This is the so-called "modified k-NN." That's why, it is advised to pick an odd k when using a conventional k-NN.

OCR implementation

Now that we know what k-NN is, and how it works, we can focus on our task, which is implementing an OCR. Keep in mind that this is not a production-quality one, nor is it super efficient, but it should give us a good perception of the capabilities of k-NN. Let's start with preparing our training data.

Training data

Just like we had the coordinates of the animals from the forest, we will need some example data for our OCR. This data is called the training data, and since k-NN is a supervised algorithm, it will need it in order to analyze, and classify, the input we provide.

Important note: In reality, k-NN is not really trained unlike other supervised algorithms where we build a model. Because of this, we will refer to "train" or "training" as the process of supplying example data to our algorithm, which is then used during runtime for classification.

For our OCR, we will introduce only the lowercase letters "a," "b," and "c," and will have 4 versions for each. This is a really small set, but it should work relatively well for our demo. Respectively, the larger the training data is, the more accurate results you might expect.

Every letter is comprised of 20 dots, which have x and y in the form:

[{ x: 0, y: 1 }, { x: 2, y: 4 }, ... ]

You can check the full data at GitHub.

Okay, we should be good here. Let's move on.

The application

For the purposes of our OCR, we will need a simple application for testing. We will create a 250 by 250 px plane in which we will render every click as a dark blue dot. Respectively, these dots will represent the points that compose a letter.

Note: The training data used for the algorithm was created using it.

I won't go into details how to implement this app as it is simple—and more importantly—since it's not the subject of this article. You can head to the GitHub repository, and check out the code. It's nothing more than a few div-s, buttons and some event listeners attached to them.

GitHub repo files:

The algorithm

Nice, we reached the cool part of this article. I'll presume that you have taken a look at the app's code already, so we can begin our algorithm with creating a new class named OcrKNN:

export class OcrKNN {
  constructor(k, trainingData) {
    this.__k = k;
    this.train(trainingData);
  }

  test(data) {
    // todo
  }

  train(trainingData) {
    // todo
  }
}

We'll create two methods: test will be used for testing an input data and determining its class (i.e. classification) whereas train will load our k-NN instance with the training/example data needed for the classification. As you can see, we are calling this method in our constructor, where we also pass the k value. Let's start with the implementation of the train method since it is a prerequisite for the testing (obviously). In it, we will perform the data formatting.

Data preparation and formatting

If you already took a look at the format of our training data, you would know that it is kept like this:

{ a: [Array, Array, ...], b: [Array, Array, ...], ... }

However, in order to make our k-NN function as we want, we will have to convert this data so that it is easier to process (and will accommodate for some scenarios we will later explain). In our case, we are going to perform 3 operations:

Sorting
Normalizing
Flattening

1. Sorting

Imagine that we have two 2-point uppercase "I"-s. They are composed like this:

First "I":

[
  { x: 10, y: 5 },
  { x: 10, y: 20 }
]

Second "I":

[
  { x: 10, y: 20 },
  { x: 10, y: 5 }
]

Obviously, they should be the same, but as you can see, the order of the points is different. You'll probably ask "Does it matter?" and the answer will be "In our case, yes." Since we are going to be calculating distances later in our code, an incorrect order can result in an inaccurate output. In case that's not clear now, I'll elaborate later on.

So, for that matter, we will introduce the __sort method:

export class OcrKNN {
  // ...

  __sort(data) {
    return data.slice().sort((a, b) => {
      const xDiff = a.x - b.x;
      if (xDiff !== 0) {
        return xDiff;
      }
      return a.y - b.y;
    });
  }
}

In short: it sorts the points in ascending order where the primary criteria is x and the secondary is y (i.e. if the x-s are equal, sort by y).

2. Normalization

Moving on to the normalization. Here we will take care of two potential problems that may occur during input—the position, and the size of the letter relative to our plane. First, let's tackle the position.

Our script should be able to distinguish a letter input regardless, if it was typed in the upper-left or lower-right corner of our plane. What we are going to do is to find the smallest x and y (mx and my) and then subtract them from the coordinates of every point. Hopefully, this graphical representation of the problem should give you an idea what the operation does:

Next, we will handle the different sizes of the letters. In similar fashion, we will take the biggest x and y from the dataset, but this time we will divide every point by it rather than subtracting. After this operation, we should end up with values between 0 and 1. This will be extremely helpful since now, we won't care about the actual pixels/positions, but for the ratios between the dots relative to 1. Therefore, a small and a large lowercase "a"-s will be virtually the same for our algorithm as long as the ratios between the dots are the same!

All of this can be incorporated in the __normalize method:

export class OcrKNN {
  // ...

  __normalize(data) {
    const xs = data.map(l => l.x);
    const ys = data.map(l => l.y);
    const offsetX = Math.min(...xs);
    const offsetY = Math.min(...ys);
    const maxX = Math.max(...xs) - offsetX;
    const maxY = Math.max(...ys) - offsetY;

    return data.map((l) => ({
      x: (l.x - offsetX) / maxX,
      y: (l.y - offsetY) / maxY
    }));
  }
}

3. Flattening

The final step of our data preparation will be the flattening. What we want to achieve is a single array with all of the points in the following format:

//  x1   y1    x2   y2       x3  y3
[    0, 0.1,    1, 0.5,    0.75,  0, ... ]

I'll explain why we need this transformation later on. For now, let's just focus on the implementation of the flattening represented by yet another method called __flatten (for your amazement):

export class OcrKNN {
  // ...

  __flatten(data) {
    return data.reduce((arr, point) => {
      arr.push(point.x, point.y);
      return arr;
    }, []);
  }
}

In the end, we will compose these methods in __format:

export class OcrKNN {
  // ...

  __format(data) {
    data = this.__sort(data);
    data = this.__normalize(data);
    return this.__flatten(data);
  }
}

Simple, isn't it?

Finalize training process implementation

So far, so good. What's left is to go through the passed training set, and use the power of __format to make our data nice and tidy for the calculations we are going to perform in the next section of the article.

You should be aware of the form of our training data by now. We will create a new property named __trainingData which is an array in our OcrKNN class. In it, we will push every letter from the provided data. Once again, we are aiming for a flatter structure. The output should look like this:

[
  { clss: 'a', data: [ 0, 0.1, 1, ... ] },
  { clss: 'a', data: [ 0, 0.1, 1, ... ] },
  { clss: 'a', data: [ 0, 0.1, 1, ... ] },
  { clss: 'b', data: [ 0, 0.1, 1, ... ] },
  { clss: 'b', data: [ 0, 0.1, 1, ... ] },
  ...
]

And the method implementation:

export class OcrKNN {
  // ...

  train(trainingData) {
    this.__trainingData = [];

    // Go through every property of the training data object (i.e. "a", "b", etc.)
    Object.keys(trainingData).forEach((clss) => {
      // Iterate through every test letter from the current class
      trainingData[clss].forEach((l) => {
        // Format the [{ x, y }, ...] letters
        // to a flat array of [0, 0.1, 1, ...]
        // and then push it to the training set
        // in a { className, flatArray } form
        this.__trainingData.push({
          clss,
          data: this.__format(l)
        });
      });
    });
  }
}

Note: clss means "class" but since it is a keyword in JavaScript, we will use the version without vowels.

Calculating the distances

It's this part of the article that should clear a lot of things up for you. We already implemented the train method, so we are left only with the testing part, where most of the "magic" happens.

Let's start with going back to our analytic geometry classes (if you haven't taken these, don't worry). In the beginning of our article, we talked about "Euclidean space". Now, considering that we have "distance" in the title of the section, mentioned "analytic geometry", and "Euclidean space", you might realize that what's next is introducing a formula ... and you'll be correct! We are going to use the Euclidean distance formula, which is:

where p and q are the points between which we want to calculate the distance.

However, this formula won't really help us—we don't have two points or anything like that. Anyway, it was a good starting point. What we actually need is to go beyond the 2-dimensional space of these two dots. We need an n-dimensional space:

where p and q can be represented as n-tuples.

At this point, you might be frightened, but you shouldn't be. Do you remember that our letters were composed from 20 points, and then we flattened this array, respectively, ending with an array that has 40 entries? Well, what we are going to work with is a 40-dimensional space. And, yes—you don't have to imagine it. We will have to calculate the distances from our input to every other letter in our 40-space in pursuit of the scalar values that will determine the output of this algorithm. Hopefully, at this point, the flattening part of the data preparation should make sense to you. Let's take a look at the code:

export class OcrKNN {
  // ...

  test(data) {
    // Format training data
    data = this.__format(data);
    const distances = [];

    // Iterate through every letter from the training set
    this.__trainingData.forEach((l) => {
      let sum = 0;

      // Calculate the distance via the Euclidean distance formula
      // Note: having similar dot order is crucial
      // for the outcome of this calculation hence
      // why we sorted the data!
      for (let i = 0; i < data.length; i += 1) {
        sum += (data[i] - l.data[i]) * (data[i] - l.data[i]);
      }

      // Push the calculated distance
      distances.push({
        clss: l.clss,
        dist: Math.sqrt(sum)
      });
    });

    // ...
  }
}

It's apparent that the first step is to format our input/test data just like we did with our training data. After that, we are just iterating though all available example letters and calculating the distance of the test letter we want to classify. In the end, the distances array should contain all distances with their respective class. The last step is to aggregate this data so that we find the k nearest neighbors.

export class OcrKNN {
  // ...

  test(data) {
    // ...

    return distances
      .sort((a, b) => a.dist - b.dist) // Sort the distances in DESC order
      .map((d) => d.clss) // Map the output to an array with class names only
      .slice(0, this.__k) // Take the first K elements
      .reduce((map, lett) => { // Create a map in the format [[CLASS_NAME, OCCURRENCES], ...]
        let added = false;
        for (let i = 0; i < map.length; i += 1) {
          if (map[i][0] === lett) {
            map[i][1] += 1;
            added = true;
          }
        }
        if (!added) {
          map.push([lett, 1]);
        }
        return map;
      }, [])
      .sort((a, b) => b[1] - a[1]) // Sort the map by occurrence number in DESC order
      .shift() // Get the first map element
      .shift(); // Return the key of the element (i.e. the class)
  }
}

We are done with the algorithm!

Tying it all together

Let's move back to our app; we would like to create an instance of OcrKNN, set a k, provide training/example data for classification, and finally create a test letter for classification. Let's use a <button id="test"> in order to trigger the k-NN and a <div id="result"> where we can show the result:

import { Letters } from './letters.js';

const K = 3;
const data = []; // Array that contains the user input (i.e. dots/points of the test letter)

function initTestBtn() {
  const knn = new OcrKNN(K, Letters);

  document.getElementById('test')
    .addEventListener('click', () => {
      const result = knn.test(dots);
      resultEl.innerText = `The letter is "${result}"`;
    });
}

Due to the small number of example letters that we have, we are going to pick a small odd k. In our case, 3 should do the job.

The only remaining thing now is to test our completed app!

We should expect relatively correct test output. Don't be amazed, however, if your letter is recognized as a different one. In my experience, the letter "c" is sometimes confused for an "a". Anyway, as we said earlier, we would need a significantly larger training dataset (along with a good k) in order to improve and granulate the accuracy of our algorithm.

All of the code used in this article can be found on GitHub.

Conclusion

Hopefully, this example of a primitive OCR gave you a perspective on how k-NN could be used in practice. However, as you might've guessed, the major downside of this classification algorithm is the potentially weak performance and efficiency—we are forced to calculate all distances in order to classify an object, which might be a slow process when our training/example dataset grows. Still, its simplicity makes it a great tool when used appropriately!

This Dot Inc. is a consulting company which contains two branches : the media stream and labs stream. This Dot Media is the portion responsible for keeping developers up to date with advancements in the web platform. In order to inform authors of new releases or changes made to frameworks/libraries, events are hosted, and videos, articles, & podcasts are published. Meanwhile, This Dot Labs provides teams with web platform expertise using methods such as mentoring and training.

Quick intro to Genetic algorithms (with a JavaScript example)

Georgi Serev — Mon, 21 Oct 2019 23:27:14 +0000

The purpose of this article is to give the reader a quick insight into what genetic algorithms are, and how they work.

In short: What are genetic algorithms?

Genetic algorithms are a metaheuristic inspired by Charles Darwin's theory of natural selection. They replicate the operations: mutation, crossover and selection. These features make them suitable for use in optimization problems. Because of this, they find applications in a lot of disciplines like chemistry, climatology, robotics, gaming, etc. They are part of evolutionary computation.

The example problem

Before implementing the algorithm, let's take a look of the problem we are going to solve.

You might have heard about the infinite monkey theorem which states that, given an infinite amount of time, a monkey will almost certainly type logical, meaningful text while randomly pressing the keys on a keyboard. Of course, the lifetime of a monkey will probably not be long enough for this to happen. Still, the chances are greater than zero. Very close to zero, but not zero. Anyway, let's stick to the metaphor.

Another way we can imagine this: imagine we have a device that produces random strings. At some point in the future, regardless how long it takes, it will output our desired text.

The purpose of the genetic algorithm we are going to develop is to find an optimal way to achieve the result we are looking for rather than brute forcing it (which will inevitably take a ludicrous amount of time).

This problem is widely used as an example for GA, so for the sake of consistency and simplicity, we will stick to it.

Parts of GA

We already mentioned some of the operations involved in the process. Let's break down the different steps involved in the GA:

Initializing the population - This is the first step. We will pick a set of members with different traits (or genes). The key here is to have a big enough variety in order to evolve to the target for which we are aiming.
Selection - The process of selecting those members of our population who are fit enough to be reproduced. This happens by predetermined criteria.
Reproduction - After we select the fittest members from our current generation, we will perform a crossover -- mixing their traits/genes. Optionally, we will mutate the newly produced members by some random factor. That way, we will further support the variety in our population.
Repeat 2 and 3 - Simply said -- we will perform selection, crossover and mutation for every new generation until the population evolves to such an extent that we have the desired candidate.

Implementation

Okay, before we start with the algorithm, let's first introduce two utility functions that we are going to use throughout the example. The first one will be used for generating a random integer value in a provided interval, and the second -- generating a letter from a-z:

// Src: MDN
function random(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);

  // The maximum is exclusive and the minimum is inclusive
  return Math.floor(Math.random() * (max - min)) + min;
}

function generateLetter() {
  const code = random(97, 123); // ASCII char codes
  return String.fromCharCode(code);
}

Now that we have our utils ready, we'll start with the first step of the genetic algorithms, which is:

Initializing the population

Let's introduce our population member or the monkey that we referenced previously. It will be represented by an object called Member which contains an array with the pressed keys, and the target string. The constructor will generate a set of randomly pressed keys:

class Member {
  constructor(target) {
    this.target = target;
    this.keys = [];

    for (let i = 0; i < target.length; i += 1) {
      this.keys[i] = generateLetter();
    }
  }
}

For example, new Member('qwerty') can result in a member who pressed a, b, c, d, e, f or y, a, w, r, t, w.

Next, after we have our member created, let's move to the population object, which will keep the set of members we want to evolve:

class Population {
  constructor(size, target) {
    size = size || 1;
    this.members = [];

    for (let i = 0; i < size; i += 1) {
      this.members.push(new Member(target));
    }
  }
}

The Population should accept size and target (target string). In the constructor, we are going to generate size members all with randomly generated words, but with equal length.

This should be enough to create a diverse initial population!

Selection

It's time for us to add some methods to the classes we created. We will start with the Member. Do you remember that we had to develop some criteria based on how we determine the fitness of our members? This is exactly what we are going to do by introducing the fitness method.

Let me elaborate:

class Member {
  // ...

  fitness() {
    let match = 0;

    for (let i = 0; i < this.keys.length; i += 1) {
      if (this.keys[i] === this.target[i]) {
        match += 1;
      }
    }

    return match / this.target.length;
  }
}

As you can see, what we are attempting to do is to find how many of the randomly pressed keys (by a member) match the letters in our target string. The more, the better! Since we want to have a coefficient as an output, we will divide the matches by the length of the target.

Going back to our Population class, we will implement the actual selection operation. Logically, we would like to have the fitness calculated to every member of the population.

Based on that value, we want to increase the chances of the fittest members being selected, and respectively, decrease the chances of selection for the least fit candidates for the new generation. This can happen by adding an additional array called the mating pool. In it, we will add every member, multiplied by its-fitness-coefficient. To grasp this concept, let's take a look at this example:

Member1 (fitness = 4)
Member2 (fitness = 2)
Member3 (fitness = 1)

== Output ==

MatingPool = [
  Member1, Member1, Member1, Member1,
  Member2, Member2,
  Member3
]

At this point, you should be able to guess the idea behind this approach -- to increase the chances of the fittest members being randomly selected. Note that there are different ways for building your mating pool distribution.

And the code:

class Population {
  // ...

  _selectMembersForMating() {
    const matingPool = [];

    this.members.forEach((m) => {
      // The fitter it is, the more often it will be present in the mating pool
      // i.e. increasing the chances of selection
      // If fitness == 0, add just one member
      const f = Math.floor(m.fitness() * 100) || 1;

      for (let i = 0; i < f; i += 1) {
        matingPool.push(m);
      }
    });

    return matingPool;
  }
}

Now that we have readied our selection process, it is time to reproduce!

Reproduction

In this section of the implementation, we will focus on the crossover, and mutation operations. This will require further extending of our Member class. I will start by creating the crossover method. Its role is to combine/mix the traits, genes, or in our case, keys, of two parents randomly selected from the mating pool. The output child might contain only keys from parent A or keys from parent B, but in most cases, it will contain keys from both the parents. This happens by selecting a random index from the array that contains them:

class Member {
  // ...

  crossover(partner) {
    const { length } = this.target;
    const child = new Member(this.target);
    const midpoint = random(0, length);

    for (let i = 0; i < length; i += 1) {
      if (i > midpoint) {
        child.keys[i] = this.keys[i];
      } else {
        child.keys[i] = partner.keys[i];
      }
    }

    return child;
  }
}

Since we are working with the Member, let's add our last method to it. This is the mutate method. Its purpose is to give some uniqueness, and randomness, to the newly created child. It's worth mentioning that the mutation is not something that every genetic algorithm incorporates. That's why we will use a rate which will make the process controlled:

class Member {
  // ...

  mutate(mutationRate) {
    for (let i = 0; i < this.keys.length; i += 1) {
      // If below predefined mutation rate,
      // generate a new random letter on this position.
      if (Math.random() < mutationRate) {
        this.keys[i] = generateLetter();
      }
    }
  }
}

// We will also have to update the Population constructor
class Population {
  constructor(size, target, mutationRate) {
    size = size || 1;
    this.members = [];
    this.mutationRate = mutationRate // <== New property

    // ...
  }

  // ...
}

It's time to tie these two in our Population class. Previously, we added the _selectMembersForMating. Let's make use of it:

class Population {
  // ...

  _reproduce(matingPool) {
    for (let i = 0; i < this.members.length; i += 1) {
      // Pick 2 random members/parents from the mating pool
      const parentA = matingPool[random(0, matingPool.length)];
      const parentB = matingPool[random(0, matingPool.length)];

      // Perform crossover
      const child = parentA.crossover(parentB);

      // Perform mutation
      child.mutate(this.mutationRate);

      this.members[i] = child;
    }
  }
}

Here, we only pick 2 random parents. Then, we perform the crossover. After that comes the mutation. And then finally, we replace the member with the new child. That's it!

We are almost done. For the purposes of this demo, we are going to add control over the number of generations (or iterations) that we want to have. That way, we can closely monitor how our population changes over time. In a real world scenario, we would like to create new generations until we reach our final goal or target. Anyway, let's add the final evolve method to the Population class for that goal:

class Population {
  // ...

  evolve(generations) {
    for (let i = 0; i < generations; i += 1) {
      const pool = this._selectMembersForMating();
      this._reproduce(pool);
    }
  }
}

In the end, we will add a helper function that will make the running process a bit easier for us:

function generate(populationSize, target, mutationRate, generations) {
  // Create a population and evolve for N generations
  const population = new Population(populationSize, target, mutationRate);
  population.evolve(generations);

  // Get the typed words from all members, and find if someone was able to type the target
  const membersKeys = population.members.map((m) => m.keys.join(''));
  const perfectCandidatesNum = membersKeys.filter((w) => w === target);

  // Print the results
  console.log(membersKeys);
  console.log(`${perfectCandidatesNum ? perfectCandidatesNum.length : 0} member(s) typed "${target}"`);
}

generate(20, 'hit', 0.05, 5);

Running this, we will create a population of 20 members whose target is to type "hit". We'll execute it for 5 generations with a mutation rate of 5%.

Note: Keep in mind that, for our demo, the target string must contain only lowercase a-z letters.

Results

Having this particular population evolve for 5 generations will probably end up with 0 members who typed "hit". However, making that number 20 might land us a good candidate:

  5 Generations  |  20 Generations
-----------------|------------------
       ...       |        ...
                 |
      'gio'      |       'fit'
      'yix'      |       'hrt'
      'gio'      |    >> 'hit' <<
      'kbo'      |       'hiy'

Online demo

You can find the full source code on GitHub

If you want to dig more into genetic algorithms ...

Since the article only lightly touches on what genetic algorithms are, I highly recommend you check out The Nature of Code by Daniel Shiffman (from which this text was based on). It is a great resource for those who want a deeper insight.

Enjoy this article? Head on over to This Dot Labs and check us out! We are a tech consultancy that does all things javascript and front end. We specialize in open source software like, Angular, React and Vue.

lit-html rendering implementation

Georgi Serev — Sat, 12 Oct 2019 17:37:36 +0000

In a world of dominant large UI frameworks and libraries, a simple solution is attempting to combine the ergonomics of the existing technologies and the power of the modern web standards.

The aim of this article is to give you an insight of the core concepts of lit-html's rendering process. But, before that:

What is lit-html?

Note: In case you are familiar with lit-html, you can skip this section.

lit-html is a templating library which makes use of the built-in browser HTML parser rather than incorporating standalone one. Internally it creates <template> elements from user-defined string literals, and inserts and/or updates the data provided on render where needed. This makes the library not only a good performer but also extremely small!

Template literals and tagged templates

Before moving to the core part of this article, it is important to cover the not-so-popular tagged template literals which are a more advanced form of template literals. The functionality allows the user to inspect the different parts of a template literal -- the static string parts and the interpolated data. The tag itself is represented as a function:

function hello(strings, name, surname) {
  return {
    strings,
    name,
    surname
  };
}

const name = 'John';
const surname = 'Doe'

const obj = hello`Hello, ${name} ${surname}!`;

console.log(obj);

// Output:
// {
//    name: 'John',
//    surname: 'Doe',
//    strings: [ 'Hello, ', '!' ]
// }

Note that the tag function (template tag) doesn't neccesarily return a string. In our case, we return an object with the tag function input data.

A simple template

Now, that we have basic understanding of what lit-html is and how tagged templates work, let's create a small test template for the sake of consistency. First, we should import the html template tag from lit-html. Then, we can write a function that returns a template literal which will represent the lit-html template we want.

import { html } from 'lit-html';

const badge = (title) => html`
  <div class="badge">
    <p>${title}</p>
  </div>
`;

Note: lit-html supports SVG templates as well via the svg tag

Last, we would like to render the template somewhere. For this purpose, we will have to import one more function called render, again from lit-html. As its name indicates, it should help us display our template on the screen:


import { html, render } from 'lit-html';

//...

render(badge('Admin'), document.body);

The function itself accepts a template and a container as its first two arguments. After execution we should have our admin badge added in the body of the page. Simple, isn't it? Okay, let's take a look how this works behind the scenes.

Further information

If you are interested in expanding your lit-html knowledge before learning about rendering, you can take a look at these:

GitHub repos list app online demo by Martin Hochel
Article example online demo
Official lit-html docs

Rendering implementation

Disclaimer: The article is written based on lit-html v1.1

We already learnt how we can write a simple lit-html templates via the html template tag and the render function. Now we will explore the internals of the library. Note that we won't cover all of the details but the core concepts. The idea is to get an insight how this thing runs. In the process we will include code snippets of the different phases which are taken from lit-html source code. However, they are greatly simplified, so be advised.

We can informally separate the process in three parts:

Preparation - html template tag and render function
Template processing - creation of <template> & lit-html Template
Creating a template instance - TemplateInstance & cloning

Let's get started!

1. Preparation

In the very beginning, let's explore what the html template tag does. We will introduce the TemplateResult which is nothing more but a wrapper of the static string parts and the values from the tag function. Additionally, it keeps a reference to a TemplateProcessor and it has a method which generates a <template> called getTemplateElement. We will cover these two later. So, what lit-html does with html template tag is to simply create a new instance of the TemplateResult. All of this can be summarized in this code snippet:

class TemplateResult {
  strings: ReadonlyArray<string>;
  values: ReadonlyArray<unknown>;
  processor: TemplateProcessor;

  constructor(strings, values, processor) { /* ... */ }

  getTemplateElement(): HTMLTemplate { /* ... */ }
}

const defaultTemplateProcessor = /* ... */

function html(strings, value): TemplateResult {
  return new TemplateResult(strings, values, defaultTemplateProcessor);
}

Following the steps that we used in the demo, a generated TemplateResult should be then passed to the render function. It looks like we are almost done, but actually most of the work starts from here.

Having a dive into render implementation, we will notice that it has access to a weak map which associates a render container with an object of type NodePart. It acts as a cache:

const parts = new WeakMap();

function render(result: TemplateResult, container: Element | DocumentFragment) {
  let part = parts.get(container);

  if (part === undefined) {
    // *Clear container, if full*
    part = new NodePart(templateFactory);
    parts.set(container, part);
    part.appendInto(container);
  }

  part.setValue(result);
  part.commit();
}

Source of render function

Presumably, there should be a lot of questions. Let's start with what NodePart is. Well, NodePart or Part (the interface) represents a dynamic part of a template instance rendered by lit-html. Or in other words -- where our data is plugged.

As you can see in the code above, we append a Part into our container (e.g. in our demo case - the body). This happens only, if the container hasn't been used for rendering yet. If it was, the cache will already have a Part associated with it. It's interesting that if you take a look at the DOM tree at this step of the process, you will notice some empty HTML comments added to it. These are used as markers for the beginning and the end of the respective Part.

After we have our container prepared (i.e. with inserted Part), we set the TemplateResult as pending value to the respective Part. By commit-ing after that, the template processing triggers.

Moving forward, we will elaborate on commit and templateFactory in the next section.

Note: The WeakMap will allow to have its values garbage-collected, if they aren't referenced anywhere in the code.

2. Template processing

In the first section we just mentioned about the getTemplateElement method of the TemplateResult. Here we will actually make use of it. What it does is simple -- join all static string parts of the template and add markers where we plan to plug data. In the end, return a <template>. lit-html uses different types of markers depending on the place of interpolation. For instance, the content of an element will be marked with a comment of  type whereas an attribute -- with ATTR_NAME$lit$="{{lit-guid}}". If we take the template we wrote in our demo above as an example, we will end up with something like this:

<template>
  #document-fragment
  <div class="badge">
    <p><!--{{lit-9858251939913858}}--></p>
  </div>
</template>

Cool, isn't it?

Okay, nice. The next part of the chain is the templateFactory which we passed previously on our NodePart. It incorporates the Factory pattern with some caching as you might've already guessed from the name. The output -- a lit-html template or Template:

class Template {
  parts: TemplatePart[] = [];
  element: HTMLTemplateElement;

  constructor(result: TemplateResult, template: HTMLTemplateElement) {
    this.element = template;
    while (partIndex < result.values.length) {
      // ...
      this.parts.push({ type: 'node', index });
      // ...
    }
  }
}

function templateFactory(result: TemplateResult) {
  // *Check if template is in cache. If not, create a new one*
  const t = new Template(result, result.getTemplateElement());

  // *Add to cache*

  return t;
}

What the Template does is to process the generated <template> from the TemplateResult by recording/tracking the positions of the markers that we talked about earlier. That way, our lit-html template is ready to be used.

Okay, let's go back to the NodePart and the commiting process we've been talking about.

It is important to mention that for the purposes of this article, we will cover only the process of commiting of a TemplateResult. You might already know that a Part can accept a node, an iterable or text as well.

class NodePart implements Part {
  commit(value) {
    // ...
    this._commitTemplateResult(value);
    // ...
  }

  _commitTemplateResult(value) {
    // Create a Template
    const template = this.templateFactory(value);

    if (this.value instanceof TemplateInstance && this.value.template === template) {
      // *Update the instance*
    } else {
      // *Create the instance*
      this.value = /* new instance */
    }
  }
}

Source of NodePart

As you can see this is where we make use of the template factory which should return a ready-to-use lit-html Template. After that we create or update the template instance associated with the NodePart.

3. Creating a template instance

It's time to create our TemplateInstance. The instance is an object
that accepts a lit-html Template and the processor we briefly mentioned in the first code snippet. Its task is to use the processor in order to create dynamic parts in the document fragment derived from the <template> during cloning:

class TemplateInstance {
  private _parts: Array<Part|undefined> = [];
  processor: TemplateProcessor;
  template: Template;

  constructor(template: Template, processor: TemplateProcessor) { /* ... */ }

  update(values: ReadonlyArray<unknown>) {
    // *for each part*
    // *set a value and then commit*
  }

  clone(): DocumentFragment {
    // ...
    const fragment = this.template.element.content.cloneNode(true) as DocumentFragment;

    // *Use the processor and the Template's part metadata to create Parts*

    return fragment;
  }
}

Source of TemplateInstance

The processor itself contains the lit-html template specific stuff like the attribute prefixes . @ or ?. Based on this syntax, it creates a Part -- NodePart, AttributePart, etc.

Finally, after we have our instance created and cloned, we can commit it which means that it is inserted to the DOM. At this point of the process you should be able to see the template rendered on the screen!

Now, on every new update, lit-html will use the exactly the instance and will modify only the values of the dynamic parts we created. Neat!

lit-html GitHub repository

In short

lit-html builds a HTML template by concatenating the static string parts and inserting markers where an interpolation is going to happen.
Later, the locations of these markers are recorded in an lit-html template object.
An instance is created. The metadata from the lit-html template is used in order to create dynamic parts within the template instance.
Finally, the ready product is added to the DOM and the dynamic parts are being updated when new values are provided.

Conclusion

While the templating with lit-html looks very similar to what we have with the popular web UI technologies, it is vastly different behind the scenes. The lack of an additional compilation step or the need of a virtual DOM, contribute to the simplicity of this templating library which has its own place in the modern and diverse front-end world.

Forem: Georgi Serev

Virtual scrolling of content with variable height with Angular

Harnessing @angular/cdk

@angular/cdk-experimental

Chapters

Contents

I. Case study – Hero Feed

II. VirtualScrollStrategy – What is that?

Summary

III. Setting up the custom strategy

Data source

Infinite scrolling

Summary

IV. Strategy implementation

Determining the height of the messages (list items)

Incorporating height prediction

Complementary methods

Improving height measurement

Final code

Conclusion

Transitioning from React class components to function components with hooks

Functional components

Component state

Class components

Functional components

Component initialization

Class components

Functional components

Component destruction

Class components

Functional component

An important remark

Changed properties

Class components

Functional components

Changed properties and memoization

References

Conclusion

5-minute introduction to Cypher query language

What is a graph data structure? How is it applied in database systems?

Our data

Writing queries in Cypher

Nodes and relationships

Getting data with MATCH

Conditional fetching

1. Inlined JSON-like object

2. Using WHERE

Updating the existing data

Creating new data

Removing data

Properties and labels

Deleting nodes and relationships

Further information

Implementing a primitive OCR using k-NN

k-NN—quick introduction

OCR implementation

Training data

The application

The algorithm

Data preparation and formatting

1. Sorting

2. Normalization

3. Flattening

Finalize training process implementation

Calculating the distances

Tying it all together

Conclusion

Quick intro to Genetic algorithms (with a JavaScript example)

In short: What are genetic algorithms?

The example problem

Parts of GA

Implementation

Initializing the population

Selection

Reproduction

Results

If you want to dig more into genetic algorithms ...

lit-html rendering implementation

What is lit-html?

Template literals and tagged templates

II. `VirtualScrollStrategy` – What is that?

Getting data with `MATCH`

2. Using `WHERE`