UList.H 19.3 KB
Newer Older
1
2
3
4
/*---------------------------------------------------------------------------*\
  =========                 |
  \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   \\    /   O peration     |
5
    \\  /    A nd           | Copyright (C) 2011-2016 OpenFOAM Foundation
6
     \\/     M anipulation  | Copyright (C) 2017 OpenCFD Ltd.
7
8
9
10
-------------------------------------------------------------------------------
License
    This file is part of OpenFOAM.

11
12
13
14
    OpenFOAM 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 3 of the License, or
    (at your option) any later version.
15
16
17
18
19
20
21

    OpenFOAM 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
22
    along with OpenFOAM.  If not, see <http://www.gnu.org/licenses/>.
23
24
25
26
27
28

Class
    Foam::UList

Description
    A 1D vector of objects of type \<T\>, where the size of the vector is
Mark Olesen's avatar
Mark Olesen committed
29
    known and can be used for subscript bounds checking, etc.
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

    Storage is not allocated during construction or use but is supplied to
    the constructor as an argument.  This type of list is particularly useful
    for lists that refer to parts of existing lists such as SubList.

SourceFiles
    UList.C
    UListI.H
    UListIO.C

\*---------------------------------------------------------------------------*/

#ifndef UList_H
#define UList_H

#include "bool.H"
Mark Olesen's avatar
Mark Olesen committed
46
47
#include "label.H"
#include "uLabel.H"
48
#include "zero.H"
49
50
#include "contiguous.H"
#include "nullObject.H"
51
#include "stdFoam.H"
52
#include "Swap.H"
53
#include "HashFwd.H"
54

55
#include <initializer_list>
56
57
#include <iterator>
#include <type_traits>
58
59
60
61
62
63

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

namespace Foam
{

64
65
// Forward declarations
class labelRange;
Mark Olesen's avatar
Mark Olesen committed
66
67
template<class T> class List;
template<class T> class SubList;
68
69
template<class T> class UList;
template<class T> Ostream& operator<<(Ostream&, const UList<T>&);
mattijs's avatar
mattijs committed
70
template<class T> Istream& operator>>(Istream&, UList<T>&);
71

72
// Common list types
73
typedef UList<char> charUList;
74
typedef UList<label> labelUList;
75

76

77
78
79
80
81
82
83
84
85
/*---------------------------------------------------------------------------*\
                           Class UList Declaration
\*---------------------------------------------------------------------------*/

template<class T>
class UList
{
    // Private data

86
        //- Number of elements in UList
87
88
        label size_;

89
        //- Vector of values of type T
90
91
92
        T* __restrict__ v_;


93
94
    // Private Member Functions

95
        //- No copy assignment (shallow copy)
96
97
98
99
100
101
        //
        //  Assignment of UList<T> may need to be either shallow (copy pointer)
        //  or deep (copy elements) depending on context or the particular type
        //  of list derived from UList and it is confusing and prone to error
        //  for the default assignment to be either.  The solution is to
        //  disallow default assignment and provide separate 'shallowCopy' and
102
        //  'deepCopy' member functions
103
        UList<T>& operator=(const UList<T>&) = delete;
104
105


106
107
108
109
protected:

    // Protected Member Functions

110
111
112
113
        //- Override size to be inconsistent with allocated storage.
        //  Use with care
        inline void size(const label n);

114
115
116
117
        //- True if there are two or more entries and all entries have
        //  identical values.
        inline bool uniform() const;

118
119
120
        //- Write the UList with its compound type
        void writeEntry(Ostream& os) const;

121
        //- Return a validated (start,size) subset range, which means that it
122
        //- always addresses a valid section of the list.
123
124
125
        labelRange validateRange(const labelRange& range) const;

        //- Return a validated (start,size) subset range, which means that it
126
        //- always addresses a valid section of the list.
127
128
129
130
        labelRange validateRange
        (
            std::initializer_list<label> start_size_pair
        ) const;
131

132
133
public:

134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
    // STL type definitions

