Endsieg77's Studio.

my_header_library

Cpp
Data Structure
2021/01/07 Share

Overview

​ In this markdown I will share my realization of some classic containers and polynomial division.

​ Capacity limited, as a result they might seem to be quite foolish loool.

Section 1: Containers

Forward declarations

“standard_container.h”

1
2
3
4
5
6
7
8
#ifndef __STANDARD_CONTAINER_H__
#define __STANDARD_CONTAINER_H__

#include "heap.h"
#include "array.h"
#include "lists.h"

#endif

“lists.h”

1
2
3
4
5
6
7
#ifndef __LISTS_H__
#define __LISTS_H__

#include "link_list.h"
#include "loop_list.h"

#endif

“listfwd.h”

1
2
3
4
5
6
7
8
9
10
11
12
13
#ifndef __LISTFWD_H__
#define __LISTFWD_H__

#include <iosfwd>
#include <functional>

template<class T> class LinkList;
template<class T> class LoopList;
template<class T> class LinkListNode;
template<class T> LinkListNode<T> *moveForwards(LinkListNode<T>*&);
template<class T> LinkListNode<T> *moveBackwards(LinkListNode<T>*&);

#endif
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
// LinkList.hpp
// This header file contains some
// facilities of data structure LinkList.
// Copyright(c) @ Offensive77

#ifndef __LINKLIST_H__
#define __LINKLIST_H__

#include "listfwd.h"

template<class T>
class LinkListNode
{
public:
    typedef std::bidirectional_iterator_tag iterator_category;
    friend class LinkList<T>;
    friend class LoopList<T>;
private:
    T data;
    LinkListNode *next;
    LinkListNode *prev;
    LinkList<T> *belongsTo;  // Introduction to superior abstract.
    // Derived Class can also be considered in this case.
public:

    LinkListNode(
                                   T dat,
            LinkList<T>  *bT   = nullptr,
            LinkListNode *pPtr = nullptr,
            LinkListNode *nPtr = nullptr
    )
        : data(dat), belongsTo(bT), prev(pPtr), next(nPtr)
    {
        if(bT&&bT!=belongsTo)
        {
            ++bT->len;
            bT->tailInsert(dat);
        }
    }
    LinkListNode(const LinkListNode *&lln)
    {
        data = lln->data;
        next = lln->next;
        prev = lln->prev;
        belongsTo = lln->belongsTo;
    }
    ~LinkListNode() = default;
    T getValue() const;
    friend LinkListNode *moveBackwards<T>(LinkListNode*&);
    friend LinkListNode *moveForwards<T>(LinkListNode*&);
    LinkListNode *erase();
    LinkList<T> *comeFrom() const;
};

template<class T>
inline T LinkListNode<T>::getValue() const
{
    if(belongsTo->empty()) return 0;
    return this->data;
}

template<class T>
LinkListNode<T> *moveBackwards(LinkListNode<T> *&node)
{
    if(node)node = node->prev;
    return node;
}

template<class T>
LinkListNode<T> *moveForwards(LinkListNode<T> *&node)
{
    if(node)node = node->next;
    return node;
}

template<class T>
LinkListNode<T> *LinkListNode<T>::erase()
{
    if(belongsTo->empty())return nullptr;
    --(belongsTo->len);
    if(this == belongsTo->head)
    {
        auto temp = this->next;
        if(temp)
            temp->prev = nullptr;
        belongsTo->head = temp;
        delete this;
        /* Member function can not visit class's
           members after being deleted. */
        return temp;
    }
    if(this == belongsTo->tail)
    {
        delete this;
        return nullptr;
    }
    auto temp = this->next;
    this->prev->next = this->next;
    this->next->prev = this->prev;
    return temp;
}

template<class T>
inline LinkList<T> *LinkListNode<T>::comeFrom() const
{
    return this->belongsTo;
}

// LinkList is defined as below:

template<class T>
class LinkList
{
    friend class LinkListNode<T>;
protected:
    LinkListNode<T> *head;
    LinkListNode<T> *tail;
    int len;
public:
    LinkList(LinkListNode<T> *hPtr = nullptr, LinkListNode<T> *tPtr = nullptr):
        head(hPtr), tail(tPtr), len(0)
        {
        if(hPtr){
            ++len;
            hPtr->belongsTo = this;
        }
        if(tPtr)
        {
            ++len;
            tPtr->belongsTo = this;
            this->tail->prev = this->head;
            this->head->next = this->tail;
            this->tail->next = nullptr;
            this->head->prev = nullptr;
        }
    }
    LinkList(std::initializer_list<T> init_lst):
        head(nullptr), tail(nullptr), len(0)
    {
        for(auto elem : init_lst)
            this->tailInsert(elem);
    }
    virtual ~LinkList() = default;
    virtual void headInsert(const T&);
    virtual void tailInsert(const T&);
    virtual void insert(LinkListNode<T>*, const T&);
    int length() const;
    LinkListNode<T> *begin() const;
    LinkListNode<T> *end() const;
    virtual void displayList(const bool& = 1) const;
    bool empty() const;
    LinkList operator+(const LinkList&);
    LinkList &operator+=(const LinkList&);
    LinkList &operator=(const LinkList&);
    bool &operator==(const LinkList&);
    bool &operator!=(const LinkList&);
    friend void operator<<(std::ostream &os, const LinkList &LL)
    {
        LL.displayList();
    }
    // the reference to constant member or constant member
    // itself can only call the const member function
    // with regard to the possibility of being hacked.
};

