tuple-set.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Mikael Lagerkvist <lagerkvist@gecode.org> 00005 * 00006 * Copyright: 00007 * Mikael Lagerkvist, 2007 00008 * 00009 * Last modified: 00010 * $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00011 * $Revision: 11192 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include <gecode/int.hh> 00039 00040 namespace { 00041 00042 typedef ::Gecode::TupleSet::Tuple Tuple; 00043 00047 class FullTupleCompare { 00048 private: 00050 int arity; 00051 public: 00053 forceinline 00054 FullTupleCompare(int a) : arity(a) {} 00056 forceinline bool 00057 operator ()(const Tuple& a, const Tuple& b) { 00058 for (int i = 0; i < arity; i++) 00059 if (a[i] < b[i]) 00060 return true; 00061 else if (a[i] > b[i]) 00062 return false; 00063 return a < b; 00064 } 00065 }; 00066 00073 class TuplePosCompare { 00074 private: 00076 int pos; 00077 public: 00079 forceinline 00080 TuplePosCompare(int p) : pos(p) {} 00082 forceinline bool 00083 operator ()(const Tuple& a, const Tuple& b) { 00084 if (a[pos] == b[pos]) 00085 return a < b; 00086 else 00087 return a[pos] < b[pos]; 00088 } 00089 }; 00090 00091 } 00092 00093 namespace Gecode { 00094 00095 void 00096 TupleSet::TupleSetI::finalize(void) { 00097 assert(!finalized()); 00098 assert(tuples == NULL); 00099 00100 // Add final largest tuple 00101 IntArgs ia(arity); 00102 for (int i = arity; i--; ) 00103 ia[i] = Int::Limits::max+1; 00104 int real_min = min, real_max = max; 00105 add(ia); 00106 min = real_min; max = real_max; 00107 00108 // Domainsize 00109 domsize = static_cast<unsigned int>(max - min) + 1; 00110 00111 // Allocate tuple indexing data-structures 00112 tuples = heap.alloc<Tuple*>(arity); 00113 tuple_data = heap.alloc<Tuple>(size*arity+1); 00114 tuple_data[size*arity] = NULL; 00115 nullpointer = tuple_data+(size*arity); 00116 00117 // Rearrange the tuples for faster comparisons. 00118 for (int i = arity; i--; ) 00119 tuples[i] = tuple_data + (i * size); 00120 for (int i = size; i--; ) 00121 tuples[0][i] = data + (i * arity); 00122 00123 FullTupleCompare ftc(arity); 00124 Support::quicksort(tuples[0], size, ftc); 00125 assert(tuples[0][size-1][0] == ia[0]); 00126 int* new_data = heap.alloc<int>(size*arity); 00127 for (int t = size; t--; ) 00128 for (int i = arity; i--; ) 00129 new_data[t*arity + i] = tuples[0][t][i]; 00130 00131 heap.rfree(data); 00132 data = new_data; 00133 excess = -1; 00134 00135 // Set up indexing structure 00136 for (int i = arity; i--; ) 00137 for (int t = size; t--; ) 00138 tuples[i][t] = data + (t * arity); 00139 for (int i = arity; i-->1; ) { 00140 TuplePosCompare tpc(i); 00141 Support::quicksort(tuples[i], size, tpc); 00142 } 00143 00144 // Set up initial last-structure 00145 last = heap.alloc<Tuple*>(domsize*arity); 00146 for (int i = arity; i--; ) { 00147 Tuple* t = tuples[i]; 00148 for (unsigned int d = 0; d < domsize; ++d) { 00149 while (t && *t && (*t)[i] < static_cast<int>(min+d)) { 00150 ++t; 00151 } 00152 if (t && *t && (*t)[i] == static_cast<int>(min+d)) { 00153 last[(i*domsize) + d] = t; 00154 ++t; 00155 } else { 00156 last[(i*domsize) + d] = nullpointer; 00157 } 00158 } 00159 } 00160 00161 assert(finalized()); 00162 } 00163 00164 void 00165 TupleSet::TupleSetI::resize(void) { 00166 assert(excess == 0); 00167 int ndatasize = static_cast<int>(1+size*1.5); 00168 data = heap.realloc<int>(data, size * arity, ndatasize * arity); 00169 excess = ndatasize - size; 00170 } 00171 00172 SharedHandle::Object* 00173 TupleSet::TupleSetI::copy(void) const { 00174 assert(finalized()); 00175 TupleSetI* d = new TupleSetI; 00176 d->arity = arity; 00177 d->size = size; 00178 d->excess = excess; 00179 d->min = min; 00180 d->max = max; 00181 d->domsize = domsize; 00182 00183 // Table data 00184 d->data = heap.alloc<int>(size*arity); 00185 heap.copy(&d->data[0], &data[0], size*arity); 00186 00187 // Indexing data 00188 d->tuples = heap.alloc<Tuple*>(arity); 00189 d->tuple_data = heap.alloc<Tuple>(size*arity+1); 00190 d->tuple_data[size*arity] = NULL; 00191 d->nullpointer = d->tuple_data+(size*arity); 00192 00193 // Rearrange the tuples for faster comparisons. 00194 for (int i = arity; i--; ) 00195 d->tuples[i] = d->tuple_data + (i * size); 00196 for (int a = arity; a--; ) { 00197 for (int i = size; i--; ) { 00198 d->tuples[a][i] = d->data + (tuples[a][i]-data); 00199 } 00200 } 00201 00202 // Last data 00203 d->last = heap.alloc<Tuple*>(domsize*arity); 00204 for (int i = static_cast<int>(domsize)*arity; i--; ) { 00205 d->last[i] = d->tuple_data + (last[i]-tuple_data); 00206 } 00207 00208 return d; 00209 } 00210 00211 TupleSet::TupleSetI::~TupleSetI(void) { 00212 excess = -2; 00213 heap.rfree(tuples); 00214 heap.rfree(tuple_data); 00215 heap.rfree(data); 00216 heap.rfree(last); 00217 } 00218 00219 } 00220 00221 // STATISTICS: int-prop 00222