In this project, you will be implementing a doubly linked list. This means that each node has two pointers: to the element before it in the list and to the element after it in the list. Furthermore, you will need to keep the list in order. Other specifics of private member data is up to you.
We are implementing two templated types. In particular, every node stores two pieces of information: a key and a value. The keys are what you are keeping in sorted order. This is an idea behind a "map" interface; keys are how we look up information, while values are the information associated with the keys. To some extent, you are implementing an ordered map in this project, although the manner by which we are implementing it in this project is not how std::map is implemented
This section provides you an overview of the functions to implement. For some functions, there is more detail provided in SortedList.hpp
Your implementation must be a doubly linked list.
You may not add any additional #include directives. Furthermore, you may not use any container classes, for any reason. Using a container class (such as std::map) within your SortedList.
You may, and are encouraged to, add "helper functions" -- making one or more additional private member functions to the existing classes. If you so choose, you may also add public functions. Do not remove from the public interface : our grading programs expect them to be in this format. If you change or remove an existing function, it is possible that your program will not compile when we attempt to grade it: this will result in a zero for the project. Since this project is a sizable part of your grade, this would be very bad.
Be very careful with your use of generic types, and be sure to check your GenericQueue.
SortedList.hpp
#ifndef __SORTED_DOUBLY_LINKED_LIST_HPP
#define __SORTED_DOUBLY_LINKED_LIST_HPP
#include < stdexcept >
class KeyNotFoundException : public std::runtime_error
{
public:
explicit KeyNotFoundException(const std::string & err) : std::runtime_error(err) {}
};
template< typename Key, typename Value >
class SortedList
{
private:
// fill in private member data here
public:
SortedList();
// Note: copy constructors are required.
// Be sure to do a "deep copy" -- if I
// make a copy and modify one, it should not affect the other.
SortedList(const SortedList & st);
SortedList & operator=(const SortedList & st);
~SortedList();
size_t size() const noexcept;
bool isEmpty() const noexcept;
// If this key is already present, return false.
// otherwise, return true after inserting this key/value pair.
bool insert(const Key &k, const Value &v);
// Return true if this SortedList contains a mapping of this key.
bool contains(const Key &k) const noexcept;
// removes the given key (and its associated value) from the list.
// If that key is not in the list, this will silently do nothing.
void remove(const Key &k);
// If this key exists in the list, this function returns how many keys are in the list that are less than it.
// If this key does not exist in the list, this throws a KeyNotFoundException.
unsigned getIndex(const Key &k) const;
// If this key does not exist in the list, this throws a KeyNotFoundException.
// subscript operator for non-const objects returns modifiable lvalue
Value & operator[] (const Key &k) ;
// subscript operator for nonconst objects returns non-modifiable lvalue
// DON'T FORGET TO TEST THIS FUNCTION EXPLICITLY
// I omitted it from required test cases on purpose.
// Write a test case that calls this -- I showed you how in class a few times.
// In projects like this (which also come up in ICS 46), forgetting to test this
// is a major cause of lost points, sometimes disproportionate to how easy the fix is.
// Don't let that happen to you.
// (I'd rather it doesn't happen to anyone)
const Value & operator [] (const Key & k) const;
// returns the largest key in the list that is < the given key.
// If no such element exists, this throws a KeyNotFoundException.
// Hint: think carefully about the situation where none would exist.
// Think also very carefully about how this is different
// from the subscript operator functions and the getIndex function.
// A little bit of thinking ahead of time will make this *much easier* to program.
const Key & largestLessThan(const Key & k) const;
// This is similar to the previous one, but has some key (pun intended) differences.
// I recommend you finish the previous function and *extensively* test it first.
// (be sure to think about boundary cases!)
// THEN, think carefully about how this differs from that -- you might want to
// approach it slightly differently than you approached that one.
// The time you spend thinking about this will likely save you even more time
// when you can code this quicker and have fewer bugs.
// There's no prize for "first to finish this function." Write the previous one first.
const Key & smallestGreaterThan(const Key & k) const;
// Two SortedLists are equal if and only if:
// * They have the same number of elements
// * Each element matches in both key and value.
// This is only a meaningful operator when key-type and value-type both have
// an implemented operator==. As such, we will only test with those.
bool operator==(const SortedList & l) const noexcept;
// preincrement every Value (not key) in the list.
// Unlike a numeric type's ++ operator, this does not return a copy of itself.
// Note that this is silly and is done explicitly to have overload this operator
// in this assignment.
// Because the syntax of pre-incrementing an element can be weird, although
// it is what you probably think it is, for purposes of this assignment, I will
// only test this with value-types whose pre-increment and post-increment
// operators have the same end-state.
void operator++();
};
template< typename Key, typename Value >
SortedList< Key,Value >::SortedList()
{}
template< typename Key, typename Value >
SortedList< Key,Value >::SortedList(const SortedList & st)
{
}
template< typename Key, typename Value >
SortedList< Key,Value > & SortedList< Key,Value >::operator=(const SortedList & st)
{
if( this != &st )
{
}
return *this;
}
template< typename Key, typename Value >
SortedList< Key,Value >::~SortedList()
{
}
template< typename Key, typename Value >
size_t SortedList< Key,Value >::size() const noexcept
{
return 0; // STUB; fix then remove this comment
}
template< typename Key, typename Value >
bool SortedList< Key,Value >::isEmpty() const noexcept
{
return false; // STUB; fix then remove this comment
}
// If this key is already present, return false.
// otherwise, return true after inserting this key/value pair/.
template< typename Key, typename Value >
bool SortedList< Key,Value >::insert(const Key &k, const Value &v)
{
return false; // STUB; fix then remove this comment
}
template< typename Key, typename Value >
bool SortedList< Key,Value >::contains(const Key &k) const noexcept
{
return false; // STUB; fix then remove this comment
}
template< typename Key, typename Value >
void SortedList< Key,Value >::remove(const Key &k)
{
}
// If this key exists in the list, this function returns how many keys are in the list that are less than it.
// If this key does not exist in the list, this throws a KeyNotFoundException.
template< typename Key, typename Value >
unsigned SortedList< Key,Value >::getIndex(const Key &k) const
{
throw KeyNotFoundException{"Key not found in list"}; // STUB; fix then remove this comment
}
template< typename Key, typename Value >
Value & SortedList< Key,Value >::operator[] (const Key &k)
{
throw KeyNotFoundException{"Key not found in list"}; // STUB; fix then remove this comment
}
template< typename Key, typename Value >
const Value & SortedList< Key,Value >::operator[] (const Key &k) const
{
throw KeyNotFoundException{"Key not found in list"}; // STUB; fix then remove this comment
}
template< typename Key, typename Value >
const Key & SortedList< Key,Value >::largestLessThan(const Key & k) const
{
throw KeyNotFoundException{"Key not found in list"}; // STUB; fix then remove this comment
}
template< typename Key, typename Value >
const Key & SortedList< Key,Value >::smallestGreaterThan(const Key & k) const
{
throw KeyNotFoundException{"Key not found in list"}; // STUB; fix then remove this comment
}
template < typename Key, typename Value >
bool SortedList< Key,Value >::operator==(const SortedList & l) const noexcept
{
return false; // STUB; fix then remove this comment
}
template < typename Key, typename Value >
void SortedList< Key,Value >::operator++()
{
}
#endif
sortedlistttests.cpp
#include "catch_amalgamated.hpp"
#include < string >
#include "SortedList.hpp"
namespace{
TEST_CASE("PreliminaryTests", "[RequiredOne]")
{
SortedList< unsigned, std::string > l;
l.insert(1, "One");
l.insert(2, "Two");
l.insert(3, "Three");
REQUIRE(l.contains(1));
REQUIRE(l.contains(2));
REQUIRE(l.contains(3));
REQUIRE(! l.contains(4) );
REQUIRE(! l.contains(0) );
REQUIRE(l.size() == 3);
REQUIRE(! l.isEmpty() );
}
TEST_CASE("ReverseInserts", "[RequiredOne]")
{
SortedList< unsigned, std::string > l;
l.insert(3, "Three");
l.insert(2, "Two");
l.insert(1, "One");
REQUIRE(l.contains(1));
REQUIRE(l.contains(2));
REQUIRE(l.contains(3));
REQUIRE(! l.contains(4) );
REQUIRE(! l.contains(0) );
}
TEST_CASE("MyFirstRemovals1", "[RequiredOne]")
{
SortedList< unsigned, std::string > l;
l.insert(1, "One");
l.insert(2, "Two");
l.insert(3, "Three");
l.remove(1);
REQUIRE(! l.contains(1));
REQUIRE(l.contains(2));
REQUIRE(l.contains(3));
REQUIRE(! l.contains(4) );
}
TEST_CASE("MyFirstRemovals2", "[Explanatory]")
{
SortedList< unsigned, std::string > l;
l.insert(1, "One");
l.insert(2, "Two");
l.insert(3, "Three");
l.remove(2);
REQUIRE(l.contains(1));
REQUIRE(! l.contains(2));
REQUIRE(l.contains(3));
REQUIRE(! l.contains(4) );
}
TEST_CASE("MyFirstRemovals3", "[Explanatory]")
{
SortedList< unsigned, std::string > l;
l.insert(1, "One");
l.insert(2, "Two");
l.insert(3, "Three");
l.remove(3);
REQUIRE(l.contains(1));
REQUIRE(l.contains(2));
REQUIRE(! l.contains(3));
REQUIRE(! l.contains(4) );
}
TEST_CASE("ContainsWithCarmichaelNumbers", "[Explanatory]")
{
// because Carmichael numbers are fun
SortedList< unsigned, std::string > cms;
cms.insert(561, "First");
cms.insert(1105, "Second");
cms.insert(1729, "Third");
cms.insert(2465, "Fourth");
REQUIRE(cms.getIndex(561) == 0);
REQUIRE(cms.getIndex(1105) == 1);
REQUIRE(cms.getIndex(1729) == 2);
REQUIRE(cms.getIndex(2465) == 3);
REQUIRE_THROWS_AS( cms.getIndex(600), KeyNotFoundException );
REQUIRE_THROWS_AS( cms.getIndex(6000), KeyNotFoundException );
}
TEST_CASE("LargestLessThanTest1", "[RequiredTwo]")
{
SortedList< unsigned, std::string > cms;
cms.insert(561, "First");
cms.insert(1105, "Second");
cms.insert(1729, "Third");
cms.insert(2465, "Fourth");
REQUIRE_THROWS_AS( cms.largestLessThan(560), KeyNotFoundException );
REQUIRE_THROWS_AS( cms.largestLessThan(561), KeyNotFoundException );
REQUIRE( cms.largestLessThan(1104) == 561 );
REQUIRE( cms.largestLessThan(1728) == 1105 );
REQUIRE( cms.largestLessThan(1900) == 1729 );
REQUIRE( cms.largestLessThan(2470) == 2465 );
REQUIRE( cms.largestLessThan(4096) == 2465 );
}
// Note that this is not "required" in the sense of getting this section graded.
// However, I strongly suggest you get this case working. Just because it isn't
// in the "required" category doesn't mean I won't be grading things like this.
// (Or maybe I'll even have this as a grading test, who knows?)
TEST_CASE("SmallestGreaterThanTest1", "[Explanatory]")
{
SortedList< unsigned, std::string > cms;
cms.insert(561, "First");
cms.insert(1105, "Second");
cms.insert(1729, "Third");
cms.insert(2465, "Fourth");
REQUIRE_THROWS_AS( cms.smallestGreaterThan(2470), KeyNotFoundException );
REQUIRE_THROWS_AS( cms.smallestGreaterThan(4096), KeyNotFoundException );
REQUIRE( cms.smallestGreaterThan(560) == 561 );
REQUIRE( cms.smallestGreaterThan(1) == 561 );
REQUIRE( cms.smallestGreaterThan(562) == 1105 );
REQUIRE( cms.smallestGreaterThan(1728) == 1729 );
REQUIRE( cms.smallestGreaterThan(2048) == 2465 );
}
TEST_CASE("EveryonesCopyAndAssignmentOperatorCanBeGraded", "[RequiredThree]")
{
/*
Our grading script requires that every segment have
at least one "required" test case.
This test case will pass for *everyone*
Be sure to test your copy constructor and assignment operator!
Our grading test cases will be more thorough than this one.
*/
REQUIRE(true);
}
TEST_CASE("SubscriptOperatorAsAccessor", "[RequiredFour]")
{
SortedList< unsigned, std::string > cms;
cms.insert(561, "First");
cms.insert(1105, "Secnod");
cms.insert(1729, "Thrid");
cms.insert(2465, "Fourth");
REQUIRE(cms[561] == "First");
REQUIRE(cms[1105] == "Secnod");
REQUIRE(cms[1729] == "Thrid");
REQUIRE(cms[2465] == "Fourth");
REQUIRE_THROWS_AS( cms[600], KeyNotFoundException );
REQUIRE_THROWS_AS( cms[6000], KeyNotFoundException );
}
TEST_CASE("SubscriptOperatorReturnsReference", "[RequiredFour]")
{
SortedList< unsigned, std::string > cms;
cms.insert(561, "First");
cms.insert(1105, "Secnod");
cms.insert(1729, "Thrid");
cms.insert(2465, "Fourth");
// oops, let's fix those typos.
cms[1105] = "Second";
cms[1729] = "Third";
REQUIRE(cms[561] == "First");
REQUIRE(cms[1105] == "Second");
REQUIRE(cms[1729] == "Third");
REQUIRE(cms[2465] == "Fourth");
}
// don't forget to test the const version too. See your notes for how to do this!
/*
Note that none of the "required" test cases in part four
use the ++ or == operators. We will still be grading these,
for obvious reasons.
*/
TEST_CASE("SimpleTestsOfEquality", "[Explanatory]")
{
SortedList< unsigned, std::string > l1;
SortedList< unsigned, std::string > l2;
REQUIRE(l1 == l2);
l1.insert(561, "First");
REQUIRE(!(l1 == l2));
l2.insert(561, "First");
REQUIRE(l1==l2);
}
TEST_CASE("Testing++Operator", "[Explanatory]")
{
SortedList< std::string, unsigned > numbers;
numbers.insert("Jenny", 8675309);
++numbers;
REQUIRE(numbers["Jenny"] == 8675310); // that hurt to type.
}
} // end namespace