//

template<class T>
void LinkList<T>::headInsert(const T &newData)
{
    ++len;
    LinkListNode<T> *newNode = new LinkListNode<T>(newData, this);
    if(!head&&!tail)
    {
        this->tail = newNode;
        return;
    }
    if(!head&&tail)
    {
        this->head =newNode;
        this->head->next = this->tail;
        this->tail->prev = this->head;
        return;
    }
    this->head->prev = newNode;
    newNode->next = this->head;
    this->head = newNode;
}

template<class T>
void LinkList<T>::tailInsert(const T &newData)
{
    ++len;
    LinkListNode<T> *newNode = new LinkListNode<T>(newData, this);
    if(!head&&!tail)
    {
        this->head = newNode;
        return;
    }
    if(head&&!tail)
    {
        this->tail =newNode;
        this->head->next = this->tail;
        this->tail->prev = this->head;
        return;
    }
    this->tail->next = newNode;
    newNode->prev = this->tail;
    this->tail = newNode;
}

template<class T>
void LinkList<T>::insert(LinkListNode<T> *After, const T &newData)
{
    if(After == tail)
    {
        tailInsert(newData);
        return;
    }
    ++len;
    LinkListNode<T> *newNode = new LinkListNode<T>(newData, this);
    newNode->next = After->next;
    newNode->prev = After;
    After->next->prev = newNode;
    After->next = newNode;
}

template<class T>
inline LinkListNode<T> *LinkList<T>::begin() const
{
    if(this->empty())return nullptr;
    if(!head)return this->head->next;
    return this->head;
}

template<class T>
inline LinkListNode<T> *LinkList<T>::end() const
{
    if(this->empty())return nullptr;
    if(!tail)return this->tail->prev;
    return this->tail;
}

template<class T>
inline int LinkList<T>::length() const
{
    return this->len;
}

template<class T>
void LinkList<T>::displayList(const bool& ctrl_arg) const
{
    if(empty())return;
    if(ctrl_arg)
    {
        auto iter = begin();
        while(iter)
        {
            std::cout<<iter->getValue();
            if(iter->next)std::cout<<' ';
            moveForwards(iter);
        }
        return;
    }
    else
    {
        auto iter = end();
        while(iter)
        {
            std::cout<<iter->getValue();
            if(iter->prev)std::cout<<' ';
            moveBackwards(iter);
        }
        return;
    }
}

template<class T>
inline bool LinkList<T>::empty() const
{
    if(!len)return true;
    return false;
}

template<class T>
LinkList<T> LinkList<T>::operator+(const LinkList<T> &anotherList)
{
    // refer to anotherList to avoid the cost of copying it
    LinkList<T> temp = LinkList<T>();
    auto iter1 = this->begin(), iter2 = anotherList.begin();
    while(iter1)
    {
        temp.tailInsert(iter1->data);
        moveForwards(iter1);
    }
    while(iter2)
    {
        temp.tailInsert(iter2->data);
        moveForwards(iter2);
    }
    // implicitly call the constructor at the exit point (if any
    // temporary object exists)
    return temp;
}

#endif

“loop_list.h”

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
#include "link_list.h"
// LoopList is defined as below:

template<class T>
class LoopList : public LinkList<T>
{
private:
    bool hasCircle;
public:
    LoopList(LinkListNode<T>* hPtr = nullptr, LinkListNode<T>* tPtr = nullptr)
        : LinkList<T>(hPtr, tPtr)
    {
        Close();
    }
    LoopList(std::initializer_list<T> init_lst)
        : LinkList<T>(init_lst)
    {
        Close();
    }
    LoopList(const LinkList<T> &another_linklist)
        : LinkList<T>(another_linklist)
    {
        Close();
    }
    ~LoopList() = default;
    void displayList(const bool & = 1) const override;
    void Close();
    bool isClosed();
};

template<class T>
void LoopList<T>::Close()
{
    if(this->tail)
    {
        this->head->prev = this->tail;
        this->tail->next = this->head;
        hasCircle = 1;
    } else hasCircle = 0;
}

template<class T>
inline bool LoopList<T>::isClosed()
{
    return hasCircle;
}

template<class T>
void LoopList<T>::displayList(const bool &ctrl_arg) const
{
    if(this->empty())return;
    int counted = 0;
    auto iter =
        ctrl_arg ? this->begin() : this->end();
    std::function<LinkListNode<T>*(LinkListNode<T>*&)>
        dir
        {
            ctrl_arg ?
                moveForwards<T>:
                moveBackwards<T>
        };
    while(1)
    {
        ++counted;
        auto val = iter->getValue();
        std::cout << val;
        // std::cout << iter->getValue();
        if(this->len - counted) std::cout<<' ';
        if(counted == this->len) return;
        dir(iter);
    }
}

