l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.6/include/ext/pb_ds/priority_queue.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26
  27 // Permission to use, copy, modify, sell, and distribute this software
  28 // is hereby granted without fee, provided that the above copyright
  29 // notice appears in all copies, and that both that copyright notice
  30 // and this permission notice appear in supporting documentation. None
  31 // of the above authors, nor IBM Haifa Research Laboratories, make any
  32 // representation about the suitability of this software for any
  33 // purpose. It is provided "as is" without express or implied
  34 // warranty.
  35
  36 /**
  37  * @file priority_queue.hpp
  38  * Contains priority_queues.
  39  */
  40
  41 #ifndef PB_DS_PRIORITY_QUEUE_HPP
  42 #define PB_DS_PRIORITY_QUEUE_HPP
  43
  44 #include <bits/c++config.h>
  45 #include <ext/pb_ds/tag_and_trait.hpp>
  46 #include <ext/pb_ds/detail/priority_queue_base_dispatch.hpp>
  47 #include <ext/pb_ds/detail/standard_policies.hpp>
  48
  49 namespace __gnu_pbds
  50 {
  51   // A priority queue.
  52   template<typename Value_Type,
  53            typename Cmp_Fn = std::less<Value_Type>,
  54            typename Tag = pairing_heap_tag,
  55            typename Allocator = std::allocator<char> >
  56   class priority_queue
  57   : public detail::priority_queue_base_dispatch<Value_Type,
  58                                                 Cmp_Fn,Tag,Allocator>::type
  59   {
  60   private:
  61     typedef typename
  62     detail::priority_queue_base_dispatch<Value_Type, Cmp_Fn,
  63                                          Tag, Allocator>::type base_type;
  64
  65   public:
  66     typedef Value_Type                                  value_type;
  67     typedef Cmp_Fn                                      cmp_fn;
  68     typedef Tag                                         container_category;
  69     typedef Allocator                                   allocator_type;
  70     typedef typename allocator_type::size_type          size_type;
  71     typedef typename allocator_type::difference_type    difference_type;
  72
  73     typedef typename allocator_type::template rebind<value_type>::other value_rebind;
  74     typedef typename value_rebind::reference            reference;
  75     typedef typename value_rebind::const_reference      const_reference;
  76     typedef typename value_rebind::pointer              pointer;
  77     typedef typename value_rebind::const_pointer        const_pointer;
  78
  79     typedef typename base_type::const_point_iterator const_point_iterator;
  80     typedef typename base_type::point_iterator          point_iterator;
  81     typedef typename base_type::const_iterator          const_iterator;
  82     typedef typename base_type::iterator                iterator;
  83
  84     priority_queue() { }
  85
  86     // Constructor taking some policy objects. r_cmp_fn will be copied
  87     // by the Cmp_Fn object of the container object.
  88     priority_queue(const cmp_fn& r_cmp_fn) : base_type(r_cmp_fn) { }
  89
  90     // Constructor taking __iterators to a range of value_types. The
  91     // value_types between first_it and last_it will be inserted into
  92     // the container object.
  93     template<typename It>
  94     priority_queue(It first_it, It last_it)
  95     { base_type::copy_from_range(first_it, last_it); }
  96
  97     // Constructor taking __iterators to a range of value_types and
  98     // some policy objects The value_types between first_it and
  99     // last_it will be inserted into the container object. r_cmp_fn
 100     // will be copied by the cmp_fn object of the container object.
 101     template<typename It>
 102     priority_queue(It first_it, It last_it, const cmp_fn& r_cmp_fn)
 103     : base_type(r_cmp_fn)
 104     { base_type::copy_from_range(first_it, last_it); }
 105
 106     priority_queue(const priority_queue& other)
 107     : base_type((const base_type& )other) { }
 108
 109     virtual
 110     ~priority_queue() { }
 111
 112     priority_queue&
 113     operator=(const priority_queue& other)
 114     {
 115       if (this != &other)
 116         {
 117           priority_queue tmp(other);
 118           swap(tmp);
 119         }
 120       return *this;
 121     }
 122
 123     void
 124     swap(priority_queue& other)
 125     { base_type::swap(other); }
 126   };
 127 } // namespace __gnu_pbds
 128
 129 #endif