1 /**************************************************************************\
2 * Copyright (c) Kongsberg Oil & Gas Technologies AS
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met:
8 *
9 * Redistributions of source code must retain the above copyright notice,
10 * this list of conditions and the following disclaimer.
11 *
12 * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * Neither the name of the copyright holder nor the names of its
17 * contributors may be used to endorse or promote products derived from
18 * this software without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 \**************************************************************************/
32
33 /*!
34 \class SoPathList SoPathList.h Inventor/lists/SoPathList.h
35 \brief The SoPathList class is a container for pointers to SoPath objects.
36
37 \ingroup general
38
39 As this class inherits SoBaseList, referencing and dereferencing
40 will default be done on the objects at append(), remove(), insert()
41 etc.
42 */
43
44 #include <Inventor/lists/SoPathList.h>
45 #include <Inventor/SoPath.h>
46 #include <Inventor/SoFullPath.h>
47 #include <Inventor/C/tidbits.h>
48 #include <cassert>
49
50
51 /*!
52 Default constructor.
53 */
SoPathList(void)54 SoPathList::SoPathList(void)
55 : SoBaseList()
56 {
57 }
58
59 /*!
60 Constructor with a hint about the number of elements the list will
61 hold.
62
63 \sa SoBaseList::SoBaseList(const int)
64 */
SoPathList(const int size)65 SoPathList::SoPathList(const int size)
66 : SoBaseList(size)
67 {
68 }
69
70 /*!
71 Copy constructor.
72
73 Does a shallow copy of the SoPath pointer values, but updates
74 reference count.
75
76 \sa SoBaseList::SoBaseList(const SoBaseList &)
77 */
SoPathList(const SoPathList & pl)78 SoPathList::SoPathList(const SoPathList & pl)
79 : SoBaseList(pl)
80 {
81 }
82
83 /*!
84 Destructor.
85
86 \sa SoBaseList::~SoBaseList()
87 */
~SoPathList()88 SoPathList::~SoPathList()
89 {
90 }
91
92 /*!
93 Append \a ptr to the list.
94
95 \sa SoBaseList::append()
96 */
97 void
append(SoPath * const path)98 SoPathList::append(SoPath * const path)
99 {
100 SoBaseList::append((SoBase *)path);
101 }
102
103 /*!
104 Return node pointer at index \a i.
105
106 \sa SoBaseList::operator[]()
107 */
108 SoPath *
operator [](const int i) const109 SoPathList::operator[](const int i) const
110 {
111 return (SoPath *)SoBaseList::operator[](i);
112 }
113
114 /*!
115 Shallow copy of contents of list \a pl to this list.
116
117 \sa SoBaseList::operator=()
118 */
119 SoPathList &
operator =(const SoPathList & pl)120 SoPathList::operator=(const SoPathList & pl)
121 {
122 SoBaseList::copy(pl);
123 return *this;
124 }
125
126 /*!
127 Find and return index of first item equal to \a path.
128 */
129 int
findPath(const SoPath & path) const130 SoPathList::findPath(const SoPath & path) const
131 {
132 int i, n = this->getLength();
133 for (i = 0; i < n; i++) if (*(*this)[i] == path) return i;
134 return -1;
135
136 }
137
138 // Return a negative number if the path pointed to by v0 is considered
139 // "less than" v1, a positive number if v0 is considered "larger than"
140 // v1 and zero if they are equal.
141 //
142 // "extern C" wrapper is needed with the OSF1/cxx compiler (probably a
143 // bug in the compiler, but it doesn't seem to hurt to do this
144 // anyway).
145 extern "C" {
146 static int
compare_paths(const void * v0,const void * v1)147 compare_paths(const void * v0, const void * v1)
148 {
149 SoFullPath * p0 = *((SoFullPath**)v0);
150 SoFullPath * p1 = *((SoFullPath**)v1);
151
152 const ptrdiff_t diff = (char *)p0->getHead() - (char *)p1->getHead();
153 if (diff != 0) { return (int)diff; }
154
155 int n = SbMin(p0->getLength(), p1->getLength());
156 int i;
157 for (i = 1; i < n; i++) {
158 const int diff = p0->getIndex(i) - p1->getIndex(i);
159 if (diff != 0) { return (int)diff; }
160 }
161 // shortest path first
162 return p0->getLength() - p1->getLength();
163 }
164 }
165
166 /*!
167 Sort paths in list according to how early they are run into when
168 traversing the scene graph.
169 */
170 void
sort(void)171 SoPathList::sort(void)
172 {
173 qsort((void **)this->getArrayPtr(), this->getLength(), sizeof(void *), compare_paths);
174 }
175
176 /*!
177 Removes identical paths and paths that go through the tail of
178 another path.
179
180 Note that this method assumes the list to be in a sorted order.
181
182 \sa sort()
183 */
184 void
uniquify(void)185 SoPathList::uniquify(void)
186 {
187 SoFullPath ** array = (SoFullPath**) this->getArrayPtr();
188
189 for (int i = this->getLength()-2; i >= 0; i--) {
190 SoFullPath * p = array[i];
191 int j = i+1;
192 // if fork is at tail of current path, remove next path. We might
193 // have more than one path that go through this path's tail, so do
194 // the test in a while loop
195 while ((j < this->getLength()) && (p->findFork(array[j]) == p->getLength()-1)) {
196 this->remove(j);
197 // get array pointer again even though it shouldn't change, but
198 // it might do in the future so...
199 array = (SoFullPath**) this->getArrayPtr();
200 }
201 }
202 }
203