[SOLVED] COMP5421 Assignment 2-Custom String Tokenzier

1 Objectives

In this assignment, you will redo Assignment 1 without getting involved with dynamic storage management. A major goal in this and the following assignments is to encourage you to leverage the C++ standard and popular libraries to do the work for you so you don’t ever have to reinvent the wheel.

Although assignment 1 can be ideally and conveniently implemented using associative containers such as std::map and std::set, this assignment requires that class IntList be replaced with std::vector<int>, class TList with std::list<Token>, and C-style text processing with std::string.

Token

1 1

std::list<Token> *

1

Tokenizer

1 1 std::vector<int>

TokenizerApp

1 1..*

In addition to implementing the bulk of the work in this assignment, the vector<int> and list<Token> classes also provide plenty opportunities for us to learn about container iterators, which we will use in class Tokenizer to iterate through and modify the container elements.

Class Tokenizer provides the functionalities of A1’s TList class that are not directly supported by std::list<Token>, plus a few more functionalities.

2 String tokens
In assignment 1, a string token is defined as a sequence of contiguous characters excluding

white-space characters such as space, tab, and newline characters.
Generalizing that definition in this assignment, we define a string token to be a sequence of

contiguous characters excluding those specified in a user defined set of separator characters.

The separator characters are those that we do not want in a token in this assignment, and they are represented using a std::string object. For example, the separators in assignment 1 can be defined as “\n\t\0 “; that is, the new line, tab, null, and blank characters separate tokens in a text.

Assignment 2, Summer 2021 page 1 of 14

3 Class TokenizerApp

TokenizerApp is the name of a C++ file that contains the main function, and possibly other functions, to test drive the functionality of a Tokenizer object. It is a simple menu-driven program that displays a menu of options for the user to choose from:

1 2 3 4 5 6 7 8 9

10 11 12

12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

3.1 Option A (or a)

Prints all of the input lines:

Assignment 2, Summer 2021 page 2 of 14

35 36

  X - Exit
Enter your choice:

3.2 Option P (or p)

Prints all tokens in alphabetic order, similar to that in assignment 1, with one noticeable difference: the numbers inside the parentheses, each indicating the frequency of the corresponding token in the input file.

36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

