C++ Project 09 - STL

General Rules for these projects:

The purpose of these c++ projects is to get introduced into OOP. We are allowed to use standard c++17.

• code must be coiled with c++ and the flags -Wall -Werror -Wextra.
• there must be a Makefile for each exercise.
• Class names and corresponding filenames must be written in UpperCamelCase format.
• The using namespace <ns_name> and friend keywords are forbidden.
• There must be no memory leaks.
• Classes must be designed in the Orthodox Canonical Form.
• There can be no function implementations in headerfiles.
• Headers must be able to be used independently from others.
• Use of STL in the Module 08 and 09 only
• finally here we can /have to use containers and the algorithm header
• important in this one:
  • You must use at least one container for each exercise with the exception of exercise 02 which requires the use of two containers and you can use each container only in one excercise.

🔶 ex00 Bitcoin Exchange

Objective: You have to create a program which outputs the value of a certain amount of bitcoin on a certain date. The program will take as input a second database, storing the different prices/dates to evaluate.

Usage:

cd ex00
make
./btc <inputfile>

Example:

$> cat input.txt 
date | value
2011-01-03 | 3
2011-01-03 | 2
2011-01-03 | 1
2011-01-03 | 1.2
2011-01-09 | 1
2012-01-11 | -1
2001-42-42
2012-01-11 | 1
2012-01-11 | 2147483648
4554-88-11 | 500
2001-11-26 | 80
2025-01-
dfxbdh
2019-04-26 | 999
2017-02-30 | 25
2017-02-28 | 25
2017-02-29 | 25
2016-02-29 | 25
6969-69-69 | 12
2025-02-25 | 15
2025-02-26 | 15
2025-03-25 | 15%
$>

$> ./btc input.txt
2011-01-03 => 3 = 0.9
2011-01-03 => 2 = 0.6
2011-01-03 => 1 = 0.3
2011-01-03 => 1.2 = 0.36
2011-01-09 => 1 = 0.33
Error: not a positive number.
Error: bad input => 2001-42-42
2012-01-11 => 1 = 7.1
Error: too large a number.
Error: bad input => 4554-88-11 | 500
2001-11-26 => 80 = 0 (Careful! Input date far away from first database entry: 2009-01-02 converison might not be accurate!)
Error: bad input => 2025-01-
Error: bad input => dfxbdh
2019-04-26 => 999 = 5.19041e+06
Error: bad input => 2017-02-30 | 25
2017-02-28 => 25 = 29772.3
Error: bad input => 2017-02-29 | 25
2016-02-29 => 25 = 10562.5
Error: bad input => 6969-69-69 | 12
2025-02-25 => 15 = 706739 (Careful! Input date far away from last database entry: 2022-03-29 converison might not be accurate!)
2025-02-26 => 15 = 706739 (Careful! Input date far away from last database entry: 2022-03-29 converison might not be accurate!)
2025-03-25 => 15 = 706739 (Careful! Input date far away from last database entry: 2022-03-29 converison might not be accurate!)

My thoughts:

• this was way more tricky than i originally htought. tha date vaidation took me a bit reworking. but also working with maps for the first time was a big learnig curve. i was very glad about regex though.

🔶 ex01 Reverse Polish Notation

Ojective: Your program must take an inverted Polish mathematical expression as an argument. It takes integers from 0 - 9 and operators "+ - / *".

Usage:

cd ex01
make
./RPN "..<0-9> any order <+ - / *> ..."

Example:

$> ./RPN 
Error usage: ./RPN "..<0-9> any order <+ - / *> ..."
$> ./RPN "8 9 * 9 - 9 - 9 - 4 - 1 +"
42

My thoughts:

• Learning about RPN and how closely related it is in how the cpu recieves instructions was very interesting. The exercise in general was not too difficult.

🔶 ex02 PmergeMe

Ojective: Implement the Ford-Johnson algorithm (source: Art Of Computer Programming, Vol.3. Merge Insertion, Page 184.) to sort two different containers and show the difference in compute time between them.

Usage:

cd ex02
make
./PmergeMe <any number of integers from min int to max int>

Example: (not enough numbers for noticable time difference)

$> ./PmergeMe  0  1  4  2 17 11  9  3  8  5 10 12 14 18 13  6 21  7 15 19 16 
VEC Before: 0 1 4 2 17 11 9 3 8 5 10 12 14 18 13 6 21 7 15 19 16 
DEQ Before: 0 1 4 2 17 11 9 3 8 5 10 12 14 18 13 6 21 7 15 19 16 

VEC After: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 21 
DEQ After: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 21 
Maximum comparisons for 21 numbers: 66
Time to process a range of 21 elements with std::vector<int>: 17 microseconds
Comparisons for vector: 64
Time to process a range of 21 elements with std::deque<int>: 17 microseconds
Comparisons: 64

