add minisat and TNM sequential solvers in sat problem
authorYanhua YanhuaSunLaptop <yanhuasun@yanhua-suns-macbook-pro.local>
Mon, 29 Mar 2010 03:05:44 +0000 (22:05 -0500)
committerYanhua YanhuaSunLaptop <yanhuasun@yanhua-suns-macbook-pro.local>
Mon, 29 Mar 2010 03:05:44 +0000 (22:05 -0500)
16 files changed:
examples/charm++/satisfiability/TNM/TNM.C [new file with mode: 0644]
examples/charm++/satisfiability/TNM/TNM.h [new file with mode: 0644]
examples/charm++/satisfiability/TNM/TNM.pdf [new file with mode: 0644]
examples/charm++/satisfiability/TNM/adaptnoisebis1at5.C [new file with mode: 0644]
examples/charm++/satisfiability/TNM/inputbis.C [new file with mode: 0644]
examples/charm++/satisfiability/minisat/Solver.C [new file with mode: 0644]
examples/charm++/satisfiability/minisat/Solver.h [new file with mode: 0644]
examples/charm++/satisfiability/minisat/SolverTypes.h [new file with mode: 0644]
examples/charm++/satisfiability/minisat/mtl/Alg.h [new file with mode: 0644]
examples/charm++/satisfiability/minisat/mtl/BasicHeap.h [new file with mode: 0644]
examples/charm++/satisfiability/minisat/mtl/BoxedVec.h [new file with mode: 0644]
examples/charm++/satisfiability/minisat/mtl/Map.h [new file with mode: 0644]
examples/charm++/satisfiability/minisat/mtl/Queue.h [new file with mode: 0644]
examples/charm++/satisfiability/minisat/mtl/Sort.h [new file with mode: 0644]
examples/charm++/satisfiability/minisat/mtl/Vec.h [new file with mode: 0644]
examples/charm++/satisfiability/minisat/mtl/minisatHeap.h [new file with mode: 0644]

