#include <iostream>
#include <map>
template<typename T>
bool is_lt(const T& lhs, const T& rhs) noexcept {
return ( lhs < rhs );
}
template<typename T>
bool is_gt(const T& lhs, const T& rhs) noexcept {
return !is_lt(lhs,rhs);
}
template<typename T>
bool is_eq(const T& lhs, const T& rhs) noexcept {
return is_lt(lhs,rhs) == is_lt(rhs,lhs);
}
template<typename K, typename V>
class interval_map {
friend void IntervalMapTest();
V m_valBegin;
std::map<K,V> m_map;
public:
// constructor associates whole range of K with val
interval_map(V const& val)
: m_valBegin(val)
{}
// Assign value val to interval [keyBegin, keyEnd).
// Overwrite previous values in this interval.
// Conforming to the C++ Standard Library conventions, the interval
// includes keyBegin, but excludes keyEnd.
// If !( keyBegin < keyEnd ), this designates an empty interval,
// and assign must do nothing.
void assign( K const& keyBegin, K const& keyEnd, V const& val ) {
// INSERT YOUR SOLUTION HERE
if ( auto iter = m_map.lower_bound(keyBegin) ; iter == m_map.end() ){
// No values present with Key KeyBegin
m_map.emplace_hint(iter,keyBegin,val);
m_map.emplace_hint(iter,keyEnd,m_valBegin);
return;
}
if (auto iter = m_map.lower_bound(keyBegin) ; iter != m_map.end() ){
//few values found ,
//if iter-- has val , implies prev range also has val
//skip next elements ??
//If iter found... chk keyBegin == iter->key &
//means ... we need to update the current iter->value.
//Keep it current iter<K,V>::value in temp
//insert KeyEnd , temp
if (is_eq(keyBegin,iter->first) ){
auto tmp =iter->second;
//auto iter2 = m_map.emplace_hint(iter,keyBegin,val);
iter->second = val;
m_map.emplace_hint(iter,keyEnd,tmp);
return;
}
//If iter found... chk keyBegin < iter->key &
//means ... we need to insert keyBegin 1 position behind.
//Keep it current iter<K,V>::value in temp
//insert KeyEnd , temp
//if (!( iter->first < keyBegin )){
if ( is_lt(keyBegin,iter->first)){
--iter;
auto tmp =iter->second;
auto iter2 = m_map.emplace_hint(iter,keyBegin,val);
m_map.emplace_hint(iter2,keyEnd,tmp);
return;
}
//Assuming no overlapping keys
auto iter2 = m_map.emplace_hint(iter,keyBegin,val);
//m_map.emplace_hint(iter,keyBegin,val);
while (iter2!=m_map.end()&& iter2->first < keyEnd ){
iter2++;
}
if (iter2 == m_map.end()){
m_map.emplace_hint(iter2,keyEnd,m_valBegin);
}else{
//?? TODO
}
}
}
// look-up of the value associated with key
V const& operator[]( K const& key ) const {
auto it=m_map.upper_bound(key);
if(it==m_map.begin()) {
return m_valBegin;
} else {
return (--it)->second;
}
}
void __print(){
std::cout<< " Key: -Inf " << " Val: "<<m_valBegin <<std::endl;
for ( const auto &[key,val] : m_map) {
std::cout<< " Key:" <<key << " Val:"<<val << " | {" << key << ", "<<val <<" }"<<std::endl;
}
std::cout<< " Key: +Inf " << " Val: "<<m_valBegin <<std::endl;
}
void __xtra_print(){
std::cout<< "\n { -Inf," << m_valBegin<<" },";
auto prev_key =0;
auto prev_val =' ';
for ( const auto &[key,val] : m_map) {
while (++prev_key < key){
std::cout<< "<"<<prev_key<<","<<prev_val <<">,";
}
std::cout<< "{"<<key<<" ,"<<val <<"},";
prev_key = key;
prev_val = val;
}
std::cout<< " { +Inf ," <<m_valBegin <<" }"<<std::endl;
}
bool isCannonical(){
bool isCnnl = true;
V prev_val= m_valBegin;
for ( const auto &[key,val] : m_map) {
if ( is_eq(prev_val,val)){
isCnnl = false;
std::cout<< " Key:" <<key << " Val:"<<val << " Cannonical property breaks here !! "<<std::endl;
break;
}
prev_val = val;
}
return isCnnl;
}
};
// Many solutions we receive are incorrect. Consider using a randomized test
// to discover the cases that your implementation does not handle correctly.
// We recommend to implement a test function that tests the functionality of
// the interval_map, for example using a map of int intervals to char.
int main (){
interval_map<int ,char> imap('X');
std::cout<< " Assign 1,10,A " <<std::endl;
imap.assign(1,10,'A');
imap.__print();
imap.__xtra_print();
imap.isCannonical();
std::cout<< " -------------" <<std::endl;
std::cout<< " Assign 4,8,B " <<std::endl;
imap.assign(4,8,'B');
imap.__print();
imap.__xtra_print();
imap.isCannonical();
std::cout<< " -------------" <<std::endl;
std::cout<< " Assign 10,15,C " <<std::endl;
imap.assign(10,15,'C');
imap.__print();
imap.__xtra_print();
imap.isCannonical();
std::cout<< " -------------" <<std::endl;
std::cout<< " Assign 7,11,A " <<std::endl;
imap.assign(7,11,'A');
imap.__print();
imap.__xtra_print();
imap.isCannonical();
}
