# Note s on Pointers, Arrays and 2D arrays in Python

A = [3,5,7]  # an ordinary array
B = A        # a "copy" of the array?
B[0] = 9
print(A)     # what do you expect A to be?
A[1] = 8   
print(B)     # what do you expect B to be?

# You should see that, after the lines above, both A and B become
# [9,8,7].  This behavior is in contrast to the behavior of:
a = 3
b = a
b = 4
#print(a)  # of course a is still 3

# But changing B[0] is not the same as changing B, why?  Because unlike
# the integer variables a and b, the array variables A and B are POINTERS,
# that is, they are memory addresses of where the actual array is stored.
# You didn't copy the entire array into a new memory location with B=A,
# you only copied the pointer.  B[0] and A[0] therefore refers to the
# same memory location, and therefore changing one will also change the other.

# But if you now do:
B = [4,6,8]
print(A)  # don't expect A to also become 4,6,8, why?

# because B=[4,6,8] reassigned B to point somewhere else - the location of
# the new array [4,6,8] that you just created.  B is nolonger pointing to
# the same array that A is pointing to.  This is why CHANGING B IS NOT THE
# SAME AS CHANGING B[i].  This is also why a function that changes the
# contents of an array argument is not just local.  

# Quiz:  Determine the output of the following and explain why:

def f(A):
  A[0] += 1
  A = [0,0,0]
#
C = [2,2,2]
f(C)
print(C)

# Answer: it prints [3,2,2].  The assignment A=[0,0,0] inside the
# function is local, but A[0] += 1 is not changing A, but the array
# that A points to, which exists outside the function call.  We don't
# really pass the entire array to the function (that can be
# inefficient), but just a pointer to the array.  So if a function
# changes that array's contents, those changes are reflected outside.

## It's not just arrays that use pointers, but all mutable data structures,
## including association lists (hash maps).

## To copy an array (or hash map), we can write our own loop, or use
C2 = C.copy()  # creates a shallow copy of C
# This works for simple arrays such as arrays of integers or strings, but
# not for arrays that contain other pointers ...


########## 2D Arrays ###########

# An array is addressed used one index. A 2D array is addressed with 2
# indices.  Picture a grid.  Each square of the grid is identified by a
# row (y) coordinate and column (x) coordinate. In Python, there are two ways
# to represent 2D (and 3D, 4D by extrapolation) arrays.

# The first method is to use an array of arrays:

A = [ ["a","b","c","d"], ["p","q","r","s"], ["w","x","y","z"] ]

""" 
You can think of A as representing a 3x4 2D array:

a b c d
p q r s
w x y z

"""

print(len(A))  # what do you expect?   Answer: 3, the number of rows

# each array within A represents one row of the 2D array.  The length of A
# is therefore the number of rows.  There are 4 columns.

print(len(A[0]))  # what do you expect here? answer: 4, the number of columns

print(A[1])   # prints the second row

# Each value (string) stored in the array requires 2 indices to access:

print(A[0][0])  # prints a
print(A[0][2])  # prints c
print(A[1][2])  # what does this print?

A[2][2] = "K"   # which value did I change to K?

### Creating a 2D array.

# With a 1D array we have the option of starting with [] and then
# adding to it one value at a time with .append, or use something like
# [' ']*4.  With 2D arrays, we also have the option of using .append, but
# that's rather cumbersome.  But setting up an intial array with all
# the required rows and columns is actually a bit tricky.

B = [ [0]*3 ] * 3  # what do you think B is?

print(B)
# this prints [[0, 0, 0], [0, 0, 0], [0, 0, 0]].  Unfortunately, WE CANNOT
# use this as a two-D array.

B[0][0] = 1  # which value was set to 1?
print(B)
# this prints [[1, 0, 0], [1, 0, 0], [1, 0, 0]], which is NOT what you want.

# What happened? Why did B[0][0]=1 change more than one value?  If you 
# understood the ideas concerning pointers as explained above,
# you can probably guess what happened.  When the array created by the
# expression [0]*3 was itself copied three times (by the outer *3), only
# the *pointer* to the array was copied three times, not the array itself.
# So we don't have an array of three sub-arrays but an array of three pointers
# to a single subarray.

# Arrays being referenced by pointers is an issue because arrays
# are mutable (destructable).  If We used tuples or strings, 
# whether they're referenced by pointers wouldn't matter: the programmer
# doesn't even need to know.  But for arrays and any other kinds of
# mutable data structures, we need to be aware of pointers.

# Time for quiz! Determine the output of the following and explain why:

def f(A,x):
   A[0] += 1
   x += 1

q = 0   
f(Q,q)   # Q is from above
print(Q,q) # what does this print?



# Answer:you will see Q[0] increased by one, but q is still 0, because
# Q is a pointer and q is not.  We changed Q[0] in the array but not Q.


#### Now back to creating and initalizing a 2D array properly.

P = Q.copy()  # this copies the array, not Q itself
# however, if Q contains pointers, it's the pointers that are copied.

#So to set up, for example, a 3x4 array properly, you can do

A = []
for i in range(0,3): A.append([0]*4)
# Each time we write [0]*4 a new array is created.
# The above for loop is equivalent to
i = 0
while i<3:
    A.append([0]*4)
    i+=1
#while

##### function to print 2D array

def print2d(A,rows,cols): # prints A, given dimensions in rows x cols
    i = 0 # row index
    while i<rows:
        k = 0
        while k<cols:
            print(A[i][k],end=" ")  # print without new line
            k += 1
        #while k
        print("")    # prints new line
        i +=1
    # while i
# alternatively, if rows and cols are not passed into the function,
# we can do (inside function:) rows,cols = len(A),len(A[0])


# function to find the largest value in a 2D array, returns i,k index of value:
def maxi(A):
    rows,cols = len(A),len(A[0])
    mi,mk = 0,0 # start at first value
    i = 0 # row index
    while i<rows:
        k = 0 # column index
        while k<cols:
            if A[i][k] > A[mi][mk]: mi,mk = i,k
            k +=1
        # while k
        i +=1
    # while i
    return (mi,mk)
# maxi

    
############### Simulating a 2D array with a 1D array ############

# The other way of creating a 2D array is to use a 1D array.  Say you
# want to create a 4 rows by 5 columns array of integers (also called
# a "matrix"), you can just create an array 20 integers, and keep
# track that indices 0-4 refer to the first row, 5-9 refer to the
# second row, and so on. In this setting, instead of writing A[i][k],
# you would instead write A[i*columns+k], where columns is the number
# of values in each row (same as number of columns). So for example,
# A[2*columns+1] would refer to the second value in the third row:

rows,columns = 4,5
A =[0]*(rows*columns)
# array to fill each coordinate i,k with i*k:
for i in range(0,rows):
   for k in range(0,columns):
      A[i*columns+k] = i*k

# Print this 1D array as a 2D array:

def printas2D(A,rows,cols):  # print array A as a rowsXcols 2D array
  if len(A) != rows*cols: raise Exception("array not of right size")
  i = 0
  while i<rows:
     print(A[i*cols:i*cols+cols]) # print portion of A representing 1 row
     i += 1
#printas2D

printas2D(A,rows,columns) # prints array created above

# You should know that the computer's memory itself can be thought of
# as a large 1D array, and a memory addresses index the array.  So what
# ever data structure you create must ultimately fit inside this array
# anyway.