src/utils/LocalndexManager.hpp

/*
 * Copyright (C) 2000-2004  Object Oriented Parallel Simulation Engine (OOPSE) project
 * 
 * Contact: oopse@oopse.org
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2.1
 * of the License, or (at your option) any later version.
 * All we ask is that proper credit is given for our work, which includes
 * - but is not limited to - adding the above copyright notice to the beginning
 * of your source code files, and to any copyright notice that you may distribute
 * with programs based on this work.
 * 
 * This program 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 Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 */

/**
 * @file LocalIndexManager.hpp
 * @author    tlin
 * @date  11/02/2004
 * @version 1.0
 */ 

#ifndef UTILS_LOCALINDEXMANAGER_HPP
#define UTILS_LOCALINDEXMANAGER_HPP
#include <algorithm>
#include <cassert>
#include <list>
#include <utility>

namespace oopse {

/**
 * @class IndexListContainer
 * @brief 
 * @todo documentation
 */
class IndexListContainer{
    public:
        static const unsigned int MAX_INTEGER = 2147483647;
        typedef IndexListContainerIterator IndexListContainerIterator;

        
        IndexListContainer(unsigned int maxIndex = MAX_INTEGER) : maxIndex_(maxIndex) {
            
            indexContainer_.push_back(make_pair(0, maxIndex));
        }
        
        unsigned int pop() {
            
            if (indexContainer_.empty()) {
                std::cerr << "" << std::endl;
            }

            IndexListContainerIterator i = indexContainer_.begin();
            unsigned int result;
            
            result = indexContainer_.front().first;
            
            if (indexContainer_.front().first  == indexContainer_.front().second) {
                indexContainer_.pop_front();
            } else if (indexContainer_.front().first < indexContainer_.front().second) {
                --indexContainer_.front().first;
            } else {
                std::cerr << "" << std::endl;
            }

            return result;
        }


        /**
         *
         */
        void insert(unsigned int index) {
            IndexListContainerIterator insertPos = internalInsert(index, index, indexContainer_.begin());            
            merge(insertPos);
        }

        /**
         * Reclaims an index range
         * @param beginIndex
         * @param endIndex
         */
        void insert(unsigned int beginIndex, unsigned int endIndex) {
             IndexListContainerIterator insertPos = internalInsert(index, index, indexContainer_.begin()); 
             merge(insertPos);            
        }

        /**
         * Reclaims an index array.
         * @param indices
         */
        void insert(std::vector<unsigned int>& indices){

            if (indices.empty()) {
                return;
            }
            
            std::sort(indices.begin(), indices.end());
            std::unique(indices);

            std::vector<unsigned int>::iterator i;
            IndexListContainerIterator insertPos;
            unsigned int beginIndex;
            unsigned int endIndex;

            beginIndex = indices[0];
        
            for ( i = indices.begin() + 1 ; i != indices.end(); ++i) {
                if (*i != *(i -1) + 1) {
                    insertPos = insert(beginIndex, *(i-1));
                    merge(insertPos);
                    beginIndex = *i;
                }
            }

            insertPos = insert(beginIndex, *(i-1));
            merge(insertPos);
            
            
        }
        
        std::vector<unsigned int> getIndicesBefore(unsigned int index) {
            std::vector<unsigned int> result;
            IndexListContainerIterator i;

            for(i = indexContainer_.begin(); i != indexContainer_.end(); ++i) {
                if ((*i).first > index) {
                    indexContainer_.erase(indexContainer_, i);
                    break;
                } else if ((*i).second < index) {

                    for (unsigned int j = (*i).first; j <= (*i).second; ++j) {
                        result.push_back(j);
                    }
                    continue;
                } else if ((*i).first == (*i).second) {
                    result.push_back((*i).first);
                    indexContainer_.erase(indexContainer_.begin(), i);
                    break;
                } else {

                    for (unsigned int j = (*i).first; j < index; ++j) {
                        result.push_back(j);
                    }
                        
                    (*i).first =  index;                   
                    indexContainer_.erase(indexContainer_.begin(), i);
                    break;
                }
                
            }

            return result;

        }
        
        unsigned int getMaxIndex() {
            return maxIndex_;
        }
                
    private:
        
