vtkEdgeTable.cxx 10.3 KB
Newer Older
1 2 3
/*=========================================================================

  Program:   Visualization Toolkit
Ken Martin's avatar
Ken Martin committed
4
  Module:    vtkEdgeTable.cxx
5 6 7 8 9
  Language:  C++
  Date:      $Date$
  Version:   $Revision$


Will Schroeder's avatar
Will Schroeder committed
10
Copyright (c) 1993-2001 Ken Martin, Will Schroeder, Bill Lorensen 
Will Schroeder's avatar
Will Schroeder committed
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

 * Redistributions of source code must retain the above copyright notice,
   this list of conditions and the following disclaimer.

 * Redistributions in binary form must reproduce the above copyright notice,
   this list of conditions and the following disclaimer in the documentation
   and/or other materials provided with the distribution.

 * Neither name of Ken Martin, Will Schroeder, or Bill Lorensen nor the names
   of any contributors may be used to endorse or promote products derived
   from this software without specific prior written permission.

 * Modified source versions must be plainly marked as such, and must not be
   misrepresented as being the original software.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
Will Schroeder's avatar
Will Schroeder committed
33
ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR
Will Schroeder's avatar
Will Schroeder committed
34 35 36 37 38 39
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
40 41

=========================================================================*/
Ken Martin's avatar
Ken Martin committed
42
#include "vtkEdgeTable.h"
Will Schroeder's avatar
Will Schroeder committed
43
#include "vtkPoints.h"
44
#include "vtkIdList.h"
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
#include "vtkObjectFactory.h"

//------------------------------------------------------------------------------
vtkEdgeTable* vtkEdgeTable::New()
{
  // First try to create the object from the vtkObjectFactory
  vtkObject* ret = vtkObjectFactory::CreateInstance("vtkEdgeTable");
  if(ret)
    {
    return (vtkEdgeTable*)ret;
    }
  // If the factory was unable to create the object, then create it here.
  return new vtkEdgeTable;
}



62 63

// Instantiate object based on maximum point id.
Will Schroeder's avatar
Will Schroeder committed
64
vtkEdgeTable::vtkEdgeTable()
65
{
Will Schroeder's avatar
Will Schroeder committed
66 67 68 69
  this->Table = NULL;
  this->Attributes = NULL;
  this->Points = NULL;

70
  this->TableMaxId = -1;
Will Schroeder's avatar
Will Schroeder committed
71
  this->TableSize = 0;
72

Will Schroeder's avatar
Will Schroeder committed
73 74 75 76 77 78 79 80
  this->Position[0] = 0;
  this->Position[1] = -1;
  this->NumberOfEdges = 0;
}

// Free memory and return to instantiated state.
void vtkEdgeTable::Initialize()
{
81 82
  int i;
  
Will Schroeder's avatar
Will Schroeder committed
83 84
  if ( this->Table )
    {
85
    for (i=0; i < this->TableSize; i++)
Will Schroeder's avatar
Will Schroeder committed
86 87 88 89 90 91 92 93
      {
      if ( this->Table[i] )
        {
        this->Table[i]->Delete();
        }
      }
    delete [] this->Table;
    this->Table = NULL;
94
    this->TableMaxId = -1;
Will Schroeder's avatar
Will Schroeder committed
95 96 97

    if ( this->StoreAttributes )
      {
98
      for (i=0; i < this->TableSize; i++)
Will Schroeder's avatar
Will Schroeder committed
99 100 101 102 103 104 105 106 107 108 109
        {
        if ( this->Attributes[i] )
          {
          this->Attributes[i]->Delete();
          }
        }
      delete [] this->Attributes;
      this->Attributes = NULL;
      }
    }//if table defined

Bill Lorensen's avatar
Bill Lorensen committed
110
    if ( this->Points )
Will Schroeder's avatar
Will Schroeder committed
111 112 113 114
    {
    this->Points->Delete();
    this->Points = NULL;
    }
115
    
Bill Lorensen's avatar
Bill Lorensen committed
116
  this->TableSize = 0;
117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146
  this->NumberOfEdges = 0;
  this->StoreAttributes = 0;
}

