How would you create Set.prototype.add() from scratch?

user_12471381 0
Viewed 113

On ECMAScript, it explains how you would create the add prototype.

The following steps are taken:

Let S be the this value.

If Type(S) is not Object, throw a TypeError exception.

If S does not have a [[SetData]] internal slot, throw a TypeError exception.

Let entries be the List that is the value of S’s [[SetData]] internal slot.

Repeat for each e that is an element of entries,

If e is not empty and SameValueZero(e, value) is true, then

Return S.

If value is −0, let value be +0.

Append value as the last element of entries.

Return S."

I am fairly new to JS and have no idea what this means. If I were to create a class such that

class mySet {
constructor(){
    this.set = {}
}
//adds a value to set
add(){
    
}

How would I proceed?

data-structures javascript
2 Answers

Here is a sample implementation. It's basically just following the steps outlined in the specs. I'm however not entirely sure what is empty means so (i'm treating it as undefined.)

To check for a negative zero you need to cheat and test for -Infinity or sth alike.

function isNegativeZero (x) {
  return 1 / x === -Infinity
}

function SameValueZero (a, b) {
    if (typeof a !== typeof b) return false

    if (typeof a === 'number') {
        if (Number.isNaN(a) && Number.isNaN(b)) return true;
        if (isNegativeZero(a) && b === 0) return true;
        if (isNegativeZero(b) && a === 0) return true;
        if (+a === +b) return true;
        return false
    }
    return a === b;
}


class MySet {
    constructor(){
        this[MySet.Symbols.SetData] = [];
    }

    //adds a value to set
    add(value){
        const S = this;
        
        if (typeof S !== 'object') throw new TypeError(`Type mismatch. Expected ${this} to be of type object`);

        const entries = this[MySet.Symbols.SetData];
        
        for (const e of entries) {
            if (typeof e !== 'undefined' && SameValueZero(e, value)) return S;
        }

        if (isNegativeZero (value)) value = 0;

        entries.push(value);

        return S;
    }
    toString() {
      return `MySet(${this[MySet.Symbols.SetData].length}) {${this[MySet.Symbols.SetData]}}`
    }
}
MySet.Symbols = {
    SetData: Symbol('SetData')
}


const mySet = new MySet();

mySet.add(1);
console.log(mySet + '');
mySet.add(1);
console.log(mySet + '');
mySet.add(NaN);
console.log(mySet + '');
mySet.add(NaN);
console.log(mySet + '');

user_14877560

Here's an idea. It doesn't work with undefined, because that value is used to indicate an empty space. It could work with undefined if a holey array was used instead, but that would have performance costs.

In this example the value is not appended as the last element of the array, instead it is appended in the place of the first empty space, to prevent needlessly expanding the array.

Of course, JavaScript code can't access internal slots, so a property is used here.

class MySet {
  setData = [];

  add(value) {
    if (!("setData" in this))
      throw new TypeError("add method called on incompatible Object");

    let firstEmptyIndex = -1;
    for (let i = 0; i < this.setData.length; i++) {
      const item = this.setData[i];
      if (firstEmptyIndex < 0 && item === undefined) {
        firstEmptyIndex = i;
        continue;
      }

      if ((typeof item === "number" && Number.isNaN(item) && typeof value === "number" && Number.isNaN(value)) || item === value) // Item already in the set
        return this;
    }
    
    if (firstEmptyIndex < 0)
      this.setData.push(value);
    else
      this.setData[firstEmptyIndex] = value;
    return this;
  }
}
user_92534140
Related