diff --git a/examples/charm++/satisfiability/TNM/TNM.C b/examples/charm++/satisfiability/TNM/TNM.C
new file mode 100644 (file)
index 0000000..d96ec79
--- /dev/null
@@ -0,0 +1,1318 @@
+/* 
+Copyright (C) 2009
+Wanxia WEI (weiwanxia@gmail.com), 
+Chumin LI (chu-min.li@u-picardie.fr)
+
+   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
+   the Free Software Foundation; either version 2 of the License, or
+   (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.
+
+   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
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/time.h>
+#include <time.h>
+
+#include <sys/times.h>
+#include <sys/types.h>
+#include <limits.h>
+
+#include "TNM.h"
+
+#include <vector>
+
+using namespace std;
+
+typedef signed int my_type;
+typedef unsigned int my_unsigned_type;
+
+//#define lookahead_length 30
+//int decreasing_vars_stack1[lookahead_length+1];
+#define WORD_LENGTH 100 
+#define TRUE 1
+#define FALSE 0
+#define NONE -1
+#define SATISFIABLE 2
+#define walk_satisfiable() (MY_CLAUSE_STACK_fill_pointer == 0)
+
+#define WEIGTH 4
+#define T 10
+
+/* the tables of variables and clauses are statically allocated. Modify the 
+   parameters tab_variable_size and tab_clause_size before compilation if 
+   necessary */
+
+#define tab_variable_size  1000000
+#define tab_clause_size 5000000
+
+#define tab_unitclause_size \
+ ((tab_clause_size/4<2000) ? 2000 : tab_clause_size/4)
+#define my_tab_variable_size \
+ ((tab_variable_size/2<1000) ? 1000 : tab_variable_size/2)
+#define my_tab_clause_size \
+ ((tab_clause_size/2<2000) ? 2000 : tab_clause_size/2)
+#define my_tab_unitclause_size \
+ ((tab_unitclause_size/2<1000) ? 1000 : tab_unitclause_size/2)
+#define tab_literal_size 2*tab_variable_size
+#define double_tab_clause_size 2*tab_clause_size
+#define positive(literal) literal<NB_VAR
+#define negative(literal) literal>=NB_VAR
+#define get_var_from_lit(negative_literal) negative_literal-NB_VAR
+#define RESOLVANT_LENGTH 3
+#define RESOLVANT_SEARCH_THRESHOLD 5000
+#define complement(lit1, lit2) \
+ ((lit1<lit2) ? lit2-lit1 == NB_VAR : lit1-lit2 == NB_VAR)
+
+#define inverse_signe(signe) \
+ (signe == POSITIVE) ? NEGATIVE : POSITIVE
+#define unsat(val) (val==0)?"UNS":"SAT"
+#define pop(stack) stack[--stack ## _fill_pointer]
+#define push(item, stack) stack[stack ## _fill_pointer++] = item
+#define satisfiable() CLAUSE_STACK_fill_pointer == NB_CLAUSE
+
+#define NEGATIVE 0
+#define POSITIVE 1
+#define PASSIVE 0
+#define ACTIVE 1
+#define INUTILE 2
+#define MAX_NODE_NUMBER 6000
+struct node {
+  int clause;
+  struct node *next;
+};
+
+int *neg_in[tab_variable_size];
+int *pos_in[tab_variable_size];
+int neg_nb[tab_variable_size];
+int pos_nb[tab_variable_size];
+my_type var_current_value[tab_variable_size];
+my_type var_rest_value[tab_variable_size];
+my_type var_state[tab_variable_size];
+
+
+float reduce_if_negative_nb[tab_variable_size];
+float reduce_if_positive_nb[tab_variable_size];
+
+int *sat[tab_clause_size];
+int *var_sign[tab_clause_size];
+my_type clause_state[tab_clause_size];
+my_type clause_length[tab_clause_size];
+int most_recent[tab_clause_size];
+int most_recent_count[tab_clause_size];
+
+int VARIABLE_STACK_fill_pointer = 0;
+int CLAUSE_STACK_fill_pointer = 0;
+int UNITCLAUSE_STACK_fill_pointer = 0;
+int MANAGEDCLAUSE_STACK_fill_pointer = 0;
+
+
+int VARIABLE_STACK[tab_variable_size];
+int CLAUSE_STACK[tab_clause_size];
+int UNITCLAUSE_STACK[tab_unitclause_size];
+int MANAGEDCLAUSE_STACK[tab_clause_size];
+//int TESTED_VAR_STACK[tab_variable_size];
+//int TESTED_VAR_STACK_fill_pointer=0;
+
+
+int tab_variable_nb_unit[2*tab_variable_size]={0};
+int clause_possible[tab_clause_size]={0};
+//int SAVED_VAR_VARIABLE_STACK[tab_variable_size];
+int SAVED_VAR_VARIABLE_STACK_fill_pointer = 0;
+//int SAVED_DEB_CLAUSE_STACK[tab_variable_size];
+int SAVED_DEB_CLAUSE_STACK_fill_pointer;
+//int SAVED_FIN_CLAUSE_STACK[tab_variable_size];
+int SAVED_FIN_CLAUSE_STACK_fill_pointer;
+//int SAVED_VARIABLE_STACK[tab_variable_size];
+int SAVED_VARIABLE_STACK_fill_pointer = 0;
+//int SAVED_MANAGEDCLAUSE_STACK[tab_clause_size];
+int SAVED_MANAGEDCLAUSE_STACK_fill_pointer = 0;
+//int SAVED_CLAUSE_STACK[tab_clause_size];
+int SAVED_CLAUSE_STACK_fill_pointer = 0;
+int PREVIOUS_MANAGEDCLAUSE_STACK_fill_pointer = 0;
+
+int CPT=0;
+
+int NB_VAR;
+int NB_ACTIVE_VAR;
+int NB_CLAUSE;
+int INIT_NB_CLAUSE;
+my_type R = 3;
+
+double counter[tab_variable_size];
+double max_counter, min_counter, ave_counter, old_ave_counter;
+int global_j;
+
+double Interval, Adjustment, Sigma;
+double coefficient_for_prm;
+int Intensity;
+
+long NB_UNIT=1, NB_MONO=0, NB_BRANCHE=0, NB_BACK = 0;
+
+#define double_tab_clause_size 2*tab_clause_size
+
+struct var_node {
+  int var;
+  int weight;
+  struct var_node *next;
+};
+
+#define VAR_NODES1_nb 6
+int VAR_NODES1_index=0;
+struct var_node VAR_NODES1[10*VAR_NODES1_nb];
+struct var_node *VAR_FOR_TEST1=NULL;
+
+struct var_node *allocate_var_node1() {
+  return &VAR_NODES1[VAR_NODES1_index++];
+}
+
+int test_flag[tab_variable_size];
+
+int MAX_REDUCED;
+int T_SEUIL;
+
+unsigned int SEED;
+int SEED_FLAG=FALSE, BUILD_FLAG=TRUE;
+char saved_input_file[WORD_LENGTH];
+char *INPUT_FILE;
+
+unsigned long IMPLIED_LIT_FLAG=0;
+int IMPLIED_LIT_STACK_fill_pointer=0;
+int IMPLIED_LIT_STACK[tab_variable_size];
+unsigned long LIT_IMPLIED[tab_variable_size]={0};
+
+long NB_SECOND_SEARCH=0;
+long NB_SECOND_FIXED = 0;
+
+void remove_clauses(int var) {
+  register int clause;
+  register int *clauses;
+  if (var_current_value[var] == POSITIVE) clauses = pos_in[var];
+  else clauses = neg_in[var];
+  for(clause=*clauses; clause!=NONE; clause=*(++clauses)) {
+    if (clause_state[clause] == ACTIVE) {
+      clause_state[clause] = PASSIVE;
+      push(clause, CLAUSE_STACK);
+    }
+  }
+}
+
+int manage_clauses(int var) {
+  register int clause;
+  register int *clauses;
+  if (var_current_value[var] == POSITIVE) clauses = neg_in[var];
+  else clauses = pos_in[var];
+  for(clause=*clauses; clause!=NONE; clause=*(++clauses)) {
+    if (clause_state[clause] == ACTIVE) {
+      switch (clause_length[clause]) {
+      case 1: return FALSE;
+      case 2: push(clause, UNITCLAUSE_STACK);
+       push(clause, MANAGEDCLAUSE_STACK);
+       clause_length[clause]--; break;
+      default: clause_possible[clause] = 1;
+       clause_length[clause]--;
+       push(clause, MANAGEDCLAUSE_STACK);
+      }
+    }
+  }
+  return TRUE;
+}
+void print_values(int nb_var) {
+  FILE* fp_out;
+  int i;
+  fp_out = fopen("satx.sol", "w");
+  for (i=0; i<nb_var; i++) {
+    if (var_current_value[i] == 1) 
+      fprintf(fp_out, "%d ", i+1);
+    else
+      fprintf(fp_out, "%d ", 0-i-1);
+  }
+  fprintf(fp_out, "\n");
+  fclose(fp_out);                      
+} 
+#include "inputbis.C"
+
+int verify_solution() {
+  int i, var, *vars_signs, clause_truth,cpt;
+
+  for (i=0; i<NB_CLAUSE; i++) {
+    clause_truth = FALSE;
+    vars_signs = var_sign[i];
+    for(var=*vars_signs; var!=NONE; var=*(vars_signs+=2))
+      if (*(vars_signs+1) == var_current_value[var] ) {
+       clause_truth = TRUE;
+       break;
+      }
+    if (clause_truth == FALSE) return FALSE;
+  }
+  return TRUE;
+}
+
+long NB_SEARCH = 0; long NB_FIXED = 0;
+  
+int unitclause_process() {
+  int  i, unitclause, var, *vars_signs, unitclause_position,cpt;
+  
+  for (unitclause_position = 0; 
+       unitclause_position < UNITCLAUSE_STACK_fill_pointer;
+       unitclause_position++) {
+    unitclause = UNITCLAUSE_STACK[unitclause_position];
+    if (clause_state[unitclause] == ACTIVE) {
+      NB_UNIT++;
+      vars_signs = var_sign[unitclause];
+      for(var=*vars_signs; var!=NONE; var=*(vars_signs+=2)) {
+       if (var_state[var] == ACTIVE ){
+         var_current_value[var] = *(vars_signs+1);
+         var_rest_value[var] = NONE;
+         if (manage_clauses(var)==TRUE) {
+           var_state[var] = PASSIVE;
+           push(var, VARIABLE_STACK);
+           remove_clauses(var);
+           break;
+         }
+         else {
+           return NONE;
+         }
+       }
+      }
+    }     
+  }
+  UNITCLAUSE_STACK_fill_pointer = 0;
+  return TRUE;
+}
+int PREVIOUS_UNITCLAUSE_STACK_fill_pointer = 0;
+
+/*
+my_type build(int build_flag, char* input_file) {
+  if (build_flag==TRUE)
+    return build_simple_sat_instance(input_file);
+  else return build_simple_sat_instance(input_file);
+}
+*/
+
+
+#define DECREASING 1
+#define INCREASING 2
+#define PLATEAU 0
+int var_count[tab_variable_size]={1};
+int neibor_stack[tab_variable_size];
+int neibor_stack_fill_pointer=0;
+int **neibor_relations[tab_variable_size];
+int *neibor[tab_variable_size];
+int score[tab_variable_size];
+int make[tab_variable_size];
+int break_value[tab_variable_size];
+int tmp_score[tab_variable_size];
+int decreasing_vars_stack[tab_variable_size];
+int decreasing_vars_stack_fill_pointer=0;
+int tabu[tab_variable_size]={FALSE};
+int tabu_stack[tab_variable_size];
+int tabu_stack_fill_pointer=0;
+int tabu_list[tab_variable_size];
+int tendance[tab_variable_size];
+int MY_CLAUSE_STACK_fill_pointer=0;
+int MY_CLAUSE_STACK[tab_clause_size];
+int nb_lit_true[tab_clause_size];
+int clause_truth[tab_clause_size];
+int dommage_if_flip[tab_variable_size];
+int zerodommage[tab_variable_size];
+int zerodommage_vars_stack[tab_variable_size];
+int zerodommage_vars_stack_fill_pointer=0;
+int flip_time[tab_variable_size];
+int enter_stack_time[tab_variable_size];
+int walk_time[tab_variable_size];
+int MAXTRIES=10000;
+int MAXSTEPS=2000000000;
+int NOISE=50;
+int NOISE1=50;
+int LNOISE=5;
+int saved_var_current_value[tab_variable_size];
+
+int index_in_MY_CLAUSE_STACK[tab_clause_size];
+
+void clause_value() {
+  int clause, var, *vars_signs, nb_true;
+   
+  MY_CLAUSE_STACK_fill_pointer=0;  
+  for (clause=0; clause<NB_CLAUSE; clause++) {
+    nb_true=0;
+    vars_signs = var_sign[clause];
+    for(var=*vars_signs; var!=NONE; var=*(vars_signs+=2))
+      if (var_current_value[var]==*(vars_signs+1))  
+       nb_true++;        
+    nb_lit_true[clause]=nb_true;
+    if (nb_true ==0 ) {
+      clause_truth[clause]=FALSE;
+      //push(clause, MY_CLAUSE_STACK);
+      index_in_MY_CLAUSE_STACK[clause]=MY_CLAUSE_STACK_fill_pointer;
+      push(clause, MY_CLAUSE_STACK);
+    }
+    else
+      clause_truth[clause]=TRUE;    
+  } 
+}
+
+void pass(int the_var, int *clauses) {
+  int clause, var, *vars_signs;
+  for(clause=*clauses; clause!=NONE; clause=*(++clauses)) {
+    if (clause_state[clause] == ACTIVE) {
+      vars_signs = var_sign[clause];
+      for(var=*vars_signs; var!=NONE; var=*(vars_signs+=2)) {
+       if (var_state[var]==ACTIVE && var != the_var) {
+         if (var_count[var]==1) push(var, neibor_stack);
+         // nb of cells for other variables (than var and the_var: length-2)
+         //and a sign for dxdy and a separator from the next clauses
+         var_count[var]+=2*(clause_length[clause]-1);
+       }
+      }
+    }
+  }
+}
+
+int *build_neibor_relation(int var, int neibor_var, 
+                         int *neibor_relations, int *clauses) {
+  int i, clause, var1, *vars_signs, present, *relations, sign1, sign2;
+
+  for(clause=*clauses; clause!=NONE; clause=*(++clauses)) {
+    if (clause_state[clause] == ACTIVE) {
+      vars_signs = var_sign[clause];
+      present=FALSE;
+      for(var1=*vars_signs; var1!=NONE; var1=*(vars_signs+=2)) {
+       if (var1==neibor_var) {present=TRUE; break;}
+      }
+      if (present==TRUE) {
+       relations=neibor_relations; neibor_relations++;
+       vars_signs = var_sign[clause];
+       for(var1=*vars_signs; var1!=NONE; var1=*(vars_signs+=2)) {
+         if (var_state[var1]==ACTIVE) {
+           if (var1==var) sign1=*(vars_signs+1);
+           else if (var1==neibor_var) sign2=*(vars_signs+1);
+           else {
+             *neibor_relations=var1; 
+             *(neibor_relations+1)=*(vars_signs+1);
+             neibor_relations+=2;
+           }
+         }
+       }
+       *relations=(sign1==sign2);
+       *neibor_relations=NONE;
+       neibor_relations++;
+      }
+    }
+  }
+  return neibor_relations;
+}
+      
+
+void preprocess() {
+  int var, neibor_var, i, *vector;
+
+  for (var=0; var<NB_VAR; var++) {
+    var_count[var]=1;
+    tabu[var]=FALSE;
+    tabu_list[var]=FALSE;
+  }
+
+  for (var=0; var<NB_VAR; var++) {
+    for(i=0; i<neibor_stack_fill_pointer; i++) var_count[neibor_stack[i]]=1;
+    neibor_stack_fill_pointer=0;
+    pass(var, neg_in[var]);
+    pass(var, pos_in[var]);
+    vector=(int *)malloc((neibor_stack_fill_pointer+1)*sizeof(int));
+    // vector_relations=(int **)malloc((neibor_stack_fill_pointer+1)*sizeof(int));
+    for(i=0; i<neibor_stack_fill_pointer; i++) {
+      neibor_var=neibor_stack[i];
+      vector[i]=neibor_var;
+      // neibor_var occupies var_count cells for all clauses
+      // in which var and neibor_var both occur
+      //vector_relations[i]=(int *)malloc((var_count[neibor_var])*sizeof(int));
+      //relations=build_neibor_relation(var, neibor_var, 
+      //vector_relations[i], neg_in[var]);
+    // relations=build_neibor_relation(var, neibor_var, 
+      //                             relations, pos_in[var]);
+      //the end
+      //*relations=NONE;
+    }
+    vector[i]=NONE;
+    neibor[var]=vector;
+// neibor_relations[var]=vector_relations;
+  }
+}
+
+int random_integer(int max)
+{
+  unsigned long int RAND;
+  RAND=rand();
+  return RAND % max;
+}//random_integer(max) is from 0 to max-1
+
+//-------------------------------------------------------------------------
+
+//Modifaction du germe du générateur aléatoire
+
+//-------------------------------------------------------------------------
+/*
+void modify_seed()
+{
+  struct tms *a_tms;
+  int seed=2;
+  time_t tp, mess;
+
+  mess=time(&tp);
+
+//  tv=(struct timeval *)malloc(sizeof(struct timeval));
+//  tzp=(struct timezone *)malloc(sizeof(struct timezone));
+//  gettimeofday(tv,tzp);
+//  seed = (( tv->tv_sec & 0177 ) * 1000000) + tv->tv_usec;  
+
+  if (mess==-1) {
+    a_tms = ( struct tms *) malloc( sizeof (struct tms));
+    mess=times(a_tms);
+    seed = a_tms->tms_utime;
+  }
+  else seed=mess;
+  srand(seed);
+}
+*/
+
+  struct timeval tv;
+  struct timezone tzp;
+
+void modify_seed() {
+  int seed;
+  if (SEED_FLAG==TRUE) {
+    srand(SEED); SEED=SEED+17;
+    if (SEED==0) SEED=17;
+  }
+  else {
+    gettimeofday(&tv,&tzp);
+    seed = (( tv.tv_sec & 0177 ) * 1000000) + tv.tv_usec;
+    srand(seed);
+  }
+}
+
+
+int get_gradient(int var, int *clauses) {
+  int clause, var1, *vars_signs, gradient=0, clause_gradient=1;
+  for(clause=*clauses; clause!=NONE; clause=*(++clauses)) {
+    if (clause_state[clause] == ACTIVE) {
+      vars_signs = var_sign[clause];  clause_gradient=1;
+      for(var1=*vars_signs; var1!=NONE; var1=*(vars_signs+=2)) {
+       if ((var_state[var1]==ACTIVE) && (var1!=var)) {
+
+         if (var_current_value[var1]==*(vars_signs+1)) {
+           clause_gradient=0; break;
+         }
+       }
+      }
+      gradient+=clause_gradient;
+    }
+  }
+  return gradient;
+}
+
+void free_tabu() {
+  int i, var;
+  for (i=0; i<tabu_stack_fill_pointer; i++) {
+    var=tabu_stack[i];
+    tabu[var]=FALSE;
+    tabu_list[var]=FALSE;
+  }
+  tabu_stack_fill_pointer=0;
+}
+
+inline int decreasing_var(int var) {
+  return (score[var]>0);
+}
+//int clause_weight[tab_clause_size];
+//after vars have initial values, call initialize()
+int initialize() {
+  int var, gradient, neg_gradient, pos_gradient, clause;
+
+  decreasing_vars_stack_fill_pointer=0;
+  zerodommage_vars_stack_fill_pointer=0;
+  for (var=0; var<NB_VAR; var++) {
+       counter[var]=0.0; 
+    tmp_score[var]=0;
+    if (var_state[var]==ACTIVE) {
+      neg_gradient=get_gradient(var, neg_in[var]);
+      pos_gradient=get_gradient(var, pos_in[var]);
+      if (var_current_value[var]==TRUE) {
+       score[var]=neg_gradient-pos_gradient;
+       make[var]=neg_gradient; break_value[var]=pos_gradient;
+      }        
+      else {
+       score[var]=pos_gradient-neg_gradient;
+       make[var]=pos_gradient; break_value[var]=neg_gradient; 
+      }        
+      if (var_current_value[var]==TRUE)
+            dommage_if_flip[var]=pos_gradient;
+      else dommage_if_flip[var]=neg_gradient;
+      if ((dommage_if_flip[var]==0)  && ( score[var] != 0)) {
+       push(var, zerodommage_vars_stack);
+               zerodommage[var]=TRUE;
+      }
+      else zerodommage[var]=FALSE;
+      if (decreasing_var(var)) {
+       push(var, decreasing_vars_stack);
+       tendance[var]=DECREASING;
+      }
+      else if (score[var]==0)
+       tendance[var]=PLATEAU;
+      else tendance[var]=INCREASING;
+    }
+  }
+  max_counter=0.0; min_counter=0.0; ave_counter=0.0;
+  
+  for(clause=0; clause<NB_CLAUSE; clause++) {
+    most_recent[clause]=NONE;
+    most_recent_count[clause]=0;
+   // clause_weight[clause]=0;
+  }  
+  
+  free_tabu();
+  return TRUE;
+}
+
+int nb_clauses_violated(int *clauses) {
+  int clause, nb_violated=0;
+    
+  for (clause=*clauses;clause!=NONE;clause=*(++clauses))
+    if (nb_lit_true[clause]==1)
+      nb_violated++;       
+  return nb_violated; 
+}
+
+int choose_least_flipped_var() {
+  int var, chosen_var, i, flip=MAXSTEPS;
+
+  for (i=0; i<VARIABLE_STACK_fill_pointer; i++) {
+    var=VARIABLE_STACK[i];
+    if (flip_time[var]<flip) {
+      chosen_var=var; flip=flip_time[var];
+    }
+  }
+  return chosen_var;
+}
+
+void score_for_vars_in_sat_clauses(int var, int *clauses) {
+  int clause,  neibor_var, *vars_signs, dommage=0;
+  for (clause=*clauses;clause!=NONE;clause=*(++clauses)) {
+    vars_signs=var_sign[clause];
+    switch(nb_lit_true[clause]) {
+    case 0: 
+      for(neibor_var=*vars_signs; neibor_var!=NONE; 
+         neibor_var=*(vars_signs+=2)) {
+       if (neibor_var!=var) {
+           tmp_score[neibor_var]--;
+       }
+      }
+      break;
+    case 1: 
+      for(neibor_var=*vars_signs; neibor_var!=NONE; 
+         neibor_var=*(vars_signs+=2)) {
+       if ((neibor_var!=var) && 
+           (var_current_value[neibor_var]==*(vars_signs+1))) {
+         tmp_score[neibor_var]++;
+         break;
+       }
+      }
+      break;
+    }
+  }
+}
+
+void score_for_vars_in_unsat_clauses(int var, int *clauses) {
+  int clause, neibor_var, *vars_signs;
+  for (clause=*clauses;clause!=NONE;clause=*(++clauses)) {
+    vars_signs=var_sign[clause];
+    switch(nb_lit_true[clause]) {
+    case 1: 
+      for(neibor_var=*vars_signs; neibor_var!=NONE; 
+         neibor_var=*(vars_signs+=2)) {
+       if (neibor_var!=var) {
+         tmp_score[neibor_var]++;
+       }
+      }
+      break;
+    case 2: 
+      for(neibor_var=*vars_signs; neibor_var!=NONE; 
+         neibor_var=*(vars_signs+=2)) {
+       if ((neibor_var!=var) && 
+           (var_current_value[neibor_var]==*(vars_signs+1))) {
+         tmp_score[neibor_var]--;
+         break;
+       }
+      }
+      break;
+    }
+  }
+}
+
+int TIME;
+
+char expchance(int X)
+{
+   if (X>Intensity) X=Intensity;
+   if (X<1) return 1;
+   X=1<<X;
+   if (rand()%X==0) return 1;
+   return 0;
+}
+      
+int get_wp_var(int random_clause_unsat) {
+  int number_vars=0, index_of_vars, var;
+  //int number_vars=0, index_vars, var, old=MAXSTEPS, old_var=NONE, clause, *clauses, weight;
+  register int *vars_signs;
+  int all_vars[tab_variable_size];
+
+  vars_signs = var_sign[random_clause_unsat]; 
+  
+  //weight=MAXSTEPS; old_var=NONE;
+  for(var=*vars_signs; var!=NONE; var=*(vars_signs+=2)) {
+       all_vars[number_vars++]=var;
+       //number_vars++;
+  }//var is all_vars[0], all_vars[1], ..., all_vars[number_vars-1]
+  index_of_vars=random_integer(number_vars);//index_of_vars is from 0 to number_vars-1
+  //random_integer(max) is from 0 to max-1
+  return all_vars[index_of_vars];
+ }
+
+
+
+int get_var_by_ori_vw() {
+  int  random_unsatisfied_clause,  var_to_flip, number_vars=0, ii, one_index, var, best_break, the_break, best_var, best_counter, var_counter;
+  int all_vars[tab_variable_size]; 
+  register int *vars_signs;
+  
+  random_unsatisfied_clause=random_integer(MY_CLAUSE_STACK_fill_pointer);
+  random_unsatisfied_clause=MY_CLAUSE_STACK[random_unsatisfied_clause];
+  vars_signs = var_sign[random_unsatisfied_clause]; 
+  for(var=*vars_signs; var!=NONE; var=*(vars_signs+=2)) {
+       all_vars[number_vars++]=var;
+       //number_vars++;
+  }//var is all_vars[0], all_vars[1], ..., all_vars[number_vars-1], there are number_vars vars
+  //number_vw++;
+  one_index=random_integer(number_vars);
+  var=all_vars[one_index];
+  best_break=break_value[var]; 
+  if (best_break==0) return var;
+  best_var=var; best_counter=counter[var]; 
+  for (ii=1;ii<number_vars;ii++) {
+    one_index++; if (one_index>=number_vars) one_index=0;
+    var=all_vars[one_index];
+    the_break=break_value[var];
+       if (the_break==0) return var;
+       var_counter=counter[var];
+       if (the_break<best_break || (var_counter<best_counter) && (the_break==best_break || expchance(the_break-best_break)))
+         {
+          best_var=var; best_counter=var_counter; best_break=the_break; 
+         }
+ }
+ return best_var;
+}
+
+int get_var_to_flip_in_clause_as_plus(int random_clause_unsat) {
+  int var, best_var, second_best_var, nb, max_nb, pos_gradient, second_max=-NB_CLAUSE,
+    neg_gradient, real_nb, flip=-1, flip_index, var_to_flip, old=MAXSTEPS, old_var;
+  register int *vars_signs;
+
+  vars_signs = var_sign[random_clause_unsat]; max_nb=-NB_CLAUSE;
+  for(var=*vars_signs; var!=NONE; var=*(vars_signs+=2)) {
+    nb=score[var];
+    if ((nb>max_nb) || ((nb==max_nb) && (flip_time[var]<flip_time[best_var]))) {
+      second_best_var=best_var; second_max=max_nb; best_var=var; max_nb=nb;
+    }
+    else if ((nb>second_max) || 
+            ((nb==second_max) && (flip_time[var]<flip_time[second_best_var]))) {
+      second_max=nb; second_best_var=var;
+    }
+    if (flip_time[var]>flip) 
+      flip=flip_time[var];
+    if (flip_time[var]<old) {
+      old=flip_time[var];
+      old_var=var;
+    }
+  }
+  
+  //if (random_integer(100)<LNOISE)
+  //  return old_var;
+    
+  if (random_integer(100)<LNOISE) {
+     return get_wp_var(random_clause_unsat);
+  }  
+  else {
+    if (flip_time[best_var]==flip) {
+      if (random_integer(100)<NOISE) 
+           return second_best_var; 
+      else return best_var;
+      }
+    else return best_var;
+  }
+}
+
+
+
+int get_var_to_flip_in_clause_as_new(int random_clause_unsat) {
+  int var, best_var, second_best_var, nb, max_nb, pos_gradient, second_max=-NB_CLAUSE,
+    neg_gradient, real_nb, flip=-1, flip_index, var_to_flip, old=MAXSTEPS, old_var,
+    chosen_var;
+  register int *vars_signs;
+
+  vars_signs = var_sign[random_clause_unsat]; max_nb=-NB_CLAUSE;
+  for(var=*vars_signs; var!=NONE; var=*(vars_signs+=2)) {
+    nb=score[var];
+    if ((nb>max_nb) || ((nb==max_nb) && (flip_time[var]<flip_time[best_var]))) {
+      second_best_var=best_var; second_max=max_nb; best_var=var; max_nb=nb;
+    }
+    else if ((nb>second_max) || 
+            ((nb==second_max) && (flip_time[var]<flip_time[second_best_var]))) {
+      second_max=nb; second_best_var=var;
+    }
+    if (flip_time[var]<old) {
+      old=flip_time[var];
+      old_var=var;
+    }
+  }
+  if (random_integer(100)<LNOISE)
+    chosen_var=old_var;
+  else {
+    if (best_var==most_recent[random_clause_unsat]) {
+      switch(most_recent_count[random_clause_unsat]) {
+      case 1: NOISE1=20; break;
+      case 2: NOISE1=50; break;
+      case 3: NOISE1=65; break;
+      case 4: NOISE1=72; break;
+      case 5: NOISE1=78; break;
+      case 6: NOISE1=86; break;
+      case 7: NOISE1=90; break;
+      case 8: NOISE1=95; break;
+      case 9: NOISE1=98; break;
+      default: NOISE1=100; break;
+      }
+      if (random_integer(100)<NOISE1) {
+       chosen_var=second_best_var; 
+      }
+      else 
+       chosen_var=best_var;
+    }
+    else
+       chosen_var=best_var;
+  }
+  return chosen_var;
+}
+
+void satisfy_clauses(int var, int *clauses) {
+  int clause,  neibor_var, *vars_signs, dommage=0, last_unsatisfied_clause,
+    index;
+  for (clause=*clauses;clause!=NONE;clause=*(++clauses)) {
+    vars_signs=var_sign[clause];
+    switch(nb_lit_true[clause]) {
+    case 0: clause_truth[clause]=TRUE; nb_lit_true[clause]++;
+      dommage++; //clause_weight[clause]=TIME;
+      last_unsatisfied_clause=pop(MY_CLAUSE_STACK);
+      index=index_in_MY_CLAUSE_STACK[clause];
+      MY_CLAUSE_STACK[index]=last_unsatisfied_clause;
+      index_in_MY_CLAUSE_STACK[last_unsatisfied_clause]=index;
+
+      for(neibor_var=*vars_signs; neibor_var!=NONE; 
+         neibor_var=*(vars_signs+=2)) {
+       if (neibor_var!=var) {
+           tmp_score[neibor_var]--;
+           make[neibor_var]--;// break_value[neibor_var] unchanged
+       }
+      }
+      break;
+    case 1: nb_lit_true[clause]++;
+      for(neibor_var=*vars_signs; neibor_var!=NONE; 
+         neibor_var=*(vars_signs+=2)) {
+       if ((neibor_var!=var) && 
+           (var_current_value[neibor_var]==*(vars_signs+1))) {
+         // dommage_if_flip[neibor_var]--;
+         tmp_score[neibor_var]++;
+         break_value[neibor_var]--;//make[neibor_var] unchanged, 
+         break;
+       }
+      }
+      break;
+    default:  nb_lit_true[clause]++;
+    }
+  }
+  if (dommage==0) 
+    printf("c'est curieux...");
+  
+}
+
+/* let x1 be the new value of x and x0 be the old value of x
+   then for each clause in *clauses here, (x1-x0)df/dx is positive */
+void unsatisfy_clauses(int var, int *clauses) {
+  int clause, neibor_var, *vars_signs;
+  for (clause=*clauses;clause!=NONE;clause=*(++clauses)) {
+    vars_signs=var_sign[clause];
+    switch(nb_lit_true[clause]) {
+       //before flipping var, nb_lit_true[cause]>=1 because var is a positive literal  
+    case 1:  clause_truth[clause]=FALSE; nb_lit_true[clause]--;
+      //push(clause,MY_CLAUSE_STACK);
+      
+      if (most_recent[clause]==var) 
+            most_recent_count[clause]++;
+      else {
+           most_recent[clause]=var;
+           most_recent_count[clause]=1;
+      }
+      
+      index_in_MY_CLAUSE_STACK[clause]=MY_CLAUSE_STACK_fill_pointer;
+      push(clause,MY_CLAUSE_STACK);
+
+      for(neibor_var=*vars_signs; neibor_var!=NONE; 
+         neibor_var=*(vars_signs+=2)) {
+       if (neibor_var!=var) {
+         tmp_score[neibor_var]++;
+         make[neibor_var]++;// break_value[neibor_var] unchanged
+       }
+      }
+      break;
+    case 2: nb_lit_true[clause]--;
+      for(neibor_var=*vars_signs; neibor_var!=NONE; 
+         neibor_var=*(vars_signs+=2)) {
+       if ((neibor_var!=var) && 
+           (var_current_value[neibor_var]==*(vars_signs+1))) {
+         tmp_score[neibor_var]--;
+         break_value[neibor_var]++; 
+         // dommage_if_flip[neibor_var]++;
+         break;
+       }
+      }
+      break;
+    default:  nb_lit_true[clause]--;
+    }
+  }
+}
+
+void check_implied_clauses(int var, int value, int nb_flip) { 
+  int *neibors, neibor_var;
+  //neibors=neibor[var];
+  //  for(neibor_var=*neibors; neibor_var!=NONE; neibor_var=*(++neibors)) 
+  //  tmp_score[neibor_var]=0;
+  if (value==TRUE) {
+    satisfy_clauses(var, pos_in[var]);
+    unsatisfy_clauses(var, neg_in[var]);
+  }
+  else {
+    satisfy_clauses(var, neg_in[var]);
+    unsatisfy_clauses(var, pos_in[var]);
+  }
+  neibors=neibor[var];
+  for(neibor_var=*neibors; neibor_var!=NONE; neibor_var=*(++neibors)) {
+    if ((score[neibor_var]<=0) && (score[neibor_var]+tmp_score[neibor_var]>0))
+      push(neibor_var, decreasing_vars_stack);
+    score[neibor_var]+=tmp_score[neibor_var];
+    tmp_score[neibor_var]=0;
+  }
+}
+
+void eliminate_satisfied_clauses() {
+  int first_satisfied=NONE,put_in,i;
+  
+  for (i=0;i<MY_CLAUSE_STACK_fill_pointer;i++)
+    if(clause_truth[MY_CLAUSE_STACK[i]]==TRUE) {
+      first_satisfied=i;
+      break;
+    }    
+  if (first_satisfied!=NONE) { 
+    put_in=first_satisfied;
+    for (i=first_satisfied+1;i<MY_CLAUSE_STACK_fill_pointer;i++)
+      if (clause_truth[MY_CLAUSE_STACK[i]]!=TRUE) {
+       MY_CLAUSE_STACK[put_in]=MY_CLAUSE_STACK[i];
+       put_in++;              
+      }
+    MY_CLAUSE_STACK_fill_pointer=put_in;
+  }
+}
+
+void push_unsatisfied_clauses(int var, int value) { 
+  int *clauses,clause;
+   
+  if (value==TRUE) clauses=neg_in[var];
+  else clauses=pos_in[var];
+  for (clause=*clauses;clause!=NONE;clause=*(++clauses)) {
+    if (nb_lit_true[clause]==1 ) {
+      push(clause,MY_CLAUSE_STACK);
+      clause_truth[clause]=FALSE;         
+    }
+    nb_lit_true[clause]--;
+  } 
+}
+
+void dec_nb_lit_true(int var, int value) {
+  int *clauses,clause;
+  if (positive(var))
+    clauses=neg_in[var];
+  else
+    clauses=pos_in[var];
+  for (clause=*clauses;clause!=NONE;clause=*(++clauses))    
+    nb_lit_true[clause]--;    
+}
+
+int simple_eliminate_increasing_vars() {
+  int i, first=NONE, put_in, var, current=0, nb=0, chosen_var=NONE, flip=MAXSTEPS;
+  for (i=0; i<decreasing_vars_stack_fill_pointer; i++) {
+    var=decreasing_vars_stack[i];
+    if (score[var]<=0) {
+      first=i;
+      break;
+    }
+  }
+  if (first !=NONE) {
+    put_in=first;
+    for (i=first+1; i<decreasing_vars_stack_fill_pointer; i++) {
+      var=decreasing_vars_stack[i];
+      if (score[var]>0) {
+       decreasing_vars_stack[put_in++]=var;
+      }
+    }
+    decreasing_vars_stack_fill_pointer=put_in;
+  }
+  return chosen_var;
+}
+
+void eliminate_dommage_vars() {
+  int i, first=NONE, put_in, var, current=-1;
+  for (i=0; i<zerodommage_vars_stack_fill_pointer; i++) {
+    var=zerodommage_vars_stack[i];
+    if (zerodommage[var]==FALSE) {
+      first=i;
+      break;
+    }
+  }
+  if (first !=NONE) {
+    put_in=first;
+    for (i=first+1; i<zerodommage_vars_stack_fill_pointer; i++) {
+      var=zerodommage_vars_stack[i];
+      if (zerodommage[var]==TRUE)
+       zerodommage_vars_stack[put_in++]=var;
+    }
+    zerodommage_vars_stack_fill_pointer=put_in;
+  }
+}
+
+int choose_best_decreasing_var() {
+  int var, chosen_var, i, maxnb=0, flip=MAXSTEPS, nb, considered_length;
+  double the_counter;
+  considered_length=decreasing_vars_stack_fill_pointer; 
+  var=decreasing_vars_stack[0]; 
+  //the_counter=counter[var]; 
+  flip=flip_time[var]; 
+  chosen_var=var;
+  for (i=1; i<considered_length; i++) {
+     var=decreasing_vars_stack[i];
+     if (flip_time[var]<flip) {
+          flip=flip_time[var]; chosen_var=var; 
+     }
+  }
+  return chosen_var;
+}
+
+
+  
+int update_gradient_and_choose_flip_var(int var) {
+  int neibor_var, chosen1, sign, index, for_swap, 
+    other_var_in_same_clause, clause_gradient, gradient, chosen_var=NONE;
+
+  score[var]=0-score[var];
+  for_swap=make[var];
+  make[var]=break_value[var];
+  break_value[var]=for_swap;
+  simple_eliminate_increasing_vars();
+  if (decreasing_vars_stack_fill_pointer>1)
+    return choose_best_decreasing_var();
+  else if (decreasing_vars_stack_fill_pointer==1)
+    return decreasing_vars_stack[0];
+  return chosen_var;
+}
+  
+
+int choose_var_by_random_walk_as_plus() {
+  int  random_unsatisfied_clause,  var_to_flip;
+  random_unsatisfied_clause=random_integer(MY_CLAUSE_STACK_fill_pointer);
+  random_unsatisfied_clause=MY_CLAUSE_STACK[random_unsatisfied_clause];
+  var_to_flip=get_var_to_flip_in_clause_as_plus(random_unsatisfied_clause);
+  return  var_to_flip;
+}
+
+ int choose_var_by_random_walk_as_new() {
+  int  random_unsatisfied_clause,  var_to_flip;
+  random_unsatisfied_clause=random_integer(MY_CLAUSE_STACK_fill_pointer);
+  random_unsatisfied_clause=MY_CLAUSE_STACK[random_unsatisfied_clause];
+  var_to_flip=get_var_to_flip_in_clause_as_new(random_unsatisfied_clause);
+  return  var_to_flip;
+}
+
+
+int flipped_var_stack[tab_variable_size];
+int flipped_var_stack_fill_pointer=0;
+int flipped[tab_variable_size];
+
+void clean_flipped() {
+  int i;
+  for(i=0; i<flipped_var_stack_fill_pointer; i++)
+    flipped[flipped_var_stack[i]]=0;
+  flipped_var_stack_fill_pointer=0;
+}
+
+void save_assignment() {
+  int i;
+  clean_flipped();
+  // for(i=0; i<NB_VAR; i++) 
+  //  saved_var_current_value[i]=var_current_value[i];
+}
+
+int compute_distance() {
+  int k, dist=0, var, i;
+  for(i=0; i<flipped_var_stack_fill_pointer; i++) {
+    var=flipped_var_stack[i];
+    if (flipped[var]%2 == 1) 
+      dist++;
+  }
+  //for(k=0;k<NB_VAR;k++) {
+  //  if (var_current_value[k] != saved_var_current_value[k])
+  //    dist++; 
+  //}
+  return dist;
+}
+
+//int TIME;
+
+#include "adaptnoisebis1at5.C"
+
+void update_counter(int var_to_flip) {
+  double the_old_counter, the_new_counter;     
+  //if ((j+1)%1000==0) analyse_counter(var_to_flip, counter[var_to_flip]);
+  the_old_counter=counter[var_to_flip];
+  //ounter[var_to_flip]=(1.0-Sigma)*(counter[var_to_flip]+1.0)+Sigma*(double)(global_j+1);
+  counter[var_to_flip]=1.0*(counter[var_to_flip]+1.0);
+  the_new_counter=counter[var_to_flip];
+  old_ave_counter=ave_counter;
+  ave_counter=old_ave_counter+(the_new_counter-the_old_counter)/(double)NB_VAR;
+  if (the_new_counter>max_counter) {
+       max_counter=the_new_counter;
+       //var_with_biggest_counter=var_to_flip;
+  }
+}
+
+bool search() {
+  int last_suc_j=MAXSTEPS, i,j,k,SAT=FALSE, var_to_flip=NONE, index, flag, 
+    *min, nbwalk=0, var;
+
+  double avgdepth, depth=0;
+  //double avgdepths=0, total_min=0, total_last=0, total_nbwalk=0;
+  long begintime, endtime, mess;
+  struct tms *a_tms;
+  
+  a_tms = ( struct tms *) malloc( sizeof (struct tms));
+  mess=times(a_tms); begintime = a_tms->tms_utime;
+  
+  min=(int *)malloc(MAXTRIES*sizeof(int));
+  preprocess();
+
+  for (i=0;i<MAXTRIES;i++) {
+       //Intensity=1;  Sigma=0.1;  Interval=1000.0;  Adjustment=1000.0;
+       Sigma=0.0;
+    modify_seed(); min[i]=NB_CLAUSE; nbwalk=0; SAT=FALSE; depth=0;
+    for (k=0;k<NB_VAR;k++) {
+      if (var_state[k]==ACTIVE) {
+       var_current_value[k]=random_integer(2);
+       enter_stack_time[k]=0;
+       flip_time[k]=0;
+       walk_time[k]=0;
+       flipped[k]=0;
+      }
+    }
+    initialize();
+    clause_value();
+    initNoise();
+    if (zerodommage_vars_stack_fill_pointer>0) {
+      index=random_integer(zerodommage_vars_stack_fill_pointer);
+      var_to_flip=zerodommage_vars_stack[index];
+    }
+    else 
+    if (decreasing_vars_stack_fill_pointer>0) {
+      index=random_integer(decreasing_vars_stack_fill_pointer);
+      var_to_flip=decreasing_vars_stack[index];
+      // var_to_flip=choose_best_decreasing_var();
+    }
+    else var_to_flip=NONE;
+    for (j=0;j<MAXSTEPS;j++) {
+      global_j=j;      
+      flag=TRUE; TIME=j;
+      if (walk_satisfiable()) {
+           SAT=TRUE; last_suc_j=j;
+           break;
+      }
+     
+      if (max_counter>=(double)coefficient_for_prm*ave_counter)
+       {
+               //number_uneven++;
+               if (var_to_flip==NONE) {// when there is no non-tabu decreasing var 
+               nbwalk++; 
+               var_to_flip=choose_var_by_random_walk_as_new();
+               flag=FALSE; 
+          }   
+       }
+      else 
+       {
+           //number_even++;     
+          if (var_to_flip==NONE) {// when there is no non-tabu decreasing var 
+               nbwalk++; 
+               var_to_flip=choose_var_by_random_walk_as_plus(); 
+               flag=FALSE; 
+          }   
+        }
+               
+      var_current_value[var_to_flip]=1-var_current_value[var_to_flip]; 
+      check_implied_clauses(var_to_flip, var_current_value[var_to_flip], j);
+      //eliminate_satisfied_clauses();
+      flip_time[var_to_flip]=j;
+      update_counter(var_to_flip);
+      //if ((double)(j+1)>Adjustment) adjust_parameters_from_ori_vw((double)(j+1)); 
+      adaptNoveltyNoise(j);
+      // flipped_var=var_to_flip;
+      var_to_flip=update_gradient_and_choose_flip_var(var_to_flip);
+   }
+    if (SAT==TRUE) {
+      clause_value();
+      if (walk_satisfiable()) {
+       //fprintf(stdout, "c A solution is found\n");
+       break;
+      }
+      else {
+       //fprintf(stdout, "c I'AM SORRY SOMETHING IS WRONG\n");
+       SAT=FALSE;
+      }
+    }
+    
+ }
+  mess=times(a_tms); endtime = a_tms->tms_utime;
+   if (SAT==TRUE) {
+    //fprintf(stdout, "s SATISFIABLE\n");
+    //fprintf(stdout, "v ");
+    /*for (var=0; var<NB_VAR; var++) {
+      if (var_current_value[var]==TRUE)
+       fprintf(stdout, "%d ", var+1);
+      else fprintf(stdout, "%d ", -(var+1));
+    }*/
+    //fprintf(stdout, "\n");
+    //fprintf(stdout, "v 0 \n");
+  }
+  else {
+    //fprintf(stdout, "s UNKNOWN\n");
+  }
+  fprintf(stdout, "c Done (mycputime is %5.3f seconds)\n", 
+         ((double)(endtime-begintime)/((double)CLOCKS_PER_SEC/(double)10000)));
+  if (SAT==TRUE)
+    return true;
+  else return false;
+}
+
+
+
+int HELP_FLAG=FALSE;
+
+
+bool seq_processing(int _var_size, const vector< vector<int> >& clauses)
+{
+
+    int NB_VAR, NB_CLAUSE;
+    int ret = build_simple_sat_instance(_var_size, clauses);
+
+    switch(ret)
+    {
+    case FALSE:
+         return false;
+    case SATISFIABLE:
+         return true;
+    case TRUE:
+         VARIABLE_STACK_fill_pointer=0;
+         CLAUSE_STACK_fill_pointer = 0;
+         MANAGEDCLAUSE_STACK_fill_pointer = 0;
+         T_SEUIL= 0; 
+         return search();
+    case NONE:
+         return false;
+    }
+
+    return false;
+}
+
+/*
+main(int argc, char *argv[]) {
+  int i,  var; 
+
+  if (argc==3) {
+    SEED_FLAG=TRUE; 
+    if (sscanf(argv[2],"%u",&SEED)!=1) {
+      fprintf(stdout, "c Bad argument %s\n", argv[2]);
+      fprintf(stdout, "s UNKNOWN\n");
+      exit(0);
+    }
+  } 
+  //parse_parameters(argc,argv);
+  INPUT_FILE=argv[1];
+  coefficient_for_prm = 10.0; 
+   switch (build(BUILD_FLAG, INPUT_FILE)) {
+  case FALSE: fprintf(stdout, "c Input file error or too large formula\n"); 
+    fprintf(stdout, "s UNKNOWN\n");
+    exit(0);
+    return FALSE;
+  case SATISFIABLE:
+    if (verify_sol_input(argv[1])==TRUE) {
+      fprintf(stdout, "c Satisfied at top\n");
+      fprintf(stdout, "s SATISFIABLE\n");
+      fprintf(stdout, "v ");
+
+      for (var=0; var<NB_VAR; var++) {
+       if (var_current_value[var]==TRUE)
+         fprintf(stdout, "%d ", var+1);
+       else fprintf(stdout, "%d ", -(var+1));
+      }
+      fprintf(stdout, "\n");
+      fprintf(stdout, "v 0 \n");
+      exit(10);
+    }
+    else {
+      fprintf(stdout, "c problem at top\n");
+      fprintf(stdout, "s UNKNOWN\n");
+      exit(0);
+    }
+    return FALSE;
+  case TRUE:
+    VARIABLE_STACK_fill_pointer=0;
+    CLAUSE_STACK_fill_pointer = 0;
+    MANAGEDCLAUSE_STACK_fill_pointer = 0;
+    T_SEUIL= 0; 
+    if (search(argv[1])==TRUE) {
+       exit(10);
+    }
+    else 
+      exit(0);
+    break;
+  case NONE: fprintf(stdout, "c A contradiction is found at top!\n");
+    fprintf(stdout, "s UNSATISFIABLE\n");
+    exit(20);
+  }
+  return TRUE;
+}
+
+*/
diff --git a/examples/charm++/satisfiability/TNM/TNM.h b/examples/charm++/satisfiability/TNM/TNM.h
new file mode 100644 (file)
index 0000000..019b87b
--- /dev/null
@@ -0,0 +1,10 @@
+#ifndef _TNM_H_
+#define _TNM_H_
+
+#include <vector>
+
+using namespace std;
+
+bool seq_processing(int _var_size, const vector< vector<int> >& clauses);
+
+#endif
diff --git a/examples/charm++/satisfiability/TNM/TNM.pdf b/examples/charm++/satisfiability/TNM/TNM.pdf
new file mode 100644 (file)
index 0000000..37e7e4a
Binary files /dev/null and b/examples/charm++/satisfiability/TNM/TNM.pdf differ
diff --git a/examples/charm++/satisfiability/TNM/adaptnoisebis1at5.C b/examples/charm++/satisfiability/TNM/adaptnoisebis1at5.C
new file mode 100644 (file)
index 0000000..61cd079
--- /dev/null
@@ -0,0 +1,31 @@
+#define invPhi 10\r
+#define invTheta 5\r
+\r
+int lastAdaptFlip, lastBest, AdaptLength, NB_BETTER;\r
+\r
+int initNoise() {\r
+  lastAdaptFlip=0;\r
+  lastBest = MY_CLAUSE_STACK_fill_pointer;\r
+  NOISE=0; LNOISE=0; NB_BETTER=0;\r
+  AdaptLength=NB_CLAUSE / invTheta;\r
+}\r
+\r
+void adaptNoveltyNoise(int flip) {\r
+  if ((flip - lastAdaptFlip) > AdaptLength) {\r
+    NOISE += (int) ((100 - NOISE) / invPhi);\r
+    LNOISE= (int) NOISE/10;\r
+    lastAdaptFlip = flip;      \r
+    // NB_BETTER=0;\r
+    lastBest = MY_CLAUSE_STACK_fill_pointer;\r
+  } \r
+  else if (MY_CLAUSE_STACK_fill_pointer < lastBest) {\r
+    //  NB_BETTER++;\r
+    //  if (NB_BETTER>1) {\r
+      NOISE -= (int) (NOISE / invPhi / 2);\r
+      LNOISE= (int) NOISE/10;\r
+      lastAdaptFlip = flip;\r
+      lastBest = MY_CLAUSE_STACK_fill_pointer;\r
+      //   NB_BETTER=0;\r
+      // }\r
+  }\r
+}\r
diff --git a/examples/charm++/satisfiability/TNM/inputbis.C b/examples/charm++/satisfiability/TNM/inputbis.C
new file mode 100644 (file)
index 0000000..7cca5d5
--- /dev/null
@@ -0,0 +1,377 @@
+\r
+#define OLD_CLAUSE_REDUNDANT -77\r
+#define NEW_CLAUSE_REDUNDANT -7\r
+\r
+\r
+int smaller_than(int lit1, int lit2) {\r
+  return ((lit1<NB_VAR) ? lit1 : lit1-NB_VAR) < \r
+    ((lit2<NB_VAR) ? lit2 : lit2-NB_VAR);\r
+}\r
+\r
+my_type redundant(int *new_clause, int *old_clause) {\r
+  int lit1, lit2, old_clause_diff=0, new_clause_diff=0;\r
+    \r
+  lit1=*old_clause; lit2=*new_clause;\r
+  while ((lit1 != NONE) && (lit2 != NONE)) {\r
+    if (smaller_than(lit1, lit2)) {\r
+      lit1=*(++old_clause); old_clause_diff++;\r
+    }\r
+    else\r
+      if (smaller_than(lit2, lit1)) {\r
+       lit2=*(++new_clause); new_clause_diff++;\r
+      }\r
+      else\r
+       if (complement(lit1, lit2)) {\r
+         return FALSE; /* old_clause_diff++; new_clause_diff++; j1++; j2++; */\r
+       }\r
+       else {\r
+          lit1=*(++old_clause);  lit2=*(++new_clause);\r
+       }\r
+  }\r
+  if ((lit1 == NONE) && (old_clause_diff == 0))\r
+    /* la nouvelle clause est redondante ou subsumee */\r
+    return NEW_CLAUSE_REDUNDANT;\r
+  if ((lit2 == NONE) && (new_clause_diff == 0))\r
+    /* la old clause est redondante ou subsumee */\r
+    return OLD_CLAUSE_REDUNDANT;\r
+  return FALSE;\r
+}\r
+\r
+my_type get_resolvant(int *clause1, int *clause2, int *resolvant) {\r
+  int lit1, lit2, nb_diff1=0,  nb_diff2=0,\r
+    nb_iden=0, nb_opps=0, j1=0, j2=0, j, limited_length;\r
+\r
+  while (((lit1=clause1[j1])!=NONE) && ((lit2=clause2[j2]) != NONE)) {\r
+    if (complement(lit1, lit2)) {\r
+      j1++; j2++; nb_opps++;\r
+    }\r
+    else\r
+      if (lit1 == lit2) {\r
+       j1++; j2++; nb_iden++;\r
+      }\r
+      else\r
+       if (smaller_than(lit1, lit2)) {\r
+          nb_diff1++; j1++;\r
+       }\r
+       else {\r
+          nb_diff2++; j2++;\r
+       }\r
+  }\r
+  if (nb_opps ==1) {\r
+    if (clause1[j1] ==NONE) {\r
+      for (; clause2[j2]!= NONE; j2++) nb_diff2++;\r
+    }\r
+    else {\r
+      for (; clause1[j1]!= NONE; j1++) nb_diff1++;\r
+    }\r
+    if ((j1==1) || (j2==1))  limited_length=RESOLVANT_LENGTH; \r
+    else\r
+      if ((j1==2) && (j2==2))  limited_length=1;\r
+      else\r
+       if (j1<j2) limited_length=((j1<RESOLVANT_LENGTH) ? j1 : RESOLVANT_LENGTH);\r
+       else  limited_length=((j2<RESOLVANT_LENGTH) ? j2 : RESOLVANT_LENGTH);\r
+\r
+    if (nb_diff1 + nb_diff2 + nb_iden <= limited_length) {\r
+      j1=0; j2=0; j=0;\r
+      while (((lit1 = clause1[j1])!=NONE) && ((lit2 = clause2[j2]) != NONE)) {\r
+       if (lit1 == lit2) {\r
+         resolvant[j] = lit1; j1++; j2++; j++;\r
+       }\r
+       else \r
+         if (smaller_than(lit1, lit2)) {\r
+           resolvant[j] = lit1; j1++; j++;\r
+         }\r
+         else\r
+           if (smaller_than(lit2, lit1)) {\r
+             resolvant[j] = lit2; j2++; j++;\r
+           }\r
+           else {\r
+             j1++; j2++;\r
+           }\r
+      }\r
+      if (clause1[j1] ==NONE) while ((resolvant[j++] = clause2[j2++]) != NONE);\r
+      else while ((resolvant[j++] = clause1[j1++]) != NONE);\r
+      if (j==0) return NONE;\r
+      if (nb_diff2==0) return 2; /* clause1 is redundant */\r
+      return TRUE;\r
+    }\r
+  }\r
+  return FALSE;\r
+}\r
+\r
+int INVOLVED_CLAUSE_STACK[tab_clause_size];\r
+int INVOLVED_CLAUSE_STACK_fill_pointer=0;\r
+int CLAUSE_INVOLVED[tab_clause_size];\r
+\r
+void remove_passive_clauses() {\r
+  int  clause, put_in, first=NONE;\r
+  for (clause=0; clause<NB_CLAUSE; clause++) {\r
+    if (clause_state[clause]==PASSIVE) {\r
+      first=clause; break;\r
+    }\r
+  }\r
+  if (first!=NONE) {\r
+    put_in=first;\r
+    for(clause=first+1; clause<NB_CLAUSE; clause++) {\r
+      if (clause_state[clause]==ACTIVE) {\r
+       sat[put_in]=sat[clause]; var_sign[put_in]=var_sign[clause];\r
+       clause_state[put_in]=ACTIVE; \r
+       clause_length[put_in]=clause_length[clause];\r
+       put_in++;\r
+      }\r
+    }\r
+    NB_CLAUSE=put_in;\r
+  }\r
+}\r
+\r
+void remove_passive_vars_in_clause(int clause) {\r
+  int *vars_signs, *vars_signs1, var, var1, first=NONE;\r
+  vars_signs=var_sign[clause];\r
+  for(var=*vars_signs; var!=NONE; var=*(vars_signs+=2)) {\r
+    if (var_state[var]!=ACTIVE) {\r
+      first=var; break;\r
+    }\r
+  }\r
+  if (first!=NONE) {\r
+    for(vars_signs1=vars_signs+2, var1=*vars_signs1; var1!=NONE; \r
+       var1=*(vars_signs1+=2)) {\r
+      if (var_state[var1]==ACTIVE) {\r
+       *vars_signs=var1; *(vars_signs+1) = *(vars_signs1+1);\r
+       vars_signs+=2;\r
+      }\r
+    }\r
+    *vars_signs=NONE;\r
+  }\r
+}\r
+\r
+int clean_structure() {\r
+  int clause, var, *vars_signs;\r
+  remove_passive_clauses();\r
+  if (NB_CLAUSE==0) \r
+    return SATISFIABLE;\r
+  for (clause=0; clause<NB_CLAUSE; clause++) \r
+    remove_passive_vars_in_clause(clause);\r
+  NB_ACTIVE_VAR=0;\r
+  for (var=0; var<NB_VAR; var++) { \r
+    neg_nb[var] = 0;\r
+    pos_nb[var] = 0;\r
+    if (var_state[var]==ACTIVE) NB_ACTIVE_VAR++;\r
+  }\r
+  for (clause=0; clause<NB_CLAUSE; clause++) {\r
+    vars_signs=var_sign[clause];\r
+    for(var=*vars_signs; var!=NONE; var=*(vars_signs+=2)) {\r
+      if (*(vars_signs+1)==POSITIVE) \r
+       pos_in[var][pos_nb[var]++]=clause;\r
+      else  neg_in[var][neg_nb[var]++]=clause;\r
+    }\r
+  }\r
+  for (var=0; var<NB_VAR; var++) { \r
+    neg_in[var][neg_nb[var]]=NONE;\r
+    pos_in[var][pos_nb[var]]=NONE;\r
+  }\r
+  return TRUE;\r
+}\r
+\r
+int unitclause_process();\r
+int simplify_formula();\r
+\r
+int lire_clauses(const vector< vector<int> >& _clauses) {\r
+    int i, j, jj, ii, length, tautologie, lits[1000], lit, lit1;\r
+    for (i=0; i<NB_CLAUSE; i++) {\r
+    \r
+        length = _clauses[i].size();\r
+        for(j=0; j<length; j++)\r
+        {\r
+            lits[j] = _clauses[i][j];\r
+        }\r
+        tautologie = FALSE;\r
+        /* test if some literals are redundant and sort the clause */\r
+        for (ii=0; ii<length-1; ii++) {\r
+            lit = lits[ii];\r
+            for (jj=ii+1; jj<length; jj++) {\r
+                if (abs(lit)>abs(lits[jj])) {\r
+                    lit1=lits[jj]; lits[jj]=lit; lit=lit1;\r
+                }\r
+                else\r
+                    if (lit == lits[jj]) {\r
+                        lits[jj] = lits[length-1]; \r
+                        jj--; length--; lits[length] = 0;\r
+                    }\r
+                    else\r
+                        if (abs(lit) == abs(lits[jj])) {\r
+                            tautologie = TRUE; break;\r
+                        }\r
+            }\r
+            if (tautologie == TRUE) break;\r
+            else lits[ii] = lit;\r
+        }\r
+        if (tautologie == FALSE) {\r
+            sat[i]= (int *)malloc((length+1) * sizeof(int));\r
+            for (j=0; j<length; j++) {\r
+              if (lits[j] < 0) \r
+                  sat[i][j] = abs(lits[j]) - 1 + NB_VAR ;\r
+              else \r
+                  sat[i][j] = lits[j]-1;\r
+          }\r
+          sat[i][length]=NONE;\r
+          clause_length[i]=length;\r
+          clause_state[i] = ACTIVE;\r
+      }\r
+      else { i--; NB_CLAUSE--;}\r
+  }\r
+  return TRUE;\r
+}\r
+\r
+void build_structure() {\r
+    int i, j, var, *lits1, length, clause, *vars_signs, lit;\r
+    for (i=0; i<NB_VAR; i++) { \r
+        neg_nb[i] = 0; pos_nb[i] = 0;\r
+    }\r
+    for (i=0; i<NB_CLAUSE; i++) {\r
+        for(j=0; j<clause_length[i]; j++) {\r
+            if (sat[i][j]>=NB_VAR) {\r
+                var=sat[i][j]-NB_VAR; neg_nb[var]++;\r
+            }\r
+            else {\r
+                var=sat[i][j]; \r
+                pos_nb[var]++;\r
+            }\r
+        }\r
+        if (sat[i][clause_length[i]] !=NONE)\r
+            printf("erreur ");\r
+    }\r
+    for(clause=0;clause<NB_CLAUSE;clause++) {\r
+        length = clause_length[clause];\r
+        var_sign[clause] = (int *)malloc((2*length+1)*sizeof(int));\r
+        lits1 = sat[clause]; vars_signs = var_sign[clause];\r
+        for(lit=*lits1; lit!=NONE; lit=*(++lits1),(vars_signs+=2)) {\r
+            if (negative(lit)) {\r
+                *(vars_signs+1)= NEGATIVE;\r
+                *vars_signs = get_var_from_lit(lit);\r
+            }\r
+            else {\r
+                *(vars_signs+1)=POSITIVE;\r
+                *vars_signs = lit;\r
+            }\r
+        }\r
+        *vars_signs = NONE;  \r
+    }\r
+    for (i=0; i<NB_VAR; i++) { \r
+    neg_in[i] = (int *)malloc((neg_nb[i]+1) * sizeof(int));\r
+    pos_in[i] = (int *)malloc((pos_nb[i]+1) * sizeof(int));\r
+    neg_in[i][neg_nb[i]]=NONE; pos_in[i][pos_nb[i]]=NONE;\r
+    neg_nb[i] = 0; pos_nb[i] = 0;\r
+    var_state[i] = ACTIVE;\r
+  }   \r
+  for (i=0; i<NB_CLAUSE; i++) {\r
+    // if (i==774)\r
+    //  printf("kjhsdf");\r
+    lits1 = sat[i];\r
+    //printf("\n");\r
+    for(lit=*lits1; lit!=NONE; lit=*(++lits1)) {\r
+\r
+      //  printf("   %d", get_var_from_lit(lit));\r
+        if (positive(lit)) \r
+            pos_in[lit][pos_nb[lit]++] = i;\r
+        else\r
+            neg_in[get_var_from_lit(lit)]\r
+                [neg_nb[get_var_from_lit(lit)]++] = i;\r
+    }\r
+  }\r
+}\r
+\r
+\r
+void eliminate_redundance() {\r
+  int *lits, i, lit, *clauses, res, clause;\r
+\r
+  for (i=0; i<NB_CLAUSE; i++) {\r
+    if (clause_state[i]==ACTIVE) {\r
+      if (clause_length[i]==1)\r
+       push(i, UNITCLAUSE_STACK);\r
+      lits = sat[i];\r
+      for(lit=*lits; lit!=NONE; lit=*(++lits)) {\r
+       if (positive(lit)) \r
+         clauses=pos_in[lit];\r
+       else clauses=neg_in[lit-NB_VAR];\r
+       for(clause=*clauses; clause!=NONE; clause=*(++clauses)) {\r
+         if ((clause<i) && (clause_state[clause]==ACTIVE)) {\r
+           res=redundant(sat[i], sat[clause]);\r
+           if (res==NEW_CLAUSE_REDUNDANT) {\r
+             clause_state[i]=PASSIVE;\r
+             break;\r
+           }\r
+           else if (res==OLD_CLAUSE_REDUNDANT)\r
+             clause_state[clause]=PASSIVE;\r
+         }\r
+       }\r
+       if (res==NEW_CLAUSE_REDUNDANT)\r
+         break;\r
+      }\r
+    }\r
+  }\r
+}\r
+\r
+my_type build_simple_sat_instance(int vars_size,  const vector< vector<int> >&  clauses) {\r
+  \r
+    int i, j, length, NB_CLAUSE1, res, ii, jj, tautologie, lit1,\r
+        *pos_nb, *neg_nb;\r
\r
+    NB_VAR = vars_size;\r
+    NB_CLAUSE = clauses.size();\r
+\r
+    INIT_NB_CLAUSE = NB_CLAUSE;\r
+    neg_nb=(int *)reduce_if_negative_nb;\r
+    pos_nb=(int *)reduce_if_positive_nb;\r
+\r
+    if (lire_clauses(clauses)==FALSE)\r
+        return FALSE;\r
+    build_structure();\r
+    eliminate_redundance();\r
+    if (unitclause_process()==NONE) return NONE;\r
+    res=clean_structure();\r
+    if (res==FALSE)\r
+        return FALSE;\r
+    else if (res==SATISFIABLE)\r
+        return SATISFIABLE;\r
+    return TRUE;\r
+}\r
+\r
+int verify_sol_input(char *input_file) {\r
+    FILE* fp_in=fopen(input_file, "r");\r
+  char ch, word2[WORD_LENGTH];\r
+  int i, j, lit, var, nb_var1, nb_clause1;\r
+\r
+  if (fp_in == NULL) return FALSE;\r
+\r
+  fscanf(fp_in, "%c", &ch);\r
+  while (ch!='p') {\r
+    while (ch!='\n') fscanf(fp_in, "%c", &ch);  \r
+    fscanf(fp_in, "%c", &ch);\r
+  }\r
+  \r
+  fscanf(fp_in, "%s%d%d", word2, &nb_var1, &nb_clause1);\r
+  for (i=0; i<nb_clause1; i++) {\r
+    fscanf(fp_in, "%d", &lit);\r
+    while (lit != 0) {\r
+      if (lit<0) {\r
+       if (var_current_value[abs(lit)-1]==FALSE)\r
+         break;\r
+      }\r
+      else {\r
+       if (var_current_value[lit-1]==TRUE)\r
+         break;\r
+      }\r
+      fscanf(fp_in, "%d", &lit);\r
+    }\r
+    if (lit==0) {\r
+      fclose(fp_in);\r
+      return FALSE;\r
+    }\r
+    else {\r
+      do fscanf(fp_in, "%d", &lit);\r
+      while (lit != 0) ;\r
+    }\r
+  }\r
+  fclose(fp_in);\r
+  return TRUE;\r
+}\r
diff --git a/examples/charm++/satisfiability/minisat/Solver.C b/examples/charm++/satisfiability/minisat/Solver.C
new file mode 100644 (file)
index 0000000..7468f3d
--- /dev/null
@@ -0,0 +1,778 @@
+/****************************************************************************************[Solver.C]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+//#include <vector>
+#include "Solver.h"
+#include "mtl/Sort.h"
+#include <cmath>
+
+//using namespace std;
+
+//=================================================================================================
+// Constructor/Destructor:
+
+
+Solver::Solver() :
+
+    // Parameters: (formerly in 'SearchParams')
+    var_decay(1 / 0.95), clause_decay(1 / 0.999), random_var_freq(0.02)
+  , restart_first(100), restart_inc(1.5), learntsize_factor((double)1/(double)3), learntsize_inc(1.1)
+
+    // More parameters:
+    //
+  , expensive_ccmin  (true)
+  , polarity_mode    (polarity_false)
+  , verbosity        (0)
+
+    // Statistics: (formerly in 'SolverStats')
+    //
+  , starts(0), decisions(0), rnd_decisions(0), propagations(0), conflicts(0)
+  , clauses_literals(0), learnts_literals(0), max_literals(0), tot_literals(0)
+
+  , ok               (true)
+  , cla_inc          (1)
+  , var_inc          (1)
+  , qhead            (0)
+  , simpDB_assigns   (-1)
+  , simpDB_props     (0)
+  , order_heap       (VarOrderLt(activity))
+  , random_seed      (91648253)
+  , progress_estimate(0)
+  , remove_satisfied (true)
+{}
+
+
+Solver::~Solver()
+{
+    for (int i = 0; i < learnts.size(); i++) free(learnts[i]);
+    for (int i = 0; i < clauses.size(); i++) free(clauses[i]);
+}
+
+
+/******* framework of sequential solver */
+
+bool seq_processing(int var_size, const vector< vector<int> >& clauses)
+{
+  //   translation from charm program data structure to minisat data structure 
+    
+    Solver      S;
+    S.verbosity = 1;
+    printf(" Now in sequential processing, clauses size:%d\n", clauses.size());
+    for(int i=0; i<clauses.size(); i++)
+    {
+        vector<int> cl = clauses[i];
+
+        vec<Lit> lits;
+        int parsed_lit, var;
+        for(int j=0; j<cl.size(); j++)
+        {
+            parsed_lit = cl[j];
+            var = abs(parsed_lit)-1;
+            while (var >= S.nVars()) S.newVar();
+            lits.push( (parsed_lit > 0) ? Lit(var) : ~Lit(var) );
+        }
+        S.addClause(lits); 
+    }
+    
+    S.simplify();
+
+    bool ret = S.solve();
+   
+    if(ret)
+        printf(" By sequential, satisfiable\n");
+    else
+        printf(" NOT SAT\n");
+    return ret;
+}
+//=================================================================================================
+// Minor methods:
+
+
+// Creates a new SAT variable in the solver. If 'decision_var' is cleared, variable will not be
+// used as a decision variable (NOTE! This has effects on the meaning of a SATISFIABLE result).
+//
+Var Solver::newVar(bool sign, bool dvar)
+{
+    int v = nVars();
+    watches   .push();          // (list for positive literal)
+    watches   .push();          // (list for negative literal)
+    reason    .push(NULL);
+    assigns   .push(toInt(l_Undef));
+    level     .push(-1);
+    activity  .push(0);
+    seen      .push(0);
+
+    polarity    .push((char)sign);
+    decision_var.push((char)dvar);
+
+    insertVarOrder(v);
+    return v;
+}
+
+
+bool Solver::addClause(vec<Lit>& ps)
+{
+    assert(decisionLevel() == 0);
+
+    if (!ok)
+        return false;
+    else{
+        // Check if clause is satisfied and remove false/duplicate literals:
+        sort(ps);
+        Lit p; int i, j;
+        for (i = j = 0, p = lit_Undef; i < ps.size(); i++)
+            if (value(ps[i]) == l_True || ps[i] == ~p)
+                return true;
+            else if (value(ps[i]) != l_False && ps[i] != p)
+                ps[j++] = p = ps[i];
+        ps.shrink(i - j);
+    }
+
+    if (ps.size() == 0)
+        return ok = false;
+    else if (ps.size() == 1){
+        assert(value(ps[0]) == l_Undef);
+        uncheckedEnqueue(ps[0]);
+        return ok = (propagate() == NULL);
+    }else{
+        Clause* c = Clause_new(ps, false);
+        clauses.push(c);
+        attachClause(*c);
+    }
+
+    return true;
+}
+
+
+void Solver::attachClause(Clause& c) {
+    assert(c.size() > 1);
+    watches[toInt(~c[0])].push(&c);
+    watches[toInt(~c[1])].push(&c);
+    if (c.learnt()) learnts_literals += c.size();
+    else            clauses_literals += c.size(); }
+
+
+void Solver::detachClause(Clause& c) {
+    assert(c.size() > 1);
+    assert(find(watches[toInt(~c[0])], &c));
+    assert(find(watches[toInt(~c[1])], &c));
+    remove(watches[toInt(~c[0])], &c);
+    remove(watches[toInt(~c[1])], &c);
+    if (c.learnt()) learnts_literals -= c.size();
+    else            clauses_literals -= c.size(); }
+
+
+void Solver::removeClause(Clause& c) {
+    detachClause(c);
+    free(&c); }
+
+
+bool Solver::satisfied(const Clause& c) const {
+    for (int i = 0; i < c.size(); i++)
+        if (value(c[i]) == l_True)
+            return true;
+    return false; }
+
+
+// Revert to the state at given level (keeping all assignment at 'level' but not beyond).
+//
+void Solver::cancelUntil(int level) {
+    if (decisionLevel() > level){
+        for (int c = trail.size()-1; c >= trail_lim[level]; c--){
+            Var     x  = var(trail[c]);
+            assigns[x] = toInt(l_Undef);
+            insertVarOrder(x); }
+        qhead = trail_lim[level];
+        trail.shrink(trail.size() - trail_lim[level]);
+        trail_lim.shrink(trail_lim.size() - level);
+    } }
+
+
+//=================================================================================================
+// Major methods:
+
+
+Lit Solver::pickBranchLit(int polarity_mode, double random_var_freq)
+{
+    Var next = var_Undef;
+
+    // Random decision:
+    if (drand(random_seed) < random_var_freq && !order_heap.empty()){
+        next = order_heap[irand(random_seed,order_heap.size())];
+        if (toLbool(assigns[next]) == l_Undef && decision_var[next])
+            rnd_decisions++; }
+
+    // Activity based decision:
+    while (next == var_Undef || toLbool(assigns[next]) != l_Undef || !decision_var[next])
+        if (order_heap.empty()){
+            next = var_Undef;
+            break;
+        }else
+            next = order_heap.removeMin();
+
+    bool sign = false;
+    switch (polarity_mode){
+    case polarity_true:  sign = false; break;
+    case polarity_false: sign = true;  break;
+    case polarity_user:  sign = polarity[next]; break;
+    case polarity_rnd:   sign = irand(random_seed, 2); break;
+    default: assert(false); }
+
+    return next == var_Undef ? lit_Undef : Lit(next, sign);
+}
+
+
+/*_________________________________________________________________________________________________
+|
+|  analyze : (confl : Clause*) (out_learnt : vec<Lit>&) (out_btlevel : int&)  ->  [void]
+|  
+|  Description:
+|    Analyze conflict and produce a reason clause.
+|  
+|    Pre-conditions:
+|      * 'out_learnt' is assumed to be cleared.
+|      * Current decision level must be greater than root level.
+|  
+|    Post-conditions:
+|      * 'out_learnt[0]' is the asserting literal at level 'out_btlevel'.
+|  
+|  Effect:
+|    Will undo part of the trail, upto but not beyond the assumption of the current decision level.
+|________________________________________________________________________________________________@*/
+void Solver::analyze(Clause* confl, vec<Lit>& out_learnt, int& out_btlevel)
+{
+    int pathC = 0;
+    Lit p     = lit_Undef;
+
+    // Generate conflict clause:
+    //
+    out_learnt.push();      // (leave room for the asserting literal)
+    int index   = trail.size() - 1;
+    out_btlevel = 0;
+
+    do{
+        assert(confl != NULL);          // (otherwise should be UIP)
+        Clause& c = *confl;
+
+        if (c.learnt())
+            claBumpActivity(c);
+
+        for (int j = (p == lit_Undef) ? 0 : 1; j < c.size(); j++){
+            Lit q = c[j];
+
+            if (!seen[var(q)] && level[var(q)] > 0){
+                varBumpActivity(var(q));
+                seen[var(q)] = 1;
+                if (level[var(q)] >= decisionLevel())
+                    pathC++;
+                else{
+                    out_learnt.push(q);
+                    if (level[var(q)] > out_btlevel)
+                        out_btlevel = level[var(q)];
+                }
+            }
+        }
+
+        // Select next clause to look at:
+        while (!seen[var(trail[index--])]);
+        p     = trail[index+1];
+        confl = reason[var(p)];
+        seen[var(p)] = 0;
+        pathC--;
+
+    }while (pathC > 0);
+    out_learnt[0] = ~p;
+
+    // Simplify conflict clause:
+    //
+    int i, j;
+    if (expensive_ccmin){
+        uint32_t abstract_level = 0;
+        for (i = 1; i < out_learnt.size(); i++)
+            abstract_level |= abstractLevel(var(out_learnt[i])); // (maintain an abstraction of levels involved in conflict)
+
+        out_learnt.copyTo(analyze_toclear);
+        for (i = j = 1; i < out_learnt.size(); i++)
+            if (reason[var(out_learnt[i])] == NULL || !litRedundant(out_learnt[i], abstract_level))
+                out_learnt[j++] = out_learnt[i];
+    }else{
+        out_learnt.copyTo(analyze_toclear);
+        for (i = j = 1; i < out_learnt.size(); i++){
+            Clause& c = *reason[var(out_learnt[i])];
+            for (int k = 1; k < c.size(); k++)
+                if (!seen[var(c[k])] && level[var(c[k])] > 0){
+                    out_learnt[j++] = out_learnt[i];
+                    break; }
+        }
+    }
+    max_literals += out_learnt.size();
+    out_learnt.shrink(i - j);
+    tot_literals += out_learnt.size();
+
+    // Find correct backtrack level:
+    //
+    if (out_learnt.size() == 1)
+        out_btlevel = 0;
+    else{
+        int max_i = 1;
+        for (int i = 2; i < out_learnt.size(); i++)
+            if (level[var(out_learnt[i])] > level[var(out_learnt[max_i])])
+                max_i = i;
+        Lit p             = out_learnt[max_i];
+        out_learnt[max_i] = out_learnt[1];
+        out_learnt[1]     = p;
+        out_btlevel       = level[var(p)];
+    }
+
+
+    for (int j = 0; j < analyze_toclear.size(); j++) seen[var(analyze_toclear[j])] = 0;    // ('seen[]' is now cleared)
+}
+
+
+// Check if 'p' can be removed. 'abstract_levels' is used to abort early if the algorithm is
+// visiting literals at levels that cannot be removed later.
+bool Solver::litRedundant(Lit p, uint32_t abstract_levels)
+{
+    analyze_stack.clear(); analyze_stack.push(p);
+    int top = analyze_toclear.size();
+    while (analyze_stack.size() > 0){
+        assert(reason[var(analyze_stack.last())] != NULL);
+        Clause& c = *reason[var(analyze_stack.last())]; analyze_stack.pop();
+
+        for (int i = 1; i < c.size(); i++){
+            Lit p  = c[i];
+            if (!seen[var(p)] && level[var(p)] > 0){
+                if (reason[var(p)] != NULL && (abstractLevel(var(p)) & abstract_levels) != 0){
+                    seen[var(p)] = 1;
+                    analyze_stack.push(p);
+                    analyze_toclear.push(p);
+                }else{
+                    for (int j = top; j < analyze_toclear.size(); j++)
+                        seen[var(analyze_toclear[j])] = 0;
+                    analyze_toclear.shrink(analyze_toclear.size() - top);
+                    return false;
+                }
+            }
+        }
+    }
+
+    return true;
+}
+
+
+/*_________________________________________________________________________________________________
+|
+|  analyzeFinal : (p : Lit)  ->  [void]
+|  
+|  Description:
+|    Specialized analysis procedure to express the final conflict in terms of assumptions.
+|    Calculates the (possibly empty) set of assumptions that led to the assignment of 'p', and
+|    stores the result in 'out_conflict'.
+|________________________________________________________________________________________________@*/
+void Solver::analyzeFinal(Lit p, vec<Lit>& out_conflict)
+{
+    out_conflict.clear();
+    out_conflict.push(p);
+
+    if (decisionLevel() == 0)
+        return;
+
+    seen[var(p)] = 1;
+
+    for (int i = trail.size()-1; i >= trail_lim[0]; i--){
+        Var x = var(trail[i]);
+        if (seen[x]){
+            if (reason[x] == NULL){
+                assert(level[x] > 0);
+                out_conflict.push(~trail[i]);
+            }else{
+                Clause& c = *reason[x];
+                for (int j = 1; j < c.size(); j++)
+                    if (level[var(c[j])] > 0)
+                        seen[var(c[j])] = 1;
+            }
+            seen[x] = 0;
+        }
+    }
+
+    seen[var(p)] = 0;
+}
+
+
+void Solver::uncheckedEnqueue(Lit p, Clause* from)
+{
+    assert(value(p) == l_Undef);
+    assigns [var(p)] = toInt(lbool(!sign(p)));  // <<== abstract but not uttermost effecient
+    level   [var(p)] = decisionLevel();
+    reason  [var(p)] = from;
+    trail.push(p);
+}
+
+
+/*_________________________________________________________________________________________________
+|
+|  propagate : [void]  ->  [Clause*]
+|  
+|  Description:
+|    Propagates all enqueued facts. If a conflict arises, the conflicting clause is returned,
+|    otherwise NULL.
+|  
+|    Post-conditions:
+|      * the propagation queue is empty, even if there was a conflict.
+|________________________________________________________________________________________________@*/
+Clause* Solver::propagate()
+{
+    Clause* confl     = NULL;
+    int     num_props = 0;
+
+    while (qhead < trail.size()){
+        Lit            p   = trail[qhead++];     // 'p' is enqueued fact to propagate.
+        vec<Clause*>&  ws  = watches[toInt(p)];
+        Clause         **i, **j, **end;
+        num_props++;
+
+        for (i = j = (Clause**)ws, end = i + ws.size();  i != end;){
+            Clause& c = **i++;
+
+            // Make sure the false literal is data[1]:
+            Lit false_lit = ~p;
+            if (c[0] == false_lit)
+                c[0] = c[1], c[1] = false_lit;
+
+            assert(c[1] == false_lit);
+
+            // If 0th watch is true, then clause is already satisfied.
+            Lit first = c[0];
+            if (value(first) == l_True){
+                *j++ = &c;
+            }else{
+                // Look for new watch:
+                for (int k = 2; k < c.size(); k++)
+                    if (value(c[k]) != l_False){
+                        c[1] = c[k]; c[k] = false_lit;
+                        watches[toInt(~c[1])].push(&c);
+                        goto FoundWatch; }
+
+                // Did not find watch -- clause is unit under assignment:
+                *j++ = &c;
+                if (value(first) == l_False){
+                    confl = &c;
+                    qhead = trail.size();
+                    // Copy the remaining watches:
+                    while (i < end)
+                        *j++ = *i++;
+                }else
+                    uncheckedEnqueue(first, &c);
+            }
+        FoundWatch:;
+        }
+        ws.shrink(i - j);
+    }
+    propagations += num_props;
+    simpDB_props -= num_props;
+
+    return confl;
+}
+
+/*_________________________________________________________________________________________________
+|
+|  reduceDB : ()  ->  [void]
+|  
+|  Description:
+|    Remove half of the learnt clauses, minus the clauses locked by the current assignment. Locked
+|    clauses are clauses that are reason to some assignment. Binary clauses are never removed.
+|________________________________________________________________________________________________@*/
+struct reduceDB_lt { bool operator () (Clause* x, Clause* y) { return x->size() > 2 && (y->size() == 2 || x->activity() < y->activity()); } };
+void Solver::reduceDB()
+{
+    int     i, j;
+    double  extra_lim = cla_inc / learnts.size();    // Remove any clause below this activity
+
+    sort(learnts, reduceDB_lt());
+    for (i = j = 0; i < learnts.size() / 2; i++){
+        if (learnts[i]->size() > 2 && !locked(*learnts[i]))
+            removeClause(*learnts[i]);
+        else
+            learnts[j++] = learnts[i];
+    }
+    for (; i < learnts.size(); i++){
+        if (learnts[i]->size() > 2 && !locked(*learnts[i]) && learnts[i]->activity() < extra_lim)
+            removeClause(*learnts[i]);
+        else
+            learnts[j++] = learnts[i];
+    }
+    learnts.shrink(i - j);
+}
+
+
+void Solver::removeSatisfied(vec<Clause*>& cs)
+{
+    int i,j;
+    for (i = j = 0; i < cs.size(); i++){
+        if (satisfied(*cs[i]))
+            removeClause(*cs[i]);
+        else
+            cs[j++] = cs[i];
+    }
+    cs.shrink(i - j);
+}
+
+
+/*_________________________________________________________________________________________________
+|
+|  simplify : [void]  ->  [bool]
+|  
+|  Description:
+|    Simplify the clause database according to the current top-level assigment. Currently, the only
+|    thing done here is the removal of satisfied clauses, but more things can be put here.
+|________________________________________________________________________________________________@*/
+bool Solver::simplify()
+{
+    assert(decisionLevel() == 0);
+
+    if (!ok || propagate() != NULL)
+        return ok = false;
+
+    if (nAssigns() == simpDB_assigns || (simpDB_props > 0))
+        return true;
+
+    // Remove satisfied clauses:
+    removeSatisfied(learnts);
+    if (remove_satisfied)        // Can be turned off.
+        removeSatisfied(clauses);
+
+    // Remove fixed variables from the variable heap:
+    order_heap.filter(VarFilter(*this));
+
+    simpDB_assigns = nAssigns();
+    simpDB_props   = clauses_literals + learnts_literals;   // (shouldn't depend on stats really, but it will do for now)
+
+    return true;
+}
+
+
+/*_________________________________________________________________________________________________
+|
+|  search : (nof_conflicts : int) (nof_learnts : int) (params : const SearchParams&)  ->  [lbool]
+|  
+|  Description:
+|    Search for a model the specified number of conflicts, keeping the number of learnt clauses
+|    below the provided limit. NOTE! Use negative value for 'nof_conflicts' or 'nof_learnts' to
+|    indicate infinity.
+|  
+|  Output:
+|    'l_True' if a partial assigment that is consistent with respect to the clauseset is found. If
+|    all variables are decision variables, this means that the clause set is satisfiable. 'l_False'
+|    if the clause set is unsatisfiable. 'l_Undef' if the bound on number of conflicts is reached.
+|________________________________________________________________________________________________@*/
+lbool Solver::search(int nof_conflicts, int nof_learnts)
+{
+    assert(ok);
+    int         backtrack_level;
+    int         conflictC = 0;
+    vec<Lit>    learnt_clause;
+
+    starts++;
+
+    bool first = true;
+
+    for (;;){
+        Clause* confl = propagate();
+        if (confl != NULL){
+            // CONFLICT
+            conflicts++; conflictC++;
+            if (decisionLevel() == 0) return l_False;
+
+            first = false;
+
+            learnt_clause.clear();
+            analyze(confl, learnt_clause, backtrack_level);
+            cancelUntil(backtrack_level);
+            assert(value(learnt_clause[0]) == l_Undef);
+
+            if (learnt_clause.size() == 1){
+                uncheckedEnqueue(learnt_clause[0]);
+            }else{
+                Clause* c = Clause_new(learnt_clause, true);
+                learnts.push(c);
+                attachClause(*c);
+                claBumpActivity(*c);
+                uncheckedEnqueue(learnt_clause[0], c);
+            }
+
+            varDecayActivity();
+            claDecayActivity();
+
+        }else{
+            // NO CONFLICT
+
+            if (nof_conflicts >= 0 && conflictC >= nof_conflicts){
+                // Reached bound on number of conflicts:
+                progress_estimate = progressEstimate();
+                cancelUntil(0);
+                return l_Undef; }
+
+            // Simplify the set of problem clauses:
+            if (decisionLevel() == 0 && !simplify())
+                return l_False;
+
+            if (nof_learnts >= 0 && learnts.size()-nAssigns() >= nof_learnts)
+                // Reduce the set of learnt clauses:
+                reduceDB();
+
+            Lit next = lit_Undef;
+            while (decisionLevel() < assumptions.size()){
+                // Perform user provided assumption:
+                Lit p = assumptions[decisionLevel()];
+                if (value(p) == l_True){
+                    // Dummy decision level:
+                    newDecisionLevel();
+                }else if (value(p) == l_False){
+                    analyzeFinal(~p, conflict);
+                    return l_False;
+                }else{
+                    next = p;
+                    break;
+                }
+            }
+
+            if (next == lit_Undef){
+                // New variable decision:
+                decisions++;
+                next = pickBranchLit(polarity_mode, random_var_freq);
+
+                if (next == lit_Undef)
+                    // Model found:
+                    return l_True;
+            }
+
+            // Increase decision level and enqueue 'next'
+            assert(value(next) == l_Undef);
+            newDecisionLevel();
+            uncheckedEnqueue(next);
+        }
+    }
+}
+
+
+double Solver::progressEstimate() const
+{
+    double  progress = 0;
+    double  F = 1.0 / nVars();
+
+    for (int i = 0; i <= decisionLevel(); i++){
+        int beg = i == 0 ? 0 : trail_lim[i - 1];
+        int end = i == decisionLevel() ? trail.size() : trail_lim[i];
+        progress += pow(F, i) * (end - beg);
+    }
+
+    return progress / nVars();
+}
+
+
+bool Solver::solve(const vec<Lit>& assumps)
+{
+    model.clear();
+    conflict.clear();
+
+    if (!ok) return false;
+
+    assumps.copyTo(assumptions);
+
+    double  nof_conflicts = restart_first;
+    double  nof_learnts   = nClauses() * learntsize_factor;
+    lbool   status        = l_Undef;
+
+    if (verbosity >= 1){
+        reportf("============================[ Search Statistics ]==============================\n");
+        reportf("| Conflicts |          ORIGINAL         |          LEARNT          | Progress |\n");
+        reportf("|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |\n");
+        reportf("===============================================================================\n");
+    }
+
+    // Search:
+    while (status == l_Undef){
+        if (verbosity >= 1)
+            reportf("| %9d | %7d %8d %8d | %8d %8d %6.0f | %6.3f %% |\n", (int)conflicts, order_heap.size(), nClauses(), (int)clauses_literals, (int)nof_learnts, nLearnts(), (double)learnts_literals/nLearnts(), progress_estimate*100), fflush(stdout);
+        status = search((int)nof_conflicts, (int)nof_learnts);
+        nof_conflicts *= restart_inc;
+        nof_learnts   *= learntsize_inc;
+    }
+
+    if (verbosity >= 1)
+        reportf("===============================================================================\n");
+
+
+    if (status == l_True){
+        // Extend & copy model:
+        model.growTo(nVars());
+        for (int i = 0; i < nVars(); i++) model[i] = value(i);
+#ifndef NDEBUG
+        verifyModel();
+#endif
+    }else{
+        assert(status == l_False);
+        if (conflict.size() == 0)
+            ok = false;
+    }
+
+    cancelUntil(0);
+    return status == l_True;
+}
+
+//=================================================================================================
+// Debug methods:
+
+
+void Solver::verifyModel()
+{
+    bool failed = false;
+    for (int i = 0; i < clauses.size(); i++){
+        assert(clauses[i]->mark() == 0);
+        Clause& c = *clauses[i];
+        for (int j = 0; j < c.size(); j++)
+            if (modelValue(c[j]) == l_True)
+                goto next;
+
+        reportf("unsatisfied clause: ");
+        printClause(*clauses[i]);
+        reportf("\n");
+        failed = true;
+    next:;
+    }
+
+    assert(!failed);
+
+    reportf("Verified %d original clauses.\n", clauses.size());
+}
+
+
+void Solver::checkLiteralCount()
+{
+    // Check that sizes are calculated correctly:
+    int cnt = 0;
+    for (int i = 0; i < clauses.size(); i++)
+        if (clauses[i]->mark() == 0)
+            cnt += clauses[i]->size();
+
+    if ((int)clauses_literals != cnt){
+        fprintf(stderr, "literal count: %d, real value = %d\n", (int)clauses_literals, cnt);
+        assert((int)clauses_literals == cnt);
+    }
+}
diff --git a/examples/charm++/satisfiability/minisat/Solver.h b/examples/charm++/satisfiability/minisat/Solver.h
new file mode 100644 (file)
index 0000000..da89b55
--- /dev/null
@@ -0,0 +1,308 @@
+/****************************************************************************************[Solver.h]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+#ifndef Solver_h
+#define Solver_h
+
+#include <cstdio>
+
+#include "mtl/Vec.h"
+#include "mtl/minisatHeap.h"
+#include "mtl/Alg.h"
+
+#include "SolverTypes.h"
+
+#include <vector>
+
+using namespace std;
+
+//=================================================================================================
+// Solver -- the main class:
+
+
+bool seq_processing(int var_size, const vector< vector<int> >& clauses);
+
+    class Solver {
+public:
+
+    // Constructor/Destructor:
+    //
+    Solver();
+    ~Solver();
+
+
+    // Problem specification:
+    //
+    Var     newVar    (bool polarity = true, bool dvar = true); // Add a new variable with parameters specifying variable mode.
+    bool    addClause (vec<Lit>& ps);                           // Add a clause to the solver. NOTE! 'ps' may be shrunk by this method!
+
+    // Solving:
+    //
+    bool    simplify     ();                        // Removes already satisfied clauses.
+    bool    solve        (const vec<Lit>& assumps); // Search for a model that respects a given set of assumptions.
+    bool    solve        ();                        // Search without assumptions.
+    bool    okay         () const;                  // FALSE means solver is in a conflicting state
+
+    // Variable mode:
+    // 
+    void    setPolarity    (Var v, bool b); // Declare which polarity the decision heuristic should use for a variable. Requires mode 'polarity_user'.
+    void    setDecisionVar (Var v, bool b); // Declare if a variable should be eligible for selection in the decision heuristic.
+
+    // Read state:
+    //
+    lbool   value      (Var x) const;       // The current value of a variable.
+    lbool   value      (Lit p) const;       // The current value of a literal.
+    lbool   modelValue (Lit p) const;       // The value of a literal in the last model. The last call to solve must have been satisfiable.
+    int     nAssigns   ()      const;       // The current number of assigned literals.
+    int     nClauses   ()      const;       // The current number of original clauses.
+    int     nLearnts   ()      const;       // The current number of learnt clauses.
+    int     nVars      ()      const;       // The current number of variables.
+
+    // Extra results: (read-only member variable)
+    //
+    vec<lbool> model;             // If problem is satisfiable, this vector contains the model (if any).
+    vec<Lit>   conflict;          // If problem is unsatisfiable (possibly under assumptions),
+                                  // this vector represent the final conflict clause expressed in the assumptions.
+
+    // Mode of operation:
+    //
+    double    var_decay;          // Inverse of the variable activity decay factor.                                            (default 1 / 0.95)
+    double    clause_decay;       // Inverse of the clause activity decay factor.                                              (1 / 0.999)
+    double    random_var_freq;    // The frequency with which the decision heuristic tries to choose a random variable.        (default 0.02)
+    int       restart_first;      // The initial restart limit.                                                                (default 100)
+    double    restart_inc;        // The factor with which the restart limit is multiplied in each restart.                    (default 1.5)
+    double    learntsize_factor;  // The intitial limit for learnt clauses is a factor of the original clauses.                (default 1 / 3)
+    double    learntsize_inc;     // The limit for learnt clauses is multiplied with this factor each restart.                 (default 1.1)
+    bool      expensive_ccmin;    // Controls conflict clause minimization.                                                    (default TRUE)
+    int       polarity_mode;      // Controls which polarity the decision heuristic chooses. See enum below for allowed modes. (default polarity_false)
+    int       verbosity;          // Verbosity level. 0=silent, 1=some progress report                                         (default 0)
+
+    enum { polarity_true = 0, polarity_false = 1, polarity_user = 2, polarity_rnd = 3 };
+
+    // Statistics: (read-only member variable)
+    //
+    uint64_t starts, decisions, rnd_decisions, propagations, conflicts;
+    uint64_t clauses_literals, learnts_literals, max_literals, tot_literals;
+
+protected:
+
+    // Helper structures:
+    //
+    struct VarOrderLt {
+        const vec<double>&  activity;
+        bool operator () (Var x, Var y) const { return activity[x] > activity[y]; }
+        VarOrderLt(const vec<double>&  act) : activity(act) { }
+    };
+
+    friend class VarFilter;
+    struct VarFilter {
+        const Solver& s;
+        VarFilter(const Solver& _s) : s(_s) {}
+        bool operator()(Var v) const { return toLbool(s.assigns[v]) == l_Undef && s.decision_var[v]; }
+    };
+
+    // Solver state:
+    //
+    bool                ok;               // If FALSE, the constraints are already unsatisfiable. No part of the solver state may be used!
+    vec<Clause*>        clauses;          // List of problem clauses.
+    vec<Clause*>        learnts;          // List of learnt clauses.
+    double              cla_inc;          // Amount to bump next clause with.
+    vec<double>         activity;         // A heuristic measurement of the activity of a variable.
+    double              var_inc;          // Amount to bump next variable with.
+    vec<vec<Clause*> >  watches;          // 'watches[lit]' is a list of constraints watching 'lit' (will go there if literal becomes true).
+    vec<char>           assigns;          // The current assignments (lbool:s stored as char:s).
+    vec<char>           polarity;         // The preferred polarity of each variable.
+    vec<char>           decision_var;     // Declares if a variable is eligible for selection in the decision heuristic.
+    vec<Lit>            trail;            // Assignment stack; stores all assigments made in the order they were made.
+    vec<int>            trail_lim;        // Separator indices for different decision levels in 'trail'.
+    vec<Clause*>        reason;           // 'reason[var]' is the clause that implied the variables current value, or 'NULL' if none.
+    vec<int>            level;            // 'level[var]' contains the level at which the assignment was made.
+    int                 qhead;            // Head of queue (as index into the trail -- no more explicit propagation queue in MiniSat).
+    int                 simpDB_assigns;   // Number of top-level assignments since last execution of 'simplify()'.
+    int64_t             simpDB_props;     // Remaining number of propagations that must be made before next execution of 'simplify()'.
+    vec<Lit>            assumptions;      // Current set of assumptions provided to solve by the user.
+    Heap<VarOrderLt>    order_heap;       // A priority queue of variables ordered with respect to the variable activity.
+    double              random_seed;      // Used by the random variable selection.
+    double              progress_estimate;// Set by 'search()'.
+    bool                remove_satisfied; // Indicates whether possibly inefficient linear scan for satisfied clauses should be performed in 'simplify'.
+
+    // Temporaries (to reduce allocation overhead). Each variable is prefixed by the method in which it is
+    // used, exept 'seen' wich is used in several places.
+    //
+    vec<char>           seen;
+    vec<Lit>            analyze_stack;
+    vec<Lit>            analyze_toclear;
+    vec<Lit>            add_tmp;
+
+    // Main internal methods:
+    //
+    void     insertVarOrder   (Var x);                                                 // Insert a variable in the decision order priority queue.
+    Lit      pickBranchLit    (int polarity_mode, double random_var_freq);             // Return the next decision variable.
+    void     newDecisionLevel ();                                                      // Begins a new decision level.
+    void     uncheckedEnqueue (Lit p, Clause* from = NULL);                            // Enqueue a literal. Assumes value of literal is undefined.
+    bool     enqueue          (Lit p, Clause* from = NULL);                            // Test if fact 'p' contradicts current state, enqueue otherwise.
+    Clause*  propagate        ();                                                      // Perform unit propagation. Returns possibly conflicting clause.
+    void     cancelUntil      (int level);                                             // Backtrack until a certain level.
+    void     analyze          (Clause* confl, vec<Lit>& out_learnt, int& out_btlevel); // (bt = backtrack)
+    void     analyzeFinal     (Lit p, vec<Lit>& out_conflict);                         // COULD THIS BE IMPLEMENTED BY THE ORDINARIY "analyze" BY SOME REASONABLE GENERALIZATION?
+    bool     litRedundant     (Lit p, uint32_t abstract_levels);                       // (helper method for 'analyze()')
+    lbool    search           (int nof_conflicts, int nof_learnts);                    // Search for a given number of conflicts.
+    void     reduceDB         ();                                                      // Reduce the set of learnt clauses.
+    void     removeSatisfied  (vec<Clause*>& cs);                                      // Shrink 'cs' to contain only non-satisfied clauses.
+
+    // Maintaining Variable/Clause activity:
+    //
+    void     varDecayActivity ();                      // Decay all variables with the specified factor. Implemented by increasing the 'bump' value instead.
+    void     varBumpActivity  (Var v);                 // Increase a variable with the current 'bump' value.
+    void     claDecayActivity ();                      // Decay all clauses with the specified factor. Implemented by increasing the 'bump' value instead.
+    void     claBumpActivity  (Clause& c);             // Increase a clause with the current 'bump' value.
+
+    // Operations on clauses:
+    //
+    void     attachClause     (Clause& c);             // Attach a clause to watcher lists.
+    void     detachClause     (Clause& c);             // Detach a clause to watcher lists.
+    void     removeClause     (Clause& c);             // Detach and free a clause.
+    bool     locked           (const Clause& c) const; // Returns TRUE if a clause is a reason for some implication in the current state.
+    bool     satisfied        (const Clause& c) const; // Returns TRUE if a clause is satisfied in the current state.
+
+    // Misc:
+    //
+    int      decisionLevel    ()      const; // Gives the current decisionlevel.
+    uint32_t abstractLevel    (Var x) const; // Used to represent an abstraction of sets of decision levels.
+    double   progressEstimate ()      const; // DELETE THIS ?? IT'S NOT VERY USEFUL ...
+
+    // Debug:
+    void     printLit         (Lit l);
+    template<class C>
+    void     printClause      (const C& c);
+    void     verifyModel      ();
+    void     checkLiteralCount();
+
+    // Static helpers:
+    //
+
+    // Returns a random float 0 <= x < 1. Seed must never be 0.
+    static inline double drand(double& seed) {
+        seed *= 1389796;
+        int q = (int)(seed / 2147483647);
+        seed -= (double)q * 2147483647;
+        return seed / 2147483647; }
+
+    // Returns a random integer 0 <= x < size. Seed must never be 0.
+    static inline int irand(double& seed, int size) {
+        return (int)(drand(seed) * size); }
+};
+
+
+//=================================================================================================
+// Implementation of inline methods:
+
+
+inline void Solver::insertVarOrder(Var x) {
+    if (!order_heap.inHeap(x) && decision_var[x]) order_heap.insert(x); }
+
+inline void Solver::varDecayActivity() { var_inc *= var_decay; }
+inline void Solver::varBumpActivity(Var v) {
+    if ( (activity[v] += var_inc) > 1e100 ) {
+        // Rescale:
+        for (int i = 0; i < nVars(); i++)
+            activity[i] *= 1e-100;
+        var_inc *= 1e-100; }
+
+    // Update order_heap with respect to new activity:
+    if (order_heap.inHeap(v))
+        order_heap.decrease(v); }
+
+inline void Solver::claDecayActivity() { cla_inc *= clause_decay; }
+inline void Solver::claBumpActivity (Clause& c) {
+        if ( (c.activity() += cla_inc) > 1e20 ) {
+            // Rescale:
+            for (int i = 0; i < learnts.size(); i++)
+                learnts[i]->activity() *= 1e-20;
+            cla_inc *= 1e-20; } }
+
+inline bool     Solver::enqueue         (Lit p, Clause* from)   { return value(p) != l_Undef ? value(p) != l_False : (uncheckedEnqueue(p, from), true); }
+inline bool     Solver::locked          (const Clause& c) const { return reason[var(c[0])] == &c && value(c[0]) == l_True; }
+inline void     Solver::newDecisionLevel()                      { trail_lim.push(trail.size()); }
+
+inline int      Solver::decisionLevel ()      const   { return trail_lim.size(); }
+inline uint32_t Solver::abstractLevel (Var x) const   { return 1 << (level[x] & 31); }
+inline lbool    Solver::value         (Var x) const   { return toLbool(assigns[x]); }
+inline lbool    Solver::value         (Lit p) const   { return toLbool(assigns[var(p)]) ^ sign(p); }
+inline lbool    Solver::modelValue    (Lit p) const   { return model[var(p)] ^ sign(p); }
+inline int      Solver::nAssigns      ()      const   { return trail.size(); }
+inline int      Solver::nClauses      ()      const   { return clauses.size(); }
+inline int      Solver::nLearnts      ()      const   { return learnts.size(); }
+inline int      Solver::nVars         ()      const   { return assigns.size(); }
+inline void     Solver::setPolarity   (Var v, bool b) { polarity    [v] = (char)b; }
+inline void     Solver::setDecisionVar(Var v, bool b) { decision_var[v] = (char)b; if (b) { insertVarOrder(v); } }
+inline bool     Solver::solve         ()              { vec<Lit> tmp; return solve(tmp); }
+inline bool     Solver::okay          ()      const   { return ok; }
+
+
+
+//=================================================================================================
+// Debug + etc:
+
+
+#define reportf(format, args...) ( fflush(stdout), fprintf(stderr, format, ## args), fflush(stderr) )
+
+static inline void logLit(FILE* f, Lit l)
+{
+    fprintf(f, "%sx%d", sign(l) ? "~" : "", var(l)+1);
+}
+
+static inline void logLits(FILE* f, const vec<Lit>& ls)
+{
+    fprintf(f, "[ ");
+    if (ls.size() > 0){
+        logLit(f, ls[0]);
+        for (int i = 1; i < ls.size(); i++){
+            fprintf(f, ", ");
+            logLit(f, ls[i]);
+        }
+    }
+    fprintf(f, "] ");
+}
+
+static inline const char* showBool(bool b) { return b ? "true" : "false"; }
+
+
+// Just like 'assert()' but expression will be evaluated in the release version as well.
+static inline void check(bool expr) { assert(expr); }
+
+
+inline void Solver::printLit(Lit l)
+{
+    reportf("%s%d:%c", sign(l) ? "-" : "", var(l)+1, value(l) == l_True ? '1' : (value(l) == l_False ? '0' : 'X'));
+}
+
+
+template<class C>
+inline void Solver::printClause(const C& c)
+{
+    for (int i = 0; i < c.size(); i++){
+        printLit(c[i]);
+        fprintf(stderr, " ");
+    }
+}
+
+
+//=================================================================================================
+#endif
diff --git a/examples/charm++/satisfiability/minisat/SolverTypes.h b/examples/charm++/satisfiability/minisat/SolverTypes.h
new file mode 100644 (file)
index 0000000..47e3023
--- /dev/null
@@ -0,0 +1,197 @@
+/***********************************************************************************[SolverTypes.h]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+
+#ifndef SolverTypes_h
+#define SolverTypes_h
+
+#include <cassert>
+#include <stdint.h>
+
+//=================================================================================================
+// Variables, literals, lifted booleans, clauses:
+
+
+// NOTE! Variables are just integers. No abstraction here. They should be chosen from 0..N,
+// so that they can be used as array indices.
+
+typedef int Var;
+#define var_Undef (-1)
+
+
+class Lit {
+    int     x;
+ public:
+    Lit() : x(2*var_Undef)                                              { }   // (lit_Undef)
+    explicit Lit(Var var, bool sign = false) : x((var+var) + (int)sign) { }
+
+    // Don't use these for constructing/deconstructing literals. Use the normal constructors instead.
+    friend int  toInt       (Lit p);  // Guarantees small, positive integers suitable for array indexing.
+    friend Lit  toLit       (int i);  // Inverse of 'toInt()'
+    friend Lit  operator   ~(Lit p);
+    friend bool sign        (Lit p);
+    friend int  var         (Lit p);
+    friend Lit  unsign      (Lit p);
+    friend Lit  id          (Lit p, bool sgn);
+
+    bool operator == (Lit p) const { return x == p.x; }
+    bool operator != (Lit p) const { return x != p.x; }
+    bool operator <  (Lit p) const { return x < p.x;  } // '<' guarantees that p, ~p are adjacent in the ordering.
+};
+
+inline  int  toInt       (Lit p)           { return p.x; }
+inline  Lit  toLit       (int i)           { Lit p; p.x = i; return p; }
+inline  Lit  operator   ~(Lit p)           { Lit q; q.x = p.x ^ 1; return q; }
+inline  bool sign        (Lit p)           { return p.x & 1; }
+inline  int  var         (Lit p)           { return p.x >> 1; }
+inline  Lit  unsign      (Lit p)           { Lit q; q.x = p.x & ~1; return q; }
+inline  Lit  id          (Lit p, bool sgn) { Lit q; q.x = p.x ^ (int)sgn; return q; }
+
+const Lit lit_Undef(var_Undef, false);  // }- Useful special constants.
+const Lit lit_Error(var_Undef, true );  // }
+
+
+//=================================================================================================
+// Lifted booleans:
+
+
+class lbool {
+    char     value;
+    explicit lbool(int v) : value(v) { }
+
+public:
+    lbool()       : value(0) { }
+    lbool(bool x) : value((int)x*2-1) { }
+    int toInt(void) const { return value; }
+
+    bool  operator == (lbool b) const { return value == b.value; }
+    bool  operator != (lbool b) const { return value != b.value; }
+    lbool operator ^ (bool b) const { return b ? lbool(-value) : lbool(value); }
+
+    friend int   toInt  (lbool l);
+    friend lbool toLbool(int   v);
+};
+inline int   toInt  (lbool l) { return l.toInt(); }
+inline lbool toLbool(int   v) { return lbool(v);  }
+
+const lbool l_True  = toLbool( 1);
+const lbool l_False = toLbool(-1);
+const lbool l_Undef = toLbool( 0);
+
+//=================================================================================================
+// Clause -- a simple class for representing a clause:
+
+
+class Clause {
+    uint32_t size_etc;
+    union { float act; uint32_t abst; } extra;
+    Lit     data[0];
+
+public:
+    void calcAbstraction() {
+        uint32_t abstraction = 0;
+        for (int i = 0; i < size(); i++)
+            abstraction |= 1 << (var(data[i]) & 31);
+        extra.abst = abstraction;  }
+
+    // NOTE: This constructor cannot be used directly (doesn't allocate enough memory).
+    template<class V>
+    Clause(const V& ps, bool learnt) {
+        size_etc = (ps.size() << 3) | (uint32_t)learnt;
+        for (int i = 0; i < ps.size(); i++) data[i] = ps[i];
+        if (learnt) extra.act = 0; else calcAbstraction(); }
+
+    // -- use this function instead:
+    template<class V>
+    friend Clause* Clause_new(const V& ps, bool learnt = false) {
+        assert(sizeof(Lit)      == sizeof(uint32_t));
+        assert(sizeof(float)    == sizeof(uint32_t));
+        void* mem = malloc(sizeof(Clause) + sizeof(uint32_t)*(ps.size()));
+        return new (mem) Clause(ps, learnt); }
+
+    int          size        ()      const   { return size_etc >> 3; }
+    void         shrink      (int i)         { assert(i <= size()); size_etc = (((size_etc >> 3) - i) << 3) | (size_etc & 7); }
+    void         pop         ()              { shrink(1); }
+    bool         learnt      ()      const   { return size_etc & 1; }
+    uint32_t     mark        ()      const   { return (size_etc >> 1) & 3; }
+    void         mark        (uint32_t m)    { size_etc = (size_etc & ~6) | ((m & 3) << 1); }
+    const Lit&   last        ()      const   { return data[size()-1]; }
+
+    // NOTE: somewhat unsafe to change the clause in-place! Must manually call 'calcAbstraction' afterwards for
+    //       subsumption operations to behave correctly.
+    Lit&         operator [] (int i)         { return data[i]; }
+    Lit          operator [] (int i) const   { return data[i]; }
+    operator const Lit* (void) const         { return data; }
+
+    float&       activity    ()              { return extra.act; }
+    uint32_t     abstraction () const { return extra.abst; }
+
+    Lit          subsumes    (const Clause& other) const;
+    void         strengthen  (Lit p);
+};
+
+
+/*_________________________________________________________________________________________________
+|
+|  subsumes : (other : const Clause&)  ->  Lit
+|  
+|  Description:
+|       Checks if clause subsumes 'other', and at the same time, if it can be used to simplify 'other'
+|       by subsumption resolution.
+|  
+|    Result:
+|       lit_Error  - No subsumption or simplification
+|       lit_Undef  - Clause subsumes 'other'
+|       p          - The literal p can be deleted from 'other'
+|________________________________________________________________________________________________@*/
+inline Lit Clause::subsumes(const Clause& other) const
+{
+    if (other.size() < size() || (extra.abst & ~other.extra.abst) != 0)
+        return lit_Error;
+
+    Lit        ret = lit_Undef;
+    const Lit* c  = (const Lit*)(*this);
+    const Lit* d  = (const Lit*)other;
+
+    for (int i = 0; i < size(); i++) {
+        // search for c[i] or ~c[i]
+        for (int j = 0; j < other.size(); j++)
+            if (c[i] == d[j])
+                goto ok;
+            else if (ret == lit_Undef && c[i] == ~d[j]){
+                ret = c[i];
+                goto ok;
+            }
+
+        // did not find it
+        return lit_Error;
+    ok:;
+    }
+
+    return ret;
+}
+
+
+inline void Clause::strengthen(Lit p)
+{
+    remove(*this, p);
+    calcAbstraction();
+}
+
+#endif
diff --git a/examples/charm++/satisfiability/minisat/mtl/Alg.h b/examples/charm++/satisfiability/minisat/mtl/Alg.h
new file mode 100644 (file)
index 0000000..240962d
--- /dev/null
@@ -0,0 +1,57 @@
+/*******************************************************************************************[Alg.h]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+#ifndef Alg_h
+#define Alg_h
+
+//=================================================================================================
+// Useful functions on vectors
+
+
+#if 1
+template<class V, class T>
+static inline void remove(V& ts, const T& t)
+{
+    int j = 0;
+    for (; j < ts.size() && ts[j] != t; j++);
+    assert(j < ts.size());
+    for (; j < ts.size()-1; j++) ts[j] = ts[j+1];
+    ts.pop();
+}
+#else
+template<class V, class T>
+static inline void remove(V& ts, const T& t)
+{
+    int j = 0;
+    for (; j < ts.size() && ts[j] != t; j++);
+    assert(j < ts.size());
+    ts[j] = ts.last();
+    ts.pop();
+}
+#endif
+
+template<class V, class T>
+static inline bool find(V& ts, const T& t)
+{
+    int j = 0;
+    for (; j < ts.size() && ts[j] != t; j++);
+    return j < ts.size();
+}
+
+#endif
diff --git a/examples/charm++/satisfiability/minisat/mtl/BasicHeap.h b/examples/charm++/satisfiability/minisat/mtl/BasicHeap.h
new file mode 100644 (file)
index 0000000..556d98f
--- /dev/null
@@ -0,0 +1,98 @@
+/******************************************************************************************[Heap.h]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+#ifndef BasicHeap_h
+#define BasicHeap_h
+
+#include "Vec.h"
+
+//=================================================================================================
+// A heap implementation with support for decrease/increase key.
+
+
+template<class Comp>
+class BasicHeap {
+    Comp     lt;
+    vec<int> heap;     // heap of ints
+
+    // Index "traversal" functions
+    static inline int left  (int i) { return i*2+1; }
+    static inline int right (int i) { return (i+1)*2; }
+    static inline int parent(int i) { return (i-1) >> 1; }
+
+    inline void percolateUp(int i)
+    {
+        int x = heap[i];
+        while (i != 0 && lt(x, heap[parent(i)])){
+            heap[i]          = heap[parent(i)];
+            i                = parent(i);
+        }
+        heap   [i] = x;
+    }
+
+
+    inline void percolateDown(int i)
+    {
+        int x = heap[i];
+        while (left(i) < heap.size()){
+            int child = right(i) < heap.size() && lt(heap[right(i)], heap[left(i)]) ? right(i) : left(i);
+            if (!lt(heap[child], x)) break;
+            heap[i]          = heap[child];
+            i                = child;
+        }
+        heap[i] = x;
+    }
+
+
+    bool heapProperty(int i) {
+        return i >= heap.size()
+            || ((i == 0 || !lt(heap[i], heap[parent(i)])) && heapProperty(left(i)) && heapProperty(right(i))); }
+
+
+  public:
+    BasicHeap(const C& c) : comp(c) { }
+
+    int  size      ()                     const { return heap.size(); }
+    bool empty     ()                     const { return heap.size() == 0; }
+    int  operator[](int index)            const { return heap[index+1]; }
+    void clear     (bool dealloc = false)       { heap.clear(dealloc); }
+    void insert    (int n)                      { heap.push(n); percolateUp(heap.size()-1); }
+
+
+    int  removeMin() {
+        int r   = heap[0];
+        heap[0] = heap.last();
+        heap.pop();
+        if (heap.size() > 1) percolateDown(0);
+        return r; 
+    }
+
+
+    // DEBUG: consistency checking
+    bool heapProperty() {
+        return heapProperty(1); }
+
+
+    // COMPAT: should be removed
+    int  getmin    ()      { return removeMin(); }
+};
+
+
+//=================================================================================================
+#endif
diff --git a/examples/charm++/satisfiability/minisat/mtl/BoxedVec.h b/examples/charm++/satisfiability/minisat/mtl/BoxedVec.h
new file mode 100644 (file)
index 0000000..bddf410
--- /dev/null
@@ -0,0 +1,147 @@
+/*******************************************************************************************[Vec.h]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+#ifndef BoxedVec_h
+#define BoxedVec_h
+
+#include <cstdlib>
+#include <cassert>
+#include <new>
+
+//=================================================================================================
+// Automatically resizable arrays
+//
+// NOTE! Don't use this vector on datatypes that cannot be re-located in memory (with realloc)
+
+template<class T>
+class bvec {
+
+    static inline int imin(int x, int y) {
+        int mask = (x-y) >> (sizeof(int)*8-1);
+        return (x&mask) + (y&(~mask)); }
+
+    static inline int imax(int x, int y) {
+        int mask = (y-x) >> (sizeof(int)*8-1);
+        return (x&mask) + (y&(~mask)); }
+
+    struct Vec_t {
+        int sz;
+        int cap;
+        T   data[0];
+
+        static Vec_t* alloc(Vec_t* x, int size){
+            x = (Vec_t*)realloc((void*)x, sizeof(Vec_t) + sizeof(T)*size);
+            x->cap = size;
+            return x;
+        }
+        
+    };
+
+    Vec_t* ref;
+
+    static const int init_size = 2;
+    static int   nextSize (int current) { return (current * 3 + 1) >> 1; }
+    static int   fitSize  (int needed)  { int x; for (x = init_size; needed > x; x = nextSize(x)); return x; }
+
+    void fill (int size) {
+        assert(ref != NULL);
+        for (T* i = ref->data; i < ref->data + size; i++)
+            new (i) T();
+    }
+
+    void fill (int size, const T& pad) {
+        assert(ref != NULL);
+        for (T* i = ref->data; i < ref->data + size; i++)
+            new (i) T(pad);
+    }
+
+    // Don't allow copying (error prone):
+    altvec<T>&  operator = (altvec<T>& other) { assert(0); }
+    altvec (altvec<T>& other)                  { assert(0); }
+
+public:
+    void     clear  (bool dealloc = false) { 
+        if (ref != NULL){
+            for (int i = 0; i < ref->sz; i++) 
+                (*ref).data[i].~T();
+
+            if (dealloc) { 
+                free(ref); ref = NULL; 
+            }else 
+                ref->sz = 0;
+        } 
+    }
+
+    // Constructors:
+    altvec(void)                   : ref (NULL) { }
+    altvec(int size)               : ref (Vec_t::alloc(NULL, fitSize(size))) { fill(size);      ref->sz = size; }
+    altvec(int size, const T& pad) : ref (Vec_t::alloc(NULL, fitSize(size))) { fill(size, pad); ref->sz = size; }
+   ~altvec(void) { clear(true); }
+
+    // Ownership of underlying array:
+    operator T*       (void)           { return ref->data; }     // (unsafe but convenient)
+    operator const T* (void) const     { return ref->data; }
+
+    // Size operations:
+    int      size   (void) const       { return ref != NULL ? ref->sz : 0; }
+
+    void     pop    (void)             { assert(ref != NULL && ref->sz > 0); int last = --ref->sz; ref->data[last].~T(); }
+    void     push   (const T& elem) {
+        int size = ref != NULL ? ref->sz  : 0;
+        int cap  = ref != NULL ? ref->cap : 0;
+        if (size == cap){
+            cap = cap != 0 ? nextSize(cap) : init_size;
+            ref = Vec_t::alloc(ref, cap); 
+        }
+        //new (&ref->data[size]) T(elem); 
+        ref->data[size] = elem; 
+        ref->sz = size+1; 
+    }
+
+    void     push   () {
+        int size = ref != NULL ? ref->sz  : 0;
+        int cap  = ref != NULL ? ref->cap : 0;
+        if (size == cap){
+            cap = cap != 0 ? nextSize(cap) : init_size;
+            ref = Vec_t::alloc(ref, cap); 
+        }
+        new (&ref->data[size]) T(); 
+        ref->sz = size+1; 
+    }
+
+    void     shrink (int nelems)             { for (int i = 0; i < nelems; i++) pop(); }
+    void     shrink_(int nelems)             { for (int i = 0; i < nelems; i++) pop(); }
+    void     growTo (int size)               { while (this->size() < size) push(); }
+    void     growTo (int size, const T& pad) { while (this->size() < size) push(pad); }
+    void     capacity (int size)             { growTo(size); }
+
+    const T& last  (void) const              { return ref->data[ref->sz-1]; }
+    T&       last  (void)                    { return ref->data[ref->sz-1]; }
+
+    // Vector interface:
+    const T& operator [] (int index) const  { return ref->data[index]; }
+    T&       operator [] (int index)        { return ref->data[index]; }
+
+    void copyTo(altvec<T>& copy) const { copy.clear(); for (int i = 0; i < size(); i++) copy.push(ref->data[i]); }
+    void moveTo(altvec<T>& dest) { dest.clear(true); dest.ref = ref; ref = NULL; }
+
+};
+
+
+#endif
diff --git a/examples/charm++/satisfiability/minisat/mtl/Map.h b/examples/charm++/satisfiability/minisat/mtl/Map.h
new file mode 100644 (file)
index 0000000..b6d76a3
--- /dev/null
@@ -0,0 +1,118 @@
+/*******************************************************************************************[Map.h]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+#ifndef Map_h
+#define Map_h
+
+#include <stdint.h>
+
+#include "Vec.h"
+
+//=================================================================================================
+// Default hash/equals functions
+//
+
+template<class K> struct Hash  { uint32_t operator()(const K& k)               const { return hash(k);  } };
+template<class K> struct Equal { bool     operator()(const K& k1, const K& k2) const { return k1 == k2; } };
+
+template<class K> struct DeepHash  { uint32_t operator()(const K* k)               const { return hash(*k);  } };
+template<class K> struct DeepEqual { bool     operator()(const K* k1, const K* k2) const { return *k1 == *k2; } };
+
+//=================================================================================================
+// Some primes
+//
+
+static const int nprimes          = 25;
+static const int primes [nprimes] = { 31, 73, 151, 313, 643, 1291, 2593, 5233, 10501, 21013, 42073, 84181, 168451, 337219, 674701, 1349473, 2699299, 5398891, 10798093, 21596719, 43193641, 86387383, 172775299, 345550609, 691101253 };
+
+//=================================================================================================
+// Hash table implementation of Maps
+//
+
+template<class K, class D, class H = Hash<K>, class E = Equal<K> >
+class Map {
+    struct Pair { K key; D data; };
+
+    H          hash;
+    E          equals;
+
+    vec<Pair>* table;
+    int        cap;
+    int        size;
+
+    // Don't allow copying (error prone):
+    Map<K,D,H,E>&  operator = (Map<K,D,H,E>& other) { assert(0); }
+                   Map        (Map<K,D,H,E>& other) { assert(0); }
+
+    int32_t index  (const K& k) const { return hash(k) % cap; }
+    void   _insert (const K& k, const D& d) { table[index(k)].push(); table[index(k)].last().key = k; table[index(k)].last().data = d; }
+    void    rehash () {
+        const vec<Pair>* old = table;
+
+        int newsize = primes[0];
+        for (int i = 1; newsize <= cap && i < nprimes; i++)
+           newsize = primes[i];
+
+        table = new vec<Pair>[newsize];
+
+        for (int i = 0; i < cap; i++){
+            for (int j = 0; j < old[i].size(); j++){
+                _insert(old[i][j].key, old[i][j].data); }}
+
+        delete [] old;
+
+        cap = newsize;
+    }
+
+    
+    public:
+
+     Map () : table(NULL), cap(0), size(0) {}
+     Map (const H& h, const E& e) : Map(), hash(h), equals(e) {}
+    ~Map () { delete [] table; }
+
+    void insert (const K& k, const D& d) { if (size+1 > cap / 2) rehash(); _insert(k, d); size++; }
+    bool peek   (const K& k, D& d) {
+        if (size == 0) return false;
+        const vec<Pair>& ps = table[index(k)];
+        for (int i = 0; i < ps.size(); i++)
+            if (equals(ps[i].key, k)){
+                d = ps[i].data;
+                return true; } 
+        return false;
+    }
+
+    void remove (const K& k) {
+        assert(table != NULL);
+        vec<Pair>& ps = table[index(k)];
+        int j = 0;
+        for (; j < ps.size() && !equals(ps[j].key, k); j++);
+        assert(j < ps.size());
+        ps[j] = ps.last();
+        ps.pop();
+    }
+
+    void clear  () {
+        cap = size = 0;
+        delete [] table;
+        table = NULL;
+    }
+};
+
+#endif
diff --git a/examples/charm++/satisfiability/minisat/mtl/Queue.h b/examples/charm++/satisfiability/minisat/mtl/Queue.h
new file mode 100644 (file)
index 0000000..2cc110c
--- /dev/null
@@ -0,0 +1,82 @@
+/*****************************************************************************************[Queue.h]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+#ifndef Queue_h
+#define Queue_h
+
+#include "Vec.h"
+
+//=================================================================================================
+
+
+template <class T>
+class Queue {
+    vec<T>  elems;
+    int     first;
+
+public:
+    Queue(void) : first(0) { }
+
+    void insert(T x)   { elems.push(x); }
+    T    peek  () const { return elems[first]; }
+    void pop   () { first++; }
+
+    void clear(bool dealloc = false)   { elems.clear(dealloc); first = 0; }
+    int  size(void)    { return elems.size() - first; }
+
+    //bool has(T x) { for (int i = first; i < elems.size(); i++) if (elems[i] == x) return true; return false; }
+
+    const T& operator [] (int index) const  { return elems[first + index]; }
+
+};
+
+//template<class T>
+//class Queue {
+//    vec<T>  buf;
+//    int     first;
+//    int     end;
+//
+//public:
+//    typedef T Key;
+//
+//    Queue() : buf(1), first(0), end(0) {}
+//
+//    void clear () { buf.shrinkTo(1); first = end = 0; }
+//    int  size  () { return (end >= first) ? end - first : end - first + buf.size(); }
+//
+//    T    peek  () { assert(first != end); return buf[first]; }
+//    void pop   () { assert(first != end); first++; if (first == buf.size()) first = 0; }
+//    void insert(T elem) {   // INVARIANT: buf[end] is always unused
+//        buf[end++] = elem;
+//        if (end == buf.size()) end = 0;
+//        if (first == end){  // Resize:
+//            vec<T>  tmp((buf.size()*3 + 1) >> 1);
+//            //**/printf("queue alloc: %d elems (%.1f MB)\n", tmp.size(), tmp.size() * sizeof(T) / 1000000.0);
+//            int     i = 0;
+//            for (int j = first; j < buf.size(); j++) tmp[i++] = buf[j];
+//            for (int j = 0    ; j < end       ; j++) tmp[i++] = buf[j];
+//            first = 0;
+//            end   = buf.size();
+//            tmp.moveTo(buf);
+//        }
+//    }
+//};
+
+//=================================================================================================
+#endif
diff --git a/examples/charm++/satisfiability/minisat/mtl/Sort.h b/examples/charm++/satisfiability/minisat/mtl/Sort.h
new file mode 100644 (file)
index 0000000..1f301f5
--- /dev/null
@@ -0,0 +1,93 @@
+/******************************************************************************************[Sort.h]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+#ifndef Sort_h
+#define Sort_h
+
+#include "Vec.h"
+
+//=================================================================================================
+// Some sorting algorithms for vec's
+
+
+template<class T>
+struct LessThan_default {
+    bool operator () (T x, T y) { return x < y; }
+};
+
+
+template <class T, class LessThan>
+void selectionSort(T* array, int size, LessThan lt)
+{
+    int     i, j, best_i;
+    T       tmp;
+
+    for (i = 0; i < size-1; i++){
+        best_i = i;
+        for (j = i+1; j < size; j++){
+            if (lt(array[j], array[best_i]))
+                best_i = j;
+        }
+        tmp = array[i]; array[i] = array[best_i]; array[best_i] = tmp;
+    }
+}
+template <class T> static inline void selectionSort(T* array, int size) {
+    selectionSort(array, size, LessThan_default<T>()); }
+
+template <class T, class LessThan>
+void sort(T* array, int size, LessThan lt)
+{
+    if (size <= 15)
+        selectionSort(array, size, lt);
+
+    else{
+        T           pivot = array[size / 2];
+        T           tmp;
+        int         i = -1;
+        int         j = size;
+
+        for(;;){
+            do i++; while(lt(array[i], pivot));
+            do j--; while(lt(pivot, array[j]));
+
+            if (i >= j) break;
+
+            tmp = array[i]; array[i] = array[j]; array[j] = tmp;
+        }
+
+        sort(array    , i     , lt);
+        sort(&array[i], size-i, lt);
+    }
+}
+template <class T> static inline void sort(T* array, int size) {
+    sort(array, size, LessThan_default<T>()); }
+
+
+//=================================================================================================
+// For 'vec's:
+
+
+template <class T, class LessThan> void sort(vec<T>& v, LessThan lt) {
+    sort((T*)v, v.size(), lt); }
+template <class T> void sort(vec<T>& v) {
+    sort(v, LessThan_default<T>()); }
+
+
+//=================================================================================================
+#endif
diff --git a/examples/charm++/satisfiability/minisat/mtl/Vec.h b/examples/charm++/satisfiability/minisat/mtl/Vec.h
new file mode 100644 (file)
index 0000000..e780aa1
--- /dev/null
@@ -0,0 +1,133 @@
+/*******************************************************************************************[Vec.h]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+#ifndef Vec_h
+#define Vec_h
+
+#include <cstdlib>
+#include <cassert>
+#include <new>
+
+//=================================================================================================
+// Automatically resizable arrays
+//
+// NOTE! Don't use this vector on datatypes that cannot be re-located in memory (with realloc)
+
+template<class T>
+class vec {
+    T*  data;
+    int sz;
+    int cap;
+
+    void     init(int size, const T& pad);
+    void     grow(int min_cap);
+
+    // Don't allow copying (error prone):
+    vec<T>&  operator = (vec<T>& other) { assert(0); return *this; }
+             vec        (vec<T>& other) { assert(0); }
+
+    static inline int imin(int x, int y) {
+        int mask = (x-y) >> (sizeof(int)*8-1);
+        return (x&mask) + (y&(~mask)); }
+
+    static inline int imax(int x, int y) {
+        int mask = (y-x) >> (sizeof(int)*8-1);
+        return (x&mask) + (y&(~mask)); }
+
+public:
+    // Types:
+    typedef int Key;
+    typedef T   Datum;
+
+    // Constructors:
+    vec(void)                   : data(NULL) , sz(0)   , cap(0)    { }
+    vec(int size)               : data(NULL) , sz(0)   , cap(0)    { growTo(size); }
+    vec(int size, const T& pad) : data(NULL) , sz(0)   , cap(0)    { growTo(size, pad); }
+    vec(T* array, int size)     : data(array), sz(size), cap(size) { }      // (takes ownership of array -- will be deallocated with 'free()')
+   ~vec(void)                                                      { clear(true); }
+
+    // Ownership of underlying array:
+    T*       release  (void)           { T* ret = data; data = NULL; sz = 0; cap = 0; return ret; }
+    operator T*       (void)           { return data; }     // (unsafe but convenient)
+    operator const T* (void) const     { return data; }
+
+    // Size operations:
+    int      size   (void) const       { return sz; }
+    void     shrink (int nelems)       { assert(nelems <= sz); for (int i = 0; i < nelems; i++) sz--, data[sz].~T(); }
+    void     shrink_(int nelems)       { assert(nelems <= sz); sz -= nelems; }
+    void     pop    (void)             { sz--, data[sz].~T(); }
+    void     growTo (int size);
+    void     growTo (int size, const T& pad);
+    void     clear  (bool dealloc = false);
+    void     capacity (int size) { grow(size); }
+
+    // Stack interface:
+#if 1
+    void     push  (void)              { if (sz == cap) { cap = imax(2, (cap*3+1)>>1); data = (T*)realloc(data, cap * sizeof(T)); } new (&data[sz]) T(); sz++; }
+    //void     push  (const T& elem)     { if (sz == cap) { cap = imax(2, (cap*3+1)>>1); data = (T*)realloc(data, cap * sizeof(T)); } new (&data[sz]) T(elem); sz++; }
+    void     push  (const T& elem)     { if (sz == cap) { cap = imax(2, (cap*3+1)>>1); data = (T*)realloc(data, cap * sizeof(T)); } data[sz++] = elem; }
+    void     push_ (const T& elem)     { assert(sz < cap); data[sz++] = elem; }
+#else
+    void     push  (void)              { if (sz == cap) grow(sz+1); new (&data[sz]) T()    ; sz++; }
+    void     push  (const T& elem)     { if (sz == cap) grow(sz+1); new (&data[sz]) T(elem); sz++; }
+#endif
+
+    const T& last  (void) const        { return data[sz-1]; }
+    T&       last  (void)              { return data[sz-1]; }
+
+    // Vector interface:
+    const T& operator [] (int index) const  { return data[index]; }
+    T&       operator [] (int index)        { return data[index]; }
+
+
+    // Duplicatation (preferred instead):
+    void copyTo(vec<T>& copy) const { copy.clear(); copy.growTo(sz); for (int i = 0; i < sz; i++) new (&copy[i]) T(data[i]); }
+    void moveTo(vec<T>& dest) { dest.clear(true); dest.data = data; dest.sz = sz; dest.cap = cap; data = NULL; sz = 0; cap = 0; }
+};
+
+template<class T>
+void vec<T>::grow(int min_cap) {
+    if (min_cap <= cap) return;
+    if (cap == 0) cap = (min_cap >= 2) ? min_cap : 2;
+    else          do cap = (cap*3+1) >> 1; while (cap < min_cap);
+    data = (T*)realloc(data, cap * sizeof(T)); }
+
+template<class T>
+void vec<T>::growTo(int size, const T& pad) {
+    if (sz >= size) return;
+    grow(size);
+    for (int i = sz; i < size; i++) new (&data[i]) T(pad);
+    sz = size; }
+
+template<class T>
+void vec<T>::growTo(int size) {
+    if (sz >= size) return;
+    grow(size);
+    for (int i = sz; i < size; i++) new (&data[i]) T();
+    sz = size; }
+
+template<class T>
+void vec<T>::clear(bool dealloc) {
+    if (data != NULL){
+        for (int i = 0; i < sz; i++) data[i].~T();
+        sz = 0;
+        if (dealloc) free(data), data = NULL, cap = 0; } }
+
+
+#endif
diff --git a/examples/charm++/satisfiability/minisat/mtl/minisatHeap.h b/examples/charm++/satisfiability/minisat/mtl/minisatHeap.h
new file mode 100644 (file)
index 0000000..6cb66cc
--- /dev/null
@@ -0,0 +1,169 @@
+/******************************************************************************************[Heap.h]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+#ifndef minisatHeap_h
+#define minisatHeap_h
+
+#include "Vec.h"
+
+//=================================================================================================
+// A heap implementation with support for decrease/increase key.
+
+
+template<class Comp>
+class Heap {
+    Comp     lt;
+    vec<int> heap;     // heap of ints
+    vec<int> indices;  // int -> index in heap
+
+    // Index "traversal" functions
+    static inline int left  (int i) { return i*2+1; }
+    static inline int right (int i) { return (i+1)*2; }
+    static inline int parent(int i) { return (i-1) >> 1; }
+
+
+    inline void percolateUp(int i)
+    {
+        int x = heap[i];
+        while (i != 0 && lt(x, heap[parent(i)])){
+            heap[i]          = heap[parent(i)];
+            indices[heap[i]] = i;
+            i                = parent(i);
+        }
+        heap   [i] = x;
+        indices[x] = i;
+    }
+
+
+    inline void percolateDown(int i)
+    {
+        int x = heap[i];
+        while (left(i) < heap.size()){
+            int child = right(i) < heap.size() && lt(heap[right(i)], heap[left(i)]) ? right(i) : left(i);
+            if (!lt(heap[child], x)) break;
+            heap[i]          = heap[child];
+            indices[heap[i]] = i;
+            i                = child;
+        }
+        heap   [i] = x;
+        indices[x] = i;
+    }
+
+
+    bool heapProperty (int i) const {
+        return i >= heap.size()
+            || ((i == 0 || !lt(heap[i], heap[parent(i)])) && heapProperty(left(i)) && heapProperty(right(i))); }
+
+
+  public:
+    Heap(const Comp& c) : lt(c) { }
+
+    int  size      ()          const { return heap.size(); }
+    bool empty     ()          const { return heap.size() == 0; }
+    bool inHeap    (int n)     const { return n < indices.size() && indices[n] >= 0; }
+    int  operator[](int index) const { assert(index < heap.size()); return heap[index]; }
+
+    void decrease  (int n) { assert(inHeap(n)); percolateUp(indices[n]); }
+
+    // RENAME WHEN THE DEPRECATED INCREASE IS REMOVED.
+    void increase_ (int n) { assert(inHeap(n)); percolateDown(indices[n]); }
+
+
+    void insert(int n)
+    {
+        indices.growTo(n+1, -1);
+        assert(!inHeap(n));
+
+        indices[n] = heap.size();
+        heap.push(n);
+        percolateUp(indices[n]); 
+    }
+
+
+    int  removeMin()
+    {
+        int x            = heap[0];
+        heap[0]          = heap.last();
+        indices[heap[0]] = 0;
+        indices[x]       = -1;
+        heap.pop();
+        if (heap.size() > 1) percolateDown(0);
+        return x; 
+    }
+
+
+    void clear(bool dealloc = false) 
+    { 
+        for (int i = 0; i < heap.size(); i++)
+            indices[heap[i]] = -1;
+#ifdef NDEBUG
+        for (int i = 0; i < indices.size(); i++)
+            assert(indices[i] == -1);
+#endif
+        heap.clear(dealloc); 
+    }
+
+
+    // Fool proof variant of insert/decrease/increase
+    void update (int n)
+    {
+        if (!inHeap(n))
+            insert(n);
+        else {
+            percolateUp(indices[n]);
+            percolateDown(indices[n]);
+        }
+    }
+
+
+    // Delete elements from the heap using a given filter function (-object).
+    // *** this could probaly be replaced with a more general "buildHeap(vec<int>&)" method ***
+    template <class F>
+    void filter(const F& filt) {
+        int i,j;
+        for (i = j = 0; i < heap.size(); i++)
+            if (filt(heap[i])){
+                heap[j]          = heap[i];
+                indices[heap[i]] = j++;
+            }else
+                indices[heap[i]] = -1;
+
+        heap.shrink(i - j);
+        for (int i = heap.size() / 2 - 1; i >= 0; i--)
+            percolateDown(i);
+
+        assert(heapProperty());
+    }
+
+
+    // DEBUG: consistency checking
+    bool heapProperty() const {
+        return heapProperty(1); }
+
+
+    // COMPAT: should be removed
+    void setBounds (int n) { }
+    void increase  (int n) { decrease(n); }
+    int  getmin    ()      { return removeMin(); }
+
+};
+
+
+//=================================================================================================
+#endif