1: /** @file profiler_search_linear.cpp
2: Perform timing and operation counts for linear searches.
3: */
5: #include <iostream>
6: #include <iomanip>
7: #include <string>
8: #include <vector>
9: using namespace std;
11: #include "utilities.h"
12: using Scobey::Pause;
13: using Scobey::ReadInt;
14: using Scobey::userSaysYes;
15: using Scobey::OperationCounter;
16: using Scobey::RandomGenerator;
17: using Scobey::Stopwatch;
19: //Global variables permitted
20: //These global variables are permissible for the following reasons:
21: //There is only one of each used throughout the program and each is used
22: //in the same way each time it is used, much like the "global object" cout
23: //is used everywhere throughout a program to display output on the screen.
24: OperationCounter counter;
25: Stopwatch timer;
26: bool counter_ON = false;
27: bool timer_ON = false;
30: //Function prototypes
31: void Search
32: (
33: vector<int>& v //in
34: );
35: /**<
36: Handle the high-level interaction with the user for each search.
37: @param v The current vector of integer values through which to search.
38: @pre v has been initialized.
39: @post A search for some value in v has been performed.
40: */
43: void SearchLinear
44: (
45: const vector<int>& v, //in
46: int targetValue, //in
47: int firstPosition, //in
48: int lastPosition, //in
49: int& targetPosition, //out
50: bool& targetFound //out
51: );
52: /**<
53: Perform a search for a target value in the vector of integers.
54: @param v The current vector of integers through which to search.
55: @param targetValue The value for which to search.
56: @param firstPosition The first postion of the range to search.
57: @param lastPosition The last position of the range to search.
58: @param targetPosition The position where the target value was found.
59: @param targetFound Indicates if the target was found.
60: @pre v, targetValue, firstPosition and lastPosition have been initialized.
61: It must also be true that 1 <= firstPosition <= lastPosition <= v.size().
62: @post Either targetFound == true and targetValue is located at position
63: targetPosition (i.e., at v[targetPosition-1]), or targetFound == false
64: and targetPosition == lastPostion+1. Note that in this latter case
65: targetPosition must not be used.
66: */
69: void DisplayValues
70: (
71: const vector<int>& v //in
72: );
73: /**<
74: Display the sequence of integers through which the searches will
75: be performed.
76: @param v The current vector of integers through which to search.
77: @pre v has been initialized.
78: @post The integer values in v have been displayed, 10 per line.
79: */
82: void DisplayStatistics();
83: /**<
84: Display results of comparison counting and timing if these actions
85: have been performed.
86: @pre The following global objects and variables have been declared:
87: - timer, an object of the Stopwatch class
88: - timer_ON, a "switch" variable of type bool
89: - counter, an object of the OperationCounter class
90: - counter_ON, a "switch" variable of type bool
91: @post If counter_ON is true, the number of comparisons recorded by
92: counter are displayed in summary form. And, if timer_ON is true,
93: the time taken by the algorithm is displayed. If neither counter_ON
94: nor timer_ON is true, the function does nothing (except provide a
95: pause if actually called).
96: */
99: int main()
100: {
101: cout << "\nThis program is a \"search profiler\". It uses a linear "
102: "search algorithm to\nsearch through a randomly generated sequence "
103: "of integers for a target value\nsupplied by the user, and then "
104: "reports the first position where the target\nvalue was found, or "
105: "that the target value was not present. It can also time\na search "
106: "and/or count the number of comparisons performed."
107:
108: "\n\nAll values may be displayed, if the user so wishes. "
109: "They are shown 10 per\nline, with each value right-justified "
110: "within a fieldwidth of 7 spaces. Thus\neach generated value, "
111: "including the minus sign, if any, should not occupy\nmore than "
112: "6 spaces.\n";
113: Pause();
115: vector<int> v; //Sequence of integer values to be searched
116: int numberOfInts; //Number of integer values in search sequence
117: int low, high; //Range of values in search sequence
119: ReadInt("Enter required number of integers for the sequence to "
120: "be searched: ", numberOfInts);
121: ReadInt("Enter lower bound for that sequence: ", low);
122: ReadInt("Enter upper bound for that sequence: ", high);
123: RandomGenerator g;
124: if (userSaysYes("Would you like to \"seed\" the random generator?"))
125: {
126: int seedValue;
127: ReadInt("What seed value would you like to use? ", seedValue);
128: g.reset(seedValue);
129: }
130: for (int i=1; i<=numberOfInts; i++)
131: v.push_back(g.getNextInt(low, high));
133: const string CONTINUE_QUERY =
134: "Would you like to search for another target value?";
135: do
136: {
137: if (userSaysYes("Display the values?"))
138: DisplayValues(v);
139: timer_ON = userSaysYes("Time the search?");
140: counter_ON = userSaysYes("Count the operations?");
141: Search(v);
142: if (timer_ON || counter_ON) DisplayStatistics();
143: }
144: while (userSaysYes(CONTINUE_QUERY));
145: }
148: void DisplayValues
149: (
150: const vector<int>& v //in
151: )
152: {
153: cout << "\nHere is the current list of integer values:\n";
154: const int NUMBER_PER_LINE = 10;
155: vector<int>::size_type i;
156: for (i = 0; i<v.size(); i++)
157: {
158: cout << setw(7) << v.at(i);
159: if ((i+1) % NUMBER_PER_LINE == 0) cout << endl;
160: }
161: //Note that the value of i in the following is the same as
162: //the last value of i+1 in the body of the above loop.
163: cout << ((i % NUMBER_PER_LINE == 0) ? "\n" : "\n\n");
164: }
167: void DisplayStatistics()
168: {
169: if (counter_ON) counter.displayAllCounts();
170: if (timer_ON) cout << "Time taken = " << timer.getSeconds()
171: << " seconds.\n\n";
172: Pause();
173: }
176: void Search
177: (
178: vector<int>& v //in
179: )
180: {
181: int targetValue;
182: ReadInt("\nFor what value would you like to search? ", targetValue);
184: cout << "Between what two positions would you like to search?\n";
185: int firstPosition, lastPosition;
186: ReadInt("Enter first position here: ", firstPosition);
187: ReadInt("Enter last position here: ", lastPosition);
189: bool targetFound;
190: int targetPosition;
191: if (timer_ON) timer.start();
192: SearchLinear(v, targetValue, firstPosition, lastPosition,
193: targetPosition, targetFound);
194: if (timer_ON) timer.stop();
196: cout << "\nValue " << targetValue;
197: if (targetFound)
198: cout << " located at position " << targetPosition << ".\n";
199: else
200: cout << " not found.\n";
201: Pause();
202: }
205: void SearchLinear
206: (
207: const vector<int>& v, //in
208: int targetValue, //in
209: int firstPosition, //in
210: int lastPosition, //in
211: int& targetPosition, //out
212: bool& targetFound //out
213: )
214: {
215: if (counter_ON) counter.reset();
217: int index = firstPosition-1;
218: while (index < lastPosition && targetValue != v.at(index))
219: {
220: ++index;
221: if (timer_ON) timer.delay(10);
222: if (counter_ON) counter.incrementComparisons();
223: }
225: if (timer_ON) timer.delay(10);
226: if (index < lastPosition) counter.incrementComparisons();
227: //Since if the target value is found, the value comparison
228: //in the while-condition is not counted in the loop body.
230: targetFound = (index < lastPosition);
231: targetPosition = index+1;
232: }
234: /*Here is the essential code of the algorithm, repeated for clarity:
235: ====================================================================
236: int index = firstPosition-1;
237: while (index < lastPosition && targetValue != v.at(index))
238: ++index;
239: targetFound = (index < lastPosition);
240: targetPosition = index+1;
241: */
243: //Show that the replacement shown below for the while condition
244: //in the above loop does not work in all cases and explain where
245: //and why things go wrong.
246: //while (targetValue != v.at(index) && index <= lastPosition-1)