Method: deepCopy()

1: package de.fhdw.gaming.ipspiel23.c4.domain.impl;
2:
3: import java.util.HashMap;
4: import java.util.HashSet;
5: import java.util.Map;
6: import java.util.Optional;
7: import java.util.Set;
8:
9: import de.fhdw.gaming.ipspiel23.c4.domain.C4PositionMaterializer;
10: import de.fhdw.gaming.ipspiel23.c4.domain.IC4Board;
11: import de.fhdw.gaming.ipspiel23.c4.domain.IC4Position;
12: import de.fhdw.gaming.ipspiel23.c4.domain.IC4BoardSlim;
13: import de.fhdw.gaming.ipspiel23.c4.domain.IC4Field;
14: import de.fhdw.gaming.ipspiel23.c4.domain.IC4Player;
15: import de.fhdw.gaming.ipspiel23.c4.domain.IC4Solution;
16: import de.fhdw.gaming.ipspiel23.c4.domain.IC4SolutionSlim;
17:
18: /**
19: * The default implementation of {@link IC4Board}.
20: */
21: public class C4Board implements IC4Board {
22:
23: /**
24: * The maximum number of fields that are allowed to be cached.
25: * For performance reasons, the field cache is limited to a certain size.
26: * At some point, it becomes more expensive to cache the fields than to create them on the fly.
27: * @hidden the value 2^16 was chosen arbitrarily, but should be fine for most use cases :)
28: * We just want to avoid that the field cache grows indefinitely, consuming more and more memory.
29: * that will never be freed again due to the strong references to the fields.
30: */
31: private static final int FIELD_CACHE_LIMIT = 1 << 16;
32:
33: /**
34: * A lazily populated cache for the field instances of this board.
35: */
36: private final Map<IC4Position, IC4Field> fieldCache;
37:
38: /**
39: * The internal slim board that is used to store the actual board state.
40: */
41: private final IC4BoardSlim slimBoard;
42:
43: /**
44: * A thread local buffer that is used to receive the dematerialized positions from the slim board.
45: */
46: private final ThreadLocal<long[]> localPositionBuffer;
47:
48: /**
49: * Creates a new instance of {@link C4Board}.
50: *
51: * @param slimBoard The internal slim board that is used to store the actual board state.
52: */
53: public C4Board(final IC4BoardSlim slimBoard) {
54: this.slimBoard = slimBoard;
55: this.fieldCache = new HashMap<>(slimBoard.getBoardStateUnsafe().length);
56: this.localPositionBuffer = ThreadLocal.withInitial(() ->
57: new long[this.slimBoard.getBoardStateUnsafe().length]);
58: }
59:
60: /**
61: * Returns the field instance cache.
62: */
63: public Map<IC4Position, IC4Field> getFieldCache() {
64: return this.fieldCache;
65: }
66:
67: @Override
68: public int getRowCount() {
69: return this.slimBoard.getRowCount();
70: }
71:
72: @Override
73: public int getColumnCount() {
74: return this.slimBoard.getColumnCount();
75: }
76:
77: @Override
78: public int getMinimumSolutionSize() {
79: return this.slimBoard.getMinimumSolutionSize();
80: }
81:
82: @Override
83: public IC4Board deepCopy() {
84: return new C4Board(this.slimBoard.deepCopy());
85: }
86:
87: @Override
88: public IC4BoardSlim getInternalBoard() {
89: return this.slimBoard;
90: }
91:
92: @Override
93: public boolean checkBounds(final IC4Position position) {
94: return this.checkBounds(position.getRow(), position.getColumn());
95: }
96:
97: @Override
98: public boolean checkBounds(final int row, final int column) {
99: return this.slimBoard.checkBounds(row, column);
100: }
101:
102: @Override
103: public boolean isEmpty(final IC4Position position) {
104: return this.isEmpty(position.getRow(), position.getColumn());
105: }
106:
107: @Override
108: public boolean isEmpty(final int row, final int column) {
109: if (!this.checkBounds(row, column)) {
110: throw new IndexOutOfBoundsException("The provided position is not within the defined bounds of the board!");
111: }
112: return this.slimBoard.isEmptyUnsafe(row, column);
113: }
114:
115: @Override
116: public Optional<IC4Field> tryGetField(final IC4Position position) {
117: return Optional.ofNullable(this.getFieldInternal(position, false));
118: }
119:
120: @Override
121: public IC4Field getField(final IC4Position position) {
122: return this.getFieldInternal(position, true);
123: }
124:
125: /**
126: * Retrieves the field from the specified position, either from cache or from the board itself.
127: * @param position the position to retrieve the field from
128: * @param throwOob whether an {@link IndexOutOfBoundsException} should be thrown if the bounds are violated.
129: * @return the field or null if throwOob is false.
130: */
131: private IC4Field getFieldInternal(final IC4Position position, final boolean throwOob) {
132: IC4Field field = this.fieldCache.get(position);
133: if (field != null) {
134: return field;
135: }
136: if (!this.checkBounds(position)) {
137: if (throwOob) {
138: throw new IndexOutOfBoundsException("The provided position violates the bounds of the board!");
139: }
140: return null;
141: }
142: field = new C4Field(this, position);
143: // assume that later fields are more likely to be accessed again
144: // therefore, clear the cache if it is full allowing the new field to be cached
145: if (this.fieldCache.size() >= FIELD_CACHE_LIMIT) {
146: this.fieldCache.clear();
147: }
148: this.fieldCache.put(position, field);
149: return field;
150: }
151:
152: @Override
153: public Optional<IC4Player> getOccupyingPlayerOrDefault(final IC4Position position) {
154: final int row = position.getRow();
155: final int column = position.getColumn();
156: if (!this.checkBounds(row, column)) {
157: throw new IndexOutOfBoundsException("The provided position is not within the defined bounds of the board!");
158: }
159: final int token = this.slimBoard.getTokenUnsafe(row, column);
160: return Optional.ofNullable(this.slimBoard.getPlayerByToken(token));
161: }
162:
163: @Override
164: public IC4Field[][] getFields() {
165: // this is the GC's worst nightmare, but whatever :P
166: // if you call this method, you probably don't care about performance anyway
167: // no need for fancy caching here ¯\_(ツ)_/¯
168: final int rows = this.getRowCount();
169: final int cols = this.getColumnCount();
170: final IC4Field[][] fields = new C4Field[rows][cols];
171: for (int row = 0; row < rows; row++) {
172: for (int col = 0; col < cols; col++) {
173: final IC4Position position = new C4Position(row, col);
174: fields[row][col] = this.getFieldInternal(position, false);
175: }
176: }
177: return fields;
178: }
179:
180: @Override
181: public Optional<IC4Solution> tryFindFirstSolution() {
182: final IC4SolutionSlim slimSolution = this.slimBoard.tryFindFirstSolution(true);
183: if (slimSolution == null) {
184: return Optional.empty();
185: }
186: final IC4Solution solution = new C4Solution(this, slimSolution);
187: return Optional.of(solution);
188: }
189:
190: @Override
191: public Set<IC4Solution> findAllSolutions() {
192: final Set<IC4SolutionSlim> slimSolutions = this.slimBoard.findAllSolutions(true);
193: if (slimSolutions.isEmpty()) {
194: return Set.of();
195: }
196: final Set<IC4Solution> solutions = new HashSet<>(slimSolutions.size());
197: for (final IC4SolutionSlim slimSolution : slimSolutions) {
198: solutions.add(new C4Solution(this, slimSolution));
199: }
200: return solutions;
201: }
202:
203: @Override
204: public boolean isSolid(final IC4Position position) {
205: return this.isSolid(position.getRow(), position.getColumn());
206: }
207:
208: @Override
209: public boolean isSolid(final int row, final int column) {
210: // we need to also shift the row by one to the top because
211: // the row below the board is also considered solid and
212: // therefore for the context of this method, the board is
213: // one row higher than it actually is
214: if (!this.checkBounds(row, column) && !this.checkBounds(row - 1, column)) {
215: throw new IndexOutOfBoundsException("The provided position is not within the defined bounds of the board!");
216: }
217: return this.slimBoard.isSolidUnsafe(row, column);
218: }
219:
220: @Override
221: public IC4Position[] getEmptyPositions() {
222: return this.getPositionsByToken(this.slimBoard.emptyToken());
223: }
224:
225: @Override
226: public IC4Position[] getPositionsByPlayer(final IC4Player player) {
227: return this.getPositionsByToken(player.getToken());
228: }
229:
230: /**
231: * Returns all positions on the board that match the given token.
232: * @param token The token to search for.
233: * @return All positions on the board that match the given token.
234: */
235: private IC4Position[] getPositionsByToken(final int token) {
236: // re-use the same thread-local buffer :)
237: final long[] buffer = this.localPositionBuffer.get();
238: final int positionsRead = this.slimBoard.getDematPositionsByTokenUnsafe(buffer, token);
239: final IC4Position[] positions = new IC4Position[positionsRead];
240: for (int i = 0; i < positions.length && i < buffer.length; i++) {
241: positions[i] = C4PositionMaterializer.rematerialize(buffer[i]);
242: }
243: return positions;
244: }
245:
246: @Override
247: public IC4Position[] getLegalPositions() {
248: final long[] buffer = this.localPositionBuffer.get();
249: final int positionsRead = this.slimBoard.getLegalDematPositionsUnsafe(buffer);
250: final IC4Position[] positions = new IC4Position[positionsRead];
251: for (int i = 0; i < positions.length && i < buffer.length; i++) {
252: positions[i] = C4PositionMaterializer.rematerialize(buffer[i]);
253: }
254: return positions;
255: }
256:
257: @Override
258: public int countEmptyPositions() {
259: return this.countPositionsByToken(this.slimBoard.emptyToken());
260: }
261:
262: @Override
263: public int countPositionsByPlayer(final IC4Player player) {
264: return this.countPositionsByToken(player.getToken());
265: }
266:
267: /**
268: * Counts all positions on the board that match the given token.
269: * @param token The token to search for.
270: * @return The number of positions on the board that match the given token.
271: */
272: private int countPositionsByToken(final int token) {
273: final long[] buffer = this.localPositionBuffer.get();
274: return this.slimBoard.getDematPositionsByTokenUnsafe(buffer, token);
275: }
276:
277: @Override
278: public int countLegalPositions() {
279: final long[] buffer = this.localPositionBuffer.get();
280: return this.slimBoard.getLegalDematPositionsUnsafe(buffer);
281: }
282:
283: @Override
284: public int hashCode() {
285: int hash = 7;
286: final int[] board = this.slimBoard.getBoardStateUnsafe();
287: for (final int token : board) {
288: hash = hash * 31 + token;
289: }
290: hash = hash * 31 + this.getMinimumSolutionSize();
291: hash = hash * 31 + this.getRowCount();
292: hash = hash * 31 + this.getColumnCount();
293: return hash;
294: }
295:
296: @Override
297: public boolean equals(final Object object) {
298: if (object == this) {
299: return true;
300: }
301: if (!(object instanceof IC4Board)) {
302: return false;
303: }
304: final IC4Board other = (IC4Board) object;
305: // quick check if dimensions even match
306: if (this.getRowCount() != other.getRowCount() || this.getColumnCount() != other.getColumnCount()) {
307: return false;
308: }
309: // more thorough check over every field
310: final int[] myBoard = this.slimBoard.getBoardStateUnsafe();
311: final int[] otherBoard = other.getInternalBoard().getBoardStateUnsafe();
312: for (int i = 0; i < myBoard.length; i++) {
313: if (myBoard[i] != otherBoard[i]) {
314: return false;
315: }
316: }
317: return this.getMinimumSolutionSize() == other.getMinimumSolutionSize();
318: }
319:
320: @Override
321: public boolean isFull() {
322: return this.slimBoard.isFull();
323: }
324:
325: @Override
326: public String toString() {
327: return "C4Board{"
328: + "slimBoard=" + this.slimBoard
329: + '}';
330: }
331: }