sorted-iterators-find-matching

Given an iterator/list of sorted items, find matching items in another (sorted) iterator/list.

Installation

npm install sorted-iterators-find-matching

Usage

Let's say you have a sorted list of people

const people = [
	{id: 'ada', name: 'Ada'},
	{id: 'bob', name: 'Bob'},
	{id: 'dora', name: 'Dora'},
]

and a list of books, sorted by who owns them:

const books = [
	// Ada has no books.
	{nr: 5, belongsTo: 'bob'},
	{nr: 1, belongsTo: 'bob'},
	{nr: 4, belongsTo: 'bob'},
	// We don't know who Carlos is.
	{nr: 6, belongsTo: 'carlos'},
	{nr: 2, belongsTo: 'carlos'},
	{nr: 0, belongsTo: 'dora'},
	{nr: 3, belongsTo: 'elisa'},
]

Because both lists are sorted by the "person ID", all books owned by a single person occur consecutively. Therefore, we can tell which books a person owns, only by reading the books list until it mentions a different person. This is what sorted-iterators-find-matching does:

const iterateMatching = require('sorted-iterators-find-matching')

// We define a function that, given a person, tells if the book belongs to
// - that person, or
// - a person with an alphabetically ealier/lower person ID, or
// - a person with an alphabetically later/higher person ID.
const matchBookWithPerson = (person, book) => {
	if (person.id === book.belongsTo) return 0
	return person.id < book.belongsTo ? -1 : 1
}
const ownedBooks = iterateMatching(matchBookWithPerson, books)

for (const person of people) {
	console.log(`${person.name} has these books:`)
	for (const book of ownedBooks(person)) console.log(`- ${book.nr}`)
}

async iterators

If you have two async iterators, use sorted-iterators-find-matching/async:

const iterateMatching = require('sorted-iterators-find-matching/async')

const match = (itemOfListA, itemOfListB) => {
	if (itemOfListA.field === itemOfListB.field) return 0
	return itemOfListA.field < itemOfListB.field ? -1 : 1
}
const matching = iterateMatching(match, listA)

// Note the `for await`!
for await (const itemA of listA) {
	for await (const itemB of matching(itemA)) {
		console.log(itemA, itemB)
	}
}

Contributing

If you have a question or need support using sorted-iterators-find-matching, please double-check your code and setup first. If you think you have found a bug or want to propose a feature, use the issues page.

derhuerst / sorted-iterators-find-matching Goto Github PK