Method PartitionSubArray

Filters/Parallel/vtkPKdTree.cxx:1177–1452

// If there is no third interval, the second index returned will be R+1.

int* vtkPKdTree::PartitionSubArray(int L, int R, int K, int dim, int p1, int p2)
{
  int rootrank = this->SubGroup->getLocalRank(p1);

  int me = this->MyId;

  if ((me < p1) || (me > p2))
  {
    this->SubGroup->Broadcast(this->SelectBuffer.data(), 2, rootrank);
    return this->SelectBuffer.data();
  }

  if (p1 == p2)
  {
    int* idx = this->PartitionAboutMyValue(L, R, K, dim);

    this->SubGroup->Broadcast(idx, 2, rootrank);

    return idx;
  }

  // Each process will rearrange their subarray myL-myR into a left region
  // of values less than X[K], a center region of values equal to X[K], and
  // a right region of values greater than X[K].  "I" will be the index
  // of the first value in the center region, or it will equal "J" if there
  // is no center region.  "J" will be the index to the start of the
  // right region, or it will be R+1 if there is no right region.

  int tag = this->SubGroup->tag;

  vtkSubGroup* sg = vtkSubGroup::New();
  sg->Initialize(p1, p2, me, tag, this->Controller->GetCommunicator());

  int hasK = this->WhoHas(K);

  int Krank = sg->getLocalRank(hasK);

  int myL = this->StartVal[me];
  int myR = this->EndVal[me];

  myL = std::max(myL, L);
  myR = std::min(myR, R);

  // Get Kth element

  float T;

  if (hasK == me)
  {
    T = this->GetLocalVal(K)[dim];
  }

  sg->Broadcast(&T, 1, Krank);

  int* idx; // dividing points in rearranged sub array

  if (hasK == me)
  {