1 /* 2 Copyright (C) 2013 Tom Bachmann 3 4 This file is part of FLINT. 5 6 FLINT is free software: you can redistribute it and/or modify it under 7 the terms of the GNU Lesser General Public License (LGPL) as published 8 by the Free Software Foundation; either version 2.1 of the License, or 9 (at your option) any later version. See <http://www.gnu.org/licenses/>. 10 */ 11 12 // Sketch of a generic vector class. 13 14 #ifndef CXX_VECTOR_H 15 #define CXX_VECTOR_H 16 17 #include <string> 18 #include <sstream> 19 20 #include "expression.h" 21 #include "evaluation_tools.h" 22 #include "ltuple.h" 23 #include "mp.h" 24 25 namespace flint { 26 FLINT_DEFINE_BINOP(vector_at) 27 28 template<class Underlying_traits, class Operation, class Data> 29 class vector_expression; 30 31 namespace detail { 32 template<class Traits> 33 struct vector_wrapper : derived_wrapper2<vector_expression, Traits> { }; 34 35 template<class Idx, class Operation, class Expr, class Traits> 36 struct vector_at_traits 37 { 38 typedef FLINT_BINOP_ENABLE_RETTYPE(vector_at, Expr, Idx) ref_t; 39 typedef ref_t cref_t; atvector_at_traits40 static ref_t at(const Expr& v, Idx i) 41 {return vector_at(v, i);} 42 }; 43 template<class Idx, class Expr, class Traits> 44 struct vector_at_traits<Idx, operations::immediate, Expr, Traits> 45 : Traits { }; 46 } 47 48 template<class Underlying_traits, class Operation, class Data> 49 class vector_expression 50 : public expression<detail::vector_wrapper<Underlying_traits>, Operation, Data> 51 { 52 public: 53 typedef expression<detail::vector_wrapper<Underlying_traits>, 54 Operation, Data> base_t; 55 typedef typename Underlying_traits::ref_t ref_t; 56 typedef typename Underlying_traits::cref_t cref_t; 57 typedef typename Underlying_traits::idx_t idx_t; 58 typedef typename Underlying_traits::underlying_t underlying_t; 59 typedef typename Underlying_traits::arrayref_t arrayref_t; 60 typedef typename Underlying_traits::arraysrcref_t arraysrcref_t; 61 62 vector_expression() {} 63 64 template<class T> 65 explicit vector_expression(const T& t) : base_t(t) {} 66 template<class T, class U> 67 vector_expression(const T& t, const U& u) : base_t(t, u) {} 68 template<class T, class U, class V> 69 vector_expression(const T& t, const U& u, const V& v) 70 : base_t(t, u, v) {} 71 72 template<class T> 73 vector_expression& operator=(const T& t) 74 { 75 this->set(t); 76 return *this; 77 } 78 79 template<class Idx> 80 typename detail::vector_at_traits<Idx, Operation, vector_expression, 81 Underlying_traits>::ref_t operator[](Idx idx) 82 { 83 return detail::vector_at_traits<Idx, Operation, vector_expression, 84 Underlying_traits>::at(*this, idx); 85 } 86 template<class Idx> 87 typename detail::vector_at_traits<Idx, Operation, vector_expression, 88 Underlying_traits>::cref_t operator[](Idx idx) const 89 { 90 return detail::vector_at_traits<Idx, Operation, vector_expression, 91 Underlying_traits>::at(*this, idx); 92 } 93 94 idx_t size() const {return Underlying_traits::size(*this);} 95 96 arrayref_t _array() {return Underlying_traits::array(*this);} 97 arraysrcref_t _array() const {return Underlying_traits::array(*this);} 98 99 typename base_t::evaluated_t create_temporary() const 100 { 101 return Underlying_traits::create_temporary(*this); 102 } 103 104 protected: 105 explicit vector_expression(const Data& d) : base_t(d) {} 106 107 template<class D, class O, class Da> 108 friend class expression; 109 }; 110 111 namespace vectors { 112 // Similar to matrices, the size of a vector expression has to be known in 113 // order to allocate temporary objects. In this case, the generic 114 // implementation looks for any vector immediate subexpression and returs its 115 // size. This makes sense since mixing vectors of differing sizes usually makes 116 // no sense. 117 // Thus specialisation is usually only necessary in constructor-like operations, 118 // which do not involve vector immediates. 119 template<class Operation> 120 struct outsize 121 { 122 template<class Expr> 123 static unsigned get(const Expr& e) 124 { 125 return tools::find_subexpr_T<typename Expr::evaluated_t>(e)._data().size; 126 } 127 }; 128 129 // Hack for ltuple_get, similar to the matrices case. 130 template<unsigned n> 131 struct outsize<operations::ltuple_get_op<n> > 132 { 133 template<class Expr> 134 static unsigned get(const Expr& e) 135 { 136 return outsize<typename Expr::data_t::head_t::operation_t>::get( 137 e._data().head); 138 } 139 }; 140 } 141 142 namespace detail { 143 template<class T, class Ref, class Cref, class ArrayT> 144 struct basic_vector_traits 145 { 146 typedef unsigned idx_t; 147 typedef Ref ref_t; 148 typedef const Cref cref_t; 149 typedef T underlying_t; 150 typedef ArrayT* arrayref_t; 151 typedef const ArrayT* arraysrcref_t; 152 153 template<class Expr> 154 static ref_t at(Expr& e, unsigned i) 155 { 156 return e.evaluate()._data().array[i]; 157 } 158 159 template<class Expr> 160 static cref_t at(const Expr& e, unsigned i) 161 { 162 return e.evaluate()._data().array[i]; 163 } 164 165 template<class Expr> 166 static arrayref_t array(Expr& e) 167 { 168 return e.evaluate()._data().array; 169 } 170 171 template<class Expr> 172 static arraysrcref_t array(const Expr& e) 173 { 174 return e.evaluate()._data().array; 175 } 176 }; 177 template<class T, class Ref = T&, class Cref = const T&, class ArrayT = T> 178 struct rtfixed_size_traits 179 : basic_vector_traits<T, Ref, Cref, ArrayT> 180 { 181 template<class Expr> 182 static unsigned size(const Expr& e) 183 { 184 return vectors::outsize<typename Expr::operation_t>::get(e); 185 } 186 187 template<class Expr> 188 static typename Expr::evaluated_t create_temporary(const Expr& e) 189 { 190 return typename Expr::evaluated_t(e.size()); 191 } 192 }; 193 template<class T, class Ref = T&, class Cref = const T&, class ArrayT = T> 194 struct fixed_size_traits 195 : basic_vector_traits<T, Ref, Cref, ArrayT> 196 { 197 template<class Expr> 198 static unsigned size(const Expr& e) 199 { 200 return Expr::evaluated_t::data_t::size; 201 } 202 203 template<class Expr> 204 static typename Expr::evaluated_t create_temporary(const Expr& e) 205 { 206 return typename Expr::evaluated_t(); 207 } 208 }; 209 210 template<class T, class Size, class Ref, class Cref, class ArrayT> 211 struct wrapped_vector_traits 212 : rtfixed_size_traits<T, Ref, Cref, ArrayT> 213 { 214 typedef Size idx_t; 215 216 template<class Expr> 217 static Ref at(Expr& e, idx_t i) 218 { 219 return e.evaluate()._data().at(i); 220 } 221 222 template<class Expr> 223 static Cref at(const Expr& e, idx_t i) 224 { 225 return e.evaluate()._data().at(i); 226 } 227 }; 228 229 template<class T> 230 struct rtfixed_size_data 231 { 232 const unsigned size; 233 T* array; 234 235 rtfixed_size_data(unsigned n) 236 : size(n), array(new T[n]) {} 237 ~rtfixed_size_data() {delete[] array;} 238 239 rtfixed_size_data(const rtfixed_size_data& o) 240 : size(o.size) 241 { 242 // TODO this is very non-optimal ... (?) 243 array = new T[size]; 244 for(unsigned i = 0;i < size;++i) 245 { 246 array[i] = o.array[i]; 247 } 248 } 249 }; 250 template<class T, unsigned n> 251 struct fixed_size_data 252 { 253 static const unsigned size = n; 254 T array[n]; 255 }; 256 } // detail 257 258 template<class T> 259 struct make_vector 260 { 261 typedef vector_expression<detail::rtfixed_size_traits<T>, 262 operations::immediate, detail::rtfixed_size_data<T> > type; 263 }; 264 template<class T, unsigned n> 265 struct make_vector_n 266 { 267 typedef vector_expression<detail::fixed_size_traits<T>, 268 operations::immediate, detail::fixed_size_data<T, n> > type; 269 }; 270 271 template<class Expr> 272 struct enable_vector_rules : mp::false_ { }; 273 274 template<class Traits, class Data> 275 struct enable_vector_rules< 276 vector_expression<Traits, operations::immediate, Data> > 277 : mp::true_ { }; 278 279 namespace rules { 280 // temporary allocation inside ltuples 281 template<class Operation, class Data, class U, 282 class Traits, class Op, class Da> 283 struct instantiate_temporaries<ltuple_expression<U, Operation, Data>, 284 vector_expression<Traits, Op, Da> > 285 { 286 typedef ltuple_expression<U, Operation, Data> Expr; 287 typedef vector_expression<Traits, Op, Da> T; 288 static T get(const Expr& e) 289 { 290 return T(vectors::outsize<Operation>::get(e)); 291 } 292 }; 293 294 template<class Traits, class Data, class T> 295 struct binary_expression<vector_expression<Traits, operations::immediate, Data>, 296 operations::vector_at_op, T> 297 { 298 typedef typename Traits::underlying_t return_t; 299 template<class V> 300 static void doit(V& to, 301 const vector_expression<Traits, operations::immediate, Data>& v, 302 T i) 303 { 304 to = Traits::at(v, i); 305 } 306 }; 307 308 309 template<class Expr> 310 struct to_string<Expr, typename mp::enable_if<mp::and_< 311 enable_vector_rules<Expr>, 312 traits::is_implemented<to_string<typename Expr::underlying_t> > > >::type> 313 { 314 static std::string get(const Expr& e, int base) 315 { 316 // TODO inefficient 317 std::string res = "("; 318 for(typename Expr::idx_t i = 0;i < e.size();++i) 319 { 320 res += e[i].to_string(); 321 if(i != e.size() - 1) 322 res += ", "; 323 } 324 res += ")"; 325 return res; 326 } 327 }; 328 329 template<class Expr> 330 struct equals<Expr, Expr, 331 typename mp::enable_if<enable_vector_rules<Expr> >::type> 332 { 333 static bool get(const Expr& e1, const Expr& e2) 334 { 335 if(e1.size() != e2.size()) 336 return false; 337 for(typename Expr::idx_t i = 0;i < e1.size();++i) 338 if(e1[i] != e2[i]) 339 return false; 340 return true; 341 } 342 }; 343 344 namespace rvdetail { 345 template<class Tuple> 346 struct translate_data; 347 348 template<class Expr, class enable = void> 349 struct translate_expr 350 { 351 typedef translate_data<typename Expr::data_t> trdata_t; 352 typedef typename Expr::underlying_t ul_t; 353 typedef typename ul_t::template make_helper< 354 typename Expr::operation_t, typename trdata_t::type> make_helper; 355 typedef typename make_helper::type type; 356 357 template<class Idx> 358 static type make(const Expr& e, Idx idx) 359 { 360 return make_helper::make(trdata_t::make(e._data(), idx)); 361 } 362 }; 363 364 template<class Expr> 365 struct translate_expr<Expr, 366 typename mp::enable_if<traits::is_immediate<Expr> >::type> 367 { 368 typedef typename Expr::cref_t type; 369 370 template<class Idx> 371 static type make(const Expr& e, Idx idx) 372 { 373 return e[idx]; 374 } 375 }; 376 377 template<class Head, class Tail> 378 struct translate_data<tuple<Head, Tail> > 379 { 380 typedef translate_expr<typename traits::basetype<Head>::type> trexpr; 381 typedef translate_data<Tail> trtail; 382 typedef tuple<typename trexpr::type, typename trtail::type> type; 383 384 template<class Idx> 385 static type make(const tuple<Head, Tail>& e, Idx idx) 386 { 387 return type(trexpr::make(e.head, idx), trtail::make(e.tail, idx)); 388 } 389 }; 390 template<> 391 struct translate_data<empty_tuple> 392 { 393 typedef empty_tuple type; 394 template<class Idx> 395 static type make(empty_tuple, Idx) {return empty_tuple();} 396 }; 397 398 template<class Data, class Enable = void> 399 struct enable_evaluation : mp::false_ {typedef void vector_t;}; 400 401 template<class Data> 402 struct enable_evaluation<Data, 403 typename mp::enable_if<traits::is_expression< 404 typename traits::basetype<Data>::type> >::type> 405 : enable_vector_rules<typename traits::basetype<Data>::type::evaluated_t> 406 { 407 typedef typename traits::basetype<Data>::type::evaluated_t vector_t; 408 }; 409 template<class Head, class Tail> 410 struct enable_evaluation<tuple<Head, Tail> > 411 : mp::and_<enable_evaluation<Head>, enable_evaluation<Tail> > 412 { 413 typedef typename enable_evaluation<Head>::vector_t vector_t; 414 }; 415 template<> 416 struct enable_evaluation<empty_tuple> 417 : mp::true_ { }; 418 } //rvdetail 419 420 // TODO this is a bit greedy .. 421 template<class Op, class Data, bool result_is_temporary> 422 struct evaluation<Op, Data, result_is_temporary, 1, 423 typename mp::enable_if<rvdetail::enable_evaluation<Data> >::type> 424 { 425 typedef rvdetail::translate_data<Data> translator; 426 typedef typename translator::type trdata_t; 427 typedef typename mp::find_evaluation< 428 Op, trdata_t, result_is_temporary>::type rule_t; 429 typedef typename rvdetail::enable_evaluation<Data>::vector_t vector_t; 430 typedef typename vector_t::evaluated_t return_t; // TODO 431 typedef typename rule_t::temporaries_t temporaries_t; 432 typedef typename rule_t::return_t trreturn_t; 433 434 template<class Return> 435 static void doit(const Data& input, temporaries_t temps, Return* output) 436 { 437 for(typename return_t::idx_t i = 0;i < output->size();++i) 438 { 439 rule_t::doit(translator::make(input, i), temps, &((*output)[i])); 440 } 441 } 442 }; 443 444 // TODO scalar multiplication etc 445 } // rules 446 } // flint 447 #endif 448