| TerraLib 4.1

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

- File List
- File Members

E:/Projetos_Primeiro_Semestre_2012/TerraView/terralib/src/terralib/kernel/dynpq.h
Go to the documentation of this file.

    00001 /************************************************************************************
    00002 TerraLib - a library for developing GIS applications.
    00003 Copyright � 2001-2007 INPE and Tecgraf/PUC-Rio.
    00004
    00005 This code is part of the TerraLib library.
    00006 This library is free software; you can redistribute it and/or
    00007 modify it under the terms of the GNU Lesser General Public
    00008 License as published by the Free Software Foundation; either
    00009 version 2.1 of the License, or (at your option) any later version.
    00010
    00011 You should have received a copy of the GNU Lesser General Public
    00012 License along with this library.
    00013
    00014 The authors reassure the license terms regarding the warranties.
    00015 They specifically disclaim any warranties, including, but not limited to,
    00016 the implied warranties of merchantability and fitness for a particular purpose.
    00017 The library provided hereunder is on an "as is" basis, and the authors have no
    00018 obligation to provide maintenance, support, updates, enhancements, or modifications.
    00019 In no event shall INPE and Tecgraf / PUC-Rio be held liable to any party for direct,
    00020 indirect, special, incidental, or consequential damages arising out of the use
    00021 of this library and its documentation.
    00022 *************************************************************************************/
    00023
    00024 // include/dynpq.h
    00025 #ifndef DYNPQ_H
    00026 #define DYNPQ_H
    00027 #include "checkvec.h"
    00028 #include<algorithm>
    00029 #include "showseq.h"
    00030
    00031 namespace br_stl
    00032 {
    00033            // compares the associated values of passed iterators
    00034            template<class T>
    00035            struct IterGreater
    00036            {
    00037                       bool operator()( T x,  T y) const
    00038                       {
    00039                                  return *y < *x;
    00040                       }
    00041            };
    00042
    00043            template <class key_type>
    00044            class dynamic_priority_queue
    00045            {
    00046            public:
    00047                       // public type definitions
    00048                       typedef typename std::vector<key_type>::size_type size_type;
    00049                       typedef typename std::vector<key_type>::difference_type index_type;
    00050
    00051                       // constructor
    00052                       dynamic_priority_queue(std::vector<key_type>& v);
    00053
    00054                       // change a value at position 'at'
    00055                       void changeKeyAt(index_type at, key_type k);
    00056
    00057                       // index of the smallest element (= highest priority)
    00058                       index_type topIndex() const { return c.front() - first; }
    00059
    00060                       // value of the smallest element (= highest priority)
    00061                       const key_type& topKey() const { return *c.front(); }
    00062
    00063                       void pop();       // remove smallest element from the heap
    00064
    00065                       bool empty() const { return csize == 0;}
    00066                       size_type size() const { return csize;}
    00067
    00068            private:
    00069            //    checkedVector<index_type> Indices;      // auxiliary vector ANAP
    00070                       vector<index_type> Indices;      // auxiliary vector
    00071                       typedef typename std::vector<key_type>::iterator randomAccessIterator;
    00072            //    checkedVector<randomAccessIterator> c;  // heap of iterators  ANAP
    00073                       vector<randomAccessIterator> c;  // heap of iterators
    00074                       randomAccessIterator first;             // beginning of the external vector
    00075                       IterGreater<randomAccessIterator> comp; // comparison object
    00076                       index_type csize;                       // current heap size
    00077
    00078                       // heap update (see below)
    00079                       void goUp(index_type);
    00080                       void goDown(index_type);
    00081            };
    00082
    00083            template <class key_type>
    00084            dynamic_priority_queue<key_type>::dynamic_priority_queue(
    00085                       std::vector<key_type>& v)
    00086            : Indices(v.size()), c(v.size()), first(v.begin()),
    00087            csize(v.size())
    00088            {
    00089                       // store iterators and generate heap
    00090                       for(index_type i = 0; i< csize; ++i)
    00091                       c[i] = v.begin()+i;
    00092                       make_heap(c.begin(), c.end(), comp);        // STL
    00093
    00094                       // construct index array
    00095                       for(index_type ii = 0; ii< csize; ++ii) // ANAP i-> ii
    00096                       Indices[c[ii] - first] = ii;
    00097            }
    00098
    00099            template <class key_type>
    00100            void dynamic_priority_queue<key_type>::changeKeyAt(
    00101                                                                                                    index_type at, key_type k)
    00102            {
    00103         index_type idx = Indices[at];
    00104
    00105         //  if (idx < csize) //ANAP
    00106         // {
    00107         assert(idx < csize);   // value still present in the queue?
    00108
    00109         if(*c[idx] != k)       // in case of equality, do nothing
    00110         {
    00111             if(k > *c[idx])
    00112             {
    00113                 *c[idx] = k;   // enter heavier value
    00114                 goDown(idx);   // reorganize heap
    00115             }
    00116             else
    00117             {
    00118                 *c[idx] = k;   // enter lighter value
    00119                 goUp(idx);     // reorganize heap
    00120             }
    00121         }
    00122         //  }
    00123            // else cout << "erro no dynamic_priority_queue<key_type>::changeKeyAt" << idx << csize << k << endl;
    00124            }
    00125
    00126            template <class key_type>
    00127            void dynamic_priority_queue<key_type>::goUp(index_type idx)
    00128            {
    00129                       index_type Predecessor = (idx-1)/2;
    00130                       randomAccessIterator temp = c[idx];
    00131
    00132                       while(Predecessor != idx && comp(c[Predecessor], temp))
    00133                       {
    00134                                  c[idx] = c[Predecessor];
    00135                                  Indices[c[idx]-first] = idx;
    00136                                  idx = Predecessor;
    00137                                  Predecessor = (idx-1)/2;
    00138                       }
    00139
    00140                       c[idx] = temp;
    00141                       Indices[c[idx]-first] = idx;
    00142            }
    00143
    00144            template <class key_type>
    00145            void dynamic_priority_queue<key_type>::goDown(index_type idx)
    00146            {
    00147                       index_type Successor = (idx+1)*2-1;
    00148
    00149                       if(Successor < csize-1
    00150                                  && comp(c[Successor], c[Successor+1]))
    00151                                  ++Successor;
    00152                       randomAccessIterator temp = c[idx];
    00153
    00154                       while(Successor < csize && comp(temp, c[Successor]))
    00155                       {
    00156                                  c[idx] = c[Successor];
    00157                                  Indices[c[idx]-first] = idx;
    00158                                  idx = Successor;
    00159                                  Successor = (idx+1)*2-1;
    00160
    00161                                  if(Successor < csize-1
    00162                                  && comp(c[Successor], c[Successor+1]))
    00163                                             ++Successor;
    00164                       }
    00165                       c[idx] = temp;
    00166                       Indices[c[idx]-first] = idx;
    00167            }
    00168
    00169            /* The method pop() removes the topmost element from the heap. This is
    00170            done by moving the last element to the top and blocking the freed
    00171            position with --csize. Subsequently, the element sinks down to its
    00172            proper position. */
    00173
    00174            template <class key_type>
    00175            void dynamic_priority_queue<key_type>::pop()
    00176            {
    00177            // overwrite iterator at the top with the
    00178            // address of the last element
    00179            c[0] = c[--csize];
    00180
    00181            // enter the new address 0 at the position belonging
    00182            // to this element in the auxiliary array
    00183            Indices[c[0]-first] = 0;
    00184
    00185            // let the element at the top sink to the correct
    00186            // position corresponding to its weight
    00187            goDown(0);
    00188            }
    00189
    00190 } // namespace br_stl
    00191 #endif
    00192

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines