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