import os
import random
import re
import sys

DAMPING = 0.85
SAMPLES = 10000


def main():
    if len(sys.argv) != 2:
        sys.exit("Usage: python pagerank.py corpus")
    corpus = crawl(sys.argv[1])
    ranks = sample_pagerank(corpus, DAMPING, SAMPLES)
    print(f"PageRank Results from Sampling (n = {SAMPLES})")
    for page in sorted(ranks):
        print(f"  {page}: {ranks[page]:.4f}")
    ranks = iterate_pagerank(corpus, DAMPING)
    print(f"PageRank Results from Iteration")
    for page in sorted(ranks):
        print(f"  {page}: {ranks[page]:.4f}")


def crawl(directory):
    """
    Parse a directory of HTML pages and check for links to other pages.
    Return a dictionary where each key is a page, and values are
    a list of all other pages in the corpus that are linked to by the page.
    """
    pages = dict()

    # Extract all links from HTML files
    for filename in os.listdir(directory):
        if not filename.endswith(".html"):
            continue
        with open(os.path.join(directory, filename)) as f:
            contents = f.read()
            links = re.findall(r"<a\s+(?:[^>]*?)href=\"([^\"]*)\"", contents)
            pages[filename] = set(links) - {filename}

    # Only include links to other pages in the corpus
    for filename in pages:
        pages[filename] = set(
            link for link in pages[filename]
            if link in pages
        )

    return pages


def transition_model(corpus, page, damping_factor):
    """
    Return a probability distribution over which page to visit next,
    given a current page.

    With probability `damping_factor`, choose a link at random
    linked to by `page`. With probability `1 - damping_factor`, choose
    a link at random chosen from all pages in the corpus.
    """

    probability_distribution = dict()

    #if page has outgoing links
    if corpus[page]:

        for link in corpus:
            probability_distribution[link] = (1 - damping_factor) / len(corpus)

            if link in corpus[page]:
                probability_distribution[link] = probability_distribution[link] + (damping_factor / len(corpus[page]))

    else:

        for link in corpus:
            probability_distribution[link] = 1 / len(corpus)

    return probability_distribution


def sample_pagerank(corpus, damping_factor, n):
    """
    Return PageRank values for each page by sampling `n` pages
    according to transition model, starting with a page at random.

    Return a dictionary where keys are page names, and values are
    their estimated PageRank value (a value between 0 and 1). All
    PageRank values should sum to 1.
    """

    PageRank = dict()

    # set ranks of all pages to 0
    for page in corpus:
        PageRank[page] = 0.0

    # choose the first sample page at random
    sample = random.choice(list(corpus.keys()))
    PageRank[sample] += 1

    # to go to the next page, use the transition model generated by the current page

    for count in range(1, n):

        model = transition_model(corpus, sample, damping_factor)
        next_page = []
        probability_next_page = []

        for page, rank in model.items():
            next_page.append(page)
            probability_next_page.append(rank)

        sample = random.choices(next_page, weights = probability_next_page, k = 1)[0]
        PageRank[sample] += 1

    # normalise the ranks

    for page in corpus:
        PageRank[page] = PageRank[page] / n

    return PageRank

def iterate_pagerank(corpus, damping_factor):
    """
    Return PageRank values for each page by iteratively updating
    PageRank values until convergence.

    Return a dictionary where keys are page names, and values are
    their estimated PageRank value (a value between 0 and 1). All
    PageRank values should sum to 1.
    """

    PageRank = dict()
    accuracy = 0.001

    # initialise the rank of each page with 1 / N

    N = len(corpus)

    for page in corpus:
        PageRank[page] = 1 / N

    # for each page, use the PageRank formula to calculate the ranks

    while True:

        count = 0

        for page in corpus:

            new_rank = (1 - damping_factor) / N
            change = 0

            for new_page in corpus:

                if page in corpus[new_page]:
                    NumLinks = len(corpus[new_page])
                    change = change + (PageRank[new_page] / NumLinks)

            change = damping_factor * change
            new_rank += change

            if abs(PageRank[page] - new_rank) < accuracy:
                count += 1

            PageRank[page] = new_rank

        if count == N:
            break

    return PageRank

if __name__ == "__main__":
    main()
