DEV Community

Josh Holbrook
Josh Holbrook

Posted on

1 1

Matanuska ADR 005 - Editor Operations

This article is a repost of an ADR from Matanuska BASIC, my attempt to write a BASIC interpreter in TypeScript.

Context

The editor needs to insert, update and delete lines from a Program. These lines are ordered in an array.

Inserting into arrays is not particularly efficient as compared to a hash map. One way to handle this may be to store indexes line numbers in a Map - that would give O(1) access to the location of a line. However, that lookup won't work if the line doesn't exist yet, and requires an additional data structure. Therefore, we will need to seek to the correct location within the array.

In general, binary search is going to be the most efficient mechanism for finding the right location, scaling at O(log n). However, in terms of actual use, lines are often being entered into the program in order - and in a new program, at the very end.

Decision

Line lookup for editing will follow this general algorithm:

  1. Check if the location is at or following the most recently modified line. In that case, return this location.
  2. Check if the location is at or following the last line. In that case, return this location.
  3. If these checks fail, find the location with a binary search.
  4. In all cases, save the location of the most recently inserted line.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

đź‘‹ Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay