array queue, two implementations

array-queue.js

// 12-13 April 2024
// array queue

// first implementation uses a single array and deletes slots on "pull", while
// using "push" to append new items.

// second implementation uses a single array but uses "splice" for both "push"
// and "pull" commands, the benefit being we don't have to manage empty slots;
// however, splice results in the array indexes being shuffled internally...

// 16 April 2024
// third impl uses delete again to avoid the internal index shuffling and tracks
// the count of non-empty slots as the length of the queue array minus the
// offset index of the first non-empty slot.


// But first some exploratory tests on array methods...

;(function () {
  console.group("array methods");

  var a = ['p'];
  console.log(delete a[0]);
  /* true */
  console.log(a);
  /* [<empty slot>] */
  console.log(0 in a)
  /* false */
  console.log(a.push(2));
  /* 2 */
  console.log(a);
  /* [ <1 empty slot>, 2 ] */
  console.log(a.push('another one'));
  /* 3 */
  console.log( a );
  /* [ <1 empty slot>, 2, "another one" ] */
  console.log(delete a[a.length - 1]);
  /* 3 */
  console.log( a );
  /* [ <1 empty slot>, 2, <1 empty slot> ] */
  console.log("length:", a.length);
  /* length: 3 */

  var b = a.filter((v, i) => { console.warn("i:", i); return true; });
  /* i: 1 */
  console.log( b );
  /* [ 2 ] */
  a.some((v, i) => { console.warn("some i:", i ); return false; })
  /* some i: 1 */
  a.every((v, i) => { console.warn("every i:", i ); return true; })
  /* every i: 1 */
  var r = a.reduce((a, v, i) => {
    console.warn("reduce [v,i]:", [v,i]);
    return i;
  }, {});
  /* reduce [v,i]: Array [ 2, 1 ] */
  console.log( r );
  /* 1 */

  var c = a.map((v, i) => { console.log("map i:", i); return i; });
  /* map i: 1 */
  console.log( c );
  /* [ <1 empty slot>, 1, <1 empty slot> ] */

  c.forEach(function (value, index) {
    console.log("forEach:", [value, index])
  });
  /* forEach: Array [ 1, 1 ] */

  var i = 0;
  for (var i = 0; i < c.length; i++) {
    console.log(i, i in c);
  }
  /* 0 false */
  /* 1 true */
  /* 2 false */

  console.groupEnd("array methods");
})();


;(function () {
  console.group("delete slots");

  // 13 April 2024
  // Now that we know all that, we can make a "queue" out of an array
  // where we only push new items and pull from the first non-empty slot.

  function Q(value, ...rest) {
    var v = Array.isArray(value)
      ? [...value]
      : Object(value).valueOf() === value
        ? [value]
        : [];

    var q = v.concat(...rest);

    return {
      push(v) {
        console.log("push");

        if (Object(v).valueOf() === v) {
          q.push(v);
        }

        return this.size();
      },
      pull() {
        console.log("pull");

        for (var i = 0; i < q.length; i++) {
          if (i in q) {
            var v = q[i];

            delete q[i];

            return v;
          }
        }

        if (/* this.size() == 0 && */ q.length > 0) {
          console.log("trim after pull");
          this.trim();
        }
      },
      size() {
        console.log("size");

        var size = 0;

        for (var i = 0; i < q.length; i++) {
          if (i in q) {
            size = size + 1;
          }
        }

        return size;
      },
      trim() {
        console.log("trim");

        return (q = q.filter(_ => true)).length;
      }
    }
  }


  Q(1,2,3);
  Q(['a', 'b', 'c']);
  Q('x');
  Q({});
  Q();
  Q(null);
  Q(0);

  var test = Q(['foo', 'bar', 'baz']);
  console.log(test.size());
  /* 3 */

  console.log(test.push('quux'));
  /* 4 */
  // console.log(test.size());
  /* 4 */

  console.log(test.pull());
  /* "foo" */
  // console.log(test.size());
  /* 3 */

  console.log(test.pull());
  /* "bar" */
  // console.log(test.size());
  /* 2 */

  console.log( test.trim() );
  /* 2 */
  console.log(test.pull());
  /* "baz" */
  // console.log(test.size());
  /* 1 */

  console.log(test.push());
  // console.log(test.size());
  /* 1 */

  console.warn(test.pull());
  /* "quux" */
  // console.log(test.size());
  /* 0 */

  console.log(test.pull() === void 0);
  test.pull();
  test.push('o');
  test.pull();
  test.pull('k');
  test.pull();
  test.size();

  console.groupEnd("delete slots");
})();



