src/utils/LocalIndexManager.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 <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;
            int endIndex;

            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:	1841
Committed:	Fri Dec 3 17:59:45 2004 UTC (20 years, 10 months ago) by tim
File size:	9110 byte(s)
Log Message:	begin to fix bugs
#	User	Rev	Content
1	tim	1802	/*
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 <iostream>
37			#include <cassert>
38			#include <list>
39			#include <utility>
40
41			namespace oopse {
42
43			/**
44			* @class IndexListContainer
45			* @brief
46			* @todo documentation
47			*/
48			class IndexListContainer{
49			public:
50	tim	1803	static const int MAX_INTEGER = 2147483647;
51			typedef std::list<std::pair<int, int> >::iterator IndexListContainerIterator;
52	tim	1802
53
54	tim	1803	IndexListContainer(int minIndex = 0, int maxIndex = MAX_INTEGER)
55	tim	1802	:minIndex_(minIndex), maxIndex_(maxIndex) {
56
57			indexContainer_.push_back(std::make_pair(minIndex, maxIndex));
58			}
59
60	tim	1803	int pop() {
61	tim	1802
62			if (indexContainer_.empty()) {
63			std::cerr << "" << std::endl;
64			}
65
66			IndexListContainerIterator i = indexContainer_.begin();
67	tim	1803	int result;
68	tim	1802
69			result = indexContainer_.front().first;
70
71			if (indexContainer_.front().first == indexContainer_.front().second) {
72			indexContainer_.pop_front();
73			} else if (indexContainer_.front().first < indexContainer_.front().second) {
74	tim	1841	++indexContainer_.front().first;
75	tim	1802	} else {
76			std::cerr << "" << std::endl;
77			}
78
79			return result;
80			}
81
82
83			/**
84			*
85			*/
86	tim	1803	void insert(int index) {
87			IndexListContainerIterator insertPos = internalInsert(index, index);
88	tim	1802	merge(insertPos);
89			}
90
91			/**
92			* Reclaims an index range
93			* @param beginIndex
94			* @param endIndex
95			*/
96	tim	1803	void insert(int beginIndex, int endIndex) {
97			IndexListContainerIterator insertPos = internalInsert(beginIndex, endIndex);
98	tim	1802	merge(insertPos);
99			}
100
101			/**
102			* Reclaims an index array.
103			* @param indices
104			*/
105	tim	1803	void insert(std::vector<int>& indices){
106	tim	1802
107			if (indices.empty()) {
108			return;
109			}
110
111			std::sort(indices.begin(), indices.end());
112	tim	1803	std::unique(indices.begin(), indices.end());
113	tim	1802
114	tim	1803	std::vector<int>::iterator i;
115	tim	1802	IndexListContainerIterator insertPos;
116	tim	1803	int beginIndex;
117			int endIndex;
118	tim	1802
119			beginIndex = indices[0];
120
121			for ( i = indices.begin() + 1 ; i != indices.end(); ++i) {
122			if (i != (i -1) + 1) {
123	tim	1803	insert(beginIndex, *(i-1));
124	tim	1802	beginIndex = *i;
125			}
126			}
127
128
129			}
130
131	tim	1803	std::vector<int> getIndicesBefore(int index) {
132			std::vector<int> result;
133	tim	1802	IndexListContainerIterator i;
134
135			for(i = indexContainer_.begin(); i != indexContainer_.end(); ++i) {
136			if ((*i).first > index) {
137	tim	1803	//we locate the node whose minimum index is greater that index
138			indexContainer_.erase(indexContainer_.begin(), i);
139	tim	1802	break;
140			} else if ((*i).second < index) {
141	tim	1803	//The biggest index current node hold is less than the index we want
142			for (int j = (i).first; j <= (i).second; ++j) {
143	tim	1802	result.push_back(j);
144			}
145			continue;
146			} else if ((i).first == (i).second) {
147	tim	1803	//the index happen to equal to a node which only contains one index
148	tim	1802	result.push_back((*i).first);
149			indexContainer_.erase(indexContainer_.begin(), i);
150			break;
151			} else {
152
153	tim	1803	for (int j = (*i).first; j < index; ++j) {
154	tim	1802	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	tim	1803	int getMaxIndex() {
169	tim	1802	return maxIndex_;
170			}
171
172			private:
173
174	tim	1803	IndexListContainerIterator internalInsert(int beginIndex, int endIndex) {
175
176	tim	1802	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	tim	1803
186	tim	1802	IndexListContainerIterator j;
187
188	tim	1803	IndexListContainerIterator i = indexContainer_.begin();
189			for (; i != indexContainer_.end(); ++i) {
190			if ((*i).first > endIndex) {
191			indexContainer_.insert(i, std::make_pair(beginIndex, endIndex));
192			return --i;
193			} else if ((*i).second < beginIndex) {
194	tim	1802	continue;
195			} else {
196			std::cerr << "" << std::endl;
197			}
198			}
199
200	tim	1803	indexContainer_.push_back(std::make_pair(beginIndex, endIndex));
201			return --indexContainer_.end();
202	tim	1802
203			}
204
205			void merge(IndexListContainerIterator i) {
206			IndexListContainerIterator j;
207	tim	1803
208			//check whether current node can be merged with its previous node
209	tim	1802	if ( i != indexContainer_.begin()) {
210			j = i;
211			--j;
212			if (j != indexContainer_.begin() && (j).second + 1 == (i).first) {
213			(i).first = (j).first;
214			indexContainer_.erase(j);
215			}
216			}
217
218	tim	1803	//check whether current node can be merged with its next node
219	tim	1802	if ( i != indexContainer_.end()) {
220			j = i;
221			++j;
222
223			if (j != indexContainer_.end() && (i).second + 1 == (j).first) {
224			(i).second = (j).second;
225			indexContainer_.erase(j);
226			}
227			}
228
229			}
230	tim	1803	int minIndex_;
231			int maxIndex_;
232			std::list<std::pair<int, int> > indexContainer_;
233	tim	1802	};
234
235
236			/**
237			* @class LocalIndexManager LocalIndexManager.hpp "utils/LocalIndexManager.hpp"
238			* @brief
239			*/
240			class LocalIndexManager {
241			public:
242
243	tim	1803	int getNextAtomIndex() {
244	tim	1802	return atomIndexContainer_.pop();
245			}
246
247	tim	1803	std::vector<int> getAtomIndicesBefore(int index) {
248	tim	1802	return atomIndexContainer_.getIndicesBefore(index);
249			}
250
251	tim	1803	void releaseAtomIndex(int index) {
252	tim	1802	atomIndexContainer_.insert(index);
253			}
254
255	tim	1803	void releaseAtomIndex(int beginIndex, int endIndex) {
256	tim	1802	atomIndexContainer_.insert(beginIndex, endIndex);
257			}
258
259	tim	1803	void releaseAtomIndex(std::vector<int> indices) {
260	tim	1802	atomIndexContainer_.insert(indices);
261			}
262
263	tim	1803	int getNextRigidBodyIndex() {
264	tim	1802	return rigidBodyIndexContainer_.pop();
265			}
266
267	tim	1803	std::vector<int> getRigidBodyIndicesBefore(int index) {
268	tim	1802	return rigidBodyIndexContainer_.getIndicesBefore(index);
269			}
270
271	tim	1803	void releaseRigidBodyIndex(int index) {
272	tim	1802	rigidBodyIndexContainer_.insert(index);
273			}
274
275	tim	1803	void releaseRigidBodyIndex(int beginIndex, int endIndex) {
276	tim	1802	rigidBodyIndexContainer_.insert(beginIndex, endIndex);
277			}
278
279	tim	1803	void releaseRigidBodyIndex(std::vector<int> indices) {
280	tim	1802	rigidBodyIndexContainer_.insert(indices);
281			}
282
283	tim	1803	private:
284	tim	1802
285			IndexListContainer atomIndexContainer_;
286			IndexListContainer rigidBodyIndexContainer_;
287			};
288
289			} //end namespace oopse
290			#endif //UTILS_LOCALINDEXMANAGER_HPP