Xalan-C++ API Reference 1.12.0
XalanDeque.hpp
Go to the documentation of this file.
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19#if !defined(XALANDEQUE_HEADER_GUARD_1357924680)
20#define XALANDEQUE_HEADER_GUARD_1357924680
21
22
23
24// Base include file. Must be first.
26
27
28
31
32
33
34namespace XALAN_CPP_NAMESPACE {
35
36
37
38template <class Value>
40{
42 typedef Value& reference;
43 typedef Value* pointer;
44 typedef const Value& const_reference;
45};
46
47template <class Value>
49{
51 typedef const Value& reference;
52 typedef const Value* pointer;
53 typedef const Value& const_reference;
54};
55
56template <class Traits, class XalanDeque>
58{
59public:
60
61 typedef size_t size_type;
62 typedef typename Traits::value_type value_type;
63 typedef typename Traits::reference reference;
64 typedef typename Traits::pointer pointer;
65 typedef typename Traits::const_reference const_reference;
67
68 typedef std::random_access_iterator_tag iterator_category;
69
70 // The non-const iterator type. In the case of the non-const instatiation, this
71 // is the same type.
73
74 // The const version needs access to our private data members for copy construction and
75 // assignment. For the const instantiation, this is a superfluous friend declaration,
76 // since it's the same type as the class itself.
78
80 XalanDeque* deque,
81 size_type pos) :
82 m_deque(deque),
83 m_pos(pos)
84 {
85 }
86
87 // This is standard copy-construction for the non-const iterator type. For the
88 // const iterator type, this is copy construction from the non-const type, and the
89 // compiler will generate the standard copy constructor.
90 XalanDequeIterator(const Iterator& iterator) :
91 m_deque(iterator.m_deque),
92 m_pos(iterator.m_pos)
93 {
94 }
95
96 // This is the standard assignment operator for the non-const iterator type.
97 // For the const iterator type, this is the assignment operator from the
98 // non-const type, and the compiler will generate the standard assignment
99 // operator.
101 operator=(const Iterator& iterator)
102 {
103 m_deque = iterator.m_deque;
104 m_pos = iterator.m_pos;
105
106 return *this;
107 }
108
111 {
112 ++m_pos;
113
114 return *this;
115 }
116
119 {
120 XalanDequeIterator temp = *this;
121 ++m_pos;
122
123 return temp;
124 }
125
128 {
129 --m_pos;
130
131 return *this;
132 }
133
134 pointer
136 {
137 return &(*m_deque[m_pos]);
138 }
139
140 reference
142 {
143 return (*m_deque)[m_pos];
144 }
145
146 const_reference
147 operator*() const
148 {
149 return (*m_deque)[m_pos];
150 }
151
154 {
155 return XalanDequeIterator(m_deque, m_pos + difference);
156 }
157
160 {
161 return XalanDequeIterator(m_deque, m_pos - difference);
162 }
163
164 difference_type
166 {
167 return m_pos - theRHS.m_pos;
168 }
169
170 bool
172 {
173 return theRHS.m_deque == m_deque &&
174 theRHS.m_pos == m_pos;
175 }
176
177 bool
179 {
180 return !(theRHS == *this);
181 }
182
183 bool
185 {
186 return m_pos < theRHS.m_pos;
187 }
188
189private:
190
191 XalanDeque* m_deque;
192
193 size_type m_pos;
194};
195
196/**
197 * Xalan implementation of deque
198 */
199template <class Type, class ConstructionTraits = MemoryManagedConstructionTraits<Type> >
201{
202public:
203
204 typedef size_t size_type;
205
207 typedef Type& reference;
208 typedef const Type& const_reference;
209
212
214
217
218 typedef std::reverse_iterator<iterator> reverse_iterator_;
219 typedef std::reverse_iterator<const_iterator> const_reverse_iterator_;
220
223
224 typedef typename ConstructionTraits::Constructor Constructor;
225 typedef typename Constructor::ConstructableType ConstructableType;
226
228 MemoryManager& memoryManager,
230 size_type blockSize = 10) :
231 m_memoryManager(&memoryManager),
232 m_blockSize(blockSize),
233 m_blockIndex(memoryManager,
234 initialSize / blockSize + (initialSize % blockSize == 0 ? 0 : 1)),
235 m_freeBlockVector(memoryManager)
236 {
237 const ConstructableType defaultValue(*m_memoryManager);
238
239 using std::fill_n;
240 using std::back_inserter;
241
242 fill_n(
243 back_inserter(*this),
245 defaultValue.value);
246 }
247
249 const XalanDeque& theRHS,
250 MemoryManager& theMemoryManager) :
251 m_memoryManager(&theMemoryManager),
252 m_blockSize(theRHS.m_blockSize),
253 m_blockIndex(*theRHS.m_memoryManager,
254 theRHS.size() / theRHS.m_blockSize + (theRHS.size() % theRHS.m_blockSize == 0 ? 0 : 1)),
255 m_freeBlockVector(theMemoryManager)
256 {
257 using std::copy;
258 using std::back_inserter;
259
260 copy(
261 theRHS.begin(),
262 theRHS.end(),
263 back_inserter(*this));
264 }
265
266 static XalanDeque*
268 MemoryManager& theManager,
270 size_type blockSize = 10)
271 {
273
274 ThisType* const theResult =
276
278
279 return theResult;
280 }
281
283 {
284 destroyBlockList(m_freeBlockVector);
285
286 destroyBlockList(m_blockIndex);
287 }
288
289 iterator
291 {
292 return iterator(this, 0);
293 }
294
295 const_iterator
296 begin() const
297 {
298 return const_iterator(const_cast<XalanDeque*>(this), 0);
299 }
300
301 iterator
303 {
304 return iterator(this, size());
305 }
306
307 const_iterator
308 end() const
309 {
310 return const_iterator(const_cast<XalanDeque*>(this), size());
311 }
312
313 const_reverse_iterator
314 rbegin() const
315 {
316 return const_reverse_iterator(end());
317 }
318
319 const_reverse_iterator
320 rend() const
321 {
322 return const_reverse_iterator(begin());
323 }
324
325 bool
326 empty() const
327 {
328 return m_blockIndex.empty();
329 }
330
331 size_type
332 size() const
333 {
334 if (m_blockIndex.empty())
335 {
336 return 0;
337 }
338 else
339 {
340 return (m_blockIndex.size() - 1) * m_blockSize
341 + m_blockIndex.back()->size();
342 }
343 }
344
345 value_type&
347 {
348 return m_blockIndex.back()->back();
349 }
350
351 value_type&
353 {
354 BlockType& block = *m_blockIndex[index / m_blockSize];
355
356 return block[index % m_blockSize];
357 }
358
359 const value_type&
361 {
362 BlockType& block = *m_blockIndex[index / m_blockSize];
363
364 return block[index % m_blockSize];
365 }
366
367 void
369 {
370 typename BlockIndexType::iterator iter = m_blockIndex.begin();
371
372 m_freeBlockVector.reserve(m_freeBlockVector.size() + m_blockIndex.size());
373
374 while (iter != m_blockIndex.end())
375 {
376 (*iter)->clear();
377 m_freeBlockVector.push_back(*iter);
378 ++iter;
379 }
380
381 m_blockIndex.clear();
382 }
383
384 void
385 push_back(const value_type& value)
386 {
387 if (m_blockIndex.empty() ||
388 m_blockIndex.back()->size() >= m_blockSize)
389 {
390 pushNewIndexBlock();
391 }
392
393 m_blockIndex.back()->push_back(value);
394 }
395
396 void
398 {
399 assert(!empty());
400
401 BlockType& lastBlock = *m_blockIndex.back();
402 lastBlock.pop_back();
403
404 if (lastBlock.empty())
405 {
406 m_freeBlockVector.push_back(&lastBlock);
407 m_blockIndex.pop_back();
408 }
409 }
410
411 void
413 {
414 const ConstructableType defaultValue(*m_memoryManager);
415
416 if (newSize > size())
417 {
418 for (size_type i = 0; i < newSize - size(); ++i)
419 {
420 push_back(defaultValue.value);
421 }
422 }
423 else
424 {
425 for (size_type i = 0; i < size() - newSize; ++i)
426 {
427 pop_back();
428 }
429 }
430 }
431
432 void
434 {
435 MemoryManager* const temp = m_memoryManager;
436 m_memoryManager = theRHS.m_memoryManager;
437 theRHS.m_memoryManager = temp;
438
439 theRHS.m_blockIndex.swap(m_blockIndex);
440 theRHS.m_freeBlockVector.swap(m_freeBlockVector);
441 }
442
445 {
446 if (this != &theRHS)
447 {
448 using std::copy;
449 using std::back_inserter;
450
451 clear();
452
453 copy(
454 theRHS.begin(),
455 theRHS.end(),
456 back_inserter(*this));
457 }
458
459 return *this;
460 }
461
462 MemoryManager&
464 {
465 assert (m_memoryManager != 0);
466
467 return *m_memoryManager;
468 }
469
470private:
471
472 void
473 pushNewIndexBlock()
474 {
475 // Allocate space first, so we don't have to worry
476 // about an out-of-memory error once we've constructed
477 // the new block.
478 m_blockIndex.push_back(0);
479
480 if (m_freeBlockVector.empty())
481 {
483 *m_memoryManager,
484 m_blockIndex.back(),
485 *m_memoryManager,
486 m_blockSize);
487 }
488 else
489 {
490 m_blockIndex.back() = m_freeBlockVector.back();
491
492 // Now that ownership has been transfered, pop
493 // it off the free list.
494 m_freeBlockVector.pop_back();
495 }
496
497 assert(m_blockIndex.back() != 0);
498 }
499
500 void
501 destroyBlockList(BlockIndexType& theBlockIndex)
502 {
503 typename BlockIndexType::iterator iter =
504 theBlockIndex.begin();
505
506 while (iter != theBlockIndex.end())
507 {
508 // Normally, we should be able to just call
509 // the version of XalanDestroy() that accepts
510 // a pointer, but Visual Studio 6 has issues
511 // with partial ordering, so we're stuck with
512 // this for now.
513 if (*iter != 0)
514 {
515 XalanDestroy(*m_memoryManager, **iter);
516 }
517
518 ++iter;
519 }
520 }
521
522 MemoryManager* m_memoryManager;
523
524 const size_type m_blockSize;
525
526 BlockIndexType m_blockIndex;
527 BlockIndexType m_freeBlockVector;
528
529
530 // These are not implemented
531 XalanDeque();
532
533 XalanDeque(const XalanDeque&);
534};
535
536
537
538}
539
540
541
542#endif // XALANDEQUE_HEADER_GUARD_1357924680
543
#define XALAN_CPP_NAMESPACE
Xalan-C++ namespace, including major and minor version.
XalanDequeIterator & operator--()
bool operator!=(const XalanDequeIterator &theRHS) const
bool operator==(const XalanDequeIterator &theRHS) const
XalanDequeIterator(const Iterator &iterator)
XalanDequeIterator(XalanDeque *deque, size_type pos)
XalanDequeIterator operator+(difference_type difference) const
XalanDequeIterator & operator++()
std::random_access_iterator_tag iterator_category
difference_type operator-(const XalanDequeIterator &theRHS) const
Traits::value_type value_type
XalanDequeIterator operator-(difference_type difference) const
XalanDequeIterator & operator=(const Iterator &iterator)
XalanDequeIterator operator++(int)
Traits::const_reference const_reference
Traits::reference reference
XalanDequeIterator< XalanDequeIteratorTraits< value_type >, XalanDeque > Iterator
const_reference operator*() const
Xalan implementation of deque.
XalanDeque & operator=(const XalanDeque &theRHS)
value_type & operator[](size_type index)
static XalanDeque * create(MemoryManager &theManager, size_type initialSize=0, size_type blockSize=10)
XalanVector< BlockType * > BlockIndexType
void push_back(const value_type &value)
Constructor::ConstructableType ConstructableType
XalanDeque(MemoryManager &memoryManager, size_type initialSize=0, size_type blockSize=10)
size_type size() const
XalanDequeIterator< XalanDequeIteratorTraits< value_type >, ThisType > iterator
const_iterator begin() const
const_reverse_iterator_ const_reverse_iterator
void resize(size_type newSize)
reverse_iterator_ reverse_iterator
XalanDequeIterator< XalanDequeConstIteratorTraits< value_type >, ThisType > const_iterator
const_reverse_iterator rbegin() const
const value_type & operator[](size_type index) const
ConstructionTraits::Constructor Constructor
std::reverse_iterator< const_iterator > const_reverse_iterator_
XalanDeque< Type, ConstructionTraits > ThisType
const Type & const_reference
XalanDeque(const XalanDeque &theRHS, MemoryManager &theMemoryManager)
const_iterator end() const
void swap(XalanDeque &theRHS)
bool empty() const
value_type & back()
XalanVector< Type, ConstructionTraits > BlockType
MemoryManager & getMemoryManager()
std::reverse_iterator< iterator > reverse_iterator_
const_reverse_iterator rend() const
void clear(XalanDOMString &theString)
Remove all elements from target string.
size_t size_type
Definition XalanMap.hpp:46
Type * XalanConstruct(MemoryManager &theMemoryManager, Type *&theInstance)
void XalanDestroy(Type &theArg)