        //- The value type the list contains
        typedef T value_type;

        //- The pointer type for non-const access to value_type items
        typedef T* pointer;

        //- The pointer type for const access to value_type items
        typedef const T* const_pointer;

        //- The type used for storing into value_type objects
        typedef T& reference;

        //- The type used for reading from constant value_type objects.
        typedef const T& const_reference;

        //- Random access iterator for traversing a UList
        typedef T* iterator;

        //- Random access iterator for traversing a UList
        typedef const T* const_iterator;

        //- The type to represent the size of a UList
        typedef label size_type;

        //- The difference between iterator objects
        typedef label difference_type;

        //- Reverse iterator (non-const access)
        typedef std::reverse_iterator<iterator>  reverse_iterator;

        //- Reverse iterator (const access)
        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;


170
171
172
173
174
175
176
177
    // Related types

        //- Declare friendship with the List class
        friend class List<T>;

        //- Declare friendship with the SubList class
        friend class SubList<T>;

178

179
180
    // Static Member Functions

181
        //- Return a UList reference to a nullObject
182
183
        inline static const UList<T>& null();

184

Mark Olesen's avatar
Mark Olesen committed
185
186
    // Public classes

187
188
        //- A list compare binary predicate for normal sort
        struct less
Mark Olesen's avatar
Mark Olesen committed
189
        {
190
            const UList<T>& values;
Mark Olesen's avatar
Mark Olesen committed
191

192
            less(const UList<T>& list)
Mark Olesen's avatar
Mark Olesen committed
193
            :
194
                values(list)
Mark Olesen's avatar
Mark Olesen committed
195
196
            {}

197
            bool operator()(const label a, const label b) const
Mark Olesen's avatar
Mark Olesen committed
198
            {
199
                return values[a] < values[b];
Mark Olesen's avatar
Mark Olesen committed
200
201
202
            }
        };

203
204
        //- A list compare binary predicate for reverse sort
        struct greater
205
        {
206
            const UList<T>& values;
207

208
            greater(const UList<T>& list)
209
            :
210
                values(list)
211
212
            {}

213
            bool operator()(const label a, const label b) const
214
            {
215
                return values[b] < values[a];
216
217
218
            }
        };

219
220
221

    // Constructors

222
        //- Null constructor
223
        inline constexpr UList() noexcept;
224
225

        //- Construct from components
226
        inline UList(T* __restrict__ v, label size) noexcept;
227
228


229
    // Member Functions
230
231
232

        // Access

233
            //- Return the forward circular index, i.e. next index
234
            //- which returns to the first at the end of the list
235
236
            inline label fcIndex(const label i) const;

237
238
239
240
241
242
243
            //- Return forward circular value (ie, next value in the list)
            inline const T& fcValue(const label i) const;

            //- Return forward circular value (ie, next value in the list)
            inline T& fcValue(const label i);

            //- Return the reverse circular index, i.e. previous index
244
            //- which returns to the last at the beginning of the list
245
246
            inline label rcIndex(const label i) const;

247
248
249
250
251
252
            //- Return reverse circular value (ie, previous value in the list)
            inline const T& rcValue(const label i) const;

