algorithms – How to test large tree data structure shape properly?

Here is a sort of B+tree data structure:

class KeyValue {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
}

class Node {
  constructor(capacity) {
    // Mimic fixed-size array (avoid accidentally growing it)
    this.children = Object.seal(Array(capacity).fill(null));
    this.childCount = 0; // Number of used slots in children array
    this.treeSize = 0
    // The algorithm relies on that fact that both KeyValue & Node have a key property:
    this.key = null; // Here it is a property for supporting a search
    // Maintain back-link to parent.
    this.parent = null;
    // Per level in the tree, maintain a doubly linked list
    this.prev = this.next = null;
  }
  updateTreeSize(start, end, sign=1) {
    let sum = 0;
    if (this.isLeaf()) {
        sum = end - start;
    } else {
        for (let i = start; i < end; i++) sum += this.children(i).treeSize;
    }
    if (!sum) return;
    sum *= sign;
    // Apply the sum change to this node and all its ancestors
    for (let node = this; node; node = node.parent) {
        node.treeSize += sum;
    }
  }
  setCapacity(capacity) {
    if (capacity < 1) return;
    // Here we make a new array, and copy the data into it
    let children = Object.seal(Array(capacity).fill(null));
    for (let i = 0; i < this.childCount; i++) children(i) = this.children(i);
    this.children = children;
  }
  isLeaf() {
    return !(this.children(0) instanceof Node);
  }
  index() {
    return this.parent.children.indexOf(this);
  }
  updateKey() {
    for (let node = this; node; node = node.parent) {
      node.key = node.children(0).key;
    }
  }
  wipe(start, end) {
    this.updateTreeSize(start, end, -1);
    this.children.copyWithin(start, end, this.childCount);
    for (let i = this.childCount - end + start; i < this.childCount; i++) {
      this.children(i) = null;
    }
    this.childCount -= end - start;
    // Reduce allocated size if possible
    if (this.childCount * 2 <= this.children.length) this.setCapacity(this.children.length / 2);
    // Update key if first item changed
    if (start === 0 && this.childCount > 0) this.updateKey();
  }
  moveFrom(neighbor, target, start, count = 1) {
    // Note: `start` can have two meanings:
    //   if neighbor is null, it is the value/Node to move to the target
    //   if neighbor is a Node, it is the index from where value(s) have to be moved to the target
    // Make room in target node
    if (this.childCount + count > this.children.length) this.setCapacity(this.children.length * 2);
    this.children.copyWithin(target + count, target, Math.max(target + count, this.childCount));
    this.childCount += count;
    if (neighbor !== null) {
      // Copy the children
      for (let i = 0; i < count; i++) {
        this.children(target + i) = neighbor.children(start + i);
      }
      // Remove the original references
      neighbor.wipe(start, start + count);
    } else {
      this.children(target) = start; // start is value to insert
    }
    this.updateTreeSize(target, target + count, 1);
    // Set parent link(s)
    if (!this.isLeaf()) {
      for (let i = 0; i < count; i++) {
        this.children(target + i).parent = this;
      }
    }
    // Update key if first item changed
    if (target === 0) this.updateKey();
  }
  moveToNext(count) {
    this.next.moveFrom(this, 0, this.childCount - count, count);
  }
  moveFromNext(count) {
    this.moveFrom(this.next, this.childCount, 0, count);
  }
  basicRemove(index) {
    if (!this.isLeaf()) {
      // Take node out of the level's linked list
      let prev = this.children(index).prev;
      let next = this.children(index).next;
      if (prev) prev.next = next;
      if (next) next.prev = prev;
    }
    this.wipe(index, index + 1);
  }
  basicInsert(index, value) {
    this.moveFrom(null, index, value);
    if (value instanceof Node) {
      // Insert node in the level's linked list
      if (index > 0) {
        value.prev = this.children(index - 1);
        value.next = value.prev.next;
      } else if (this.childCount > 1) {
        value.next = this.children(1);
        value.prev = value.next.prev;
      }
      if (value.prev) value.prev.next = value;
      if (value.next) value.next.prev = value;
    }
  }
  pairWithSmallest() {
    return this.prev && (!this.next || this.next.childCount > this.prev.childCount) ?
      (this.prev, this) : (this, this.next);
  }
  toString() {
    return "(" + this.children.map(v => v ?? "-").join() + ")";
  }
}

