Generated on Fri Oct 19 11:25:03 2018 for Gecode by doxygen 1.6.3

tree.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Guido Tack <tack@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2009
00009  *     Guido Tack, 2010
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 namespace Gecode { namespace Int {
00037 
00038   forceinline int
00039   plus(int x, int y) {
00040     assert(y != -Limits::infinity);
00041     return (x == -Limits::infinity) ? x : x+y;
00042   }
00043 
00044   forceinline long long int
00045   plus(long long int x, long long int y) {
00046     assert(y != -Limits::llinfinity);
00047     return (x == -Limits::llinfinity) ? x : x+y;
00048   }
00049 
00050   template<class TaskView, class Node>
00051   forceinline int
00052   TaskTree<TaskView,Node>::n_inner(void) const {
00053     return tasks.size()-1;
00054   }
00055   template<class TaskView, class Node>
00056   forceinline int
00057   TaskTree<TaskView,Node>::n_nodes(void) const {
00058     return 2*tasks.size() - 1;
00059   }
00060 
00061   template<class TaskView, class Node>
00062   forceinline bool
00063   TaskTree<TaskView,Node>::n_root(int i) {
00064     return i == 0;
00065   }
00066   template<class TaskView, class Node>
00067   forceinline bool
00068   TaskTree<TaskView,Node>::n_leaf(int i) const {
00069     return i >= n_inner();
00070   }
00071   template<class TaskView, class Node>
00072   forceinline int
00073   TaskTree<TaskView,Node>::n_left(int i) {
00074     return 2*(i+1) - 1;
00075   }
00076   template<class TaskView, class Node>
00077   forceinline bool
00078   TaskTree<TaskView,Node>::left(int i) {
00079     assert(!n_root(i));
00080     // A left node has an odd number
00081     return (i & 1) != 0;
00082   }
00083   template<class TaskView, class Node>
00084   forceinline int
00085   TaskTree<TaskView,Node>::n_right(int i) {
00086     return 2*(i+1);
00087   }
00088   template<class TaskView, class Node>
00089   forceinline bool
00090   TaskTree<TaskView,Node>::right(int i) {
00091     assert(!n_root(i));
00092     // A left node has an even number
00093     return (i & 1) == 0;
00094   }
00095   template<class TaskView, class Node>
00096   forceinline int
00097   TaskTree<TaskView,Node>::n_parent(int i) {
00098     return (i+1)/2 - 1;
00099   }
00100 
00101   template<class TaskView, class Node>
00102   forceinline Node&
00103   TaskTree<TaskView,Node>::leaf(int i) {
00104     return node[_leaf[i]];
00105   }
00106 
00107   template<class TaskView, class Node>
00108   forceinline const Node&
00109   TaskTree<TaskView,Node>::root(void) const {
00110     return node[0];
00111   }
00112 
00113   template<class TaskView, class Node>
00114   forceinline void
00115   TaskTree<TaskView,Node>::init(void) {
00116     for (int i=n_inner(); i--; )
00117       node[i].init(node[n_left(i)],node[n_right(i)]);
00118   }
00119 
00120   template<class TaskView, class Node>
00121   forceinline void
00122   TaskTree<TaskView,Node>::update(void) {
00123     for (int i=n_inner(); i--; )
00124       node[i].update(node[n_left(i)],node[n_right(i)]);
00125   }
00126 
00127   template<class TaskView, class Node>
00128   forceinline void
00129   TaskTree<TaskView,Node>::update(int i, bool l) {
00130     if (l)
00131       i = _leaf[i];
00132     assert(!n_root(i));
00133     do {
00134       i = n_parent(i);
00135       node[i].update(node[n_left(i)],node[n_right(i)]);
00136     } while (!n_root(i));
00137   }
00138 
00139   template<class TaskView, class Node>
00140   forceinline
00141   TaskTree<TaskView,Node>::TaskTree(Region& r,
00142                                     const TaskViewArray<TaskView>& t)
00143     : tasks(t),
00144       node(r.alloc<Node>(n_nodes())),
00145       _leaf(r.alloc<int>(tasks.size())) {
00146     // Compute a sorting map to order by non decreasing est
00147     int* map = r.alloc<int>(tasks.size());
00148     sort<TaskView,STO_EST,true>(map, tasks);
00149     // Compute inverse of sorting map
00150     for (int i=0; i<tasks.size(); i++)
00151       _leaf[map[i]] = i;
00152     r.free<int>(map,tasks.size());
00153     // Compute index of first leaf in tree: the next larger power of two
00154     int fst = 1;
00155     while (fst < tasks.size())
00156       fst <<= 1;
00157     fst--;
00158     // Remap task indices to leaf indices
00159     for (int i=0; i<tasks.size(); i++)
00160       if (_leaf[i] + fst >= n_nodes())
00161         _leaf[i] += fst - tasks.size();
00162       else
00163         _leaf[i] += fst;
00164   }
00165 
00166   template<class TaskView, class Node> template<class Node2>
00167   forceinline
00168   TaskTree<TaskView,Node>::TaskTree(Region& r,
00169                                     const TaskTree<TaskView,Node2>& t)
00170     : tasks(t.tasks),
00171       node(r.alloc<Node>(n_nodes())),
00172       _leaf(r.alloc<int>(tasks.size())) {
00173     for (int i=0; i<tasks.size(); i++)
00174       _leaf[i] = t._leaf[i];
00175   }
00176 
00177 }}
00178 
00179 // STATISTICS: int-prop