PriorityStack/PriorityStack.h at master · seregamikhailov/PriorityStack · 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
//
// Created by Serg on 25.10.2024.
//

#ifndef PRIORITYSTACK_H
#define PRIORITYSTACK_H
#include <ostream>
using namespace std;

class PriorityStack {
private:
    struct Node {
        int value;
        Node *right;
        Node *left;
        int priority;
        int height;

        Node(int value, int priority) {
            this->value = value;
            this->priority = priority;
            left = nullptr;
            right = nullptr;
            height = 1;
        }
    };

    Node *root;

    Node *add(Node *node, int value, int priority);

    int getHeight(Node *node);

    int getBalanceFactor(Node *node);

    Node *rightRotate(Node *y);

    Node *leftRotate(Node *x);

    Node *balance(Node *node);

    int count(Node *node, int priority) const;

    Node *removeNode(Node *node, int priority, int &value, bool &found);

    Node *findMin(Node *node);

    Node *removeNodesWithPriority(Node *node, int priority, int *&buffer, int &count, int &capacity);

    Node *mergeSubtrees(Node *left, Node *right);

    Node *findMaxNode(Node *node);

    Node *contains(Node *node, int value, int priority) const;

    void addAllNodes(Node *node);

    int getMaxPriority(Node *node) const;

    int getNextLowerPriority(Node *node, int currentPriority) const;

    void deleteTree(Node *node);

    void subtractElements(Node *node, const PriorityStack &other, PriorityStack &result);

    void addIntersection(Node *node, const PriorityStack &other, PriorityStack &result);

    Node *copyTree(Node *node);

    void printInOrder(Node *node, std::ostream &stream) const;

public:
    PriorityStack();

    ~PriorityStack();

    PriorityStack(const PriorityStack &other);

    void clear();

    PriorityStack &operator=(const PriorityStack &other);

    void add(int value, int priority);

    bool get(int &value, int &priority);

    bool peek(int &value, int &priority);

    int count(int priority = 0) const;

    bool contains(int value, int priority = 0) const;

    int get(int priority, int *&buffer);

    friend ostream &operator<<(ostream &os, const PriorityStack &stack);

    bool operator==(const PriorityStack &other) const;

    bool operator!=(const PriorityStack &other) const;

    bool operator>(const PriorityStack &other) const;

    bool operator<(const PriorityStack &other) const;

    bool operator>=(const PriorityStack &other) const;

    bool operator<=(const PriorityStack &other) const;

    PriorityStack operator+(const PriorityStack &other);

    PriorityStack operator-(const PriorityStack &other);

    PriorityStack operator&(const PriorityStack &other);
};


#endif //PRIORITYSTACK_H