A Computer Science Tapestrypixmap.1Test #2 Topicsz Parameter passing¾ value, reference, constreferencez Classes¾ Documentation/Class design¾ interface vs. implementation¾ Free vs. member functionsz Structsz Enumerated Typesz Vectors¾ Basic methods¾ Size vs. capacity¾ Searching¾ Sorted insertion & deletionz Streams¾ Reading by char¾ Reading by line¾ Reading by “word”¾ Reading stringsz Recursion¾ Tracing function calls¾ Base and recursive cases¾ Iteration and tail-recursionz Algorithmic design¾ Data & loop invariants¾ Patternsz Matrices¾ Nested loopsz Built-in classes, C++…A Computer Science Tapestrypixmap.2Matricesz Matrix class tmatrix is a 2-dimensional version of a vector¾ Useful for tables, bitmaps, and lots of mathematical operatons¾ First index is the row, second index is the columnz Common idiom for iterating through matrixtmatrix<int> mat(rows,cols);for (int i=0; i < rows; i++)for (int j=0; j < cols; j ++){// do something with mat[i][j]}A Computer Science Tapestrypixmap.3Blob Counting: Recursion at Workz Blob counting is similar to what’s called Flood Fill, the method used to fill in an outline with a color (use the paint-can in many drawing programs to fill in)¾ Possible to do this iteratively, but hard to get right¾ Simple recursive solutionz Suppose a slide is viewed under a microscope¾ Count images on the slide, or blobs in a gel, or …¾ Erase noise and make the blobs more visiblez To write the program we’ll use a class CharBitMap which represents images using characters¾ The program blobs.cpp and class Blobs are essential tooA Computer Science Tapestrypixmap.4Counting blobs, the first slideprompt> blobsenter row col size 10 50# pixels on: between 1 and 500: 200+--------------------------------------------------+| * * * * * * *** * **** * * || * * *** ** ** * * * * * * *|| * *** * * *** * * * * * * * * **|| * ** ** * ** * * * *** * * || * * ***** *** * * ** ** * ||* * * * * * ** * *** * *** *||* * *** * ** * * * * * ** ||* * ** * * * * *** ** * || **** * * ** **** * *** * * **||** * * * ** **** ** * * ** *|+--------------------------------------------------+z How many blobs are there? Blobs are connected horizontally and vertically, suppose a minimum of 10 cells in a blob¾ What if blob size changes?A Computer Science Tapestrypixmap.5Identifying Larger Blobsblob size (0 to exit) between 0 and 50: 10.................1...............................................111................................................1................................................11................................................111............2...................................1.............2..................................111...33.......2....................................1...3........222.22..............................11..3333........222...................................33.3333.......................# blobs = 3zThe class Blobs makes a copy of the CharBitMap and then counts blobs in the copy, by erasing noisy data (essentially)¾ In identifying blobs, too-small blobs are counted, then uncounted by erasing themA Computer Science Tapestrypixmap.6Identifying smaller blobsblob size (0 to exit) between 0 and 50: 5....1............2....................................1.1........222....................................111.....333.2.......................4....................33..22......................444....5............33333.222............6.......44.....55...................2.............6.....444.....555..................222...77.......6.......4..............8.............2...7........666.66...............8888...........22..7777........666...............88..8...............77.7777.......................# blobs = 8z What might be a problem if there are more than nine blobs?¾ Issues in looking at code: how do language features get in the way of understanding the code? ¾ How can we track blobs, e.g., find the largest blob?A Computer Science Tapestrypixmap.7Recursive helper functionsz Client programs use Blobs::FindBlobs to find blobs of a given size in a CharBitMap object¾ This is a recursive function, private data is often needed/used in recursive member function parameters¾ Use a helper function, not accessible to client code, use recursion to implement member functionz To find a blob, look at every pixel, if a pixel is part of a blob, identify the entire blob by sending out recursive clones/scouts¾ Each clone reports back the number of pixels it counts¾ Each clone “colors” the blob with an identifying mark¾ The mark is used to avoid duplicate (unending) workA Computer Science Tapestrypixmap.8Conceptual Details of BlobFillz Once a blob pixel is found, four recursive clones are “sent out” looking horizontally and vertically, reporting pixel count¾ How are pixel counts processed by clone-sender?¾ What if all the clones ultimately report a blob that’s small?z In checking horizontal/vertical neighbors what happens if there aren’t four neighbors? Is this a potential problem?¾ Who checks for valid pixel coordinates, or pixel color?¾ Two options: don’t make the call, don’t process the callz Non-recursive member function takes care of looking for blobsign, then filling/counting/unfilling blobs¾ How is unfill/uncount managed?A Computer Science Tapestrypixmap.9What's a pixmap, a bit, a byte, a char?z The pbm ASCII format we're using in Pixmap assignment is not for conserving space, it's for ease-of-reading¾ Here's a 3x6 (rows,columns) image, what is it?0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0¾ How much disk space does this use?• (18 + 18) chars/spaces * 8 bits/char = 288 bits = 36 chars• We have 18 bits, should be able to store in 4 charsz The xv toolkit can save an image in raw pbm too¾ Uses one bit per 0/1 rather than 2 bytes (space)¾ To convert back, read a byte/char at a time, and peel off the bits, see convertpbm.cpp00101010 = 0x27+ 0x26+ 1x25+ 0x24+ 1x23+ 0x22+ 1x21+