← Back to branch summary

~ubuntu-branches/ubuntu/wily/octave-miscellaneous/wily

« back to all changes in this revision

Viewing changes to src/sample.cc

  • Committer: Package Import Robot
  • Author(s): Sébastien Villemot, Rafael Laboissiere, Sébastien Villemot
  • Date: 2012-10-17 13:40:55 UTC
  • mfrom: (1.2.1) (12 sid)
  • mto: This revision was merged to the branch mainline in revision 13.
  • Revision ID: package-import@ubuntu.com-20121017134055-vatltexghy77fnv7
Tags: 1.2.0-1
[ Rafael Laboissiere ]
* Imported Upstream version 1.2.0
* Bump Standards-Version to 3.9.4 (no changes needed)
* Refresh for new upstream release
* Use Sébastien Villemot's @debian.org email address
* Remove obsolete DM-Upload-Allowed flag
* Add patch autoload-yes.patch
* Add copyright info for file lauchli.m (included in a Debian patch)
* Add patch partcnt-test-succeeds.patch
* Build-depends on octave-pkg-dev >= 1.0.3

[ Sébastien Villemot ]
* debian/control: fix versioned dependency on debhelper
* Add lintian override for false positive on hardening (fortify)

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/sample.cc
 
1
// Copyright (C) 2011 Piotr Krzyzanowski <piotr.krzyzanowski@mimuw.edu.pl>
 
2
//
 
3
// This program is free software; you can redistribute it and/or modify it under
 
4
// the terms of the GNU General Public License as published by the Free Software
 
5
// Foundation; either version 3 of the License, or (at your option) any later
 
6
// version.
 
7
//
 
8
// This program is distributed in the hope that it will be useful, but WITHOUT
 
9
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 
10
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 
11
// details.
 
12
//
 
13
// You should have received a copy of the GNU General Public License along with
 
14
// this program; if not, see <http://www.gnu.org/licenses/>.
 
15
 
 
16
#include <octave/oct.h>
 
17
#include "randmtzig.h"
 
18
 
 
19
/* 
 
20
 
 
21
IntSetBins2 class and its usage from 'Programming Pearls' 
 
22
by Jon Bentley, 2nd edition, available at 
 
23
http://netlib.bell-labs.com/cm/cs/pearls/sets.cpp.
 
24
 
 
25
The notice on http://netlib.bell-labs.com/cm/cs/pearls/code.html says
 
26
  "You may use this code for any purpose, 
 
27
  as long as you leave the copyright notice and book citation attached." 
 
28
 
 
29
*/ 
 
30
 
 
31
/* IntSetBins2 class Copyright (C) 1999 Lucent Technologies */
 
32
/* From 'Programming Pearls', 2nd edition, by Jon Bentley */
 
33
/* sets.cpp -- exercise set implementations on random numbers */
 
34
 
 
35
#include <set>
 
36
 
 
37
class IntSetBins2 {
 
38
private:
 
39
        unsigned int    n, bins;
 
40
        double maxval;
 
41
        struct node {
 
42
                double val;
 
43
                node *next;
 
44
        };
 
45
        node **bin, *sentinel, *freenode;
 
46
        node *rinsert(node *p, double t)
 
47
        {       if (p->val < t) {
 
48
                        p->next = rinsert(p->next, t);
 
49
                } else if (p->val > t) {
 
50
                        freenode->val = t;
 
51
                        freenode->next = p;
 
52
                        p = freenode++;
 
53
                        n++;
 
54
                }
 
55
                return p;
 
56
        }
 
57
public:
 
58
        IntSetBins2(unsigned int maxelements, double pmaxval)
 
59
        {       bins = maxelements;
 
60
                maxval = pmaxval;
 
61
                freenode = new node[maxelements];
 
62
                bin = new node*[bins];
 
63
                sentinel = new node;
 
64
                sentinel->val = maxval;
 
65
                for (unsigned int i = 0; i < bins; i++)
 
66
                        bin[i] = sentinel;
 
67
                n = 0;
 
68
        }
 
69
        unsigned int size() { return n; }
 
70
        void insert1(double t)
 
71
        {       unsigned int i = t / (1.0 + maxval/bins);
 
72
                bin[i] = rinsert(bin[i], t);
 
73
        }
 
74
        void insert(double t)
 
75
        {       node **p;
 
76
                unsigned int i = t / (1.0 + maxval/bins);
 
77
                for (p = &bin[i]; (*p)->val < t; p = &((*p)->next))
 
78
                        ;
 
79
                if ((*p)->val == t)
 
80
                        return;
 
81
                freenode->val = t;
 
82
                freenode->next = *p;
 
83
                *p = freenode++;
 
84
                n++;
 
85
        }
 
86
        void report(double *v)
 
87
        {       unsigned int j = 0;
 
88
                for (unsigned int i = 0; i < bins; i++)
 
89
                        for (node *p = bin[i]; p != sentinel; p = p->next)
 
90
                                v[j++] = p->val;
 
91
        }
 
92
};
 
93
 
 
94
 
 
95
DEFUN_DLD (sample, args, , "-*- texinfo -*-\n\
 
96
@deftypefn {Loadable Function} {@var{s}} = sample (@var{m}, @var{n})\n\
 
97
Return @var{m} unique random integer values from 0..@var{n}-1,\n\
 
98
sorted in ascending order.\n\
 
99
\n\
 
100
Based on a code from Jon Bentley's \"Programming Pearls\", \n\
 
101
see @url{http://netlib.bell-labs.com/cm/cs/pearls/}.\n\
 
102
@end deftypefn")
 
103
{
 
104
        int nargin = args.length();
 
105
        if (nargin < 2)
 
106
        {
 
107
                print_usage ();
 
108
                return octave_value ();
 
109
        }
 
110
        
 
111
        unsigned int m;
 
112
        double M = args(0).scalar_value();      // temporarily allow for 
 
113
                                                // negative values of "m"
 
114
        double n = args(1).scalar_value();      // allow huge values of "n"
 
115
        if (M > n) 
 
116
                M = n;
 
117
        if (M <= 0)
 
118
                M = 0;
 
119
                
 
120
        m = M; // set actual "m" only after making sure it is not negative
 
121
        RowVector s(m);
 
122
        
 
123
        /* as in the code from "Programming Pearls" */
 
124
        IntSetBins2 S(m, n);
 
125
        while (S.size() < m)
 
126
                S.insert(floor(oct_randu()*n)); // use Octave's uniform RNG
 
127
        S.report(s.fortran_vec());
 
128
        return octave_value (s);
 
129
}
 
130
/*
 
131
%!assert (isempty(sample(0,10)));
 
132
%!assert (isempty(sample(-2,10)));
 
133
%!assert (sample(10,10),[0:9]);
 
134
%!assert (sample(12,10),[0:9]);
 
135
%!assert (length(sample(9,10)),9);
 
136
%!shared a,m,n
 
137
%! m = 1e4-5;
 
138
%! n = 1e4;
 
139
%! a = sample(m,n);
 
140
%!assert (all(a<n));
 
141
%!assert (all(a>=0));
 
142
%!assert (length(a),m);
 
143
%! n = 1e300;
 
144
%! a = sample(m,n);
 
145
%!assert (all(a<n));
 
146
%!assert (all(a>=0));
 
147
%!assert (length(a),m);
 
148
%!demo
 
149
%! s = sample(4,8)
 
150
%! % s should contain an increasing sequence of 4 integers from the range 0..7
 
151
*/