;(function () {
  console.group("splice");

  // 13 April 2004
  // alternatively, we can use splice instead of delete so we don't have
  // to loop or manage empty slots...

  var d = ['a', 'b', 'c'];

  // push or append new value
  d.splice(d.length, 1, "new value");
  console.log( d );
  /* [ "a", "b", "c", "new value" ] */

  // pull first value (note that splice returns an array of removed values)
  console.warn( d.splice(0, 1)[0] );
  console.log( d );
  /* [ b", "c", "new value" ] */

  function Q(value, ...rest) {
    var a = Array.isArray(value)
      ? [...value]
      : Object(value).valueOf() === value
        ? [value]
        : [];

    var q = a.concat(...rest);

    var o = Object.defineProperties({}, {
      "push": {
        value (v) {
          console.log("push");

          if (Object(v).valueOf() === v) {
            q.splice(q.length, 1, v);
          }

          return q.length;
        }
      },
      "pull": {
        value () {
          console.log("pull");

          return (0 in q)
            ? { value: q.splice(0, 1)[0], done: false}
            : { value: void 0, done: true };
        }
      },
      "length": {
        get() { return q.length; }
      },
      "size" : {
        value () { return q.length; }
      },
      "clear" : {
        value () { return q.length = 0; }
      }
    });

    return Object.freeze(o);
  }


  Q(1,2,3);
  Q(['a', 'b', 'c']);
  Q('x');
  Q({});
  Q();
  Q(null);
  Q(0);

  var test = Q(['foo', 'bar', 'baz']);
  console.log(test.size());
  /* 3 */

  console.log(test.push('quux'));
  /* 4 */
  console.log(test.size());
  /* 4 */

  console.log(test.pull().value);
  /* "foo" */
  console.log(test.size());
  /* 3 */

  console.log(test.pull().value);
  /* "bar" */
  console.log(test.size());
  /* 2 */

  console.log(test.pull().value);
  /* "baz" */
  console.log(test.size());
  /* 1 */

  console.log(test.push());
  console.log(test.size());
  /* 1 */

  console.warn(test.pull().value);
  /* "quux" */
  console.warn(test.size());
  /* 0 */

  console.log(test.pull().value === void 0);

  console.dir(test.pull());
  test.push('a');
  test.push('b');
  console.dir(test.pull());
  test.push('c');
  test.push('d');
  console.log(test.size());
  console.log(test.length);

  console.log(test.clear());

  test.length = 9 && test.length;

  console.groupEnd("splice");
})();


;(function () {
  console.group("delete variant");

  // 16 April 2024
  // In this version, we'll remove all empty slots (and undefined, null, and NaN
  // values) from the incoming array, and track the current count of non-empty
  // slots in the array as an offset value (where offset is the index of the first
  // non-empty slot in the array in ascending order). The incrementing offset and
  // resizing an array with only non-empty slots happens in the `pull()` method.

  function Q(value, ...rest) {
    var v = Array.isArray(value)
      ? [...value]
      : Object(value).valueOf() === value
        ? [value]
        : [];

    // trim out all empty slots initially

    var q = v.concat(...rest)
      // filter out empty slots, undefined, null, and NaN
      .filter(_ => Object(_).valueOf() === _);

    // track the first non-empty index

    var offset = 0;

    return {
      pull() {
        console.log("pull");

        while (!(offset in q) && offset < q.length) {
          offset += 1;
        }

        var v = q[offset];

        if (offset in q) {
          delete q[offset];

          offset += 1;
        }

        if (offset && offset == q.length) {
          console.log("resize");

          offset = q.length = 0;
        }

        return v;
      },
      push(v) {
        console.log("push");

        if (Object(v).valueOf() === v) {
          q.push(v);
        }

        // number of non-empty slots

        return q.length - offset;
      },
      size() {
        console.log("size");

        return q.length - offset;
      }
    }
  }


  Q(1,2,3);
  Q(['a', 'b', 'c']);
  Q('x');
  Q({});
  Q();
  Q(null);
  Q(0);

  var test = Q(['foo', 'bar', 'baz']);

  console.log(test.size());
  /* 3 */

  console.log(test.push('quux'));
  /* 4 */
  console.log(test.size());
  /* 4 */

  console.log(test.pull());
  /* "foo" */
  console.log(test.size());
  /* 3 */

  console.log(test.pull());
  /* "bar" */
  console.log(test.size());
  /* 2 */

  console.log(test.pull());
  /* "baz" */
  console.log(test.size());
  /* 1 */

  console.warn(test.push());
  /* 1 */
  console.log(test.size());
  /* 1 */

  console.warn(test.pull());
  /* "quux" */
  console.log(test.size());
  /* 0 */

  console.warn(test.pull() === void 0);
  /* true */

  console.log(test.pull());
  /* undefined */
  console.log(test.push('o'));
  /* 1 */

  console.warn(test.pull());
  /* o */
  console.log(test.push('k'));
  /* 1 */

  console.warn(test.pull());
  /* k */
  console.log(test.size());
  /* 0 */

  console.groupEnd("delete variant");
})();