| 1 |
(* Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010 |
| 2 |
Free Software Foundation, Inc. *) |
| 3 |
(* This file is part of GNU Modula-2. |
| 4 |
|
| 5 |
GNU Modula-2 is free software; you can redistribute it and/or modify it under |
| 6 |
the terms of the GNU General Public License as published by the Free |
| 7 |
Software Foundation; either version 3, or (at your option) any later |
| 8 |
version. |
| 9 |
|
| 10 |
GNU Modula-2 is distributed in the hope that it will be useful, but WITHOUT ANY |
| 11 |
WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 12 |
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| 13 |
for more details. |
| 14 |
|
| 15 |
You should have received a copy of the GNU General Public License along |
| 16 |
with gm2; see the file COPYING. If not, write to the Free Software |
| 17 |
Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. *) |
| 18 |
IMPLEMENTATION MODULE MakeBoxes ; |
| 19 |
|
| 20 |
|
| 21 |
FROM StrIO IMPORT WriteString, WriteLn ; |
| 22 |
|
| 23 |
FROM Chance IMPORT GetRand ; |
| 24 |
|
| 25 |
|
| 26 |
CONST |
| 27 |
MaxBox = 15000 ; |
| 28 |
MaxIndex = 500 ; |
| 29 |
|
| 30 |
TYPE |
| 31 |
Box = RECORD |
| 32 |
LengthX, |
| 33 |
LengthY: CARDINAL ; |
| 34 |
END ; |
| 35 |
|
| 36 |
Index = RECORD |
| 37 |
Start, (* Start of the Box list *) |
| 38 |
End : CARDINAL ; (* End of the Box list *) |
| 39 |
END ; |
| 40 |
|
| 41 |
VAR |
| 42 |
BoxIndex : ARRAY [0..MaxIndex] OF Index ; |
| 43 |
Boxes : ARRAY [1..MaxBox] OF Box ; |
| 44 |
NoOfBoxes : CARDINAL ; (* Number of boxes in array Boxes *) |
| 45 |
NoOfIndices: CARDINAL ; (* Number of indices in BoxIndex *) |
| 46 |
|
| 47 |
|
| 48 |
(* |
| 49 |
InitBoxes - Initializes a list of boxes. |
| 50 |
An index to this box list is returned. |
| 51 |
*) |
| 52 |
|
| 53 |
PROCEDURE InitBoxes () : CARDINAL ; |
| 54 |
BEGIN |
| 55 |
IF NoOfIndices=MaxIndex |
| 56 |
THEN |
| 57 |
WriteString('Too many box list indices in Module MakeBoxes') ; |
| 58 |
WriteLn ; |
| 59 |
WriteString('Increase MaxIndex') ; |
| 60 |
WriteLn ; |
| 61 |
HALT |
| 62 |
ELSE |
| 63 |
INC(NoOfIndices) ; |
| 64 |
WITH BoxIndex[NoOfIndices] DO |
| 65 |
Start := NoOfBoxes+1 ; |
| 66 |
End := NoOfBoxes |
| 67 |
END ; |
| 68 |
RETURN(NoOfIndices) |
| 69 |
END |
| 70 |
END InitBoxes ; |
| 71 |
|
| 72 |
|
| 73 |
(* |
| 74 |
AddBoxes - Adds a list of boxes MinX..MaxX, MinY..MaxY |
| 75 |
to a box list BoxListIndex. |
| 76 |
*) |
| 77 |
|
| 78 |
PROCEDURE AddBoxes (BoxListIndex: CARDINAL; |
| 79 |
MinX, MinY, MaxX, MaxY: CARDINAL) ; |
| 80 |
BEGIN |
| 81 |
WITH BoxIndex[BoxListIndex] DO |
| 82 |
Expand(BoxListIndex, MinX, MinY, MaxX, MaxY) ; |
| 83 |
End := NoOfBoxes |
| 84 |
END |
| 85 |
END AddBoxes ; |
| 86 |
|
| 87 |
|
| 88 |
(* |
| 89 |
Expand - expands the box limitations MinX..MaxX, MinY..MaxY for all |
| 90 |
possibilities of boxes. |
| 91 |
*) |
| 92 |
|
| 93 |
PROCEDURE Expand (BoxListIndex: CARDINAL; |
| 94 |
MinX, MinY, MaxX, MaxY: CARDINAL) ; |
| 95 |
VAR |
| 96 |
i, j: CARDINAL ; |
| 97 |
BEGIN |
| 98 |
i := MinX ; |
| 99 |
WHILE i<=MaxX DO |
| 100 |
j := MinY ; |
| 101 |
WHILE j<=MaxY DO |
| 102 |
AddBox(BoxListIndex, i, j) ; |
| 103 |
INC(j) |
| 104 |
END ; |
| 105 |
INC(i) |
| 106 |
END |
| 107 |
END Expand ; |
| 108 |
|
| 109 |
|
| 110 |
(* |
| 111 |
AddBox - adds a box of Width, Height to a list of boxes specified by |
| 112 |
BoxListIndex. |
| 113 |
*) |
| 114 |
|
| 115 |
PROCEDURE AddBox (BoxListIndex: CARDINAL; |
| 116 |
Width, Height: CARDINAL) ; |
| 117 |
BEGIN |
| 118 |
IF NoOfBoxes=MaxBox |
| 119 |
THEN |
| 120 |
WriteString('Too many boxes in a list in Module MakeBoxes') ; |
| 121 |
WriteLn ; |
| 122 |
WriteString('Increase MaxBox') ; |
| 123 |
WriteLn ; |
| 124 |
HALT |
| 125 |
ELSIF UniqueBox(BoxListIndex, Width, Height) |
| 126 |
THEN |
| 127 |
INC(NoOfBoxes) ; |
| 128 |
WITH Boxes[NoOfBoxes] DO |
| 129 |
LengthX := Width ; |
| 130 |
LengthY := Height |
| 131 |
END |
| 132 |
END |
| 133 |
END AddBox ; |
| 134 |
|
| 135 |
|
| 136 |
(* |
| 137 |
UniqueBox - returns true if a box Width, Height is unique in the |
| 138 |
box list BoxListIndex. |
| 139 |
*) |
| 140 |
|
| 141 |
PROCEDURE UniqueBox (BoxListIndex: CARDINAL; |
| 142 |
Width, Height: CARDINAL) : BOOLEAN ; |
| 143 |
VAR |
| 144 |
i : CARDINAL ; |
| 145 |
Found: BOOLEAN ; |
| 146 |
BEGIN |
| 147 |
WITH BoxIndex[BoxListIndex] DO |
| 148 |
i := Start ; |
| 149 |
Found := FALSE ; |
| 150 |
WHILE (NOT Found) AND (i<=End) DO |
| 151 |
WITH Boxes[i] DO |
| 152 |
Found := (LengthX=Width) AND (LengthY=Height) |
| 153 |
END ; |
| 154 |
INC(i) |
| 155 |
END |
| 156 |
END ; |
| 157 |
RETURN( NOT Found ) |
| 158 |
END UniqueBox ; |
| 159 |
|
| 160 |
|
| 161 |
(* |
| 162 |
KillBoxes - Kills a complete box list. |
| 163 |
*) |
| 164 |
|
| 165 |
PROCEDURE KillBoxes (BoxListIndex: CARDINAL) ; |
| 166 |
BEGIN |
| 167 |
IF NoOfIndices>0 |
| 168 |
THEN |
| 169 |
(* Destroy index to box list *) |
| 170 |
WITH BoxIndex[BoxListIndex] DO |
| 171 |
Start := 0 ; |
| 172 |
End := 0 |
| 173 |
END ; |
| 174 |
(* |
| 175 |
If killed last box list see if we can garbage collect |
| 176 |
previously killed middle indices. |
| 177 |
*) |
| 178 |
IF NoOfIndices=BoxListIndex |
| 179 |
THEN |
| 180 |
REPEAT |
| 181 |
DEC(NoOfIndices) |
| 182 |
UNTIL (NoOfIndices=0) OR (BoxIndex[NoOfIndices].Start#0) |
| 183 |
END ; |
| 184 |
NoOfBoxes := BoxIndex[NoOfIndices].End |
| 185 |
ELSE |
| 186 |
WriteString('All boxes have been killed - Module MakeBoxes') ; |
| 187 |
WriteLn ; |
| 188 |
HALT |
| 189 |
END |
| 190 |
END KillBoxes ; |
| 191 |
|
| 192 |
|
| 193 |
(* |
| 194 |
GetAndDeleteRandomBox - Returns a random box from the box list and |
| 195 |
this box is then deleted from the list. |
| 196 |
*) |
| 197 |
|
| 198 |
PROCEDURE GetAndDeleteRandomBox (BoxListIndex: CARDINAL; |
| 199 |
VAR SizeX, SizeY: CARDINAL) ; |
| 200 |
VAR |
| 201 |
i, j: CARDINAL ; |
| 202 |
BEGIN |
| 203 |
WITH BoxIndex[BoxListIndex] DO |
| 204 |
i := Start+GetRand(End-Start+1) ; (* +1 for GetRand *) |
| 205 |
j := i ; |
| 206 |
REPEAT |
| 207 |
IF Boxes[j].LengthX=0 |
| 208 |
THEN |
| 209 |
INC(j) ; |
| 210 |
IF j>End |
| 211 |
THEN |
| 212 |
j := Start |
| 213 |
END |
| 214 |
END |
| 215 |
UNTIL (j=i) OR (Boxes[j].LengthX#0) ; |
| 216 |
WITH Boxes[j] DO |
| 217 |
SizeX := LengthX ; |
| 218 |
SizeY := LengthY ; |
| 219 |
LengthX := 0 ; (* Now delete this box *) |
| 220 |
LengthY := 0 |
| 221 |
END |
| 222 |
END |
| 223 |
END GetAndDeleteRandomBox ; |
| 224 |
|
| 225 |
|
| 226 |
PROCEDURE Init ; |
| 227 |
BEGIN |
| 228 |
NoOfBoxes := 0 ; |
| 229 |
NoOfIndices := 0 ; |
| 230 |
WITH BoxIndex[NoOfIndices] DO |
| 231 |
End := 0 |
| 232 |
END |
| 233 |
END Init ; |
| 234 |
|
| 235 |
|
| 236 |
BEGIN |
| 237 |
Init |
| 238 |
END MakeBoxes. |