CS253 HW6: Shift-Over List

Description

For this assignment, you will implement a templated STL-like container called a Shift-Over List, or Sol.

You will turn in a single file, Sol.h. You may use C++11 features.

Template Parameters

An Sol takes three template parameters:

The type to be stored
The amount to promote a value when find is called (default is 1). Behavior is undefined if this value is negative. Whenever you search for an element using find, it’s moved this much closer to the start of the list. The most popular items migrate to the front of the list for quick access.
Comparison functor (defaults to std::less).

Examples

Here are several example programs:

    #include "Sol.h"
    #include <iostream>

    using namespace std;

    int main() {
        Sol<int> foo;

        foo.insert(2);
        foo.insert(5);
        foo.insert(3);

        // Should print "253"
        for (Sol<int>::iterator it = foo.begin(); it != foo.end(); ++it)
            cout << *it;
        cout << '\n';
        return 0;
    }

    #include "Sol.h"
    #include <iostream>
    #include <cassert>
    #include <cstring>
    #include <sstream>

    using namespace std;

    template<typename T>
    string cat(const T &con) {
        ostringstream os;
        for (typename T::iterator it = con.begin(); it != con.end(); ++it)
            os << *it;
        return os.str();
    }

    int main() {
        char data[] = "abcdefghXYZ";
        Sol<char,4> foo(data, data+strlen(data));
        Sol<char,4>::iterator it;

        foo.erase('X');
        cout << cat(foo) << '\n';   // Should print abcdefghYZ
        it = foo.find('Z');
        assert(it != foo.end());
        assert(*it == 'Z');
        cout << cat(foo) << '\n';   // Should print abcdeZfghY
        foo.find('Z');
        cout << cat(foo) << '\n';   // Should print aZbcdefghY
        foo.find('Z');
        cout << cat(foo) << '\n';   // Should print ZabcdefghY

        return 0;
    }

    #include "Sol.h"
    #include <iostream>
    #include <cassert>
    #include <cstring>
    #include <sstream>

    using namespace std;

    template<typename T>
    string cat(const T &con) {
        ostringstream os;
        for (typename T::iterator it = con.begin(); it != con.end(); ++it)
            os << *it;
        return os.str();
    }

    int main() {
        Sol<int> foo;
        for (int i=1; i<=9; i++)
            foo.insert(i);

        cout << cat(foo) << '\n';    // Should print 123456789
        cout << cat(foo+3) << '\n';  // Should print 789123456
        cout << cat(foo) << '\n';    // Should print 123456789
        ++foo;
        cout << cat(foo) << '\n';    // Should print 912345678
        foo -= 2;
        cout << cat(foo) << '\n';    // Should print 234567891

        return 0;
    }

    #include "Sol.h"
    #include <cassert>
    #include <iostream>
    #include <sstream>

    using namespace std;

    // A simple wrapper around a float.
    class Age {
      public:
        Age() : years(0.0) { }
        Age(float y) : years(y) { }
        float years;
    };

    // Note that you CAN'T compare two Age objects using < or ==.
    // This compares two Age objects, but only the integral portion.
    // Therefore, it is NOT the case that 5.3 compares less than 5.4;
    // they’re both the same as far as we’re concerned.
    class AgeCompare {
      public:
        bool operator()(Age a, Age b) const {
            return int(a.years) < int(b.years);
        }
    };

    int main() {
        Sol<Age, 0, AgeCompare> who;
        who.insert(1.25);   // a baby
        who.insert(54.45);  // Jack
        who.insert(20);     // a typical student

        assert(who.find(1.00) != who.end());   // should succeed
        assert(who.find(1.25) != who.end());   // should succeed
        assert(who.find(1.99) != who.end());   // should succeed
        assert(who.find(2.00) == who.end());   // should fail

        assert(who.find(53.45) == who.end());  // should fail
        assert(who.find(54.00) != who.end());  // should succeed
        assert(who.find(54.45) != who.end());  // should succeed
        assert(who.find(54.78) != who.end());  // should succeed
        assert(who.find(55.78) == who.end());  // should fail

        assert(who.find(19.99) == who.end());  // should fail
        assert(who.find(20.00) != who.end());  // should succeed
        assert(who.find(20.11) != who.end());  // should succeed
        assert(who.find(20.99) != who.end());  // should succeed
        assert(who.find(21.00) == who.end());  // should fail
        assert(who.find(21.01) == who.end());  // should fail

        assert(who.count(54.1) == 1);       // Are we using the functor?

        cout << "Success!  Promotions for everyone!\n";
    }