            //- Return reverse circular value (ie, previous value in the list)
            inline T& rcValue(const label i);

253
            //- Return the binary size in number of characters of the UList
254
            //- if the element is a primitive type
255
256
257
            //  i.e. contiguous<T>() == true.
            //  Note that is of type streamsize since used in stream ops
            std::streamsize byteSize() const;
258
259


260
261
            //- Return a const pointer to the first data element.
            //  Similar to the STL front() method and the string::data() method
262
            //  This can be used (with caution) when interfacing with C code
Mark Olesen's avatar
Mark Olesen committed
263
264
            inline const T* cdata() const;

265
266
            //- Return a pointer to the first data element.
            //  Similar to the STL front() method and the string::data() method
267
            //  This can be used (with caution) when interfacing with C code
Mark Olesen's avatar
Mark Olesen committed
268
269
            inline T* data();

270
            //- Return the first element of the list
271
272
            inline T& first();

273
            //- Return first element of the list
274
275
            inline const T& first() const;

276
            //- Return the last element of the list
277
278
            inline T& last();

279
            //- Return the last element of the list
280
281
            inline const T& last() const;

Mark Olesen's avatar
Mark Olesen committed
282

283
284
        // Check

285
            //- Check start is within valid range [0,size)
286
287
            inline void checkStart(const label start) const;

288
            //- Check size is within valid range [0,size]
289
290
            inline void checkSize(const label size) const;

291
            //- Check index is within valid range [0,size)
292
293
294
            inline void checkIndex(const label i) const;


295
296
      // Search

Andrew Heather's avatar
Andrew Heather committed
297
298
        //- Find index of the first occurrence of the value.
        //  When start is specified, any occurrences before start are ignored.
299
        //  Linear search.
300
        //  \return position in list or -1 if not found.
301
302
        label find(const T& val, const label start=0) const;

Andrew Heather's avatar
Andrew Heather committed
303
304
        //- Find index of the last occurrence of the value.
        //  When pos is specified, any occurrences after pos are ignored.
305
        //  Linear search.
306
        //  \return position in list or -1 if not found.
307
308
        label rfind(const T& val, const label pos=-1) const;

309
310
311
312
        //- True if the value if found in the list.
        //  When start is specified, any occurences before start are ignored.
        //  Linear search.
        //  \return true if found.
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
        inline bool found(const T& val, const label start=0) const;


      // Edit

        //- Move element to the first position.
        void moveFirst(const label i);

        //- Move element to the last position.
        void moveLast(const label i);

        //- Swap element with the first element. Fatal on an empty list.
        void swapFirst(const label i);

        //- Swap element with the last element. Fatal on an empty list.
        void swapLast(const label i);


      // Copy

333
        //- Copy the pointer held by the given UList
334
        inline void shallowCopy(const UList<T>& list);
335

336
        //- Copy elements of the given UList
337
        void deepCopy(const UList<T>& list);
338

339
340
341

    // Member operators

342
        //- Return element of UList
Mark Olesen's avatar
Mark Olesen committed
343
        inline T& operator[](const label i);
344

345
        //- Return element of constant UList
Mark Olesen's avatar
Mark Olesen committed
346
347
        //  Note that the bool specialization adds lazy evaluation so reading
        //  an out-of-range element returns false without any ill-effects
Mark Olesen's avatar
Mark Olesen committed
348
        inline const T& operator[](const label i) const;
349

350
351
352
353
354
355
356
357
358
359
360
361
362
        //- Return (start,size) subset from UList with non-const access.
        //  The range is subsetted with the list size itself to ensure that the
        //  result always addresses a valid section of the list.
        UList<T> operator[](const labelRange& range);

        //- Return (start,size) subset from UList with const access.
        //  The range is subsetted with the list size itself to ensure that the
        //  result always addresses a valid section of the list.
        const UList<T> operator[](const labelRange& range) const;

        //- Return (start,size) subset from UList with non-const access.
        //  The range is subsetted with the list size itself to ensure that the
        //  result always addresses a valid section of the list.
363
        UList<T> operator[](std::initializer_list<label> start_size);
364
365
366
367
368
369

        //- Return (start,size) subset from UList with const access.
        //  The range is subsetted with the list size itself to ensure that the
        //  result always addresses a valid section of the list.
        const UList<T> operator[]
        (
370
            std::initializer_list<label> start_size
371
372
        ) const;

373
374
375
376
        //- Allow cast to a const List<T>&
        inline operator const Foam::List<T>&() const;

