18

UPDATE:

I have an array of objects called cars that contains li tags with attribute data about cars (such as price, car type, etc.). My goal is to consolidate these cars into one single listing if they are a match based on certain criteria.

Requirements

  1. Fast Performance
  2. Keep same cars array structure
  3. Main Goal: Match Prepaid and Retail listings - Combine the HTML from Retail listing (such as button and pricing information) into Prepaid Listing. See: enter image description here
  4. If there is a match (based on criteria in IF statement), then remove the matched listing without class "listing-prepaid" AND update matched prepaid listing with certain information from retail listing.

Cars Array:

<li xmlns="http://www.w3.org/1999/xhtml" id="listing-CCAR-RM-AD-SFBT003-AD-SFBT003" data-location-id="AD-28.7455--81.2411" data-dropoff-location-id="AD-28.7455--81.2411" data-partner-name="Advantage" data-partner-code="AD" data-type="CCAR" data-vehicle-class-description="Compact Car" data-seats="5" data-bags="2" data-counter-type="ON_AIRPORT" data-prepaid="Y" data-fare-type="PREPAID" data-transmission="Automatic" data-unlimited-miles="Y" data-preferred="N" data-price="34.81" data-original-price="35.70" data-base-price="24.25" data-vehicle-example="Nissan Versa" data-highlighted="N" data-deal="Y" class="listing listing-prepaid" data-original-position="18"><div class="row"><div class="column column-images"><div class="img-wrapper"><ul class="icons"><li class="people"><span>5</span></li><li class="bags"><span>2</span></li></ul></div></div><div class="column car-details"><div class="car-title"><h3><a><span class="car-class">Compact</span><b></b></a></h3><span class="car-example">Nissan Versa or similar<sup>†</sup></span><span class="counter-type airport">Car on Airport</span></div><div class="features"><span>Unlimited Miles</span></div><div class="car-location-container"><div class="car-location"><h6>Pick-up</h6>SFB: Orlando Sanford Intl Airport</div><div class="car-location"><h6>Drop-off</h6>Same as pick-up</div></div></div><div class="column column-price"><span class="car-badge prepaid">Pay Now &amp; Save 2%</span><div class="container retail prepaid"><div class="rate"><span class="strikethrough"><span class="price-original">$25</span></span><span class="cur-symbol">$</span><span class="price">24</span><span class="rate-plan">/day</span></div><p class="button"><a class="button">Pay Now</a></p><span class="total">Total: $<span class="price">34</span></span></div></div></div><b style="clear:both;display:block;height:1px;width:1px"></b></li>

<li xmlns="http://www.w3.org/1999/xhtml" id="listing-ECAR-RP-HZ-ORLN003-HZ-ORLN003" data-location-id="HZ-28.5042--81.4284" data-dropoff-location-id="HZ-28.5042--81.4284" data-partner-name="Hertz" data-partner-code="HZ" data-type="ECAR" data-vehicle-class-description="Economy Car" data-seats="4" data-bags="1" data-counter-type="" data-prepaid="Y" data-fare-type="PREPAID" data-transmission="Automatic" data-unlimited-miles="Y" data-preferred="N" data-price="36.34" data-original-price="39.95" data-base-price="29.83" data-vehicle-example="Chevrolet Spark" data-highlighted="N" data-deal="Y" class="listing listing-prepaid" data-original-position="30"><div class="row"><div class="column column-images"><div class="img-wrapper"><ul class="icons"><li class="people"><span>4</span></li><li class="bags"><span>1</span></li></ul></div></div><div class="column car-details"><div class="car-title"><h3><a><span class="car-class">Economy</span><b></b></a></h3><span class="car-example">Chevrolet Spark or similar<sup>†</sup></span></div><div class="features"><span>Unlimited Miles</span></div><div class="car-location-container"><div class="car-location"><h6>Pick-up</h6>3575 Vineland Road, Orlando, FL</div><div class="car-location"><h6>Drop-off</h6>Same as pick-up</div></div></div><div class="column column-price"><span class="car-badge prepaid">Pay Now &amp; Save 9%</span><div class="container retail prepaid"><div class="rate"><span class="strikethrough"><span class="price-original">$33</span></span><span class="cur-symbol">$</span><span class="price">29</span><span class="rate-plan">/day</span></div><p class="button"><a class="button">Pay Now</a></p><span class="total">Total: $<span class="price">36</span></span></div></div></div><b style="clear:both;display:block;height:1px;width:1px"></b></li>