class Tree {
  constructor(nodeCapacity = 32) {
    this.nodeCapacity = nodeCapacity;
    this.base = new Node(1);
    this.first = this.base; // Head of doubly linked list at bottom level
  }
  locate(key) {
    let node = this.base;
    let low;
    while (true) {
      // Binary search among keys
      low = 1;
      let high = node.childCount;
      while (low < high) {
        let index = (low + high) >> 1;
        if (key >= node.children(index).key) {
          low = index + 1;
        } else {
          high = index;
        }
      }
      low--;
      if (node.isLeaf()) break;
      node = node.children(low);
    }
    if (low < node.childCount && key > node.children(low).key) return (node, low + 1);
    return (node, low);
  }
  get(key) {
    let (node, index) = this.locate(key);
    if (index < node.childCount) {
      let keyValue = node.children(index);
      if (keyValue.key === key) return keyValue.value;
    }
  }
  set(key, value) {
    let (node, index) = this.locate(key);
    if (index < node.childCount && node.children(index).key === key) {
      // already present: update the value
      node.children(index).value = value;
      return;
    }
    let item = new KeyValue(key, value); // item can be a KeyValue or a Node
    while (node.childCount === this.nodeCapacity) { // No room here
      if (index === 0 && node.prev && node.prev.childCount < this.nodeCapacity) {
        return node.prev.basicInsert(node.prev.childCount, item);
      }
      // Check whether we can redistribute (to avoid a split)
      if (node !== this.base) {
        let (left, right) = node.pairWithSmallest();
        let joinedIndex = left === node ? index : left.childCount + index;
        let sumCount = left.childCount + right.childCount + 1;
        if (sumCount <= 2 * this.nodeCapacity) { // redistribute
          let childCount = sumCount >> 1;
          if (node === right) { // redistribute to the left
            let insertInLeft = joinedIndex < childCount;
            left.moveFromNext(childCount - left.childCount - +insertInLeft);
          } else { // redistribute to the right
            let insertInRight = index >= sumCount - childCount;
            left.moveToNext(childCount - right.childCount - +insertInRight);
          }
          if (joinedIndex > left.childCount ||
            joinedIndex === left.childCount && left.childCount > right.childCount) {
            right.basicInsert(joinedIndex - left.childCount, item);
          } else {
            left.basicInsert(joinedIndex, item);
          }
          return;
        }
      }
      // Cannot redistribute: split node
      let childCount = node.childCount >> 1;
      // Create a new node that will later become the right sibling of this node
      let sibling = new Node(childCount);
      // Move half of node node's data to it
      sibling.moveFrom(node, 0, childCount, childCount);
      // Insert the item in either the current node or the new one
      if (index > node.childCount) {
        sibling.basicInsert(index - node.childCount, item);
      } else {
        node.basicInsert(index, item);
      }
      // Is this the base?
      if (!node.parent) {
        // ...then first create a parent, which is the new base
        this.base = new Node(2);
        this.base.basicInsert(0, node);
      }
      // Prepare for inserting the sibling node into the tree
      index = node.index() + 1;
      node = node.parent;
      item = sibling; // item is now a Node
    }
    node.basicInsert(index, item);
  }
  remove(key) {
    let (node, index) = this.locate(key);
    if (index >= node.childCount || node.children(index).key !== key) return; // not found
    while (true) {
      node.basicRemove(index);

      // Exit when node's fill ratio is fine
      if (!node.parent || node.childCount * 2 > this.nodeCapacity) return;
      // Node has potentially too few children, we should either merge or redistribute

      let (left, right) = node.pairWithSmallest();

      if (!left || !right) { // A node with no siblings? Must become the base!
        this.base = node;
        node.parent = null;
        return;
      }
      let sumCount = left.childCount + right.childCount;
      let childCount = sumCount >> 1;

      // Check whether to merge or to redistribute
      if (sumCount > this.nodeCapacity) { // redistribute
        // Move some data from the bigger to the smaller node
        let shift = childCount - node.childCount;
        if (!shift) { // Boundary case: when a redistribution would bring no improvement
          console.assert(node.childCount * 2 === this.nodeCapacity && sumCount === this.nodeCapacity + 1);
          return;
        }
        if (node === left) { // move some children from right to left
          left.moveFromNext(shift);
        } else { // move some children from left to right
          left.moveToNext(shift);
        }
        return;
      }

      // Merge:
      // Move all data from the right to the left
      left.moveFromNext(right.childCount);
      // Prepare to delete right node
      node = right.parent;
      index = right.index();
    }
  }
}

