# Životní cyklus hodnot Ukázky: 1. ‹xxx› 2. ‹numbers› – a list of numbers which remember their type 3. ‹refs› – overloading with references 4. ‹pool› – ownership and indirect references Elementary exercises: 1. ‹diameter› – basic function overloading (circle diameter) 2. ‹circle› – same story, but with constructors 3. ‹force› – a type to represent a force (3D vector) Preparatory exercises: 1. ‹distance› – vzdálenost v rovině 2. ‹least› – nejmenší prvek bez kopií 3. ‹loan› – bankovní půjčka 4. ‹zipper› – jednoduchá datová struktura 5. ‹rpn› – postfixová aritmetika s přetěžováním 6. ‹eval› – infixová aritmetika s vlastnictvím zdrojů Regular exercises: 1. ‹complex› – přetěžování konstruktorů 2. ‹xxx› 3. ‹search› – vyhledávací strom s uzly v poli 4. ‹bitptr› – odkaz na jednotlivý bit 5. ‹xxx› 6. ‹xxx› ## d. Demonstrace (ukázky) ### 2. [‹numbers›] In this demonstration, we will look at overloading: both of regular «methods» and of «constructors». The first class which we will implement is ‹number›, which can represent either a real (floating-point) number or an integer. Besides the attributes ‹integer› and ‹real› which store the respective numbers, the class remembers which type of number it stores, using a boolean attribute called ‹is_real›. struct number /* C */ { bool is_real; int integer = 0; double real = 0; We provide two constructors for ‹number›: one for each type of number that we wish to store. The overload is selected based on the type of argument that is provided. number( int i ) : is_real( false ), integer( i ) {} /* C */ number( double r ) : is_real( true ), real( r ) {} }; The second class will be a container of numbers which directly allows the user to insert both floating-point and integer numbers, without converting them to a common type. To make insertion convenient, we provide overloads of the ‹add› method. Access to the numbers is index-based and is provided by the ‹at› method, which is overloaded for entirely different reasons. class numbers /* C */ { The sole attribute of the ‹numbers› class is the backing store, which is an ‹std::vector› of ‹number› instances. std::vector< number > _data; /* C */ public: The two ‹add› overloads both construct an appropriate instance of ‹number› and push it to the backing vector. Nothing surprising there. void add( double d ) { _data.emplace_back( d ); } /* C */ void add( int i ) { _data.emplace_back( i ); } The overloads for ‹at› are much more subtle: notice that the argument types are all identical – there are only 2 differences, first is the return type, which however does «not participate» in overload resolution. If two functions only differ in return type, this is an error, since there is no way to select which overload should be used. The other difference is the ‹const› qualifier, which indeed does participate in overload resolution. This is because methods have a hidden argument, ‹this›, and the trailing ‹const› concerns this argument. The ‹const› method is selected when the call is performed on a ‹const› object (most often because the call is done on a constant reference). const number &at( int i ) const { return _data.at( i ); } /* C */ number &at( int i ) { return _data.at( i ); } }; int main() /* demo */ /* C */ { numbers n; n.add( 7 ); n.add( 3.14 ); assert( !n.at( 0 ).is_real ); /* C */ assert( n.at( 1 ).is_real ); assert( n.at( 0 ).integer == 7 ); /* C */ Notice that it is possible to assign through the ‹at› method, if the object itself is mutable. In this case, overload resolution selects the second overload, which returns a mutable reference to the ‹number› instance stored in the container. n.at( 0 ) = number( 3 ); /* C */ assert( n.at( 0 ).integer == 3 ); However, it is still possible to use ‹at› on a constant object – in this case, the resolution picks the first overload, which returns a constant reference to the relevant ‹number› instance. Hence, we cannot change the number this way (as we expect, since the entire object is constant, and hence also each of its components). const numbers &n_const = n; /* C */ assert( n_const.at( 0 ).integer == 3 ); // n_const.at( 1 ) = number( 1 ); this will not compile /* C */ } ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄ ### 3. [‹refs›] In this demonstration, we will look at overloading functions based on different kinds of references. This will allow us to adapt our functions to the kind of value (and its lifetime) that is passed to them, and to deal with arguments efficiently (without making unnecessary copies). But first, let's define a few type aliases: using int_pair = std::pair< int, int >; /* C */ using int_vector = std::vector< int >; using int_matrix = std::vector< int_vector >; Our goal will be simple enough: write a function which gives access to the first element of any of the above types. In the case of ‹int_matrix›, the element is an entire row, which has some important implications that we will discuss shortly. Our main requirements will be that: 1. ‹first› should work correctly when we call it on a constant, 2. when called on a mutable value, ‹first( x ) = y› should work and alter the value ‹x› (i.e. update the first element of ‹x›). These requirements are seemingly contradictory: if we return a value (or a constant reference), we can satisfy point 1, but we fail point 2. If we return a mutable reference, point 2 will work, but point 1 will fail. Hence we need the result type to be different depending on the argument. This can be achieved by overloading on the argument type. However, we still have one problem: how do we tell apart, using a type, whether the passed value was constant or not? Think about this: if you write a function which accepts a mutable reference, it cannot be called on an argument which is constant: the compiler will complain about the value losing its ‹const› qualifier (if you never encountered this behaviour, try it out; it's important that you understand this). But that means that ‹first( int_pair &arg )› can only be called on mutable arguments, which is exactly what we need. Fortunately for us, if the compiler decides that this particular ‹first› cannot be used (because of missing ‹const›), it will keep looking for some other ‹first› that might work. You hopefully remember that ‹first( const int_pair &arg )› can be called on any value of type ‹int_pair› (without creating a copy). If we provide both, the compiler will use the non-‹const› version if it can, but fall back to the ‹const› one otherwise. And since overloaded functions can differ in their return type, we have our solution: int &first( int_pair &p ) { return p.first; } /* C */ int first( const int_pair &p ) { return p.first; } The case of ‹int_vector› is completely analogous: int &first( int_vector &v ) { return v[ 0 ]; } /* C */ int first( const int_vector &v ) { return v[ 0 ]; } Since in the above cases, the return value was of type ‹int›, we did not bother with returning ‹const› references. But when we look at ‹int_matrix›, the situation has changed: the value which we return is an ‹std::vector›, which could be very expensive to copy. So we will want to avoid that. The first case (mutable argument), stays the same – we already returned a reference in this case. int_vector &first( int_matrix &v ) { return v[ 0 ]; } /* C */ At first glance, the second case would seem straightforward enough – just return a ‹const int_vector &› and be done with it. But there is a catch: what if the argument is a temporary value, which will be destroyed at the end of the current statement? It's not a very good idea to return a reference to a doomed object, since an unwitting caller could get into serious trouble if they store the returned reference – that reference will be invalid on the next line, even though there is no obvious reason for that at the callsite. You perhaps also remember, that the above function, with a mutable reference, cannot be used with a temporary as its argument: like with a constant, the compiler will complain that it cannot bind a temporary to an argument of type ‹int_matrix &›. So is there some kind of a reference that can bind a temporary, but not a constant? Yes, that would be an «rvalue reference», written ‹int_matrix &&›. If the above candidate fails, the next one the compiler will look at is one with an rvalue reference as its argument. In this case, we know the value is doomed, so we better return a value, not a reference into the doomed matrix. Moreover, since the input matrix is doomed anyway, we can steal the value we are after using ‹std::move› and hence still manage to avoid a copy. int_vector first( int_matrix &&v ) { return std::move( v[ 0 ] ); } /* C */ If both of the above fail, the value must be a constant – in this case, we can safely return a reference into the constant. The argument is not immediately doomed, so it is up to the caller to ensure that if they store the reference, it does not outlive its parent object. const int_vector &first( const int_matrix &v ) /* C */ { return v[ 0 ]; } That concludes our quest for a polymorphic accessor. Let's have a look at how it works when we try to use it: int main() /* demo */ /* C */ { int_vector v{ 3, 5, 7, 1, 4 }; assert( first( v ) == 3 ); first( v ) = 5; assert( first( v ) == 5 ); const int_vector &const_v = v; /* C */ assert( first( const_v ) == 5 ); int_matrix m{ int_vector{ 1, 2, 3 }, v }; /* C */ const int_matrix &const_m = m; assert( first( first( m ) ) == 1 ); /* C */ first( first( m ) )= 2; assert( first( first( const_m ) ) == 2 ); /* C */ assert( first( first( int_matrix{ v, v } ) ) == 5 ); What follows is the case where the rvalue-reference overload of ‹first› (the one which handles temporaries) saves us: try to comment the overload out and see what happens on the next 2 lines for yourself. const int_vector &x = first( int_matrix{ v, v } ); /* C */ assert( first( x ) == 5 ); } ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄ ### 4. [‹pool›] This demo will be our first serious foray into dealing with object lifetime. In particular, we will want to implement binary trees – clearly, the lifetime of tree nodes must exactly match the lifetime of the tree itself: • if the nodes were released too early, the program would perform invalid memory access when traversing the tree, • if the nodes are not released with the tree, that would be a memory leak – we keep the nodes around, but cannot access them. This is an ubiquitous problem, and if you think about it, we have encountered it a lot, but did not have to think about it yet: the items in an ‹std::vector› or ‹std::map› or other containers have the same property: their lifetime must match the lifetime of the instance which «owns them». This is one of the most important differences between C and C++: if we do C++ right, most of the time, we do not need to manage object lifetimes manually. This is achieved through two main mechanisms: 1. pervasive use of «automatic variables», through «value semantics» – local variables and arguments are «automatically destroyed» when they go out of scope, 2. «cascading» – whenever an object is destroyed, its attributes are also destroyed «automatically», and a mechanism is provided for classes which own additional, non-attribute objects (e.g. elements in an ‹std::vector›) to automatically destroy them too (this is achieved by «user-defined destructors»). In general, destroying objects at an appropriate time is the job of the «owner» of the object – whether the owner is a function (this is the case with by-value arguments and local variables) or another object (attributes, elements of a container and so on). Additionally, this happens «transparently» for the user: the compiler takes care of inserting the right calls at the right places to ensure everything is destroyed at the right time. The end result is modular or «composable» resource management – well-behaved objects can be composed into well-behaved composites without any additional glue or boilerplate. To make things easy for now, we will take advantage of existing containers to do resource management for us, which will save us from writing destructors (the proverbial glue, which is boring to write and easy to get wrong). In the next chapter, we will see how we can use «smart pointers» for the same purpose. We will be keeping the nodes of our binary tree in an ‹std::vector› – this means that each node has an «index» which we can use to refer to that node. In other words, in this demo (and in some of this week's exercises) indices will play the role of pointers. Since 0 is a valid index, we will use -1 to indicate an invalid (‘null’) reference. Besides ‘pointers’ to the left and right child, the node will contain a single integer value. struct node /* C */ { int left = -1, right = -1; int value; }; As mentioned earlier, the nodes will be held in a vector: let's give a name to the particular vector type, for convenience: using node_pool = std::vector< node >; /* C */ Working with ‹node› is, however, rather inconvenient: we cannot ‘dereference’ the ‹left›/‹right› ‘pointers’ without going through ‹node_pool›. This makes for verbose code which is unpleasant to both read and to write. But we can do better: let's add a simple wrapper type, which will remember both a reference to the ‹node_pool› and an index of the ‹node› we are interested in: values of this type can then behave like a proper reference to ‹node›: only a value of the ‹node_ref› type is needed to access the node and to walk the tree. struct node_ref /* C */ { node_pool &_pool; int _idx; To make the subsequent code easier to write (and read), we will define a few helper methods: first, a ‹get› method which returns an actual reference to the ‹node› instance that this ‹node_ref› represents. node &get() { return _pool[ _idx ]; } /* C */ And a method to construct a new ‹node_ref› using the same pool as this one, but with a new index. node_ref make( int idx ) { return { _pool, idx }; } /* C */ Normally, we do not want to expose the ‹_pool› or ‹node› to users directly, hence we keep them private. But it's convenient for ‹tree› itself to be able to access them. So we make ‹tree› a friend. node_ref( node_pool &p, int i ) : _pool( p ), _idx( i ) {} /* C */ For simplicity, we allow invalid references to be constructed: those will have an index -1, and will naturally arise when we encounter a node with a missing child – that missing node is represented as index -1. The ‹valid› method allows the user to check whether the reference is valid. The remaining methods (‹left›, ‹right› and ‹value›) must not be called on an invalid ‹node_ref›. This is the moral equivalent of a null pointer. bool valid() const { return _idx >= 0; } /* C */ What follows is a simple interface for traversing and inspecting the tree. Notice that ‹left› and ‹right› again return ‹node_ref› instances. This makes tree traversal simple and convenient. node_ref left() { return make( get().left ); } /* C */ node_ref right() { return make( get().right ); } int &value() { return get().value; } /* C */ }; Finally the class to represent the tree as a whole. It will own the nodes (by keeping a ‹node_pool› of them as an attribute, will remember a «root node» (which may be invalid, if the tree is empty) and provide an interface for adding nodes to the tree. Notice that «removal» of nodes is conspicuously missing: that's because the pool model is not well suited for removals (smart pointers will be better in that regard). struct tree /* C */ { node_pool _pool; int _root_idx = -1; A helper method to append a new ‹node› to the pool and return its index. int make( int value ) /* C */ { _pool.emplace_back(); _pool.back().value = value; return _pool.size() - 1; } node_ref root() { return { _pool, _root_idx }; } /* C */ bool empty() const { return _root_idx == -1; } We will use a vector to specify a location in the tree for adding a node, with values -1 (left) and 1 (right). An empty vector represents at the root node. using path_t = std::vector< int >; /* C */ Find the location for adding a node recursively and create the node when the location is found. Assumes that the path is correct. void add( node_ref parent, path_t path, int value, /* C */ unsigned path_idx = 0 ) { assert( path_idx < path.size() ); int dir = path[ path_idx ]; if ( path_idx < path.size() - 1 ) /* C */ { auto next = dir < 0 ? parent.left() : parent.right(); return add( next, path, value, path_idx + 1 ); } if ( dir < 0 ) /* C */ parent.get().left = make( value ); else parent.get().right = make( value ); } Main entry point for adding nodes. void add( path_t path, int value ) /* C */ { if ( root().valid() ) add( root(), path, value ); else { assert( path.empty() ); _root_idx = make( value ); } } }; int main() /* demo */ /* C */ { tree t; t.add( {}, 1 ); assert( t.root().value() == 1 ); /* C */ assert( t.root().valid() ); assert( !t.root().left().valid() ); t.add( { -1 }, 7 ); /* C */ assert( t.root().value() == 1 ); assert( t.root().left().valid() ); assert( t.root().left().value() == 7 ); t.add( { -1, 1 }, 3 ); /* C */ assert( t.root().left().right().value() == 3 ); } ## e. Elementární příklady ### 2. [‹circle›] Standard 2D point. struct point; /* C */ Implement a structure ‹circle› with 2 constructors, one of which accepts a point and a number (center and radius) and another which accepts 2 points (center and a point on the circle itself). Store the circle using its center and radius, in attributes ‹center› and ‹radius› respectively. struct circle; /* C */ ### 3. [‹force›] In this example, we will define a class that represents a (physical) force in 3D. Forces are «vectors» (in the mathematical sense): they can be added and multiplied by scalars (scalars are, in this case, real numbers). Forces can also be compared for equality (we will use fuzzy comparison because floating point computations are inexact). Hint: It may be useful to know that when overloading binary operators, the operands do not need to be of the same type. class force; /* C */ ## p. Přípravy ### 1. [‹distance›] V této úloze se budeme pohybovat v dvourozměrné ploše a počítat při tom uraženou vzdálenost. Typ ‹walk› nechť má tyto metody: • ‹line( p )› – přesuneme se do bodu ‹p› po úsečce, • ‹arc( p, radius )› – přesuneme se do bodu ‹p› po kružnicovém oblouku s poloměrem ‹radius›,¹ přitom ‹radius› je alespoň polovina vzdálenosti do bodu ‹p› po přímce, • ‹backtrack()› – vrátíme se po vlastních stopách do předchozího bodu (vzdálenost se přitom bude «zvětšovat»), • ‹distance()› – vrátí celkovou dosud uraženou vzdálenost. Metody nechť je možné libovolně řetězit, tzn. je-li ‹w› typu ‹walk›, následovný výraz musí být dobře utvořený: w.line( { 1, 1 } ) .line( { 2, 1 } ) .backtrack() .arc( { 4, 1 }, 7 ); Hodnoty typu ‹walk› lze sestrojit zadáním počátečního bodu, nebo implicitně – začínají pak z bodu ⟦(0, 0)⟧. ¹ Potřebný středový úhel naleznete například vyřešením rovnoramenného trojúhelníku s délkou ramene ‹radius› a základnou určenou vzdáleností spojovaných bodů. struct walk; /* C */ ### 2. [‹least›] Uvažme typ ‹element› hodnot, které (z nějakého důvodu) nelze kopírovat. Našim cílem bude naprogramovat funkci, která vrátí nejmenší prvek ze zadaného vektoru hodnot typu ‹element›. Definici tohoto typu nijak neměňte. struct element /* C */ { element( int v ) : value( v ) {} element( element &&v ) : value( v.value ) {} element &operator=( element &&v ) = default; bool less_than( const element &o ) const { return value < o.value; } bool equal( const element &o ) const { return value == o.value; } private: int value; }; using data = std::vector< element >; /* C */ Naprogramujte funkci (nebo rodinu funkcí) ‹least› tak, že volání ‹least( d )› vrátí nejmenší prvek zadaného vektoru ‹d› typu ‹data›. Dobře si rozmyslete platnost (délku života) dotčených objektů. Nápověda: Protože nemůžete přímo manipulovat hodnotami typu ‹element›, zkuste využít k zapamatování si dosud nejlepšího kandidáta iterátor. ### 3. [‹loan›] V tomto příkladu se budeme zabývat (velmi zjednodušenými) bankovními půjčkami. Navrhneme 2 třídy: ‹account›, která bude mít obvyklé metody ‹deposit›, ‹withdraw›, ‹balance›, a které konstruktoru lze předat počáteční zůstatek (v opačném případě bude implicitně nula). Druhá třída bude ‹loan› – její konstruktor přijme «referenci» na instanci třídy ‹account› a velikost půjčky (‹int›). Sestrojením hodnoty typu ‹loan› se na přidružený účet připíše vypůjčená částka. Třída ‹loan› nechť má metodu ‹repay›, která zařídí (případně částečné – určeno volitelným parametrem typu ‹int›) navrácení půjčky. Proběhne-li vše v pořádku, metoda vrátí ‹true›, jinak ‹false›. Zůstatek účtu může být záporný, hodnota půjčky nikoliv. Půjčka musí být vždy plně splacena (tzn. zabraňte situaci, kdy se informace o dluhu „ztratí“ aniž by byl tento dluh splacen). struct account; /* C */ struct loan; ### 4. [‹zipper›] V tomto příkladu implementujeme jednoduchou datovou strukturu, které se říká «zipper» – reprezentuje sekvenci prvků, přitom právě jeden z nich je «aktivní» (angl. focused). Abychom se nemuseli zabývat generickými datovými typy, vystačíme si celočíselnými položkami. Typ ‹zipper› nechť má toto rozhraní: • konstruktor vytvoří jednoprvkový ‹zipper› z celého čísla, • ‹shift_left› (‹shift_right›) aktivuje prvek vlevo (vpravo) od toho dosud aktivního, a to v čase O(1); metody vrací ‹true› bylo-li posun možné provést (jinak nic nezmění a vrátí ‹false›), • ‹insert_left› (‹insert_right›) přidá nový prvek těsně vlevo (vpravo) od právě aktivního prvku (opět v čase O(1)) • ‹focus› zpřístupní aktivní prvek (pro čtení i zápis) • «volitelně» metody ‹erase_left› (‹erase_right›) které odstraní prvek nalevo (napravo) od aktivního, v čase O(1), a vrátí ‹true› bylo-li to možné struct zipper; /* C */ ### 5. [‹rpn›] Naprogramujte jednoduchý zásobníkový evaluátor aritmetických výrazů zapsaných v RPN (postfixové notaci). Operace: • ‹push› vloží na vrch pracovního zásobníku konstantu, • ‹apply› přijme hodnotu jednoho ze tří níže definovaných typů, které reprezentují operace a příslušnou operaci provede, • metoda ‹top› poskytne přístup k aktuálnímu vrcholu pracovního zásobníku, včetně možnosti změnit jeho hodnotu, • ‹pop› odstraní jednu hodnotu z vrcholu zásobníku a vrátí ji, • ‹empty› vrátí ‹true› je-li pracovní zásobník prázdný. Podobně jako v příkladu ‹distance› zařiďte, aby bylo možné metody ‹push› a ‹apply› libovolně řetězit. Všechny tři operace uvažujeme jako binární. struct add {}; /* addition */ /* C */ struct mul {}; /* multiplication */ struct dist {}; /* absolute value of difference */ struct eval; /* C */ ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄ ### 6. [‹eval›] V tomto cvičení naprogramujeme vyhodnocování infixových aritmetických výrazů. Zároveň zabezpečíme, aby bylo lze sdílet společné podvýrazy (tzn. uložit je jenom jednou a při dalším výskytu je pouze odkázat). Proto budeme uzly ukládat ve společném úložišti. const int op_mul = 1; /* C */ const int op_add = 2; const int op_num = 3; struct node /* C */ { Operace, kterou tento uzel reprezentuje (viz konstanty definované výše). Pouze uzly typu ‹mul› a ‹add› mají potomky. int op; /* C */ Položky ‹left› a ‹right› jsou indexy, přičemž hodnota -1 značí neplatný odkaz. Položka ‹is_root› je nastavena na ‹true› právě tehdy, když tento uzel není potomkem žádného jiného uzlu. int left = -1, right = -1; /* C */ bool is_root = true; Hodnota uzlu, je-li tento uzel typu ‹op_num›. int value = 0; /* C */ }; using node_pool = std::vector< node >; /* C */ Dočasná reference na uzel, kterou lze použít při procházení stromu, ale která je platná pouze tak dlouho, jako hodnota typu ‹eval›, která ji vytvořila. Přidejte (konstantní) metody ‹left› a ‹right›, kterých výsledkem je nová hodnota typu ‹node_ref› popisující příslušný uzel, a dále metodu ‹compute›, která vyhodnotí podstrom začínající v aktuálním uzlu. Konečně přidejte metodu ‹update›, která upraví hodnotu v aktuálním uzlu. Metodu ‹update› je dovoleno použít pouze na uzly typu ‹op_num›. struct node_ref; /* C */ Typ ‹eval› reprezentuje výraz jako celek. Umožňuje vytvářet nové výrazy ze stávajících (pomocí metod ‹add›, ‹mul› a ‹num›) a procházet strom výrazů (počínaje z kořenů, které lze získat metodou ‹roots›). struct eval /* C */ { node_pool _pool; std::vector< node_ref > roots(); /* C */ node_ref add( node_ref, node_ref ); /* C */ node_ref mul( node_ref, node_ref ); node_ref num( int ); }; ## r. Řešené úlohy ### 1. [‹complex›] Structure ‹angle› simply wraps a single double-precision number, so that we can use constructor overloads to allow use of both polar and cartesian forms to create instances of a single type (‹complex›). struct angle; /* C */ struct complex; Now implement the following two functions, so that they work both for real and complex numbers. // double magnitude( … ) /* C */ // … reciprocal( … ) The following two functions only make sense for complex numbers, where ‹arg› is the argument, normalized into the range ⟦(-π, π⟩⟧: double real( complex ); /* C */ double imag( complex ); double arg( complex ); ### 2. [‹account›] In this exercise, you will create a simple class: it will encapsulate some state (account balance) and provide a simple, safe interface around that state. The class should have the following interface: • the constructor takes 2 integer arguments: the initial balance and the maximum overdraft • a ‹withdraw› method which returns a boolean: it performs the action and returns ‹true› iff there was sufficient balance to do the withdrawal • a ‹deposit› method which adds funds to the account • a ‹balance› method which returns the current balance (may be negative) and that can be called on ‹const› instances of ‹account› class account; /* C */ ### 3. [‹search›] Implement a binary search tree, i.e. a binary tree which maintains the search property. That is, a value of each node is: • ≥ than all values in its left subtree, • ≤ than all values in its right subtree. Store the nodes in a pool (a vector or a list, your choice). The interface is as follows: • ‹node_ref root() const› returns the root node, • ‹bool empty() const› checks whether the tree is empty, • ‹void insert( int v )› inserts a new value into the tree (without rebalancing). The ‹node_ref› class then ought to provide: • ‹node_ref left() const› and ‹node_ref right() const›, • ‹bool valid() const›, • ‹value() const› which returns the value stored in the node. Calling ‹root› on an empty tree is undefined. struct node; /* ref: 6 lines */ /* C */ using node_pool = std::vector< node >; /* C */ class node_ref; /* ref: 12 lines */ /* C */ class tree; /* ref: 28 lines */ ### 4. [‹bitptr›] Implement 2 classes, ‹bitptr› and ‹const_bitptr›, which provide access to a single (mutable or constant) bit. Instances of these classes should behave as pointers in principle, though we don't yet have tools to make them behave this way syntactically (that comes next week). In the meantime, let's use the following interface: • ‹bool get()› – read the pointed-to bit, • ‹void set( bool )› – write the same, • ‹void advance()› – move to the next bit, • ‹void advance( int )› – move by a given number of bits, • ‹bool valid()› – is the pointer valid? A default-constructed ‹bitptr› is not valid. Moving an invalid ‹bitptr› results in another invalid ‹bitptr›. Otherwise, a ‹bitptr› is constructed from a ‹std::byte› pointer and an ‹int› with value between 0 and 7 (with 0 being the least-significant bit). A ‹bitptr› constructed this way is always considered valid, regardless of the value of the ‹std::byte› pointer passed to it. class bitptr; /* C */ class const_bitptr; ### 6. [‹sort›] Implement ‹sort› which works both on vectors (‹std::vector›) and linked lists (‹std::list›) of integers. The former should use in-place quicksort, while the latter should use merge sort (it's okay to use the ‹splice› and ‹merge› methods on lists, but not ‹sort›). Feel free to refer back to ‹01/r5› for the quicksort.