<li xmlns="http://www.w3.org/1999/xhtml" id="listing-CCAR-R-AD-SFBT003-AD-SFBT003" data-location-id="AD-28.7455--81.2411" data-dropoff-location-id="AD-28.7455--81.2411" data-partner-name="Advantage" data-partner-code="AD" data-type="CCAR" data-vehicle-class-description="Compact Car" data-seats="5" data-bags="2" data-counter-type="ON_AIRPORT" data-prepaid="N" data-fare-type="RETAIL" data-transmission="Automatic" data-unlimited-miles="Y" data-preferred="N" data-price="35.70" data-base-price="25.00" data-vehicle-example="Nissan Versa" data-highlighted="N" data-deal="N" class="listing" data-original-position="22"><div class="row"><div class="column column-images"><div class="img-wrapper"><ul class="icons"><li class="people"><span>5</span></li><li class="bags"><span>2</span></li></ul></div></div><div class="column car-details"><div class="car-title"><h3><a><span class="car-class">Compact</span><b></b></a></h3><span class="car-example">Nissan Versa or similar<sup>†</sup></span><span class="counter-type airport">Car on Airport</span></div><div class="features"><span>Free Cancellation</span><span>Pay at Pick-up</span><span>Unlimited Miles</span></div><div class="car-location-container"><div class="car-location"><h6>Pick-up</h6>SFB: Orlando Sanford Intl Airport</div><div class="car-location"><h6>Drop-off</h6>Same as pick-up</div></div></div><div class="column column-price"><div class="container retail"><div class="rate"><span class="cur-symbol">$</span><span class="price">25</span><span class="rate-plan">/day</span></div><p class="button"><a class="button">Select Car</a></p><span class="total">Total: $<span class="price">35</span></span></div></div></div><b style="clear:both;display:block;height:1px;width:1px"></b></li>

<li xmlns="http://www.w3.org/1999/xhtml" id="listing-ECAR-R-EX-MCOO001-EX-MCOO001" data-location-id="EX-28.4514095--81.3577729" data-dropoff-location-id="EX-28.4514095--81.3577729" data-partner-name="Executive" data-partner-code="EX" data-type="ECAR" data-vehicle-class-description="Economy Car" data-seats="2" data-bags="1" data-counter-type="OFF_AIR_SHTL" data-prepaid="N" data-fare-type="RETAIL" data-transmission="Automatic" data-unlimited-miles="Y" data-preferred="N" data-price="28.78" data-base-price="14.58" data-vehicle-example="SmartCar" data-highlighted="N" data-deal="N" class="listing" data-original-position="2"><div class="row"><div class="column column-images"><div class="img-wrapper"><ul class="icons"><li class="people"><span>2</span></li><li class="bags"><span>1</span></li></ul></div></div><div class="column car-details"><div class="car-title"><h3><a><span class="car-class">Economy</span><b></b></a></h3><span class="car-example">SmartCar or similar<sup>†</sup></span><span class="counter-type shuttle">Shuttle to Car</span></div><div class="features"><span>Pay at Pick-up</span><span>Unlimited Miles</span></div><div class="car-location-container"><div class="car-location"><h6>Pick-up</h6>MCO: Orlando Intl Airport</div><div class="car-location"><h6>Drop-off</h6>Same as pick-up</div></div></div><div class="column column-price"><div class="container retail"><div class="rate"><span class="cur-symbol">$</span><span class="price">14</span><span class="rate-plan">/day</span></div><p class="button"><a class="button">Select Car</a></p><span class="total">Total: $<span class="price">28</span></span></div></div></div><b style="clear:both;display:block;height:1px;width:1px"></b></li>

