vtkIdList.cxx 4.97 KB
Newer Older
Will Schroeder's avatar
Will Schroeder committed
1
2
/*=========================================================================

Ken Martin's avatar
Ken Martin committed
3
  Program:   Visualization Toolkit
Ken Martin's avatar
Ken Martin committed
4
  Module:    vtkIdList.cxx
Will Schroeder's avatar
Will Schroeder committed
5

6
  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7
8
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
Ken Martin's avatar
Ken Martin committed
9

10
11
     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12
     PURPOSE.  See the above copyright notice for more information.
Will Schroeder's avatar
Will Schroeder committed
13
14

=========================================================================*/
Ken Martin's avatar
Ken Martin committed
15
#include "vtkIdList.h"
16
17
#include "vtkObjectFactory.h"

Brad King's avatar
Brad King committed
18
vtkStandardNewMacro(vtkIdList);
19

20
21
22
23
24
25
vtkIdList::vtkIdList()
{
  this->NumberOfIds = 0;
  this->Size = 0;
  this->Ids = NULL;
}
26

27
28
29
30
31
32
33
vtkIdList::~vtkIdList()
{
  if ( this->Ids != NULL )
    {
    delete [] this->Ids;
    }
}
34

35
36
37
38
39
40
41
42
43
44
void vtkIdList::Initialize()
{
  if ( this->Ids != NULL )
    {
    delete [] this->Ids;
    this->Ids = NULL;
    }
  this->NumberOfIds = 0;
  this->Size = 0;
}
Charles Law's avatar
Charles Law committed
45

46
int vtkIdList::Allocate(const vtkIdType sz, const int vtkNotUsed(strategy))
Charles Law's avatar
Charles Law committed
47
{
48
49
50
51
  if ( sz > this->Size)
    {
    this->Initialize();
    this->Size = ( sz > 0 ? sz : 1);
52
    if ( (this->Ids = new vtkIdType[this->Size]) == NULL )
53
54
55
56
57
58
      {
      return 0;
      }
    }
  this->NumberOfIds = 0;
  return 1;
Charles Law's avatar
Charles Law committed
59
60
}

61
void vtkIdList::SetNumberOfIds(const vtkIdType number)
Charles Law's avatar
Charles Law committed
62
{
63
64
  this->Allocate(number,0);
  this->NumberOfIds = number;
Charles Law's avatar
Charles Law committed
65
66
}

67
void vtkIdList::InsertId(const vtkIdType i, const vtkIdType vtkid)
68
{
69
70
71
72
  if ( i >= this->Size )
    {
    this->Resize(i+1);
    }
73
  this->Ids[i] = vtkid;
74
  if ( i >= this->NumberOfIds )
75
    {
76
    this->NumberOfIds = i + 1;
77
78
79
    }
}

80
vtkIdType vtkIdList::InsertUniqueId(const vtkIdType vtkid)
Will Schroeder's avatar
Will Schroeder committed
81
{
82
  for (vtkIdType i=0; i < this->NumberOfIds; i++)
83
    {
84
    if ( vtkid == this->Ids[i] )
85
86
87
88
89
      {
      return i;
      }
    }
  
90
  return this->InsertNextId(vtkid);
91
}
Will Schroeder's avatar
Will Schroeder committed
92

93
vtkIdType *vtkIdList::WritePointer(const vtkIdType i, const vtkIdType number)
94
{
95
  vtkIdType newSize=i+number;
96
  if ( newSize > this->Size )
Will Schroeder's avatar
Will Schroeder committed
97
    {
98
99
100
101
102
103
104
105
106
    this->Resize(newSize);
    }
  if ( newSize > this->NumberOfIds )
    {
    this->NumberOfIds = newSize;
    }
  return this->Ids + i;
}

107
void vtkIdList::DeleteId(vtkIdType vtkid)
108
{
109
  vtkIdType i=0;
110

111
  // while loop is necessary to delete all occurences of vtkid
112
113
114
  while ( i < this->NumberOfIds )
    {
    for ( ; i < this->NumberOfIds; i++)
Jim Miller's avatar
Style    
Jim Miller committed
115
      {
116
      if ( this->Ids[i] == vtkid )
117
        {
118
        break;
119
        }
Jim Miller's avatar
Style    
Jim Miller committed
120
      }
Will Schroeder's avatar
Will Schroeder committed
121

122
    // if found; replace current id with last
123
    if ( i < this->NumberOfIds )
124
      {
125
126
      this->SetId(i,this->Ids[this->NumberOfIds-1]);
      this->NumberOfIds--;
127
      }
Will Schroeder's avatar
Will Schroeder committed
128
129
130
    }
}

