p2.md

Sparrow Stage P2: NullableInts

In this stage, you'll create an efficient way to represent a series of integer values, some of which may be missing. Floating points have NaN (not a number), but there is no equivalent for integers.

See the overall project description here.

Corrections/updates

• Mar 30: tests 6-10 (those covering P2) are released
• Apr 3: update test 9 -- make printing of invalid NullableInts safe and remove requirement to use const

Learning objectives

• create structs
• create pointers
• use indirection and address-of operators
• use const

Directions

NullableInts struct

If you want to have a list of ints, with some values missing, one way would be to create a vector of int pointers -- you could use NULL to represent the missing values. This is a very inefficient approach. An int is often only 4 bytes, but a pointer on a 64-bit CPU is 8-bytes. So you would need 2-3x more memory to do this than a simple vector of ints (exact overhead would depend on how many ints are missing, among other things). Furthermore, the ints wouldn't be adjacent in memory, so this would not be a cache-friendly data structure.

Instead, you'll pair up a regular vector of ints (not pointers!) with bitsets. The bits will indicate which integers are valid and which should be ignored (a bit plus an arbitrary int value only consume 33 bits, whereas an int pointer with nullptr would be 64 bits).

To keep this information together (i.e., ints and valid bits), create a NullableInts struct in the sparrow namespace in sparrow.h. It should have two members: nums (a vector of ints) and valid (a vector of 32-bit bitsets).

The num[idx] value is only considered valid if valid[i/32][i%32] is true. The size of nums might not be a multiple of 32; this is fine -- any code you write should ignore the extra valid bits at the end.

Helper Code

For debugging, it will be useful to have a function that lets you inspect the contents of a NullableInts. Feel free to write your own, or borrow from the following if you like:

// print NullableInts                                                                    
std::ostream& operator<<(std::ostream &os, sparrow::NullableInts &obj) {
  std::cout << "NullableInts: [";
  for (int i=0; i<obj.nums.size(); i++) {
    if (obj.valid[i/32][i%32]) {
      std::cout << obj.nums[i];
    } else {
      std::cout << "null";
    }
    if (i < obj.nums.size()-1) {
      std::cout << ", ";
    }
  }
  std::cout << "]\n";
  return os;
}

DropZero function

Create a DropZero function that takes a pointer to a NullableInts struct as the only argument and returns nothing. It should loop over all the numbers and flip the corresponding valid bit to false whenever it encounters a 0 in nums.

Average function

Write an Average function that takes a pointer to NullableInts and computes the average number (as a float), skipping any numbers not marked as valid according to the bits.

Return a struct AverageResult (that you should define) with two members, value (containing the computed result) and ok, a bool. If you cannot compute an average because there are no valid numbers, then ok should be false; it doesn't matter what value is in this scenario.

Divide function

Write a Divide function that takes two pointers to NullableInts structs. Divide will perform an element-wise division, such that the output number at index idx will be the number in the first NullableInts at index idx divided by the number at the same position in the second NullableInts.

Divide should return a DivideResult struct that you'll define -- it will have a value (a NullableInts object) and an ok to indicate whether value is meaningful.

Your Divide function should first use the BitAnd function from the P1 stage to determine which bits will be valid in the result. The computed result at index idx should be considered valid if and only if the numerator and denominator are considered valid in their respective NullableInts inputs.

If BitAnd fails, you should propagate the error, meaning Divide should indicate failure as well. Divide may ignore other issues (e.g., divide by zero, size mismatch, etc).

Executable

Write a p2.cpp program that uses the new functionality in your library.

Paste in these values into main (feel free to modify depending on how you're managing namespaces):

  NullableInts nints1{.nums={20,999,40,60}, .valid=vector{bitset<32>{"00000000000000000000000000001101"}}};
  NullableInts nints2{.nums={10,10,0,20}, .valid=vector{bitset<32>{"00000000000000000000000000001111"}}};

Remember that vector indexes start at 0 from the left, but bitset indexes start at zero from the right, so ...1101 in nints1 is saying that the number at index 1 (999) is an arbitrary value that should be ignored.

Write some code that does an element-wise division of nints1 by nints2, computes the average of the resulting numbers, and prints it out. Be sure to drop any zero values from the denominator prior to doing the division.