Sayonara Player
Tree.h
1 
2 /* Copyright (C) 2011-2019 Lucio Carreras
3  *
4  * This file is part of sayonara player
5  *
6  * This program is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * (at your option) any later version.
10 
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15 
16  * You should have received a copy of the GNU General Public License
17  * along with this program. If not, see <http://www.gnu.org/licenses/>.
18  */
19 
20 #ifndef TREE_H
21 #define TREE_H
22 
23 #include <QList>
24 #include <algorithm>
25 
26 namespace Util
27 {
28  template<typename T>
33  class Tree
34  {
35  public:
36 
37  Tree* parent=nullptr;
38  T data;
39  QList<Tree*> children;
40 
41  Tree()
42  {
43  parent = nullptr;
44  }
45 
50  Tree(const T& data_) : Tree()
51  {
52  data = data_;
53  }
54 
55  ~Tree()
56  {
57  for(Tree* child : children){
58  delete child; child = nullptr;
59  }
60 
61  children.clear();
62  data = T();
63  }
64 
69  {
70  Tree* node = new Tree(this->data);
71 
72  for(Tree* child : children){
73  node->children << child->copy();
74  }
75 
76  return node;
77  }
78 
79 
86  {
87  node->parent = this;
88 
89  this->children << node;
90  this->sort(false);
91 
92  return node;
93  }
94 
95  Tree* add_child(const T& data)
96  {
97  Tree* node = new Tree(data);
98  return add_child(node);
99  }
100 
101 
107  Tree* remove_child(Tree* deleted_node)
108  {
109  deleted_node->parent = nullptr;
110 
111  for(int i=0; i < children.size(); i++){
112  Tree* node = children[i];
113 
114  if(node == deleted_node){
115  deleted_node = children.takeAt(i);
116  i--;
117  }
118  }
119 
120  return deleted_node;
121  }
122 
123 
128  void move(Tree* new_parent)
129  {
130  parent->remove_child(data);
131  new_parent->add_child(this);
132  }
133 
138  void sort(bool recursive)
139  {
140  int i;
141 
142  if(children.isEmpty()){
143  return;
144  }
145 
146  auto lambda = [](Tree* a, Tree* b){
147  return (a->data < b->data);
148  };
149 
150  std::sort(children.begin(), children.end(), lambda);
151 
152 
153  i=0;
154  for(Tree* child : children){
155  if(recursive){
156  child->sort(recursive);
157  }
158  i++;
159  }
160  }
161  };
162 }
163 
164 #endif // TREE_H
Util::Tree::Tree
Tree(const T &data_)
Tree constructor.
Definition: Tree.h:50
QList
Definition: EngineUtils.h:33
Util
Helper functions.
Definition: GenreView.h:35
Util::Tree
The Tree class.
Definition: GenreView.h:38
Util::Tree::remove_child
Tree * remove_child(Tree *deleted_node)
remove a node from the current node
Definition: Tree.h:107
Util::Tree::add_child
Tree * add_child(Tree *node)
adds a child to the given node
Definition: Tree.h:85
Util::Tree::move
void move(Tree *new_parent)
move current node to a new parent
Definition: Tree.h:128
Util::Tree::copy
Tree * copy()
Definition: Tree.h:68
Util::Tree::sort
void sort(bool recursive)
sort children of all nodes in ascending way according to their data
Definition: Tree.h:138