8

currently I am following a book and am severely confused and have tried understandng the following code several times. My first confusion is actually approaching the problem of comparing two objects a, and b. 

 function deepEqual(a, b) {
  if (a === b) return true;

  if (a == null || typeof a != "object" ||
      b == null || typeof b != "object")
    return false;

  var propsInA = 0, propsInB = 0;

  for (var prop in a)
    propsInA += 1;

  for (var prop in b) {
    propsInB += 1;
    if (!(prop in a) || !deepEqual(a[prop], b[prop]))
      return false;
  }

  return propsInA == propsInB;
}

var obj = {here: {is: "an"}, object: 2};
console.log(deepEqual(obj, obj));
// → true
console.log(deepEqual(obj, {here: 1, object: 2}));
// → false
console.log(deepEqual(obj, {here: {is: "an"}, object: 2}));
// → true
Muntasir Alam
  • 1,777
  • 2
  • 17
  • 26
  • typeof is used here to make sure you're comparing apples to apples. propsInX is used to count the number of props without comparing values; if the count is different, so to are the objects, whereas if you just compared `{a:1,b:2}` to `{a:1}` by looking at only the 2nd object, you'de get a false-positive. the alternative is to iterate both objects and compare; the counter removes the need for "double" iteration. – dandavis Jun 20 '16 at 19:28
  • If they aren't objects, and they aren't equal, then that evaluates to false (objects comparison is done based on reference value instead of object value - which is where the entire need to do this type of checking comes into play in the first place). Beyond that it just recurses through the properties if it is an object and there is a nested object. – Travis J Jun 20 '16 at 19:29
  • `!=` means "not equal". `typeof a != "object"` means a is not of type "object" – Juan Tomas Jun 20 '16 at 19:29

4 Answers4

3
function deepEqual(a, b) {
  if (a === b) return true;

First, we're checking if a and b are strictly equal (meaning, "referring to exactly the same thing"). Most things, such as strings and numbers, will pass this test if they are equal; objects are the exception, since two "identical" objects may not necessarily be the same object (they can just look the same).

  if (a == null || typeof a != "object" ||
      b == null || typeof b != "object")
    return false;

Then we're saying that if either of the two is not an object, and they did not pass the last test, then they cannot be the same. Again, objects are the exception here, so the remaining code will take care of the case where a and b are both objects.

  var propsInA = 0, propsInB = 0;

  for (var prop in a)
    propsInA += 1;

This code simply counts the number of properties of a.

  for (var prop in b) {
    propsInB += 1;
    if (!(prop in a) || !deepEqual(a[prop], b[prop]))
      return false;
  }

This code takes every property in b, and checks that a contains the same property with the same value. If a doesn't have a property that b has, or they are different, then the two objects cannot be equal.

  return propsInA == propsInB;
}

Finally, if a and b do not have the same number of properties, then they cannot be equal. However, if they do have the same number of properties, then a and b must be equal, since a has all the properties that b has, and only those.

Frxstrem
  • 38,761
  • 9
  • 79
  • 119
1

I'll walk you through it.

if (a === b) return true;

We check if these are the same thing, we'll come back to here later.

if (a == null || typeof a != "object" ||
      b == null || typeof b != "object")
    return false;

We check if one or neither of these things are objects are defined. We'll come back here too.

Keep these first two snippets in mind, they don't come into play until we call the function recursively.

var propsInA = 0, propsInB = 0;

These will be used to keep track of the number of properties in object A and B

for (var prop in a)
    propsInA += 1;

  for (var prop in b) {
    propsInB += 1;
    if (!(prop in a) || !deepEqual(a[prop], b[prop]))
      return false;
  }

  return propsInA == propsInB;
}

