idx-vector.cc

Go to the documentation of this file.
00001 /*
00002 
00003 Copyright (C) 1993-2012 John W. Eaton
00004 Copyright (C) 2008-2009 Jaroslav Hajek
00005 Copyright (C) 2009-2010 VZLU Prague
00006 
00007 This file is part of Octave.
00008 
00009 Octave is free software; you can redistribute it and/or modify it
00010 under the terms of the GNU General Public License as published by the
00011 Free Software Foundation; either version 3 of the License, or (at your
00012 option) any later version.
00013 
00014 Octave is distributed in the hope that it will be useful, but WITHOUT
00015 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00016 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
00017 for more details.
00018 
00019 You should have received a copy of the GNU General Public License
00020 along with Octave; see the file COPYING.  If not, see
00021 <http://www.gnu.org/licenses/>.
00022 
00023 */
00024 
00025 #ifdef HAVE_CONFIG_H
00026 #include <config.h>
00027 #endif
00028 
00029 #include <cstdlib>
00030 
00031 #include <iostream>
00032 
00033 #include "idx-vector.h"
00034 #include "Array.h"
00035 #include "Array-util.h"
00036 #include "Sparse.h"
00037 #include "Range.h"
00038 
00039 #include "oct-locbuf.h"
00040 #include "lo-error.h"
00041 #include "lo-mappers.h"
00042 
00043 static void
00044 gripe_invalid_range (void)
00045 {
00046   (*current_liboctave_error_handler)
00047     ("invalid range used as index");
00048 }
00049 
00050 static void
00051 gripe_index_out_of_range (void)
00052 {
00053   (*current_liboctave_error_handler)
00054     ("internal error: idx_vector index out of range");
00055 }
00056 
00057 Array<octave_idx_type>
00058 idx_vector::idx_base_rep::as_array (void)
00059 {
00060   (*current_liboctave_error_handler)
00061     ("internal error: as_array not allowed for this index class");
00062 
00063   return Array<octave_idx_type> ();
00064 }
00065 
00066 DEFINE_OCTAVE_ALLOCATOR(idx_vector::idx_colon_rep);
00067 
00068 idx_vector::idx_colon_rep::idx_colon_rep (char c)
00069 {
00070   if (c != ':')
00071     {
00072       (*current_liboctave_error_handler)
00073         ("internal error: invalid character converted to idx_vector; must be ':'");
00074       err = true;
00075     }
00076 }
00077 
00078 octave_idx_type
00079 idx_vector::idx_colon_rep::checkelem (octave_idx_type i) const
00080 {
00081   if (i < 0)
00082     {
00083       gripe_index_out_of_range ();
00084       return 0;
00085     }
00086   else
00087     return i;
00088 }
00089 
00090 idx_vector::idx_base_rep *
00091 idx_vector::idx_colon_rep::sort_idx (Array<octave_idx_type>&)
00092 {
00093   (*current_liboctave_error_handler)
00094     ("internal error: idx_colon_rep::sort_idx");
00095 
00096   count++;
00097   return this;
00098 }
00099 
00100 std::ostream&
00101 idx_vector::idx_colon_rep::print (std::ostream& os) const
00102 {
00103   return os << ":";
00104 }
00105 
00106 DEFINE_OCTAVE_ALLOCATOR(idx_vector::idx_range_rep);
00107 
00108 idx_vector::idx_range_rep::idx_range_rep (octave_idx_type _start,
00109                                           octave_idx_type _limit,
00110                                           octave_idx_type _step)
00111   : start(_start), len (_step ? std::max((_limit - _start) / _step, static_cast<octave_idx_type> (0)) : -1), step (_step)
00112 {
00113   if (len < 0)
00114     {
00115       gripe_invalid_range ();
00116       err = true;
00117     }
00118   else if (start < 0 || (step < 0 && start + (len-1)*step < 0))
00119     {
00120       gripe_invalid_index ();
00121       err = true;
00122     }
00123 }
00124 
00125 idx_vector::idx_range_rep::idx_range_rep (const Range& r)
00126   : start (0), len (r.nelem ()), step (1)
00127 {
00128   if (len < 0)
00129     {
00130       gripe_invalid_range ();
00131       err = true;
00132     }
00133   else if (len > 0)
00134     {
00135       if (r.all_elements_are_ints ())
00136         {
00137           start = static_cast<octave_idx_type> (r.base ()) - 1;
00138           step = static_cast<octave_idx_type> (r.inc ());
00139           if (start < 0 || (step < 0 && start + (len-1)*step < 0))
00140             {
00141               gripe_invalid_index ();
00142               err = true;
00143             }
00144         }
00145       else
00146         {
00147           gripe_invalid_index ();
00148           err = true;
00149         }
00150     }
00151 }
00152 
00153 octave_idx_type
00154 idx_vector::idx_range_rep::checkelem (octave_idx_type i) const
00155 {
00156   if (i < 0 || i >= len)
00157     {
00158       gripe_index_out_of_range ();
00159       return 0;
00160     }
00161   else
00162     return start + i*step;
00163 }
00164 
00165 idx_vector::idx_base_rep *
00166 idx_vector::idx_range_rep::sort_uniq_clone (bool)
00167 {
00168   if (step < 0)
00169     return new idx_range_rep (start + (len - 1)*step, len, -step, DIRECT);
00170   else
00171     {
00172       count++;
00173       return this;
00174     }
00175 }
00176 
00177 idx_vector::idx_base_rep *
00178 idx_vector::idx_range_rep::sort_idx (Array<octave_idx_type>& idx)
00179 {
00180   if (step < 0 && len > 0)
00181     {
00182       idx.clear (1, len);
00183       for (octave_idx_type i = 0; i < len; i++)
00184         idx.xelem (i) = len - 1 - i;
00185       return new idx_range_rep (start + (len - 1)*step, len, -step, DIRECT);
00186     }
00187   else
00188     {
00189       idx.clear (1, len);
00190       for (octave_idx_type i = 0; i < len; i++)
00191         idx.xelem (i) = i;
00192       count++;
00193       return this;
00194     }
00195 }
00196 
00197 std::ostream&
00198 idx_vector::idx_range_rep::print (std::ostream& os) const
00199 {
00200   os << start << ':' << step << ':' << start + len*step;
00201   return os;
00202 }
00203 
00204 Range
00205 idx_vector::idx_range_rep::unconvert (void) const
00206 {
00207   return Range (static_cast<double> (start+1),
00208                 static_cast<double> (step), len);
00209 }
00210 
00211 Array<octave_idx_type>
00212 idx_vector::idx_range_rep::as_array (void)
00213 {
00214   Array<octave_idx_type> retval (dim_vector (1, len));
00215   for (octave_idx_type i = 0; i < len; i++)
00216     retval.xelem (i) = start + i*step;
00217 
00218   return retval;
00219 }
00220 
00221 inline octave_idx_type
00222 convert_index (octave_idx_type i, bool& conv_error,
00223                octave_idx_type& ext)
00224 {
00225   if (i <= 0)
00226     conv_error = true;
00227 
00228   if (ext < i)
00229     ext = i;
00230 
00231   return i - 1;
00232 }
00233 
00234 inline octave_idx_type
00235 convert_index (double x, bool& conv_error, octave_idx_type& ext)
00236 {
00237   octave_idx_type i = static_cast<octave_idx_type> (x);
00238 
00239   if (static_cast<double> (i) != x)
00240     conv_error = true;
00241 
00242   return convert_index (i, conv_error, ext);
00243 }
00244 
00245 inline octave_idx_type
00246 convert_index (float x, bool& conv_error, octave_idx_type& ext)
00247 {
00248   return convert_index (static_cast<double> (x), conv_error, ext);
00249 }
00250 
00251 template <class T>
00252 inline octave_idx_type
00253 convert_index (octave_int<T> x, bool& conv_error,
00254                octave_idx_type& ext)
00255 {
00256   octave_idx_type i = octave_int<octave_idx_type> (x).value ();
00257 
00258   return convert_index (i, conv_error, ext);
00259 }
00260 
00261 DEFINE_OCTAVE_ALLOCATOR(idx_vector::idx_scalar_rep);
00262 
00263 template <class T>
00264 idx_vector::idx_scalar_rep::idx_scalar_rep (T x)
00265   : data (0)
00266 {
00267   octave_idx_type dummy = 0;
00268 
00269   data = convert_index (x, err, dummy);
00270 
00271   if (err)
00272     gripe_invalid_index ();
00273 }
00274 
00275 idx_vector::idx_scalar_rep::idx_scalar_rep (octave_idx_type i)
00276   : data (i)
00277 {
00278   if (data < 0)
00279     {
00280       gripe_invalid_index ();
00281       err = true;
00282     }
00283 }
00284 
00285 octave_idx_type
00286 idx_vector::idx_scalar_rep::checkelem (octave_idx_type i) const
00287 {
00288   if (i != 0)
00289     gripe_index_out_of_range ();
00290 
00291   return data;
00292 }
00293 
00294 idx_vector::idx_base_rep *
00295 idx_vector::idx_scalar_rep::sort_idx (Array<octave_idx_type>& idx)
00296 {
00297   idx.clear (1, 1);
00298   idx.fill (0);
00299   count++;
00300   return this;
00301 }
00302 
00303 std::ostream& idx_vector::idx_scalar_rep::print (std::ostream& os) const
00304 {
00305   return os << data;
00306 }
00307 
00308 double
00309 idx_vector::idx_scalar_rep::unconvert (void) const
00310 {
00311   return data + 1;
00312 }
00313 
00314 Array<octave_idx_type>
00315 idx_vector::idx_scalar_rep::as_array (void)
00316 {
00317   return Array<octave_idx_type> (dim_vector (1, 1), data);
00318 }
00319 
00320 DEFINE_OCTAVE_ALLOCATOR(idx_vector::idx_vector_rep);
00321 
00322 template <class T>
00323 idx_vector::idx_vector_rep::idx_vector_rep (const Array<T>& nda)
00324   : data (0), len (nda.numel ()), ext (0), aowner (0), orig_dims (nda.dims ())
00325 {
00326   if (len != 0)
00327     {
00328       octave_idx_type *d = new octave_idx_type[len];
00329       for (octave_idx_type i = 0; i < len; i++)
00330         d[i] = convert_index (nda.xelem (i), err, ext);
00331       data = d;
00332 
00333       if (err)
00334       {
00335         delete [] data;
00336         gripe_invalid_index ();
00337       }
00338     }
00339 }
00340 
00341 // Note that this makes a shallow copy of the index array.
00342 
00343 idx_vector::idx_vector_rep::idx_vector_rep (const Array<octave_idx_type>& inda)
00344   : data (inda.data ()), len (inda.numel ()), ext (0),
00345     aowner (new Array<octave_idx_type> (inda)), orig_dims (inda.dims ())
00346 {
00347   if (len != 0)
00348     {
00349       octave_idx_type max = -1;
00350       for (octave_idx_type i = 0; i < len; i++)
00351         {
00352           octave_idx_type k = inda.xelem (i);
00353           if (k < 0)
00354             err = true;
00355           else if (k > max)
00356             max = k;
00357         }
00358 
00359       ext = max + 1;
00360 
00361       if (err)
00362         gripe_invalid_index ();
00363     }
00364 }
00365 
00366 idx_vector::idx_vector_rep::idx_vector_rep (const Array<octave_idx_type>& inda,
00367                                             octave_idx_type _ext, direct)
00368   : data (inda.data ()), len (inda.numel ()), ext (_ext),
00369     aowner (new Array<octave_idx_type> (inda)), orig_dims (inda.dims ())
00370 {
00371   // No checking.
00372   if (ext < 0)
00373     {
00374       octave_idx_type max = -1;
00375       for (octave_idx_type i = 0; i < len; i++)
00376         if (data[i] > max)
00377           max = data[i];
00378 
00379       ext = max + 1;
00380     }
00381 }
00382 
00383 idx_vector::idx_vector_rep::idx_vector_rep (bool b)
00384   : data (0), len (b ? 1 : 0), ext (0), aowner (0), orig_dims (len, len)
00385 {
00386   if (len != 0)
00387     {
00388       octave_idx_type *d = new octave_idx_type [1];
00389       d[0] = 0;
00390       data = d;
00391       ext = 1;
00392     }
00393 }
00394 
00395 idx_vector::idx_vector_rep::idx_vector_rep (const Array<bool>& bnda,
00396                                             octave_idx_type nnz)
00397   : data (0), len (nnz), ext (0), aowner (0), orig_dims ()
00398 {
00399   if (nnz < 0)
00400     len = bnda.nnz ();
00401 
00402   const dim_vector dv = bnda.dims ();
00403 
00404   if (! dv.all_zero ())
00405     orig_dims = ((dv.length () == 2 && dv(0) == 1)
00406                  ? dim_vector (1, len) : dim_vector (len, 1));
00407 
00408   if (len != 0)
00409     {
00410       octave_idx_type *d = new octave_idx_type [len];
00411 
00412       octave_idx_type ntot = bnda.length ();
00413 
00414       octave_idx_type k = 0;
00415       for (octave_idx_type i = 0; i < ntot; i++)
00416         if (bnda.xelem (i))
00417           d[k++] = i;
00418 
00419       data = d;
00420 
00421       ext = d[k-1] + 1;
00422     }
00423 }
00424 
00425 idx_vector::idx_vector_rep::idx_vector_rep (const Sparse<bool>& bnda)
00426   : data (0), len (0), ext (0), aowner (0), orig_dims ()
00427 {
00428   for (octave_idx_type i = 0, l = bnda.nnz (); i < l; i++)
00429     if (bnda.data (i)) len++;
00430 
00431   dim_vector dv = bnda.dims ();
00432 
00433   orig_dims = ((dv.length () == 2 && dv(0) == 1)
00434                ? dim_vector (1, len) : orig_dims = dim_vector (len, 1));
00435 
00436   if (len != 0)
00437     {
00438       octave_idx_type *d = new octave_idx_type [len];
00439 
00440       octave_idx_type nnz = bnda.nnz ();
00441 
00442       octave_idx_type k = 0;
00443       // FIXME: I hope this is OK, i.e. the element iterated this way are correctly ordered.
00444       for (octave_idx_type i = 0; i < nnz; i++)
00445         {
00446           if (bnda.data (i))
00447             d[k++] = bnda.cidx (i) + bnda.rows () * bnda.ridx (i);
00448         }
00449 
00450       data = d;
00451 
00452       ext = d[k-1] + 1;
00453     }
00454 }
00455 
00456 idx_vector::idx_vector_rep::~idx_vector_rep (void)
00457 {
00458   if (aowner)
00459     delete aowner;
00460   else
00461     delete [] data;
00462 }
00463 
00464 octave_idx_type
00465 idx_vector::idx_vector_rep::checkelem (octave_idx_type n) const
00466 {
00467   if (n < 0 || n >= len)
00468     {
00469       gripe_invalid_index ();
00470       return 0;
00471     }
00472 
00473   return xelem (n);
00474 }
00475 
00476 idx_vector::idx_base_rep *
00477 idx_vector::idx_vector_rep::sort_uniq_clone (bool uniq)
00478 {
00479   if (len == 0)
00480     {
00481       count++;
00482       return this;
00483     }
00484 
00485   // This is wrapped in auto_ptr so that we don't leak on out-of-memory.
00486   std::auto_ptr<idx_vector_rep> new_rep (
00487     new idx_vector_rep (0, len, ext, orig_dims, DIRECT));
00488 
00489   if (ext > len*xlog2 (1.0 + len))
00490     {
00491       // Use standard sort via octave_sort.
00492       octave_idx_type *new_data = new octave_idx_type[len];
00493       new_rep->data = new_data;
00494 
00495       std::copy (data, data + len, new_data);
00496       octave_sort<octave_idx_type> lsort;
00497       lsort.set_compare (ASCENDING);
00498       lsort.sort (new_data, len);
00499 
00500       if (uniq)
00501         {
00502           octave_idx_type new_len = std::unique (new_data, new_data + len) - new_data;
00503           new_rep->len = new_len;
00504           if (new_rep->orig_dims.length () == 2 && new_rep->orig_dims(0) == 1)
00505             new_rep->orig_dims = dim_vector (1, new_len);
00506           else
00507             new_rep->orig_dims = dim_vector (new_len, 1);
00508         }
00509     }
00510   else if (uniq)
00511     {
00512       // Use two-pass bucket sort (only a mask array needed).
00513       OCTAVE_LOCAL_BUFFER_INIT (bool, has, ext, false);
00514       for (octave_idx_type i = 0; i < len; i++)
00515         has[data[i]] = true;
00516 
00517       octave_idx_type new_len = 0;
00518       for (octave_idx_type i = 0; i < ext; i++)
00519         new_len += has[i];
00520 
00521       new_rep->len = new_len;
00522       if (new_rep->orig_dims.length () == 2 && new_rep->orig_dims(0) == 1)
00523         new_rep->orig_dims = dim_vector (1, new_len);
00524       else
00525         new_rep->orig_dims = dim_vector (new_len, 1);
00526 
00527       octave_idx_type *new_data = new octave_idx_type[new_len];
00528       new_rep->data = new_data;
00529 
00530       for (octave_idx_type i = 0, j = 0; i < ext; i++)
00531         if (has[i])
00532           new_data[j++] = i;
00533     }
00534   else
00535     {
00536       // Use two-pass bucket sort.
00537       OCTAVE_LOCAL_BUFFER_INIT (octave_idx_type, cnt, ext, 0);
00538       for (octave_idx_type i = 0; i < len; i++)
00539         cnt[data[i]]++;
00540 
00541       octave_idx_type *new_data = new octave_idx_type[len];
00542       new_rep->data = new_data;
00543 
00544       for (octave_idx_type i = 0, j = 0; i < ext; i++)
00545         {
00546           for (octave_idx_type k = 0; k < cnt[i]; k++)
00547             new_data[j++] = i;
00548         }
00549     }
00550 
00551   return new_rep.release ();
00552 }
00553 
00554 idx_vector::idx_base_rep *
00555 idx_vector::idx_vector_rep::sort_idx (Array<octave_idx_type>& idx)
00556 {
00557   // This is wrapped in auto_ptr so that we don't leak on out-of-memory.
00558   std::auto_ptr<idx_vector_rep> new_rep (
00559     new idx_vector_rep (0, len, ext, orig_dims, DIRECT));
00560 
00561   if (ext > len*xlog2 (1.0 + len))
00562     {
00563       // Use standard sort via octave_sort.
00564       idx.clear (orig_dims);
00565       octave_idx_type *idx_data = idx.fortran_vec ();
00566       for (octave_idx_type i = 0; i < len; i++)
00567         idx_data[i] = i;
00568 
00569       octave_idx_type *new_data = new octave_idx_type [len];
00570       new_rep->data = new_data;
00571       std::copy (data, data + len, new_data);
00572 
00573       octave_sort<octave_idx_type> lsort;
00574       lsort.set_compare (ASCENDING);
00575       lsort.sort (new_data, idx_data, len);
00576     }
00577   else
00578     {
00579       // Use two-pass bucket sort.
00580       OCTAVE_LOCAL_BUFFER_INIT (octave_idx_type, cnt, ext, 0);
00581 
00582       for (octave_idx_type i = 0; i < len; i++)
00583         cnt[data[i]]++;
00584 
00585       idx.clear (orig_dims);
00586       octave_idx_type *idx_data = idx.fortran_vec ();
00587 
00588       octave_idx_type *new_data = new octave_idx_type [len];
00589       new_rep->data = new_data;
00590 
00591       for (octave_idx_type i = 0, k = 0; i < ext; i++)
00592         {
00593           octave_idx_type j = cnt[i];
00594           cnt[i] = k;
00595           k += j;
00596         }
00597 
00598       for (octave_idx_type i = 0; i < len; i++)
00599         {
00600           octave_idx_type j = data[i], k = cnt[j]++;
00601           new_data[k] = j;
00602           idx_data[k] = i;
00603         }
00604     }
00605 
00606   return new_rep.release ();
00607 }
00608 
00609 std::ostream&
00610 idx_vector::idx_vector_rep::print (std::ostream& os) const
00611 {
00612   os << '[';
00613 
00614   for (octave_idx_type ii = 0; ii < len - 1; ii++)
00615     os << data[ii] << ',' << ' ';
00616 
00617   if (len > 0)
00618     os << data[len-1]; os << ']';
00619 
00620   return os;
00621 }
00622 
00623 Array<double>
00624 idx_vector::idx_vector_rep::unconvert (void) const
00625 {
00626   Array<double> retval (orig_dims);
00627   for (octave_idx_type i = 0; i < len; i++)
00628     retval.xelem (i) = data[i] + 1;
00629   return retval;
00630 }
00631 
00632 Array<octave_idx_type>
00633 idx_vector::idx_vector_rep::as_array (void)
00634 {
00635   if (aowner)
00636     return *aowner;
00637   else
00638     {
00639       Array<octave_idx_type> retval (orig_dims);
00640       std::memcpy (retval.fortran_vec (), data, len*sizeof (octave_idx_type));
00641       // Delete the old copy and share the data instead to save memory.
00642       delete [] data;
00643       data = retval.fortran_vec ();
00644       aowner = new Array<octave_idx_type> (retval);
00645       return retval;
00646     }
00647 }
00648 
00649 DEFINE_OCTAVE_ALLOCATOR(idx_vector::idx_mask_rep);
00650 
00651 idx_vector::idx_mask_rep::idx_mask_rep (bool b)
00652   : data (0), len (b ? 1 : 0), ext (0), lsti (-1), lste (-1),
00653     aowner (0), orig_dims (len, len)
00654 {
00655   if (len != 0)
00656     {
00657       bool *d = new bool [1];
00658       d[0] = true;
00659       data = d;
00660       ext = 1;
00661     }
00662 }
00663 
00664 idx_vector::idx_mask_rep::idx_mask_rep (const Array<bool>& bnda,
00665                                         octave_idx_type nnz)
00666   : data (0), len (nnz), ext (bnda.numel ()), lsti (-1), lste (-1),
00667     aowner (0), orig_dims ()
00668 {
00669   if (nnz < 0)
00670     len = bnda.nnz ();
00671 
00672   // We truncate the extent as much as possible. For Matlab
00673   // compatibility, but maybe it's not a bad idea anyway.
00674   while (ext > 0 && ! bnda(ext-1))
00675     ext--;
00676 
00677   const dim_vector dv = bnda.dims ();
00678 
00679   if (! dv.all_zero ())
00680     orig_dims = ((dv.length () == 2 && dv(0) == 1)
00681                  ? dim_vector (1, len) : dim_vector (len, 1));
00682 
00683   aowner = new Array<bool> (bnda);
00684   data = bnda.data ();
00685 }
00686 
00687 idx_vector::idx_mask_rep::~idx_mask_rep (void)
00688 {
00689   if (aowner)
00690     delete aowner;
00691   else
00692     delete [] data;
00693 }
00694 
00695 octave_idx_type
00696 idx_vector::idx_mask_rep::xelem (octave_idx_type n) const
00697 {
00698   if (n == lsti + 1)
00699     {
00700       lsti = n;
00701       while (! data[++lste]) ;
00702     }
00703   else
00704     {
00705       lsti = n++;
00706       lste = -1;
00707       while (n > 0)
00708         if (data[++lste]) --n;
00709     }
00710   return lste;
00711 }
00712 
00713 octave_idx_type
00714 idx_vector::idx_mask_rep::checkelem (octave_idx_type n) const
00715 {
00716   if (n < 0 || n >= len)
00717     {
00718       gripe_invalid_index ();
00719       return 0;
00720     }
00721 
00722   return xelem (n);
00723 }
00724 
00725 std::ostream&
00726 idx_vector::idx_mask_rep::print (std::ostream& os) const
00727 {
00728   os << '[';
00729 
00730   for (octave_idx_type ii = 0; ii < ext - 1; ii++)
00731     os << data[ii] << ',' << ' ';
00732 
00733   if (ext > 0)
00734     os << data[ext-1]; os << ']';
00735 
00736   return os;
00737 }
00738 
00739 Array<bool>
00740 idx_vector::idx_mask_rep::unconvert (void) const
00741 {
00742   if (aowner)
00743     return *aowner;
00744   else
00745     {
00746       Array<bool> retval (dim_vector (ext, 1));
00747       for (octave_idx_type i = 0; i < ext; i++)
00748         retval.xelem (i) = data[i];
00749       return retval;
00750     }
00751 }
00752 
00753 Array<octave_idx_type>
00754 idx_vector::idx_mask_rep::as_array (void)
00755 {
00756   if (aowner)
00757     return aowner->find ().reshape (orig_dims);
00758   else
00759     {
00760       Array<bool> retval (orig_dims);
00761       for (octave_idx_type i = 0, j = 0; i < ext; i++)
00762         if (data[i])
00763           retval.xelem (j++) = i;
00764 
00765       return retval;
00766     }
00767 }
00768 
00769 idx_vector::idx_base_rep *
00770 idx_vector::idx_mask_rep::sort_idx (Array<octave_idx_type>& idx)
00771 {
00772   idx.clear (len, 1);
00773   for (octave_idx_type i = 0; i < len; i++)
00774     idx.xelem (i) = i;
00775 
00776   count++;
00777   return this;
00778 }
00779 
00780 const idx_vector idx_vector::colon (new idx_vector::idx_colon_rep ());
00781 
00782 idx_vector::idx_vector (const Array<bool>& bnda)
00783   : rep (0)
00784 {
00785   // Convert only if it means saving at least half the memory.
00786   static const int factor = (2 * sizeof (octave_idx_type));
00787   octave_idx_type nnz = bnda.nnz ();
00788   if (nnz <= bnda.numel () / factor)
00789     rep = new idx_vector_rep (bnda, nnz);
00790   else
00791     rep = new idx_mask_rep (bnda, nnz);
00792 }
00793 
00794 bool
00795 idx_vector::maybe_reduce (octave_idx_type n, const idx_vector& j,
00796                           octave_idx_type nj)
00797 {
00798   bool reduced = false;
00799 
00800   // Empty index always reduces.
00801   if (rep->length (n) == 0)
00802     {
00803       *this = idx_vector ();
00804       return true;
00805     }
00806 
00807   // Possibly skip singleton dims.
00808   if (n == 1 && rep->is_colon_equiv (n))
00809     {
00810       *this = j;
00811       return true;
00812     }
00813 
00814   if (nj == 1 && j.is_colon_equiv (nj))
00815     return true;
00816 
00817   switch (j.idx_class ())
00818     {
00819     case class_colon:
00820       switch (rep->idx_class ())
00821         {
00822         case class_colon:
00823           // (:,:) reduces to (:)
00824           reduced = true;
00825           break;
00826 
00827         case class_scalar:
00828           {
00829             // (i,:) reduces to a range.
00830             idx_scalar_rep * r = dynamic_cast<idx_scalar_rep *> (rep);
00831             octave_idx_type k = r->get_data ();
00832             *this = new idx_range_rep (k, nj, n, DIRECT);
00833             reduced = true;
00834           }
00835           break;
00836 
00837         case class_range:
00838           {
00839             // (i:k:end,:) reduces to a range if i <= k and k divides n.
00840             idx_range_rep * r = dynamic_cast<idx_range_rep *> (rep);
00841             octave_idx_type s = r->get_start (), l = r->length (n);
00842             octave_idx_type t = r->get_step ();
00843             if (l*t == n)
00844               {
00845                 *this = new idx_range_rep (s, l * nj, t, DIRECT);
00846                 reduced = true;
00847               }
00848           }
00849           break;
00850 
00851         default:
00852           break;
00853         }
00854       break;
00855 
00856     case class_range:
00857       switch (rep->idx_class ())
00858         {
00859         case class_colon:
00860           {
00861             // (:,i:j) reduces to a range (the step must be 1)
00862             idx_range_rep * rj = dynamic_cast<idx_range_rep *> (j.rep);
00863             if (rj->get_step () == 1)
00864               {
00865                 octave_idx_type sj = rj->get_start (), lj = rj->length (nj);
00866                 *this = new idx_range_rep (sj * n, lj * n, 1, DIRECT);
00867                 reduced = true;
00868               }
00869           }
00870           break;
00871 
00872         case class_scalar:
00873           {
00874             // (k,i:d:j) reduces to a range.
00875             idx_scalar_rep * r = dynamic_cast<idx_scalar_rep *> (rep);
00876             idx_range_rep * rj = dynamic_cast<idx_range_rep *> (j.rep);
00877             octave_idx_type k = r->get_data ();
00878             octave_idx_type sj = rj->get_start (), lj = rj->length (nj);
00879             octave_idx_type tj = rj->get_step ();
00880             *this = new idx_range_rep (n * sj + k, lj, n * tj, DIRECT);
00881             reduced = true;
00882           }
00883           break;
00884 
00885         case class_range:
00886           {
00887             // (i:k:end,p:q) reduces to a range if i <= k and k divides n.
00888             // (ones (1, m), ones (1, n)) reduces to (ones (1, m*n))
00889             idx_range_rep * r = dynamic_cast<idx_range_rep *> (rep);
00890             octave_idx_type s = r->get_start (), l = r->length (n);
00891             octave_idx_type t = r->get_step ();
00892             idx_range_rep * rj = dynamic_cast<idx_range_rep *> (j.rep);
00893             octave_idx_type sj = rj->get_start (), lj = rj->length (nj);
00894             octave_idx_type tj = rj->get_step ();
00895             if ((l*t == n && tj == 1) || (t == 0 && tj == 0))
00896               {
00897                 *this = new idx_range_rep (s + n * sj, l * lj, t, DIRECT);
00898                 reduced = true;
00899               }
00900           }
00901           break;
00902 
00903         default:
00904           break;
00905         }
00906       break;
00907 
00908     case class_scalar:
00909       switch (rep->idx_class ())
00910         {
00911         case class_scalar:
00912           {
00913             // (i,j) reduces to a single index.
00914             idx_scalar_rep * r = dynamic_cast<idx_scalar_rep *> (rep);
00915             idx_scalar_rep * rj = dynamic_cast<idx_scalar_rep *> (j.rep);
00916             octave_idx_type k = r->get_data () + n * rj->get_data ();
00917             *this = new idx_scalar_rep (k, DIRECT);
00918             reduced = true;
00919           }
00920           break;
00921 
00922         case class_range:
00923           {
00924             // (i:d:j,k) reduces to a range.
00925             idx_range_rep * r = dynamic_cast<idx_range_rep *> (rep);
00926             idx_scalar_rep * rj = dynamic_cast<idx_scalar_rep *> (j.rep);
00927             octave_idx_type s = r->get_start (), l = r->length (nj);
00928             octave_idx_type t = r->get_step ();
00929             octave_idx_type k = rj->get_data ();
00930             *this = new idx_range_rep (n * k + s, l, t, DIRECT);
00931             reduced = true;
00932           }
00933           break;
00934 
00935         case class_colon:
00936           {
00937             // (:,k) reduces to a range.
00938             idx_scalar_rep * rj = dynamic_cast<idx_scalar_rep *> (j.rep);
00939             octave_idx_type k = rj->get_data ();
00940             *this = new idx_range_rep (n * k, n, 1, DIRECT);
00941             reduced = true;
00942           }
00943           break;
00944 
00945         default:
00946           break;
00947         }
00948       break;
00949 
00950     default:
00951       break;
00952     }
00953 
00954   return reduced;
00955 }
00956 
00957 bool
00958 idx_vector::is_cont_range (octave_idx_type n,
00959                            octave_idx_type& l, octave_idx_type& u) const
00960 {
00961   bool res = false;
00962 
00963   switch (rep->idx_class ())
00964     {
00965     case class_colon:
00966       l = 0; u = n;
00967       res = true;
00968       break;
00969 
00970     case class_range:
00971       {
00972         idx_range_rep * r = dynamic_cast<idx_range_rep *> (rep);
00973         if (r->get_step () == 1)
00974           {
00975             l = r->get_start ();
00976             u = l + r->length (n);
00977             res = true;
00978           }
00979       }
00980       break;
00981 
00982     case class_scalar:
00983       {
00984         idx_scalar_rep * r = dynamic_cast<idx_scalar_rep *> (rep);
00985         l = r->get_data ();
00986         u = l + 1;
00987         res = true;
00988       }
00989       break;
00990 
00991     case class_mask:
00992       {
00993         idx_mask_rep * r = dynamic_cast<idx_mask_rep *> (rep);
00994         octave_idx_type ext = r->extent (0), len = r->length (0);
00995         if (ext == len)
00996           {
00997             l = 0;
00998             u = len;
00999             res = true;
01000           }
01001       }
01002 
01003     default:
01004       break;
01005     }
01006 
01007   return res;
01008 }
01009 
01010 octave_idx_type
01011 idx_vector::increment (void) const
01012 {
01013   octave_idx_type retval = 0;
01014 
01015   switch (rep->idx_class ())
01016     {
01017     case class_colon:
01018       retval = 1;
01019       break;
01020 
01021     case class_range:
01022       retval = dynamic_cast<idx_range_rep *> (rep) -> get_step ();
01023       break;
01024 
01025     case class_vector:
01026     case class_mask:
01027       {
01028         if (length (0) > 1)
01029           retval = elem (1) - elem (0);
01030       }
01031       break;
01032 
01033     default:
01034       break;
01035     }
01036 
01037   return retval;
01038 }
01039 
01040 const octave_idx_type *
01041 idx_vector::raw (void)
01042 {
01043   if (rep->idx_class () != class_vector)
01044     *this = idx_vector (as_array (), extent (0));
01045 
01046   idx_vector_rep * r = dynamic_cast<idx_vector_rep *> (rep);
01047 
01048   assert (r != 0);
01049 
01050   return r->get_data ();
01051 }
01052 
01053 void
01054 idx_vector::copy_data (octave_idx_type *data) const
01055 {
01056   octave_idx_type len = rep->length (0);
01057 
01058   switch (rep->idx_class ())
01059     {
01060     case class_colon:
01061       current_liboctave_error_handler ("colon not allowed");
01062       break;
01063 
01064     case class_range:
01065       {
01066         idx_range_rep * r = dynamic_cast<idx_range_rep *> (rep);
01067         octave_idx_type start = r->get_start (), step = r->get_step ();
01068         octave_idx_type i, j;
01069         if (step == 1)
01070           for (i = start, j = start + len; i < j; i++) *data++ = i;
01071         else if (step == -1)
01072           for (i = start, j = start - len; i > j; i--) *data++ = i;
01073         else
01074           for (i = 0, j = start; i < len; i++, j += step) *data++ = j;
01075       }
01076       break;
01077 
01078     case class_scalar:
01079       {
01080         idx_scalar_rep * r = dynamic_cast<idx_scalar_rep *> (rep);
01081         *data = r->get_data ();
01082       }
01083       break;
01084 
01085     case class_vector:
01086       {
01087         idx_vector_rep * r = dynamic_cast<idx_vector_rep *> (rep);
01088         const octave_idx_type *rdata = r->get_data ();
01089         copy_or_memcpy (len, rdata, data);
01090       }
01091       break;
01092 
01093     case class_mask:
01094       {
01095         idx_mask_rep * r = dynamic_cast<idx_mask_rep *> (rep);
01096         const bool *mask = r->get_data ();
01097         octave_idx_type ext = r->extent (0);
01098         for (octave_idx_type i = 0, j = 0; i < ext; i++)
01099           if (mask[i])
01100             data[j++] = i;
01101       }
01102     break;
01103 
01104     default:
01105       assert (false);
01106       break;
01107     }
01108 }
01109 
01110 idx_vector
01111 idx_vector::complement (octave_idx_type n) const
01112 {
01113   idx_vector retval;
01114   if (extent (n) > n)
01115     (*current_liboctave_error_handler)
01116       ("internal error: out of range complement index requested");
01117 
01118   if (idx_class () == class_mask)
01119     {
01120       idx_mask_rep * r = dynamic_cast<idx_mask_rep *> (rep);
01121       octave_idx_type nz = r->length (0), ext = r->extent (0);
01122       Array<bool> mask (dim_vector (n, 1));
01123       const bool *data = r->get_data ();
01124       bool *ndata = mask.fortran_vec ();
01125       for (octave_idx_type i = 0; i < ext; i++)
01126         ndata[i] = ! data[i];
01127       for (octave_idx_type i = ext; i < n; i++)
01128         ndata[i] = true;
01129       retval = new idx_mask_rep (mask, n - nz);
01130     }
01131   else
01132     {
01133       Array<bool> mask (dim_vector (n, 1), true);
01134       fill (false, length (n), mask.fortran_vec ());
01135       retval = idx_vector (mask);
01136     }
01137 
01138   return retval;
01139 }
01140 
01141 bool
01142 idx_vector::is_permutation (octave_idx_type n) const
01143 {
01144   bool retval = false;
01145 
01146   if (is_colon_equiv (n))
01147     retval = true;
01148   else if (length (n) == n && extent(n) == n)
01149     {
01150       OCTAVE_LOCAL_BUFFER_INIT (bool, left, n, true);
01151 
01152       retval = true;
01153 
01154       for (octave_idx_type i = 0, len = length (); i < len; i++)
01155         {
01156           octave_idx_type k = xelem (i);
01157           if (left[k])
01158               left[k] = false;
01159           else
01160             {
01161               retval = false;
01162               break;
01163             }
01164         }
01165     }
01166 
01167   return retval;
01168 }
01169 
01170 idx_vector
01171 idx_vector::inverse_permutation (octave_idx_type n) const
01172 {
01173   assert (n == length (n));
01174 
01175   idx_vector retval;
01176 
01177   switch (idx_class ())
01178     {
01179     case class_range:
01180       {
01181         if (increment () == -1)
01182           retval = sorted ();
01183         else
01184           retval = *this;
01185         break;
01186       }
01187     case class_vector:
01188       {
01189         idx_vector_rep *r = dynamic_cast<idx_vector_rep *> (rep);
01190         const octave_idx_type *ri = r->get_data ();
01191         Array<octave_idx_type> idx (orig_dimensions ());
01192         for (octave_idx_type i = 0; i < n; i++)
01193           idx.xelem(ri[i]) = i;
01194         retval = new idx_vector_rep (idx, r->extent (0), DIRECT);
01195         break;
01196       }
01197     default:
01198       retval = *this;
01199       break;
01200     }
01201 
01202   return retval;
01203 }
01204 
01205 idx_vector
01206 idx_vector::unmask (void) const
01207 {
01208   if (idx_class () == class_mask)
01209     {
01210       idx_mask_rep * r = dynamic_cast<idx_mask_rep *> (rep);
01211       const bool *data = r->get_data ();
01212       octave_idx_type ext = r->extent (0), len = r->length (0);
01213       octave_idx_type *idata = new octave_idx_type [len];
01214 
01215       for (octave_idx_type i = 0, j = 0; i < ext; i++)
01216         if (data[i])
01217           idata[j++] = i;
01218 
01219       ext = len > 0 ? idata[len - 1] + 1 : 0;
01220 
01221       return new idx_vector_rep (idata, len, ext, r->orig_dimensions (),
01222                                  DIRECT);
01223     }
01224   else
01225     return *this;
01226 }
01227 
01228 void idx_vector::unconvert (idx_class_type& iclass,
01229                             double& scalar, Range& range,
01230                             Array<double>& array, Array<bool>& mask) const
01231 {
01232   iclass = idx_class ();
01233   switch (iclass)
01234     {
01235     case class_colon:
01236       break;
01237 
01238     case class_range:
01239       {
01240         idx_range_rep *r = dynamic_cast<idx_range_rep *> (rep);
01241         range = r->unconvert ();
01242       }
01243       break;
01244 
01245     case class_scalar:
01246       {
01247         idx_scalar_rep *r = dynamic_cast<idx_scalar_rep *> (rep);
01248         scalar = r->unconvert ();
01249       }
01250       break;
01251 
01252     case class_vector:
01253       {
01254         idx_vector_rep *r = dynamic_cast<idx_vector_rep *> (rep);
01255         array = r->unconvert ();
01256       }
01257       break;
01258 
01259     case class_mask:
01260       {
01261         idx_mask_rep *r = dynamic_cast<idx_mask_rep *> (rep);
01262         mask = r->unconvert ();
01263       }
01264       break;
01265 
01266     default:
01267       assert (false);
01268       break;
01269     }
01270 }
01271 
01272 Array<octave_idx_type>
01273 idx_vector::as_array (void) const
01274 {
01275   return rep->as_array ();
01276 }
01277 
01278 bool
01279 idx_vector::is_vector (void) const
01280 {
01281   return idx_class () != class_vector || orig_dimensions ().is_vector ();
01282 }
01283 
01284 octave_idx_type
01285 idx_vector::freeze (octave_idx_type z_len, const char *, bool resize_ok)
01286 {
01287   if (! resize_ok && extent (z_len) > z_len)
01288     {
01289       (*current_liboctave_error_handler)
01290         ("invalid matrix index = %d", extent (z_len));
01291       rep->err = true;
01292       chkerr ();
01293     }
01294 
01295   return length (z_len);
01296 }
01297 
01298 octave_idx_type
01299 idx_vector::ones_count () const
01300 {
01301   octave_idx_type n = 0;
01302 
01303   if (is_colon ())
01304     n = 1;
01305   else
01306     {
01307       for (octave_idx_type i = 0; i < length (1); i++)
01308         if (xelem (i) == 0)
01309           n++;
01310     }
01311 
01312   return n;
01313 }
01314 
01315 // Instantiate the octave_int constructors we want.
01316 #define INSTANTIATE_SCALAR_VECTOR_REP_CONST(T) \
01317   template OCTAVE_API idx_vector::idx_scalar_rep::idx_scalar_rep (T); \
01318   template OCTAVE_API idx_vector::idx_vector_rep::idx_vector_rep (const Array<T>&);
01319 
01320 INSTANTIATE_SCALAR_VECTOR_REP_CONST (float)
01321 INSTANTIATE_SCALAR_VECTOR_REP_CONST (double)
01322 INSTANTIATE_SCALAR_VECTOR_REP_CONST (octave_int8)
01323 INSTANTIATE_SCALAR_VECTOR_REP_CONST (octave_int16)
01324 INSTANTIATE_SCALAR_VECTOR_REP_CONST (octave_int32)
01325 INSTANTIATE_SCALAR_VECTOR_REP_CONST (octave_int64)
01326 INSTANTIATE_SCALAR_VECTOR_REP_CONST (octave_uint8)
01327 INSTANTIATE_SCALAR_VECTOR_REP_CONST (octave_uint16)
01328 INSTANTIATE_SCALAR_VECTOR_REP_CONST (octave_uint32)
01329 INSTANTIATE_SCALAR_VECTOR_REP_CONST (octave_uint64)
01330 
01331 /*
01332 
01333 %!error id=Octave:index-out-of-bounds 1(find([1,1] != 0))
01334 %!assert ((1:3)(find([1,0,1] != 0)), [1,3])
01335 
01336 */
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Defines