module.exports = Tree
Tree.Node = Node
Tree.KeyValue = KeyValue

It has some initial tests like this:

const Tree = require('./keyValueTree')
const { Node, KeyValue } = Tree

  /* Below this point: these methods are optional */
Tree.prototype(Symbol.iterator) = function*() { // Make tree iterable, yielding key/value pairs
    for (let node = this.first; node; node = node.next) {
        for (let i = 0; i < node.childCount; i++) yield (node.children(i).key, node.children(i).value);
    }
}

Tree.prototype.verify = function() {
    // Raise an error when the tree violates one of the required properties
    if (!this.base || !this.base.childCount) return; // An empty tree is fine.
    if (this.base.parent) throw "base should not have a parent";
    // Perform a breadth first traversal
    let q = (this.base);
    while (q.length) {
        if (q(0).isLeaf() && this.first !== q(0)) throw "this.first is not pointing to first leaf";
        let level = ();
        let last = null;
        for (let parent of q) {
            if (!(parent instanceof Node)) throw "parent is not instance of Node";
            if (parent.children.length > this.nodeCapacity) throw "node's children array is too large";
            if (parent.childCount > 0 && parent.childCount * 2 <= parent.children.length) throw "node's fill ratio is too low";
            for (let i = parent.childCount; i < parent.children.length; i++) {
                if (parent.children(i) !== null) throw "child beyond childCount should be null but is not";
            }
            if (parent.isLeaf()) {
                if (parent.children(0).key !== parent.key) throw "key does not match with first child value";
                for (let value of parent.children.slice(0, parent.childCount)) {
                    if (value === null) throw "leaf has a null as value";
                    if (!(value instanceof KeyValue)) throw "leaf has a non-KeyValue item";
                }
            } else {
                if (parent.children(0).key !== parent.key) throw "key does not match with first child's key";
                for (let node of parent.children.slice(0, parent.childCount)) {
                    if (node === null) throw "internal node has a null as value";
                    if (!(node instanceof Node)) throw "internal node has a non-Node as value";
                    if (node.parent !== parent) throw "wrong parent";
                    if (node.prev !== last) throw "prev link incorrect";
                    if (last && last.next !== node) throw "next link incorrect";
                    if (last && last.children.length + node.children.length <= this.nodeCapacity) {
                        throw "two consecutive siblings have a total number of children that is too small";
                    }
                    if (node.childCount * 2 < this.nodeCapacity) {
                        throw "internal node is too small: " + node;
                    }
                    level.push(node);
                    last = node;
                }
            }
        }
        if (last && last.next) throw "last node in level has a next reference";
        q = level;
    }
}

