· 6 years ago · Sep 18, 2019, 01:04 AM
1//Tucker Miles
2//Wednesday, September 18, 2019
3
4#ifndef SLIST_H
5#define SLIST_H
6
7#include<string>
8#include<vector>
9#include<cstring>
10#include<algorithm>
11
12template <class T>
13class slist {
14 private:
15 struct node {
16 node() { data = T(); next = NULL; }
17
18 // add node(const T &key) { write this }
19 node(const T &key) { data = key; next = NULL; }
20
21 // add overloaded operator< code
22 bool operator<(const node &x) const { return data < x.data; }
23
24 T data;
25 node *next;
26 };
27
28 // add class sptr { write this for node data }
29 class sptr {
30 public:
31 sptr(node *_ptr = NULL) { ptr = _ptr; }
32
33 bool operator<(const sptr &rhs) const { return *ptr < *rhs.ptr; }
34
35 operator node * () const { return ptr; }
36
37 public:
38 node *ptr;
39 };
40
41 public:
42 //Provided iterator code
43 class iterator {
44 public:
45 iterator() { p = NULL; }
46 T & operator*() { return p->data; }
47 iterator & operator++() { p = p->next; return *this; }
48 bool operator!=(const iterator & rhs) const { return p != rhs.p; }
49
50 private:
51 iterator(node *n_p) { p = n_p; }
52 node *p;
53
54 friend class slist<T>;
55 };
56
57 public:
58 //Provided class members
59 slist();
60 ~slist();
61
62 void push_back(const T &);
63 void sort(const string &);
64
65 iterator begin() { return iterator(head->next); }
66 iterator end() { return iterator(NULL); }
67
68 private:
69 node *head;
70 node *tail;
71};
72
73//provided constructor
74template <typename T>
75slist<T>::slist() {
76 head = new node();
77 tail = head;
78}
79
80//Provided destructor
81template <typename T>
82slist<T>::~slist() {
83 while (head->next != NULL) {
84 node *p = head->next;
85 head->next = p->next;
86 delete p;
87 }
88 delete head;
89
90 head = NULL;
91 tail = NULL;
92}
93
94//Provided push_back function
95template <typename T>
96void slist<T>::push_back(const T &din) {
97 tail->next = new node(din);
98 tail = tail->next;
99}
100
101template <typename T>
102void slist<T>::sort(const string &algname) {
103 // determine number of list elements
104 int N = 0;
105 node *current = head;
106 while(current != tail) {
107 N++;
108 current = current->next;
109 }
110
111 // set up smart pointer array called Ap
112 vector<sptr> Ap(N);
113 current = head->next;
114 int i = 0;
115
116 while(i < N) {
117 Ap[i] = sptr(current);
118 current = current->next;
119 i++;
120 }
121
122 // if quicksort, apply std::sort(...)
123 if (strcmp(algname.c_str(), "quicksort") == 0) {
124 std::sort(Ap.begin(), Ap.end());
125 }
126 // if mergesort, apply std::stable_sort(...)
127 if (strcmp(algname.c_str(), "mergesort") == 0) {
128 std::stable_sort(Ap.begin(), Ap.end());
129 }
130
131 // use sorted Ap array to relink list
132 current = head;
133 for(i = 0; i < Ap.size(); i++) {
134 current->next = Ap[i];
135 current = current->next;
136 }
137 current->next = NULL;
138}
139#endif // SLIST_H