Function constructTree

packages/merkle/src/binary/binaryMerkleTree.ts:26–68

(data: string[])

 * Construct tree
 */
export function constructTree(data: string[]): Node[] {
  const nodes = [];
  for (let i = 0; i < data.length; i += 1) {
    const hashed = hashLeaf(data[i]);
    const leaf = new Node(-1, -1, -1, hashed, data[i]);
    leaf.index = i;
    nodes.push(leaf);
  }

  const nodesList = [...nodes];
  let pNodes = [...nodes];

  let size = (nodes.length + 1) >> 1;
  let odd = nodes.length & 1;
  // eslint-disable-next-line no-constant-condition
  while (true) {
    let i = 0;
    for (; i < size - odd; i += 1) {
      const j = i << 1;
      const hashed = hashNode(pNodes[j].hash, pNodes[j + 1].hash);
      nodes[i] = new Node(pNodes[j].index, pNodes[j + 1].index, -1, hashed, '');
      const nextIndex = nodesList.length;
      nodes[i].index = nextIndex;

      nodesList[pNodes[j].index].parent = nextIndex;
      nodesList[pNodes[j + 1].index].parent = nextIndex;
      nodesList.push(nodes[i]);
    }

    if (size === 1) {
      break;
    }

    if (odd === 1) {
      nodes[i] = pNodes[i << 1];
    }

    odd = size & 1;
    size = (size + 1) >> 1;
    pNodes = [...nodes];
  }
  return nodesList;
}

/**
 * Compute the merkle root