Expected Output:

In the above example array, the first and third listings should be a match (since they have same car type, location ids, vehicle example, etc.). The first listing should be removed from the array since it does not have class listing-prepaid AND the HTML within .column-price should be added into its prepaid match (in this example, the 3rd listing in array).

Final Product:

enter image description here

Code:

 cars = cars.reduce((acc, car) => {
    let retail_match = false;
    cars.forEach(car2 => {

        if (((car[0].hasAttribute("data-original-price") && car[0].getAttribute("data-original-price") === car2[0].getAttribute("data-price")) || (car2[0].hasAttribute("data-original-price") && car2[0].getAttribute("data-original-price") === car[0].getAttribute("data-price"))) && (car[0].getAttribute("data-base-price") != car2[0].getAttribute("data-base-price")) && (car[0].getAttribute("data-price") != car2[0].getAttribute("data-price")) && (car[0].getAttribute("data-type") == car2[0].getAttribute("data-type")) && (car[0].getAttribute("data-vehicle-example") == car2[0].getAttribute("data-vehicle-example")) && (car[0].getAttribute("data-location-id") == car2[0].getAttribute("data-location-id")) && (car[0].getAttribute("data-dropoff-location-id") == car2[0].getAttribute("data-dropoff-location-id")))
        {
            if (!car.hasClass("listing-prepaid"))
                retail_match = true;
            else
            {
                car.find(".column-price")
                    .addClass("prepaid-match")
                    .append(car2.find(".column-price div.retail"))
                    .find("div.retail:not(.prepaid) p.button a").text("Pay Later");
            }
        }
    });
    if (!retail_match)
        acc.push(car);
    return acc;
}, []);
Michael
  • 403
  • 1
  • 9
  • 28

4 Answers4

8

As mentioned in the comments, using reduce keeps the complexity at O(n). This basically means, that a list twice the size will take twice the time, as the algorithm only iterates the list of cars once.

If you need to compare each item in the cars array to each other item in the cars array, the complexity with loop-like approaches will ne O(n^2), as for every additional item (roughly speaking) there will be exponentially more loops/time used.

I'm not 100% certain about the data structure of your javascript objects, but the following approach should work:

