ADT

At University we were taught that using Abstract Data Types was sensible programming practice. So when upon starting work in Java I made the ADT package and began filling it up with useful types and algorithms.

Queue

ADT.Queue is an implementation of the classic queue data structure containing a sequence of elements. Items can be remove from the front of the queue (dequeue) and added to the back (enqueue). Error conditions are indicated using the exceptions ADT.QueueEmpty and ADT.QueueItemAbsent. Along with standard enqueue and dequeue methods are membership, arbitrary deletion, peeking, and requeueing. Peeking returns the first item in the queue but does not dequeue it. Requeueing is a combination of dequeue and enqueue which avoids creating or deleting objects.

ADT.Ring is a fixed-size queue with only membership, peek, and requeue available. This is useful after initialisation has taken place and their will be no changes to the contents of the queue.

Random

Many of my applets have require a supply of pseudo-random numbers. Rather than use the standard random number generator I prefer a standard generator which can be implemented in other languages.

Random numbers are not normally available inside a computer and instead we have to make do with pseudo-random. By using certain formulae we can generate a sequence of numbers which has no obvious pattern, pseudo-random numbers. We start with a seed value which is modified after each number is taken, one seed value will always give the same sequence of numbers. If we choose a seed value based on the time and date we will not see a pattern in the numbers. If we always choose the same seed value we will generate identical patterns which is advantageous when replicating experiments.

ADT.Random class has two constructors, one which takes an explicit seed, the other looks at the time and date. The seed value can be examined but not modified once an object has been created. Two other methods are available: one supplies random booleans, the other random numbers between 0 and (range - 1).

To get slightly more technical, this is a linear congruential generator which is based on the formula:

Such generators repeats every m turns but this is good enough for most simulation purposes. To get really unpredictable numbers another scheme developed by Blum, Blum, and Shub can be used. For those who are interested the theory behind it is based on quadratic residues but the details are unknown to me.

1. Find two large prime numbers, p and q, such that p mod 4 = q mod 4 = 3
2. Let n = p * q
3. Choose an x so that gcd(x, n) = 1
4. Let x0 = x ^ 2 mod n
5. Let xi = x(i - 1) ^ 2 mod n

The log log n least significant bits of each xi is random.

Binary Space Partition Trees

Binary space partition trees are a way of storing a set of polygons. Originally developed for rendering 3D scenes it is also suitable for collision detection. An explanation of the principles at work are available in this FAQ although it concentrates on rendering.

ADT.BSPT's current implementation of polygon parsing and collision detection is workable but not perfect. Polygon line segments which are on the same extended line create a false line within the collision detection tree. Sharp edges also pose some problem for radius based collision detection. Collisions are detected when an object is considerably beyond the actual edge.

Credits

The technical aspects of random number generation come from a lecture by Ron Poet at the University of Glasgow and the current random number implementation is based on the generator used in C.