        IndexListContainerIterator internalInsert(unsigned int beginIndex, unsigned int endIndex, 
                                               IndexListContainerIterator i) {
            if (beginIndex > endIndex) {
                std::swap(beginIndex, endIndex);
                std::cerr << "" << std::endl;
            }

            if (endIndex > maxIndex_) {
                std::cerr << "" << std::endl;
            }

            IndexListContainerIterator j;

            if (i == indexContainer_.end()) {
                j = i;
                --j;
                if (j != indexContainer_.begin() && (*j).second >= beginIndex) {
                     std::cerr << "" << std::endl;
                }

                indexContainer_.insert(i, make_pair(beginIndex, endIndex));
                return --i;
            }
                

            for (j = i; j != indexContainer_.end(); ++j) {
                if ((*j).first > endIndex) {
                    indexContainer_.insert(j, make_pair(beginIndex, endIndex));
                    return --j;
                } else if ((*j).second < beginIndex) {
                    continue;
                } else {
                    std::cerr << "" << std::endl;
                }
            }

            
        }

        void merge(IndexListContainerIterator i) {
            IndexListContainerIterator j;
            
            if ( i != indexContainer_.begin()) {
                j = i;
                --j;
                if (j != indexContainer_.begin() && (*j).second + 1 == (*i).first) {
                    (*i).first = (*j).first;
                    indexContainer_.erase(j);
                }
            }

            if ( i != indexContainer_.end()) {
                j = i;
                ++j;

                if (j != indexContainer_.end() && (*i).second + 1 == (*j).first) {
                    (*i).second = (*j).second;
                    indexContainer_.erase(j);
                }
            }

        }
        
        unsigned int maxIndex_;        
        std::list<std::pair<unsigned int, unsigned int> > indexContainer_;
};


/**
 * @class LocalIndexManager LocalIndexManager.hpp "utils/LocalIndexManager.hpp"
 * @brief
 */
class LocalIndexManager {
    public:
        ~LocalIndexManager() {
            delete instance_;
        }
        
        unsigned int getNextAtomIndex() {
            return atomIndexContainer_.pop();
        }

        std::vector<unsigned int> getAtomIndicesBefore(unsigned int index) {
            return atomIndexContainer_.getIndicesBefore(index);
        }
        
        void releaseAtomIndex(unsigned int index) {
            atomIndexContainer_.insert(index);
        }

        void releaseAtomIndex(unsigned int beginIndex, unsigned int endIndex) {
            atomIndexContainer_.insert(beginIndex, endIndex);
        }

        void releaseAtomIndex(std::vector<unsigned int> indices) {
            atomIndexContainer_.insert(indices);
        }

       unsigned int getNextRigidBodyIndex() {
            return rigidBodyIndexContainer_.pop();
        }

        std::vector<unsigned int> getRigidBodyIndicesBefore(unsigned int index) {
            return rigidBodyIndexContainer_.getIndicesBefore(index);
        }
        
        void releaseRigidBodyIndex(unsigned int index) {
            rigidBodyIndexContainer_.insert(index);
        }

        void releaseRigidBodyIndex(unsigned int beginIndex, unsigned int endIndex) {
            rigidBodyIndexContainer_.insert(beginIndex, endIndex);
        }

        void releaseRigidBodyIndex(std::vector<unsigned int> indices) {
            rigidBodyIndexContainer_.insert(indices);
        }
 
        static LocalIndexManager* getInstance() {
            if (instance_ == NULL) {
                instance_ = new LocalIndexManager();
            } else {
                return instance_;
            }
        }

    private:
        LocalIndexManager();
        
