Tulip  5.0.0
Large graphs analysis and drawing
GraphTableModel.cxx
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip 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.
16  * See the GNU General Public License for more details.
17  *
18  */
19 
20 
21 using namespace tlp;
22 
23 template<typename T>
24 void GraphTableModel::removeFromVector(const std::set<T>& objects,std::vector<T>& vect,TLP_HASH_MAP<T,int>& objToIndexes,bool deleteRows) {
25  //Sort from the greatest to the smallest to ensure index are not invalidate during the destruction process
26  std::set<int, std::greater<int> > indexes;
27 
28  for( typename std::set<T>::const_iterator it = objects.begin(); it != objects.end(); ++it) {
29  assert(objToIndexes.find(*it)!=objToIndexes.end());
30  indexes.insert(objToIndexes[*it]);
31  objToIndexes.erase(*it);
32  }
33 
34  while(!indexes.empty()) {
35  //Compute the greatest range of successive indexes.
36  std::set<int, std::greater<int> >::const_iterator from = indexes.begin();
37 
38  std::set<int, std::greater<int> >::const_iterator current = from;
39  std::set<int, std::greater<int> >::const_iterator to=from;
40  ++to;
41 
42  //If the indexes are successive delete them at the same time.
43  while(to != indexes.end() && *to == (*current)-1 ) {
44  current = to;
45  ++to;
46  }
47 
48  //Range to destruct
49  int fromIndex = *current;
50  int toIndex = *from;
51 
52  //Remove the range from the index list
53  indexes.erase(from,to);
54 
55  if(deleteRows) {
56  beginRemoveRows(QModelIndex(),fromIndex,toIndex);
57  }
58  else {
59  beginRemoveColumns(QModelIndex(),fromIndex,toIndex);
60  }
61 
62  //Erase data
63  vect.erase(vect.begin()+fromIndex,vect.begin()+toIndex+1);
64 
65  //Update objToIndex map
66  for(unsigned int i = fromIndex ; i < vect.size() ; ++i) {
67  objToIndexes[vect[i]] = static_cast<int>(i);
68  }
69 
70  if(deleteRows) {
71  endRemoveRows();
72  }
73  else {
74  endRemoveColumns();
75  }
76  }
77 }
78 
79 template<typename T, class Compare>
80 void GraphTableModel::addToVector(const std::set<T>& objects,std::vector<T>& vect,TLP_HASH_MAP<T,int>& objToIndex,bool addRows, Compare* comp) {
81  //Reserve size
82  if(vect.capacity() <= vect.size() + objects.size()) {
83  vect.reserve(vect.size() + objects.size());
84  }
85 
86  if(comp == NULL) {
87  //If there is no comparator append the elements to add at the end of the vector
88  if(addRows) {
89  beginInsertRows(QModelIndex(),vect.size(),vect.size()+objects.size()-1);
90  }
91  else {
92  beginInsertColumns(QModelIndex(),vect.size(),vect.size()+objects.size()-1);
93  }
94 
95  for(typename std::set<T>::const_iterator it = objects.begin(); it != objects.end() ; ++it) {
96  unsigned int i = vect.size();
97  objToIndex[*it]=i;
98  vect.push_back((*it));
99  }
100 
101  if(addRows) {
102  endInsertRows();
103  }
104  else {
105  endInsertColumns();
106  }
107  }
108  else {
109  //Order objects
110  std::vector<T> sortedObjects(objects.begin(),objects.end());
111  std::sort(sortedObjects.begin(),sortedObjects.end(),*comp);
112  unsigned int current = 0;
113  typename std::vector<T>::iterator it;
114 
115  for( it = vect.begin() , current = 0 ; it != vect.end() && !sortedObjects.empty() ; ++it, ++current) {
116  //First element greater than the element to insert
117  if(!(*comp)(*it,sortedObjects.front())) {
118  //Compute the elements to insert in the vector
119  typename std::vector<T>::iterator to = sortedObjects.begin()+1;
120  unsigned int insertedElementsCount = 1;
121 
122  //While there is more elements to insert at this position
123  while(to != sortedObjects.end() && !(*comp)(*it,*to)) {
124  ++to;
125  ++insertedElementsCount;
126  }
127 
128  //Notify Qt model
129  if(addRows) {
130  beginInsertRows(QModelIndex(),current,current+insertedElementsCount-1);
131  }
132  else {
133  beginInsertColumns(QModelIndex(),current,current+insertedElementsCount-1);
134  }
135 
136  //Update data
137  vect.insert(it,sortedObjects.begin(),to);
138 
139  //Update data index
140  for(unsigned int i = current ; i < vect.size() ; ++i) {
141  objToIndex[vect[i]]=i;
142  }
143 
144  if(addRows) {
145  endInsertRows();
146  }
147  else {
148  endInsertColumns();
149  }
150 
151  //Erase added elements.
152  sortedObjects.erase(sortedObjects.begin(),to);
153  it = vect.begin()+current;
154  }
155  }
156 
157  //If there is some elements to add insert them at the end of the data.
158  if(!sortedObjects.empty()) {
159  if(addRows) {
160  beginInsertRows(QModelIndex(),vect.size(),vect.size()+sortedObjects.size()-1);
161  }
162  else {
163  beginInsertColumns(QModelIndex(),vect.size(),vect.size()+sortedObjects.size()-1);
164  }
165 
166  size_t from = vect.size();
167  //Update data
168  vect.insert(vect.end(),sortedObjects.begin(),sortedObjects.end());
169 
170  //Update data index
171  for(unsigned int i = from ; i < vect.size() ; ++i) {
172  objToIndex[vect[i]]=i;
173  }
174 
175  if(addRows) {
176  endInsertRows();
177  }
178  else {
179  endInsertColumns();
180  }
181  }
182  }
183 }
184 
185 template<typename T>
186 void GraphTableModel::updateIndexMap(const std::vector<T>& table,TLP_HASH_MAP<T,int>& indexMap) {
187  indexMap.clear();
188 
189  for(size_t i = 0 ; i < table.size(); ++i) {
190  indexMap[table[i]]=i;
191  }
192 }
193 
194 template<typename T>
195 std::pair<unsigned int,unsigned int> GraphTableModel::computeArea(const std::set<T>& elementsToFind,const std::vector<T>& elements,const TLP_HASH_MAP<T,int>& objToIndex)const {
196  //Init from and to values
197  int first=elements.size()-1,last=0;
198 
199  for(typename std::set<T>::const_iterator it = elementsToFind.begin(); it != elementsToFind.end() ; ++it) {
200  assert(objToIndex.find(*it) != objToIndex.end());
201  int index = (objToIndex.find(*it))->second;
202  first = std::min(first,index);
203  last = std::max(last,index);
204  }
205 
206  first = std::max(first,0);
207  last = std::min(last,static_cast<int>(elements.size()-1));
208  return std::make_pair(first,last);
209 }