UList.H 16.2 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 "nullObject.H"
49
#include "zero.H"
50
#include "stdFoam.H"
51
52
#include "Swap.H"

53
#include <initializer_list>
54
55
56
57
58
59

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

namespace Foam
{

60
61
// Forward declarations
class labelRange;
Mark Olesen's avatar
Mark Olesen committed
62
63
template<class T> class List;
template<class T> class SubList;
64
65
66
67

// Forward declaration of friend functions and operators
template<class T> class UList;
template<class T> Ostream& operator<<(Ostream&, const UList<T>&);
mattijs's avatar
mattijs committed
68
template<class T> Istream& operator>>(Istream&, UList<T>&);
69

70
typedef UList<label> labelUList;
71
72
73
74
75
76
77
78
79
80

/*---------------------------------------------------------------------------*\
                           Class UList Declaration
\*---------------------------------------------------------------------------*/

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

81
        //- Number of elements in UList
82
83
        label size_;

84
        //- Vector of values of type T
85
86
87
        T* __restrict__ v_;


88
89
90
91
92
93
94
95
96
    // Private Member Functions

        //- Disallow default shallow-copy assignment
        //
        //  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
97
        //  'deepCopy' member functions
98
99
100
        void operator=(const UList<T>&) = delete;


101
102
103
104
protected:

    // Protected Member Functions

105
106
107
108
        //- Override size to be inconsistent with allocated storage.
        //  Use with care
        inline void size(const label n);

109
110
111
        //- Write the UList with its compound type
        void writeEntry(Ostream& os) const;

112
113
114
115
116
117
118
119
120
121
        //- Return a validated (start,size) subset range, which means that it
        //  always addresses a valid section of the list.
        labelRange validateRange(const labelRange& range) const;

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

123
124
125
126
127
128
129
130
131
132
public:

    // Related types

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

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

133

134
135
136
137
138
    // Static Member Functions

        //- Return a null UList
        inline static const UList<T>& null();

139

Mark Olesen's avatar
Mark Olesen committed
140
141
    // Public classes

142
143
        //- A list compare binary predicate for normal sort
        struct less
Mark Olesen's avatar
Mark Olesen committed
144
        {
145
            const UList<T>& values;
Mark Olesen's avatar
Mark Olesen committed
146

147
            less(const UList<T>& list)
Mark Olesen's avatar
Mark Olesen committed
148
            :
149
                values(list)
Mark Olesen's avatar
Mark Olesen committed
150
151
            {}

152
            bool operator()(const label a, const label b) const
Mark Olesen's avatar
Mark Olesen committed
153
            {
154
                return values[a] < values[b];
Mark Olesen's avatar
Mark Olesen committed
155
156
157
            }
        };

158
159
        //- A list compare binary predicate for reverse sort
        struct greater
160
        {
161
            const UList<T>& values;
162

163
            greater(const UList<T>& list)
164
            :
165
                values(list)
166
167
            {}

168
            bool operator()(const label a, const label b) const
169
            {
170
                return values[a] > values[b];
171
172
173
            }
        };

174
175
176

    // Constructors

177
        //- Null constructor
178
179
180
181
182
183
        inline UList();

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


184
    // Member Functions
185
186
187

        // Access

188
            //- Return the forward circular index, i.e. next index
189
190
191
            //  which returns to the first at the end of the list
            inline label fcIndex(const label i) const;

192
193
194
195
196
197
198
            //- 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
199
            //  which returns to the last at the beginning of the list
200
201
            inline label rcIndex(const label i) const;

202
203
204
205
206
207
            //- 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);

208
209
            //- Return the binary size in number of characters of the UList
            //  if the element is a primitive type
210
211
212
            //  i.e. contiguous<T>() == true.
            //  Note that is of type streamsize since used in stream ops
            std::streamsize byteSize() const;
213
214


Mark Olesen's avatar
Mark Olesen committed
215
216
            //- Return a const pointer to the first data element,
            //  similar to the STL front() method and the string::data() method
217
            //  This can be used (with caution) when interfacing with C code
Mark Olesen's avatar
Mark Olesen committed
218
219
220
221
            inline const T* cdata() const;

