001: /*
002: * Created on 26-Sep-2003
003: */
004: package uk.org.ponder.intutil;
005:
006: import java.util.Arrays;
007: import java.util.Random;
008:
009: import uk.org.ponder.arrayutil.ArrayUtil;
010:
011: /**
012: * @author Bosmon
013: *
014: * The class Algorithms incorporates several useful algorithms culled from the STL.
015: */
016: public class Algorithms {
017:
018: // QQQQQ crappy n^2 implementation until can think of some way to run
019: // an intpair sort in Java.
020: public static int[] invert_permutation(int[] indices, int maximum) {
021: int[] togo = new int[maximum];
022: for (int i = 0; i < maximum; ++i) {
023: togo[i] = ArrayUtil.indexOf(indices, i);
024: }
025: return togo;
026: }
027:
028: public static void random_shuffle(intVector toshuf, int first,
029: int last, Random random) {
030: for (int i = first + 1; i < last; ++i) {
031: int swapind = first + random.nextInt(1 + i - first);
032: int temp = toshuf.intAt(i);
033: toshuf.setIntAt(i, toshuf.intAt(swapind));
034: toshuf.setIntAt(swapind, temp);
035: }
036: }
037:
038: public static void random_shuffle(int[] toshuf, Random random) {
039: for (int i = 1; i < toshuf.length; ++i) {
040: int swapind = random.nextInt(1 + i);
041: int temp = toshuf[i];
042: toshuf[i] = toshuf[swapind];
043: toshuf[swapind] = temp;
044: }
045: }
046:
047: public static int[] ensure_size(int[] array, int newsize) {
048: if (array != null && array.length >= newsize) {
049: return array;
050: } else
051: return new int[newsize * 3 / 2];
052: }
053:
054: public static boolean[] ensure_size(boolean[] array, int newsize) {
055: if (array != null && array.length >= newsize) {
056: return array;
057: } else
058: return new boolean[newsize * 3 / 2];
059: }
060:
061: public static int[] random_sample(int choose, int from,
062: Random random) {
063: int[] bits = new int[from];
064: for (int i = 0; i < choose; ++i) {
065: bits[i] = 1;
066: }
067: random_shuffle(bits, random);
068: int[] togo = new int[choose];
069: int index = 0;
070: for (int i = 0; i < from; ++i) {
071: if (bits[i] == 1)
072: togo[index++] = i;
073: }
074: return togo;
075: }
076:
077: public static boolean equals(int[] array1, int[] array2) {
078: if (array1.length != array2.length)
079: return false;
080: for (int i = 0; i < array1.length; ++i) {
081: if (array1[i] != array2[i])
082: return false;
083: }
084: return true;
085: }
086:
087: // I do not write this in the C style for "purely philosophical reasons"
088: public static int lexicalCompare(int[] array1, int length1,
089: int[] array2, int length2) {
090: int i = 0;
091: while (true) {
092: if (i >= length1) {
093: // off the end of 1 means that 1 is possibly shorter
094: if (length1 == length2)
095: return 0;
096: else
097: return -1;
098: }
099: if (i >= length2)
100: return 1;
101: int a1 = array1[i];
102: int a2 = array2[i];
103: if (a1 < a2)
104: return -1;
105: else if (a1 > a2)
106: return 1;
107: ++i;
108: }
109: }
110:
111: public static int[] makeIota(int size, int start) {
112: int[] togo = new int[size];
113: for (int i = 0; i < size; ++i) {
114: togo[i] = start + i;
115: }
116: return togo;
117: }
118:
119: /**
120: * @param size
121: * @param val
122: * @return
123: */
124: public static int[] fill(int size, int val) {
125: int[] togo = new int[size];
126: for (int i = 0; i < size; ++i) {
127: togo[i] = val;
128: }
129: return togo;
130: }
131:
132: public static int[] fill(int[] target, int size, int val) {
133: for (int i = 0; i < size; ++i) {
134: target[i] = val;
135: }
136: return target;
137: }
138:
139: public static int[] copy(int[] tocopy) {
140: int[] togo = new int[tocopy.length];
141: System.arraycopy(tocopy, 0, togo, 0, tocopy.length);
142: return togo;
143: }
144:
145: /** Count the number of set bits in the argument, by the accepted method */
146: public static int count_bits(int tocount) {
147: int n = 0;
148: for (; tocount != 0; n++) {
149: tocount &= tocount - 1;
150: }
151: return n;
152: }
153:
154: /*
155: public static void reverse(intIterator first, intIterator last) {
156: while (true)
157: if (first == last || first == last.prev())
158: return;
159: else {
160: int temp = first.getInt();
161: first.setInt(last.getInt());
162: iter_swap(__first++, __last);
163: first.next();
164: }
165: }
166:
167: template <class _BidirectionalIter, class _Distance>
168: _BidirectionalIter __rotate(_BidirectionalIter __first,
169: _BidirectionalIter __middle,
170: _BidirectionalIter __last,
171: _Distance*,
172: const bidirectional_iterator_tag &) {
173: if (__first == __middle)
174: return __last;
175: if (__last == __middle)
176: return __first;
177:
178: __reverse(__first, __middle, bidirectional_iterator_tag());
179: __reverse(__middle, __last, bidirectional_iterator_tag());
180:
181: while (__first != __middle && __middle != __last)
182: swap (*__first++, *--__last);
183:
184: if (__first == __middle) {
185: __reverse(__middle, __last, bidirectional_iterator_tag());
186: return __last;
187: }
188: else {
189: __reverse(__first, __middle, bidirectional_iterator_tag());
190: return __first;
191: }
192: }
193: */
194:
195: }
|