percolation/Percolation.java at master · pomkine/percolation · GitHub

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

public class Percolation {
  //0-closed, 1-open
  private int [] states;
  private int side;
  private WeightedQuickUnionUF cellStorage;
// create N-by-N grid, with all sites blocked
     public Percolation(int N){
       side=N;
        //+2 are for additional top and bottom cells
       cellStorage=new WeightedQuickUnionUF(N*N+2);
       states=new int[N*N+2];
       for(int index=0;index<N*N;index++){
           states[index]=0;
       }
       states[N*N]=1;
       states[N*N+1]=1;
     }
   // open site (row i, column j) if it is not already
     public void open(int i, int j){
       checkRange(i,j);
       if(isOpen(i,j))return;
       int cell=getCellIndex(i,j);
       states[cell]=1;
       //if not top row
       if(i!=1 && isOpen(i-1,j)){
          union(getCellIndex(i-1,j),cell);
       }else if(i==1){
          //connect to virtual top cell
         union(cell,side*side);
       }
       //if not bottom row
       if(i!=side && isOpen(i+1,j)){
         union(getCellIndex(i+1,j),cell);
       }else if (i==side){
          //connect to virtual bottom cell
          union(cell,side*side+1);
       }
       //if not left border
       if(j!=1 && isOpen(i,j-1)){
         union(getCellIndex(i,j-1),cell);
       }
       //if not right border
        if(j!=side && isOpen(i,j+1)){
         union(getCellIndex(i,j+1),cell);
       }
     }

     private void checkRange(int i, int j){
       if (i<=0||j<=0||i>side||j>side)throw new IndexOutOfBoundsException();
     }

     private void union(int a, int b){
         if (!cellStorage.connected(a,b)){
           cellStorage.union(a,b);
         }
     }

     // is site (row i, column j) open?
     public boolean isOpen(int i, int j){
       checkRange(i,j);
       return states[getCellIndex(i,j)]==1;
     }

      // is site (row i, column j) full?
     public boolean isFull(int i, int j){
       checkRange(i,j);
       return cellStorage.connected(side*side,getCellIndex(i,j));
     }

      // does the system percolate?
     public boolean percolates(){
       return cellStorage.connected(side*side,side*side+1);
     }

     private int getCellIndex(int row, int column){
       return (side*(row-1))+column-1;
     }
}