            //- Return a pointer to the first data element,
            //  similar to the STL front() method and the string::data() method
222
            //  This can be used (with caution) when interfacing with C code
Mark Olesen's avatar
Mark Olesen committed
223
224
            inline T* data();

225
            //- Return the first element of the list
226
227
            inline T& first();

228
            //- Return first element of the list
229
230
            inline const T& first() const;

231
            //- Return the last element of the list
232
233
            inline T& last();

234
            //- Return the last element of the list
235
236
            inline const T& last() const;

Mark Olesen's avatar
Mark Olesen committed
237

238
239
        // Check

240
            //- Check start is within valid range (0 ... size-1)
241
242
            inline void checkStart(const label start) const;

243
            //- Check size is within valid range (0 ... size)
244
245
            inline void checkSize(const label size) const;

246
            //- Check index i is within valid range (0 ... size-1)
247
248
249
            inline void checkIndex(const label i) const;


250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
      // Search

        //- Find index of the first occurence of the value.
        //  When start is specified, any occurences before start are ignored.
        //  Linear search.
        //  \return -1 if not found.
        label find(const T& val, const label start=0) const;

        //- Find index of the last occurence of the value.
        //  When pos is specified, any occurences after pos are ignored.
        //  Linear search.
        //  \return -1 if not found.
        label rfind(const T& val, const label pos=-1) const;

        //- True if the value if found in the list. Linear search.
        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

285
        //- Copy the pointer held by the given UList
Mark Olesen's avatar
Mark Olesen committed
286
        inline void shallowCopy(const UList<T>& a);
287

288
        //- Copy elements of the given UList
Mark Olesen's avatar
Mark Olesen committed
289
        void deepCopy(const UList<T>& a);
290

291
292
293

    // Member operators

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

297
        //- Return element of constant UList
Mark Olesen's avatar
Mark Olesen committed
298
299
        //  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
300
        inline const T& operator[](const label i) const;
301

302
303
304
305
306
307
308
309
310
311
312
313
314
        //- 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.
315
        UList<T> operator[](std::initializer_list<label> start_size);
316
317
318
319
320
321

        //- 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[]
        (
322
            std::initializer_list<label> start_size
323
324
        ) const;

325
326
327
328
        //- Allow cast to a const List<T>&
        inline operator const Foam::List<T>&() const;

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

331
332
333
        //- Assignment of all entries to zero
        void operator=(const zero);

334
335
336

    // STL type definitions

337
        //- Type of values the UList contains
338
339
        typedef T value_type;

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

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

        //- The type that can represent the difference between any two
347
        //  UList iterator objects
348
349
        typedef label difference_type;

350
        //- The type that can represent the size of a UList
351
352
353
354
355
        typedef label size_type;


    // STL iterator

356
        //- Random access iterator for traversing UList
357
358
        typedef T* iterator;

359
        //- Return an iterator to begin traversing the UList
360
361
        inline iterator begin();

362
        //- Return an iterator to end traversing the UList
363
364
365
366
367
        inline iterator end();


    // STL const_iterator

368
        //- Random access iterator for traversing UList
369
370
        typedef const T* const_iterator;

371
        //- Return const_iterator to begin traversing the constant UList
372
373
        inline const_iterator cbegin() const;

374
        //- Return const_iterator to end traversing the constant UList
375
376
        inline const_iterator cend() const;

377
        //- Return const_iterator to begin traversing the constant UList
378
379
        inline const_iterator begin() const;

380
        //- Return const_iterator to end traversing the constant UList
381
382
383
384
385
        inline const_iterator end() const;


