2023 Startups these days are merging so fast it s hard to keep track of who is | Assignment Collections

Startups these days are merging so fast, it’s hard to keep track of who is in what company. Company A merges with Company B, and Company C merges with Company D, and then the two merged companies merge, and suddenly, employees from companies A and C find themselves being colleagues. This is getting sufficiently difficult to follow that we will have you write a Startup Tracker.

Here is how this will work. You have n students. Initially, each starts a startup company by himself/herself. Then, companies may merge. When you have a merge command, you will be given the numbers of two representative students, one from each company. Then, for each of those two students, you find the “biggest” company they are in, i.e., companies that are not subcompanies of any bigger company; let’s call them A and B. Those two companies A and B are then merged into a new company; let’s call it C. C will become the parent company of A and B.

Sometimes, companies also split up again. When we call split, we will again give you a representative student. Then, you find the biggest company that the student is in – let’s call it A. As a result of the split, A should be completely removed, and the two companies that were at some point in the past merged to become A will now be individual companies without a parent again. (If the student is only in their own 1-person company, split does nothing.)

You will build a data structure that allows you to process a sequence of merges and splits, and answer queries about whether two students are in the same company.

To illustrate this, consider the following example with 5 students. After each command, we are showing you the structure of the nested companies with braces. The notation { {1}, { {2}, {3} } } means that we have a company with two subcompanies: the first subcompany is just student 1, while the second subcompany again has two subcompanies, one consisting of just student 2, the other consisting of just student 3.

merge (0,1)   => { {0}, {1} }, {2}, {3}, {4}
merge (2,3)   => { {0}, {1} }, { {2}, {3} }, {4}
merge (0,3)   => { { {0}, {1} }, { {2}, {3} } }, {4}
split (2)     => { {0}, {1} }, { {2},{3} }, {4}
split (2)     => { {0}, {1} }, {2}, {3}, {4}
merge (2,4)   => { {0}, {1} }, { {2}, {4} }, {3}
split (0)     => {0}, {1}, { {2}, {4} }, {3}

A company is captured by the following

struct Company {
  Company *parent;   // the parent company, or nullptr if it has no parent
  Company *merge1, *merge2;
  /* the subcompanies that were merged to obtain this company, or
     nullptr if this is a 1-student company */

  Company ()
  { parent = nullptr; merge1 = nullptr; merge2 = nullptr; }
  Company (Company *m1, Company *m2)
  { parent = nullptr; merge1 = m1; merge2 = m2; }
};

Your task is to implement the following data structure:

class CompanyTracker {
public:
  CompanyTracker (int n);
  // initializes the tracker with n students and their 1-person companies

  ~CompanyTracker (); // deallocates all dynamically allocated memory

  void merge (int i, int j);
  /* Merges the largest companies containing students i and j,
     according to the rules described above.
     That is, it generates a new Company object which will
     become the parent company of the largest companies currently
     containing students i and j.
     If i and j already belong to the same company (or are the same),
     merge doesn't do anything.
     If either i or j are out of range, merge doesn't do anything. */

  void split (int i);
  /* Splits the largest company that student i belongs to,
     according to the rules described above.
     That is, it deletes that Company object, and makes sure that
     the two subcompanies have no parent afterwards.
     If i's largest company is a 1-person company, split doesn't do anything.
     If i is out of range, split doesn't do anything. */

  bool inSameCompany (int i, int j);
  /* Returns whether students i and j are currently in the same company.
     Returns true if i==j.
     Returns false if i or j (or both) is out of range. */

private:
  int numCompanies;  // the number of companies you are tracking

  Company** companies; 
  /* an array (allocated once in the constructor)
     to keep pointers to all the 1-person companies.
     Will not contain the merged companies. */

  /* Feel free to add private helper functions as you see fit.
     In particular, you may want a function to find the largest company
     that a student i is part of. */
};

The signature above is given to you as a file company.h in the homework-resources repo. There, we also give you a bit of skeleton code that you are welcome to use to simplify your life a little bit. You may add private helper functions to CompanyTracker, but you cannot change the signatures of any of the functions we gave you – otherwise, we cannot test your solution, and that would be bad for your score. Each of your functions should run in no worse than O(n) time.

In order to test your CompanyTracker implementation, you will almost certainly want to write another file that includes it, and has a main function. You can then either read from a file, or hard-wire test-cases. Your test cases and main will not be graded, though; you should submit only your company.cpp file and company.h file (even if you didn’t change it from our provided file).

You may not use any containers from the STL in this problem, other than the vector (if you so choose).