import time
// 41s.

struct Node[T] {
mut:
	data T
	prev ?&Node[T]
	next ?&Node[T]
}

struct LinkedList[T] {
mut:
	size usize
	head ?&Node[T]
}

fn new_linked_list[T]() &LinkedList[T] {
	return &LinkedList[T]{}
}

fn (mut li LinkedList[T]) add[T](data T) ? {
	mut node := &Node[T]{data, none, none}

	if li.head == none {
		li.head = node
		node.next = node
		node.prev = node
	} else {
		node.next = li.head
		node.prev = li.head.prev
		node.prev?.next = node
		li.head.prev = node
	}

	li.size += 1
}

fn (mut li LinkedList[T]) pop[T]() ?T {
	if li.head == none {
		return none
	}
	if li.size == 1 {
		data := li.head?.data
		li.head?.next = none
		li.head?.prev = none
		li.head = none
		li.size -= 1
		return data
	}

	mut tail := li.head?.prev?
	mut curr := tail.prev?
	curr.next = li.head
	li.head?.prev = curr

	tail.next = none
	tail.prev = none
	li.size -= 1

	return tail.data
}

@[heap]
struct Integer {
	value int
}

fn test_main() {
	max_itr := 2
	t := time.now()
	for itr in 0 .. max_itr {
		mut list := new_linked_list[&Integer]()
		println('Itr#${itr} list size: ${list.size}')

		list.add(&Integer{10})
		println('Itr#${itr} list size: ${list.size}')
		list.add(&Integer{20})
		println('Itr#${itr} list size: ${list.size}')

		mut n := list.pop()
		println('Itr#${itr} list size: ${list.size}, data: ${n?}')
		n = list.pop()
		println('Itr#${itr} list size: ${list.size}, data: ${n?}')
		n = list.pop()
		println('Itr#${itr} list size: ${list.size}, data: ${n}')
	}
	d := time.since(t)
	println('Bye(time ${d})!')
}