Sequence Data Structure

Homework 1 gave you extensive experience with the Sequence type using both arrays and dynamically-allocated arrays. In this project, you will re-write the implementation of the Sequence type to employ a doubly-linked list rather than an array. You must not use arrays. You will also implement a couple of algorithms that operate on sequences.

Implement Sequence yet again

Consider the Sequence interface from problem 2 of Homework 1:

using ItemType = TheTypeOfElementGoesHere;

class Sequence
{
public:
Sequence();
bool empty() const;
int size() const;
int insert(int pos, const ItemType& value);
int insert(const ItemType& value);
bool erase(int pos);
int remove(const ItemType& value);
bool get(int pos, ItemType& value) const;
bool set(int pos, const ItemType& value);
int find(const ItemType& value) const;
void swap(Sequence& other);
};

In problem 3 of Homework 1, you implemented this interface using an array. For this project, implement this Sequence interface using a doubly-linked list. (You must not use the list class template from the C++ library.)

For the array implementation of problem 3 of Homework 1, since you declared no destructor, copy constructor, or assignment operator, the compiler wrote them for you, and they did the right thing. For this linked list implementation, if you let the compiler write the destructor, copy constructor, and assignment operator, they will do the wrong thing, so you will have to declare and implement these public member functions as well:

Destructor: When a Sequence is destroyed, the nodes in the linked list must be deallocated.

Copy constructor: When a brand new Sequence is created as a copy of an existing Sequence, enough new nodes must be allocated to hold a duplicate of the original list.

Assignment operator: When an existing Sequence (the left-hand side) is assigned the value of another Sequence (the right-hand side), the result must be that the left-hand side object is a duplicate of the right-hand side object, with no memory leak of list nodes (i.e. no list node from the old value of the left-hand side should be still allocated yet inaccessible).

Notice that there is now no a priori limit on the maximum number of items in the Sequence (so the one-argument form of insert should never return 1). Notice also that, as in Homework 1, if a Sequence has a size of n, then the values of the first parameter to get for which that function retrieves an item (that was previously inserted by a call to one of the insert member functions) and returns true are 0, 1, 2, ..., n1; for other values, it returns false without setting its second parameter. For example:

Sequence ss; // ItemType is std::string
ss.insert(0, "aaa");
ss.insert(1, "bbb");
ss.insert(2, "ccc");
ItemType x = "xxx";
assert(!ss.get(3, x) && x == "xxx"); // x is unchanged
assert(ss.get(1, x) && x == "bbb");

This is the same visible behavior as in Homework 1.

Another requirement is that as in Problem 5 of Homework 1, the number of statement executions when swapping two sequences must be the same no matter how many items are in the sequences.

Implement some sequence algorithms

Implement the following two functions. Notice that they are non-member functions: They are not members of Sequence or any other class, so they must not access private members of Sequence.

int subsequence(const Sequence& seq1, const Sequence& seq2);

Consider all the items in seq2; let's call them seq2₀, seq2₁, ..., seq2_n. If there exists at least one k such that seq1_k == seq2₀ and seq1_k+1 == seq2₁ and ... and seq1_k+n == seq2_n, and k+n < seq1.size(), then this function returns the smallest such k. (In other words, if seq2 is a consecutive subsequence of seq1, the function returns the earliest place in seq1 where that subsequence starts.) If no such k exists or if seq2 is empty, the function returns -1. For example, if seq1 were a sequence of ints consisting of

30 21 63 42 17 63 17 29 8 32

and seq2 consists of

63 17 29