$> ./PmergeMe `jot -r 300 1 10000 | tr '\n' ' '`
VEC Before: 9538 7421 5813 152 4433 5904 2374 3603 5682 2443 3 6230 9973 85 4136 7809 1413 3701 9562 7558 7727 3361 4892 1385 9504 8522 8018 7858 9292 4900 426 4385 5827 2326 7383 1103 821 1566 792 3168 2932 2165 3703 5113 4941 4834 1248 9668 3592 7170 1006 5548 9227 9963 4640 8114 3553 669 3778 1389 8424 4715 80 6988 8731 8354 5462 3394 2275 7519 6718 7130 2116 1872 4761 5 4370 9619 4159 7537 2483 6502 1615 2116 4451 2291 3926 5160 9245 7184 9280 399 5228 4036 2320 9334 87 5996 3642 7537 4090 7966 9972 8600 8741 2530 6795 3212 2278 5056 7651 9425 7936 3766 5335 4991 6016 5894 9237 3701 2497 8728 8140 6048 7567 3956 8899 9629 5866 576 8755 7980 1795 9072 265 1172 1247 132 2080 931 5197 3823 1527 737 6292 7837 2239 7530 6181 1631 8683 8090 9586 2530 4232 8764 3092 2676 676 740 2181 7628 9117 9079 8966 9350 3018 7992 660 2918 3666 1609 934 2345 3122 7075 9202 7982 9999 1219 8631 7960 3067 5970 6501 7180 9437 5533 703 3734 1242 6632 1099 1008 4704 4446 7859 1104 1572 773 2710 8470 7235 83 3711 8094 7298 3475 9016 2307 3009 1787 847 331 2121 873 2037 5107 1200 4380 8497 495 3705 6866 9337 1505 44 3692 7009 327 8164 3171 3774 8926 2064 293 699 6575 3865 1771 226 3688 5476 6182 6577 1616 2390 5562 5793 7744 7256 1098 2660 1808 4469 9588 3222 893 2086 313 8846 5738 9211 7341 6058 1468 1204 4740 7522 206 6477 8000 1349 6275 5627 7128 9846 6390 5237 6464 8700 3867 1404 8372 9156 8784 748 3967 6040 6990 5388 6002 7826 9510 3049 8404 7993 8188 4818 4280 
DEQ Before: 9538 7421 5813 152 4433 5904 2374 3603 5682 2443 3 6230 9973 85 4136 7809 1413 3701 9562 7558 7727 3361 4892 1385 9504 8522 8018 7858 9292 4900 426 4385 5827 2326 7383 1103 821 1566 792 3168 2932 2165 3703 5113 4941 4834 1248 9668 3592 7170 1006 5548 9227 9963 4640 8114 3553 669 3778 1389 8424 4715 80 6988 8731 8354 5462 3394 2275 7519 6718 7130 2116 1872 4761 5 4370 9619 4159 7537 2483 6502 1615 2116 4451 2291 3926 5160 9245 7184 9280 399 5228 4036 2320 9334 87 5996 3642 7537 4090 7966 9972 8600 8741 2530 6795 3212 2278 5056 7651 9425 7936 3766 5335 4991 6016 5894 9237 3701 2497 8728 8140 6048 7567 3956 8899 9629 5866 576 8755 7980 1795 9072 265 1172 1247 132 2080 931 5197 3823 1527 737 6292 7837 2239 7530 6181 1631 8683 8090 9586 2530 4232 8764 3092 2676 676 740 2181 7628 9117 9079 8966 9350 3018 7992 660 2918 3666 1609 934 2345 3122 7075 9202 7982 9999 1219 8631 7960 3067 5970 6501 7180 9437 5533 703 3734 1242 6632 1099 1008 4704 4446 7859 1104 1572 773 2710 8470 7235 83 3711 8094 7298 3475 9016 2307 3009 1787 847 331 2121 873 2037 5107 1200 4380 8497 495 3705 6866 9337 1505 44 3692 7009 327 8164 3171 3774 8926 2064 293 699 6575 3865 1771 226 3688 5476 6182 6577 1616 2390 5562 5793 7744 7256 1098 2660 1808 4469 9588 3222 893 2086 313 8846 5738 9211 7341 6058 1468 1204 4740 7522 206 6477 8000 1349 6275 5627 7128 9846 6390 5237 6464 8700 3867 1404 8372 9156 8784 748 3967 6040 6990 5388 6002 7826 9510 3049 8404 7993 8188 4818 4280 

