LongList.H 6.92 KB
Newer Older
Franjo's avatar
Franjo committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*---------------------------------------------------------------------------*\
  =========                 |
  \\      /  F ield         | cfMesh: A library for mesh generation
   \\    /   O peration     |
    \\  /    A nd           | Author: Franjo Juretic (franjo.juretic@c-fields.com)
     \\/     M anipulation  | Copyright (C) Creative Fields, Ltd.
-------------------------------------------------------------------------------
License
    This file is part of cfMesh.

    cfMesh 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.

    cfMesh 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
    along with cfMesh.  If not, see <http://www.gnu.org/licenses/>.

Class
    LongList

Description
    A dynamic list is a 1-D vector of objects of type T which resizes
    itself as necessary to accept the new objects.  Internal storage
    is a 2-D graph with a fixed size of the chunks used to store the data.
    This way the data does not get copied every time array is resized, but
    only the pointers to the chunks of data.

SourceFiles
    LongListI.H
    LongList.C

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

#ifndef LongList_H
#define LongList_H

#include "label.H"
44
#include "longLong.H"
Franjo's avatar
Franjo committed
45
#include "bool.H"
Franjo's avatar
Franjo committed
46
#include "IOstreams.H"
Franjo's avatar
Franjo committed
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include "error.H"

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

namespace Foam
{

// * * * * * * Forward declaration of template friend fuctions * * * * * * * //

template<class T, label Offset>
class LongList;

template<class T, label Offset>
Ostream& operator<<
(
    Ostream&,
    const LongList<T, Offset>&
);
template<class T, label Offset>
Istream& operator>>
(
    Istream&,
    LongList<T, Offset>&
);

/*---------------------------------------------------------------------------*\
                           Class LongList Declaration
\*---------------------------------------------------------------------------*/

template<class T, label Offset = 19>
class LongList
{
    // Private data
        //- number of allocated elements
Franjo's avatar
Franjo committed
81
        label N_;
82

Franjo's avatar
Franjo committed
83
        //- number of elements in the list
Franjo's avatar
Franjo committed
84
        label nextFree_;
85

Franjo's avatar
Franjo committed
86
87
        //- number of used blocks of data
        label numBlocks_;
88

Franjo's avatar
Franjo committed
89
90
91
92
        //- maximum number of blocks that can be allocated
        //- without reallocating the list containing pointers
        //- to the chunks of data
        label numAllocatedBlocks_;
93

Franjo's avatar
Franjo committed
94
95
96
97
        //- size of blocks is calculated by powers of 2
        //- and therefore the access can be done using shift and mask
        label shift_;
        label mask_;
98

Franjo's avatar
Franjo committed
99
100
101
102
103
        //- array of pointers to the blocks of data, each of the size WIDTH
        T** dataPtr_;

    // Private member functions
        //- check index
Franjo's avatar
Franjo committed
104
        void checkIndex(const label i) const;
105

Franjo's avatar
Franjo committed
106
107
        //- initialize width and mask
        void initializeParameters();
108

Franjo's avatar
Franjo committed
109
        //- Allocate memory for the list
Franjo's avatar
Franjo committed
110
        void allocateSize(const label);
111

Franjo's avatar
Franjo committed
112
113
        //- delete all elements
        void clearOut();
114

Franjo's avatar
Franjo committed
115
116
117
118
119
120
121
122
public:

    // Constructors

        //- Construct null
        inline LongList();

        //- Construct given size
Franjo's avatar
Franjo committed
123
        explicit inline LongList(const label size);
Franjo's avatar
Franjo committed
124
125

        //- Construct to given size and initialize
Franjo's avatar
Franjo committed
126
        explicit inline LongList(const label size, const T& t);
Franjo's avatar
Franjo committed
127
128
129
130
131
132
133
134
135
136
137
138
139

        //- Copy contructor
        inline LongList(const LongList<T, Offset>&);

    // Destructor

        inline ~LongList();

    // Member Functions

        // Access

            //- Size of the active part of the list.
Franjo's avatar
Franjo committed
140
            inline label size() const;
141

Franjo's avatar
Franjo committed
142
            //- Return the binary size in number of characters of the UList
143
            //  if the element is a primitive type
Franjo's avatar
Franjo committed
144
            //  i.e. contiguous<T>() == true
Franjo's avatar
Franjo committed
145
            inline label byteSize() const;
Franjo's avatar
Franjo committed
146
147
148
149

        // Edit

            //- Reset size of List.
Franjo's avatar
Franjo committed
150
            void setSize(const label);
Franjo's avatar
Franjo committed
151
152
153
154
155
156
157

            //- Clear the list, i.e. set next free to zero.
            //  Allocated size does not change
            void clear();

            //- Shrink the list to the number of elements used
            inline LongList<T, Offset>& shrink();
158

Franjo's avatar
Franjo committed
159
160
161
162
163
164
165
166
            //- transfer the list from another one without allocating it
            inline void transfer(LongList<T, Offset>&);


    // Member Operators

        //- Append an element at the end of the list
        inline void append(const T& e);
167

Franjo's avatar
Franjo committed
168
169
170
        //- Append an element at the end of the list if it is not yet
        //- present in the list (takes linear time)
        inline void appendIfNotIn(const T& e);
171

Franjo's avatar
Franjo committed
172
173
        //- check if the element is in the list (takes linear time)
        inline bool contains(const T& e) const;
Franjo's avatar
Franjo committed
174
        inline label containsAtPosition(const T& e) const;
Franjo's avatar
Franjo committed
175
176

        //- Return and remove the element
Franjo's avatar
Franjo committed
177
        inline T remove(const label i);
Franjo's avatar
Franjo committed
178
        inline T removeLastElement();
179

Franjo's avatar
Franjo committed
180
        //- get and set operators
Franjo's avatar
Franjo committed
181
182
        inline const T& operator[](const label i) const;
        inline T& operator[](const label i);
Franjo's avatar
Franjo committed
183
184
185

        //- Return non-const access to an element,
        //  resizing the list if necessary
Franjo's avatar
Franjo committed
186
        inline T& operator()(const label);
187

Franjo's avatar
Franjo committed
188
189
        //- return a non-const access to an element,
        // resize the list if necessary
Franjo's avatar
Franjo committed
190
        inline T& newElmt(const label);
Franjo's avatar
Franjo committed
191
192
193

        //- Assignment of all entries to the given value
        inline void operator=(const T&);
194

Franjo's avatar
Franjo committed
195
196
197
198
199
200
201
        //- Assignment operator
        inline void operator=(const LongList<T, Offset>&);


    // IOstream operators
        //- Read from stream and append to the current content
        void appendFromStream(Istream&);
202

Franjo's avatar
Franjo committed
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
        //- Write as a dictionary entry.
        void writeEntry(Ostream& os) const;

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

        // Write LongList to Ostream.
        friend Ostream& operator<< <T, Offset>
        (
            Ostream&,
            const LongList<T, Offset>&
        );

        //- Read from Istream, discarding contents of existing LongList.
        friend Istream& operator>> <T, Offset>
        (
            Istream&,
            LongList<T, Offset>&
        );
};


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

} // End namespace Foam

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

#include "LongListI.H"

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

#ifdef NoRepository
#   include "LongList.C"
#endif

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

#endif

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