Finding objects in array by multiple (and unknown in advance) properties

Question

I have an array of objects. I need to write a function that will search the array by properties/values passed as param object. So for example I have this array of users:

const items = [{
  firstName:"John",
  lastName: 'Doe',
  password: '*******',
  email: '[email protected]',
  role: 'ROLE_ADMIN'
},
{
  firstName:"Jane",
  lastName: 'Doe',
  password: '********',
  email: '[email protected]',
  role: 'ROLE_USER'
},
{
  firstName:"John",
  lastName: 'Roe',
  password: '**********',
  email: '[email protected]',
  role: 'ROLE_USER'
}]

Given I pass to the function the following param

{firstName: 'John'}

I should return an array of 2 objects for both users with the name John. And if I pass this param:

{firstName: 'John', role: 'ROLE_ADMIN'}

then I should return an array with only 1 user (in this case) which matches both params.

If no matching users found - return an empty array. If params is an empty object - return the entire array.

So I wrote this function:

findMany(params) {
  return new Promise((resolve, reject) => {
    const keys = Object.keys(params)
    if (!keys.length || !this.items.length) return resolve(this.items)
    let result = []
    let isMatch = false
    for (const item of this.items) {
      for (const key of keys) {
        if(item[key] === params[key]) {
          isMatch = true
        } else {
          isMatch = false
        }
        if (!isMatch) break
      }
      if (isMatch) result.push(item.toJSON())
    }
    resolve(result)
  })
}

Though it works just fine and I do get the desired result, I was wondering is there a more elegant way to write this? It kinda bugs me to have a nested loop, which increases the time complexity to O(n2). So is there a more elegant solution?

And I still didn't care of a case when someone may pass a property that doesn't exist, i.e.

{firstName: 'John', role: 'ROLE_ADMIN', someProperty: 'some value'}

Not sure how to tackle it...

"to have a nested loop, which increases the time complexity to O(n2)" a nested loop is O(n^2) only when it's looping twice over the same dataset. Therefore, for a dataset of size n it will check every element a number of times equal to n. Having two loops over two different things is not n^2 - at worse it's O(n*m) (here that being the number of properties to check) but m might be not very relevant. If you only check 1-3 properties, then the complexity still scales mostly with the number of elements - n. — VLAZ
– VLAZ, Commented Jun 15, 2022 at 10:28
On a completely different note, I don't know why this needs to be a promise. There is nothing asynchronous happening. — VLAZ
– VLAZ, Commented Jun 15, 2022 at 10:28
@VLAZ Thanks for that time complexity clarification. And yes, I know currently there's nothing aync in this function, had just to convey with other methods in this class. I think it's easier to remember that every method in this class returns a Promise than to remember which one does does and which one doesn't. — Igal
– Igal, Commented Jun 15, 2022 at 10:38

Peter Seliger · Accepted Answer · 2022-06-15 13:23:53Z

2

The implementation of a possible solution is pretty straight forward. One basically has to write a filter function.

Such a function receives a single item and upon some comparison logic returns either of the boolean values.

In addition one can take advantage of the filter method's 2nd thisArg argument which will hold the to be matched key-values pairs, provided as object reference.

Thus one just needs to iterate over the provided object's entries and has to return whether every looked for key-value pair has a matching counterpart in the currently processed item.

function doesItemMatchEveryBoundEntry(item) {
  return Object
    // `this` refers to the bound and to matched entries.
    .entries(this)
    .every(([key, value]) => item[key] === value);
}

const items = [{
  firstName: 'John',
  lastName: 'Doe',
  password: '*******',
  email: '[email protected]',
  role: 'ROLE_ADMIN',
}, {
  firstName: 'Jane',
  lastName: 'Doe',
  password: '********',
  email: '[email protected]',
  role: 'ROLE_USER',
}, {
  firstName: 'John',
  lastName: 'Roe',
  password: '**********',
  email: '[email protected]',
  role: 'ROLE_USER',
}];

console.log(
  "{ firstName: 'John' } ...",
  items
    .filter(
      doesItemMatchEveryBoundEntry,
      { firstName: 'John' },
    ),
);
console.log(
  "{ firstName: 'John', role: 'ROLE_ADMIN' } ...",
  items
    .filter(
      doesItemMatchEveryBoundEntry,
      { firstName: 'John', role: 'ROLE_ADMIN' },
    ),
);

