5 \brief Code of IndexedHeap
7 //============================================================================
8 template <class T, class CT, class IT>
9 std::ostream& operator << (std::ostream& s, const IndexedHeap<T,CT,IT>& t)
12 for (int i=0; i<t.size(); i++) s << t[i] << " " ;
16 //============================================================================
19 //===========================================================
20 template <class T, class CT, class IT>
21 IndexedHeap<T,CT,IT>::IndexedHeap ( const CT& comp, const IT& index )
22 : m_c(&comp), m_i(&index)
24 //===========================================================
27 //===========================================================
28 template <class T, class CT, class IT>
29 void IndexedHeap<T,CT,IT>::set( const CT& comp )
33 //===========================================================
35 //===========================================================
36 template <class T, class CT, class IT>
37 void IndexedHeap<T,CT,IT>::set ( const IT& index )
41 //===========================================================
44 //===========================================================
45 template <class T, class CT, class IT>
46 int IndexedHeap<T,CT,IT>::insert(T t)
50 return upsort(size()-1);
52 //===========================================================
54 //===========================================================
55 template <class T, class CT, class IT>
56 T& IndexedHeap<T,CT,IT>::top()
58 // lglASSERT( size() > 0)
61 //===========================================================
64 //===========================================================
65 template <class T, class CT, class IT>
66 const T& IndexedHeap<T,CT,IT>::top() const
68 // lglASSERT( size() > 0)
71 //===========================================================
73 //===========================================================
74 template <class T, class CT, class IT>
75 T IndexedHeap<T,CT,IT>::remove_top()
77 // lglASSERT( size() > 0 )
90 //============================================================================
94 //============================================================================
95 template <class T, class CT, class IT>
96 T IndexedHeap<T,CT,IT>::remove(int n)
98 // lglASSERT ( (n>=0)&&(n<size()) )
111 //============================================================================
114 //============================================================================
115 template <class T, class CT, class IT>
116 void IndexedHeap<T,CT,IT>::clear()
118 for (typename std::vector<T>::iterator i=m_p.begin(); i!=m_p.end(); ++i)
124 //============================================================================
127 //============================================================================
128 template <class T, class CT, class IT>
129 int IndexedHeap<T,CT,IT>::father( int i) const
133 //============================================================================
135 //============================================================================
136 template <class T, class CT, class IT>
137 int IndexedHeap<T,CT,IT>::rightson( int i) const
141 //============================================================================
143 //============================================================================
144 template <class T, class CT, class IT>
145 int IndexedHeap<T,CT,IT>::leftson( int i) const
149 //============================================================================
151 //============================================================================
152 template <class T, class CT, class IT>
153 void IndexedHeap<T,CT,IT>::swap(int i, int j)
162 //============================================================================
166 //============================================================================
167 template <class T, class CT, class IT>
168 int IndexedHeap<T,CT,IT>::upsort(int i)
170 //if (i==0) return i;
172 while ((i>0)&&(*m_c)(m_p[i],m_p[j]))
180 //============================================================================
183 //============================================================================
184 template <class T, class CT, class IT>
185 int IndexedHeap<T,CT,IT>::downsort(int i)
190 unsigned int ls = leftson(i);
193 bool lc = ((*m_c)(m_p[i],m_p[ls]));
194 unsigned int rs = ls + 1;
196 if (rs<m_p.size()) rc = ((*m_c)(m_p[i],m_p[rs]));
201 if ((*m_c)(m_p[ls],m_p[rs]))
230 //============================================================================
233 //============================================================================
235 //============================================================================