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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009 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 <ext/pb_ds/tag_and_trait.hpp>
  45 #include <ext/pb_ds/detail/priority_queue_base_dispatch.hpp>
  46 #include <ext/pb_ds/detail/standard_policies.hpp>
  47
  48 namespace __gnu_pbds
  49 {
  50   // A priority queue.
  51   template<typename Value_Type,
  52            typename Cmp_Fn = std::less<Value_Type>,
  53            typename Tag = pairing_heap_tag,
  54            typename Allocator = std::allocator<char> >
  55   class priority_queue
  56   : public detail::priority_queue_base_dispatch<Value_Type,Cmp_Fn,Tag,Allocator>::type
  57   {
  58   private:
  59     typedef typename detail::priority_queue_base_dispatch<Value_Type,Cmp_Fn,Tag,Allocator>::type base_type;
  60
  61   public:
  62     typedef Value_Type                                  value_type;
  63     typedef Cmp_Fn                                      cmp_fn;
  64     typedef Tag                                         container_category;
  65     typedef Allocator                                   allocator_type;
  66     typedef typename allocator_type::size_type          size_type;
  67     typedef typename allocator_type::difference_type    difference_type;
  68
  69     typedef typename allocator_type::template rebind<value_type>::other value_rebind;
  70     typedef typename value_rebind::reference            reference;
  71     typedef typename value_rebind::const_reference      const_reference;
  72     typedef typename value_rebind::pointer              pointer;
  73     typedef typename value_rebind::const_pointer        const_pointer;
  74
  75     typedef typename base_type::const_point_iterator const_point_iterator;
  76     typedef typename base_type::point_iterator          point_iterator;
  77     typedef typename base_type::const_iterator          const_iterator;
  78     typedef typename base_type::iterator                iterator;
  79
  80     priority_queue() { }
  81
  82     // Constructor taking some policy objects. r_cmp_fn will be copied
  83     // by the Cmp_Fn object of the container object.
  84     priority_queue(const cmp_fn& r_cmp_fn) : base_type(r_cmp_fn) { }
  85
  86     // Constructor taking __iterators to a range of value_types. The
  87     // value_types between first_it and last_it will be inserted into
  88     // the container object.
  89     template<typename It>
  90     priority_queue(It first_it, It last_it)
  91     { base_type::copy_from_range(first_it, last_it); }
  92
  93     // Constructor taking __iterators to a range of value_types and
  94     // some policy objects The value_types between first_it and
  95     // last_it will be inserted into the container object. r_cmp_fn
  96     // will be copied by the cmp_fn object of the container object.
  97     template<typename It>
  98     priority_queue(It first_it, It last_it, const cmp_fn& r_cmp_fn)
  99     : base_type(r_cmp_fn)
 100     { base_type::copy_from_range(first_it, last_it); }
 101
 102     priority_queue(const priority_queue& other)
 103     : base_type((const base_type& )other) { }
 104
 105     virtual
 106     ~priority_queue() { }
 107
 108     priority_queue&
 109     operator=(const priority_queue& other)
 110     {
 111       if (this != &other)
 112         {
 113           priority_queue tmp(other);
 114           swap(tmp);
 115         }
 116       return *this;
 117     }
 118
 119     void
 120     swap(priority_queue& other)
 121     { base_type::swap(other); }
 122   };
 123 } // namespace __gnu_pbds
 124
 125 #endif