// Free memory and return to instantiated state.
void vtkEdgeTable::Reset()
{
  int i;

  if ( this->Table )
    {
    for (i=0; i < this->TableSize; i++)
      {
      if ( this->Table[i] )
        {
        this->Table[i]->Reset();
        }
      }

    if ( this->StoreAttributes )
      {
      for (i=0; i < this->TableSize; i++)
        {
        if ( this->Attributes[i] )
          {
          this->Attributes[i]->Reset();
          }
        }
      }
    }//if table defined
Will Schroeder's avatar
Will Schroeder committed
147

148 149 150 151 152 153 154
  this->TableMaxId = -1;

  if ( this->Points )
    {
    this->Points->Reset();
    }
    
Will Schroeder's avatar
Will Schroeder committed
155 156 157 158 159 160 161 162 163 164 165
  this->NumberOfEdges = 0;
  this->StoreAttributes = 0;
}

vtkEdgeTable::~vtkEdgeTable()
{
  this->Initialize();
}

int vtkEdgeTable::InitEdgeInsertion(int numPoints, int storeAttributes)
{
166 167
  int i;
  
Jim Miller's avatar
Style  
Jim Miller committed
168 169 170 171
  if ( numPoints < 1 )
    {
    numPoints = 1;
    }
172

173 174
  // Discard old memory if not enough has benn previously allocated
  if ( numPoints > this->TableSize )
Jim Miller's avatar
Style  
Jim Miller committed
175
    {
176 177
    this->Initialize();
    this->Table = new vtkIdList *[numPoints];
178
    for (i=0; i < numPoints; i++)
Will Schroeder's avatar
Will Schroeder committed
179
      {
180
      this->Table[i] = NULL;
Will Schroeder's avatar
Will Schroeder committed
181 182
      }

183 184 185 186
    this->StoreAttributes = storeAttributes;
    if ( this->StoreAttributes )
      {
      this->Attributes = new vtkIdList *[numPoints];
187
      for (i=0; i < numPoints; i++)
188 189 190 191 192 193 194 195 196 197 198 199 200 201 202
        {
        this->Attributes[i] = NULL;
        }
      }
    this->TableMaxId = -1;
    this->TableSize = numPoints;
    }
  
  // Otherwise, reuse the old memory
  else
    {
    this->Reset();
    this->StoreAttributes = storeAttributes;
    this->TableMaxId = -1;
    }
Will Schroeder's avatar
Will Schroeder committed
203 204 205

  this->Position[0] = 0;
  this->Position[1] = -1;
Will Schroeder's avatar
Will Schroeder committed
206 207 208 209

  this->NumberOfEdges = 0;

  return 1;
210 211
}

Will Schroeder's avatar
Will Schroeder committed
212 213
// Return non-negative if edge (p1,p2) is an edge; otherwise -1.
int vtkEdgeTable::IsEdge(int p1, int p2)
214
{
Will Schroeder's avatar
Will Schroeder committed
215 216 217
  int index, search;

  if ( p1 < p2 )
218
    {
Will Schroeder's avatar
Will Schroeder committed
219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235
    index = p1;
    search = p2;
    }
  else
    {
    index = p2;
    search = p1;
    }

  if ( this->Table[index] == NULL ) 
    {
    return (-1);
    }
  else
    {
    int loc;
    if ( (loc=this->Table[index]->IsId(search)) == (-1) )
236
      {
Will Schroeder's avatar
Will Schroeder committed
237 238 239 240 241
      return (-1);
      }
    else
      {
      if ( this->StoreAttributes )
242
        {
Will Schroeder's avatar
Will Schroeder committed
243 244 245 246 247
        return this->Attributes[index]->GetId(loc);
        }
      else
        {
        return 1;
248 249 250 251 252
        }
      }
    }
}

