1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    * 
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   * 
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math.random;
18  
19  import junit.framework.Test;
20  import junit.framework.TestSuite;
21  import java.util.HashSet;
22  
23  import org.apache.commons.math.RetryTestCase;
24  import org.apache.commons.math.stat.Frequency;
25  import org.apache.commons.math.stat.inference.ChiSquareTestImpl;
26  import org.apache.commons.math.stat.descriptive.SummaryStatistics;
27  
28  /**
29   * Test cases for the RandomData class.
30   * 
31   * @version $Revision: 783041 $ $Date: 2009-04-05 11:55:59 -0500 (Sun, 05 Apr
32   *          2009) $
33   */
34  
35  public class RandomDataTest extends RetryTestCase {
36  
37  	public RandomDataTest(String name) {
38  		super(name);
39  		randomData = new RandomDataImpl();
40  	}
41  
42  	protected long smallSampleSize = 1000;
43  	protected double[] expected = { 250, 250, 250, 250 };
44  	protected int largeSampleSize = 10000;
45  	private String[] hex = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
46  			"a", "b", "c", "d", "e", "f" };
47  	protected RandomDataImpl randomData = null;
48  	protected ChiSquareTestImpl testStatistic = new ChiSquareTestImpl();
49  
50  	public static Test suite() {
51  		TestSuite suite = new TestSuite(RandomDataTest.class);
52  		suite.setName("RandomData Tests");
53  		return suite;
54  	}
55  
56  	public void testNextIntExtremeValues() {
57  		int x = randomData.nextInt(Integer.MIN_VALUE, Integer.MAX_VALUE);
58  		int y = randomData.nextInt(Integer.MIN_VALUE, Integer.MAX_VALUE);
59  		assertFalse(x == y);
60  	}
61  
62  	public void testNextLongExtremeValues() {
63  		long x = randomData.nextLong(Long.MIN_VALUE, Long.MAX_VALUE);
64  		long y = randomData.nextLong(Long.MIN_VALUE, Long.MAX_VALUE);
65  		assertFalse(x == y);
66  	}
67  
68  	/** test dispersion and failure modes for nextInt() */
69  	public void testNextInt() {
70  		try {
71  			randomData.nextInt(4, 3);
72  			fail("IllegalArgumentException expected");
73  		} catch (IllegalArgumentException ex) {
74  			// ignored
75  		}
76  		Frequency freq = new Frequency();
77  		int value = 0;
78  		for (int i = 0; i < smallSampleSize; i++) {
79  			value = randomData.nextInt(0, 3);
80  			assertTrue("nextInt range", (value >= 0) && (value <= 3));
81  			freq.addValue(value);
82  		}
83  		long[] observed = new long[4];
84  		for (int i = 0; i < 4; i++) {
85  			observed[i] = freq.getCount(i);
86  		}
87  
88  		/*
89  		 * Use ChiSquare dist with df = 4-1 = 3, alpha = .001 Change to 11.34
90  		 * for alpha = .01
91  		 */
92  		assertTrue("chi-square test -- will fail about 1 in 1000 times",
93  				testStatistic.chiSquare(expected, observed) < 16.27);
94  	}
95  
96  	/** test dispersion and failure modes for nextLong() */
97  	public void testNextLong() {
98  		try {
99  			randomData.nextLong(4, 3);
100 			fail("IllegalArgumentException expected");
101 		} catch (IllegalArgumentException ex) {
102 			// ignored
103 		}
104 		Frequency freq = new Frequency();
105 		long value = 0;
106 		for (int i = 0; i < smallSampleSize; i++) {
107 			value = randomData.nextLong(0, 3);
108 			assertTrue("nextInt range", (value >= 0) && (value <= 3));
109 			freq.addValue(value);
110 		}
111 		long[] observed = new long[4];
112 		for (int i = 0; i < 4; i++) {
113 			observed[i] = freq.getCount(i);
114 		}
115 
116 		/*
117 		 * Use ChiSquare dist with df = 4-1 = 3, alpha = .001 Change to 11.34
118 		 * for alpha = .01
119 		 */
120 		assertTrue("chi-square test -- will fail about 1 in 1000 times",
121 				testStatistic.chiSquare(expected, observed) < 16.27);
122 	}
123 
124 	/** test dispersion and failure modes for nextSecureLong() */
125 	public void testNextSecureLong() {
126 		try {
127 			randomData.nextSecureLong(4, 3);
128 			fail("IllegalArgumentException expected");
129 		} catch (IllegalArgumentException ex) {
130 			// ignored
131 		}
132 		Frequency freq = new Frequency();
133 		long value = 0;
134 		for (int i = 0; i < smallSampleSize; i++) {
135 			value = randomData.nextSecureLong(0, 3);
136 			assertTrue("nextInt range", (value >= 0) && (value <= 3));
137 			freq.addValue(value);
138 		}
139 		long[] observed = new long[4];
140 		for (int i = 0; i < 4; i++) {
141 			observed[i] = freq.getCount(i);
142 		}
143 
144 		/*
145 		 * Use ChiSquare dist with df = 4-1 = 3, alpha = .001 Change to 11.34
146 		 * for alpha = .01
147 		 */
148 		assertTrue("chi-square test -- will fail about 1 in 1000 times",
149 				testStatistic.chiSquare(expected, observed) < 16.27);
150 	}
151 
152 	/** test dispersion and failure modes for nextSecureInt() */
153 	public void testNextSecureInt() {
154 		try {
155 			randomData.nextSecureInt(4, 3);
156 			fail("IllegalArgumentException expected");
157 		} catch (IllegalArgumentException ex) {
158 			// ignored
159 		}
160 		Frequency freq = new Frequency();
161 		int value = 0;
162 		for (int i = 0; i < smallSampleSize; i++) {
163 			value = randomData.nextSecureInt(0, 3);
164 			assertTrue("nextInt range", (value >= 0) && (value <= 3));
165 			freq.addValue(value);
166 		}
167 		long[] observed = new long[4];
168 		for (int i = 0; i < 4; i++) {
169 			observed[i] = freq.getCount(i);
170 		}
171 
172 		/*
173 		 * Use ChiSquare dist with df = 4-1 = 3, alpha = .001 Change to 11.34
174 		 * for alpha = .01
175 		 */
176 		assertTrue("chi-square test -- will fail about 1 in 1000 times",
177 				testStatistic.chiSquare(expected, observed) < 16.27);
178 	}
179 
180 	/**
181 	 * Make sure that empirical distribution of random Poisson(4)'s has P(X <=
182 	 * 5) close to actual cumulative Poisson probablity and that nextPoisson
183 	 * fails when mean is non-positive TODO: replace with statistical test,
184 	 * adding test stat to TestStatistic
185 	 */
186 	public void testNextPoisson() {
187 		try {
188 			randomData.nextPoisson(0);
189 			fail("zero mean -- expecting IllegalArgumentException");
190 		} catch (IllegalArgumentException ex) {
191 			// ignored
192 		}
193 		Frequency f = new Frequency();
194 		for (int i = 0; i < largeSampleSize; i++) {
195 			try {
196 				f.addValue(randomData.nextPoisson(4.0d));
197 			} catch (Exception ex) {
198 				fail(ex.getMessage());
199 			}
200 		}
201 		long cumFreq = f.getCount(0) + f.getCount(1) + f.getCount(2)
202 				+ f.getCount(3) + f.getCount(4) + f.getCount(5);
203 		long sumFreq = f.getSumFreq();
204 		double cumPct = Double.valueOf(cumFreq).doubleValue()
205 				/ Double.valueOf(sumFreq).doubleValue();
206 		assertEquals("cum Poisson(4)", cumPct, 0.7851, 0.2);
207 		try {
208 			randomData.nextPoisson(-1);
209 			fail("negative mean supplied -- IllegalArgumentException expected");
210 		} catch (IllegalArgumentException ex) {
211 			// ignored
212 		}
213 		try {
214 			randomData.nextPoisson(0);
215 			fail("0 mean supplied -- IllegalArgumentException expected");
216 		} catch (IllegalArgumentException ex) {
217 			// ignored
218 		}
219 
220 	}
221 
222 	public void testNextPoissonLargeMean() {
223 		for (int i = 0; i < 1000; i++) {
224 			long n = randomData.nextPoisson(1500.0);
225 			assertTrue(0 <= n);
226 		}
227 	}
228 
229 	/** test dispersion and failute modes for nextHex() */
230 	public void testNextHex() {
231 		try {
232 			randomData.nextHexString(-1);
233 			fail("negative length supplied -- IllegalArgumentException expected");
234 		} catch (IllegalArgumentException ex) {
235 			// ignored
236 		}
237 		try {
238 			randomData.nextHexString(0);
239 			fail("zero length supplied -- IllegalArgumentException expected");
240 		} catch (IllegalArgumentException ex) {
241 			// ignored
242 		}
243 		String hexString = randomData.nextHexString(3);
244 		if (hexString.length() != 3) {
245 			fail("incorrect length for generated string");
246 		}
247 		hexString = randomData.nextHexString(1);
248 		if (hexString.length() != 1) {
249 			fail("incorrect length for generated string");
250 		}
251 		try {
252 			hexString = randomData.nextHexString(0);
253 			fail("zero length requested -- expecting IllegalArgumentException");
254 		} catch (IllegalArgumentException ex) {
255 			// ignored
256 		}
257 		if (hexString.length() != 1) {
258 			fail("incorrect length for generated string");
259 		}
260 		Frequency f = new Frequency();
261 		for (int i = 0; i < smallSampleSize; i++) {
262 			hexString = randomData.nextHexString(100);
263 			if (hexString.length() != 100) {
264 				fail("incorrect length for generated string");
265 			}
266 			for (int j = 0; j < hexString.length(); j++) {
267 				f.addValue(hexString.substring(j, j + 1));
268 			}
269 		}
270 		double[] expected = new double[16];
271 		long[] observed = new long[16];
272 		for (int i = 0; i < 16; i++) {
273 			expected[i] = (double) smallSampleSize * 100 / 16;
274 			observed[i] = f.getCount(hex[i]);
275 		}
276 		/*
277 		 * Use ChiSquare dist with df = 16-1 = 15, alpha = .001 Change to 30.58
278 		 * for alpha = .01
279 		 */
280 		assertTrue("chi-square test -- will fail about 1 in 1000 times",
281 				testStatistic.chiSquare(expected, observed) < 37.70);
282 	}
283 
284 	/** test dispersion and failute modes for nextHex() */
285 	public void testNextSecureHex() {
286 		try {
287 			randomData.nextSecureHexString(-1);
288 			fail("negative length -- IllegalArgumentException expected");
289 		} catch (IllegalArgumentException ex) {
290 			// ignored
291 		}
292 		try {
293 			randomData.nextSecureHexString(0);
294 			fail("zero length -- IllegalArgumentException expected");
295 		} catch (IllegalArgumentException ex) {
296 			// ignored
297 		}
298 		String hexString = randomData.nextSecureHexString(3);
299 		if (hexString.length() != 3) {
300 			fail("incorrect length for generated string");
301 		}
302 		hexString = randomData.nextSecureHexString(1);
303 		if (hexString.length() != 1) {
304 			fail("incorrect length for generated string");
305 		}
306 		try {
307 			hexString = randomData.nextSecureHexString(0);
308 			fail("zero length requested -- expecting IllegalArgumentException");
309 		} catch (IllegalArgumentException ex) {
310 			// ignored
311 		}
312 		if (hexString.length() != 1) {
313 			fail("incorrect length for generated string");
314 		}
315 		Frequency f = new Frequency();
316 		for (int i = 0; i < smallSampleSize; i++) {
317 			hexString = randomData.nextSecureHexString(100);
318 			if (hexString.length() != 100) {
319 				fail("incorrect length for generated string");
320 			}
321 			for (int j = 0; j < hexString.length(); j++) {
322 				f.addValue(hexString.substring(j, j + 1));
323 			}
324 		}
325 		double[] expected = new double[16];
326 		long[] observed = new long[16];
327 		for (int i = 0; i < 16; i++) {
328 			expected[i] = (double) smallSampleSize * 100 / 16;
329 			observed[i] = f.getCount(hex[i]);
330 		}
331 		/*
332 		 * Use ChiSquare dist with df = 16-1 = 15, alpha = .001 Change to 30.58
333 		 * for alpha = .01
334 		 */
335 		assertTrue("chi-square test -- will fail about 1 in 1000 times",
336 				testStatistic.chiSquare(expected, observed) < 37.70);
337 	}
338 
339 	/** test failure modes and dispersion of nextUniform() */
340 	public void testNextUniform() {
341 		try {
342 			randomData.nextUniform(4, 3);
343 			fail("IllegalArgumentException expected");
344 		} catch (IllegalArgumentException ex) {
345 			// ignored
346 		}
347 		try {
348 			randomData.nextUniform(3, 3);
349 			fail("IllegalArgumentException expected");
350 		} catch (IllegalArgumentException ex) {
351 			// ignored
352 		}
353 		double[] expected = { 500, 500 };
354 		long[] observed = { 0, 0 };
355 		double lower = -1d;
356 		double upper = 20d;
357 		double midpoint = (lower + upper) / 2d;
358 		double result = 0;
359 		for (int i = 0; i < 1000; i++) {
360 			result = randomData.nextUniform(lower, upper);
361 			if ((result == lower) || (result == upper)) {
362 				fail("generated value equal to an endpoint: " + result);
363 			}
364 			if (result < midpoint) {
365 				observed[0]++;
366 			} else {
367 				observed[1]++;
368 			}
369 		}
370 		/*
371 		 * Use ChiSquare dist with df = 2-1 = 1, alpha = .001 Change to 6.64 for
372 		 * alpha = .01
373 		 */
374 		assertTrue("chi-square test -- will fail about 1 in 1000 times",
375 				testStatistic.chiSquare(expected, observed) < 10.83);
376 	}
377 
378 	/** test exclusive endpoints of nextUniform **/
379 	public void testNextUniformExclusiveEndpoints() {
380 		for (int i = 0; i < 1000; i++) {
381 			double u = randomData.nextUniform(0.99, 1);
382 			assertTrue(u > 0.99 && u < 1);
383 		}
384 	}
385 
386 	/** test failure modes and distribution of nextGaussian() */
387 	public void testNextGaussian() {
388 		try {
389 			randomData.nextGaussian(0, 0);
390 			fail("zero sigma -- IllegalArgumentException expected");
391 		} catch (IllegalArgumentException ex) {
392 			// ignored
393 		}
394 		SummaryStatistics u = new SummaryStatistics();
395 		for (int i = 0; i < largeSampleSize; i++) {
396 			u.addValue(randomData.nextGaussian(0, 1));
397 		}
398 		double xbar = u.getMean();
399 		double s = u.getStandardDeviation();
400 		double n = u.getN();
401 		/*
402 		 * t-test at .001-level TODO: replace with externalized t-test, with
403 		 * test statistic defined in TestStatistic
404 		 */
405 		assertTrue(Math.abs(xbar) / (s / Math.sqrt(n)) < 3.29);
406 	}
407 
408 	/** test failure modes and distribution of nextExponential() */
409 	public void testNextExponential() {
410 		try {
411 			randomData.nextExponential(-1);
412 			fail("negative mean -- expecting IllegalArgumentException");
413 		} catch (IllegalArgumentException ex) {
414 			// ignored
415 		}
416 		assertEquals("0 mean", 0, randomData.nextExponential(0), 10E-8);
417 		long cumFreq = 0;
418 		double v = 0;
419 		for (int i = 0; i < largeSampleSize; i++) {
420 			v = randomData.nextExponential(1);
421 			assertTrue("exponential deviate postive", v > 0);
422 			if (v < 2)
423 				cumFreq++;
424 		}
425 		/*
426 		 * TODO: Replace with a statistical test, with statistic added to
427 		 * TestStatistic. Check below compares observed cumulative distribution
428 		 * evaluated at 2 with exponential CDF
429 		 */
430 		assertEquals("exponential cumulative distribution", (double) cumFreq
431 				/ (double) largeSampleSize, 0.8646647167633873, .2);
432 	}
433 
434 	/** test reseeding, algorithm/provider games */
435 	public void testConfig() {
436 		randomData.reSeed(1000);
437 		double v = randomData.nextUniform(0, 1);
438 		randomData.reSeed();
439 		assertTrue("different seeds", Math
440 				.abs(v - randomData.nextUniform(0, 1)) > 10E-12);
441 		randomData.reSeed(1000);
442 		assertEquals("same seeds", v, randomData.nextUniform(0, 1), 10E-12);
443 		randomData.reSeedSecure(1000);
444 		String hex = randomData.nextSecureHexString(40);
445 		randomData.reSeedSecure();
446 		assertTrue("different seeds", !hex.equals(randomData
447 				.nextSecureHexString(40)));
448 		randomData.reSeedSecure(1000);
449 		assertTrue("same seeds", !hex
450 				.equals(randomData.nextSecureHexString(40)));
451 
452 		/*
453 		 * remove this test back soon, since it takes about 4 seconds
454 		 * 
455 		 * try { randomData.setSecureAlgorithm("SHA1PRNG","SUN"); } catch
456 		 * (NoSuchProviderException ex) { ; } assertTrue("different seeds",
457 		 * !hex.equals(randomData.nextSecureHexString(40))); try {
458 		 * randomData.setSecureAlgorithm("NOSUCHTHING","SUN");
459 		 * fail("expecting NoSuchAlgorithmException"); } catch
460 		 * (NoSuchProviderException ex) { ; } catch (NoSuchAlgorithmException
461 		 * ex) { ; }
462 		 * 
463 		 * try { randomData.setSecureAlgorithm("SHA1PRNG","NOSUCHPROVIDER");
464 		 * fail("expecting NoSuchProviderException"); } catch
465 		 * (NoSuchProviderException ex) { ; }
466 		 */
467 
468 		// test reseeding without first using the generators
469 		RandomDataImpl rd = new RandomDataImpl();
470 		rd.reSeed(100);
471 		rd.nextLong(1, 2);
472 		RandomDataImpl rd2 = new RandomDataImpl();
473 		rd2.reSeedSecure(2000);
474 		rd2.nextSecureLong(1, 2);
475 		rd = new RandomDataImpl();
476 		rd.reSeed();
477 		rd.nextLong(1, 2);
478 		rd2 = new RandomDataImpl();
479 		rd2.reSeedSecure();
480 		rd2.nextSecureLong(1, 2);
481 	}
482 
483 	/** tests for nextSample() sampling from Collection */
484 	public void testNextSample() {
485 		Object[][] c = { { "0", "1" }, { "0", "2" }, { "0", "3" },
486 				{ "0", "4" }, { "1", "2" }, { "1", "3" }, { "1", "4" },
487 				{ "2", "3" }, { "2", "4" }, { "3", "4" } };
488 		long[] observed = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
489 		double[] expected = { 100, 100, 100, 100, 100, 100, 100, 100, 100, 100 };
490 
491 		HashSet<Object> cPop = new HashSet<Object>(); // {0,1,2,3,4}
492 		for (int i = 0; i < 5; i++) {
493 			cPop.add(Integer.toString(i));
494 		}
495 
496 		Object[] sets = new Object[10]; // 2-sets from 5
497 		for (int i = 0; i < 10; i++) {
498 			HashSet<Object> hs = new HashSet<Object>();
499 			hs.add(c[i][0]);
500 			hs.add(c[i][1]);
501 			sets[i] = hs;
502 		}
503 
504 		for (int i = 0; i < 1000; i++) {
505 			Object[] cSamp = randomData.nextSample(cPop, 2);
506 			observed[findSample(sets, cSamp)]++;
507 		}
508 
509 		/*
510 		 * Use ChiSquare dist with df = 10-1 = 9, alpha = .001 Change to 21.67
511 		 * for alpha = .01
512 		 */
513 		assertTrue("chi-square test -- will fail about 1 in 1000 times",
514 				testStatistic.chiSquare(expected, observed) < 27.88);
515 
516 		// Make sure sample of size = size of collection returns same collection
517 		HashSet<Object> hs = new HashSet<Object>();
518 		hs.add("one");
519 		Object[] one = randomData.nextSample(hs, 1);
520 		String oneString = (String) one[0];
521 		if ((one.length != 1) || !oneString.equals("one")) {
522 			fail("bad sample for set size = 1, sample size = 1");
523 		}
524 
525 		// Make sure we fail for sample size > collection size
526 		try {
527 			one = randomData.nextSample(hs, 2);
528 			fail("sample size > set size, expecting IllegalArgumentException");
529 		} catch (IllegalArgumentException ex) {
530 			// ignored
531 		}
532 
533 		// Make sure we fail for empty collection
534 		try {
535 			hs = new HashSet<Object>();
536 			one = randomData.nextSample(hs, 0);
537 			fail("n = k = 0, expecting IllegalArgumentException");
538 		} catch (IllegalArgumentException ex) {
539 			// ignored
540 		}
541 	}
542 
543 	@SuppressWarnings("unchecked")
544 	private int findSample(Object[] u, Object[] samp) {
545 		for (int i = 0; i < u.length; i++) {
546 			HashSet<Object> set = (HashSet<Object>) u[i];
547 			HashSet<Object> sampSet = new HashSet<Object>();
548 			for (int j = 0; j < samp.length; j++) {
549 				sampSet.add(samp[j]);
550 			}
551 			if (set.equals(sampSet)) {
552 				return i;
553 			}
554 		}
555 		fail("sample not found:{" + samp[0] + "," + samp[1] + "}");
556 		return -1;
557 	}
558 
559 	/** tests for nextPermutation */
560 	public void testNextPermutation() {
561 		int[][] p = { { 0, 1, 2 }, { 0, 2, 1 }, { 1, 0, 2 }, { 1, 2, 0 },
562 				{ 2, 0, 1 }, { 2, 1, 0 } };
563 		long[] observed = { 0, 0, 0, 0, 0, 0 };
564 		double[] expected = { 100, 100, 100, 100, 100, 100 };
565 
566 		for (int i = 0; i < 600; i++) {
567 			int[] perm = randomData.nextPermutation(3, 3);
568 			observed[findPerm(p, perm)]++;
569 		}
570 
571 		/*
572 		 * Use ChiSquare dist with df = 6-1 = 5, alpha = .001 Change to 15.09
573 		 * for alpha = .01
574 		 */
575 		assertTrue("chi-square test -- will fail about 1 in 1000 times",
576 				testStatistic.chiSquare(expected, observed) < 20.52);
577 
578 		// Check size = 1 boundary case
579 		int[] perm = randomData.nextPermutation(1, 1);
580 		if ((perm.length != 1) || (perm[0] != 0)) {
581 			fail("bad permutation for n = 1, sample k = 1");
582 
583 			// Make sure we fail for k size > n
584 			try {
585 				perm = randomData.nextPermutation(2, 3);
586 				fail("permutation k > n, expecting IllegalArgumentException");
587 			} catch (IllegalArgumentException ex) {
588 				// ignored
589 			}
590 
591 			// Make sure we fail for n = 0
592 			try {
593 				perm = randomData.nextPermutation(0, 0);
594 				fail("permutation k = n = 0, expecting IllegalArgumentException");
595 			} catch (IllegalArgumentException ex) {
596 				// ignored
597 			}
598 
599 			// Make sure we fail for k < n < 0
600 			try {
601 				perm = randomData.nextPermutation(-1, -3);
602 				fail("permutation k < n < 0, expecting IllegalArgumentException");
603 			} catch (IllegalArgumentException ex) {
604 				// ignored
605 			}
606 
607 		}
608 	}
609 	
610 	// Disable until we have equals
611 	//public void testSerial() {
612 	//    assertEquals(randomData, TestUtils.serializeAndRecover(randomData));
613 	//}
614 	
615 	private int findPerm(int[][] p, int[] samp) {
616 		for (int i = 0; i < p.length; i++) {
617 			boolean good = true;
618 			for (int j = 0; j < samp.length; j++) {
619 				if (samp[j] != p[i][j]) {
620 					good = false;
621 				}
622 			}
623 			if (good) {
624 				return i;
625 			}
626 		}
627 		fail("permutation not found");
628 		return -1;
629 	}
630 }