1 /*
2 * scrm is an implementation of the Sequential-Coalescent-with-Recombination Model.
3 *
4 * Copyright (C) 2013, 2014 Paul R. Staab, Sha (Joe) Zhu, Dirk Metzler and Gerton Lunter
5 *
6 * This file is part of scrm.
7 *
8 * scrm is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program. If not, see <http://www.gnu.org/licenses/>.
20
21 */
22
23 #include "node_container.h"
24
25 /*******************************************************
26 * Con- & Destructor
27 *******************************************************/
28
NodeContainer()29 NodeContainer::NodeContainer() {
30 set_first(NULL);
31 set_last(NULL);
32 unsorted_node_ = NULL;
33 size_ = 0;
34
35 node_counter_ = 0;
36 lane_counter_ = 0;
37 std::vector<Node>* new_lane = new std::vector<Node>();
38 new_lane->reserve(10000);
39 node_lanes_.push_back(new_lane);
40 }
41
NodeContainer(const NodeContainer & nc)42 NodeContainer::NodeContainer(const NodeContainer &nc) {
43 size_ = 0;
44 set_first(NULL);
45 set_last(NULL);
46
47 node_counter_ = 0;
48 lane_counter_ = 0;
49 std::vector<Node>* new_lane = new std::vector<Node>();
50 new_lane->reserve(10000);
51 node_lanes_.push_back(new_lane);
52
53 this->unsorted_node_ = NULL;
54
55 std::map<Node const*, Node*> node_mapping;
56 node_mapping[NULL] = NULL;
57
58 for (auto it = nc.iterator(); it.good(); ++it) {
59 Node *node = this->createNode(**it);
60 //Node *node = new Node(**it);
61 node_mapping[*it] = node;
62 this->add(node);
63 }
64 assert( this->sorted() );
65
66 for (auto it = iterator(); it.good(); ++it) {
67 if (!(*it)->is_root()) (*it)->set_parent(node_mapping[(*it)->parent()]);
68 (*it)->set_first_child(node_mapping[(*it)->first_child()]);
69 (*it)->set_second_child(node_mapping[(*it)->second_child()]);
70 }
71 unsorted_node_ = node_mapping[nc.unsorted_node_];
72 }
73
74 /*******************************************************
75 * Management of Nodes
76 *******************************************************/
77
at(size_t nr) const78 Node* NodeContainer::at(size_t nr) const {
79 Node* current = first();
80
81 for (size_t i=0; i < nr; ++i) {
82 assert(current != NULL);
83 current = current->next();
84 }
85
86 if ( current == NULL ) throw std::out_of_range("NodeContainer out of range");
87 return current;
88 }
89
90 // Adds 'node' to the container
push_back(Node * node)91 void NodeContainer::push_back( Node* node ) {
92 ++size_;
93 if ( this->first() == NULL ) {
94 this->set_first( node );
95 this->set_last( node );
96 return;
97 }
98 assert( this->first() != NULL );
99
100 //Adding to the End, similar to vector::push_back
101 node->set_previous(this->last());
102 node->set_next(NULL);
103 this->last()->set_next(node);
104 this->set_last(node);
105 return;
106 }
107
108 // Adds 'node' to the container
push_front(Node * node)109 void NodeContainer::push_front( Node* node ) {
110 ++size_;
111 if ( this->first() == NULL ) {
112 this->set_first( node );
113 this->set_last( node );
114 return;
115 }
116 assert( this->first() != NULL );
117
118 //Adding to the End, similar to vector::push_back
119 node->set_next(first());
120 node->set_previous(NULL);
121 first()->set_previous(node);
122 this->set_first(node);
123 return;
124 }
125
126
127
128 // Adds 'node' to the container
129 // If you know that the node is higher in the tree than a other node,
130 // than you can specify the latter as 'after_node' to speedup the process.
add(Node * node,Node * after_node)131 void NodeContainer::add(Node* node, Node* after_node) {
132 ++size_;
133
134 if (first() == NULL) {
135 this->set_first(node);
136 this->set_last(node);
137 return;
138 }
139 assert(first() != NULL);
140
141 // Before first node?
142 if (node->height() < first()->height()) {
143 node->set_next(first());
144 node->set_previous(NULL);
145 first()->set_previous(node);
146 this->set_first(node);
147 assert( this->sorted() );
148 return;
149 }
150
151 // After last node?
152 if ( node->height() >= last()->height() ) {
153 node->set_previous(last());
154 node->set_next(NULL);
155 last()->set_next(node);
156 this->set_last(node);
157 assert( this->sorted() );
158 return;
159 }
160
161 assert( after_node == NULL || node->height() >= after_node->height() );
162
163
164 if (after_node == NULL) after_node = first();
165 Node* current = after_node;
166 // Find position in between
167 while ( current->height() <= node->height() ) {
168 assert( !current->is_last() );
169 if ( !current->is_root() ) {
170 if ( current->parent_height() < node->height() ) {
171 current = current->parent();
172 continue;
173 }
174 }
175 current = current->next();
176 }
177
178 // And add the node;
179 this->add_before(node, current);
180 assert( this->sorted() );
181 }
182
183
remove(Node * node,const bool & del)184 void NodeContainer::remove(Node *node, const bool &del) {
185 --size_;
186 if ( node->is_first() && node->is_last() ) {
187 this->set_first(NULL);
188 this->set_last(NULL);
189 }
190 else if ( node->is_first() ) {
191 this->set_first(node->next());
192 node->next()->set_previous(NULL);
193 }
194 else if ( node->is_last() ) {
195 this->set_last(node->previous());
196 node->previous()->set_next(NULL);
197 }
198 else {
199 node->previous()->set_next(node->next());
200 node->next()->set_previous(node->previous());
201 }
202
203 if (del) free_slots_.push(node);
204 assert( this->sorted() );
205 }
206
207
move(Node * node,const double new_height)208 void NodeContainer::move(Node *node, const double new_height) {
209 assert( node != NULL );
210
211 // Stupid edge case first: We may have only one node.
212 if ( node->is_first() && node->is_last() ) {
213 node->set_height(new_height);
214 return;
215 }
216
217 // Remove from old place
218 remove(node, false);
219
220 // Add at new place
221 Node* current = NULL;
222 if ( node->height() < new_height ) {
223 if ( node->is_first() ) current = NULL;
224 else current = node->previous();
225 } else {
226 current = first();
227 }
228
229 node->set_height(new_height);
230 this->add(node, current);
231 assert( this->sorted() );
232 }
233
234
clear()235 void NodeContainer::clear() {
236 set_first(NULL);
237 set_last(NULL);
238 this->size_ = 0;
239 this->node_counter_ = 0;
240 this->lane_counter_ = 0;
241
242 // Clear free_slots_
243 std::stack<Node*>().swap(free_slots_);
244
245 // Delete nodes
246 for (std::vector<Node>* lane : node_lanes_) lane->clear();
247 }
248
249
add_before(Node * add,Node * next_node)250 void NodeContainer::add_before(Node* add, Node* next_node){
251 add->set_next(next_node);
252 add->set_previous(next_node->previous());
253
254 if ( add->previous() != NULL ) add->previous()->set_next(add);
255 next_node->set_previous(add);
256 if ( add->is_last() ) this->set_last(add);
257 }
258
259
260
261 /*******************************************************
262 * Consistency checking
263 *******************************************************/
264
sorted() const265 bool NodeContainer::sorted() const {
266 Node* current = first();
267 if ( !current->is_first() ) {
268 dout << "NodeContainer: First Node is not first" << std::endl;
269 return 0;
270 }
271
272 while ( !current->is_last() ) {
273 current = current->next();
274 if ( current->height() < current->previous()->height() ) {
275 dout << "NodeContainer: Nodes not sorted" << std::endl;
276 return 0;
277 }
278 if ( current == current->previous() ) {
279 dout << "NodeContainer: Fatal loop detected" << std::endl;
280 return 0;
281 }
282 }
283
284 if ( !current->is_last() ) {
285 dout << "NodeContainer: Last Node not last" << std::endl;
286 return 0;
287 }
288
289 return 1;
290 }
291
292
swap(NodeContainer & first,NodeContainer & second)293 void swap(NodeContainer& first, NodeContainer& second) {
294 using std::swap;
295 swap(first.first_node_, second.first_node_);
296 swap(first.last_node_, second.last_node_);
297 swap(first.size_, second.size_);
298 swap(first.unsorted_node_, second.unsorted_node_);
299 swap(first.node_counter_, second.node_counter_);
300 swap(first.lane_counter_, second.lane_counter_);
301 swap(first.node_lanes_, second.node_lanes_);
302 swap(first.free_slots_, second.free_slots_);
303 }
304
305
operator <<(std::ostream & stream,const NodeContainer & nc)306 std::ostream& operator<< (std::ostream& stream, const NodeContainer& nc) {
307 for ( ConstNodeIterator it = nc.iterator(); it.good(); ++it ) {
308 stream << *it << "(" << (*it)->height() << ")";
309 if (*it != nc.last()) stream << " <--> ";
310 }
311 return stream;
312 }
313
314