calcpaths.cc 10.1 KB
Newer Older
1
// Copyright (C)  2002  Dominique Devriese <devriese@kde.org>
2
3
4
5
6
7
8
9
10
11
12
13
14

// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
Dirk Mueller's avatar
Dirk Mueller committed
15
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
Dirk Mueller's avatar
Dirk Mueller committed
16
// 02110-1301, USA.
17
18
19

#include "calcpaths.h"

20
#include "../objects/object_calcer.h"
21
#include "../objects/object_imp.h"
22

23
24
#include <algorithm>

25
26
27
28
29
30
31
// mp:
// The previous algorithm by Dominique had an exponential complexity
// for some constructions (e.g. a sequence of "n" triangles each inscribed
// into the previous).
// The new version is directly taken from a book of Alan Bertossi
// "Algoritmi e strutture dati"

32
33
34
35
36
37
38
39
// temporarily disabling the new algorithm due to the freeze:
// I previously misunderstood the semantics of this function
// and thought that the os vector had to be completed with all
// the subtree generated by it.  On the contrary, the os vector
// contains *all* the objects that we want, we only have to
// reorder them.  Now it *should* work, however we postpone 
// activating this to a more proper moment

40
// to deactivate the new algorithm change "define" into "undef"
41

42
#define NEWCALCPATH
43
#ifdef NEWCALCPATH
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
void localdfs( ObjectCalcer* obj,
               std::vector<ObjectCalcer*>& visited,
               std::vector<ObjectCalcer*>& all);

std::vector<ObjectCalcer*> calcPath( const std::vector<ObjectCalcer*>& os )
{
  // "all" is the Objects var we're building, in reverse ordering
  std::vector<ObjectCalcer*> visited;
  std::vector<ObjectCalcer*> all;

  for ( std::vector<ObjectCalcer*>::const_iterator i = os.begin(); i != os.end(); ++i )
  {
    if ( std::find( visited.begin(), visited.end(), *i ) == visited.end() )
    {
      localdfs( *i, visited, all );
    }
  }

62
63
64
65
66
67
68
69
70
  // now, we need to remove all objects that are not in os
  // (forgot to do this in previous fix :-( )
  std::vector<ObjectCalcer*> ret;
  for ( std::vector<ObjectCalcer*>::reverse_iterator i = all.rbegin(); i != all.rend(); ++i )
  {
    // we only add objects that appear in os
    if ( std::find( os.begin(), os.end(), *i ) != os.end() ) ret.push_back( *i );
  };
  return ret;
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
}

void localdfs( ObjectCalcer* obj,
               std::vector<ObjectCalcer*>& visited,
               std::vector<ObjectCalcer*>& all)
{
  visited.push_back( obj );
  const std::vector<ObjectCalcer*> o = obj->children();
  for ( std::vector<ObjectCalcer*>::const_iterator i = o.begin(); i != o.end(); ++i )
  {
    if ( std::find( visited.begin(), visited.end(), *i ) == visited.end() )
      localdfs( *i, visited, all );
  }
  all.push_back( obj );
}

// old calcPath commented out...

89
#else
90
// these first two functions were written before i read stuff about
91
// graph theory and algorithms, so I'm sure they're far from optimal.
92
// However, they seem to work fine, and i don't think there's a real
93
// need for optimization here..
94
std::vector<ObjectCalcer*> calcPath( const std::vector<ObjectCalcer*>& os )
95
96
97
98
99
100
101
102
103
104
{
  // this is a little experiment of mine, i don't know if it is the
  // fastest way to do it, but it seems logical to me...

  // the general idea here:
  // first we build a new Objects variable.  For every object in os,
  // we put all of its children at the end of it, and we do the same
  // for the ones we add..

  // "all" is the Objects var we're building...
105
  std::vector<ObjectCalcer*> all = os;
106
107
108
  // tmp is the var containing the objects we're iterating over.  The
  // first time around this is the os variable, the next time, this
  // contains the variables we added in the first round...
109
  std::vector<ObjectCalcer*> tmp = os;
110
111
112
  // tmp2 is a temporary var.  During a round, it receives all the
  // variables we add ( to "all" ) in that round, and at the end of
  // the round, it is assigned to tmp.
113
  std::vector<ObjectCalcer*> tmp2;
114
115
  while ( ! tmp.empty() )
  {
116
    for ( std::vector<ObjectCalcer*>::const_iterator i = tmp.begin(); i != tmp.end(); ++i )
117
    {
118
      const std::vector<ObjectCalcer*> o = (*i)->children();
119
120
121
122
123
124
125
126
127
128
      std::copy( o.begin(), o.end(), std::back_inserter( all ) );
      std::copy( o.begin(), o.end(), std::back_inserter( tmp2 ) );
    };
    tmp = tmp2;
    tmp2.clear();
  };

  // now we know that if all objects appear at least once after all of
  // their parents.  So, we take all, and of every object, we remove
  // every reference except the last one...
129
  std::vector<ObjectCalcer*> ret;
Dominique Devriese's avatar
Dominique Devriese committed
130
  ret.reserve( os.size() );
131
  for ( std::vector<ObjectCalcer*>::reverse_iterator i = all.rbegin(); i != all.rend(); ++i )
Dominique Devriese's avatar
Dominique Devriese committed
132
  {
133
134
135
136
    // we only add objects that appear in os and only if they are not
    // already in ret..
    if ( std::find( ret.begin(), ret.end(), *i ) == ret.end() &&
         std::find( os.begin(), os.end(), *i ) != os.end() ) ret.push_back( *i );
Dominique Devriese's avatar
Dominique Devriese committed
137
138
  };
  std::reverse( ret.begin(), ret.end() );
139
  return ret;
Dirk Mueller's avatar
Dirk Mueller committed
140
}
141
#endif
142