Array

“array.h”

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
#ifndef __LiNEAR_TABLE_H__
#define __LiNEAR_TABLE_H__

#include <initializer_list>

template<class _Ty, size_t _Size>
class Array;

template<class _Ty, size_t _Size>
class
    Array
{
public:
    typedef std::random_access_iterator_tag iterator_category;
    typedef _Ty                                    value_type;
    typedef _Ty*                                     iterator;
    typedef const _Ty*                         const_iterator;
    typedef _Ty&                                    reference;
    typedef const _Ty&                        const_reference;
public:
    explicit                           Array()       noexcept;
    explicit                 Array(const _Ty&)       noexcept;
    explicit                       Array(_Ty&)       noexcept;
    explicit                      Array(_Ty&&)       noexcept;
    explicit                 Array(const _Ty*)       noexcept;
    Array(const std::initializer_list<_Ty>&)         noexcept;
    Array(std::initializer_list<_Ty>&)               noexcept;
    Array(std::initializer_list<_Ty>&&)              noexcept;
    Array(const Array&)                              noexcept;
    ~Array()                                         noexcept;
    iterator                           begin() const noexcept;
    iterator                            last() const noexcept;
    iterator                             end() const noexcept;
    constexpr const_iterator          cbegin() const noexcept;   /*  yield     */
    constexpr const_iterator           clast() const noexcept;   /*  read-only */
    constexpr const_iterator            cend() const noexcept;   /*  iterators */
    constexpr size_t                    size() const noexcept;
    value_type                           max()          const;
    value_type                           min()          const;
    void                              remove()          const;
    const_reference  operator[](const size_t&) const noexcept;
    reference        operator[](const size_t&)       noexcept;
private:
    void                                 __init__(const _Ty&);
    void          __init__(const std::initializer_list<_Ty>&);
    iterator                                            __beg;
    iterator                                             __ed;
}; 
 
template<class _Ty, size_t _Size>
Array<_Ty, _Size>::Array() noexcept
    : __beg(new _Ty[_Size]),
       __ed(__beg + _Size)
{}

template<class _Ty, size_t _Size>
Array<_Ty, _Size>::Array(
                    const _Ty &
                        __init_value
            )       noexcept
{ __init__(__init_value); }

template<class _Ty, size_t _Size>
Array<_Ty, _Size>::Array(
                    _Ty &__init_value
            )       noexcept
    : Array(std::move(__init_value))
{}

template<class _Ty, size_t _Size>
Array<_Ty, _Size>::Array(
                    _Ty &&__init_value
            )       noexcept
    : Array()
{ __init__(__init_value); }

template<class _Ty, size_t _Size>
Array<_Ty, _Size>::Array(
                    const _Ty *__Arr
            )       noexcept
    : Array()
{
    std::copy(
        __Arr,
        __Arr + _Size,
        __beg
    );
}

template<class _Ty, size_t _Size>
Array<_Ty, _Size>::Array(
                const std::initializer_list<_Ty>&
                    _init_lst
            )       noexcept
    : Array()
{ __init__(_init_lst); }

template<class _Ty, size_t _Size>
Array<_Ty, _Size>::Array(
                std::initializer_list<_Ty>&
                    _init_lst
            )      noexcept
    : Array(std::move(_init_lst))
{}

template<class _Ty, size_t _Size>
Array<_Ty, _Size>::Array(
                std::initializer_list<_Ty>&&
                    _init_lst
            )       noexcept
    : Array()
{ __init__(_init_lst); }

template<class _Ty, size_t _Size>
Array<_Ty, _Size>::Array(
                    const Array &
                        _another_Arr
            )       noexcept
    : Array()
{
    std::copy(
        _another_Arr.begin(),
        _another_Arr.end(),
        __beg
    );
}

template<class _Ty, size_t _Size>
Array<_Ty, _Size>::~Array() noexcept
= default;

template<class _Ty, size_t _Size>
inline
typename Array<_Ty, _Size>::iterator
    Array<_Ty, _Size>::begin() const noexcept
{ return __beg; }

template<class _Ty, size_t _Size>
inline
typename Array<_Ty, _Size>::iterator
    Array<_Ty, _Size>::last() const noexcept
{ return __ed - 1; }

template<class _Ty, size_t _Size>
inline
typename Array<_Ty, _Size>::iterator
    Array<_Ty, _Size>::end() const noexcept
{ return __ed; }

template<class _Ty, size_t _Size>
inline constexpr
typename Array<_Ty, _Size>::const_iterator
    Array<_Ty, _Size>::cbegin() const noexcept
{ return __beg; }

template<class _Ty, size_t _Size>
inline constexpr
typename Array<_Ty, _Size>::const_iterator
    Array<_Ty, _Size>::clast() const noexcept
{ return __ed - 1; }

template<class _Ty, size_t _Size>
inline constexpr
typename Array<_Ty, _Size>::const_iterator
    Array<_Ty, _Size>::cend() const noexcept
{ return __ed; }

template<class _Ty, size_t _Size>
inline constexpr size_t
    Array<_Ty, _Size>::size() const noexcept
{ return _Size; }

