Chapter 26 // Exercise 12, 13, 14 - Principles & Practice Using C++

In this exercise I'm using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 26 // Exercise 12

Write a program that generates random floating-point numbers and sort them using std::sort. Measure the time used to sort 500,000 doubles and 5,000,000 doubles.

Github: https://github.com/l-paz91/principles-practice/blob/master/Chapter%2026/Exercise%2012

This was a fun little task and taught me how to create a function to create random doubles.

Chapter 26 // Exercise 13

Repeat the experiment in the previous exercise, but with random strings of lengths in the [0:100) range.

Github: https://github.com/l-paz91/principles-practice/blob/master/Chapter%2026/Exercise%2013

I'd already created a randString function many exercises earlier and added it to std_lib_facilities. So you can find that in the link at the top of the post. Creating the vectors took almost as much time as sorting them. Especially the second one. I watched the memory used jump to 1.1GB and it took a good 120 seconds to create the strings.

Chapter 26 // Exercise 14

Repeat the previous exercise, except using a map rather than a vector so that we don't need to sort.

Github: https://github.com/l-paz91/principles-practice/blob/master/Chapter%2026/Exercise%2014

I had to add an arbitrary value for each map entry. As its added sorted though, I timed creating the map. I found it weird though that sometimes, my strings would all start with a number; especially with 500000 strings created.

I also found it interesting that the map.size() was reporting 487,784 elements added when 500,000 were inserted. This meant that randString() created almost 13,000 duplicate strings; which is wild.

I could've used a container like Set, which only stores keys but the exercise said map. I also could've stored the strings as value and then sorted by value but then that defeats the purpose of a map.

This was much faster than the vector though, as it took 120 seconds to create the vector then the extra 80 to sort. However, I am missing a chunk of data due to keys being the same.

...

And with that, I'm done with Chapter 26! I honestly can't believe there's only 1 chapter left. It feels like a chapter of my life is coming to an end and I don't think I'm ready.

Chapter 26 // Exercise 11 - Principles & Practice Using C++

In this exercise I'm using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 26 // Exercise 11

Time the sum example from section 26.6 with m being square matrices with dimensions 100, 10,000, 1,000,000, and 10,000,000. Use random element values in the range [-10:10). Rewrite the calculation of v to use a more efficient (not O(N2)) algorithm and compare the timings.

Github:  https://github.com/l-paz91/principles-practice/blob/master/Chapter%2026/Exercise%2011

I literally had no memory of how to use the matrix code from Chapter 24 at all. It was practically a year ago for me at this point. It took me a while to figure out how to use it again and what to do.

row_sum needs to be implemented. After that I had trouble creating the random matrices of certain values as I kept getting bad memory allocations and I was only at a matrix of size 10,000. I'm pretty sure Bjarne did this intentionally, or he was using a super computer, as mine kept running out of memory trying to allocate values into the matrices. I did some quick calculations and realised this is because a matrix of size 10,000 x 10,000 is trying to allocate memory for 100,000,000 doubles. A double is 8 bytes, so we're roughly trying to allocate memory for 762 MB of memory in one go. For the next size up of 1,000,000 that would equate to 7.45 terabytes!

Yeah, Bjarne definitely did this on purpose. So instead of creating these large matrices, I decided to "simulate" the large matrix by just computing the sum. However, this is still very slow and will take forever past 10,000. 

Ultimately I don't believe there is a way to use a more efficient algorithm because summing all the elements in a matrix is O(N^2). All we can do is try and make the code more efficient like passing by reference or using multithreading.

Chapter 26 // Exercise 9, 10 - Principles & Practice Using C++

In this exercise I'm using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 26 // Exercise 9

Add a text-based output format for the graphics interface library. For example, when a call Circle{Point{0,1},15} is executed, a string like Circle{Point{0,1},15} should be produced on an output stream.

Github:  https://github.com/l-paz91/principles-practice/blob/master/Chapter%2026/Exercise%209%2C%2010

For this, I didn't know if he meant output to the window (so a cout stream of sorts) or output it to a file (so ostream). So I decided on an output file based on the next exercise.

I used my "FLTK Engine" for this exercise again:

https://github.com/l-paz91/BlinkEngine/tree/main/BlinkEngine

And added a simple call to output to a text file called DebugCommandsCalled. You can find this change in Window.cpp Blink::Window::onTextEnteredInCommandConsole().

Chapter 26 // Exercise 10

Use the text-based interface from exercise 9 to write a better test for the graphical interface library.

Github:  N/A

So we don't have any tests to start with for the FLTK code and I can't really imagine how using text files would be useful in the long run. I'd be much more inclined to add google tests to the project and start using that instead.

Chapter 26 // Exercise 8 - Principles & Practice Using C++

In this exercise I'm using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 26 // Exercise 8