143
bool addBranch( const std::vector<ObjectCalcer*>& o, const ObjectCalcer* to, std::vector<ObjectCalcer*>& ret )
144
145
{
  bool rb = false;
146
  for ( std::vector<ObjectCalcer*>::const_iterator i = o.begin(); i != o.end(); ++i )
147
148
149
150
  {
    if ( *i == to )
      rb = true;
    else
Dominique Devriese's avatar
Dominique Devriese committed
151
      if ( addBranch( (*i)->children(), to, ret ) )
152
153
154
155
156
157
      {
        rb = true;
        ret.push_back( *i );
      };
  };
  return rb;
Dirk Mueller's avatar
Dirk Mueller committed
158
}
159

160
std::vector<ObjectCalcer*> calcPath( const std::vector<ObjectCalcer*>& from, const ObjectCalcer* to )
161
{
162
  std::vector<ObjectCalcer*> all;
163

164
  for ( std::vector<ObjectCalcer*>::const_iterator i = from.begin(); i != from.end(); ++i )
165
  {
Dominique Devriese's avatar
Dominique Devriese committed
166
    (void) addBranch( (*i)->children(), to, all );
167
168
  };

169
170
  std::vector<ObjectCalcer*> ret;
  for ( std::vector<ObjectCalcer*>::iterator i = all.begin(); i != all.end(); ++i )
Dominique Devriese's avatar
Dominique Devriese committed
171
  {
172
173
    if ( std::find( ret.begin(), ret.end(), *i ) == ret.end() )
      ret.push_back( *i );
Dominique Devriese's avatar
Dominique Devriese committed
174
  };
175
  return std::vector<ObjectCalcer*>( ret.rbegin(), ret.rend() );
Dirk Mueller's avatar
Dirk Mueller committed
176
}
177

178
static void addNonCache( ObjectCalcer* o, std::vector<ObjectCalcer*>& ret )
179
180
{
  if ( ! o->imp()->isCache() )
181
  {
182
183
    if ( std::find( ret.begin(), ret.end(), o ) == ret.end() )
      ret.push_back( o );
184
185
186
187
188
189
190
    else
    {
      std::vector<ObjectCalcer*> parents = o->parents();
      for ( uint i = 0; i < parents.size(); ++i )
        addNonCache( parents[i], ret );
    };
  }
Dirk Mueller's avatar
Dirk Mueller committed
191
}
192

193
static bool visit( const ObjectCalcer* o, const std::vector<ObjectCalcer*>& from, std::vector<ObjectCalcer*>& ret )
194
195
196
197
198
{
  // this function returns true if the visited object depends on one
  // of the objects in from.  If we encounter objects that are on the
  // side of the tree path ( they do not depend on from themselves,
  // but their direct children do ), then we add them to ret.
199
  if ( std::find( from.begin(), from.end(), o ) != from.end() ) return true;
200
201
202
203

  std::vector<bool> deps( o->parents().size(), false );
  bool somedepend = false;
  bool alldepend = true;
204
  std::vector<ObjectCalcer*> parents = o->parents();
205
  for ( uint i = 0; i < parents.size(); ++i )
206
  {
Albert Astals Cid's avatar
Albert Astals Cid committed
207
    bool v = ::visit( parents[i], from, ret );
208
209
210
211
212
213
214
215
    somedepend |= v;
    alldepend &= v;
    deps[i] = v;
  };
  if ( somedepend && ! alldepend )
  {
    for ( uint i = 0; i < deps.size(); ++i )
      if ( ! deps[i] )
216
        addNonCache( parents[i], ret );
217
218
219
  };

  return somedepend;
Dirk Mueller's avatar
Dirk Mueller committed
220
}
221

