0

I have a large data set of world cities (100K+ objects in an array), and a user's location information. I want to sort the array of world cities by the user's location, and return the top 7 (or however many) most relevant matches.

For example, if a user is located in Newport Beach, CA, USA, I want to sort the array where all "Newport Beach" cities in the United States show up first, with the user's exact location as the first result in the array.

The user's location comes in via an API, and is saved to local variables:

const userCity = "Newport Beach";
const userState = "CA";
const userCountry = "United States";

The original array is saved to a variable named allCities. I sort this array as follows:

allCities
  .sort((a, b) => b.city.startsWith(userCity) - a.city.startsWith(userCity))
  .sort((a, b) => b.state && b.state.startsWith(userState) - a.state && a.state.startsWith(userState)) // This should only apply to the U.S.
  .sort((a, b) => b.country.startsWith(userCountry) - a.country.startsWith(userCountry));

And the result, which I am slicing to return only the first 7 matches:

const list = [
  { city: 'Newport', state: 'AR', country: 'United States' },
  { city: 'Chevy Chase Village',
    state: 'MD',
    country: 'United States' },
  { city: 'Newport', state: 'NH', country: 'United States' },
  { city: 'Newport', state: 'ME', country: 'United States' },
  { city: 'Newport', state: 'TN', country: 'United States' },
  { city: 'Newport', state: 'SC', country: 'United States' },
  { city: 'Newport', state: 'IN', country: 'United States' }
]

The problem here is that "Newport Beach" in "CA" doesn't even show up. The user should not have to type in the full name of their city. After just the first few characters, their location should be the first result, like an IntelliSense feature, since I already have their information.

I also don't know how Chevy Chase Village in MD showed up in the search results when "Newport Beach" was the search term.

The very first result should be the exact city, state (if they're in the U.S.), and country of the user. The second result should be the same city and country, but different states (again, if they're in the U.S.). Lastly, the same city, but other countries. If no matches are found, I will notify the user.

One thing to note is that I had a version of this that worked perfectly in the browser:

allCities
  // Show closest matching cities first
  .sort(location => userLocationData && location.city === userLocationData.city ? -1 : 1)
  // Show exact matches based on city length
  .sort((a, b) => a.city.length - b.city.length)
  // Show closest matching countries
  .sort(location => userLocationData && location.country === userLocationData.country ? -1 : 1)
  // Show closest matching states
  .sort(location => userLocationData && location.state === userLocationData.region ? -1 : 1);

The problem with this approach is that the allCities array has with over 100K objects (over 8 MB), so it won't load on slow connections. It's also probably not ideal to load that much data on a device.

When I tried to use this logic in the server, it wouldn't run. I'm thinking it's because sort() requires two arguments, and here, I'm providing only one. Other questions/answers provided on SO (like this one) were helpful, but none seemed to do the trick.

How can I sort this array based on user input to achieve the desired results?

Farid
  • 1,557
  • 2
  • 21
  • 35
  • 1
    sounds like you should be sorting by exact matches first – epascarello Jul 27 '20 at 23:31
  • 4
    Every time you call `.sort()`, you lose the previous ordering. – Pointy Jul 27 '20 at 23:32
  • 1
    See https://stackoverflow.com/questions/7160263/can-javascript-or-jquery-sort-a-json-array-on-multiple-criteria for how to sort by multiple criteria. – Barmar Jul 27 '20 at 23:35
  • You need a stable sort, for example see https://stackoverflow.com/questions/1427608/fast-stable-sorting-algorithm-implementation-in-javascript – Nick Jul 27 '20 at 23:40
  • @Nick even with a stable sort, sorting (for example) by length of the city name *after* sorting by the location will render the first sort results null and void. The user may be in Alomogordo, so all the records for Peoria will come first. – Pointy Jul 27 '20 at 23:43
  • @Pointy yes - for that case you are absolutely right. But for OPs first code (sorting on city, state then country) a stable sort should solve the problem. – Nick Jul 28 '20 at 00:07
  • @epascarello - that was my goal, but couldn't get it. `if (b.city.startsWith(userCity) === a.city.startsWith(userCity)) return 0;` didn't work. I just tried the same code above again with a different city ("Orange"), and it returned the correct results, but in the opposite order. – Farid Jul 28 '20 at 01:41
  • What is the preferred sort order.... city > state > country? – epascarello Jul 28 '20 at 01:43
  • City > country > state...I think. That's the order I had in my client. If someone is in Orange, CA, United States, that should be the very first result, followed by other cities in CA that begin with "Orange", such as Orangevale, CA, US. Once all matches of "Orange" in the state of CA have been exhausted, move to matches of "Orange" in other states in the U.S with similar logic (exact "Orange" matches, followed by cities that have "Orange" in their name). Finally, other countries with "Orange" cities, such as Orange, Australia. – Farid Jul 28 '20 at 01:55
  • I think I'm close. The problem now is I can't seem to sort by state. Some states are `null` (outside the U.S.), but when I do `return (a.state !== null) - (b.state !== null);`, I get no results. – Farid Jul 28 '20 at 03:59

1 Answers1

0

I found something that worked.

allCities.sort((a, b) => {
  if (b.city.startsWith(userCity) > a.city.startsWith(userCity)) return 1;
  if (b.city.startsWith(userCity) < a.city.startsWith(userCity)) return -1;

  if (b.country.startsWith(userCountry) > a.country.startsWith(userCountry)) return 1;
  if (b.country.startsWith(userCountry) < a.country.startsWith(userCountry)) return -1;

  if (a.state === b.state) {
    return 0;
  } else if (a.state === null) {
    return 1;
  } else if (b.state === null) {
    return -1;
  } else {
    return b.state.startsWith(userState) - a.state.startsWith(userState);
  }
})

This solution will take in a user's location: city, state (if one exists), and country. It will sort by city first with an exact match, then by country to show only the user's country first, and finally by state to show matching cities in different states in that user's country. I found the state solution here. I spent too long on this, so hopefully this helps someone else as well.

Farid
  • 1,557
  • 2
  • 21
  • 35