Tree.prototype.test = function(count=100) {
    const isEqual = () =>
        JSON.stringify((...map).sort((a,b) => a(0)-b(0))) === JSON.stringify((...this));
    // Create Map to perform the same operations on it as on the tree
    let map = new Map;
    let max = count*2;
    // Perform a series of insertions
    for (let i = 0; i < count; i++) {
        // Choose random key
        let key = Math.floor(Math.random() * max);
        let value = key*2;
        // Perform same insertion in array and tree
        map.set(key, value);
        this.set(key, value);
        // Verify tree consistency and properties
        this.verify();
        // Verify the order of key/values in the array is the same as in the tree
        console.assert(isEqual(), "tree not same as array");
    }
    // Perform a series of retrievals and updates
    for (let i = 0; i < count; i++) {
        // Choose random key
        let key = Math.floor(Math.random() * max);
        // Perform same retrieval in array and tree
        let value = map.get(key);
        if (value !== this.get(key)) throw "get() returns inconsistent result";
        if (value === undefined) { // value is not in tree
            this.remove(key); // should not alter the tree
        } else { // value is in tree: update it
            map.set(key, value+10);
            this.set(key, value+10);
        }
        // Verify tree consistency and properties
        this.verify();
        // Verify the order of key/values in the array is the same as in the tree
        console.assert(isEqual(), "tree not same as array");
    }
    // Perform a series of deletions
    for (let i = map.size; i > 0; i--) {
        // Choose random deletion value
        let j = Math.floor(Math.random() * i)
        let key = (...map.keys())(j);
        // Perform same deletion in array and tree
        map.delete(key);
        this.remove(key);
        // Verify tree consistency and properties
        this.verify();
        // Verify the order of key/values in the array is the same as in the tree
        console.assert(isEqual(), "tree not same as array");
    }
}

// Perform 1000 calls of set (some duplicates),
//    1000 calls of get and updating set calls,
//    and remove calls to remove all nodes,
//    on a tree with node capacity of 8
let tree = new Tree(8).test(1000);
console.log("all tests completed");

However, I don’t feel very comfortable with having Math.random used in the tests and not being able to really see the expected output clearly, which is more of what I’m used to.

So I am starting to put together some new tests, which happen to use this allocate function:

const Tree = require('./keyValueTree')

module.exports = allocate

function allocate(bins, bits) {
  if ((bits & (bits - 1)) != 0) {
    throw "Parameter is not a power of 2";
  }

  if (bits < 32 || bits > 4194304) {
    throw "Bits required out of range";
  }

  var startBinIndex = Math.log2(bits >> 5);
  var lastBin = bins.length - 1;

  for (var binIndex = startBinIndex; binIndex <= lastBin; binIndex++) {
    var bin = bins(binIndex);

    //
    // We have found a bin that is not empty...
    //
    if (bin.base.treeSize != 0) {
      //
      // Calculate amount of memory this bin takes up
      //
      var thisBinMemorySize = (32 << binIndex);
      var binBlock = bin.first.children(0);
      var memoryAddress = binBlock.key;

      //
      // We are going to return this block
      //
      var allocatedMemoryBlock = memoryAddress

      //
      // Before we return the above block, we need to remove the block if count is 1 otherwise decrease count and adjust memory start pointer by bin size
      //
      if (binBlock.value == 1) {
        bin.remove(binBlock.key)
      } else {
        binBlock.value--;
        binBlock.key += thisBinMemorySize;
        bin.first.updateKey()
      }

      //
      // if we want 1024 bits and it takes it from bin 15, we simply subtract 1024 from 4194304 which gives us 4193280
      // if we then populate bin 3 (1024 bits) onward, until bin 14, the exact number we end up populating those bins with is 4183280
      //
      var remainingUnsedMemory = thisBinMemorySize - bits;
      var adjustmentSize = bits;
      while (remainingUnsedMemory != 0) {
        memoryAddress += adjustmentSize;

        bins(startBinIndex).set(memoryAddress, 1)
        startBinIndex++;
        remainingUnsedMemory -= bits;
        adjustmentSize = bits;
        bits <<= 1;
      }

      return allocatedMemoryBlock;
    }
  }
  return null; // out of memory...
}

Here are the tests for that:

const Tree = require('./keyValueTree')
const allocate = require('./allocate')
const assert = require('assert')

