#include <iostream>
using namespace std;
template <typename T>
class dll {
private:
struct Node {
Node* prev;
Node* next;
T data;
};
Node* head;
Node* tail;
public:
dll();
~dll();
void insert(T value);
bool empty() const { return head == tail; };
};
template <typename T> dll<T>::dll() {
head = nullptr;
tail = head;
}
template <typename T> dll<T>::~dll() {
delete[] head;
}
template <typename T> void dll<T>::insert(T value) {
Node *node = new Node;
std::cout << node << '\n';
node->data = value;
// Case 1: There are no nodes yet
if (head == nullptr) {
node->prev = nullptr;
node->next = nullptr;
head = node;
tail = head;
}
else {
// Case 2: There is more than one node
Node *curr = head;
if (curr->next != nullptr)
{
while (curr->next) {
// If the value is less than the current value
if (value < curr->data) {
Node *temp = new Node;
temp->data = curr->data;
temp->next = curr->next;
temp->prev = curr->prev;
node->next = temp;
node->prev = temp->prev;
curr->prev = node;
}
curr = curr->next;
}
}
// Case 3: There is only one node
else {
node->prev = head;
node->next = nullptr;
tail = node;
}
}
}
int main() {
dll<int> list;
list.insert(10);
list.insert(20);
list.insert(15);
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdGVtcGxhdGUgPHR5cGVuYW1lIFQ+CmNsYXNzIGRsbCB7CnByaXZhdGU6CiAgICBzdHJ1Y3QgTm9kZSB7CiAgICAgICAgTm9kZSogcHJldjsKICAgICAgICBOb2RlKiBuZXh0OwogICAgICAgIFQgZGF0YTsKICAgIH07CgogICAgTm9kZSogaGVhZDsKICAgIE5vZGUqIHRhaWw7CgpwdWJsaWM6CiAgICBkbGwoKTsKICAgIH5kbGwoKTsKCiAgICB2b2lkIGluc2VydChUIHZhbHVlKTsKCiAgICBib29sIGVtcHR5KCkgY29uc3QgeyByZXR1cm4gaGVhZCA9PSB0YWlsOyB9Owp9OwoKdGVtcGxhdGUgPHR5cGVuYW1lIFQ+IGRsbDxUPjo6ZGxsKCkgewogICAgaGVhZCA9IG51bGxwdHI7CiAgICB0YWlsID0gaGVhZDsKfQoKdGVtcGxhdGUgPHR5cGVuYW1lIFQ+IGRsbDxUPjo6fmRsbCgpIHsKICAgIGRlbGV0ZVtdIGhlYWQ7Cn0KCnRlbXBsYXRlIDx0eXBlbmFtZSBUPiB2b2lkIGRsbDxUPjo6aW5zZXJ0KFQgdmFsdWUpIHsKICAgIE5vZGUgKm5vZGUgPSBuZXcgTm9kZTsKICAgIHN0ZDo6Y291dCA8PCBub2RlIDw8ICdcbic7CiAgICBub2RlLT5kYXRhID0gdmFsdWU7CiAgICAvLyBDYXNlIDE6IFRoZXJlIGFyZSBubyBub2RlcyB5ZXQKICAgIGlmIChoZWFkID09IG51bGxwdHIpIHsKICAgICAgICBub2RlLT5wcmV2ID0gbnVsbHB0cjsKICAgICAgICBub2RlLT5uZXh0ID0gbnVsbHB0cjsKICAgICAgICBoZWFkID0gbm9kZTsKICAgICAgICB0YWlsID0gaGVhZDsKICAgIH0KICAgIGVsc2UgewogICAgICAgIC8vIENhc2UgMjogVGhlcmUgaXMgbW9yZSB0aGFuIG9uZSBub2RlCiAgICAgICAgTm9kZSAqY3VyciA9IGhlYWQ7CiAgICAgICAgaWYgKGN1cnItPm5leHQgIT0gbnVsbHB0cikKICAgICAgICB7CiAgICAgICAgICAgIHdoaWxlIChjdXJyLT5uZXh0KSB7CiAgICAgICAgICAgICAgICAvLyBJZiB0aGUgdmFsdWUgaXMgbGVzcyB0aGFuIHRoZSBjdXJyZW50IHZhbHVlCiAgICAgICAgICAgICAgICBpZiAodmFsdWUgPCBjdXJyLT5kYXRhKSB7CiAgICAgICAgICAgICAgICAgICAgTm9kZSAqdGVtcCA9IG5ldyBOb2RlOwogICAgICAgICAgICAgICAgICAgIHRlbXAtPmRhdGEgPSBjdXJyLT5kYXRhOwogICAgICAgICAgICAgICAgICAgIHRlbXAtPm5leHQgPSBjdXJyLT5uZXh0OwogICAgICAgICAgICAgICAgICAgIHRlbXAtPnByZXYgPSBjdXJyLT5wcmV2OwogICAgICAgICAgICAgICAgICAgIG5vZGUtPm5leHQgPSB0ZW1wOwogICAgICAgICAgICAgICAgICAgIG5vZGUtPnByZXYgPSB0ZW1wLT5wcmV2OwogICAgICAgICAgICAgICAgICAgIGN1cnItPnByZXYgPSBub2RlOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgY3VyciA9IGN1cnItPm5leHQ7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgLy8gQ2FzZSAzOiBUaGVyZSBpcyBvbmx5IG9uZSBub2RlCiAgICAgICAgZWxzZSB7CiAgICAgICAgICAgIG5vZGUtPnByZXYgPSBoZWFkOwogICAgICAgICAgICBub2RlLT5uZXh0ID0gbnVsbHB0cjsKICAgICAgICAgICAgdGFpbCA9IG5vZGU7CiAgICAgICAgfQogICAgfQp9CgppbnQgbWFpbigpIHsKICAgIGRsbDxpbnQ+IGxpc3Q7CiAgICBsaXN0Lmluc2VydCgxMCk7CiAgICBsaXN0Lmluc2VydCgyMCk7CiAgICBsaXN0Lmluc2VydCgxNSk7Cn0=