Add a text-based interface to the graphics interface library from Chapters 12-15. For example, the string Circle{Point{0,1},15} should generate a call Circle{Point{0,1},15}. Use this interface to make a "kid's drawing" of a two-dimensional house with a roof, two windows, and a door.

Github:  https://github.com/l-paz91/principles-practice/blob/master/Chapter%2026/Exercise%208

So I cheated on that first graphics exercise back in Chapter 12 Exercise 7 and drew it in paint. Then loaded it as an image.

I had recently though, re-written the helper code from Bjarne into my own library of sorts (Adventures With Tetris) so going back to that messy, all over the place code from 2020 was jarring. Graph is so big now, if you make a change to it, compilation time is actually noticeable as everything includes Graph.h.

The re-write was the start of a planned FLTK Game Engine I named "Blink". You can find it here:

https://github.com/l-paz91/BLNK-Engine

Apparently Blink is already the name of a HTML engine, however it's developed by Google, so it'll probably be dead in a few years.

(EDIT 09/10/2023 - I've now renamed the engine BLNK)

For this exercise I thought it would be useful to open a "console command" box when you hit a button on the keyboard. Like in Unreal Engine when backtick is pressed you can enter console commands.

This also seemed like a useful thing to add to the engine, so using UE for inspiration, I created a BasicInputBox which is a widget that takes in text and you can grab the contents of the box in various formats (int, string, double etc). I then added an instance of a BasicInputBox to a Window calling it a "CommandConsole". 

I then overrode Fl_Window::handle() to listen for keyboard events. When backtick is pressed it simply shows the widget, making it look like the console window has been opened. You can type text into it. Then with the focus still in that widget, you press enter and the callback function associated with the widget is triggered. The callback grabs what's in the box and uses it in someway. So for example, if you pass "r.drawCircle 100 100 50" to the Command Console, it draws a Circle at x100, y100 with a radius of 50.

I then got bored of the task as I really want to get this book finished...someday. And so I added a quick method for Images. "r.drawImage 100 100 house.png" draws the image specified in the last parameter at x100, y100. Mirroring what I did in chapter 12 exercise 7 all those years ago.

It's not perfect. I'd prefer to not have the window control what the command console does. A future task would be to send the info to a Console Manager along with the window. Using callbacks it can then call the appropriate callback, send the window in and the type can draw to the window. Or you can do something else, like change the colour of the background.

Chapter 26 // Exercise 7 - Principles & Practice Using C++

In this exercise I'm using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 26 // Exercise 7

Test the "simple text editor" from section 20.6.

Github: https://github.com/l-paz91/principles-practice/tree/master/Chapter%2026/Exercise%207

I can't believe I did Chapter 20 almost 2 years ago now...I'm really slacking trying to get my way through this book.

Anyway, I went and got my code from exercise 6, chapter 20 and it no longer compiles for some reason. I had done nothing to it and I'm still using VS2019. It would appear that in the past 2 years, custom iterator classes need more definitions and I couldn't be bothered doing that. So I just re-wrote find_text to not use std::find.

I did a fair amount of testing. I didn't want to spend too much time on it though.

Chapter 26 // Exercise 6 - Principles & Practice Using C++

In this exercise I'm using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 26 // Exercise 6

Modify the calculator from Chapter 7 minimally to let it take input from a file and produce output to a file (or use your operating systems facilities for redirecting I/O). Then devise a reasonably comprehensive test for it.

Github: https://github.com/l-paz91/principles-practice/tree/master/Chapter%2026/Exercise%206

Chapter 7 is back; it's the gift that keeps on giving.

I already kind of implemented this back in Chapter 16 when we had to give this code some graphics using FLTK in C16 Exercise 9. I basically took the calculator code; did nothing to it except "fake" a cin buffer by creating an istringstream and passing the binary data directly to the cin buffer:

 string calculate(string input) 

 { 

     //put the input "into" cin 

     istringstream oss(input); 

     cin.rdbuf(oss.rdbuf());

    

     //now do normal calculator stuff as we have "characters in the buffer" 

     string answer = to_string(statement());

     //clean up token stream for next statement 

     ts.ignore(); 

     return answer; 

 }

Using this code (Exercise 9) I made it so it reads from from a text file that takes input per line, then compares it to the expected output from the next line and compares the two. I decided to just read everything in from one file instead of outputting to another file.

Amusingly, I used ChatGPT-4 to generate the test list and as I ran the tests it gave an incorrect answer for sqrt(pow(5,3)). it said it was 8.66 instead of 11.18. I've decided to leave that in so you can see a failure.

Chapter 26 // Exercise 5 - Principles & Practice Using C++

In this exercise I'm using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 26 // Exercise 5

Add a test to the set of binary_search tests to try and catch the (unlikely) error of a binary_search modifying the sequence.

Github: https://github.com/l-paz91/principles-practice/blob/master/Chapter%2026/Exercise%205

I was a bit confused by this as std::binary_search does not modify anything passed to it. The sequence must already be sorted (or it won't work properly). I tried googling for this and couldn't find any information on it. I then asked ChatGPT-4 and it said std::binary_search will not modify but could provide undefined behaviour if the sequence wasn't sorted.

I then thought that maybe, the predicate function you can pass to binary_search would be able to modify the sequence in some way however the variables are passed to the predicate by const so you would have to const_cast to change them which is considered very bad.

I then told Chat this and gave it the name of the book, the author and the exercise and it pretty much told me "you're reading into this too much, you're supposed to just write a test that shows it doesn't modify the sequence". Should've added "duh" at the end as well.

Once again, taking things literally and overthinking was not the answer.

So instead in TestAll I made a local copy of the sequence then added an if that checks if the sequence has changed after the binary_search was done. No new test needed.

Chapter 26 // Exercise 4 - Principles & Practice Using C++

In this exercise I'm using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 26 // Exercise 4

Devise a format for test data so that you can define a sequence once and run several tests against it.

Github: https://github.com/l-paz91/principles-practice/tree/master/Chapter%2026/Exercise%204

I honestly did not understand what he meant by this at first. I guessed that we had defined the test sequence

{ testName value { sequence } testResult }

and so he wants us to be able to define any test sequence like:

{ testName { sequence } value testResult } 

or even

{ testName } { value } { sequence } { testResult }

So in this case I decided to make an enum that held each part of the sequence:

Then, the user could just create a vector<TestSequences> and pass through whatever sequence type they want like:

I then made the functions into a class that held the sequence type, so it could check it whilst using operator>>. I then used a switch statement to define what to do for each part of sequence.

All you have to do then is create a TestSequence, give it a type, set the sequence type and then load in the text file.

It does rely on there being spaces though. Without the spaces, the entire line will be read in however, I imagine that that would be a major "you must do this when writing tests" line in the documentation for creating tests.

Chapter 26 // Exercise 3 - Principles & Practice Using C++

In this exercise I'm using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 26 // Exercise 3

Repeat exercise 1 with the version of binary_search that takes a comparison criterion. Make a list of new opportunities for errors introduced by that extra argument.

Github: https://github.com/l-paz91/principles-practice/tree/master/Chapter%2026/Exercise%203

I continued using the code from exercise 2 and created a new testAll function called testAllWithPredicate. This takes in the input stream and a function pointer. I then modified testType to take in function pointer and used some std library comparison functions found in <functional>:

https://en.cppreference.com/w/cpp/header/functional

Chapter 26 // Exercise 2 - Principles & Practice Using C++

In this exercise I'm using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 26 // Exercise 2

Modify the testing of binary_search to deal with arbitrary element types. Then test it with string sequences and floating-point sequences.

Github: https://github.com/l-paz91/principles-practice/tree/master/Chapter%2026/Exercise%202

I decided on the rule that you can't have tests that included wildly different types like string and floats. Binary search requires that your elements are sorted, if one element is "cheese" and the other "3.4", how do you sort that?

I then tried to do it so the the same file could read in string tests, followed by int tests or floats. But doing compile time checks on what type the stringstream was reading into became a bit long winded, so I just created 3 seperate text files and fed them into the code.

Then it was just a matter of slightly modifying operator>> overload so it could handle any type. I did this by just reading everything into a string. If it hit '}', I put that character back into the stream then converted the string into the necessary type via istringstream.

Chapter 26 // Exercise 1 - Principles & Practice Using C++

In this exercise I'm using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 26 // Exercise 1

Run your binary search algorithm from section 26.1 with the tests presented in section 26.3.2.1.

Github: https://github.com/l-paz91/principles-practice/tree/master/Chapter%2026/Exercise%201

I started off writing the function and following his bullet points and it had 3 distinct sections; getting the middle and comparing, then seeing if the middle was less or more than. I then got deja vu because knew I had seen this somewhere before in the book/done it before. And so I went looking through the other chapters and sure enough, I found the info I was looking for back in Chapter 21, page 795.

This then triggered a memory of realising how a binary search is actually implemented and I went back through my posts to this one:

https://lptcp.blogspot.com/2021/10/chapter-21-exercise-7-principles.html

Here we were tasked with writing a binary search for a vector, and I was a bit shocked to see my binary search I started implementing was exactly the same as the one I did 2 years ago. I even used the same std::advance and std::distance calls to get the middle iterator. 

Thanks to these tests though, I did find a bug in my code from that exercise, in that if there is only 1 element in the container, and the value we're looking for is more than the contents of the middleElement iterator; it would go into another binary search and eventually overflow. So I checked the distance was more than 1 before doing that.