// hashing: http://www.ccs.neu.edu/home/sbratus/com1101/hash-dict.html
// single linked list: Adam Drozdek: Data Structures and Algorithms in C++
//  
  
using System;
using System.Collections.Generic;
using System.Linq;
using System.Net;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Shapes;

namespace Hashing
{
    public partial class MainPage : UserControl
    {
        // Node //////////////////////////////////////////

        class Node
        {
	        public string key;
            public string value;
	        public Node next;

	        public Node()
            {
	            key = "\0";
                value = "\0";
	            next = null;
            }

            public Node(string s, string r, Node ptr = null)
            {
	            key = s;
                value = r;
	            next = ptr;
            }
        };

        // SLList /////////////////////////////////////////

        struct SLList
        {
	        public Node head, tail;

            public void addToTail(string s, string r)
            {
                if (tail != null)
                {
                    tail.next = new Node(s, r);
                    tail = tail.next;
                }
                else
                    head = tail = new Node(s, r);
            }

            public string printSLList()
            {
                string r = "";
                for (Node p = head; p != null; )
                {
                    r += p.key + " ";
                    p = p.next;
                }

                return r;
            }

            public Node searchInSLList(string s)
            {
                for (Node p = head; p != null; p = p.next)
                {
                    if (p.key == s)
                    {
                        return p;
                    }
                }
                return null;
            }
        };

        ////////////////////////////////////////////////////

        int HashString(string s)
        {
            int h = 0; 
  
            for (int i = 0 ; i < s.Length; i++)  
                h = 5*h + s[i];   
  
            return h;
        }

        public MainPage()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, RoutedEventArgs e)
        {
            string input = string1.Text;
            string result = "";
            string str = input;
            int i, slot;
	        const int wordsNumber = 10;
	        string[] words = {"car", "ice", "tree", "loop", "way", "sun", "grass", "lake", "sea", "gold"};
	        string[] wordsInfo = {"car info", "ice info", "tree info", "loop info", "way info", 
		                          "sun info", "grass info", "lake info", "sea info", "gold info"};
	        const int hashTableLength = 15;
	        SLList[] hashTable = new SLList[hashTableLength];

            for (i = 0; i < wordsNumber; i++)
            {
                slot = HashString(words[i]) % hashTableLength;
                hashTable[slot].addToTail(words[i], wordsInfo[i]);
            }

            for (i = 0; i < hashTableLength; i++)		// print the hash table
            {
                result += i + " : ";
                result += hashTable[i].printSLList();
                result += "\n";
            }

            slot = HashString(str) % hashTableLength;		// find the word and print the info
            Node p = hashTable[slot].searchInSLList(str);
            if (p != null)
            {
                result += p.value + "\n";
            }
            else result += "Word not found!\n";

            resultstring.Text = result;
        }
    }
}