const allCars = []; // An array of cars, each item is a HTMLElement
let matchedCars = allCars.reduce((acc, car, cars) => {

   cars.forEach(car2 => {
       // For every car iterate over the cars array again to compare car to every item in the cars array (leave out this loop if you don't need the extensive comparison)

       if (car.hasAttribute("data-original-price") 
           && car2.getAttribute("data-original-price") === car.getAttribute("data-price")
          /* Add additional matching criteria here, you may access cars to get info about other cars than the current car */) {

            // Add the desired class for a match
            car.classList.add('listing-prepaid');

            // Add the matched car to the accumulator, so it ends up in the matchedCars array
            acc.push(car);
      }

   });
}, [];

An alternative approach would be to build a data structure that allows access to elements based on their attributes in a constant time (O(1)). An example would be a (Hash)Map. In this case for each element that the algorithm is looping over it is not required to loop through the whole list again to identify matches but to query the Map structure for matches.

Bonus: Given that car is a HTMLElement, you may use the dataset property to access the data-* values easier with:

car.dataset.originalPrice === car.dataset.price

Read more about this at https://developer.mozilla.org/en-US/docs/Learn/HTML/Howto/Use_data_attributes

General sources: https://developer.mozilla.org/en-US/docs/Web/API/HTMLElement, https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce

Capricorn
  • 2,061
  • 5
  • 24
  • 31
  • Thank you for your reply! If I use reduce, do I not need the forEach? How would I look at whether one cars data-price === data-original-price from another car? – Michael May 10 '18 at 21:05
  • No need for the forEach. The reduce iterates over the list of cars and pushes all matching cars into the *acc* array which will be returned from the reduce method. Please see the adjusted answer-code on how to get hold of other cars in the cars array – Capricorn May 10 '18 at 21:16
  • Ah okay. I see you added another parameter cars to reduce function? So if I wanted to check if car.data("price") == originalPrice of other car...I would check car.data("price") == cars.data("originalPrice")? – Michael May 10 '18 at 21:24
  • Unfortunately this was not clearly stated in your question. This requires an additional loop over the whole cars array within the *reduce* function. You can use forEach for that. – Capricorn May 10 '18 at 22:04
  • I really appreciate your help! I've updated the post with clearer requirements. Hopefully it makes more sense now! – Michael May 10 '18 at 22:47
  • Hi Michael. Based on your requirements you need to have two nested iterations over your cars array. This is necessary, if for each car in the list you want to check whether there is another car in the list with matching criteria. If you experience bad performance on that, you might have to perform the calculation on your server rather than at the browser. In this scenario performance-wise it does not matter whether you're using reduce or filter – Capricorn May 11 '18 at 11:06
  • Hi! Thank you! Are you able to look at the updates I've made? I updated the post too. – Michael May 11 '18 at 19:56
  • @Capricorn If for each car in the list the goal is to find if there is another then it would be wise to have a HashTable or a Set to avoid O(N^2) complexity. – FrenchMajesty May 20 '18 at 01:20
  • @FrenchMajesty: yes, one could do so to shorten the access times. This data structure however has to be build first and requires more memory (ref. https://stackoverflow.com/questions/1898161/memory-vs-performance). So it depends on ones personal preferences or intensive testing is required to figure out what's "best". See fabbb's answer below for an alternative approach. – Capricorn May 20 '18 at 09:39
5

I'd approach this problem quite differently. To get you started, the following solution should set you on the right path. Based on the dataset provided, it should also meet all (or most) of your requirements. 

const carsUniq = new Map()

cars.forEach($car => {
  const cKeys = $car.data()
  const carAttrsId = [    
    cKeys.dropoffLocationId,
    cKeys.locationId,
    cKeys.type,
    cKeys.vehicleExample
  ].join('')

  const sCar = carsUniq.get(carAttrsId)
  if (!sCar) {
    carsUniq.set( carAttrsId, cKeys )
  } else {
    for(const c in sCar) {
      if ( !sCar[c] && cKeys[c] ) sCar[c] = cKeys[c]
    }
  }
})

--

How does it work?

  1. Create a Map for tracking cars.
  2. Determine if a car is a duplicate by referencing specific car props to carAttrsId. [O(1) lookup]
  3. If a car is found in the Map, it must be a duplicate, so we combine the datasets into one normalized object.
  4. The end result is carsUniq.values() is an array like object of unique cars.

--

Based on your dataset carsUniq will contain 3 unique cars:

"SX-34.0910834--118.352194SX-34.0910834--118.352194ICARChevrolet Cruze" => {…}
"ZR-34.1958--118.3489ZR-34.1958--118.3489IDARToyota Corolla" => {…}
"FX-34.0629025--117.6140867FX-34.0629025--117.6140867SCAR" => {…}

--

Update - improved previous code and added feature to convert items to li elements as requested.

const carsUniq = new Map()

cars.forEach($car => {
  const cKeys = $car.data()
  const { dropoffLocationId, locationId, type, vehicleExample } = cKeys
  const carAttrsId = dropoffLocationId + locationId + type + vehicleExample;

  const sCar = carsUniq.get(carAttrsId)
  if (!sCar) {
    carsUniq.set( carAttrsId, cKeys )
  } else {
    for(const c in sCar) {
      if ( !sCar[c] && cKeys[c] ) sCar[c] = cKeys[c]
    }
  }
})

const dasherizedCarKeys = new Map()
const dasherizedData = str => {
  const k = dasherizedCarKeys.get(str)
  if (!k) {
    dasherizedCarKeys.set(str, 
       'data-' + str.replace(/([a-zA-Z])(?=[A-Z])/g, '$1-').toLowerCase())
  }
  return k
}

carsUniq.forEach(car => {
  const tCar = {}
  const carKeys = Object.keys(car).map(dasherizedData)
  for (const c in car) {
    tCar[dasherizedCarKeys.get(c)] = car[c]
  }
  $('<li>').attr(tCar).appendTo("#output")
})

Output: 

<li data-vehicle-example="Chevrolet Cruze" data-original-price="180.15" data-price="180.15" data-type="ICAR" data-dropoff-location-id="SX-34.0910834--118.352194" data-location-id="SX-34.0910834--118.352194"></li>
<li data-vehicle-example="Toyota Corolla" data-price="301.43" data-type="IDAR" data-dropoff-location-id="ZR-34.1958--118.3489" data-location-id="ZR-34.1958--118.3489"></li>
<li data-price="198.81" data-type="SCAR" data-partner-code="FX" data-dropoff-location-id="FX-34.0629025--117.6140867" data-location-id="FX-34.0629025--117.6140867"></li>
MrPizzaFace
  • 7,807
  • 15
  • 79
  • 123
  • Hi Fabb! Thanks for your post :) I'm running through the code now...I like this approach a lot, how can I edit this to return the actual
  • html instead of object info in the array?
    • – Michael May 11 '18 at 20:54
  • You would create `li` elements from your templating library, i.e. on the front-end, i.e. something like Angular, React, Vue, etc... That's outside the scope of this question. – MrPizzaFace May 11 '18 at 21:09
  • Hmmm I like how fast this is. However, my main goal is to combine the information from each matched element into one listing while modifying the existing cars array. Are you able to modify your answer? Sorry if it wasn't clear. – Michael May 12 '18 at 05:27
  • Yeah, you simply reassign it like this: cars = [ ...carsUniq.values() ]; – MrPizzaFace May 12 '18 at 16:01
  • Sorry, what line would I reassign? Thank you!! – Michael May 12 '18 at 16:08
  • See my update for the code to create the li items from the unique cars array. – MrPizzaFace May 13 '18 at 03:28
  • Thanks for your update. Would you be able to start a private chat with me? I'd like to show you exactly what I'm trying to achieve. I think there may be a miscommunication with one of my requirements. – Michael May 13 '18 at 14:33
  • I can’t chat today. Just update your question with more code. I’m sure you just need to alter its application slightly. – MrPizzaFace May 13 '18 at 15:38
  • What’s the UL class and id where the cars are displayed? – MrPizzaFace May 13 '18 at 15:41
  • No worries. I really appreciate your help! I updated my post with some more information. Hopefully it's a bit clearer now. Thank you!! – Michael May 13 '18 at 21:13
  • 1
    Your latest update shows a completely different cars array. What exactly is the problem you’re having? I can’t give you exact working code without being able to replicate your exact environment. The code I provided can still be adopted to solve your question. If you want exact working code to your spec you should create a codepen or jsbin to replicate. Also it’s polite to upvote and accept any solution which is helpful. Lastly StackOverflow is meant to help guide you, not do your work for you. If you can’t figure it out with help, you may need to hire someone who can. – MrPizzaFace May 14 '18 at 01:05
  • Thanks for your reply. I updated the post to provide actual array data rather than example data. The exact problem that I am having is around performance. The code that I have in my post matches the listings together and all the front-end updates are correct. However, it's performing slowly though. I really appreciate your help and will work on putting together a codepen. – Michael May 14 '18 at 01:16
  • Do you think using reduce and forEach together could be causing the slow down? – Michael May 14 '18 at 01:31
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/170972/discussion-between-michael-and-fabbb). – Michael May 14 '18 at 02:53