VariantThree/stack.h at master · staddy/VariantThree · GitHub

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#ifndef STACK_H
#define STACK_H

#include <memory>
#include <istream>
#include <ostream>

template<typename T> class Stack {
public:
    Stack() = default;
    Stack(const Stack& other_);
    Stack(Stack&& other_) = default;
    ~Stack() = default;
    Stack& operator=(const Stack& other_);
    Stack& operator=(Stack&& other_) = default;
    T& top();
    T pop();
    void push(const T& value_);
    void push(T&& value_);
    size_t size() const;
    bool empty() const;
    void clear();
    Stack<T> reversed() const;
    //friend std::ostream& operator<<(std::ostream&, const Stack<T>&);
    //friend std::istream& operator>>(std::istream&, Stack<T>&);
private:
    void copy(const Stack& other_);
    class StackElement {
    public:
        StackElement() = delete;
        StackElement(const T& value_, std::unique_ptr<StackElement>&& next_) :
            m_value{value_}, m_next{std::move(next_)} { }
        StackElement(T&& value_, std::unique_ptr<StackElement>&& next_) :
            m_value{std::move(value_)}, m_next{std::move(next_)} { }
        T& value() { return m_value; }
        std::unique_ptr<StackElement>& next() { return m_next; }
    private:
        T m_value;
        std::unique_ptr<StackElement> m_next{nullptr};
    };
    std::unique_ptr<StackElement> m_top{nullptr};
    size_t m_size{0};
};

template<typename T> void Stack<T>::copy(const Stack& other_) {
    if (other_.m_top == nullptr) {
        return;
    }
    Stack<T> r = other_.reversed();
    auto t = r.m_top.get();
    do {
        push(t->value());
        t = t->next().get();
    } while (t != nullptr);
}

template<typename T> Stack<T>::Stack(const Stack& other_) {
    copy(other_);
}

template<typename T> Stack<T>& Stack<T>::operator=(const Stack& other_) {
    if (&other_ != this) {
        clear();
        copy(other_);
    }
    return *this;
}

template<typename T> T& Stack<T>::top() {
    if (m_top == nullptr) {
        throw std::out_of_range("top() of empty stack");
    }
    return m_top->value();
}

template<typename T> T Stack<T>::pop() {
    auto retVal = std::move(top());
    m_top = std::move(m_top->next());
    --m_size;
    return retVal;
}

template<typename T> void Stack<T>::push(const T& value_) {
    m_top = std::make_unique<StackElement>(value_, std::move(m_top));
    ++m_size;
}

template<typename T> void Stack<T>::push(T&& value_) {
    m_top = std::make_unique<StackElement>(std::move(value_), std::move(m_top));
    ++m_size;
}

template<typename T> size_t Stack<T>::size() const {
    return m_size;
}

template<typename T> bool Stack<T>::empty() const {
    return m_top == nullptr;
}

template<typename T> void Stack<T>::clear() {
    m_top = nullptr;
    m_size = 0;
}

template<typename T> Stack<T> Stack<T>::reversed() const {
    Stack<T> r;
    if (m_top == nullptr) {
        return r;
    }
    auto t = m_top.get();
    do {
        r.push(t->value());
        t = t->next().get();
    } while (t != nullptr);
    return r;
}

//std::ostream& operator<<(std::ostream& stream_, const Stack<int>& stack_) {
//    if (stack_.m_top == nullptr) {
//        return stream_;
//    }
//    auto p = stack_.m_top.get();
//    auto s = stack_.size();
//    stream_.write(reinterpret_cast<char*>(&s), sizeof(s));
//    stream_ << p->value();
//    while ((p = p->next().get())) {
//        stream_ << p->value();
//    }
//    return stream_;
//}
//
//template<typename T> std::istream& operator>>(std::istream& stream_, Stack<T>& stack_) {
//    size_t s;
//    stream_.read(reinterpret_cast<char*>(&s), sizeof(s));
//    stack_.clear();
//    for (size_t i = 0; i < s; ++i) {
//        T temp;
//        stream_ >> temp;
//        stack_.push(temp);
//    }
//    return stream_;
//}

#endif // STACK_H