2
\$\begingroup\$

I didn't find an implementation on CR of the circular doubly linked list, using generators. Hence, I tried it myself.

Description

The class Deck represents a circular doubly linked list, only referencing the head node. The tail node is derived as head.previous. The length of the list is evaluated from iterating the nodes. Adding, removing and peeking from either side of the list takes \$O(1)\$ time complexity, while it takes \$O(N)\$ time complexity in the middle.

Questions

  • Is this class usable, does it comply to collection standards and conventions?
  • Are the class, method, property names stating clearly what they do?
  • Is the use of comments optimal, too verbose or still insufficient?
  • I don't have much experience with generators and iterators. Is this idiomatic Javascript?

Code

A deck chains nodes to form a collection.

// A node is a value container, linked to its previous and next node.
// Because of its circular nature, previous and next will never be null.
// A head's previous node is the tail and the tail's next node is the head.
// A sole node has a self reference both previous as next.
class Node {

  // Constructor specifying the contained value.
  constructor(value) {
    this.value = value;
    this.previous = this.next = this;
  }

  // The specified node gets inserted after this node.
  // @returns this node.
  append(node) {
    node.next = this.next;
    node.previous = this;
    this.next.previous = node;
    this.next = node;
    return this;
  }

  // The specified node gets inserted before this node.
  // @returns this node.
  prepend(node) {
    node.previous = this.previous;
    node.next = this;
    this.previous.next = node;
    this.previous = node;
    return this;
  }

  // This node removes itself from its siblings, but keeps
  // the references in case it gets restored. 
  // The value remains untouched.
  // @returns this node.
  cloack() {
    this.previous.next = this.next;
    this.next.previous = this.previous;
    return this;
  }

  // This node removes itself fomr its siblings, and clears
  // all references to its siblings.
  // The value gets reset to null.
  // @returns this node.
  remove() {
    this.cloack();
    this.previous = this.next = this;
    this.value = null;
    return this;
  }
}

The deck itself with its head node.

// A deck is a collection of values with support to add and remove
// values at both sides as well as in the middle.
// Because its a doubly linkes list, adding and removing values at
// the sides has O(1) time complexity, while in middle O(n).
// Because of its circular nature, only the head is stored, the tail
// can be derived by taking head.previous.
class Deck {

  // Constructor optionally specifying the initial values.
  constructor(values = null) {
    this.head = null;
    if (values !== null) {
      for (const value of values) {
        this.push(value);
      }
    }
  }

  // Inserts a value at the tail.
  // @returns this deck.
  push(value) {
    const node = new Node(value);
    if (this.empty()) {
      this.head = node;
    } else {
      this.tail.append(node);
    }
    return this;
  }

  // Inserts a value at the head.
  // @returns this deck.
  unshift(value) {
    const node = new Node(value);
    if (this.any()) {
      this.head.prepend(node);
    }
    this.head = node;
    return this;
  }

  // Inserts a value at the specified index.
  // @returns a boolean indicating success; no success when out of bounds.
  insertAt(index, value) {
    const node = new Node(value);
    if (index === 0) {
      this.unshift(value);
      return true;
    } else {
      const previous = this.entryAt(index - 1);
      if (previous) previous.node.append(node);
      return previous !== null;
    }
  }

  // Removes the value at the tail.
  // @returns the value at the tail; or undefined when empty.
  pop() {
    if (this.empty()) return undefined;
    const tail = this.tail;
    const becomesEmpty = this.head === tail;
    const value = tail.value;
    tail.remove();
    if (becomesEmpty) this.head = null;
    return value;
  }

  // Removes the value at the head.
  // @returns the value at the head; or undefined when empty.
  shift() {
    if (this.empty()) return undefined;
    const newHead = this.head.next === this.head ? null : this.head.next;
    const value = this.head.value;
    this.head.remove();
    this.head = newHead;
    return value;
  }

  // Removes the value at the specified index.
  // @returns the value at the specified index; or undefined when out of bounds.
  removeAt(index) {
    if (index === 0) {
      return this.shift();
    } else {
      const entry = this.entryAt(index);
      if (entry === null) return undefined;
      const value = entry.node.value;
      entry.node.remove();
      return value;
    }
  }

  // Removes the first occurence of the specified value.
  // @returns a boolean indicating whether a value was removed.
  remove(value) {
    var entry = this.entry(value);
    if (entry === null) return false;
    if (this.head === entry.node) {
      this.shift();
    } else {
      entry.node.remove();
    }
    return true;
  }

