1 // -*- C++ -*- 2 //============================================================================================== 3 // 4 // This file is part of LiDIA --- a library for computational number theory 5 // 6 // Copyright (c) 1994--2001 the LiDIA Group. All rights reserved. 7 // 8 // See http://www.informatik.tu-darmstadt.de/TI/LiDIA/ 9 // 10 //---------------------------------------------------------------------------------------------- 11 // 12 // $Id$ 13 // 14 // Author : Patrick Theobald (PT) 15 // Changes : See CVS log 16 // 17 //============================================================================================== 18 19 20 #ifndef LIDIA_SORT_VECTOR_H_GUARD_ 21 #define LIDIA_SORT_VECTOR_H_GUARD_ 22 23 24 25 #ifndef LIDIA_COMPARATOR_H_GUARD_ 26 # include "LiDIA/comparator.h" 27 #endif 28 #ifndef LIDIA_BASE_VECTOR_H_GUARD_ 29 # include "LiDIA/base_vector.h" 30 #endif 31 32 33 34 #ifdef LIDIA_NAMESPACE 35 namespace LiDIA { 36 # define IN_NAMESPACE_LIDIA 37 #endif 38 39 40 41 template< class T > 42 class sort_vector : public virtual base_vector< T > 43 { 44 45 // 46 // constructors 47 // 48 49 public: 50 sort_vector()51 sort_vector() : 52 base_vector< T > () 53 { 54 this->sort_dir = vector_flags::sort_vector_up; 55 this->el_cmp = NULL; 56 } 57 sort_vector(const vector_flags & md)58 explicit sort_vector(const vector_flags & md) : 59 base_vector< T > (md) 60 { 61 this->sort_dir = vector_flags::sort_vector_up; 62 this->el_cmp = NULL; 63 } sort_vector(lidia_size_t all)64 explicit sort_vector(lidia_size_t all) : 65 base_vector< T > (all) 66 { 67 this->sort_dir = vector_flags::sort_vector_up; 68 this->el_cmp = NULL; 69 } 70 sort_vector(lidia_size_t all,const vector_flags & md)71 sort_vector(lidia_size_t all, const vector_flags & md) : 72 base_vector< T > (all, md) 73 { 74 this->sort_dir = vector_flags::sort_vector_up; 75 this->el_cmp = NULL; 76 } sort_vector(lidia_size_t all,lidia_size_t len)77 sort_vector(lidia_size_t all, lidia_size_t len) : 78 base_vector< T > (all, len) 79 { 80 this->sort_dir = vector_flags::sort_vector_up; 81 this->el_cmp = NULL; 82 } sort_vector(lidia_size_t all,lidia_size_t len,const vector_flags & md)83 sort_vector(lidia_size_t all, lidia_size_t len, const vector_flags & md) : 84 base_vector< T > (all, len, md) 85 { 86 this->sort_dir = vector_flags::sort_vector_up; 87 this->el_cmp = NULL; 88 } sort_vector(const sort_vector<T> & v)89 sort_vector(const sort_vector< T > &v) : 90 base_vector< T > (v) 91 { 92 this->sort_dir = v.sort_dir; 93 this->el_cmp = v.el_cmp; 94 } sort_vector(const base_vector<T> & v,const vector_flags & md)95 sort_vector(const base_vector< T > &v, const vector_flags & md) : 96 base_vector< T > (v, md) 97 { 98 this->sort_dir = vector_flags::sort_vector_up; 99 this->el_cmp = NULL; 100 } sort_vector(const T * v,lidia_size_t len)101 sort_vector(const T *v, lidia_size_t len) : 102 base_vector< T > (v, len) 103 { 104 this->sort_dir = vector_flags::sort_vector_up; 105 this->el_cmp = NULL; 106 } sort_vector(const T * v,lidia_size_t len,const vector_flags & md)107 sort_vector(const T *v, lidia_size_t len, const vector_flags &md) : 108 base_vector< T > (v, len, md) 109 { 110 this->sort_dir = vector_flags::sort_vector_up; 111 this->el_cmp = NULL; 112 } 113 114 // 115 // destructor 116 // 117 118 public: 119 ~sort_vector()120 ~sort_vector() {} 121 122 // 123 // assign 124 // 125 126 sort_vector< T > & operator = (const sort_vector< T > & v); 127 128 // 129 // reading & modifying sort-directions 130 // 131 132 public: 133 sort_direction()134 unsigned long sort_direction() const 135 { 136 return this->sort_dir; 137 } get_sort_direction()138 unsigned long get_sort_direction() const 139 { 140 return this->sort_dir; 141 } 142 143 void set_sort_direction(unsigned long); 144 void set_sort_direction(int (*cmp) (const T &, const T &)); 145 146 // 147 // sort-functions using Quick-Sort routines 148 // 149 150 public: 151 152 void sort(int (*cmp)(const T &, const T &), 153 lidia_size_t l = 0, lidia_size_t r = -1); 154 void sort(unsigned long sort_direction = vector_flags::sort_vector_def, 155 lidia_size_t l = 0, lidia_size_t r = -1); sort(lidia_size_t l,lidia_size_t r)156 void sort(lidia_size_t l, lidia_size_t r) 157 { 158 sort(vector_flags::sort_vector_def, l, r); 159 } 160 161 void sort_down(lidia_size_t l, lidia_size_t r); 162 void sort_up(lidia_size_t l, lidia_size_t r); 163 164 // 165 // functions for linear search in vectors 166 // 167 168 public: 169 170 bool linear_search(const T &, lidia_size_t &) const; 171 172 // 173 // functions for binary search in sorted vectors 174 // 175 176 public: 177 178 bool bin_search(const T &, lidia_size_t &, 179 int (*cmp)(const T &, const T &), 180 lidia_size_t l = 0, lidia_size_t r = -1) const; 181 bool bin_search(const T &, lidia_size_t &, 182 unsigned long sort_direction = vector_flags::sort_vector_def, 183 lidia_size_t l = 0, lidia_size_t r = -1) const; bin_search(const T & x,lidia_size_t & pos,lidia_size_t l,lidia_size_t r)184 bool bin_search(const T & x, lidia_size_t & pos, 185 lidia_size_t l, lidia_size_t r) const 186 { 187 return this->bin_search(x, pos, vector_flags::sort_vector_def, 188 l, r); 189 } 190 191 protected: 192 193 bool bin_search_up(const T &, lidia_size_t &, lidia_size_t, lidia_size_t) const; 194 bool bin_search_down(const T &, lidia_size_t &, lidia_size_t, lidia_size_t) const; 195 196 // 197 // functions to insert new elts. into a vector 198 // 199 200 public: 201 202 void insert(const T &, int (*cmp)(const T &, const T &), 203 lidia_size_t l = 0, lidia_size_t r = -1); 204 void insert(const T &, unsigned long sort_direction = vector_flags::sort_vector_def, 205 lidia_size_t l = 0, lidia_size_t r = -1); insert(const T & x,lidia_size_t l,lidia_size_t r)206 void insert(const T & x, lidia_size_t l, lidia_size_t r) 207 { 208 this->insert(x, vector_flags::sort_vector_def, l, r); 209 } 210 211 // 212 // functions to remove elts. from within a vector 213 // 214 215 public: 216 217 bool remove(const T &, int (*cmp)(const T &, const T &), 218 lidia_size_t l = 0, lidia_size_t r = -1); 219 bool remove(const T &, unsigned long sort_direction = vector_flags::sort_vector_def, 220 lidia_size_t l = 0, lidia_size_t r = -1); remove(const T & x,lidia_size_t l,lidia_size_t r)221 bool remove(const T & x, lidia_size_t l, lidia_size_t r) 222 { 223 return this->remove(x, vector_flags::sort_vector_def, l, r); 224 } 225 226 int lex_compare(sort_vector< T > &) const; 227 228 // 229 // miscellaneous 230 // 231 232 public: 233 234 void delete_copies(); 235 }; 236 237 238 239 #ifdef LIDIA_NAMESPACE 240 } // end of namespace LiDIA 241 # undef IN_NAMESPACE_LIDIA 242 #endif 243 244 245 246 #ifdef LIDIA_INCLUDE_CC 247 # include "LiDIA/sort_vector.cc" 248 #endif 249 250 251 252 #endif // LIDIA_SORT_VECTOR_H_GUARD_ 253