src/utils/LocalIndexManager.hpp

 /*
 * Copyright (c) 2005 The University of Notre Dame. All Rights Reserved.
 *
 * The University of Notre Dame grants you ("Licensee") a
 * non-exclusive, royalty free, license to use, modify and
 * redistribute this software in source and binary code form, provided
 * that the following conditions are met:
 *
 * 1. Acknowledgement of the program authors must be made in any
 *    publication of scientific results based in part on use of the
 *    program.  An acceptable form of acknowledgement is citation of
 *    the article in which the program was described (Matthew
 *    A. Meineke, Charles F. Vardeman II, Teng Lin, Christopher
 *    J. Fennell and J. Daniel Gezelter, "OOPSE: An Object-Oriented
 *    Parallel Simulation Engine for Molecular Dynamics,"
 *    J. Comput. Chem. 26, pp. 252-271 (2005))
 *
 * 2. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 3. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the
 *    distribution.
 *
 * This software is provided "AS IS," without a warranty of any
 * kind. All express or implied conditions, representations and
 * warranties, including any implied warranty of merchantability,
 * fitness for a particular purpose or non-infringement, are hereby
 * excluded.  The University of Notre Dame and its licensors shall not
 * be liable for any damages suffered by licensee as a result of
 * using, modifying or distributing the software or its
 * derivatives. In no event will the University of Notre Dame or its
 * licensors be liable for any lost revenue, profit or data, or for
 * direct, indirect, special, consequential, incidental or punitive
 * damages, however caused and regardless of the theory of liability,
 * arising out of the use of or inability to use software, even if the
 * University of Notre Dame has been advised of the possibility of
 * such damages.
 */
 
/**
 * @file LocalIndexManager.hpp
 * @author    tlin
 * @date  11/02/2004
 * @version 1.0
 */ 

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

namespace oopse {

/**
 * @class IndexListContainer
 * @brief 
 * @todo documentation
 */
class IndexListContainer{
    public:
        static const int MAX_INTEGER = 2147483647;
        typedef std::list<std::pair<int, int> >::iterator  IndexListContainerIterator;

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

            IndexListContainerIterator i = indexContainer_.begin();
            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(int index) {
            IndexListContainerIterator insertPos = internalInsert(index, index);            
            merge(insertPos);
        }

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

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

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

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

            beginIndex = indices[0];
        
            for ( i = indices.begin() + 1 ; i != indices.end(); ++i) {
                if (*i != *(i -1) + 1) {
                    insert(beginIndex, *(i-1));
                    beginIndex = *i;
                }
            }
            
            
        }
        