  // Removes all values from the deck.
  // @returns this deck.
  clear() {
    for (const node of this.nodes()) {
      node.remove();
    }
    this.head = null;
    return this;
  }

  // Checks whether the specified value is contained.
  // @returns a boolean indicating whether the specified value is contained.
  contains(value) {
    return this.indexOf(value) > -1;
  }

  // Gets the index of the first occurence of the specified value.
  // @returns the index of the first occurence; or -1 when not found.
  indexOf(value) {
    var entry = this.entry(value);
    return entry === null ? -1 : entry.index;
  }

  // Gets the value at the head.
  // @returns the value at the head; or undefined when empty.
  first() {
    return this.any() ? this.head.value : undefined;
  }

  // Gets the value at the tail.
  // @returns the value at the tail; or undefined when empty.
  last() {
    return this.any() ? this.tail.value : undefined;
  }

  // Gets the value at the specified index.
  // @returns the value at the specified index; or null when out of bounds.
  peek(index) {
    const entry = this.entryAt(index);
    return entry === null ? null : entry.node.value;
  }

  // Gets the entry at the specified index.
  // @returns the entry at the specified index; or null when out of bounds.
  entryAt(index) {
    return (index < 0) ? null : [...this.entries()].find(n => n.index === index) || null;
  }

  // Gets the entry matching the first occurence of the specified value.
  // @returns the entry matching the first occurence of the specified value;
  // or null when out of bounds.
  entry(value) {
    return [...this.entries()].find(n => n.node.value === value) || null;
  }

  // Maps the values given the specified selector.
  // @returns the values mapped given the specified selector.
  map(selector) {
    return this.values.map(selector);
  }

  // Finds the first value given the specified condition.
  // @returns the first value given the specified condition.
  find(condition) {
    return this.values.find(condition);
  }

  // Filters the values given the specified condition.
  // @returns the values filtered given the specified condition.
  filter(condition) {
    return this.values.filter(condition);
  }

  // Reduces the values given the specified aggregator and seed.
  // @returns the values reduced given the specified aggregator and seed.
  reduce(aggregator, seed) {
    return this.values.reduce(aggregator, seed);
  }

  // Gets whether at least one value matches the condition.
  // @returns a boolean indicating at least one value matches the condition;
  // false when empty.
  some(condition) {
    return this.values.some(condition);
  }

  // Gets whether all values matche the condition.
  // @returns a boolean indicating all values match the condition;
  // true when empty.
  every(condition) {
    return this.values.every(condition);
  }

  // Gets whether the deck contains any values.
  // @returns a boolean indicating whether any values are contained.
  any() {
    return this.head !== null;
  }

  // Gets whether the deck is empty.
  // @returns a boolean indicating whether the deck is empty.
  empty() {
    return !this.any();
  }

  // Iterates the deck.
  // @returns an iterator over the values.
  *[Symbol.iterator]() {
    for (const node of this.nodes()) 
      yield node.value;
  }

  // Iterates the nodes.
  // @returns an iterator over the nodes.
  *nodes() {
    for (const entry of this.entries()) 
      yield entry.node;
  }

  // Iterates the entries.
  // @returns an iterator over the entries.
  *entries() {
    if (this.any()) {
      let i = 0;
      let node = this.head;
      do {
        yield { index: i++, node: node };
        node = node.next;
      } while (node !== this.head);
    }
  }

  // Gets the number of values.
  // @returns the number of values.
  get length() {
    return this.values.length;
  }

  // Gets the values as array.
  // @returns the values as array.
  get values() {
    return Array.from(this);
  }

  // Gets the tail.
  // @returns the tail.
  get tail() {
    return this.any() ? this.head.previous : null;
  }
}

And some unit tests to show the behavior.

function print(deck) {
  console.log("// values: " + [...deck]);
  console.log("// first: " + deck.first());
  console.log("// last: " + deck.last());
  console.log("// map: " + deck.map(n => n * 10));
  console.log("// filter: " + deck.filter(n => n > 1));
  console.log("// reduce: " + deck.reduce((m, n) => m += n, 0));
  console.log("// any: " + deck.any());
  console.log("// some: " + deck.some(n => n > 1));
  console.log("// every: " + deck.every(n => n > 1));
  console.log("// --------------------");
}

var deck = new Deck();
print(deck);
// values:
// first: undefined
// last: undefined
// map:
// filter:
// reduce: 0
// any: false
// some: false
// every: true
// --------------------