then the function returns 5, since the consecutive items 63 17 29 appear in seq1 starting with the 63 at position 5. (The result is not 2, because while there's a 63 at position 2, followed eventually by a 17 and a 29, those items are not consecutive in seq1.) With the same seq1, if seq2 consists of

17 63 29

void interleave(const Sequence& seq1, const Sequence& seq2, Sequence& result);

This function produces as a result a sequence that consists of the first item in seq1, then the first in seq2, then the second in seq1, then the second in seq2, etc.

More formally: Consider the items in seq1; let's call them seq1₀, seq1₁, ..., seq1_m, and let's call the items seq2 contains seq2₀, seq2₁, ..., seq2_n. If m equals n, then when this function returns, result must consist of the sequence seq1₀, seq1₁, seq2₁, ..., seq1_m, seq2_n, and no other items.

If m is less than n, then when this function returns, result must consist of the sequence seq1₀, seq2₀, seq1₁, seq2₁, ..., seq1_m, seq2_n, seq1_m+1, seq1_m+2, ..., seq1_n, and no other items.

If n is less than m, then when this function returns, result must consist of the sequence seq1₀, seq2₀, seq1₁, seq2₁, ..., seq1_n, seq2_n, seq1_n+1, seq1_n+2, ..., seq1_m, and no other items.

If seq1 is empty, then when this function returns, result must consist of the sequence seq2₀, ..., seq2_n, and no other items. If seq2 is empty, then when this function returns, result must consist of the sequence seq1₀, ..., seq1_m, and no other items. If seq1 and seq2 are empty, then when this function returns, result must be empty.

When this function returns, result must not contain any items that this spec does not require it to contain. (You must not assume result is empty when it is passed in to this function; it might not be.)

As an example, if seq1 were a sequence of ints consisting of

30 21 63 42 17 63

and seq2 consists of

42 63 84 19

then no matter what value it had before, result ends up consisting of:

30 42 21 63 63 84 42 19 17 63

Be sure that in the face of aliasing, these functions behave as this spec requires: Does your implementation work correctly if seq1 and result refer to the same Sequence, for example?

Other Requirements

Regardless of how much work you put into the assignment, your program will receive a zero for correctness if you violate these requirements:

• Your class definition, declarations for the two required non-member functions, and the implementations of any functions you choose to inline must be in a file named Sequence.h, which must have appropriate include guards. The implementations of the functions you declared in Sequence.h that you did not inline must be in a file named Sequence.cpp. Neither of those files may have a main routine (unless it's commented out). You may use a separate file for the main routine to test your Sequence class; you won't turn in that separate file.
• Except to add a destructor, copy constructor, assignment operator, and dump function (described below), you must not add functions to, delete functions from, or change the public interface of the Sequence class. You must not declare any additional struct/class outside the Sequence class, and you must not declare any public struct/class inside the Sequence class. You may add whatever private data members and private member functions you like, and you may declare private structs/classes inside the Sequence class if you like. The source files you submit for this project must not contain the word friend or the character [ (open square bracket). You must not use any global variables whose values may be changed during execution. (Global constants are fine.)
• If you wish, you may add a public member function with the signature void dump() const. The intent of this function is that for your own testing purposes, you can call it to print information about the sequence; we will never call it. You do not have to add this function if you don't want to, but if you do add it, it must not make any changes to the sequence; if we were to replace your implementation of this function with one that simply returned immediately, your code must still work correctly. The dump function must not write to cout, but it's allowed to write to cerr.
• Sequence.cpp must not contain the word string. (Sequence.h may contain it only in a using statement introducing a type alias, and must contain #include if a using statement introducing a type alias contains the word string.)

• Your code must build successfully (under both g32 and either Visual C++ or clang++) if linked with a file that contains a main routine.
• You must have an implementation for every member function of Sequence, as well as the non-member functions subsequence and interleave. Even if you can't get a function implemented correctly, it must have an implementation that at least builds successfully. For example, if you don't have time to correctly implement Sequence::erase or interleave, say, here are implementations that meet this requirement in that they at least build successfully:

bool Sequence::erase(int pos)
{
return true; // not correct, but at least this compiles
}

void interleave(const Sequence& seq1, const Sequence& seq2, Sequence& result)
{
// does nothing; not correct, but at least this compiles
}

• You've probably met this requirement if the following file compiles and links with your code. (This uses magic beyond the scope of CS 32.)

#include "Sequence.h"
#include < type_traits>

#define CHECKTYPE(f, t) { auto p = static_cast< t>(f); (void)p; }

static_assert(std::is_default_constructible< Sequence>::value,
"Sequence must be default-constructible.");
static_assert(std::is_copy_constructible< Sequence>::value,
"Sequence must be copy-constructible.");
static_assert(std::is_copy_assignable< Sequence>::value,
"Sequence must be assignable.");

void thisFunctionWillNeverBeCalled()
{
CHECKTYPE(&Sequence::empty, bool (Sequence::*)() const);
CHECKTYPE(&Sequence::size, int (Sequence::*)() const);
CHECKTYPE(&Sequence::insert, int (Sequence::*)(int, const ItemType&));
CHECKTYPE(&Sequence::insert, int (Sequence::*)(const ItemType&));
CHECKTYPE(&Sequence::erase, bool (Sequence::*)(int));
CHECKTYPE(&Sequence::remove, int (Sequence::*)(const ItemType&));
CHECKTYPE(&Sequence::get, bool (Sequence::*)(int, ItemType&) const);
CHECKTYPE(&Sequence::set, bool (Sequence::*)(int, const ItemType&));
CHECKTYPE(&Sequence::find, int (Sequence::*)(const ItemType&) const);
CHECKTYPE(&Sequence::swap, void (Sequence::*)(Sequence&));
CHECKTYPE(subsequence, int (*)(const Sequence&, const Sequence&));
CHECKTYPE(interleave, void (*)(const Sequence&, const Sequence&, Sequence&));
}

int main()
{}

• If you add #include < string> to Sequence.h and have the type alias for ItemType specifystd::string, then if we make no change to your Sequence.cpp, compile it, and link it to a file containing

#include "Sequence.h"
#include < string>
#include < iostream>
#include < cassert>
using namespace std;

void test()
{
Sequence s;
assert(s.insert(0, "lavash") == 0);
assert(s.insert(0, "tortilla") == 0);
assert(s.size() == 2);
ItemType x = "injera";
assert(s.get(0, x) && x == "tortilla");
assert(s.get(1, x) && x == "lavash");
}

int main()
{
test();
cout << "Passed all tests" << endl;
}

• the linking must succeed. When the resulting executable is run, it must write Passed all tests to coutand nothing else to cout, and terminate normally.
• If we successfully do the above, then make no changes to Sequence.h other than to change the type alias so that ItemType specifies unsigned long, recompile Sequence.cpp, and link it to a file containing

#include "Sequence.h"
#include < iostream>
#include < cassert>
using namespace std;

void test()
{
Sequence s;
assert(s.insert(0, 10) == 0);
assert(s.insert(0, 20) == 0);
assert(s.size() == 2);
ItemType x = 999;
assert(s.get(0, x) && x == 20);
assert(s.get(1, x) && x == 10);
}

int main()
{
test();
cout << "Passed all tests" << endl;
}

• the linking must succeed. When the resulting executable is run, it must write Passed all tests to coutand nothing else to cout, and terminate normally.
• During execution, if a client performs actions whose behavior is defined by this spec, your program must not perform any undefined actions, such as dereferencing a null or uninitialized pointer.
• Your code in Sequence.h and Sequence.cpp must not read anything from cin and must not write anything whatsoever to cout. If you want to print things out for debugging purposes, write to cerr instead of cout. cerr is the standard error destination; items written to it by default go to the screen. When we test your program, we will cause everything written to cerr to be discarded instead we will never see that output, so you may leave those debugging output statements in your program if you wish.