    // STL reverse_iterator

386
        //- Reverse iterator for reverse traversal of UList
387
388
        typedef T* reverse_iterator;

389
        //- Return reverse_iterator to begin reverse traversing the UList
390
391
        inline reverse_iterator rbegin();

392
        //- Return reverse_iterator to end reverse traversing the UList
393
394
395
396
397
        inline reverse_iterator rend();


    // STL const_reverse_iterator

398
        //- Reverse iterator for reverse traversal of constant UList
399
400
        typedef const T* const_reverse_iterator;

401
        //- Return const_reverse_iterator to begin reverse traversing the UList
402
403
        inline const_reverse_iterator crbegin() const;

404
        //- Return const_reverse_iterator to end reverse traversing the UList
405
406
        inline const_reverse_iterator crend() const;

407
        //- Return const_reverse_iterator to begin reverse traversing the UList
408
409
        inline const_reverse_iterator rbegin() const;

410
        //- Return const_reverse_iterator to end reverse traversing the UList
411
412
413
414
415
        inline const_reverse_iterator rend() const;


    // STL member functions

416
        //- Return the number of elements in the UList
417
418
        inline label size() const;

419
        //- Return size of the largest possible UList
420
421
        inline label max_size() const;

422
        //- Return true if the UList is empty (ie, size() is zero)
423
424
        inline bool empty() const;

425
426
        //- Swap content with another UList of the same type in constant time
        inline void swap(UList<T>& lst);
427
428
429
430
431


    // STL member operators

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

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

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

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

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

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


452
453
454
455
456
    // Writing

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

457
458
459
        //- Write the List, with line-breaks in ASCII if the list length
        //  exceeds shortListLen. Using '0' suppresses line-breaks entirely.
        Ostream& writeList(Ostream& os, const label shortListLen=0) const;
460

461

Mark Olesen's avatar
Mark Olesen committed
462
463
    // IOstream operators

464
        //- Write List to Ostream, as per writeList() with shortListLen=10
Henry Weller's avatar
Henry Weller committed
465
466
        friend Ostream& operator<< <T>
        (
Mark Olesen's avatar
Mark Olesen committed
467
            Ostream& os,
468
            const UList<T>& lst
Henry Weller's avatar
Henry Weller committed
469
        );
mattijs's avatar
mattijs committed
470

Mark Olesen's avatar
Mark Olesen committed
471
472
        //- Read List contents from Istream.
        //  Requires size to have been set before
mattijs's avatar
mattijs committed
473
474
        friend Istream& operator>> <T>
        (
Mark Olesen's avatar
Mark Olesen committed
475
476
            Istream& os,
            UList<T>& L
mattijs's avatar
mattijs committed
477
        );
478
479
};

480
481
482

// Global Functions

mattijs's avatar
mattijs committed
483
template<class T>
Mark Olesen's avatar
Mark Olesen committed
484
void sort(UList<T>& a);
mattijs's avatar
mattijs committed
485

486
487
template<class T, class Compare>
void sort(UList<T>& a, const Compare& comp);
mattijs's avatar
mattijs committed
488
489

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

492
493
template<class T, class Compare>
void stableSort(UList<T>& a, const Compare& comp);
mattijs's avatar
mattijs committed
494

495
template<class T>
Mark Olesen's avatar
Mark Olesen committed
496
void shuffle(UList<T>& a);
497

498
499
// Reverse the first n elements of the list
template<class T>
500
inline void reverse(UList<T>& lst, const label n);
501
502
503

// Reverse all the elements of the list
template<class T>
504
505
506
507
508
inline void reverse(UList<T>& lst);

// Exchange contents of lists - see UList::swap().
template<class T>
inline void Swap(UList<T>& a, UList<T>& b);
509
510
511
512
513
514
515
516


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

} // End namespace Foam

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

517
#include "UListI.H"
518
519
520
521

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

#ifdef NoRepository
522
    #include "UList.C"
523
524
525
526
527
528
529
#endif

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

#endif

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