forked from uva-cs/pdr
-
Notifications
You must be signed in to change notification settings - Fork 0
/
List.h.html
103 lines (84 loc) · 8.85 KB
/
List.h.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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
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
96
97
98
99
100
101
102
103
<!DOCTYPE HTML>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="GENERATOR" content="GNU source-highlight
by Lorenzo Bettini
http://www.lorenzobettini.it
http://www.gnu.org/software/src-highlite">
<title>List.h</title>
</head>
<body style="background-color:white">
<pre><i><span style="color:#9A1900">/*</span></i>
<i><span style="color:#9A1900"> * Filename: List.h</span></i>
<i><span style="color:#9A1900"> * Description: List class definition</span></i>
<i><span style="color:#9A1900"> * also includes the prototype for non-member function printList()</span></i>
<i><span style="color:#9A1900"> */</span></i>
<b><span style="color:#000080">#ifndef</span></b> LIST_H
<b><span style="color:#000080">#define</span></b> LIST_H
<b><span style="color:#000080">#include</span></b> <span style="color:#FF0000"><iostream></span>
<b><span style="color:#000080">#include</span></b> <span style="color:#FF0000">"ListNode.h"</span>
<b><span style="color:#000080">#include</span></b> <span style="color:#FF0000">"ListItr.h"</span>
<b><span style="color:#0000FF">using</span></b> <b><span style="color:#0000FF">namespace</span></b> std<span style="color:#990000">;</span>
<i><span style="color:#9A1900">// When reading in ListItr.h first, it starts reading in this file</span></i>
<i><span style="color:#9A1900">// before declaring that ListItr is a class. This file then include</span></i>
<i><span style="color:#9A1900">// ListItr.h, but beacuse of the #ifndef LISTITR_H statement, the code</span></i>
<i><span style="color:#9A1900">// in that file is not read. Thus, in this case, this List.h file</span></i>
<i><span style="color:#9A1900">// will be read in, and will not know that ListItr is a class, which</span></i>
<i><span style="color:#9A1900">// will cause compilation problems later on in this file. Got it?</span></i>
<i><span style="color:#9A1900">// Isn't C++ fun???</span></i>
<b><span style="color:#0000FF">class</span></b> <span style="color:#008080">ListItr</span><span style="color:#990000">;</span>
<b><span style="color:#0000FF">class</span></b> <span style="color:#008080">List</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">public</span></b><span style="color:#990000">:</span>
<i><span style="color:#9A1900">// The default constructor.</span></i>
<i><span style="color:#9A1900">// It should initialize all private data members</span></i>
<i><span style="color:#9A1900">// and set up the basic list structure with the dummy head and tail nodes.</span></i>
<b><span style="color:#000000">List</span></b><span style="color:#990000">();</span>
<i><span style="color:#9A1900">// The copy constructor.</span></i>
<i><span style="color:#9A1900">// It should create a **new** list of ListNodes whose contents</span></i>
<i><span style="color:#9A1900">// are the same values as the ListNodes in `source`.</span></i>
<b><span style="color:#000000">List</span></b><span style="color:#990000">(</span><b><span style="color:#0000FF">const</span></b> List<span style="color:#990000">&</span> source<span style="color:#990000">);</span>
<i><span style="color:#9A1900">// The destructor.</span></i>
<i><span style="color:#9A1900">// It should empty the list and reclaim the memory allocated in the constructor for head and tail.</span></i>
<span style="color:#990000">~</span><b><span style="color:#000000">List</span></b><span style="color:#990000">();</span>
<i><span style="color:#9A1900">// The copy assignment operator.</span></i>
<i><span style="color:#9A1900">// It should copy the contents of every ListNode in `source`</span></i>
<i><span style="color:#9A1900">// into an **existing** list (the reference to the calling List object itself).</span></i>
List<span style="color:#990000">&</span> <b><span style="color:#0000FF">operator</span></b><span style="color:#990000">=(</span><b><span style="color:#0000FF">const</span></b> List<span style="color:#990000">&</span> source<span style="color:#990000">);</span>
<i><span style="color:#9A1900">// Returns true if empty, else false</span></i>
<span style="color:#009900">bool</span> <b><span style="color:#000000">isEmpty</span></b><span style="color:#990000">()</span> <b><span style="color:#0000FF">const</span></b><span style="color:#990000">;</span>
<i><span style="color:#9A1900">// Removes (deletes) all items except the dummy head/tail.</span></i>
<i><span style="color:#9A1900">// The list should be a working empty list after this.</span></i>
<span style="color:#009900">void</span> <b><span style="color:#000000">makeEmpty</span></b><span style="color:#990000">();</span>
<i><span style="color:#9A1900">// Returns an iterator that points to the first ListNode **after** the dummy head node (even on an empty list!)</span></i>
<span style="color:#008080">ListItr</span> <b><span style="color:#000000">first</span></b><span style="color:#990000">();</span>
<i><span style="color:#9A1900">// Returns an iterator that points to the last ListNode **before** the dummy tail node (even on an empty list!)</span></i>
<span style="color:#008080">ListItr</span> <b><span style="color:#000000">last</span></b><span style="color:#990000">();</span>
<i><span style="color:#9A1900">// Inserts x after current iterator position</span></i>
<span style="color:#009900">void</span> <b><span style="color:#000000">insertAfter</span></b><span style="color:#990000">(</span><span style="color:#009900">int</span> x<span style="color:#990000">,</span> <span style="color:#008080">ListItr</span> position<span style="color:#990000">);</span>
<i><span style="color:#9A1900">// Inserts x before current iterator position</span></i>
<span style="color:#009900">void</span> <b><span style="color:#000000">insertBefore</span></b><span style="color:#990000">(</span><span style="color:#009900">int</span> x<span style="color:#990000">,</span> <span style="color:#008080">ListItr</span> position<span style="color:#990000">);</span>
<i><span style="color:#9A1900">// Inserts x at tail of list</span></i>
<span style="color:#009900">void</span> <b><span style="color:#000000">insertAtTail</span></b><span style="color:#990000">(</span><span style="color:#009900">int</span> x<span style="color:#990000">);</span>
<i><span style="color:#9A1900">// Returns an iterator that points to the first occurrence of x.</span></i>
<i><span style="color:#9A1900">// When the parameter is not in the list, return a ListItr object that points to the dummy tail node.</span></i>
<i><span style="color:#9A1900">// This makes sense because you can test the return from find() to see if isPastEnd() is true.</span></i>
<span style="color:#008080">ListItr</span> <b><span style="color:#000000">find</span></b><span style="color:#990000">(</span><span style="color:#009900">int</span> x<span style="color:#990000">);</span>
<i><span style="color:#9A1900">// Removes the first occurrence of x</span></i>
<span style="color:#009900">void</span> <b><span style="color:#000000">remove</span></b><span style="color:#990000">(</span><span style="color:#009900">int</span> x<span style="color:#990000">);</span>
<i><span style="color:#9A1900">// Returns the number of elements in the list</span></i>
<span style="color:#009900">int</span> <b><span style="color:#000000">size</span></b><span style="color:#990000">()</span> <b><span style="color:#0000FF">const</span></b><span style="color:#990000">;</span>
<b><span style="color:#0000FF">private</span></b><span style="color:#990000">:</span>
ListNode<span style="color:#990000">*</span> head<span style="color:#990000">;</span> <i><span style="color:#9A1900">// Dummy node representing the beginning of the list</span></i>
ListNode<span style="color:#990000">*</span> tail<span style="color:#990000">;</span> <i><span style="color:#9A1900">// Dummy node representing the end of the list</span></i>
<span style="color:#009900">int</span> count<span style="color:#990000">;</span> <i><span style="color:#9A1900">// Number of elements in the list</span></i>
<span style="color:#FF0000">}</span><span style="color:#990000">;</span>
<i><span style="color:#9A1900">// printList: non-member function prototype</span></i>
<i><span style="color:#9A1900">// prints list forwards (head -> tail) when forward is true</span></i>
<i><span style="color:#9A1900">// or backwards (tail -> head) when forward is false</span></i>
<i><span style="color:#9A1900">// You **must** use your ListItr class to implement this function!</span></i>
<span style="color:#009900">void</span> <b><span style="color:#000000">printList</span></b><span style="color:#990000">(</span>List<span style="color:#990000">&</span> source<span style="color:#990000">,</span> <span style="color:#009900">bool</span> forward<span style="color:#990000">);</span>
<b><span style="color:#000080">#endif</span></b>
</pre>
</body>
</html>