Will Schroeder's avatar
Will Schroeder committed
253 254 255
// Insert the edge (p1,p2) into the table. It is the user's responsibility to
// check if the edge has already been inserted.
int vtkEdgeTable::InsertEdge(int p1, int p2)
256 257 258 259 260 261 262 263 264 265 266 267 268 269
{
  int index, search;

  if ( p1 < p2 )
    {
    index = p1;
    search = p2;
    }
  else
    {
    index = p2;
    search = p1;
    }

Will Schroeder's avatar
Will Schroeder committed
270 271 272 273
  if ( index >= this->TableSize )
    {
    this->Resize(index+1);
    }
274 275 276 277 278
  
  if ( index > this->TableMaxId )
    {
    this->TableMaxId = index;
    }
Will Schroeder's avatar
Will Schroeder committed
279

280 281
  if ( this->Table[index] == NULL ) 
    {
Will Schroeder's avatar
Will Schroeder committed
282 283 284 285
    this->Table[index] = vtkIdList::New();
    this->Table[index]->Allocate(6,12);
    if ( this->StoreAttributes )
      {
Bill Lorensen's avatar
Bill Lorensen committed
286 287 288 289
      if ( this->Attributes[index] )
        {
	this->Attributes[index]->Delete();
        }
Will Schroeder's avatar
Will Schroeder committed
290 291 292
      this->Attributes[index] = vtkIdList::New();
      this->Attributes[index]->Allocate(6,12);
      }
293
    }
Will Schroeder's avatar
Will Schroeder committed
294 295 296

  this->Table[index]->InsertNextId(search);
  if ( this->StoreAttributes )
297
    {
Will Schroeder's avatar
Will Schroeder committed
298
    this->Attributes[index]->InsertNextId(this->NumberOfEdges);
299
    }
Will Schroeder's avatar
Will Schroeder committed
300 301 302
  this->NumberOfEdges++;

  return (this->NumberOfEdges - 1);
303 304
}

Will Schroeder's avatar
Will Schroeder committed
305
void vtkEdgeTable::InsertEdge(int p1, int p2, int attributeId)
306 307 308 309 310 311 312 313 314 315 316 317 318 319
{
  int index, search;

  if ( p1 < p2 )
    {
    index = p1;
    search = p2;
    }
  else
    {
    index = p2;
    search = p1;
    }

Will Schroeder's avatar
Will Schroeder committed
320 321 322 323 324
  if ( index >= this->TableSize )
    {
    this->Resize(index+1);
    }

325 326 327 328 329
  if ( index > this->TableMaxId )
    {
    this->TableMaxId = index;
    }

330 331
  if ( this->Table[index] == NULL ) 
    {
Will Schroeder's avatar
Will Schroeder committed
332 333
    this->Table[index] = vtkIdList::New();
    this->Table[index]->Allocate(6,12);
Will Schroeder's avatar
Will Schroeder committed
334 335 336 337 338
    if ( this->StoreAttributes )
      {
      this->Attributes[index] = vtkIdList::New();
      this->Attributes[index]->Allocate(6,12);
      }
339 340
    }

Will Schroeder's avatar
Will Schroeder committed
341
  this->NumberOfEdges++;
342
  this->Table[index]->InsertNextId(search);
Will Schroeder's avatar
Will Schroeder committed
343 344 345 346
  if ( this->StoreAttributes )
    {
    this->Attributes[index]->InsertNextId(attributeId);
    }
347
}
Will Schroeder's avatar
Will Schroeder committed
348

Will Schroeder's avatar
Will Schroeder committed
349

Will Schroeder's avatar
Will Schroeder committed
350 351 352 353 354 355 356 357
// Intialize traversal of edges in table.
void vtkEdgeTable::InitTraversal()
{
  this->Position[0] = 0;
  this->Position[1] = -1;
}

