{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "We've learned a lot about arrays and how to manage the content of an array, but there other types of collections available in .NET for you to use with C#. In this module, we will learn about a few of those types and show how they can each represent an element of a card game.\n", "\n", "## Hashtable and SortedList\n", "\n", "A [Hashtable](https://docs.microsoft.com/dotnet/api/system.collections.hashtable?view=netcore-3.1?WT.mc_id=visualstudio-twitch-jefritz) and [SortedList](https://learn.microsoft.com/en-us/dotnet/api/system.collections.sortedlist) are collections of key/value pairs that contain no duplicate keys. The `Hashtable` is sorted based on the hash hash of the keys and a `SortedList` is sorted based on the key value.\n", "\n", "Let's put three cards into a SortedList and a Hashtable and see how the're sorted differently.  We'll use a hand with a poker straight flush of 2, 3, 4, 5, and 6 of clubs:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "dotnet_interactive": { "language": "csharp" }, "polyglot_notebook": { "kernelName": "csharp" } }, "outputs": [], "source": [ "// var deck = new Hashtable();\n", "var deck = new SortedList();\n", "deck.Add(\"2C\", \"2C\");\n", "deck.Add(\"3C\", \"3C\");\n", "deck.Add(\"4C\", \"4C\");\n", "deck.Add(\"5C\", \"5C\");\n", "deck.Add(\"6C\", \"6C\");\n", "\n", "display(deck)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Try commenting and uncommenting the definition of the deck and observe how it sorts the collection differently for each of the types. The Hashtable is not stored in the order by the raw values of the key, but by the hashed values of the key. Those hashed keys mean that it is quicker to look up those values from the Hashtable than the SortedList. Let's do a simple performance test, fetching a card from our hand of 5 cards 10 million times. This data set is so small, we need to fetch a random card millions of times in order to observe a difference in performance. \n", "\n", "Try running this block again, and we'll choose a card from the hand based on a random rank value. Run the code for both the SortedList and the Hashtable and observe the time that it takes to select a card from the hand 10 million times. " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "dotnet_interactive": { "language": "csharp" }, "polyglot_notebook": { "kernelName": "csharp" } }, "outputs": [], "source": [ "//var deck = new SortedList();\n", "var deck = new Hashtable();\n", "\n", "// These statements add a value to the collection in the form (key, value)\n", "deck.Add(\"2C\", \"2C\");\n", "deck.Add(\"3C\", \"3C\");\n", "deck.Add(\"4C\", \"4C\");\n", "deck.Add(\"5C\", \"5C\");\n", "deck.Add(\"6C\", \"6C\");\n", "\n", "var random = new Random();\n", "for (var i=0; i<10_000_000; i++) {\n", "\tvar rank = random.Next(2, 7);\n", "\tvar foundCard = deck[$\"{rank}C\"];\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Which one would you use to model a hand of cards? \n", "\n", "Another key feature of the SortedList and Hashtable is that they prevent duplication of keys in their collection. Let's look at our hand of cards and try to add a card with the same key:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "dotnet_interactive": { "language": "csharp" }, "polyglot_notebook": { "kernelName": "csharp" } }, "outputs": [], "source": [ "//var hand = new SortedList();\n", "var hand = new Hashtable();\n", "\n", "// These statements add a value to the collection in the form (key, value)\n", "hand.Add(\"2C\", \"2C\");\n", "hand.Add(\"3C\", \"3C\");\n", "hand.Add(\"4C\", \"4C\");\n", "hand.Add(\"5C\", \"5C\");\n", "hand.Add(\"6C\", \"6C\");\n", "\n", "// Add a duplicate\n", "hand.Add(\"2C\", \"7C\");\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Even though the value of \"7C\" is unique in the collection, both SortedList and Hashtable throw an error when adding a value with a key that already exists.\n", "\n", "We've been adding cards to the collection, but we can also remove cards from the collection with the `Remove` method:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "dotnet_interactive": { "language": "csharp" }, "polyglot_notebook": { "kernelName": "csharp" } }, "outputs": [], "source": [ "//var hand = new SortedList();\n", "var hand = new Hashtable();\n", "\n", "// These statements add a value to the collection in the form (key, value)\n", "hand.Add(\"2C\", \"2C\");\n", "hand.Add(\"3C\", \"3C\");\n", "hand.Add(\"4C\", \"4C\");\n", "hand.Add(\"5C\", \"5C\");\n", "hand.Add(\"6C\", \"6C\");\n", "\n", "// Remove a card\n", "hand.Remove(\"2C\");\n", "display(hand);\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Queues\n", "A [Queue](https://docs.microsoft.com/dotnet/api/system.collections.queue?view=netcore-3.1&WT.mc_id=visualstudio-twitch-jefritz) is a collection of objects stored and accessed in a first-in / first-out manner. `Enqueue` to add elements to the `Queue` and `Dequeue` to remove elements from the `Queue`. You can also `Peek` to inspect the oldest element in the `Queue`\n", "\n", "In the scenario of building a card game, a Queue might represent the collection of cards that is being delivered to a player by the dealer. This is not their hand, but the middle collection that represents that pile of cards the dealer builds in front of the player. The first card delivered to the player is picked up first, then the second, and so forth" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "dotnet_interactive": { "language": "csharp" }, "polyglot_notebook": { "kernelName": "csharp" } }, "outputs": [], "source": [ "var myHand = new Queue();\n", "myHand.Enqueue(\"4C\");\n", "myHand.Enqueue(\"2C\");\n", "myHand.Enqueue(\"3C\");\n", "\n", "myHand" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Our hand contains the three cards, and they reside in the order that they arrived in our hand. We can look at several properties of the queue so that we can measure and interact with the queue properly. \n", "\n", "We can count the number of entries in the queue:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "dotnet_interactive": { "language": "csharp" }, "polyglot_notebook": { "kernelName": "csharp" } }, "outputs": [], "source": [ "myHand.Count" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can also peek at the first entry in the queue without removing it from the queue:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "dotnet_interactive": { "language": "csharp" }, "polyglot_notebook": { "kernelName": "csharp" } }, "outputs": [], "source": [ "display(myHand.Peek());\n", "display(myHand);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can finally dequeue an entry from the queue and this will remove the first entry and return that value:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "dotnet_interactive": { "language": "csharp" }, "polyglot_notebook": { "kernelName": "csharp" } }, "outputs": [], "source": [ "display(myHand.Dequeue());\n", "myHand" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Stacks\n", "We've modeled a hand of cards and the process of dealing a hand of cards, but what about the deck of cards? We've previously modeled this as an array and while that worked its not entirely accurate behavior of the deck of cards. We couldn't really remove a card or add a card to the deck.\n", "\n", "A [Stack](https://docs.microsoft.com/dotnet/api/system.collections.stack?view=netcore-3.1&WT.mc_id=visualstudio-twitch-jefritz) is a collection that is accessed in Last-in/First-out manner using the `Push` and `Pop` methods to add and remove items, with the `Peek` method available to examine the next item to be removed from the `Stack`.  The `Stack` is our best representation of a deck of cards:  the last card that is placed on the top of the deck is the first to be dealt to a player." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "dotnet_interactive": { "language": "csharp" }, "polyglot_notebook": { "kernelName": "csharp" } }, "outputs": [], "source": [ "var myDeck = new Stack();\n", "myDeck.Push(\"AD\");\n", "myDeck.Push(\"AS\");\n", "myDeck.Push(\"9H\");\n", "myDeck.Push(\"9S\");\n", "myDeck.Push(\"9C\");\n", "\n", "myDeck" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's take a look at the top card of the deck using the `Peek` method. Yea, you really are peeking at the first card on top of the deck!" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "dotnet_interactive": { "language": "csharp" }, "polyglot_notebook": { "kernelName": "csharp" } }, "outputs": [], "source": [ "display(myDeck.Peek());\n", "var thisCard = myDeck.Pop();\n", "\n", "display(thisCard);\n", "display(myDeck);" ] } ], "metadata": { "kernelspec": { "display_name": ".NET (C#)", "language": "C#", "name": ".net-csharp" }, "language_info": { "name": "polyglot-notebook" }, "polyglot_notebook": { "kernelInfo": { "defaultKernelName": "csharp", "items": [ { "aliases": [], "languageName": "csharp", "name": "csharp" } ] } } }, "nbformat": 4, "nbformat_minor": 2 }