        //- Assignment of all entries to the given value
377
        void operator=(const T& val);
378

379
380
381
        //- Assignment of all entries to zero
        void operator=(const zero);

382

383
    // Random access iterator (non-const)
384

385
        //- Return an iterator to begin traversing the UList
386
387
        inline iterator begin();

388
        //- Return an iterator to end traversing the UList
389
390
391
        inline iterator end();


392
    // Random access iterator (const)
393

394
        //- Return const_iterator to begin traversing the constant UList
395
396
        inline const_iterator cbegin() const;

397
        //- Return const_iterator to end traversing the constant UList
398
399
        inline const_iterator cend() const;

400
        //- Return const_iterator to begin traversing the constant UList
401
402
        inline const_iterator begin() const;

403
        //- Return const_iterator to end traversing the constant UList
404
405
        inline const_iterator end() const;

406

407
    // Reverse iterators (non-const)
408

409
        //- Return reverse_iterator to begin reverse traversing the UList
410
411
        inline reverse_iterator rbegin();

412
        //- Return reverse_iterator to end reverse traversing the UList
413
414
415
        inline reverse_iterator rend();


416
    // Reverse iterators (const)
417

418
        //- Return const_reverse_iterator to begin reverse traversing the UList
419
420
        inline const_reverse_iterator crbegin() const;

421
        //- Return const_reverse_iterator to end reverse traversing the UList
422
423
        inline const_reverse_iterator crend() const;

424
        //- Return const_reverse_iterator to begin reverse traversing the UList
425
426
        inline const_reverse_iterator rbegin() const;

427
        //- Return const_reverse_iterator to end reverse traversing the UList
428
429
430
431
432
        inline const_reverse_iterator rend() const;


    // STL member functions

433
        //- Return the number of elements in the UList
434
435
        inline label size() const;

436
        //- Return size of the largest possible UList
437
438
        inline label max_size() const;

439
        //- Return true if the UList is empty (ie, size() is zero)
440
441
        inline bool empty() const;

442
        //- Swap content with another UList of the same type in constant time
443
        inline void swap(UList<T>& list);
444
445
446
447
448


    // STL member operators

        //- Equality operation on ULists of the same type.
449
        //  Returns true when the ULists are element-wise equal
450
        //  (using UList::value_type::operator==).  Takes linear time
Mark Olesen's avatar
Mark Olesen committed
451
        bool operator==(const UList<T>& a) const;
452

453
        //- The opposite of the equality operation. Takes linear time
Mark Olesen's avatar
Mark Olesen committed
454
        bool operator!=(const UList<T>& a) const;
455

456
        //- Compare two ULists lexicographically. Takes linear time
457
        bool operator<(const UList<T>& list) const;
458

459
        //- Compare two ULists lexicographically. Takes linear time
Mark Olesen's avatar
Mark Olesen committed
460
        bool operator>(const UList<T>& a) const;
461

462
        //- Return true if !(a > b). Takes linear time
Mark Olesen's avatar
Mark Olesen committed
463
        bool operator<=(const UList<T>& a) const;
464

465
        //- Return true if !(a < b). Takes linear time
Mark Olesen's avatar
Mark Olesen committed
466
        bool operator>=(const UList<T>& a) const;
467
468


469
470
471
472
473
    // Writing

        //- Write the List as a dictionary entry with keyword
        void writeEntry(const word& keyword, Ostream& os) const;

474
        //- Write the List, with line-breaks in ASCII if the list length
475
476
        //- exceeds shortListLen.
        //  Using '0' suppresses line-breaks entirely.
477
        Ostream& writeList(Ostream& os, const label shortListLen=0) const;
478

479

Mark Olesen's avatar
Mark Olesen committed
480
481
    // IOstream operators

482
        //- Write List to Ostream, as per writeList() with shortListLen=10
Henry Weller's avatar
Henry Weller committed
483
484
        friend Ostream& operator<< <T>
        (
Mark Olesen's avatar
Mark Olesen committed
485
            Ostream& os,
486
            const UList<T>& list
Henry Weller's avatar
Henry Weller committed
487
        );
mattijs's avatar
mattijs committed
488

Mark Olesen's avatar
Mark Olesen committed
489
490
        //- Read List contents from Istream.
        //  Requires size to have been set before
mattijs's avatar
mattijs committed
491
492
        friend Istream& operator>> <T>
        (
Mark Olesen's avatar
Mark Olesen committed
493
494
            Istream& os,
            UList<T>& L
mattijs's avatar
mattijs committed
495
        );
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533