// Traverse list of edges in table. Return the edge as (p1,p2), where p1 and p2
Will Schroeder's avatar
Will Schroeder committed
358 359 360
// are point id's. Method return value is non-negative if list is exhausted; 
// >= 0 otherwise. The value of p1 is guaranteed to be <= p2. The return value
// is an id that can be used for accessing attributes.
Will Schroeder's avatar
Will Schroeder committed
361 362
int vtkEdgeTable::GetNextEdge(int &p1, int &p2)
{
363
  for ( ; this->Position[0] <= this->TableMaxId; 
Will Schroeder's avatar
Will Schroeder committed
364 365 366 367 368 369
  this->Position[0]++, this->Position[1]=(-1) )
    {
    if ( this->Table[this->Position[0]] != NULL && 
    ++this->Position[1] < this->Table[this->Position[0]]->GetNumberOfIds() )
      {
      p1 = this->Position[0];
Will Schroeder's avatar
Will Schroeder committed
370
      p2 = this->Table[this->Position[0]]->GetId(this->Position[1]);
Will Schroeder's avatar
Will Schroeder committed
371
      return this->Attributes[this->Position[0]]->GetId(this->Position[1]);
Will Schroeder's avatar
Will Schroeder committed
372 373 374
      }
    }

Will Schroeder's avatar
Will Schroeder committed
375
  return (-1);
Will Schroeder's avatar
Will Schroeder committed
376
}
Will Schroeder's avatar
Will Schroeder committed
377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442

vtkIdList **vtkEdgeTable::Resize(int sz)
{
  vtkIdList **newTableArray;
  vtkIdList **newAttributeArray;
  int newSize, i;
  int extend=this->TableSize/2 + 1;

  if (sz >= this->TableSize)
    {
    newSize = this->TableSize + 
              extend*(((sz-this->TableSize)/extend)+1);
    }
  else
    {
    newSize = sz;
    }

  sz = (sz < this->TableSize ? sz : this->TableSize);
  newTableArray = new vtkIdList *[newSize];
  memcpy(newTableArray, this->Table, sz * sizeof(vtkIdList *));
  for (i=sz; i < newSize; i++)
    {
    newTableArray[i] = NULL;
    }
  this->TableSize = newSize;
  delete [] this->Table;
  this->Table = newTableArray;

  if ( this->StoreAttributes )
    {
    newAttributeArray = new vtkIdList *[newSize];
    memcpy(newAttributeArray, this->Attributes, sz * sizeof(vtkIdList *));
    for (i=sz; i < newSize; i++)
      {
      newAttributeArray[i] = NULL;
      }
    if ( this->Attributes )
      {
      delete [] this->Attributes;
      }
    this->Attributes = newAttributeArray;
    }

  return this->Table;
}

int vtkEdgeTable::InitPointInsertion(vtkPoints *newPts, int estSize)
{
  // Initialize
  if ( this->Table )
    {
    this->Initialize();
    }
  if ( newPts == NULL )
    {
    vtkErrorMacro(<<"Must define points for point insertion");
    return 0;
    }
  if (this->Points != NULL)
    {
    this->Points->Delete();
    }
  // Set up the edge insertion
  this->InitEdgeInsertion(estSize,1);

443 444 445
  this->Points = newPts;
  this->Points->Register(this);

Will Schroeder's avatar
Will Schroeder committed
446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465
  return 1;
}

int vtkEdgeTable::InsertUniquePoint(int p1, int p2, float x[3], int &ptId)
{
  int loc = this->IsEdge(p1,p2);

  if ( loc != -1 )
    {
    ptId = loc;
    return 0;
    }
  else
    {
    ptId = this->InsertEdge(p1,p2);
    this->Points->InsertPoint(ptId,x);
    return 1;
    }
}

466
void vtkEdgeTable::PrintSelf(ostream& os, vtkIndent indent)
Ken Martin's avatar
Ken Martin committed
467 468 469 470 471
{
  vtkObject::PrintSelf(os,indent);

  os << indent << "NumberOfEdges: " << this->GetNumberOfEdges() << "\n";
}