Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

interval _ map is a data structure that associates keys of type K with values of type V . It is designed to be used

interval_map is a data structure that associates keys of type K with values of type V. It is designed to be used efficiently in situations where intervals of consecutive keys are associated with the same value. Your task is to implement the assign member function of this data structure, which is outlined below.
interval_map is implemented on top of std::map. For more information on std::map, you may refer to cppreference.com.
Each key-value-pair (k,v) in interval_map::m_map means that the value v is associated with all keys from k (including) to the next key (excluding) in m_map. The member interval_map::m_valBegin holds the value that is associated with all keys less than the first key in m_map.
Example: Let M be an instance of interval_map where
M.m_valBegin=='A',
M.m_map=={(1,'B'),(3,'A')},
Then M represents the mapping
...
-2->'A'
-1->'A'
0->'A'
1->'B'
2->'B'
3->'A'
4->'A'
5->'A'
...
The representation in the std::map must be canonical, that is, consecutive map entries must not contain the same value: ...,(3,'A'),(5,'A'),... is not allowed. Likewise, the first entry in m_map must not contain the same value as m_valBegin. Initially, the whole range of K is associated with a given initial value, passed to the constructor of the interval_map data structure.
Key type K
- besides being copyable and assignable, is less-than comparable via operator<, and
- does not implement any other operations, in particular no equality comparison or arithmetic operators.
Value type V
- besides being copyable and assignable, is equality-comparable via operator==, and
- does not implement any other operations.
Your task is to implement the function assign. Your implementation is graded by the following criteria in this order:
Type requirements are met: You must adhere to the specification of the key and value type given above.
Correctness: Your program should produce a working interval_map with the behavior described above. In particular, pay attention to the validity of iterators. It is illegal to dereference end iterators. Consider using a checking STL implementation such as the one shipped with Visual C++ or GCC.
Canonicity: The representation in m_map must be canonical.
Running time: Imagine your implementation is part of a library, so it should be big-O optimal. In addition:
Do not make big-O more operations on K and V than necessary because you do not know how fast operations on K/V are; remember that constructions, destructions and assignments are operations as well.
Do not make more than one operation of amortized O(log N), in contrast to O(1), running time, where N is the number of elements in m_map.
Otherwise favor simplicity over minor speed improvements.
My code thus far!!! Please help in C++, I keep failing requirement 1! All other requirements are working!
1. Type requirements are met: You must adhere to the specification of the key and value type given above.
Code:
```
#include
#include
template
class interval_map {
friend void IntervalMapTest();
V m_valBegin;
std::map m_map;
public:
// Constructor associates the whole range of K with val
interval_map(V const& val) : m_valBegin(val){}
// Assign value val to the interval [keyBegin, keyEnd)
void assign(K const& keyBegin, K const& keyEnd, V const& val){
if (!(keyBegin < keyEnd)){
return; // empty interval, do nothing
}
auto itLow = m_map.lower_bound(keyBegin);
if (itLow != m_map.begin()){
auto itPrev = std::prev(itLow);
if (itPrev->second == val){
itLow = m_map.erase(itLow);
}
}
auto itHigh = m_map.lower_bound(keyEnd);
if (itLow != itHigh){
m_map.erase(itLow, itHigh);
}
m_map[keyEnd]=(itHigh != m_map.end())? itHigh->second : m_valBegin;
if (m_valBegin != val ||(itLow == m_map.begin() && keyBegin != m_map.begin()->first)){
m_map[keyBegin]= val;
}
if (keyBegin == m_map.begin()->first && m_valBegin == val){
m_map.erase(m_map.begin());
}
}
// Look-up 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;
}
}
};
int main(){
interval_map M('A');
M.assign(1,4,'B');
M.assign(8,9,'C');
for (int i =-2; i <9; ++i){
std::cout << M[i]<< std::endl;
}
return 0;
}
```

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Oracle Database 11g SQL

Authors: Jason Price

1st Edition

0071498508, 978-0071498500

More Books

Students also viewed these Databases questions