131
132
void vtkIdList::DeepCopy(vtkIdList *ids)
{
133
134
135
  this->Initialize();
  this->NumberOfIds = ids->NumberOfIds;
  this->Size = ids->Size;
136
137
  this->Ids = new vtkIdType [ids->Size];
  for (vtkIdType i=0; i < ids->NumberOfIds; i++)
138
    {
139
    this->Ids[i] = ids->Ids[i];
140
141
142
    }
}

143
vtkIdType *vtkIdList::Resize(const vtkIdType sz)
144
{
145
146
  vtkIdType *newIds;
  vtkIdType newSize;
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

  if ( sz > this->Size ) 
    {
    newSize = this->Size + sz;
    }
  else if (sz == this->Size)
    {
    return this->Ids;
    }
  else 
    {
    newSize = sz;
    }

  if (newSize <= 0)
    {
    this->Initialize();
    return 0;
    }

167
  if ( (newIds = new vtkIdType[newSize]) == NULL )
168
169
170
171
172
173
174
175
    { 
    vtkErrorMacro(<< "Cannot allocate memory\n");
    return 0;
    }

  if (this->Ids)
    {
    memcpy(newIds, this->Ids,
176
           static_cast<size_t>(sz < this->Size ? sz : this->Size) * sizeof(vtkIdType));
177
178
179
180
181
182
183
184
    delete [] this->Ids;
    }

  this->Size = newSize;
  this->Ids = newIds;
  return this->Ids;
}

185
#define VTK_TMP_ARRAY_SIZE 500
Will Schroeder's avatar
Will Schroeder committed
186
187
// Intersect this list with another vtkIdList. Updates current list according
// to result of intersection operation.
188
void vtkIdList::IntersectWith(vtkIdList* otherIds)
Will Schroeder's avatar
Will Schroeder committed
189
{
190
191
  // Fast method due to Dr. Andreas Mueller of ISE Integrated Systems 
  // Engineering (CH).
192
  vtkIdType thisNumIds = this->GetNumberOfIds();
193
194
195

  if (thisNumIds <= VTK_TMP_ARRAY_SIZE) 
    {//Use fast method if we can fit in temporary storage
196
    vtkIdType  thisIds[VTK_TMP_ARRAY_SIZE];
197
    vtkIdType i, vtkid;
198
    
Jim Miller's avatar
Style    
Jim Miller committed
199
200
201
202
    for (i=0; i < thisNumIds; i++)
      {
      thisIds[i] = this->GetId(i);
      }
203
204
    for (this->Reset(), i=0; i < thisNumIds; i++) 
      {
205
      vtkid = thisIds[i];
206
      if ( otherIds->IsId(vtkid) != (-1) )
207
        {
208
        this->InsertNextId(vtkid);
209
        }
210
211
212
213
      }
    } 
  else 
    {//use slower method for extreme cases
214
    vtkIdType *thisIds = new vtkIdType [thisNumIds];
215
    vtkIdType  i, vtkid;
216
    
Jim Miller's avatar
Style    
Jim Miller committed
217
218
219
220
    for (i=0; i < thisNumIds; i++)
      {
      *(thisIds + i) = this->GetId(i);
      }
221
    for (this->Reset(), i=0; i < thisNumIds; i++) 
Will Schroeder's avatar
Will Schroeder committed
222
      {
223
      vtkid = *(thisIds + i);
224
      if ( otherIds->IsId(vtkid) != (-1) )
225
        {
226
        this->InsertNextId(vtkid);
227
        }
Will Schroeder's avatar
Will Schroeder committed
228
      }
229
    delete [] thisIds;
Will Schroeder's avatar
Will Schroeder committed
230
231
    }
}
232
233
#undef VTK_TMP_ARRAY_SIZE

234
void vtkIdList::PrintSelf(ostream& os, vtkIndent indent)
Will Schroeder's avatar
Will Schroeder committed
235
{
Brad King's avatar
Brad King committed
236
  this->Superclass::PrintSelf(os,indent);
Will Schroeder's avatar
Will Schroeder committed
237

238
  os << indent << "Number of Ids: " << this->NumberOfIds << "\n";
Will Schroeder's avatar
Will Schroeder committed
239
}