template<class _Ty, size_t _Size>
_Ty
    Array<_Ty, _Size>::max() const
{
    _Ty __Cmp = *begin();
    for(auto __item: begin()) __Cmp = __Cmp > __item ? __Cmp : __item;
    return __Cmp;
}

template<class _Ty, size_t _Size>
_Ty
    Array<_Ty, _Size>::min() const
{
    _Ty __Cmp = *begin();
    for(auto __item: begin()) __Cmp = __Cmp < __item ? __Cmp : __item;
    return __Cmp;
}

template<class _Ty, size_t _Size>
inline void
    Array<_Ty, _Size>::remove() const
{ delete[] __beg; }

template<class _Ty, size_t _Size>
inline
typename Array<_Ty, _Size>::const_reference
    Array<_Ty, _Size>::operator[](const size_t &__index) const noexcept
{ return *(begin() + __index); }

template<class _Ty, size_t _Size>
inline
typename Array<_Ty, _Size>::reference
    Array<_Ty, _Size>::operator[](const size_t &__index) noexcept
{
    return const_cast<_Ty&>(
        static_cast<const Array&>(*this)
            [__index]
    );
}

template<class _Ty, size_t _Size>
inline
void
    Array<_Ty, _Size>::__init__(const _Ty &__init_value)
{
    auto __item = begin() - 1;
    for(; ++__item != __ed;) *__item = __init_value;
}

template<class _Ty, size_t _Size>
inline
void
    Array<_Ty, _Size>::__init__(
                            const std::initializer_list<_Ty>
                                &_init_lst
                            )
{
    size_t __index = -1;
    for(auto __item: _init_lst) *(begin() + (++__index)) = __item;
}

#endif

Heap

“heap.h”

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
146
147
148
149
150
151
#ifndef __HEAP_H__
#define __HEAP_H__
#include <iosfwd>
#include <vector>

template<class _Ty> class Heap;

template<class _Ty>
class Heap{
public:
    Heap(std::initializer_list<_Ty>,
         const bool& = big_root)                 noexcept;
    ~Heap()                                      noexcept;
    size_t                             insert(const _Ty&);
    bool                                    remove_root();
    size_t  size()                                  const;
    const _Ty     root_item()                       const;
    constexpr bool _whoami()                        const;
    bool empty()                                    const;
    enum                     { big_root = 0, small_root };
    
private:
    std::vector<_Ty>                               _Elems;
    size_t                                          _size;
    const bool                                     _style;
    bool nodecmp(const size_t&, const size_t&)      const;
    size_t  _parent(const size_t&)                  const;
    size_t  l_child(const size_t&)                  const;
    size_t  r_child(const size_t&)                  const;
};

template<class _Ty>
Heap<_Ty>::Heap(std::initializer_list<_Ty> _lst, const bool &_flg) noexcept
    : _size(0), _style(_flg)
{
    for(auto _item: _lst) insert(_item);
}

template<class _Ty>
Heap<_Ty>::~Heap() noexcept
{}

template<class _Ty>
inline
bool Heap<_Ty>::nodecmp(const size_t &_node, const size_t &_another) const
{
    if(_style) return _Elems[_node] <= _Elems[_another];
    return _Elems[_node] >= _Elems[_another];
}

template<class _Ty>
size_t Heap<_Ty>::insert(const _Ty &_nItem)
{   
    ++_size;
    if(_size == 1 && !_Elems.empty()) { _Elems[0] = _nItem;return 0; }
    size_t _pos = _size - 1;

    _Elems.push_back(_nItem);
    while(_pos != 0)
    {
        size_t parent = _parent(_pos);
        if(nodecmp(parent, _pos)) break;
        _Ty _temp = _Elems[_pos];
        _Elems[_pos] = _Elems[parent];
        _Elems[parent] = _temp;
        _pos=parent;
    }
    return _pos;
}

template<class _Ty>
bool Heap<_Ty>::remove_root()
{
    if(!_size) { std::cerr << "Heap Underflow\n"; }
    else if(_size == 1) { --_size;return false; }

    _Ty _temp = _Elems[0];
    _Elems[0] = _Elems[_size - 1];
    _Elems.erase(_Elems.begin() + _size - 1);
    --_size;

	size_t _index = 0;

	while(1)
    {
		size_t lchild = l_child(_index),
               rchild = r_child(_index);
		if(lchild >= _size - 1) lchild = _index;
		if(rchild >= _size - 1) rchild = _index;
		if(nodecmp(_index, lchild)
        && nodecmp(_index, rchild)) break;
		size_t swap_child = nodecmp(lchild, rchild)
                                ? lchild: rchild;
		_Ty _temp = _Elems[swap_child];
        _Elems[swap_child] = _Elems[_index];
        _Elems[_index] = _temp;

		_index = swap_child;
	}
    return true;
}

template<class _Ty>
inline
size_t Heap<_Ty>::size() const {
    return _size;
}

template<class _Ty>
inline
const _Ty Heap<_Ty>::root_item() const
{
    return _Elems[0];
}

template<class _Ty>
inline
size_t Heap<_Ty>::_parent(const size_t &_curr) const
{
    return (_curr - 1) / 2;
}

