Datei: Field.java

1/**

2 * @author Uwe Schmidt

3 *

4 * predicates and functions on arrays of integers

5 *

6 * the startup class

7 *

8 */

10//--------------------

12class Field {

14 public static

15 void main(String[] args) {

17 // a 1. test case

18 {

19 long [] a1 = {};

20 Array f1 = new Array(a1);

22 f1.testCases("f1");

23 }

25 // a 2. test case

26 {

27 long [] a2 = {1};

28 Array f2 = new Array(a2);

30 f2.testCases("f2");

31 }

32 // a 3. test case

33 {

34 long [] a3 = {1, 100, 40, 40, 100, 3};

35 Array f3 = new Array(a3);

37 f3.testCases("f3");

38 }

39 }

40}

42//--------------------

44/**

45 * predicates and functions for arrays of integers

46 *

47 */

49class Array {

51 /*

52 * the field variable f

53 */

55 private

56 long [] f;

58 //--------------------

59 /**

60 * the constructor: initialization of f.

61 */

63 public

64 Array(long [] f) {

65 this.f = f;

66 }

68 //--------------------

69 /**

70 * access element i.

71 */

73 public

74 long at(int i) {

75 return

76 f[i];

77 }

79 //--------------------

80 /**

81 * modification at position i.

82 */

84 public

85 void putAt(int i, long v) {

86 f[i] = v;

87 }

89 //--------------------

90 /**

91 * search function.

92 * Returns true if v is found in field f

93 */

95 public

96 boolean contains(long v) {

97 return

98 contains(v, f.length);

99 }

100

101 //--------------------

102 /**

103 * search function.

104 * returns true if v is found in the first n elements of f

105 * specification:

106 * exists 0 <= i < n : f[i] = v

107 * implemented as linear search loop

108 */

109

110 public

111 boolean contains(long v,

112 int n) {

113 int i = 0;

114

115 while ( i < n && f[i] != v ) {

116 i = i + 1;

117 }

118

119 return

120 i < n;

121 }

122

123 //--------------------

124 /**

125 * all elements equal.

126 */

127

128 public

129 boolean allEqual() {

130 return

131 allEqual(f.length);

132 }

133

134 //--------------------

135 /**

136 * all first n elements equal.

137 * specification:

138 * forall 0 < i < n : f[i-1] = f[i]

139 */

140

141 public

142 boolean allEqual(int n) {

143 int i = 1;

144 boolean equal = true;

145

146 while ( equal && i < n ) {

147 equal = f[i-1] == f[i];

148 i = i + 1;

149 }

150

151 return

152 equal;

153 }

154

155 //--------------------

156 /**

157 * all elements less than or equal to a value.

158 */

159

160 public

161 boolean allLessThanOrEqualTo(long m) {

162 return

163 allLessThanOrEqualTo(m, f.length);

164 }

165

166 //--------------------

167 /**

168 * all first n elements less than or equal to a value.

169 * specification:

170 * forall 0 <= i < n : f[i] <= m

171 * implemented as linear search:

172 * not (exists 0 <= i < n : f[i] > m)

173 */

174

175 public

176 boolean allLessThanOrEqualTo(long m,

177 int n) {

178 int i = 0;

179

180 while ( i < n && f[i] <= m) {

181 i = i + 1;

182 }

183

184 return

185 i == n;

186 }

187

188

189 //--------------------

190 /**

191 * all elements except one special value

192 * less than or equal to a given value.

193 */

194

195 public

196 boolean allExceptOneLessThanOrEqualTo(long m2,

197 long m) {

198 return

199 allExceptOneLessThanOrEqualTo(m2,m,f.length);

200 }

201

202 //--------------------

203 /**

204 * all first n elements except one special value

205 * less than or equal to a given value.

206 * specification:

207 * forall 0 <= i < n : f[i] != m => f[i] <= m2

208 */

209

210 public boolean allExceptOneLessThanOrEqualTo(long m2,

211 long m,

212 int n) {

213 int i = 0;

214 boolean r = true;

215

216 while ( r && i < n ) {

217 r = (f[i] == m) || (f[i] <= m2);

218 i = i + 1;

219 }

220

221 return r;

222 }

223

224

225 //--------------------

226 /**

227 * greatest element in f.

228 */

229

230 public long max() {

231 return

232 max(f.length);

233 }

234

235 //--------------------

236 /**

237 * greatest of first n elements.

238 * specification:

239 * exist 0 <= i < n : f[i] = max

240 * and

241 * forall 0 <= i < n : f[i] <= max

242 * precondition: checked by array index check

243 * 0 < n

244 */

245

246 public long max(int n) {

247 int i = 1;

248 long m = f[0];

249

250 while ( i < n ) {

251 m = f[i] > m ? f[i] : m;

252 i = i + 1;

253 }

254

255 return m;

256 }

257

258 //--------------------

259 /**

260 * second greatest element in f.

261 */

262

263 public long max2() {

264 return

265 max2(f.length);

266 }

267

268 //--------------------

269 /**

270 * second greatest of first n elements.

271 * specification:

272 * max = f.max(n)

273 * and

274 * f.contains(max2)

275 * and

276 * not f.allEqual(n)

277 * => (forall 0 <= i < n : f[i] != max => f[i] <= max2)

278 *

279 * if more than 1 values are stored in f,

280 * the 2. greatest is returned, else

281 * the value occuring in f is returned

282 * precondition:

283 * interval contains at least 1 element

284 * 0 < n

285 */

286

287 public

288 long max2(int n) {

289 int i = 1;

290 long max = f[0];

291 long max2 = max; // max == max2 --> all elements equal

292

293 while ( i < n ) {

294 // 3 cases: f[i] > max, f[i] < max, f[i] == max

295

296 if ( f[i] > max ) { // 1. case

297 max2 = max;

298 max = f[i];

299 }

300 else

301 if ( f[i] < max ) {

302 // 2. case

303 if ( max == max2 ) {

304 // a 2. value found, it's less than max

305 max2 = f[i];

306 }

307 else {

308 // already 2 values found, test whether new max2 found

309 if ( f[i] > max2 ) {

310 max2 = f[i];

311 }

312 }

313 }

314 else {

315 // 3. case: f[i] == max

316 // nothing changes

317 }

318 i = i + 1;

319 }

320

321 return max2;

322 }

323

324 //--------------------

325 /**

326 * the String conversion routine

327 */

328

329 public

330 String toString() {

331 if (f.length == 0)

332 return

333 "{}";

334 else {

335 String r = "{";

336

337 for (int i = 0;

338 i < f.length;

339 ++i) {

340 r = r + f[i] + (i < f.length -1 ? "," : "}");

341 }

342

343 return r;

344 }

345 }

346

347 //--------------------

348 /**

349 * a few test cases

350 */

351

352 public

353 void testCases(String n) {

354 System.out.println("Array " + n + " = " + toString());

355 System.out.println(n + ".length = " + f.length);

356 System.out.println(n + ".contains(0) = " + contains(0));

357 System.out.println(n + ".contains(1) = " + contains(1));

358 System.out.println(n + ".allEqual() = " + allEqual());

359

360 if (f.length != 0) {

361 System.out.println(n + ".max() = " + max());

362 System.out.println(n + ".max2() = " + max2());

363 System.out.println(n + ".max() == " + n + ".max2() = " +

364 (max() == max2()));

365 System.out.println(n + ".contains(" + f[0] + ") = " + contains(f[0]));

366 System.out.println(n + ".contains(" + max() + ") = " + contains(max()));

367 System.out.println(n + ".contains(" + max2() + ") = " + contains(max2()));

368 System.out.println(n + ".allLessThanOrEqualTo(" + f[0] + ") = " +

369 allLessThanOrEqualTo(f[0]));

370 System.out.println(n + ".allLessThanOrEqualTo(" + max() + ") = " +

371 allLessThanOrEqualTo(max()));

372 System.out.println(n + ".allLessThanOrEqualTo(" + max2() + ") = " +

373 allLessThanOrEqualTo(max2()));

374 System.out.println(n + ".allExceptOneLessThanOrEqualTo(" + max2() + "," + max() + ") = " +

375 allExceptOneLessThanOrEqualTo(max2(),max()));

376 System.out.println(n + ".allExceptOneLessThanOrEqualTo(" + max() + "," + max2() + ") = " +

377 allExceptOneLessThanOrEqualTo(max(),max2()));

378 }

379 System.out.println("");

380 }

381

382}

383

384//--------------------

Die Datei: Field.java