test('allocate blocks', () => {
  const bins = createBaseBins()
  var address = allocate(bins, 128)
  assert.strictEqual(address, 0)
  var address = allocate(bins, 256)
  assert.strictEqual(address, 256)
  var address = allocate(bins, 128)
  assert.strictEqual(address, 128)
  var address = allocate(bins, 256)
  assert.strictEqual(address, 512)
  var address = allocate(bins, 128)
  assert.strictEqual(address, 768)
  var address = allocate(bins, 4096)
  assert.strictEqual(address, 4096)
  // console.log(bins(15).first)
  // assert.deepStrictEqual(bins, (
  //   (),
  //   (),
  //   ( { start: 896, count: 1 } ),
  //   (),
  //   (),
  //   ( { start: 1024, count: 1 } ),
  //   ( { start: 2048, count: 1 } ),
  //   (),
  //   ( { start: 8192, count: 1 } ),
  //   ( { start: 16384, count: 1 } ),
  //   ( { start: 32768, count: 1 } ),
  //   ( { start: 65536, count: 1 } ),
  //   ( { start: 131072, count: 1 } ),
  //   ( { start: 262144, count: 1 } ),
  //   ( { start: 524288, count: 1 } ),
  //   ( { start: 1048576, count: 99 } )
  // ))
})

function test(name, fn) {
  // console.log(name)
  fn()
}

function createBaseBins() {
  let bins = (
    new Tree, // 128 bits each chunk
    new Tree, // 256
    new Tree, // 512
    new Tree, // 1024
    new Tree, // 2048
    new Tree, // 4096
    new Tree, // 8192
    new Tree, // 16384
    new Tree, // 32768
    new Tree, // 65536
    new Tree, // 131072
    new Tree, // 262144
    new Tree, // 524288
    new Tree, // 1048576
    new Tree, // 2097152
    new Tree, // 4194304
  )
  bins(bins.length - 1).set(0, 100)
  return bins
}

I commented out what I had in the test before I started using the tree data structure. It was nice to test the full structure of the “bins” layout because in this case I am working on both the implementations for the tree and the allocate function and seeing that everything is correctly laid out is helpful.

What I’m wondering though is what is the best way to write tests for this system? Should I be testing for the full structure of the “bins” layout? Or is there a more standard approach? I didn’t opt for testing specific nodes in the tree because it’s hard to read and follow after a few dozen nodes are tested and the test gets large.

Besides how to test the bins, how do I test the permutations of the tree? This tree changes shape every power of two nodes, and should shrink down if it gets below power of two. So it’s like I would take snapshots of the tree and expect or assert that I see a complete tree structure at different checkpoints. Is that the right general approach? If not, what is?

Once I have tested a few snapshots of the tree, how do I know if I have covered all of the things that can happen to the tree, is there an easy way to tell, or do I have to deeply re-understand how the implementation works and figure out what should be tested from that?

Just wondering general approaches here, not super specifics of what specifically to test. Thinking about methodology and workflow and debugging above the rest.

Does URL structure really matter to users?

I have seen a bunch of answers regarding URL structure and SEO. However, I would like to know does URL structure really matter to users?

For example, if I have:
Parentsite.com/brand1
Parentsite.com/brand2

Vs

Brand1.com
Brand2.com

Do users really care if I point them to parentsite.com/brand1 vs brand1.com if the brands are all somewhat related?

By looking at larger sites like Google or Amazon, it doesn’t seem like URLs matter as long as you have a decent navigation and search capability. For example, a lot of google websites are just google.com/site_name. However, I have also seen a lot of articles that imply a structure like that isn’t standard if you have different brands.

automata – Determine if a Kripke structure satisfies an LTL formula

I am trying to understand the correlation between LTL and Kripke structures. Zoom classes are very tough to follow and i can’t find anything online. I have the following Kripke structure with q3 as start. I have to demonstrate that it either satisfies or not the following LTL formulae.

  1. a U b

  2. a U X(a ∧ ¬b)

  3. X¬b ∧ G(¬a ∨ ¬b)

Kripke structure

I would really appreciate if somebody could explain to me the steps to prove that a KS satisfies a LTL formula.

stream processing – Clean structure for routing data through microservices using gRPC

