Synchronize with trunk

[disorder] / lib / heap.h

diff --git a/lib/heap.h b/lib/heap.h
index 56821bf0b820fb0b70499281d27f27aa879630b9..b5a8930818c0048dd011337f37129d197b56954f 100644 (file)
--- a/lib/heap.h
+++ b/lib/heap.h
@@ -1,27 +1,27 @@
 /*
  * This file is part of DisOrder.
 /*
  * This file is part of DisOrder.

- * Copyright (C) 2007 Richard Kettlewell
+ * Copyright (C) 2007, 2008 Richard Kettlewell

  *
  *

- * This program is free software; you can redistribute it and/or modify
+ * This program is free software: you can redistribute it and/or modify

  * it under the terms of the GNU General Public License as published by
  * it under the terms of the GNU General Public License as published by

- * the Free Software Foundation; either version 2 of the License, or
+ * the Free Software Foundation, either version 3 of the License, or

  * (at your option) any later version.
  * (at your option) any later version.

- *
- * 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
- * General Public License for more details.
- *
+ * 
+ * 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 General Public License for more details.
+ * 

  * You should have received a copy of the GNU General Public License
  * You should have received a copy of the GNU 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
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.

  */
 /** @file lib/heap.h @brief Binary heap template */
 
 #ifndef HEAP_H
 #define HEAP_H
 
  */
 /** @file lib/heap.h @brief Binary heap template */
 
 #ifndef HEAP_H
 #define HEAP_H
 

+#include "vector.h"
+

 /** @brief Binary heap template.
  * @param NAME name of type to define
  * @param ETYPE element type
 /** @brief Binary heap template.
  * @param NAME name of type to define
  * @param ETYPE element type


@@ -85,53 +85,60 @@
   }                                                                     \
                                                                         \
   static inline NAME##_element NAME##_first(struct NAME *heap) {        \
   }                                                                     \
                                                                         \
   static inline NAME##_element NAME##_first(struct NAME *heap) {        \

-    assert(heap->nvec > 0);                                             \
+    assert(heap->nvec > 0 && "_first");                                 \

     return heap->vec[0];                                                \
   }                                                                     \
                                                                         \
     return heap->vec[0];                                                \
   }                                                                     \
                                                                         \

-  static void NAME##_insert(struct NAME *heap, NAME##_element elt) {    \
-    int n = heap->nvec;                                                 \
-    NAME##_append(heap, elt);                                           \
-    while(n > 0) {                                                      \
-      const int p = (n-1)/2;                                            \
-      if(!LT(heap->vec[n],heap->vec[p]))                                \
-        break;                                                          \
-      else {                                                            \
-        const NAME##_element t = heap->vec[n];                          \
-        heap->vec[n] = heap->vec[p];                                    \
-        heap->vec[p] = t;                                               \
-        n = p;                                                          \
-      }                                                                 \
-    }                                                                   \
-  }                                                                     \
-                                                                        \
-  static NAME##_element NAME##_remove(struct NAME *heap) {              \
-    int n = 0;                                                          \
-    NAME##_element r;                                                   \
-                                                                        \
-    assert(heap->nvec > 0);                                             \
-    r = heap->vec[0];                                                   \
-    heap->vec[0] = heap->vec[--heap->nvec];                             \
-    while(2 * n + 1 < heap->nvec) {                                     \
-      int a = 2 * n + 1;                                                \
-      int b = 2 * n + 2;                                                \
-                                                                        \
-      if(b < heap->nvec && LT(heap->vec[b],heap->vec[a])) {             \
-        ++a;                                                            \
-        --b;                                                            \
-      }                                                                 \
-      if(LT(heap->vec[a], heap->vec[n])) {                              \
-        const NAME##_element t = heap->vec[n];                          \
-        heap->vec[n] = heap->vec[a];                                    \
-        heap->vec[a] = t;                                               \
-        n = a;                                                          \
-      } else                                                            \
-        break;                                                          \
-    }                                                                   \
-    return r;                                                           \
-  }                                                                     \
+  void NAME##_insert(struct NAME *heap, NAME##_element elt);            \
+  NAME##_element NAME##_remove(struct NAME *heap);                      \

                                                                         \
   struct heap_swallow_semicolon
                                                                         \
   struct heap_swallow_semicolon

+
+/** @brief External-linkage definitions for @ref HEAP_TYPE */
+#define HEAP_DEFINE(NAME, ETYPE, LT)                            \
+  void NAME##_insert(struct NAME *heap, NAME##_element elt) {   \
+    int n = heap->nvec;                                         \
+    NAME##_append(heap, elt);                                   \
+    while(n > 0) {                                              \
+      const int p = (n-1)/2;                                    \
+      if(!LT(heap->vec[n],heap->vec[p]))                        \
+        break;                                                  \
+      else {                                                    \
+        const NAME##_element t = heap->vec[n];                  \
+        heap->vec[n] = heap->vec[p];                            \
+        heap->vec[p] = t;                                       \
+        n = p;                                                  \
+      }                                                         \
+    }                                                           \
+  }                                                             \
+                                                                \
+  NAME##_element NAME##_remove(struct NAME *heap) {             \
+    int n = 0;                                                  \
+    NAME##_element r;                                           \
+                                                                \
+    assert(heap->nvec > 0 && "_remove");                        \
+    r = heap->vec[0];                                           \
+    heap->vec[0] = heap->vec[--heap->nvec];                     \
+    while(2 * n + 1 < heap->nvec) {                             \
+      int a = 2 * n + 1;                                        \
+      int b = 2 * n + 2;                                        \
+                                                                \
+      if(b < heap->nvec && LT(heap->vec[b],heap->vec[a])) {     \
+        ++a;                                                    \
+        --b;                                                    \
+      }                                                         \
+      if(LT(heap->vec[a], heap->vec[n])) {                      \
+        const NAME##_element t = heap->vec[n];                  \
+        heap->vec[n] = heap->vec[a];                            \
+        heap->vec[a] = t;                                       \
+        n = a;                                                  \
+      } else                                                    \
+        break;                                                  \
+    }                                                           \
+    return r;                                                   \
+  }                                                             \
+                                                                \
+  struct heap_swallow_semicolon                                 \

   
 
 #endif /* PQUEUE_H */
   
 
 #endif /* PQUEUE_H */