Data-structures 02

1a

1b

2

class CircularDynamicArray:
	array: Array[Any] # storage array
	capacity: int     # current capacity, doubled if full
	size: int         # current number of elements in array
	start: int        # physical index of "start"

# Return physical index based on "logical" index, O(1)
def physical_index(self, i):
  # return "circular" index
  return (self.start + i) % self.capacity
 
# Resizing(doubling) is O(n)
# but amortized O(1), as shown many times in class
# and in exercise 1a with multiplier 1.1
def resize(self):
  # double the capacity, allocate new array
  new_capacity = self.capacity * 2
  new_array = Array[new_capacity]
 
  # copy all existing elements
  for i in range(self.size):
    new_array[i] = self.array[self.physical_index(i)]
 
  # update internal state
  self.array = new_array
  self.capacity = new_capacity
  self.start = 0

def is_empty(self):
  return self.size == 0
 
# O(1) + possible resizing, amortized O(1)
def push_back(self, value):
  if self.size == self.capacity:
	self.resize()
  # regular push to the end
  self.array[self.physical_index(self.size)] = value
  self.size += 1
 
# O(1) + possible resizing, amortized O(1)
def push_front(self, value):
  if self.size == self.capacity:
	self.resize()
  # push to the beginning, adjust start
  self.start = (self.start - 1 + self.capacity) % self.capacity
  self.array[self.start] = value
  self.size += 1
 
# Pop from the "logical" end, O(1)
def pop_back(self):
  if self.is_empty():
	error "Empty"
  self.size -= 1
  return self.array[self.physical_index(self.size)]
 
# Pop from the "logical" start, O(1)
def pop_front(self):
	if self.is_empty():
		error "Empty"
	value = self.array[self.start]
	# move logical start
	self.start = (self.start + 1) % self.capacity
	self.size -= 1
	return value

3a

graph LR;
1(2)
2(1)
3(3, 4)

5(3)
6(2)
8(4)

9(3)
10(1, 2)
12(4)

	subgraph Sub1 [Start]
		1---2
		1---3
	end
	subgraph Sub2 [Delete 1]
		5---6
		5---8
	end
	subgraph Sub3 [Insert 1]
		9---10
		9---12
	end

Sub1-->Sub2
Sub2-->Sub3

3b

3c

graph TD;
	subgraph Sub2 [Insert 2]
		direction LR;
		Sub2Sub1-->Sub2Sub2
	end
	subgraph Sub2Sub1 [Start]
		1s1(5)
		1s2(4)
		1s3(6, 7)
		1s1---1s2
		1s1---1s3
	end
	subgraph Sub2Sub2 [Insert]
		2s1(5)
		2s2(2, 4)
		2s3(6, 7)
		2s1---2s2
		2s1---2s3
	end

	subgraph Sub3 [Insert 1]
		direction LR;
		Sub3Sub1-->Sub3Sub2
	end
	subgraph Sub3Sub1 [Insert]
		3s1(5)
		3s2(1, 2, 4)
		3s3(6, 7)
		3s1---3s2
		3s1---3s3
	end
	subgraph Sub3Sub2 [Split]
		3s4(2, 5)
		3s5(1)
		3s6(4)
		3s7(6, 7)
		3s4---3s5
		3s4---3s6
		3s4---3s7
	end

	subgraph Sub4 [Delete 2]
		direction LR;
		Sub4Sub1-->Sub4Sub2
	end
	subgraph Sub4Sub1 [Find Successor]
		4s1(4, 5)
		4s2(1)
		4s3(.)
		4s4(6, 7)
		4s1---4s2
		4s1---4s3
		4s1---4s4
	end
	subgraph Sub4Sub2 [Rotate]
		4s5(4, 6)
		4s6(1)
		4s7(5)
		4s8(7)
		4s5---4s6
		4s5---4s7
		4s5---4s8
	end

	subgraph Sub5 [Delete 1]
		direction LR;
		Sub5Sub1-->Sub5Sub2
	end
	subgraph Sub5Sub1 [Delete]
		5s1(4, 6)
		5s2(.)
		5s3(5)
		5s4(7)
		5s1---5s2
		5s1---5s3
		5s1---5s4
	end
	subgraph Sub5Sub2 [Merge]
		5s5(6)
		5s6(4, 5)
		5s7(7)
		5s5---5s6
		5s5---5s7
	end

Sub2-->Sub3
Sub3-->Sub4
Sub4-->Sub5

4