Click here to Skip to main content
15,886,724 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hi Team

I am trying to implement an assign function together with test case for this program using interval map in c++ my program somehow is compiling this below error. "
prog.cc:210:1: error: a template declaration cannot appear at block scope
 template<typename K, typename V>
 ^~~~~~~~
prog.cc:243:1: error: 'namespace' definition is not allowed here
 namespace unit_test {
 ^~~~~~~~~
prog.cc:257:12: error: a function-definition is not allowed here before '{' token
 int main() {
            ^
prog.cc: In function 'void unit_test::IntervalMapTest()':
prog.cc:458:8: error: 'cout' is not a member of 'unit_test::std'
   std::cout << "Unit test will run here." << std::endl;
        ^~~~
prog.cc:458:51: error: 'endl' is not a member of 'unit_test::std'
   std::cout << "Unit test will run here." << std::endl;
                                                   ^~~~
"

What I have tried:

#include <iostream>
#include <map>
#include <limits>

template<typename K, typename V>
class IntervalMap {
public:
    IntervalMap(V const& val)
    : m_map({{std::numeric_limits<K>::lowest(), val}})
    {
    }
    
    void assign(K const& keyBegin, K const& keyEnd, V const& val) {
        auto beginIter = m_map.lower_bound(keyBegin);
        auto endIter = m_map.upper_bound(keyEnd);
        
        V const& prevVal = (--beginIter)->second;
        if (prevVal == val) {
            // If the new value is the same as the previous value, erase the
            // entries in the map that fall within the new interval.
            m_map.erase(beginIter, endIter);
        } else {
            // Otherwise, insert a new entry into the map for the new interval.
            m_map.erase(beginIter, endIter);
            m_map.emplace(keyBegin, val);
            m_map.emplace(keyEnd, prevVal);
        }
    }
    
    V const& operator[](K const& key) const {
        return (--m_map.upper_bound(key))->second;
    }

private:
    std::map<K, V> m_map;
};

namespace unit_test {
    void IntervalMapTest() {
        std::cout << "Unit test will run here." << std::endl;
        IntervalMap<int, char> imap('A');
        imap.assign(1, 5, 'B');
        imap.assign(3, 7, 'C');
        imap.assign(8, 10, 'D');
        imap.assign(1, 10, 'E');
        for (int i = 0; i <= 10; ++i) {
            std::cout << i << ": " << imap[i] << std::endl;
        }
    }
}

int main() {
    unit_test::IntervalMapTest();
    return 0;
}


// the program is given as this as a problem before implementation(instruction)
#include <iostream>
#include <algorithm>
#include <list>
#include <map>
#include <limits>
#include <iterator>
// #include <algorithm>


template<typename T>
class ThinkCellKey : std::numeric_limits<T>{
	T v;

public:
  ThinkCellKey( T const& val) {
    v = val;
  }

  // inline bool operator< (const ThinkCellKey & s1, const ThinkCellKey & s2) {
  //   return  s1.v < s2.v;
  // }

  // overloaded < operator
  bool operator <(const ThinkCellKey& d) const {
    return v < d.v;
  }

  ThinkCellKey operator ++(int) {
    this->v++;
    return *this;
  }

  ThinkCellKey operator --(int) {
    this->v--;
    return *this;
  }

  friend std::ostream & operator << (std::ostream &out, const ThinkCellKey<T> &c) {
      out << c.v;
      return out;
  }

  static const ThinkCellKey<T> lowest() {
    return std::numeric_limits<T>::lowest();
  }

  // ThinkCellKey& operator= (const ThinkCellKey&) {
  //   return *this;
  // }
};

template<typename K, typename V>
class interval_map {
	std::map<K,V> m_map;

public:
  // constructor associates whole range of K with val by inserting (K_min, val)
  // into the map
  interval_map( V const& val) {
    m_map.insert(m_map.end(),std::make_pair(std::numeric_limits<K>::lowest(),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 (!(keyBegin < keyEnd))
      return;

    // if inserting into range of the same value before, don't insert
    // if the value existing already after out pointer, erase it
    auto before_begin_bound = m_map.lower_bound(keyBegin);
    if (before_begin_bound != m_map.begin()) {
      --before_begin_bound;
    }
    auto insert_res = before_begin_bound->second == val ?
      before_begin_bound : m_map.insert_or_assign(before_begin_bound, keyBegin, val);

    auto end_interval = m_map.lower_bound(keyEnd);

    if (end_interval != m_map.end() && end_interval->second == val)
      end_interval++;

    insert_res++;
    m_map.erase(insert_res, end_interval);

    if (end_interval == m_map.end())
      this->assign(keyEnd, std::numeric_limits<K>::max(), before_begin_bound->second);
    else
      this->assign(keyEnd, end_interval->first, before_begin_bound->second);
  }

  // look-up of the value associated with key
  V const& operator[]( K const& key ) const {
    return ( --m_map.upper_bound(key) )->second;
  }


	// a print function for debugging
	void show() {
		std::cout << "show" << std::endl;
		for(auto entry : m_map) {
			std::cout << entry.first << entry.second << std::endl;
		}
	}
};

// 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 unsigned int intervals to char.


int main(int argc, char* argv[])
{
  // TODO: test interval map with different stl algorithm methods
  // TODO: make 4 spaces tab
  // interval_map<ThinkCellKey<unsigned int>, char> imap {'a'};
  interval_map<unsigned int, char> imap {'A'};

  // imap.assign(3, 5, 'B');
  // imap.assign(5, 7, 'C');
  // imap.assign(2, 7, 'D');


  // imap.assign(8, 10, 'k');

  imap.assign(8, 12, 'k');
	imap.assign(2, 12, 'k');
	imap.assign(2, 12, 'b');
	imap.assign(5, 12, 'b');
	imap.assign(4, 10, 'b');
	imap.assign(4, 12, 'b');
	imap.assign(8, 13, 'a');
  imap.assign(6, 9, 'j');


  // imap.assign(4, 4, 'j'); // its ok 
	// imap.assign(0, 10, 'e');
	// imap.assign(0, 10, 'e');

  // imap.assign(2,6, 'B');
  // imap.assign(3,10, 'C');
  // imap.assign(4, 7, 'B');
  // imap.assign(3, 5, 'B');

  imap.show();
  return 0;
}
Posted
Updated 19-Apr-23 5:07am
Comments
k5054 19-Apr-23 11:14am    
This compiles cleanly on compiler explorer, where I tested g++ 8.5, g++ 12 and MSVC v19.30. So its one of: you're using a broken compiler, you've posted the wrong code or your compiler flags are wrong - i.e. trying to compile this with C++ 98. It compiles cleanly with gcc C++11, C++ 14, C++17 and C++20.

1 solution

The only thing that stands out to me is this line :
C++
IntervalMap(V const& val)
: m_map({{std::numeric_limits<K>::lowest(), val}})
{
}
I think the compiler does not like all those curly braces there so it should look like this :
C++
IntervalMap( V const& val )
    : m_map( std::numeric_limits<K>::lowest(), val )
{
}
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900