Im working on a project where users can upload huge data files containing, for example, word embeddings. These embeddings then get projected to a lower dimension using conventional algorithms such as PCA, UMAP et cetera.

I figured it might be a good idea to try out the microservice architecture and gRPC for the communication.

Architecture

Since gRPC-web didn’t support bi-directional streaming yet I’m using websockets to communicate the chunks of the datafiles to a gateway, which translates it to gRPC, and forwards the data to the rest of the services.

First of all, I return the projection to the gateway, which translates it to a websocket message to send it back to the client. But I also want to perform a KNN on the projected data, so currently I send the projected data to the K-nearest Neighbour service aswell.

Rough data traffic

This works fine and all, but the rerouting part of the data gets very messy in the gateway program and a lot of error handling has to be done should a pod running a service fail. Is there anyway to do this easier? Perhaps using some sort of subscribe on data streams system?

Thanks in advance.

8 – Bakery structure – Drupal Answers

I am building a bakery web shop. I wanted to ask for advice on the product/variation structure.

The products would be something as the following:

But each of these types have 10 fields in common and a couple of specific fields for each type.

Then for example, the cake would have:

  • Chocolate cake
  • Vanilla cake
  • etc…

What would be the best way to create this structure?

I had a few solutions in mind, but I am not sure if they are possible:

  • 1 product type with 5 variation types (not sure if possible)
  • 5 product types that extend from the main product type (not sure if possible)
  • 5 product types separately created, but with same field

Any suggestions to improve this structure?

mysql – Importing new db structure from dev site over older db structure using phpmyadmin

I have a site where the db structure is one way and I have a developer that provided me a copy of a database without data only the old db structure with new tables and fields added.

Using phpmyadmin how do I import the new db file so that it will allow the file to complete the import and add the new missing tables and fields that are in the new db?

I can not locate any setting to apply prior to import.

Thanks ahead of time for any help or direction to solve my problem.

Thank you

ubuntu – Nginx/Apache installed but can’t see folder structure or files

I’m using a VPS and ubuntu for the first time and I need to host a website, I’ve got the VPS running and ubuntu installed but when I install apache or nginx everything works fine and I can see the placeholder site when I go to my IP address.

The problem is that after installing I don’t see any folders or files created by nginx when doing ls -a like the /var or /etc folders.

I tried logging in as root but that also doesn’t help, also I’ve tried to recreate the folder structure and add the files I needed but that also doesn’t change anything.

I’m trying to setup server blocks/virtual hosts but nothing is working as I can’t see nginx’s files and it looks like nginx can’t see my files. Hope someone can help.

relational theory – SQL Server Diagram :: How to structure snowflake branch?

I need to solve an exercise for a pharmaceutical company, they ask me to create a database structure from scratch given a few informations.

Because I want it to be scalable and “future proof” I decided to follow the snowflake structure. For now it looks more star than snowflake but the idea is there. I have a particular question about the main Fact Table (Study) and how to represent the Dimension Table Status.

I came up with 2 options:

  • OPTION 1: Fact Table Study > Foreign Key > Dimension Table Contract > Foreign Keys > Dimension Table Status.

So we pass through two Dimension Tables in order to represent the Status on the Fact Table. I will do that through a JOIN in a view or whatever…

enter image description here

  • OPTION 2: Fact Table Study > Foreign Key > Dimension Table Status.

This way we link directly the Fact Table (Study) to the Dimension Table Status.

enter image description here

Should I go for Option 1 or Option 2?

I’m afraid to link too many Dimension Tables to the Fact Table. This is the first time I try to create a database structure.

Any advice is welcome, any suggestion is welcome, especially from seasoned database architects but also from amateurs.

Thank you

SP 2016 – Move files using Content and Structure brought over extra columns

Per a user request, I just moved some files from one library to another using Content and Structure. The source library has more columns than the target library. The files brought over the extra columns. Now when the user tries to change the metadata in the columns which belong in the target library, nothing happens.

I used Content and Structure because preserving the version history is important to the user.

  1. What can we do to enable metadata changes on the moved files?
  2. Is there a way to execute this move that does not cause these problems?