CODEWITHSUNDEEP
c++conditional-statements
Sidharth Mudgil
Sidharth Mudgil

Reputation: 1461

Impossible conditional statement

bool flag = ((idx == n) ? true : false);

if (C[idx]->n < t)
    fill(idx);

if (flag && idx > n)
    C[idx - 1]->deletion(k);

The above code snippet is part of the BTree implementation, I searched everywhere but I can't find will the second if-statement will ever be executed?

The flag will only be true when the idx == n, Right? and the if statement will execute only if idx > n and flag = true, which is impossible.

I think that the fill(idx) is changing value but I can't understand how? Someone explain

fill function

void BTreeNode::fill(int idx) {
  if (idx != 0 && C[idx - 1]->n >= t)
    borrowFromPrev(idx);

  else if (idx != n && C[idx + 1]->n >= t)
    borrowFromNext(idx);

  else {
    if (idx != n)
      merge(idx);
    else
      merge(idx - 1);
  }
  return;
}

Upvotes: 0

Views: 216

Answers (2)

Sidharth Mudgil
Sidharth Mudgil

Reputation: 1461

After implementing my version, I get to know that the in some conditions the fill function is calling another function named merge that is changing the value of n.

When child-node can't borrow either from left-sibling or right-sibling they will merge with the parent, Which results in a change in the value of n

void fill(int pos)
{
    ...

    else
    {
        if (pos != no_of_keys)
            merge(pos);
        else
            merge(pos - 1);
    }
}

merge function

void merge(int pos)
{
    Node *child = childs[pos];
    Node *sibling = childs[pos + 1];

    child->keys[no_of_keys] = keys[pos];
    child->no_of_keys++;

    for (int i = 0; i < sibling->no_of_keys; i++)
    {
        child->keys[i + t] = sibling->keys[i];
        child->no_of_keys++;
    }

    if (!child->leaf)
        for (int i = 0; i < sibling->no_of_keys + 1; i++)
            child->childs[i + t] = sibling->childs[i];

    for (int i = pos; i < no_of_keys - 1; i++)
        keys[i] = keys[pos + 1];

    for (int i = pos + 1; i < no_of_keys; i++)
        child[i] = child[pos + 1];

    no_of_keys--;
}

Upvotes: 0

qdesmettre
qdesmettre

Reputation: 123

After looking at the code from the link you provided, the variable idx is never changed. But, by going through fill(idx), n gets modified in certain cases (as it's an attribute, and as fill is a method that have access to n). So the second if statement can be triggered in some cases, when n is modified by fill or one of the methods called by fill.

The code:

fill(idx):

void BTreeNode::fill(int idx) {
  if (idx != 0 && C[idx - 1]->n >= t)
    borrowFromPrev(idx);

  else if (idx != n && C[idx + 1]->n >= t)
    borrowFromNext(idx);

  else {
    if (idx != n)
      merge(idx);
    else
      merge(idx - 1);
  }
  return;
}

It can call borrowFromPrev, borrowFromNext or merge, which functions can change n in some cases:

// Borrow from previous
void BTreeNode::borrowFromPrev(int idx) {
  BTreeNode *child = C[idx];
  BTreeNode *sibling = C[idx - 1];

  for (int i = child->n - 1; i >= 0; --i)
    child->keys[i + 1] = child->keys[i];

  if (!child->leaf) {
    for (int i = child->n; i >= 0; --i)
      child->C[i + 1] = child->C[i];
  }

  child->keys[0] = keys[idx - 1];

  if (!child->leaf)
    child->C[0] = sibling->C[sibling->n];

  keys[idx - 1] = sibling->keys[sibling->n - 1];


  child->n += 1; // here
  sibling->n -= 1; // here

  return;
}

// Borrow from the next
void BTreeNode::borrowFromNext(int idx) {
  BTreeNode *child = C[idx];
  BTreeNode *sibling = C[idx + 1];

  child->keys[(child->n)] = keys[idx];

  if (!(child->leaf))
    child->C[(child->n) + 1] = sibling->C[0];

  keys[idx] = sibling->keys[0];

  for (int i = 1; i < sibling->n; ++i)
    sibling->keys[i - 1] = sibling->keys[i];

  if (!sibling->leaf) {
    for (int i = 1; i <= sibling->n; ++i)
      sibling->C[i - 1] = sibling->C[i];
  }

  child->n += 1; // here
  sibling->n -= 1; // here

  return;
}

// Merge
void BTreeNode::merge(int idx) {
  BTreeNode *child = C[idx];
  BTreeNode *sibling = C[idx + 1];

  child->keys[t - 1] = keys[idx];

  for (int i = 0; i < sibling->n; ++i)
    child->keys[i + t] = sibling->keys[i];

  if (!child->leaf) {
    for (int i = 0; i <= sibling->n; ++i)
      child->C[i + t] = sibling->C[i];
  }

  for (int i = idx + 1; i < n; ++i)
    keys[i - 1] = keys[i];

  for (int i = idx + 2; i <= n; ++i)
    C[i - 1] = C[i];

  child->n += sibling->n + 1; // here
  n--; // here

  delete (sibling);
  return;
}

Upvotes: 5

Related Questions