We have two for loops. The first one just loops through all properties in A (look up For...in syntax if you're unfamiliar), and for each it increments the variable propsInA.

The second loop does the same for B, but here it gets more complicated. First it checks if that property exists in A, or if deepequal returns true. This is where the first two snippets we examined come into play. The first snippet is used here to return true if the properties we give it are the same. The second snippet says "if we passed properties instead of functions, stop here". This is important because this function only needs to go on past here if its the initial invocation. All recursive invocations only need to use the first part. If either of these two return false, we return false to the initial invocation, because we know there was a difference between A and B.

return propsInA == propsInB;

We can't return true here, because we don't actually know if there is just less properties in B. Even though everything else appeared the same, we can't assume that they have the same amount of properties. This assures, as a final check, that we will only return true if the number of properties in A is equal to the number in B

Feel free to ask me to explain further.

master565
  • 805
  • 1
  • 11
  • 27
  • The first case, A has two counts. The second case is the reason why its recursive (I missed this at first). After it checks that a.bob = b.bob, it tries to check a.value, and when it sees that its an object, it passes by the first two snippets again, and in this new invocation it compares a.value with b.value. In this invocation propsInA is equal to 1, and propsInB is equal to 2 – master565 Jun 20 '16 at 19:50
  • I would suggest making two decently sized objects, and trying to follow the logic of the code. Make sure each invocation of the function has its own scope of variables. This is the best way to understand recursive functions – master565 Jun 20 '16 at 19:52
  • It is comparing something. Its just being compared from within deep equal, which will return true under certain conditions. The reason we need this line is because we need to not only see if an object has all the same properties, but also any nested objects (if a.property = {}). This must be done recursively. It may help to think of deepequal as 2 functions. Function 1 is the first 2 snippets, and function 2 is the rest. F1 checks if two properties are equal, and F2 is a recursive call to do the same on any nested object – master565 Jun 21 '16 at 00:43
  • Nope. Every time you call deepEqual from within itself, it creates a new scope where every variable has a new value. So on level 1, we have 2 properties. On level 2, we have 1 property. While the total is 3, this is unimportant. The amount of properties per level is what matters. – master565 Jun 21 '16 at 02:01
  • !(prop in a) says we will return false if the property doesn't even exist in a (we don't need to check if its equal if it isn't there). It's in the loop because we need to check all of the properties of b, check if they exist in a, and then check if they're equal to a. – master565 Jun 21 '16 at 15:55
  • It checks for property "x" in object "b", does a similar property "x" exist in object "a"? If not, then they aren't equal. If this property does exist in "a", we must then check that the property's value in "b" is equal to value of that property of "a". The reason there are two loops is that, if we ignoring the recursion for a second, want to compare the elements of two arrays, we would need two loops. Kind of like here http://stackoverflow.com/questions/14983575/compare-the-elements-of-two-arrays-by-id-and-remove-the-elements-from-the-one-ar – master565 Jun 21 '16 at 16:40
  • But that kind of solution won't work for you, because you're using objects not arrays. And objects can nest other objects, and that is why we use recursion. Don't feel bad if you don't understand, recursion is a tricky concept to wrap your head around, most people struggle with it at first. – master565 Jun 21 '16 at 16:41
  • Recursion is a problem that exists in all programming languages. I'm not sure of a great tutorial, just try googling the topic. If you don't think you need to understand why this kind of thing works, then maybe it's better for you to just accept that it works, use it, and move on. – master565 Jun 21 '16 at 17:04
0

On this function

  • First of, the function checks simply if the first parameter equals to the second one and then return true.
  • typeof a! = "object" - That check if the type of the parameters (a and b) are objects, if one of them is not an object, the function will end by returning false.
  • Then if it passed this condition (a and b are objects) it will continue to the next step- a loop that will go through the items on the objects (a and b), and will count them propsInA for a and propsInB for b accordingly.
  • The next step will be to check if there is no items on the parameter, if so it will return false
  • Otherwise the function will compare between propsInA and propsInB,if they are identical the function will end by returning true otherwise it will return false.
user3378165
  • 6,546
  • 17
  • 62
  • 101
  • Yes, this function will work with multiple nested items.About your second question: propsInA and propsInB must be 'ints' because they are **counters**, the function loops through the items of each parameter and adds each time +1 to the counter and then will compare between the counters (propsInA and propsInB). For example if a has 5 items, propsInA will be equal to 4 (because it's starting with 0) – user3378165 Jun 20 '16 at 19:49
0

Your algorithm behaves like this:

  1. If a and b are considered strictly equal, return true

    a and b are considered strictly equal if one of these applies:

    • They are the same primitive value, except NaN
    • They are +0 and -0 (or viceversa)
    • They are the same object (same reference).

    This is done using the strict equality comparison (===) operator.

  2. If either a or b or both are not considered objects, return false

    o is not considered object if one of these applies:

    • o is a primitive value
    • o belongs to the Object type but has an internal [[Call]] method. That is, is a callable object, e.g. a function or a HTML <object> element.
    • o is a non-callable non-standard exotic object whose implementation-defined returned by the typeof operator is different than "object"`.

    This is done using the typeof operator, which returns a string with the type of the value, except for null and maybe objects. Since typeof null === "object", a == null is checked.

  3. If a and b have the a different number of enumerable properties (taking into account both own and inherited ones), return false.

    This is counted by propsInA and propsInB.

  4. If b has an enumerable (own or inherited) property but a doesn't have a (non-enumerable or enumerable, own or inherited, not necessarily the same as b) property with the same name, return false.

    This is done iterating for (var prop in b) and checking prop in a.

  5. If b has an enumerable (own or inherited) property whose value is considered different by the deepEqual algorithm than the value of the same property in a, return false.

    This is done iterating for (var prop in b) and checking deepEqual(a[prop], b[prop]).

  6. Otherwise, return true.

I don't think it's a good algorithm. For example, it considers {}, Object.prototype and Object.create(null) to be all equal, but I wouldn't say so.

Oriol
  • 274,082
  • 63
  • 437
  • 513
  • @cresjoy `for (var prop in b)` iterates all enumerable properties of `b`. For each property name `prop`, it checks if `a` has a property with the same name (`prop in a`) and if their values `a[prop]` and `b[prop]` are considered equal. Conditional statements can evaluate any expression, not just compare variables with literals. – Oriol Jun 21 '16 at 00:22
  • @cresjoy `prop` is a variable whose value changes at each iteration of the `for...in` loop, becoming each enumerable property of `b`. For example, if `b = {a:1, b:2}`, then `for(var prop in b) { console.log(prop); }` will log `"a"` and `"b"` (in any order). And `a[prop]` uses the value stored in the variable `prop` to access the property in `a` with that name. – Oriol Jun 21 '16 at 00:34
  • See [JavaScript property access: dot notation vs. brackets?](http://stackoverflow.com/questions/4968406/javascript-property-access-dot-notation-vs-brackets) – Oriol Jun 21 '16 at 00:39
  • Yes, if you have `{value: 3, type: { value:10}}`, `prop` will iterate `"value"` and `"type"`. It will compare if both `a["value"]` and `b["value"]` are `3`, and if both `a["type"]` and `b["type"]` are `{value:10}`. To check the later, the function will recursively be called again, checking if `a["type"]["value"]` and `b["type"]["value"]` are `10`. – Oriol Jun 21 '16 at 00:47
  • No, you want to return false whenever you find a property which is not shared by `a` and `b`. But if you find a common property, you must continue iterating the other properties, can't return `true` directly. The final `return propsInA == propsInB` will return `true` if `a` and `b` have the same number of properties (and they are the same, otherwise the function would have returned `false` earlier). – Oriol Jun 21 '16 at 01:02
  • Yes, `prop in a` returns `true` if `a` has a property (own or inherited) whose name is the string stored in the variable `prop`. – Oriol Jun 21 '16 at 15:56
  • I think I am still confused about !(prop in a). Is this saying: We loop through b, and if a[prop] doesent exist at the same time as b[prop] return false? I.E we arent even checking equality here. We are jut checking if the number of types match up? – Muntasir Alam Jun 21 '16 at 16:39
  • @cresjoy Objects can inherit properties, e.g. `'toString' in {}` is inherited from `Object.prototype`. And yes, `prop in a` only checks existence. The comparison of values is done in `deepEqual(a[prop], b[prop])` – Oriol Jun 21 '16 at 16:48
  • @cresjoy Yes, `!(prop in a)` will be `true` if `prop` is not in `a`, so then `return false` will run. – Oriol Jun 21 '16 at 17:02
  • No, because you want to check all properties, so you need a loop which iterates the properties. – Oriol Jun 21 '16 at 19:06