222
std::vector<ObjectCalcer*> sideOfTreePath( const std::vector<ObjectCalcer*>& from, const ObjectCalcer* to )
223
{
224
  std::vector<ObjectCalcer*> ret;
225
226
  visit( to, from, ret );
  return ret;
Dirk Mueller's avatar
Dirk Mueller committed
227
}
228

229
std::vector<ObjectCalcer*> getAllParents( const std::vector<ObjectCalcer*>& objs )
230
{
Dominique Devriese's avatar
Dominique Devriese committed
231
  using namespace std;
232
233
234
  std::set<ObjectCalcer*> ret( objs.begin(),objs.end() );
  std::set<ObjectCalcer*> cur = ret;
  while ( ! cur.empty() )
235
  {
236
237
238
239
240
241
242
243
244
    std::set<ObjectCalcer*> next;
    for ( std::set<ObjectCalcer*>::const_iterator i = cur.begin(); i != cur.end(); ++i )
    {
      std::vector<ObjectCalcer*> parents = (*i)->parents();
      next.insert( parents.begin(), parents.end() );
    };

    ret.insert( next.begin(), next.end() );
    cur = next;
245
  };
246
  return std::vector<ObjectCalcer*>( ret.begin(), ret.end() );
Dirk Mueller's avatar
Dirk Mueller committed
247
}
Dominique Devriese's avatar
Dominique Devriese committed
248

249
std::vector<ObjectCalcer*> getAllParents( ObjectCalcer* obj )
Dominique Devriese's avatar
Dominique Devriese committed
250
{
251
252
253
  std::vector<ObjectCalcer*> objs;
  objs.push_back( obj );
  return getAllParents( objs );
Dominique Devriese's avatar
Dominique Devriese committed
254
255
}

256
257
258
259
260
261
262
bool isChild( const ObjectCalcer* o, ObjectCalcer* op )
{
  std::vector<ObjectCalcer*> os;
  os.push_back( op );
  return isChild( o, os );
}

263
bool isChild( const ObjectCalcer* o, const std::vector<ObjectCalcer*>& os )
Dominique Devriese's avatar
Dominique Devriese committed
264
{
265
266
  std::vector<ObjectCalcer*> parents = o->parents();
  std::set<ObjectCalcer*> cur( parents.begin(), parents.end() );
Dominique Devriese's avatar
Dominique Devriese committed
267
268
  while ( ! cur.empty() )
  {
269
270
    std::set<ObjectCalcer*> next;
    for ( std::set<ObjectCalcer*>::const_iterator i = cur.begin(); i != cur.end(); ++i )
Dominique Devriese's avatar
Dominique Devriese committed
271
    {
272
273
274
      if ( std::find( os.begin(), os.end(), *i ) != os.end() ) return true;
      std::vector<ObjectCalcer*> parents = (*i)->parents();
      next.insert( parents.begin(), parents.end() );
Dominique Devriese's avatar
Dominique Devriese committed
275
276
277
278
279
    };
    cur = next;
  };
  return false;
}
280
281
282
283
284
285
286
287

std::set<ObjectCalcer*> getAllChildren( ObjectCalcer* obj )
{
  std::vector<ObjectCalcer*> objs;
  objs.push_back( obj );
  return getAllChildren( objs );
}

Laurent Montel's avatar
Laurent Montel committed
288
std::set<ObjectCalcer*> getAllChildren( const std::vector<ObjectCalcer*> &objs )
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
{
  std::set<ObjectCalcer*> ret;
  // objects to iterate over...
  std::set<ObjectCalcer*> cur( objs.begin(), objs.end() );
  while( !cur.empty() )
  {
    // contains the objects to iterate over the next time around...
    std::set<ObjectCalcer*> next;
    for( std::set<ObjectCalcer*>::iterator i = cur.begin();
         i != cur.end(); ++i )
    {
      ret.insert( *i );
      std::vector<ObjectCalcer*> children = (*i)->children();
      next.insert( children.begin(), children.end() );
    };
    cur = next;
  };
  return ret;
}

309
310
bool isPointOnCurve( const ObjectCalcer* point, const ObjectCalcer* curve )
{
311
  return point->isDefinedOnOrThrough( curve ) || curve->isDefinedOnOrThrough( point );
312
}