    // Special Methods

        //- A bitSet::test() method for a list of bool
        //
        //  \return The element value, or false for out-of-range access
        template<class TypeT = T>
        typename std::enable_if<std::is_same<TypeT, bool>::value, bool>::type
        inline test(const label i) const
        {
            return (i >= 0 && i < size() && v_[i]);
        }

        //- A bitSet::get() method for a list of bool
        //
        //  \return The element value, or false for out-of-range access
        template<class TypeT = T>
        typename std::enable_if<std::is_same<TypeT, bool>::value, bool>::type
        inline get(const label i) const
        {
            return (i >= 0 && i < size_ && v_[i]);
        }

        //- A bitSet::unset() method for a list of bool
        //
        //  \return True if value changed and was not out-of-range
        template<class TypeT = T>
        typename std::enable_if<std::is_same<TypeT, bool>::value, bool>::type
        inline unset(const label i)
        {
            if (i >= 0 && i < size_ && v_[i])
            {
                v_[i] = false;
                return true;
            }
            return false;
        }
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561


    // Other

        //- Hashing function class for UList.
        //  Can use this one (instead of the global Hash<>) for inheritance
        //  in sub-classes
        template<class HashT=Foam::Hash<T>>
        struct Hash
        {
            inline unsigned operator()
            (
                const UList<T>& obj,
                unsigned seed=0
            ) const
            {
                if (contiguous<T>())
                {
                    return Hasher(obj.cdata(), obj.size()*sizeof(T), seed);
                }

                for (const T& val : obj)
                {
                    seed = HashT()(val, seed);
                }
                return seed;
            }
        };
562
563
};

564

565
// * * * * * * * * * * * * * * Global Functions  * * * * * * * * * * * * * * //
566

mattijs's avatar
mattijs committed
567
template<class T>
Mark Olesen's avatar
Mark Olesen committed
568
void sort(UList<T>& a);
mattijs's avatar
mattijs committed
569

570
571
template<class T, class Compare>
void sort(UList<T>& a, const Compare& comp);
mattijs's avatar
mattijs committed
572
573

template<class T>
Mark Olesen's avatar
Mark Olesen committed
574
void stableSort(UList<T>& a);
mattijs's avatar
mattijs committed
575

576
577
template<class T, class Compare>
void stableSort(UList<T>& a, const Compare& comp);
mattijs's avatar
mattijs committed
578

579
template<class T>
Mark Olesen's avatar
Mark Olesen committed
580
void shuffle(UList<T>& a);
581

582
583
// Reverse the first n elements of the list
template<class T>
584
inline void reverse(UList<T>& list, const label n);
585
586
587

// Reverse all the elements of the list
template<class T>
588
inline void reverse(UList<T>& list);
589
590
591
592

// Exchange contents of lists - see UList::swap().
template<class T>
inline void Swap(UList<T>& a, UList<T>& b);
593
594


595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
//- Hashing for UList data, which uses Hasher for contiguous data and
//- element-wise incrementally hashing otherwise.
template<class T>
struct Hash<UList<T>>
{
    inline unsigned operator()(const UList<T>& obj, unsigned seed=0) const
    {
        if (contiguous<T>())
        {
            return Hasher(obj.cdata(), obj.size()*sizeof(T), seed);
        }
        for (const T& val : obj)
        {
            seed = Hash<T>()(val, seed);
        }
        return seed;
    }
};


615
616
617
618
619
620
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

} // End namespace Foam

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

621
#include "UListI.H"
622
623
624
625

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

#ifdef NoRepository
626
    #include "UList.C"
627
628
629
630
631
632
633
#endif

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

#endif

// ************************************************************************* //