template<class _Ty>
inline
size_t Heap<_Ty>::l_child(const size_t &_parent) const
{
    return _parent * 2 + 1;
}

template<class _Ty>
inline
size_t Heap<_Ty>::r_child(const size_t &_parent) const
{
    return _parent * 2 + 2;
}

template<class _Ty>
inline
constexpr bool Heap<_Ty>::_whoami() const {
    if(_style) return small_root;
    return big_root;
}

template<class _Ty>
inline
bool Heap<_Ty>::empty() const
{
    return _size > 0;
}

#endif

Section 2: Polynomial Division

Forward declarations

“fractionfwd.h”

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
/** This header contains the forward declarations
 *  of class fraction, multinomial, complex etc.
 */ 
#ifndef __FRACTIONFWD_H__
#define __FRACTIONFWD_H__

#include <map>
#include <iosfwd>
#include <string>
#include <typeinfo>
#include <functional>

class complex;
class fraction;
class polynomial;

using _multimap  = std::map<long long, fraction>;
using _multipair = std::pair<long long, fraction>;

/* fraction-related facilities defined as below: */  

fraction getfrac()                                       noexcept;
fraction operator+(const fraction&, const fraction&)     noexcept;
fraction operator-(const fraction&, const fraction&)     noexcept;
fraction operator*(const fraction&, const fraction&)     noexcept;
fraction operator/(const fraction&, const fraction&)     noexcept;
bool operator==(const fraction&, const fraction&)        noexcept;
bool operator!=(const fraction&, const fraction&)        noexcept;
bool operator>(const fraction&, const fraction&)         noexcept;
bool operator>=(const fraction&, const fraction&)        noexcept;
bool operator<(const fraction&, const fraction&)         noexcept;
bool operator<=(const fraction&, const fraction&)        noexcept;
// std::istream& operator>>(std::istream&, fraction)        noexcept;
std::ostream& operator<<(std::ostream&, const fraction&) noexcept;

/* polynomial-related facilities defined as below: */

polynomial gcf(const polynomial&, const polynomial&)     noexcept;

#endif

Implements

“fraction.h”

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
/*=================================================================================*
 *=  Header name: "fraction.h"                                                    =
 *=  Description: This header includes some updated facilities of fraction.       =
 *=  Rewritten on: 2020/12/5 Sat                                                  =
 *=  Author: Offensive77                                                          =
 *=  Version: 1.1.0                                                               =
 *=  Copyright reserved.                                                          =
 *=================================================================================*/ 

#ifndef __FRACTION_H__
#define __FRACTION_H__