        std::vector<int> getIndicesBefore(int index) {
            std::vector<int> result;
            IndexListContainerIterator i;

            for(i = indexContainer_.begin(); i != indexContainer_.end(); ++i) {
                if ((*i).first > index) {
                    //we locate the node whose minimum index is greater that index
                    indexContainer_.erase(indexContainer_.begin(), i);
                    break;
                } else if ((*i).second < index) {
                    //The biggest index current node hold is less than the index we want
                    for (int j = (*i).first; j <= (*i).second; ++j) {
                        result.push_back(j);
                    }
                    continue;
                } else if ((*i).first == (*i).second) {
                    //the index happen to equal to a node which only contains one index
                    result.push_back((*i).first);
                    indexContainer_.erase(indexContainer_.begin(), i);
                    break;
                } else {

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

            return result;

        }
        
        int getMaxIndex() {
            return maxIndex_;
        }
                
    private:
        
        IndexListContainerIterator internalInsert(int beginIndex, int endIndex) {

            if (beginIndex > endIndex) {
                std::swap(beginIndex, endIndex);
                std::cerr << "" << std::endl;
            }

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

                      
            IndexListContainerIterator j;

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

            indexContainer_.push_back(std::make_pair(beginIndex, endIndex));
            return --indexContainer_.end();

        }

        void merge(IndexListContainerIterator i) {
            IndexListContainerIterator j;

            //check whether current node can be merged with its previous node            
            if ( i != indexContainer_.begin()) {
                j = i;
                --j;
                if (j != indexContainer_.begin() && (*j).second + 1 == (*i).first) {
                    (*i).first = (*j).first;
                    indexContainer_.erase(j);
                }
            }

            //check whether current node can be merged with its next node            
            if ( i != indexContainer_.end()) {
                j = i;
                ++j;

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

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


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

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

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

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

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

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

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

        void releaseRigidBodyIndex(std::vector<int> indices) {
            rigidBodyIndexContainer_.insert(indices);
        }
 
    private:

        IndexListContainer atomIndexContainer_;
        IndexListContainer rigidBodyIndexContainer_;
};

} //end namespace oopse
#endif //UTILS_LOCALINDEXMANAGER_HPP
Revision:	1927
Committed:	Wed Jan 12 17:14:35 2005 UTC (20 years, 6 months ago) by tim
File size:	10014 byte(s)
Log Message:	change license
#	User	Rev	Content
1	tim	1927	/*
2			* Copyright (c) 2005 The University of Notre Dame. All Rights Reserved.
3	tim	1802	*
4	tim	1927	* The University of Notre Dame grants you ("Licensee") a
5			* non-exclusive, royalty free, license to use, modify and
6			* redistribute this software in source and binary code form, provided
7			* that the following conditions are met:
8			*
9			* 1. Acknowledgement of the program authors must be made in any
10			* publication of scientific results based in part on use of the
11			* program. An acceptable form of acknowledgement is citation of
12			* the article in which the program was described (Matthew
13			* A. Meineke, Charles F. Vardeman II, Teng Lin, Christopher
14			* J. Fennell and J. Daniel Gezelter, "OOPSE: An Object-Oriented
15			* Parallel Simulation Engine for Molecular Dynamics,"
16			* J. Comput. Chem. 26, pp. 252-271 (2005))
17			*
18			* 2. Redistributions of source code must retain the above copyright
19			* notice, this list of conditions and the following disclaimer.
20			*
21			* 3. Redistributions in binary form must reproduce the above copyright
22			* notice, this list of conditions and the following disclaimer in the
23			* documentation and/or other materials provided with the
24			* distribution.
25			*
26			* This software is provided "AS IS," without a warranty of any
27			* kind. All express or implied conditions, representations and
28			* warranties, including any implied warranty of merchantability,
29			* fitness for a particular purpose or non-infringement, are hereby
30			* excluded. The University of Notre Dame and its licensors shall not
31			* be liable for any damages suffered by licensee as a result of
32			* using, modifying or distributing the software or its
33			* derivatives. In no event will the University of Notre Dame or its
34			* licensors be liable for any lost revenue, profit or data, or for
35			* direct, indirect, special, consequential, incidental or punitive
36			* damages, however caused and regardless of the theory of liability,
37			* arising out of the use of or inability to use software, even if the
38			* University of Notre Dame has been advised of the possibility of
39			* such damages.
40	tim	1802	*/
41	tim	1927
42	tim	1802	/**
43			* @file LocalIndexManager.hpp
44			* @author tlin
45			* @date 11/02/2004
46			* @version 1.0
47			*/
48
49			#ifndef UTILS_LOCALINDEXMANAGER_HPP
50			#define UTILS_LOCALINDEXMANAGER_HPP
51			#include <algorithm>
52			#include <iostream>
53			#include <cassert>
54			#include <list>
55			#include <utility>
56
57			namespace oopse {
58
59			/**
60			* @class IndexListContainer
61			* @brief
62			* @todo documentation
63			*/
64			class IndexListContainer{
65			public:
66	tim	1803	static const int MAX_INTEGER = 2147483647;
67			typedef std::list<std::pair<int, int> >::iterator IndexListContainerIterator;
68	tim	1802
69
70	tim	1803	IndexListContainer(int minIndex = 0, int maxIndex = MAX_INTEGER)
71	tim	1802	:minIndex_(minIndex), maxIndex_(maxIndex) {
72
73			indexContainer_.push_back(std::make_pair(minIndex, maxIndex));
74			}
75
76	tim	1803	int pop() {
77	tim	1802
78			if (indexContainer_.empty()) {
79			std::cerr << "" << std::endl;
80			}
81
82			IndexListContainerIterator i = indexContainer_.begin();
83	tim	1803	int result;
84	tim	1802
85			result = indexContainer_.front().first;
86
87			if (indexContainer_.front().first == indexContainer_.front().second) {
88			indexContainer_.pop_front();
89			} else if (indexContainer_.front().first < indexContainer_.front().second) {
90	tim	1841	++indexContainer_.front().first;
91	tim	1802	} else {
92			std::cerr << "" << std::endl;
93			}
94
95			return result;
96			}
97
98
99			/**
100			*
101			*/
102	tim	1803	void insert(int index) {
103			IndexListContainerIterator insertPos = internalInsert(index, index);
104	tim	1802	merge(insertPos);
105			}
106
107			/**
108			* Reclaims an index range
109			* @param beginIndex
110			* @param endIndex
111			*/
112	tim	1803	void insert(int beginIndex, int endIndex) {
113			IndexListContainerIterator insertPos = internalInsert(beginIndex, endIndex);
114	tim	1802	merge(insertPos);
115			}
116
117			/**
118			* Reclaims an index array.
119			* @param indices
120			*/
121	tim	1803	void insert(std::vector<int>& indices){
122	tim	1802
123			if (indices.empty()) {
124			return;
125			}
126
127			std::sort(indices.begin(), indices.end());
128	tim	1803	std::unique(indices.begin(), indices.end());
129	tim	1802
130	tim	1803	std::vector<int>::iterator i;
131	tim	1802	IndexListContainerIterator insertPos;
132	tim	1803	int beginIndex;
133	tim	1802
134			beginIndex = indices[0];
135
136			for ( i = indices.begin() + 1 ; i != indices.end(); ++i) {
137			if (i != (i -1) + 1) {
138	tim	1803	insert(beginIndex, *(i-1));
139	tim	1802	beginIndex = *i;
140			}
141			}
142
143
144			}
145
146	tim	1803	std::vector<int> getIndicesBefore(int index) {
147			std::vector<int> result;
148	tim	1802	IndexListContainerIterator i;
149
150			for(i = indexContainer_.begin(); i != indexContainer_.end(); ++i) {
151			if ((*i).first > index) {
152	tim	1803	//we locate the node whose minimum index is greater that index
153			indexContainer_.erase(indexContainer_.begin(), i);
154	tim	1802	break;
155			} else if ((*i).second < index) {
156	tim	1803	//The biggest index current node hold is less than the index we want
157			for (int j = (i).first; j <= (i).second; ++j) {
158	tim	1802	result.push_back(j);
159			}
160			continue;
161			} else if ((i).first == (i).second) {
162	tim	1803	//the index happen to equal to a node which only contains one index
163	tim	1802	result.push_back((*i).first);
164			indexContainer_.erase(indexContainer_.begin(), i);
165			break;
166			} else {
167
168	tim	1803	for (int j = (*i).first; j < index; ++j) {
169	tim	1802	result.push_back(j);
170			}
171
172			(*i).first = index;
173			indexContainer_.erase(indexContainer_.begin(), i);
174			break;
175			}
176
177			}
178
179			return result;
180
181			}
182
183	tim	1803	int getMaxIndex() {
184	tim	1802	return maxIndex_;
185			}
186
187			private:
188
189	tim	1803	IndexListContainerIterator internalInsert(int beginIndex, int endIndex) {
190
191	tim	1802	if (beginIndex > endIndex) {
192			std::swap(beginIndex, endIndex);
193			std::cerr << "" << std::endl;
194			}
195
196			if (endIndex > maxIndex_) {
197			std::cerr << "" << std::endl;
198			}
199
200	tim	1803
201	tim	1802	IndexListContainerIterator j;
202
203	tim	1803	IndexListContainerIterator i = indexContainer_.begin();
204			for (; i != indexContainer_.end(); ++i) {
205			if ((*i).first > endIndex) {
206			indexContainer_.insert(i, std::make_pair(beginIndex, endIndex));
207			return --i;
208			} else if ((*i).second < beginIndex) {
209	tim	1802	continue;
210			} else {
211			std::cerr << "" << std::endl;
212			}
213			}
214
215	tim	1803	indexContainer_.push_back(std::make_pair(beginIndex, endIndex));
216			return --indexContainer_.end();
217	tim	1802
218			}
219
220			void merge(IndexListContainerIterator i) {
221			IndexListContainerIterator j;
222	tim	1803
223			//check whether current node can be merged with its previous node
224	tim	1802	if ( i != indexContainer_.begin()) {
225			j = i;
226			--j;
227			if (j != indexContainer_.begin() && (j).second + 1 == (i).first) {
228			(i).first = (j).first;
229			indexContainer_.erase(j);
230			}
231			}
232
233	tim	1803	//check whether current node can be merged with its next node
234	tim	1802	if ( i != indexContainer_.end()) {
235			j = i;
236			++j;
237
238			if (j != indexContainer_.end() && (i).second + 1 == (j).first) {
239			(i).second = (j).second;
240			indexContainer_.erase(j);
241			}
242			}
243
244			}
245	tim	1803	int minIndex_;
246			int maxIndex_;
247			std::list<std::pair<int, int> > indexContainer_;
248	tim	1802	};
249
250
251			/**
252			* @class LocalIndexManager LocalIndexManager.hpp "utils/LocalIndexManager.hpp"
253			* @brief
254			*/
255			class LocalIndexManager {
256			public:
257
258	tim	1803	int getNextAtomIndex() {
259	tim	1802	return atomIndexContainer_.pop();
260			}
261
262	tim	1803	std::vector<int> getAtomIndicesBefore(int index) {
263	tim	1802	return atomIndexContainer_.getIndicesBefore(index);
264			}
265
266	tim	1803	void releaseAtomIndex(int index) {
267	tim	1802	atomIndexContainer_.insert(index);
268			}
269
270	tim	1803	void releaseAtomIndex(int beginIndex, int endIndex) {
271	tim	1802	atomIndexContainer_.insert(beginIndex, endIndex);
272			}
273
274	tim	1803	void releaseAtomIndex(std::vector<int> indices) {
275	tim	1802	atomIndexContainer_.insert(indices);
276			}
277
278	tim	1803	int getNextRigidBodyIndex() {
279	tim	1802	return rigidBodyIndexContainer_.pop();
280			}
281
282	tim	1803	std::vector<int> getRigidBodyIndicesBefore(int index) {
283	tim	1802	return rigidBodyIndexContainer_.getIndicesBefore(index);
284			}
285
286	tim	1803	void releaseRigidBodyIndex(int index) {
287	tim	1802	rigidBodyIndexContainer_.insert(index);
288			}
289
290	tim	1803	void releaseRigidBodyIndex(int beginIndex, int endIndex) {
291	tim	1802	rigidBodyIndexContainer_.insert(beginIndex, endIndex);
292			}
293
294	tim	1803	void releaseRigidBodyIndex(std::vector<int> indices) {
295	tim	1802	rigidBodyIndexContainer_.insert(indices);
296			}
297
298	tim	1803	private:
299	tim	1802
300			IndexListContainer atomIndexContainer_;
301			IndexListContainer rigidBodyIndexContainer_;
302			};
303
304			} //end namespace oopse
305			#endif //UTILS_LOCALINDEXMANAGER_HPP