From d244f1f9e0b34bc47b1fe25eb266a5cf9cb52f04 Mon Sep 17 00:00:00 2001
From: guigues <guigues>
Date: Mon, 9 Feb 2009 10:09:50 +0000
Subject: [PATCH] *** empty log message ***

---
 src2/creaImageIOIndexedHeap.txx | 235 ++++++++++++++++++++++++++++++++
 1 file changed, 235 insertions(+)
 create mode 100644 src2/creaImageIOIndexedHeap.txx

diff --git a/src2/creaImageIOIndexedHeap.txx b/src2/creaImageIOIndexedHeap.txx
new file mode 100644
index 0000000..b5b5753
--- /dev/null
+++ b/src2/creaImageIOIndexedHeap.txx
@@ -0,0 +1,235 @@
+/* 
+
+*/
+/*! \file 
+  \brief Code of IndexedHeap
+*/
+//============================================================================
+template <class T, class CT, class IT>
+std::ostream& operator << (std::ostream& s, const IndexedHeap<T,CT,IT>& t)
+{
+  s << "[";
+  for (int i=0; i<t.size(); i++) s << t[i] << " "  ;
+  s << "]";
+  return s;
+}
+//============================================================================
+
+
+//===========================================================
+template <class T, class CT, class IT>
+IndexedHeap<T,CT,IT>::IndexedHeap ( const CT& comp, const IT& index ) 
+  : m_c(&comp), m_i(&index) 
+{}
+//===========================================================
+
+
+//===========================================================
+template <class T, class CT, class IT>
+void IndexedHeap<T,CT,IT>::set( const CT& comp ) 
+{ 
+  m_c = &comp; 
+}
+//===========================================================
+
+//===========================================================
+template <class T, class CT, class IT>
+void IndexedHeap<T,CT,IT>::set ( const IT& index ) 
+{ 
+  m_i = &index; 
+}
+//===========================================================
+
+
+//===========================================================
+template <class T, class CT, class IT>
+int IndexedHeap<T,CT,IT>::insert(T t)
+{
+  m_p.push_back(t);
+  (*m_i)(t) = size()-1;
+  return upsort(size()-1);
+}
+//===========================================================
+
+//===========================================================
+template <class T, class CT, class IT>
+T& IndexedHeap<T,CT,IT>::top()
+{
+  //  lglASSERT( size() > 0)
+    return m_p.front();
+}
+//===========================================================
+
+
+//===========================================================
+template <class T, class CT, class IT>
+const T& IndexedHeap<T,CT,IT>::top() const
+{
+  //  lglASSERT( size() > 0)
+    return m_p.front();
+}
+//===========================================================
+
+//===========================================================
+template <class T, class CT, class IT>
+T IndexedHeap<T,CT,IT>::remove_top()
+{
+  //  lglASSERT( size() > 0 ) 
+    T f(m_p[0]);
+  (*m_i)(f) = -1;
+  T last = m_p.back();
+  m_p.pop_back();
+  if (m_p.size()>0) 
+    {
+    m_p[0] = last;
+    (*m_i)(last) = 0;
+    downsort(0);
+  }
+  return f;
+}
+//============================================================================
+
+
+
+//============================================================================
+template <class T, class CT, class IT>
+T IndexedHeap<T,CT,IT>::remove(int n)
+{
+  //  lglASSERT ( (n>=0)&&(n<size()) ) 
+    T f(m_p[n]);
+  (*m_i)(f) = -1;
+  T last = m_p.back();
+  m_p.pop_back();
+  if (m_p.size()>0) 
+    {
+    m_p[n] = last;
+    (*m_i)(last) = n;
+    downsort(n);
+  }
+  return f;
+}
+//============================================================================
+
+
+//============================================================================
+template <class T, class CT, class IT>
+void IndexedHeap<T,CT,IT>::clear()
+{
+  for (typename std::vector<T>::iterator i=m_p.begin(); i!=m_p.end(); ++i) 
+    { 
+      (*m_i)(*i)=-1; 
+    }
+  m_p.clear();
+}
+//============================================================================
+
+
+//============================================================================
+template <class T, class CT, class IT>
+int  IndexedHeap<T,CT,IT>::father( int  i) const
+{
+  return ((i-1)/2);
+}
+//============================================================================
+
+//============================================================================
+template <class T, class CT, class IT>
+int  IndexedHeap<T,CT,IT>::rightson( int  i) const
+{ 
+  return (i*2+2);
+}
+//============================================================================
+
+//============================================================================
+template <class T, class CT, class IT>
+int  IndexedHeap<T,CT,IT>::leftson( int  i) const
+{ 
+  return (i*2+1);
+}
+//============================================================================
+
+//============================================================================
+template <class T, class CT, class IT>
+void IndexedHeap<T,CT,IT>::swap(int i, int j)
+{
+  T tmp = m_p[i];
+  m_p[i] = m_p[j];
+  m_p[j] = tmp;
+  // update indices  
+  (*m_i)(m_p[i]) = i;
+  (*m_i)(m_p[j]) = j;
+}
+//============================================================================
+
+
+
+//============================================================================
+template <class T, class CT, class IT>
+int  IndexedHeap<T,CT,IT>::upsort(int  i)
+{
+  //if (i==0) return i;
+  int  j = father(i);
+  while ((i>0)&&(*m_c)(m_p[i],m_p[j])) 
+    {
+    swap(i,j);
+    i = j;
+    j = father(j);
+  }	
+  return i;
+}
+//============================================================================
+
+
+//============================================================================
+template <class T, class CT, class IT>
+int  IndexedHeap<T,CT,IT>::downsort(int  i)
+{
+  do 
+    {
+      
+      unsigned int  ls = leftson(i);
+      if (ls<m_p.size()) 
+	{
+      bool lc = ((*m_c)(m_p[i],m_p[ls]));
+      unsigned int  rs = ls + 1;
+      bool rc = true;
+      if (rs<m_p.size()) rc = ((*m_c)(m_p[i],m_p[rs]));
+      if  ( !lc ) 
+	{ 
+	if ( !rc ) 
+	  { 
+	  if ((*m_c)(m_p[ls],m_p[rs])) 
+	    { 
+	    swap(i,ls);
+	    i = ls;
+	  }
+	  else 
+	    { 
+	    swap(i,rs);
+	    i = rs;
+	  }
+	}
+	else 
+	  {
+	  swap(i,ls);
+	  i = ls;
+	}
+      }
+      else if ( !rc ) 
+	{ 
+	swap(i,rs);
+	i = rs;
+      }
+      else return i;
+    } 
+    else return i;
+  }
+  while (true);
+  return i;
+}
+//============================================================================
+
+
+//============================================================================
+// EOF
+//============================================================================
-- 
2.45.1