Untitled

 avatar
unknown
plain_text
a year ago
5.3 kB
5
Indexable
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 ) 
    {
        // if map empty 
                //if !(val == m_valBegin)
                    //assign (keyBegin, val) and (keyEnd, m_valBegin)
        if (m_map.empty())
        {
            if (!(val == m_valBegin))
            {
                //m_map[keyBegin] = val;
                //m_map[keyEnd] = m_valBegin;
                m_map.insert_or_assign(keyBegin, val);                
                m_map.insert_or_assign(keyEnd, m_valBegin);
            }
        }
                    
            //else if keybegin is at the end
                //if !(val == m_valBegin)
                    //assign (keybegin, val) and (keyEnd, m_valBegin)
        else if ((--m_map.end())->first < keyBegin)
        {
            if (!(val == m_valBegin))
            {
                //m_map[keyBegin] = val;
                //m_map[keyEnd] = m_valBegin;
                m_map.insert_or_assign(keyBegin, val);                
                m_map.insert_or_assign(keyEnd, m_valBegin);
            }
        }
                
            //else if keybegin is at the start 
                //if (val == m_valBegin)
                    //remove all entries up to keyEnd and assign (keyEnd, lastEntry removed val) if no entry removed dont assign anything
                //else
                    //assign (keyBegin, val) remove entries up to keyEnd remember the last removed entry val
                    //assign (keyEnd, lastEntry removed val if none then m_valBegin) Note: we dont have to look past because next cant be the same            
                
        else if (!(m_map.begin()->first < keyBegin))
        {
            if (val == m_valBegin)
            {
                V tempval = (m_map.lower_bound(keyEnd)--)->second;
                if (m_map.erase(m_map.lower_bound(keyBegin), m_map.lower_bound(keyEnd)) != 0)
                {
                    //m_map[keyEnd] = tempval;
                    m_map.insert_or_assign(keyEnd, tempval);
                }
            }
            
            else
            {
                //m_map[keyBegin] = val;
                m_map.insert_or_assign(keyBegin, val);
                V tempval = (m_map.lower_bound(keyEnd)--)->second;
                if (m_map.erase(m_map.lower_bound(keyBegin), m_map.lower_bound(keyEnd)) != 0)
                {
                    //m_map[keyEnd] = tempval;
                    m_map.insert_or_assign(keyEnd, tempval);
                }
                
                else
                {
                    //m_map[keyEnd] = m_valBegin;
                    m_map.insert_or_assign(keyEnd, m_valBegin);
                }
            }
        }
            //else if keybegin is in the middle need to check previous entry
                //if prev entry val not the same as val assign (beginKey, val)
                //remove entries until keyEnd store last entry removed val
                //if none removed and starting val same as curVal do nothing
                //else if none removed and starting val not the same as curVal assign (keyEnd, prevEntry before beinKey val) 
                //else assign (keyEnd, last removed entry val)
        else 
        {
            V beginTempVal = (m_map.lower_bound(keyBegin)--)->second;
            
            if (beginTempVal != val)
            {
                //m_map[keyBegin] = val;
                m_map.insert_or_assign(keyBegin, val);
            }
            
            V tempval = (m_map.lower_bound(keyEnd)--)->second;
            int eraseCount = m_map.erase(m_map.lower_bound(keyBegin), m_map.lower_bound(keyEnd));
            
            if (eraseCount == 0 && beginTempVal == val) {}            
            
            else if (eraseCount == 0 && beginTempVal != val)
            {
                //m_map[keyEnd] = beginTempVal;
                m_map.insert_or_assign(keyEnd, beginTempVal);
            }
            
            else
            {
                //m_map[keyEnd] = tempval;
                m_map.insert_or_assign(keyEnd, tempval);
            }
        }
    }

	// 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 printMap()
    {
        for(auto it = m_map.begin(); it != m_map.end(); it++)
        {
            cout<< it->first << " " << it->second << " | ";
        }
        cout <<endl;
    }
};

int main()
{
    interval_map<int, char> IM ('A');
    IM.printMap();
    IM.assign(1,6,'b');
}
Editor is loading...
Leave a Comment