// OP ... If no matching users found - return an empty array.
console.log(
  "{ firstName: 'John', role: '' } ...",
  items
    .filter(
      doesItemMatchEveryBoundEntry,
      { firstName: 'John', role: '' },
    ),
);

// OP ... If params is an empty object - return the entire array.
console.log(
  "{ /* empty */ } ...",
  items
    .filter(
      doesItemMatchEveryBoundEntry,
      { /* empty */ },
    ),
);

.as-console-wrapper { min-height: 100%!important; top: 0; }

OP

And I still didn't care of a case when someone may pass a property that doesn't exist, i.e.
{firstName: 'John', role: 'ROLE_ADMIN', someProperty: 'some value'}
Not sure how to tackle it...

One easily could refactor the above approach into a function which receives the additional information by the filter function's this context as well. The changed implementation takes the OP's last requirement/wish into account and implements it with the desired default behavior of skipping (over) provided property names which do not exist in the processed item.

function doesItemMatchEveryBoundEntry(item) {
  const { params, skipNonExisting = true } = this;

  return Object
    .entries(params)
    .every(([key, value]) =>
      // 2nd next line translates to ... `skipProperty`.
      // (and please do not apply "De Morgan's laws".)
      (!(key in item) && !!skipNonExisting) ||
      (item[key] === value)
    );
}

const items = [{
  firstName: 'John',
  lastName: 'Doe',
  password: '*******',
  email: '[email protected]',
  role: 'ROLE_ADMIN',
}, {
  firstName: 'Jane',
  lastName: 'Doe',
  password: '********',
  email: '[email protected]',
  role: 'ROLE_USER',
}, {
  firstName: 'John',
  lastName: 'Roe',
  password: '**********',
  email: '[email protected]',
  role: 'ROLE_USER',
}];

console.log(
  'DEFAULT ... skip non existing properties',
  "\n ... { params: { firstName: 'John', foo: 'foo' } } ...",
  items
    .filter(
      doesItemMatchEveryBoundEntry,
      { params: { firstName: 'John', foo: 'foo' } },
    ),
);
console.log(
  'DEFAULT ... skip non existing properties',
  "\n ... { params: { firstName: 'John', role: 'ROLE_ADMIN', foo: 'foo' } } ...",
  items
    .filter(
      doesItemMatchEveryBoundEntry,
      { params: { firstName: 'John', role: 'ROLE_ADMIN', foo: 'foo' } },
    ),
);
// OP ... If no matching users found - return an empty array.
console.log(
  'DEFAULT ... skip non existing properties',
  "\n... { params: { role: '', foo: 'foo' } } ...",
  items
    .filter(
      doesItemMatchEveryBoundEntry,
      { params: { role: '', foo: 'foo' } },
    ),
);
// OP ... If params is an empty object - return the entire array.
console.log(
  'DEFAULT ... skip non existing properties',
  "\n... { params: { /* empty */ } } ...",
  items
    .filter(
      doesItemMatchEveryBoundEntry,
      { params: { /* empty */ } },
    ),
);

console.log(
  'explixitly take non existing properties into account',
  "\n ... { skipNonExisting: false, params: { firstName: 'John', foo: 'foo' } } ...",
  items
    .filter(
      doesItemMatchEveryBoundEntry,
      { skipNonExisting: false, params: { firstName: 'John', foo: 'foo' } },
    ),
);
console.log(
  'explixitly take non existing properties into account',
  "\n ... { skipNonExisting: false, params: { firstName: 'John', role: 'ROLE_ADMIN', foo: 'foo' } } ...",
  items
    .filter(
      doesItemMatchEveryBoundEntry,
      { skipNonExisting: false, params: { firstName: 'John', role: 'ROLE_ADMIN', foo: 'foo' } },
    ),
);
// OP ... If no matching users found - return an empty array.
console.log(
  'explixitly take non existing properties into account',
  "\n... { skipNonExisting: false, params: { role: '', foo: 'foo' } } ...",
  items
    .filter(
      doesItemMatchEveryBoundEntry,
      { skipNonExisting: false, params: { role: '', foo: 'foo' } },
    ),
);
// OP ... If params is an empty object - return the entire array.
console.log(
  'explixitly take non existing properties into account',
  "\n... { skipNonExisting: false, params: { /* empty */ } } ...",
  items
    .filter(
      doesItemMatchEveryBoundEntry,
      { skipNonExisting: false, params: { /* empty */ } },
    ),
);