deck.push(1);
deck.push(2);
deck.push(3);
deck.unshift(0);
deck.unshift(-1);
deck.insertAt(0, -2);
deck.insertAt(deck.length, 4);
print(deck);

// values: -2,-1,0,1,2,3,4
// first: -2
// last: 4
// map: -20,-10,0,10,20,30,40
// filter: 2,3,4
// reduce: 7
// any: true
// some: true
// every: false
// --------------------

deck.pop();
deck.shift();
deck.removeAt(1);
deck.remove(-1);
print(deck);

// values: 1,2,3
// first: 1
// last: 3
// map: 10,20,30
// filter: 2,3
// reduce: 6
// any: true
// some: true
// every: false
// --------------------

deck.clear();
print(deck);
// values:
// first: undefined
// last: undefined
// map:
// filter:
// reduce: 0
// any: false
// some: false
// every: true
// --------------------
\$\endgroup\$
  • 1
    \$\begingroup\$ Very comprehensive, but the class syntax breaks the fundamental OO design principle of encapsulation, it has none. Eg list = new Deck([1,2]); list.tail.next = list.tail; [...list]; will crash the page, will not throw, making it too dangerous to use. You need to protect the Node links. \$\endgroup\$ – Blindman67 Sep 1 '19 at 9:08
  • 1
    \$\begingroup\$ # isn't implemented at the moment. You'll have to use private Maps inside a function closure to do something like that. \$\endgroup\$ – FreezePhoenix Sep 1 '19 at 11:03
  • 2
    \$\begingroup\$ Naming is confusing. Deck usually means something like a deck of cards. OTOH "a collection of values with support to add and remove values at both sides" is a deque (aka Double Ended Queue). \$\endgroup\$ – vnp Sep 1 '19 at 17:45
1
\$\begingroup\$

As @BlindMan67 commented, the Nodes themselves are not protected. Apart from that, I don't see many glaring problems. Below is a short example of how to fix that (However, it does use a function closure, which may not be your style)

const [Deck, Node] = (function() {
    // Class definition for nodes, not included
    const NodeHeads = new Map(),
          NodeTails = new Map();
    // A deck is a collection of values with support to add and remove
    // values at both sides as well as in the middle.
    // Because its a doubly linkes list, adding and removing values at
    // the sides has O(1) time complexity, while in middle O(n).
    // Because of its circular nature, only the head is stored, the tail
    // can be derived by taking head.previous.
    class Deck {

        // Constructor optionally specifying the initial values.
        constructor(values = null) {
            NodeHeads.set(this, null);
            if (values !== null) {
                for (const value of values) {
                    this.push(value);
                }
            }
        }

        // Inserts a value at the tail.
        // @returns this deck.
        push(value) {
            const node = new Node(value);
            if (this.empty()) {
                NodeHeads.set(this, node);
            } else {
                NodeTails.get(this).append(node);
            }
            return this;
        }
        get head() {
            return NodeHeads.get(this).value;
        }
        // ...etc...

    }
    return [Deck, Node]
})();
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ It's indeed not my preferred style, but it's a neat trick nevertheless to workaround this encapsulation problem. \$\endgroup\$ – dfhwze Sep 1 '19 at 11:15
  • 1
    \$\begingroup\$ @dfhwze It wasn't mine either for quite a while until I realized it was the most reasonable of most of them to me. Most other methods seemed kinda hacky. Now, I'll be honest with you, it would be kinda asking for the same trouble BlindMan mentioned if you return the Node class. Instead, I wouldn't return it, and would just leave it as is with the JSDoc. \$\endgroup\$ – FreezePhoenix Sep 1 '19 at 11:16
  • 1
    \$\begingroup\$ Perhaps I should post an updated version of this class once # is implemented :p \$\endgroup\$ – dfhwze Sep 1 '19 at 11:17
  • 1
    \$\begingroup\$ Yes, you could do that. I'm currently working on a language that is very very similar to JS (Not FreezeFlame... I forgot about that one tbh...), I actually didn't think about the proposed functionality for #, i instead set it to this... I might make it a macro in the future. \$\endgroup\$ – FreezePhoenix Sep 1 '19 at 11:18
  • 1
    \$\begingroup\$ @dfhwze That's what it ends up being in the end anyhow xd \$\endgroup\$ – FreezePhoenix Sep 2 '19 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.