1 /*****************************************************************************
2 * $LastChangedDate: 2011-04-23 21:07:07 -0400 (Sat, 23 Apr 2011) $
3 * @file
4 * @author Jim E. Brooks http://www.palomino3d.org
5 * @brief Helper functions for STL.
6 *//*
7 * LEGAL: COPYRIGHT (C) 2004 JIM E. BROOKS
8 * THIS SOURCE CODE IS RELEASED UNDER THE TERMS
9 * OF THE GNU GENERAL PUBLIC LICENSE VERSION 2 (GPL 2).
10 *****************************************************************************/
11
12 #ifndef BASE_FUNCS_STL_HH
13 #define BASE_FUNCS_STL_HH 1
14
15 #include <list>
16 #include <vector>
17 #include <deque>
18 #include <set>
19 #include <map>
20 #include <algorithm>
21
22 namespace base {
23
24 /*******************************************************************************
25 * A "for each" macro for a STL container.
26 * Recommended since a common typo is "<" or "==" instead of the correct "!=".
27 * Example:
28 * typedef vector<Object> Objects;
29 * FOR_EACH( Objects, mObjects )
30 * {
31 * Object object = *iter;
32 * }
33 *******************************************************************************/
34 #define FOR_EACH( CONTAINER_TYPE, CONTAINER_VAR ) for ( CONTAINER_TYPE::iterator iter = CONTAINER_VAR.begin(); iter != CONTAINER_VAR.end(); ++iter )
35
36 /*******************************************************************************
37 * Helper for correctly writing operator<() for STL container.
38 * bool operator<( const C& a, const C& b )
39 * {
40 * RETURN_LT_TRUE_GT_FALSE( a.x, b.x )
41 * RETURN_LT_TRUE_GT_FALSE( a.y, b.y )
42 * return false; // equal
43 * }
44 * "Effective C++" Item 21 says that a comparison function
45 * should return false for equal values or it will corrupt a set/map.
46 *******************************************************************************/
47 #define RETURN_LT_TRUE_GT_FALSE( X, Y ) \
48 {{ \
49 if ( (X) < (Y) ) return true; \
50 if ( (Y) < (X) ) return false; \
51 }}
52
53 /*******************************************************************************
54 * Get raw C array from STL vector.
55 * &v[0] is a STL idiom.
56 *******************************************************************************/
PTR(std::vector<T> & v)57 template<typename T> T* PTR( std::vector<T>& v ) { return &v[0]; }
CONST_PTR(const std::vector<T> & v)58 template<typename T> const T* CONST_PTR( const std::vector<T>& v ) { return &v[0]; }
59
60 /*******************************************************************************
61 * Expand a sequential STL container if necessary.
62 * Useful before operator[] to ensure container can hold it.
63 *******************************************************************************/
Expand(SEQCONT & seqcont,uint idx)64 template<typename SEQCONT> void Expand( SEQCONT& seqcont, uint idx )
65 {
66 ASSERT2( idx < MAX_ELEMS );
67
68 // Be careful, resize() can implode a container too.
69 if ( UX( idx >= seqcont.size() ) )
70 seqcont.resize( idx + 1 ); // one more than index
71 }
72
73 /*******************************************************************************
74 * @return True if two containers have equal contents.
75 *******************************************************************************/
Compare(const CONTAINER & c1,const CONTAINER & c2)76 template<typename CONTAINER> bool Compare( const CONTAINER& c1, const CONTAINER& c2 )
77 {
78 // Check sizes before calling std::equal() else it could overrun.
79 if ( c1.size() == c2.size() )
80 return std::equal( c1.begin(), c1.end(), c2.begin() );
81 else
82 return false; // different sizes means not equal
83 }
84
85 /*****************************************************************************
86 * @return True if container contains an item.
87 *****************************************************************************/
Find(const std::list<KEY> & container,const KEY & key)88 template<typename KEY> bool Find( const std::list<KEY>& container, const KEY& key ) // STL list
89 {
90 return std::find( container.begin(), container.end(), key ) != container.end();
91 }
92
Find(const std::vector<KEY> & container,const KEY & key)93 template<typename KEY> bool Find( const std::vector<KEY>& container, const KEY& key ) // STL vector
94 {
95 return std::find( container.begin(), container.end(), key ) != container.end();
96 }
97
Find(const std::deque<KEY> & container,const KEY & key)98 template<typename KEY> bool Find( const std::deque<KEY>& container, const KEY& key ) // STL deque
99 {
100 return std::find( container.begin(), container.end(), key ) != container.end();
101 }
102
Find(const std::set<KEY> & container,const KEY & key)103 template<typename KEY> bool Find( const std::set<KEY>& container, const KEY& key ) // STL set
104 {
105 return container.find(key) != container.end();
106 }
107
Find(const std::map<KEY,VAL> & container,const KEY & key)108 template<typename KEY,typename VAL> bool Find( const std::map<KEY,VAL>& container, const KEY& key ) // STL map
109 {
110 return container.find(key) != container.end();
111 }
112
113 /*******************************************************************************
114 * Remove() is a compatible way to remove items from various STL containers.
115 * Does NOT destroy/delete items.
116 *******************************************************************************/
Remove(std::vector<T> & container,const T & item)117 template<typename T> void Remove( std::vector<T>& container, const T& item ) // STL vector
118 {
119 // erase/remove idiom for STL vectors or deques. erase() returns nothing.
120 container.erase( std::remove( container.begin(), container.begin(), item ),
121 container.end() );
122 }
123
Remove(std::deque<T> & container,const T & item)124 template<typename T> void Remove( std::deque<T>& container, const T& item ) // STL deque
125 {
126 container.erase( std::remove( container.begin(), container.begin(), item ),
127 container.end() );
128 }
129
Remove(std::list<T> & container,const T & item)130 template<typename T> void Remove( std::list<T>& container, const T& item ) // STL list
131 {
132 container.remove( item );
133 }
134
Remove(std::set<KEY> & container,const KEY & item)135 template<typename KEY> void Remove( std::set<KEY>& container, const KEY& item ) // STL set
136 {
137 container.erase( item );
138 }
139
Remove(std::map<KEY,VAL> & container,const VAL & item)140 template<typename KEY,typename VAL> void Remove( std::map<KEY,VAL>& container, const VAL& item ) // STL map
141 {
142 container.erase( item );
143 }
144
145 /*****************************************************************************
146 * @return True if two STL containers have duplicates.
147 *****************************************************************************/
IfDuplicate(const CONTAINER & c1,const CONTAINER & c2)148 template<typename CONTAINER> bool IfDuplicate( const CONTAINER& c1, const CONTAINER& c2 )
149 {
150 for ( typename CONTAINER::const_iterator i1 = c1.begin(); i1 != c1.end(); ++i1 )
151 {
152 if ( std::find( c2.begin(), c2.end(), *i1 ) != c2.end() )
153 return true;
154 }
155 return false;
156 }
157
158 } // namespace base
159
160 #endif // BASE_FUNCS_STL_HH
161