VEC After: 3 5 44 80 83 85 87 132 152 206 226 265 293 313 327 331 399 426 495 576 660 669 676 699 703 737 740 748 773 792 821 847 873 893 931 934 1006 1008 1098 1099 1103 1104 1172 1200 1204 1219 1242 1247 1248 1349 1385 1389 1404 1413 1468 1505 1527 1566 1572 1609 1615 1616 1631 1771 1787 1795 1808 1872 2037 2064 2080 2086 2116 2116 2121 2165 2181 2239 2275 2278 2291 2307 2320 2326 2345 2374 2390 2443 2483 2497 2530 2530 2660 2676 2710 2918 2932 3009 3018 3049 3067 3092 3122 3168 3171 3212 3222 3361 3394 3475 3553 3592 3603 3642 3666 3688 3692 3701 3701 3703 3705 3711 3734 3766 3774 3778 3823 3865 3867 3926 3956 3967 4036 4090 4136 4159 4232 4280 4370 4380 4385 4433 4446 4451 4469 4640 4704 4715 4740 4761 4818 4834 4892 4900 4941 4991 5056 5107 5113 5160 5197 5228 5237 5335 5388 5462 5476 5533 5548 5562 5627 5682 5738 5793 5813 5827 5866 5894 5904 5970 5996 6002 6016 6040 6048 6058 6181 6182 6230 6275 6292 6390 6464 6477 6501 6502 6575 6577 6632 6718 6795 6866 6988 6990 7009 7075 7128 7130 7170 7180 7184 7235 7256 7298 7341 7383 7421 7519 7522 7530 7537 7537 7558 7567 7628 7651 7727 7744 7809 7826 7837 7858 7859 7936 7960 7966 7980 7982 7992 7993 8000 8018 8090 8094 8114 8140 8164 8188 8354 8372 8404 8424 8470 8497 8522 8600 8631 8683 8700 8728 8731 8741 8755 8764 8784 8846 8899 8926 8966 9016 9072 9079 9117 9156 9202 9211 9227 9237 9245 9280 9292 9334 9337 9350 9425 9437 9504 9510 9538 9562 9586 9588 9619 9629 9668 9846 9963 9972 9973 9999 
DEQ After: 3 5 44 80 83 85 87 132 152 206 226 265 293 313 327 331 399 426 495 576 660 669 676 699 703 737 740 748 773 792 821 847 873 893 931 934 1006 1008 1098 1099 1103 1104 1172 1200 1204 1219 1242 1247 1248 1349 1385 1389 1404 1413 1468 1505 1527 1566 1572 1609 1615 1616 1631 1771 1787 1795 1808 1872 2037 2064 2080 2086 2116 2116 2121 2165 2181 2239 2275 2278 2291 2307 2320 2326 2345 2374 2390 2443 2483 2497 2530 2530 2660 2676 2710 2918 2932 3009 3018 3049 3067 3092 3122 3168 3171 3212 3222 3361 3394 3475 3553 3592 3603 3642 3666 3688 3692 3701 3701 3703 3705 3711 3734 3766 3774 3778 3823 3865 3867 3926 3956 3967 4036 4090 4136 4159 4232 4280 4370 4380 4385 4433 4446 4451 4469 4640 4704 4715 4740 4761 4818 4834 4892 4900 4941 4991 5056 5107 5113 5160 5197 5228 5237 5335 5388 5462 5476 5533 5548 5562 5627 5682 5738 5793 5813 5827 5866 5894 5904 5970 5996 6002 6016 6040 6048 6058 6181 6182 6230 6275 6292 6390 6464 6477 6501 6502 6575 6577 6632 6718 6795 6866 6988 6990 7009 7075 7128 7130 7170 7180 7184 7235 7256 7298 7341 7383 7421 7519 7522 7530 7537 7537 7558 7567 7628 7651 7727 7744 7809 7826 7837 7858 7859 7936 7960 7966 7980 7982 7992 7993 8000 8018 8090 8094 8114 8140 8164 8188 8354 8372 8404 8424 8470 8497 8522 8600 8631 8683 8700 8728 8731 8741 8755 8764 8784 8846 8899 8926 8966 9016 9072 9079 9117 9156 9202 9211 9227 9237 9245 9280 9292 9334 9337 9350 9425 9437 9504 9510 9538 9562 9586 9588 9619 9629 9668 9846 9963 9972 9973 9999 
Maximum comparisons for 300 numbers: 2064
Time to process a range of 300 elements with std::vector<int>: 129 microseconds
Comparisons for vector: 2044
Time to process a range of 300 elements with std::deque<int>: 176 microseconds
Comparisons: 2044

My thoughts:

• This was without a doubt the hardest of the c++ exercises. The Ford-Johnson algorithm is neither the fastest not the most efficient algorithm so there ar not many sources about it available. The reference to the book was pretty much all information i had plus my peers trying to figure it out at the same time. this algorithm is about minimizing the maximum needed comparisons of numbers so sort a list of numbers. it does so recursively and by keepig track of which numbers have been compared before to avoid unneccessary extra comparisons. in the end i was really proud of my rather short implementation which only uses three container objects to keep track of and sort everything. It took me a lot of nerves to get rid of all the off-by-one errors out of my code. But it was very rewarding when it finally worked. in the end it was a worthy last C++ exercise for the preparation to the next projects and to really learn about the effect of having gone through the tedious process of writing everything manually in C and now being able to adapt to a new language quite easily.