Homework SourseNeed help with the replace function in C code needs to be in
Need help with the replace function in C++.. code needs to be in C++. Function body is the ones in the bold letters.
#ifndef PERSISTENT_VECTOR_H
#define PERSISTENT_VECTOR_H
#include
#include
#include
#include
#include
template
class persistent_vector {
private:
class node {
public:
virtual ~node() {}
virtual void print_details() const = 0;
virtual const T& index(size_t height, size_t index) const = 0;
// virtual std::shared_ptr replace(size_t height, size_t index, const T& value) const = 0;
virtual std::shared_ptr push_back(size_t height, size_t index, const T& value) const = 0;
};
typedef std::shared_ptr node_ptr;
class leaf_node : public node {
public:
leaf_node(const T& first ): m_values { first } { }
leaf_node(const T& first, const T& second ) : m_values { first, second} { }
virtual ~leaf_node() { }
void print_details() const {
std::cout << \"leaf \" << this << \" :\";
for(auto& value : m_values) std::cout << \" \" << value;
std::cout << std::endl;
}
const T& index(size_t height, size_t index) const { return m_values.at(index&1); }
/*
node_ptr replace(size_t height, size_t index, const T& value) const {
}
*/
node_ptr push_back(size_t height, size_t index, const T& value) const {
return std::make_shared( m_values[0], value );
}
private:
const std::vector m_values;
};
static bool go_right(size_t index, size_t height) { return index&(1< static bool full_tree(size_t size, size_t height) { return size == (1<<(height+1)); }
static node_ptr make_chain(size_t length, const T& value) {
if (length==0) return std::make_shared(value);
return std::make_shared(make_chain(length-1,value));
}
class internal_node : public node {
public:
internal_node(const node_ptr& left, const node_ptr& right ) : m_left(left), m_right(right) { }
internal_node(const node_ptr& left) : m_left(left) { }
virtual ~internal_node() { }
void print_details() const {
std::cout << \"node \" << this << \" : \" << m_left.get() << \" \" << m_right.get() << std::endl;
m_left->print_details();
if ( m_right ) m_right->print_details();
}
const T& index(size_t height, size_t index) const {
return (go_right(index,height)?m_right:m_left)->index(height-1,index);
}
/*
node_ptr replace(size_t height, size_t index, const T& value) const {
}
*/
node_ptr push_back(size_t height, size_t index, const T& value) const {
if ( go_right(index,height) )
return std::make_shared( m_left,
m_right?m_right->push_back(height-1,index,value):
make_chain(height-1,value) );
return std::make_shared( m_left->push_back(height-1,index,value), m_right);
}
private:
const node_ptr m_left;
const node_ptr m_right;
};
template
std::vector make_pairs(const vector_type& v){
std::vector nodes;
for(size_t i=0; i < v.size(); i+=2 ) {
if ( i+1 < v.size() ) nodes.push_back(std::make_shared(v[i],v[i+1]));
else nodes.push_back(std::make_shared(v[i]));
}
return nodes;
}
node_ptr build_tree(const std::vector& v) {
switch(v.size()) {
case 0: return node_ptr{};
case 1: return v[0];
default: return build_tree(make_pairs(v));
}
}
size_t compute_height(size_t size) { return (m_size>1)?floor(log2(m_size-1)):0; }
persistent_vector( node_ptr head, size_t size) :
m_head(head), m_size(size), m_height(compute_height(size)) { }
public:
persistent_vector(): m_size(0),m_height(0) {}
persistent_vector(const persistent_vector& other) :
m_head(other.m_head),
m_size(other.m_size),
m_height(other.m_height) {}
persistent_vector(const std::vector& v) :
m_head(build_tree(make_pairs(v))),
m_size(v.size()),
m_height(compute_height(m_size)) {}
const persistent_vector& operator=(const persistent_vector& other) {
m_height = other.m_height;
m_size = other.m_size;
m_head = other.m_head;
return *this;
}
const T& at(size_t index) const {
if ( index >= m_size) throw std::out_of_range(\"out-of-range\");
return m_head->index(m_height,index);
}
const T& operator[](size_t index) const {
return at(index);
}
persistent_vector push_back(const T& value) const {
if(m_size==0) return persistent_vector(std::make_shared(value),1);
if( full_tree(m_size,m_height) )
return persistent_vector(
std::make_shared( m_head,
make_chain(m_height,value)),m_size+1);
return persistent_vector(m_head->push_back(m_height,m_size,value),m_size+1);
}
/*
persistent_vector replace(size_t index, const T& value) const {
if ( index >= m_size) throw std::out_of_range(\"out-of-range\");
}
*/
void print_details() const {
std::cout << \"persistent_vector of \" << m_size
<< \" elements with height \" << m_height << std::endl;
if(m_size) m_head->print_details();
}
private:
node_ptr m_head;
size_t m_size;
size_t m_height;
};
#endif // defined PERSISTENT_VECTOR_H
Solution
#ifndef PERSISTENT_VECTOR_H #define PERSISTENT_VECTOR_H #include