        static LocalIndexManager* instance_;
        IndexListContainer atomIndexContainer_;
        IndexListContainer rigidBodyIndexContainer_;
};

} //end namespace oopse
#endif //UTILS_LOCALINDEXMANAGER_HPP
Revision:	1700
Committed:	Tue Nov 2 22:41:09 2004 UTC (19 years, 9 months ago) by tim
File size:	9631 byte(s)
Log Message:	Adding LocalIndexManager and Migrator. Need unit test
#	Content
1	/*
2	* Copyright (C) 2000-2004 Object Oriented Parallel Simulation Engine (OOPSE) project
3	*
4	* Contact: oopse@oopse.org
5	*
6	* This program is free software; you can redistribute it and/or
7	* modify it under the terms of the GNU Lesser General Public License
8	* as published by the Free Software Foundation; either version 2.1
9	* of the License, or (at your option) any later version.
10	* All we ask is that proper credit is given for our work, which includes
11	* - but is not limited to - adding the above copyright notice to the beginning
12	* of your source code files, and to any copyright notice that you may distribute
13	* with programs based on this work.
14	*
15	* This program is distributed in the hope that it will be useful,
16	* but WITHOUT ANY WARRANTY; without even the implied warranty of
17	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18	* GNU Lesser General Public License for more details.
19	*
20	* You should have received a copy of the GNU Lesser General Public License
21	* along with this program; if not, write to the Free Software
22	* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
23	*
24	*/
25
26	/**
27	* @file LocalIndexManager.hpp
28	* @author tlin
29	* @date 11/02/2004
30	* @version 1.0
31	*/
32
33	#ifndef UTILS_LOCALINDEXMANAGER_HPP
34	#define UTILS_LOCALINDEXMANAGER_HPP
35	#include <algorithm>
36	#include <cassert>
37	#include <list>
38	#include <utility>
39
40	namespace oopse {
41
42	/**
43	* @class IndexListContainer
44	* @brief
45	* @todo documentation
46	*/
47	class IndexListContainer{
48	public:
49	static const unsigned int MAX_INTEGER = 2147483647;
50	typedef IndexListContainerIterator IndexListContainerIterator;
51
52
53	IndexListContainer(unsigned int maxIndex = MAX_INTEGER) : maxIndex_(maxIndex) {
54
55	indexContainer_.push_back(make_pair(0, maxIndex));
56	}
57
58	unsigned int pop() {
59
60	if (indexContainer_.empty()) {
61	std::cerr << "" << std::endl;
62	}
63
64	IndexListContainerIterator i = indexContainer_.begin();
65	unsigned int result;
66
67	result = indexContainer_.front().first;
68
69	if (indexContainer_.front().first == indexContainer_.front().second) {
70	indexContainer_.pop_front();
71	} else if (indexContainer_.front().first < indexContainer_.front().second) {
72	--indexContainer_.front().first;
73	} else {
74	std::cerr << "" << std::endl;
75	}
76
77	return result;
78	}
79
80
81	/**
82	*
83	*/
84	void insert(unsigned int index) {
85	IndexListContainerIterator insertPos = internalInsert(index, index, indexContainer_.begin());
86	merge(insertPos);
87	}
88
89	/**
90	* Reclaims an index range
91	* @param beginIndex
92	* @param endIndex
93	*/
94	void insert(unsigned int beginIndex, unsigned int endIndex) {
95	IndexListContainerIterator insertPos = internalInsert(index, index, indexContainer_.begin());
96	merge(insertPos);
97	}
98
99	/**
100	* Reclaims an index array.
101	* @param indices
102	*/
103	void insert(std::vector<unsigned int>& indices){
104
105	if (indices.empty()) {
106	return;
107	}
108
109	std::sort(indices.begin(), indices.end());
110	std::unique(indices);
111
112	std::vector<unsigned int>::iterator i;
113	IndexListContainerIterator insertPos;
114	unsigned int beginIndex;
115	unsigned int endIndex;
116
117	beginIndex = indices[0];
118
119	for ( i = indices.begin() + 1 ; i != indices.end(); ++i) {
120	if (i != (i -1) + 1) {
121	insertPos = insert(beginIndex, *(i-1));
122	merge(insertPos);
123	beginIndex = *i;
124	}
125	}
126
127	insertPos = insert(beginIndex, *(i-1));
128	merge(insertPos);
129
130
131	}
132
133	std::vector<unsigned int> getIndicesBefore(unsigned int index) {
134	std::vector<unsigned int> result;
135	IndexListContainerIterator i;
136
137	for(i = indexContainer_.begin(); i != indexContainer_.end(); ++i) {
138	if ((*i).first > index) {
139	indexContainer_.erase(indexContainer_, i);
140	break;
141	} else if ((*i).second < index) {
142
143	for (unsigned int j = (i).first; j <= (i).second; ++j) {
144	result.push_back(j);
145	}
146	continue;
147	} else if ((i).first == (i).second) {
148	result.push_back((*i).first);
149	indexContainer_.erase(indexContainer_.begin(), i);
150	break;
151	} else {
152
153	for (unsigned int j = (*i).first; j < index; ++j) {
154	result.push_back(j);
155	}
156
157	(*i).first = index;
158	indexContainer_.erase(indexContainer_.begin(), i);
159	break;
160	}
161
162	}
163
164	return result;
165
166	}
167
168	unsigned int getMaxIndex() {
169	return maxIndex_;
170	}
171
172	private:
173
174	IndexListContainerIterator internalInsert(unsigned int beginIndex, unsigned int endIndex,
175	IndexListContainerIterator i) {
176	if (beginIndex > endIndex) {
177	std::swap(beginIndex, endIndex);
178	std::cerr << "" << std::endl;
179	}
180
181	if (endIndex > maxIndex_) {
182	std::cerr << "" << std::endl;
183	}
184
185	IndexListContainerIterator j;
186
187	if (i == indexContainer_.end()) {
188	j = i;
189	--j;
190	if (j != indexContainer_.begin() && (*j).second >= beginIndex) {
191	std::cerr << "" << std::endl;
192	}
193
194	indexContainer_.insert(i, make_pair(beginIndex, endIndex));
195	return --i;
196	}
197
198
199	for (j = i; j != indexContainer_.end(); ++j) {
200	if ((*j).first > endIndex) {
201	indexContainer_.insert(j, make_pair(beginIndex, endIndex));
202	return --j;
203	} else if ((*j).second < beginIndex) {
204	continue;
205	} else {
206	std::cerr << "" << std::endl;
207	}
208	}
209
210
211
212	}
213
214	void merge(IndexListContainerIterator i) {
215	IndexListContainerIterator j;
216
217	if ( i != indexContainer_.begin()) {
218	j = i;
219	--j;
220	if (j != indexContainer_.begin() && (j).second + 1 == (i).first) {
221	(i).first = (j).first;
222	indexContainer_.erase(j);
223	}
224	}
225
226	if ( i != indexContainer_.end()) {
227	j = i;
228	++j;
229
230	if (j != indexContainer_.end() && (i).second + 1 == (j).first) {
231	(i).second = (j).second;
232	indexContainer_.erase(j);
233	}
234	}
235
236	}
237
238	unsigned int maxIndex_;
239	std::list<std::pair<unsigned int, unsigned int> > indexContainer_;
240	};
241
242
243	/**
244	* @class LocalIndexManager LocalIndexManager.hpp "utils/LocalIndexManager.hpp"
245	* @brief
246	*/
247	class LocalIndexManager {
248	public:
249	~LocalIndexManager() {
250	delete instance_;
251	}
252
253	unsigned int getNextAtomIndex() {
254	return atomIndexContainer_.pop();
255	}
256
257	std::vector<unsigned int> getAtomIndicesBefore(unsigned int index) {
258	return atomIndexContainer_.getIndicesBefore(index);
259	}
260
261	void releaseAtomIndex(unsigned int index) {
262	atomIndexContainer_.insert(index);
263	}
264
265	void releaseAtomIndex(unsigned int beginIndex, unsigned int endIndex) {
266	atomIndexContainer_.insert(beginIndex, endIndex);
267	}
268
269	void releaseAtomIndex(std::vector<unsigned int> indices) {
270	atomIndexContainer_.insert(indices);
271	}
272
273	unsigned int getNextRigidBodyIndex() {
274	return rigidBodyIndexContainer_.pop();
275	}
276
277	std::vector<unsigned int> getRigidBodyIndicesBefore(unsigned int index) {
278	return rigidBodyIndexContainer_.getIndicesBefore(index);
279	}
280
281	void releaseRigidBodyIndex(unsigned int index) {
282	rigidBodyIndexContainer_.insert(index);
283	}
284
285	void releaseRigidBodyIndex(unsigned int beginIndex, unsigned int endIndex) {
286	rigidBodyIndexContainer_.insert(beginIndex, endIndex);
287	}
288
289	void releaseRigidBodyIndex(std::vector<unsigned int> indices) {
290	rigidBodyIndexContainer_.insert(indices);
291	}
292
293	static LocalIndexManager* getInstance() {
294	if (instance_ == NULL) {
295	instance_ = new LocalIndexManager();
296	} else {
297	return instance_;
298	}
299	}
300
301	private:
302	LocalIndexManager();
303
304	static LocalIndexManager* instance_;
305	IndexListContainer atomIndexContainer_;
306	IndexListContainer rigidBodyIndexContainer_;
307	};
308
309	} //end namespace oopse
310	#endif //UTILS_LOCALINDEXMANAGER_HPP