.as-console-wrapper { min-height: 100%!important; top: 0; }

edited Jun 15, 2022 at 13:23

answered Jun 15, 2022 at 11:37

Peter Seliger

13.5k3 gold badges31 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Peter Seliger Over a year ago

@angel.bonev ... it's not about "fast". A good approach mainly is about being focused on the task which results in a straightforward implementation. In the same time it has to be readable to (and thus maintainable by) others. Bonus points are given for a generic enough implementation and code re-usability.

angel.bonev Over a year ago

Point taken, I really liked your approach, it's really elegant and reusable. But I was curious about the part in OP question about complexity. And what is the fastest algorithm to do that. But maybe that part is more suitable for Code Review. Cheers and have a great day

VLAZ Over a year ago

@angel.bonev complexity doesn't exactly mean speed. You can make an algorithm that always takes exactly 5 days to finish, whether the input is one item or 1000. It is going to be O(1) but not very fast. Also, I believe OP had misconception about what complexity even means. Yes, analytically, going through all the items and then for each going through all the fields of the search item is O(n*m) but that's also inherent to the problem. To filter the whole set, you need to go through all of it. And to filter by all fields, you need to go through each.

angel.bonev Over a year ago

@VLAZ when I was talking about "fast" i mean least operations to do something, so for every answer that I saw here it was at minimum O(n + n*m) and that extra n can be removed. But I thing that Peter answer is really good, and easy to read and reuse for different situations

angel.bonev Over a year ago

And after I've concidered Petar's advice and VLAZ explanation. I've came up with this jsBench . It was a pleasure to discuss this with you guys. I've learned a lot

Rohan Veer · Accepted Answer · 2022-06-15 11:10:49Z

-1

You can use filter to filter out the array.

const items = [
  {
    firstName: "John",
    lastName: "Doe",
    password: "*******",
    email: "[email protected]",
    role: "ROLE_ADMIN"
  },
  {
    firstName: "Jane",
    lastName: "Doe",
    password: "********",
    email: "[email protected]",
    role: "ROLE_USER"
  },
  {
    firstName: "John",
    lastName: "Roe",
    password: "**********",
    email: "[email protected]",
    role: "ROLE_USER"
  }
];

function match(params) {
  const keys = Object.keys(params);
  return items.filter((item) => {
    let flag = true;
    keys.every((key) => {
      if ((item[key] && item[key] !== params[key]) || !item[key]) {
        flag = false;
        return false;
      }
      return true;
    });
    return flag;
  });
}

console.log(match({ firstName: "John",role: "ROLE_USER" }));

edited Jun 15, 2022 at 11:10

answered Jun 15, 2022 at 10:36

Rohan Veer

1,5001 gold badge15 silver badges22 bronze badges

4 Comments

VLAZ Over a year ago

There is no reason to use every() and set an external flag. It's just piggybacking on the iteration mechanism. Either write a proper loop or, better yet, just use every as intended flag = Object.keys().every()

angel.bonev Over a year ago

Why do you need to use Object.keys(params) every time ? Can't you just store it , like OP is doing in his code?

Igal Over a year ago

Thank you for your assistance! Though it does look more elegant, I testes it and found some issues: if I pass { some: 'some', firstName: "John", role: "ROLE_USER" }, and the property some doesn't exist on any object, the function still returns an array with that one user. And if I pass only the non-existent property as param { some: 'some' } - it returns an array with all the objects, while it really should be an empty array, as none can match a non-existent property.

Igal Over a year ago

@RohanVeer Thank you very much! Now it does work as expected and does look more elegant than what I wrote! Cheers! :)

Collectives™ on Stack Overflow

Finding objects in array by multiple (and unknown in advance) properties

2 Answers 2

5 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related