#define __ABS(x) ((x) >= 0 ? (x) : -(x))
#define Frac(x) typeid(x) == typeid(NULL) ? \
                fraction(#x) : fraction(x)
#define New_Frac(x) typeid(x) == typeid(NULL) ? \
                    new fraction(#x) : new fraction(x)
#define Unique_Frac(x) typeid(x) == typeid(NULL) ? \
                       std::make_unique<fraction>(#x) : std::make_unique<fraction>(x)

#include "fractionfwd.h"

std::function<const long long(const long long&, const long long&)>
    packaged_greatest_common_divisor =
[](const long long& __1, const long long& __2) -> const long long
{
    return __1 % __2 ? packaged_greatest_common_divisor(__2, __1 % __2) : __2;
};


// An interface for gcd algorithm, also for initialization.
auto
    greatest_common_divisor =
[](const long long& __1, const long long& __2)
{
    bool symb = (__2 > 0) ? true : false;
    const long long& __3
    = __ABS(__1) >= __ABS(__2) ? __ABS(__1) : __ABS(__2);
    const long long& __4
    = __ABS(__1) <  __ABS(__2) ? __ABS(__1) : __ABS(__2);
    if (symb)
        return __3 % __4 ? 
              packaged_greatest_common_divisor(__4, __3 % __4)
            : __4;
    // Else situation
    return - (__3 % __4 ?
              packaged_greatest_common_divisor(__ABS(__4), __ABS(__3) % __ABS(__4))
            : __ABS(__4));
};

auto
    least_common_multiplier =
[](const long long __1, const long long __2) ->const long long
{
    return __1 / greatest_common_divisor(__1, __2) * __2;
};

class
    fraction
{
    friend polynomial;
    friend complex;
    using LL = long long;
    using string = std::string;

private:
    LL                                                                     q;
    LL                                                                     p;
    template <int _Num> void change_at(const LL&)                   noexcept;

public:
    fraction(const LL& = 0, const LL& = 1)                          noexcept;
    fraction(LL&, LL&)                                              noexcept;
    fraction(LL&&, LL&)                                             noexcept;
    fraction(LL&, LL&&)                                             noexcept;
    fraction(LL&&, LL&&)                                            noexcept;
    fraction(const fraction&)                                       noexcept;
    explicit fraction(const string&)                                noexcept;
    explicit fraction(string&)                                      noexcept;
    explicit fraction(string&&)                                     noexcept;
    ~fraction()                                                     noexcept;
    void reduction()                                                noexcept;
    void display()                                            const noexcept;
    void to_latex()                                           const noexcept;
    string to_string()                                        const noexcept;
    const LL get_at(const bool&)                              const noexcept;
    fraction operator+=(const fraction&)                            noexcept;
    fraction operator-=(const fraction&)                            noexcept;
    fraction operator*=(const fraction&)                            noexcept;
    fraction operator/=(const fraction&)                            noexcept;
    fraction& operator=(const fraction&)                            noexcept;
    // friend std::istream& operator>>(std::istream&, fraction)        noexcept;
    friend std::ostream& operator<<(std::ostream&, const fraction&) noexcept;
    friend fraction getfrac()                                       noexcept;
	friend polynomial gcf(const polynomial&, const polynomial&)     noexcept;
};

inline
    fraction::fraction(const LL& _q, const LL& _p) noexcept
    : q(_q), p(_p) { reduction(); }

inline
    fraction::fraction(LL& _q, LL& _p) noexcept
    : fraction(std::move(_q), std::move(_p)) {}

inline
    fraction::fraction(LL&& _q, LL& _p) noexcept
    : fraction(std::move(_q), std::move(_p)) {}

inline
    fraction::fraction(LL& _q, LL&& _p) noexcept
    : fraction(std::move(_q), std::move(_p)) {}

inline
    fraction::fraction(LL&& _q, LL&& _p) noexcept
    : q(_q), p(_p) { reduction(); }

inline
    fraction::fraction(const std::string& str_frac) noexcept
{
    size_t len = str_frac.size();
    for(size_t i = 0; i < len; ++i)
        if(str_frac[i] == '/')
        {
            q = std::stoll(str_frac.substr(0, i));
            p = std::stoll(str_frac.substr(i + 1, len - i - 1));
            reduction();
            return;
        }
    q = std::stoll(str_frac);
    p = 1;
}

inline
    fraction::fraction(std::string& str_frac) noexcept
    : fraction(std::move(str_frac)) {}

inline
    fraction::fraction(std::string&& str_frac) noexcept
{
    size_t len = str_frac.size();
    for(size_t i = 0; i < len; ++i)
        if(str_frac[i] == '/')
        {
            q = std::stoll(str_frac.substr(0, i));
            p = std::stoll(str_frac.substr(i + 1, len - i - 1));
            reduction();
            return;
        }
    q = std::stoll(str_frac);
    p = 1;
}

inline
    fraction::fraction(const fraction& frac) noexcept
{
    q = frac.q;
    p = frac.p;
}


inline
    fraction::~fraction() noexcept {}

inline std::string
    fraction::to_string() const noexcept
{ return p == 1 ? std::to_string(q) : std::to_string(q) + "/" + std::to_string(p); }

inline const long long
    fraction::get_at(const bool &_tag) const noexcept
{
    if(_tag) return p;
    return q;
}

template <int _Num>
inline void
    fraction::change_at(const long long& num) noexcept
{
    if(_Num) p = num;
    q = num;
}

void fraction::reduction() noexcept
{
    if(!q) { p = 1;return; }
    LL z = greatest_common_divisor(q, p);
    p /= z;
    q /= z;
    if(p * q < 0)
    { q = -__ABS(q);p = __ABS(p); }
}

void fraction::display() const noexcept
{
    if(p!=1) printf("%lld/%lld", q ,p);
    else printf("%lld", q);
}

void fraction::to_latex() const noexcept
{
    if(q > 0 && p!=1) printf("\\frac{%lld}{%lld}", q ,p);
    else if(q > 0) printf("{%lld}", q);
    else if(q < 0 && p != 1) printf("-\\frac{%lld}{%lld}", -q, p);
    else printf("-{%lld}", -q);
}

inline fraction
    fraction::operator+=(const fraction& frac) noexcept
{
    *this = *this + frac;
    return *this;
}

inline fraction
    fraction::operator-=(const fraction& frac) noexcept
{
    *this = *this - frac;
    return *this;
}

inline fraction
    fraction::operator*=(const fraction& frac) noexcept
{
    *this = *this * frac;
    return *this;
}

inline fraction
    fraction::operator/=(const fraction& frac) noexcept
{
    *this = *this / frac;
    return *this;
}

inline fraction&
    fraction::operator=(const fraction& frac) noexcept
{
    q = frac.q;
    p = frac.p;
    return *this;
}

std::ostream& operator<<(std::ostream& os, const fraction& frac) noexcept
{
    if(frac.p == 1) printf("%lld", frac.q);
    else printf("%lld/%lld", frac.q, frac.p);
    return os;
}

fraction getfrac() noexcept
{
    std::string str_frac;
    std::cin >> str_frac;
    return fraction(str_frac);
}

inline fraction
    operator+(const fraction &lhs,
              const fraction &rhs) noexcept
{
    auto z = least_common_multiplier(lhs.get_at(1),
                                     rhs.get_at(1));
    return fraction(z / lhs.get_at(1) * lhs.get_at(0) +
                    z / rhs.get_at(1) * rhs.get_at(0),
                    z);
}

inline fraction
    operator-(const fraction &lhs,
              const fraction &rhs) noexcept
{
    auto z = least_common_multiplier(lhs.get_at(1),
                                     rhs.get_at(1));
    return fraction(z / lhs.get_at(1) * lhs.get_at(0) -
                    z / rhs.get_at(1) * rhs.get_at(0),
                    z);
}

inline fraction
    operator*(const fraction &lhs,
              const fraction &rhs) noexcept
{ return fraction(lhs.get_at(0) * rhs.get_at(0), lhs.get_at(1) * rhs.get_at(1)); }

inline fraction
    operator/(const fraction &lhs,
              const fraction &rhs) noexcept
{ return fraction(lhs.get_at(0) * rhs.get_at(1), lhs.get_at(1) * rhs.get_at(0)); }

inline bool
    operator==(const fraction &lhs,
               const fraction &rhs) noexcept
{ return lhs.get_at(0) * rhs.get_at(1) == lhs.get_at(1) * rhs.get_at(0); }

inline bool
    operator!=(const fraction &lhs,
               const fraction &rhs) noexcept
{ return lhs.get_at(0) * rhs.get_at(1) != lhs.get_at(1) * rhs.get_at(0); }

inline bool
    operator>(const fraction &lhs,
               const fraction &rhs) noexcept
{ return lhs.get_at(0) * rhs.get_at(1) > lhs.get_at(1) * rhs.get_at(0); }

inline bool
    operator>=(const fraction &lhs,
               const fraction &rhs) noexcept
{ return lhs.get_at(0) * rhs.get_at(1) >= lhs.get_at(1) * rhs.get_at(0); }

inline bool
    operator<(const fraction &lhs,
               const fraction &rhs) noexcept
{ return lhs.get_at(0) * rhs.get_at(1) < lhs.get_at(1) * rhs.get_at(0); }

inline bool
    operator<=(const fraction &lhs,
               const fraction &rhs) noexcept
{ return lhs.get_at(0) * rhs.get_at(1) <= lhs.get_at(1) * rhs.get_at(0); }

#undef __INCLUDES__
#undef __ABS
#endif

“polynomial.h”

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
/** This header contains the realization of polynomial division.
 *  Copyright(C) @ Offensive77
 */

#ifndef __POLYNOMIAL_DIVISION_H_
#define __POLYNOMIAL_DIVISION_H_

#define AddItem(x, y) insert(_multipair((x), Frac(y)))

#include "fractionfwd.h"
#include "fraction.h"

class
	polynomial
{
using LL = long long;

public:
	explicit polynomial()													     noexcept;
	explicit polynomial(const std::map<LL, fraction>&)                           noexcept;
	~polynomial()                                                                noexcept;
	void suffix_at(const int&, const bool& = stringify)                    const noexcept;
	void to_latex()                                                        const noexcept;
	void display_polynomial(const bool& = stringify)                       const noexcept;
	unsigned update_degree()                                               const noexcept;
	polynomial derivative()											       const noexcept;
	polynomial operator/(const polynomial&)                                const noexcept;
	polynomial operator%(const polynomial&)                                const noexcept;
	polynomial& operator=(const polynomial&)		        		     		 noexcept;
	friend polynomial process_polynomial(polynomial)                             noexcept;
	friend polynomial get_polynomial()                                           noexcept;
	friend polynomial gcf(const polynomial&, const polynomial&)                  noexcept;
	enum                                                                  {stringify = 0};

private:
	enum                                                                  {max_size = 45};
	fraction                                                              times[max_size];
	mutable unsigned                                                               degree;
};

inline
	polynomial::polynomial() noexcept
= default;

inline
	polynomial::polynomial(const std::map<LL, fraction>& multi_map) noexcept
		: polynomial()
{
	signed temp = 0;
	for(auto _item : multi_map) {
		times[_item.first] += _item.second;
		if(_item.first > temp) temp = _item.first;
	}
	degree = temp;
}

inline
	polynomial::~polynomial() noexcept {}

void
	polynomial::suffix_at(
						const int& index,
		                const bool& arg
				)		const noexcept
{
	std::function<void()>
		fun
		{
			arg == stringify ?
				std::bind(
					&fraction::display,
					times[index]
				):
				std::bind(
					&fraction::to_latex,
					times[index]
				)
		};
	if (!index)
		fun();
	else if(
		index == 1)
	{
		if(times[1] != 1) fun();
		printf("x");
	}
	else if (times[index] == 1)
		printf("x^{%d}", index);
	else if(times[index] == -1)
		printf("-x^{%d}", index);
	else
	{
		fun();
		printf("x^{%d}", index);
	}
}

void
	polynomial::display_polynomial(const bool& arg) const noexcept
{
	int deg = degree;
	if (!deg)
	{
		times[0].display();
		printf("\n");
		return;
	}
	bool flag = 1;
	int counted = 0;
	for (int i = 0; i <= deg; ++i)
		if (times[i].q)
			++counted;
	for (int i = deg; i >= 0; --i)
	{
		if (flag)
		{
			flag = 0;
			suffix_at(i, arg);
			--counted;
			continue;
		}
		if (times[i] > 0)
		{
			printf("+");
			suffix_at(i, arg);
			--counted;
		}
		else if (times[i] < 0)
		{
			suffix_at(i, arg);
			--counted;
		}
		if (!counted)
		{
			printf("\\\\\n");
			break;
		}
	}
}

inline void
	polynomial::to_latex() const noexcept
{ display_polynomial(1); }

polynomial
	get_polynomial() noexcept
{
	polynomial result;
	int temp = -1;
	fraction m;
	int n;
	while (std::cin >> n)
	{
		if (n == -1)
			break;
		m = getfrac();
		result.times[n] += m;
		if (n > temp)
			temp = n;
	}
	result.degree = temp;
	return result;
}

unsigned
	polynomial::update_degree() const noexcept
{
	for (int i = degree; i >= 1; i--)
		if (times[i] != 0)
		{
			degree = i;
			return i;
		}
	degree = 0;
	return 0;
}

polynomial
	polynomial::derivative() const noexcept
{
	polynomial derivated = *this;
	derivated.degree = degree - 1;
	size_t i = 1;
	for(; i <= degree; ++i)
	{
		derivated.times[i - 1] = i * times[i];
	}
	return derivated;
}

polynomial
	polynomial::operator/(const polynomial &gx) const noexcept
{
	polynomial fx = *this, qx;
	if (!degree && !(gx.degree))
	{
		qx.degree = 0;
		qx.times[0] = fx.times[0] / gx.times[0];
		return qx;
	}
	const unsigned &deg = gx.degree;
	qx.degree = fx.degree - gx.degree;
	if (qx.degree < 0) qx.degree = 0;
	while (fx.degree >= deg)
	{
		fraction temp = fx.times[fx.degree] / gx.times[deg];
		int index = fx.degree - deg;
		qx.times[index] = temp;
		for (int j = fx.degree; j >= index; --j)
			fx.times[j] -= temp * gx.times[j - index];
		fx.update_degree();
	}
	return qx;
}

polynomial
	polynomial::operator%(const polynomial &gx) const noexcept
{
	polynomial fx = *this, qx;
	if (!degree && !(gx.degree))
	{
		fx.degree = 0;
		fx.times[0].q = 0;
		return fx;
	}
	const unsigned &deg = gx.degree;
	qx.degree = fx.degree - gx.degree;
	while (fx.degree >= deg)
	{
		fraction temp = fx.times[fx.degree] / gx.times[deg];
		int index = fx.degree - deg;
		qx.times[index] = temp;
		for (int j = fx.degree; j >= index; j--)
			fx.times[j] -= temp * gx.times[j - index];
		fx.update_degree();
	}
	return fx;
}

inline polynomial&
	polynomial::operator=(const polynomial& gx) noexcept
{
	this->degree = gx.degree;
	for(int i = degree; i>=0; --i) times[i] = gx.times[i];
	return *this;
}

polynomial
	process_polynomial(polynomial fx) noexcept
{
	int deg = fx.degree;
	fraction temp = fx.times[deg];
	for (int i = deg; i >= 0; i--)
	{
		if (fx.times[i] != 0)
			fx.times[i] = fx.times[i] / temp;
	}
	return fx;
}

polynomial
	gcf(const polynomial& fx, const polynomial& gx) noexcept
{
	if (!(fx.degree) && !(gx.degree))
	{
		polynomial gcfx;
		if (!(fx.times[0].get_at(0)) && !(gx.times[0].get_at(0)))
			gcfx.times[0].change_at<0>(0);
		else
			gcfx.times[0].change_at<0>(1);
		gcfx.degree = 0;
		return gcfx;
	}
	if (!(gx.degree))
		return gx;
	polynomial rx = fx % gx;
	if (!(rx.degree) && rx.times[0] == 0)
	{
		polynomial res = process_polynomial(gx);
		return res;
	}
	return gcf(gx, rx);
}

#endif

End of the file

Author: Endsieg77

Link: https://endsieg77.github.io/2021/01/07/my-header-library/

Post on: January 7th 2021, 4:49:38 pm

Update on: January 19th 2021, 12:40:42 pm

CATALOG
  1. 1. Overview
  2. 2. Section 1: Containers
    1. 2.1. Forward declarations
      1. 2.1.1. “standard_container.h”
      2. 2.1.2. “lists.h”
      3. 2.1.3. “listfwd.h”
    2. 2.2. Link List
      1. 2.2.1. “link_list.h”
      2. 2.2.2. “loop_list.h”
    3. 2.3. Array
      1. 2.3.1. “array.h”
    4. 2.4. Heap
      1. 2.4.1. “heap.h”
  3. 3. Section 2: Polynomial Division
    1. 3.1. Forward declarations
      1. 3.1.1. “fractionfwd.h”
    2. 3.2. Implements
      1. 3.2.1. “fraction.h”
      2. 3.2.2. “polynomial.h”
  4. 4. End of the file
Total : 26
2021
2020
basic algebra_and_geometry warstory WOC realization remedies utilities Poems Marks English Plugins PyPinyin emoji retrospect grammatical jQuery Data Structure
Maths F2E Cpp algorithm Centos7 Hollow-Knight Linux Cpp/QT study hexo Python Centos7/Linux dishonor C functional Latex Matlab letters Python/Project