Notice that the user supplied separator characters ;.␣,?!”=’: defines a very limited number of separators, allowing, for example, the strings 123 and }1+2*3{ as tokens. For a C++ source file, the user might input something like ;.␣,?!”=’:|{}[]()&+-*%$#!~>^</\ for the separator characters.

Assignment 2, Summer 2021 page 3 of 14

3.3 Option F (or f)

Prints the tokens sorted in the ascending order of their frequencies in the input file:

66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

Knowing that sorting a linked list in general is not a trivial task, let alone sorting the list efficiently, we are happy to know that std::list<Token> can sort the list for us if we tell it how to compare two tokens.

See here for a quick example.

Assignment 2, Summer 2021 page 4 of 14

3.4 Option L (or L)

Prints the tokens sorted on the length of each string tokens, with tokens of equal lengths sorted alphabetically.

95 96 97 98 99

100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124

Again, the std::list<Token> class can sort the list for us as long as we tell it how to compare two tokens.

Assignment 2, Summer 2021 page 5 of 14

124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154

3.5 Option P (or p), Again

Let us note that printing the tokens sorted on some attributes must not disturb the order of the tokens in the original indexed list. In other words, selecting option P now should print the original indexed list:

Assignment 2, Summer 2021 page 6 of 14

3.6 Option S (or s)

Prompts the user for a token to search for; if found, prints the input lines on which the token appears; otherwise, displays the message “token not found”.

154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170

170 171 172 173

3.7 Option X (or x)

Assignment 2, Summer 2021 page 7 of 14

4 Class Token 4.1 Representation

    string theText{};
    vector<size_t> theLineNumbers{}; // this token’s list of (non-negative) line numbers
    size_t theFrequency{1};          // the frequency of this token in the input file

We choose size t over int as the type of the line numbers, because in this application we only deal non-negative line numbers and size t represents non-negative (unsigned) integers.

The size of theLineNumbers is at least 1, because a string token must reside on some line in the input file, and every input line has a number ≥ 1.

Note that the size of theLineNumbers may not necessarily represt the frequency because a string token can appear multiple times on a single input line.

4.2 Normal constructors

This is the only normal (non-special) constructor of the class; it sets the frequency to 1, and initializes the text and line number of the token being constructed with the corresponding supplied argument values.

    Token(string text, size_t linenum);         // a normal constructor

4.3 Default constructor

Since a token cannot exist without a text and associated line number, we decide to disallow default construction; so we make our decision visible to both the human reader as well as the compiler by explicitly declaring the default constructor deleted.

8 9

1 2 3 4 5 6

// the text of this token

7

public:
   Token()                             = delete; // disable default construction

Note that disabling the default constructor of a class, in turn, disables creating an array of objects of that class. That is fine in this application, but it may not be an option in another application, forcing us to define a default Token object.

Assignment 2, Summer 2021 page 8 of 14

4.4 Other Special Member Functions: The Big Five

Modern C++ programming style encourages that these members be explicitly either defined, deleted, or defaulted. Since Token is not involved directly in dynamic resource allocation, the compiler-generated versions of these members are most appropriate for Token objects.

10 11 12 13 14 15 16 17

Consequently,

􏰀 copy/move constructors copy/move the source token’s theFrequency, theText, and theLineNumbers members to theFrequency, theText, and theLineNumbers of the Token object being constructed. Note that these data members in turn propagate and apply copy/move construction internally to their respective members, recursively.

􏰀 copy/move assignments copy/move-assign the right-hand side token’s theFrequency, theText, and theLineNumbers members to the left-hand side token theFrequency, theText, and theLineNumbers members. Note that the data members in turn propagate and apply the copy/move assignment internally to their respective members, recursively.

4.5 Comparison operations

In this assignment we use case insensitive comparison to compare the text of the tokens.

18 19 20

See Here for an example of a case insensitive comparison function.

Assignment 2, Summer 2021 page 9 of 14

4.6 Other Self-Explanatory Operations

21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

size_t
size_t

getFrequency()
getLineNumber(size_t = 1) const; // line number is 1-based

5

                                             // to provide user friendly interface
void pushBackLineNumber(size_t lineNum);  // append the suppled line number

Class Tokenizer

A Tokenizer object provides a minimal set of services, allowing a typical menu-driven program to produce an interactive session as shown above.

5.1 Representation

const;

1 2 3 4 5 6

5.2 Default constructor

Since a Tokenizer cannot exist without an input file of text, we decide to disallow default construction; so we make our decision visible to both the human reader as well as the compiler by explicitly declaring the default constructor deleted.

7 8

public:
   Tokenizer()    = delete;      // disable default constructor

Assignment 2, Summer 2021 page 10 of 14

5.3 Normal constructor

Supplied with the name of an input file of text and with a string of separator characters, this constructor extracts the lines from the input file one line at at a time, delegating the pro- cess of extracting the tokens in a line and keeping track of the associated line numbers to ProcessTokensInLine(text, line number), a private facilitator member function.

     Tokenizer(const string& filename, const string& separators);

5.4 Other Special Member Functions: The Big Five

Modern C++ programming style encourages that these members be explicitly either defined, deleted, or defaulted. Since our class is not involved directly in dynamic resource allocation, the compiler-generated versions of these members are most appropriate to use.

10 11 12 13 14

9

5.5 Private Facilitators 5.5.1 15

16

Outsources the process of extracting the tokens in line and inserting them each into the token list to two private facilitator (helper) member functions:

1. 2.

5.5.2 17

returning them all in a std::vector of std::strings.

Requirement Yourimplementationofthismemberfunctionmayonlyusethestd::string class, which offers a useful set of string operations, including substr, find first of, find first not of, and a few more.

Toextractsthetokensfromline,itdelegatestomemberfunctionsplitLineIntoTokens, which in turn returns the extracted tokens in a std::vector<string>, say, vec.

To turn the string tokens in vec into Token objects and to store the resulting objects in the token list, it delegates to the member function insert, one vec element at time.

vector<string> splitLineIntoTokens(const string& line) const;
Using the separator characters, it splits the given line of text into string tokens, storing and

Assignment 2, Summer 2021 page 11 of 14

5.5.3 18 void insert(string text, size_t linenum);
This function is equivalent to the addSorted member function in the TList class in A1.

Specifically, it first creates a Token object using the supplied text and line number; it then compares that object against the Token objects in the token list, which are already sorted in ascending order; if found, it updates the number list of that object; otherwise, it inserts the newly created Token object into the token list.

Requirement To scan and to insert into the token list, your implementation of this member function must use list<Token>::iterators.

5.5.4 19 vector<size_t> search(const string& str)const;

Searches the token list for a token object whose text is equal (case insensitive) to that of the given string str. If found, it returns a copy of that object’s line number list; otherwise, it returns an empty number list.

5.5.5 20 void printSomeInputLines(const vector<size_t>& vec)const;
Given a std::vector of line numbers, prints the input lines corresponding to those line

numbers.

5.6 Public Interface 5.6.1 21

22

Searches the token list for a token object whose text is the same as the given string str; if found, it prints the input lines that contain str.

5.6.2 23 24

Prints all input lines.

5.6.3 25 26

Prints the token list to the given output stream sout. 5.6.4 27

28

Prints the token list sorted on frequencies of the tokens in the input file.

public:
   void searchAndPrint(string& str)const;

public:
   void printAllInputLines()const;

public:
   void print(ostream& sout)const;

public:
   void sortOnFrequecy()const;

Assignment 2, Summer 2021 page 12 of 14

Requirements

1. Since the token list must remain intact, we need to copy it into another linear sequence and then sort that linear sequence.

   Our options here are limited to std::list, std::vector, and std::forward list.

   Familiar with std::list and std::vector, we take advantage of this opportunity to use std::forward list, which already comes equipped with a sort member fuction ( std::vector does not).

2. This member function must use std::forward list’s sort member.
   (Hint: simply implement the compareFrequency function given in 5.7.3 below and pass it

   to std::forward list’s sort member function as the argument.)

5.6.5 29

30

Prints the token list sorted on the text of the tokens..

Requirements

Similar to 5.6.4 above, copy the token list into a std::forward list and then sort that forward list using std::forward list’s own sort member function.

This member function must use std::forward list’s sort member.
(Hint: simply implement the compareLength function given in 5.7.2 below and pass it to

   void sortOnTokenLength()const;
};

1. 2.

std::forward list’s sort member function.) Free (top-level) helper functions

5.7
5.7.1 31 ostream& operator<<(ostream&, const Tokenizer&);

Writes a given token to a given stream

5.7.2 32 bool compareLength(const Token& t1, const Token& t2);

Determines whether t1 is less than t2, comparing their lengths; if they are of equal length, then determines whether t1 is less than t2, alphabetically (using std::string’s operator<).

5.7.3 33 bool compareFrequency(const Token& t1, const Token& t2); Comparing the frequencies of t1 and t2, determines whether t1 is less than t2.

Assignment 2, Summer 2021 page 13 of 14

6 Deliverables

Create a a new folder that contains the files listed below, then compress (zip) your folder, and submit the compressed (zipped) folder as instructed in the course outline.

7

1. 2. 3. 4.

5.

Header files: Token.h, and Tokenizer.h

Implementation files: Token.cpp, Tokenizer.cpp, and TokenizerApp.cpp

Input file input file A1.txt

Output file output file A1.txt (copy output from cmd window and paste it into this file)

A README.txt text file (see the course outline). Grading scheme

Assignment 2, Summer 2021 page 14 of 14