1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
#include "TileList.h"
TileList::TileList()
{
tiles = new Tile[INITIAL_SIZE];
cur_size = INITIAL_SIZE;
}
TileList::~TileList()
{
delete[] tiles;
}
void TileList::addTile(Tile tile)
{
// O(1) (amortized)
if (amount_tiles == cur_size) {
// reached size limit, so allocate new array and move the old tiles
cur_size *= 2;
Tile *expanded_tiles = new Tile[cur_size];
for (int i = 0; i < amount_tiles; i++) {
expanded_tiles[i] = tiles[i];
}
delete[] tiles;
tiles = expanded_tiles;
}
tiles[amount_tiles++] = tile;
}
void TileList::drawAll(QGraphicsScene *scene) const
{
// O(n)
for (int i = 0; i < amount_tiles; i++) {
(tiles + i)->draw(scene);
}
}
int TileList::indexOfTopTile(int x, int y) const
{
// O(n)
for (int i = amount_tiles - 1; i >= 0; --i) {
if ((tiles + i)->contains(x, y)) {
return i;
}
}
return -1;
}
void TileList::shiftRight(int start, int end)
{
// e.g. amount_tiles=6, start=1, end=4:
// 0 1 2 3 4 5
// 0 1 1 2 3 5
// O(n)
for (int i = end; i > start; i--) {
tiles[i] = tiles[i - 1];
}
}
void TileList::shiftLeft(int start, int end)
{
// e.g. amount_tiles=6, start=4, end=1:
// 0 1 2 3 4 5
// 0 2 3 4 4 5
// O(n)
for (int i = end; i < start; i++) {
tiles[i] = tiles[i + 1];
}
}
void TileList::raise(int x, int y)
{
// 0 1 2 3 4 5 -
// 0 1 2 3 4 5 3
// 0 1 2 4 5 5 3
// 0 1 2 4 5 3 -
// O(n)
int index = indexOfTopTile(x, y);
if (index == -1 || index == amount_tiles - 1) {
// no tile found, or tile is already at top
return;
}
Tile tmpTile = tiles[index];
shiftLeft(amount_tiles - 1, index);
tiles[amount_tiles - 1] = tmpTile;
}
void TileList::lower(int x, int y)
{
// 0 1 2 3 4 5 -
// 0 1 2 3 4 5 3
// 0 0 1 2 4 5 3
// 3 0 1 2 4 5 -
// O(n)
int index = indexOfTopTile(x, y);
if (index == -1 || index == 0) {
// no tile found, or tile is already at bottom
return;
}
Tile tmpTile = tiles[index];
shiftRight(0, index);
tiles[0] = tmpTile;
}
void TileList::remove(int x, int y)
{
// V
// 0 1 2 3 4 5
// 0 1 3 4 5 5
// 0 1 3 4 5 x
// O(n)
int index;
if ((index = indexOfTopTile(x, y)) != -1) {
shiftLeft(amount_tiles - 1, index);
amount_tiles--;
}
}
void TileList::removeAll(int x, int y)
{
// O(n^2)
int index;
while ((index = indexOfTopTile(x, y)) != -1) {
shiftLeft(amount_tiles - 1, index);
amount_tiles--;
}
}
|