Requirements for stored type

The type stored by this templated class has the following requirements:

Default constructor
Copy constructor
Assignment operator
It is not required that ==, <, etc., be valid for the stored types. Your code must not use such operators—it must use the comparison functor, which should default to the less<T> functor.

Required public types of `Sol`

The following types are required, and have similar meanings as they do in the standard STL containers:

size_type (must be an unsigned integral type)
key_type
value_type
iterator

Required public methods of `Sol`

default constructor
copy constructor
constructor that takes a half-open range of two iterators
- These do not have to be iterators from an Sol.
assignment operator
destructor
iterator begin() const
iterator end() const
bool empty() const
size_type size() const
- Number of data items currently stored
size_type max_size() const
- Maximum possible number of elements allowed by this design
iterator find(const key_type &)
- Look for the first instance of the given value from the start of the list to the end.
- Return an iterator pointing to the given value, after that value was moved forward (toward the start of the container).
- Return end() if not found.
size_type count(const key_type &) const
- Return how many times the given value occurs in the container.
iterator insert(const key_type &)
- Insert this value at the end of the list
- Duplicates are not treated specially.
- Returns an iterator pointing to the newly-inserted value.
iterator insert(iterator, const key_type &)
- Insert this value at the given location.
- Returns an interator pointing to the newly-inserted value.
size_type erase(const key_type &)
- Erase all matching items, returns number of items erased.
void erase(iterator)
- Erase the value at the given location.
void erase(iterator, iterator)
- Erase the values in the half-open range!
void clear()
- Make it have no values.

Required operators

Sol + N or N + Sol (where N is an int)
- Return a copy of Sol, rotated right by N places.
- Undefined behaviour unless 0 ≤ N < size().
Sol - N or N - Sol (where N is an int)
- Return a copy of Sol, rotated left by N places.
- Undefined behaviour unless 0 ≤ N < size().
Sol += N
- Same as Sol = Sol + N;
Sol -= N
- Same as Sol = Sol - N;
Preincrement, postincrement, predecrement, postdecrement
- analogously

Required operations on `Sol::iterator`:

default constructor
copy constructor
assignment operator
destructor
==
!=
indirection
->
pre-/post-increment/decrement

Requirements

We will compile your program with: g++ -std=c++0x
Your header file must have #include guards.
Your header file must not have any using declarations.
You may not use any C++ containers in your implementation. No list, no vector, no set, no string, etc.
You may use C++ algorithms, functors, pair, etc.
You may not use any external programs, e.g., via system, popen, fork, exec, etc.
No memory leaks.
It must be possible for a program have several instances of Sol active at the same time, and they must not interfere with each other.
It is acceptable for insert and erase operations to invalidate all existing iterators. It is also acceptable for insert and erase to not invalidate any iterators. It’s up to you.
A successful find may invalidate iterators pointing to any element moved, but no others.
An element of the Sol may be changed after it has been placed into the collection. *iter = whatever; must compile.
Pay attention to const-correctness. We may try to assign a const Sol to a non-const Sol, take the size() of a const Sol, etc.
Brush your teeth after every meal.
You may add other methods and operators, as needed.
You may implement the methods inside or outside of the class declaration.

Hints

Implement operator<< or a .print() method, so you can see what’s going on in your container.
Use plenty of assertions. You will be surprised.
Don’t worry about space/time efficiency, at first. Get it working.
Use other methods in your implementation. It’s crazy to implement each of the three erase methods via copy-and-paste.
Implement the comparison functor last. Use // TODO comments to mark where you need to go back and use it.

How to submit your homework:

Follow the directions on the homework page.

How to receive negative points:

Turn in someone else’s work.

CS253: Problem Solving with C++

Spring 2012

HW 6

CS253 HW6: Shift-Over List

Description

Template Parameters

Examples

Requirements for stored type

Required public types of `Sol`

Required public methods of `Sol`

Required operators

Required operations on `Sol::iterator`:

Requirements

Hints

How to submit your homework:

How to receive negative points:

CS253: Problem Solving with C++

Spring 2012

HW 6

CS253 HW6: Shift-Over List

Description

Template Parameters

Examples

Requirements for stored type

Required public types of Sol

Required public methods of Sol

Required operators

Required operations on Sol::iterator:

Requirements

Hints

How to submit your homework:

How to receive negative points:

Required public types of `Sol`

Required public methods of `Sol`

Required operations on `Sol::iterator`: