Courses/Mathesis/Intro2ProgrammingWithJava/Week5/5.4-Sets/5.4-Sets.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "31023c3d-e021-4562-9345-6046b29c4ff1",
   "metadata": {},
   "source": [
    "# 5.4 Σύνολα (Sets)\n",
    "© Γιάννης Κωστάρας\n",
    "\n",
    "---\n",
    "\n",
    "[<](../5.3-Generics/5.3-Generics.ipynb) | [Δ](../../TOC.ipynb) |  [>](../5.5-Queues/5.5-Queues.ipynb) \n",
    " \n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1fb5a509-fba1-4bca-97ff-8d21885c66ed",
   "metadata": {},
   "source": [
    "Τα σύνολα (sets) αποθηκεύουν μόνο μοναδικά στοιχεία, δηλ. δεν επιτρέπουν διπλότυπα.\n",
    "\n",
    "![](assets/Fig1.png)\n",
    "\n",
    "**Εικόνα 5.4.1** _Σύνολα στη Java_\n",
    "\n",
    "Το _Συσχετισμένο Σύνολο (HashSet)_ είναι η πιο συνηθισμένη υλοποίηση ενός συνόλου. Όπως συνάγεται και από το όνομά του, υλοποιείται ως ένα πίνακας κατακερματισμού (HashMap)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d9db4a51-decf-4d90-8e7e-1524a39f9aab",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 10]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Set<Integer> set = new HashSet<>();\n",
    "set.add(10);\n",
    "set.add(20);\n",
    "set.add(20);\n",
    "set"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35dccdeb-843d-40ee-9792-af900afe9305",
   "metadata": {},
   "source": [
    "Στο πιο πάνω παράδειγμα, βλέπουμε ότι η εισαγωγή της τιμής ```20``` δυο φορές αποτυγχάνει. Παρατηρήστε επίσης ότι τα σύνολα δεν αποθηκεύουν τα στοιχεία τους με κάποια συγκεκριμένη σειρά, όπως οι λίστες, όπου η σειρά των στοιχείων είναι ίδια με τη σειρά εισαγωγής των στοιχείων στη λίστα.\n",
    "\n",
    "Θα μπορούσαμε ν' αρχικοποιήσουμε το σύνολο και ως εξής:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "39c88216-4da8-4f77-9b50-a904f3c61c56",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 10, 30]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Set<Integer> set = Set.of(10, 20, 30);\n",
    "set"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f31f5a65-2a57-4107-bb3f-4f40944dabaa",
   "metadata": {},
   "source": [
    "Προσοχή όμως. Σ' αυτήν την περίπτωση επιστρέφεται ένα σύνολο το οποίο _δεν_ μπορεί να μεταβληθεί. Επιπλέον, δεν επιτρέπονται ```null``` στοιχεία."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e4cc155b-cb79-42fe-85d6-ffad8ccfbe39",
   "metadata": {},
   "outputs": [
    {
     "ename": "EvalException",
     "evalue": "null",
     "output_type": "error",
     "traceback": [
      "\u001b[1m\u001b[31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1m\u001b[31mjava.lang.UnsupportedOperationException: null\u001b[0m",
      "\u001b[1m\u001b[31m\tat java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:142)\u001b[0m",
      "\u001b[1m\u001b[31m\tat java.base/java.util.ImmutableCollections$AbstractImmutableCollection.add(ImmutableCollections.java:147)\u001b[0m",
      "\u001b[1m\u001b[31m\tat .(#18:1)\u001b[0m"
     ]
    }
   ],
   "source": [
    "set.add(40);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "527b2558-d685-428f-ad40-9447f4f59e0e",
   "metadata": {},
   "source": [
    "Για να μπορέσουμε να δημιουργήσουμε μια μεταβαλλόμενη λίστα σ' αυτή την περίπτωση, πρέπει να χρησιμοποιήσουμε την μέθοδο κατασκευής της ```HashSet``` που δέχεται μια άλλη συλλογή:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "59dc7aef-52af-446d-9683-7ab3837c4985",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 10, 30]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Set<Integer> set = new HashSet<>(Set.of(10, 20, 30));\n",
    "set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "4bd7a70a-8bdb-4b05-abef-90bbae45e6f0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set.add(40)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "ce0305e3-94e3-4a3f-9b38-e2ba5e0221f5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 40, 10, 30]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba0cf688-ab52-4b98-91bf-4cabd871a032",
   "metadata": {},
   "source": [
    "Στη συνέχεια θα δούμε τις διάφορες μεθόδους της κλάσης.\n",
    "\n",
    "### Προσπέλαση στοιχείων\n",
    "Παρακάτω βλέπουμε τρόπους προσπέλασης των στοιχείων ενός συνόλου. Καθώς τα στοιχεία ενός συνόλου δεν αποθηκεύονται με τη σειρά, δε μπορούμε να προσπελάσουμε κάποιο στοιχείο του συνόλου χρησιμοποιώντας δείκτες (indexes), καθώς δεν υπάρχουν δείκτες.\n",
    "\n",
    "Για να προσπελάσουμε όλα τα στοιχεία ενός συνόλου, χρησιμοποιούμε τον επαναλήπτη (iterator):\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "e2b39ed3-60c2-4987-887e-4e005734e866",
   "metadata": {},
   "outputs": [],
   "source": [
    "int sum = 0;\n",
    "Iterator<Integer> iter = set.iterator();\n",
    "while (iter.hasNext()) \n",
    "    sum += iter.next();"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f3b08fd-7450-486d-9b86-2e682df2f4d5",
   "metadata": {},
   "source": [
    "Η διεπαφή ```Collection```, την οποία επεκτείνει η ```Set```, επεκτείνει με τη σειρά της τη διεπαφή ```Iterable```:\n",
    "```java\n",
    "interface Iterable {\n",
    "\tpublic Iterator iterator();\n",
    "}\n",
    "\n",
    "interface Iterator {\n",
    "\tpublic boolean hasNext();\n",
    "\tpublic Object next();\n",
    "\tpublic void remove();\n",
    "}\n",
    "```\n",
    "Άλλος τρόπος είναι με τον αναβαθμισμένο βρόγχο ```for``` που εισήχθηκε στην έκδοση 5:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "cf3a4619-e056-462b-9067-c3c192a77b11",
   "metadata": {},
   "outputs": [],
   "source": [
    "sum = 0;\n",
    "for (int n : set) \n",
    "    sum += n;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc812af8-a921-4170-a980-4f9b0246919b",
   "metadata": {},
   "source": [
    "### Εισαγωγή στοιχείων\n",
    "Όπως είδαμε, η εισαγωγή δεδομένων σ' ένα σύνολο γίνεται με την μέθοδο ```add()```. Η μέθοδος επιστρέφει ```true``` αν η εισαγωγή του στοιχείου ήταν επιτυχής, αλλοιώς επιστρέφει ```false```. \n",
    "\n",
    "Η μέθοδος ```addAll(Collection<?> c)``` μας επιτρέπει να προσθέσουμε μια συλλογή από στοιχεία στο σύνολό μας.\n",
    "\n",
    "### Διαγραφή στοιχείων\n",
    "Η μέθοδος ```remove(Object o)``` διαγράφει το στοιχείο του συνόλου που είναι ίσο με το το ```ο``` αν βρέθηκε και επιστρέφει ```true``` σ' αυτήν την περίπτωση. Προσοχή γιατί κι εδώ η μέθοδος **δεν** είναι ```remove(E e)``` όπως θα έπρεπε που σημαίνει ότι σε συνδυασμό με Autoboxing μπορεί να διαγράψει λάθος στοιχεία. \n",
    "\n",
    "Επίσης, πολύ μεγάλη προσοχή χρειάζεται αν διαγράφετε στοιχεία από ένα σύνολο ενώ προσπελάζετε τα στοιχεία του καθώς μπορεί να προκαλέσετε ```ConcurrentModificationException```. Ένας ασφαλής τρόπος είναι να καλέσετε την μέθοδο ```remove()``` του ```Iterator```."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "6c8e3640-3227-4ee0-8f52-b44a11f3081a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 40, 10, 30]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "4c9213f4-ee8c-49b4-aad8-386774511502",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 40, 30]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for (Iterator<Integer> i = set.iterator(); i.hasNext(); ) {\n",
    "    int n = i.next(); \n",
    "    if (n == 10) i.remove();\n",
    "}\n",
    "set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "5b28beef-6660-47fe-a682-1d6fb0937258",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 40]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for (int n : set) {\n",
    "    if (n == 30) set.remove(n) ;\n",
    "}\n",
    "set"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "681121f3-1739-4025-98f5-e3e878e220aa",
   "metadata": {},
   "source": [
    "Τέλος, η διεπαφή ```Collection``` παρέχει και τις ακόλουθες δυο μεθόδους οι οποίες μπορούν να διαγράψουν με τη μία από το σύνολό μας όλα τα στοιχεία της παρεχόμενης συλλογής ```c``` (```removeAll(Collection<?> c)```) και επιστρέφει ```true``` αν τα κατάφερε (αν δεν κατάφερε να διαγράψει έστω και ένα από τα στοιχεία της ```c``` από το σύνολό μας, τότε επιστρέφει ```false```).\n",
    "\n",
    "Η ```retainAll(Collection<?> c)``` κρατάει από το σύνολό μας μόνο τα στοιχεία που περιέχονται στη ```c``` και διαγράφει όλα τα υπόλοιπα. \n",
    "\n",
    "Η ```NavigableSet``` διαθέτει δυο ακόμα μεθόδους που διαγράφουν το πρώτο και το τελευταίο στοιχείο του ταξινομημένου συνόλου: ```pollFirst()``` και ```pollLast()```."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b874859-2264-4e60-9d1a-254b8573a1a5",
   "metadata": {},
   "source": [
    "### Αναζήτηση στοιχείων\n",
    "Δυστυχώς η κλάση ```Collections``` δε διαθέτει κάποια μέθοδο για να αναζητήσει κάποιο στοιχείο σε ένα σύνολο (οι μέθοδοι ```binarySearch()``` δέχονται ως όρισμα λίστα)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "e906fa34-4182-42b2-9945-9a01a150e79e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 40]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "e2c9557f-33ce-4f0f-ac40-df570383e70b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set.contains(20); "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72b3e0fd-44a5-4106-bdae-49d872263cdc",
   "metadata": {},
   "source": [
    "Οπότε, μπορούμε να εφαρμόσουμε μόνο γραμμική αναζήτηση (η οποία αφήνεται ως άσκηση στον αναγνώστη).\n",
    "\n",
    "### Ταξινόμηση \n",
    "Όπως είδαμε παραπάνω, η δομή δεδομένων _Σύνολο_ δεν είναι ταξινομημένη και δεν μπορεί να ταξινομηθεί. Υπάρχει όμως η ```TreeSet``` (η οποία κληρονομεί από τις ```SortedSet``` και ```NavigableSet```) και  ταξινομεί τα στοιχεία της:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "d65255e0-b2dc-4fe7-a894-b06574c56ba8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 20, 30, 40]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set = new HashSet<>(Set.of(20, 10, 40, 30));\n",
    "TreeSet<Integer> sortedSet = new TreeSet<>(set);\n",
    "sortedSet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "91d81ec9-41e2-4886-8f67-114271fc59fe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.first();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "a2b58f3e-96e8-4a51-842f-afeb330494cf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.last();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "60b13a5a-2a0b-46cb-8b72-606802eb8390",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 30]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.subSet(20,40);\t// 20 <= στοιχεία < 40 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "e13bdcf8-61e8-4407-85a4-aefb66395be3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 30, 40]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.subSet(20, true, 40, true);  // inclusive = true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "b3e669ca-ade3-408d-9446-9157166356a7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.headSet(20);\t   // στοιχεία < 20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "e04e02f1-1560-44f8-a517-8e27f7efcb72",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 20]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.headSet(20, true);\t// inclusive = true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "8a76c2c8-69ca-4338-bcfc-9e4ad9fd1987",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[20, 30, 40]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.tailSet(20);\t\t\t// στοιχεία >= 20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "4e5a832c-ee89-4649-ae60-b07758363a53",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[30, 40]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.tailSet(20, false);\t// inclusive = false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "146a706a-cff2-47e0-b74f-7fb4f3a9f7a4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[30, 40]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.tailSet(25);\t\t// στοιχεία >= 25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "867c0dfa-7303-4cf9-b985-b1369e7d19fb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[30, 40]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.tailSet(25, true);\t// inclusive = true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "526f1759-4200-4025-aa0c-5d303b99f1d4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.ceiling(25);\t\t// το μικρότερο στοιχείο >= 25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "97dbda96-e776-4262-a9e2-4018a63d9be6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.floor(25);\t\t// το μεγαλύτερο στοιχείο <= 25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "d35065f5-fc55-4ab0-a927-a5ee3f820707",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.higher(20);\t\t// το μικρότερο στοιχείο > 20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "71100a97-1edf-40bc-91e0-4268d5da0058",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.lower(20);\t\t// το μεγαλύτερο στοιχείο < 20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "af84a44b-9f75-4168-9bb1-0788fff35ad2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[40, 30, 20, 10]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSet.descendingSet();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "dc802f0f-27a7-481d-ad15-26f004d0c4ef",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "40 30 20 10 "
     ]
    }
   ],
   "source": [
    "Iterator<Integer> i = sortedSet.descendingIterator();\n",
    "while (i.hasNext()) \n",
    "    System.out.print(i.next() + \" \");"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b5ab965-80e8-4681-936c-8196d8b60cc2",
   "metadata": {},
   "source": [
    "### Αντιγραφή \n",
    "Ήδη είδαμε τον copy constructor ```HashSet(Collection<?> c)``` που δημιουργεί ένα νέο ```HashSet``` από τη συλλογή που του περνάμε ως όρισμα και την ```addAll(Collection<?> c)```. Υπάρχει επίσης και η στατική μέθοδος ```copyOf(Collection<? extends E> c)```.\n",
    "\n",
    "### Συγχώνευση \n",
    "Σαν άσκηση, γράψτε μια μέθοδο ```union()``` στο jshell που θα ενώνει τα στοιχεία δυο συνόλων που περνάτε ως ορίσματα στη μέθοδο.\n",
    "\n",
    "### Διαχωρισμός \n",
    "Σαν άσκηση, γράψτε μια μέθοδο ```split()``` στο jshell που θα διαχωρίζει ένα σύνολο με ακέραια στοιχεία σε δυο νέα σύνολα που το ένα θα αποθηκεύει τα ζυγά και η άλλη τα μονά στοιχεία του αρχικού συνόλου."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28d44bab-346e-40a4-bbd4-976bfd73b015",
   "metadata": {},
   "source": [
    "### Ισότητα"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "7aaf1c4d-dfbc-4f19-a1bb-e7076cd91743",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Set src = new HashSet<>(Set.of(1, 2, 3, 4, 5));\n",
    "src"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "1d7b84d1-e4b1-4574-a029-e8ef3a5f850e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Set dest = new HashSet<>(Set.of(1, 2, 3, 4, 5));\n",
    "dest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "c5ac22fb-e0de-4f2c-8fce-7cf09090ee82",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dest.equals(src); "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d24d500-ed9e-4b64-b180-3f1f94319366",
   "metadata": {},
   "source": [
    "## Συνδεδεμένα Συσχετισμένα Σύνολα (```LinkedHashSet```)\n",
    "Το Συνδεδεμένο Συσχετισμένο Σύνολο (```LinkedHashSet```) κληρονομεί από την κλάση ```HashSet``` αλλά επιπλέον διατηρεί και μια συνδεδεμένη λίστα (```LinkedList```) με τα στοιχεία του που βελτιώνει την απόδοσή του σε σχέση με το HashSet αν θέλετε να προσπελάσετε όλα τα στοιχεία του. Με αυτόν τον τρόπο οι επαναλήπτες της (iterators) επιστρέφουν τα στοιχεία της με τη σειρά που εισήχθηκαν (θυμηθείτε ότι στην κλάση ```HashSet``` δεν υπάρχει κάποια σειρά στα στοιχεία).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "59ec728c-bc73-4db7-9cab-4e864d78366f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Set<Character> characterSet = new LinkedHashSet<>();\n",
    "Collections.addAll(characterSet, 'z', 'y', 'x');\n",
    "characterSet.toString().equals(\"[z, y, x]\");"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "111b6431-885d-4636-ba30-0e39e189eba5",
   "metadata": {},
   "source": [
    "Οι πράξεις στα συνδεδεμένα συσχετισμένα σύνολα είναι ίδιες με αυτές των συσχετισμένων συνόλων (```HashSet```s).\n",
    "\n",
    "## Σύνολα Απαριθμημένων Τύπων (```EnumSet```)\n",
    "Χρησιμοποιείται όταν ο αριθμός των στοιχείων είναι γνωστός εξ' αρχής και δεν αλλάζει και μπορούμε να αναθέσουμε ένα ευρετήριο (index) σ' αυτά. Ως αποτέλεσμα, είναι πολύ πιο αποδοτικό από τις υπόλοιπες υλοποιήσεις. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "753f1a76-0e27-4b2b-9744-af69c68ee5f3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[JACK, QUEEN, KING]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enum Faces {JACK, QUEEN, KING};\n",
    "Set<Faces> faceCards = EnumSet.of(Faces.JACK, Faces.QUEEN, Faces.KING);\n",
    "Set<Faces> faceCards = EnumSet.allOf(Faces.class);\n",
    "faceCards"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2fcbfac5-3c9d-41d4-bb20-d9aca0da7045",
   "metadata": {},
   "source": [
    "Επιστρέφει τα στοιχεία του με τη σειρά που ορίζονται στο ```enum```.\n",
    "\n",
    "Μπορείτε να πειραματιστείτε περαιτέρω εδώ <a href=\"sandbox/set.html\" target=\"_blank\"><img src=\"../../../assets/javaalmanac.svg\" alt=\"javaalmanac.io\" style=\"width:5%; height:5%;\"></a>.\n",
    "\n",
    "## Σύγκριση των διαφόρων υλοποιήσεων της ```Set```\n",
    "\n",
    "| | ```add``` |  ```contains``` | ```next``` |\n",
    "|---|---|---|---|\n",
    "| ```HashSet```  | O(1) | O(n) | O(k*/n) |  \n",
    "| ```LinkedHashSet``` | O(1) | O(1) | O(1) | \n",
    "| ```EnumSet``` | O(1) | O(n) | O(1)** | \n",
    "| ```TreeSet``` | O(logn) | O(logn) | O(logn) | \n",
    "\n",
    "*k είναι η χωρητικότητα του συνόλου\n",
    "\n",
    "** για ```EnumSet```s μέχρι 64 στοιχείων, μετά γίνεται O(logn)\n",
    "\n",
    "_Πηγή: [Naftalin, Wadler (2006)](https://www.amazon.com/-/en/Maurice-Naftalin/dp/0596527756)_\n",
    "\n",
    "Αν η εφαρμογή σας διαβάζει συχνότερα στοιχεία τότε καλύτερη απόδοση έχει η ```LinkedHashSet```.\n",
    "\n",
    "|![]()|![]()|![]()|![]()|\n",
    "|---|---|---|---|\n",
    "| Ιδιότητα | ```HashSet``` |  ```LinkedHashSet``` | ```TreeSet``` | \n",
    "| Δομή δεδομένων | \t```Hashtable``` | ```Hashtable```+```LinkedList``` | Ισοζυγισμένο (red-black) δέντρο  |  \n",
    "| Σειρά εισαγωγής | Δε διατηρείται | Διατηρείται | Δε διατηρείται | \n",
    "| Διπλότυπα αντικείμενα | Δεν επιτρέπονται | Δεν επιτρέπονται | Δεν επιτρέπονται | \n",
    "| Δυνατότητα ταξινόμησης | Όχι | Όχι | Ναι |\n",
    "| Ετερογενή αντικείμενα | Ναι | Ναι | Όχι |\n",
    "| ```null``` στοιχεία | Ναι | Ναι | Όχι, μόνο ως πρώτη εισαγωγή, δηλ. ως ρίζα του δέντρου | \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f87db625-d819-4a8e-8380-80d88dfbb0a1",
   "metadata": {},
   "source": [
    "## Ασκήσεις\n",
    "1. [Γράψτε ένα πρόγραμμα που θα εισάγει ακέραιους αριθμούς σε ένα ```TreeSet``` με φθίνουσα ταξινόμηση.](https://codecheck.io/files/240624201627o5ut847srxt1sj2s2q0fe5i)\n",
    "2. [Γράψτε ένα πρόγραμμα που θα εισάγει συμβολοσειρές σε ένα ```TreeSet``` ταξινομημένες ως προς το μήκος τους. Αν δυο συμβολοσειρές έχουν ίδιο μήκος τότε θα πρέπει να ληφθεί υπόψιν η λεξικογραφική σειρά των χαρακτήρων.](https://codecheck.io/files/24063020253yfuywknhq1mmcwdtly0ukj30)\n",
    "3. [Γράψτε μια μέθοδο που θα δέχεται μια ```List``` ως παράμετρο και θα επιστρέφει μια νέα ```List``` εξαφανίζοντας τα διπλότυπα στοιχεία της αρχικής. Π.χ. αν η αρχική λίστα περιέχει [\"ένα\", \"δυο\", \"δυο\", \"τρία\", \"τρία\", \"τρία\"] η μέθοδος θα επιστρέφει: [\"ένα\", \"δυο\", \"τρία\"].](https://codecheck.io/files/2407042051d2oj6vb2wpeo4tn75gp04lx5j)\n",
    "4. Υλοποιήστε μια νέα κλάση ```ListSet<E>```. Η ```ListSet<E>``` είναι μια ```List<E>``` που όμως δεν επιτρέπει διπλότυπες τιμές. Η υλοποίησή σας θα πρέπει να είναι αντίστοιχη της [SetUniqueList&lt;E&gt;](https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/list/SetUniqueList.html).\n",
    "5. [Ο μαθηματικός όρος _συμμετρική διαφορά_ (△ ή ⊕) δυο συνόλων είναι το σύνολο εκείνων των στοιχείων που είναι είτε στο ένα σύνολο είτε στο άλλο αλλά όχι και στα δυο. Π.χ. έστω τα σύνολα A = {1, 2, 3} και B = {2, 3, 4}, τότε A △ B = {1, 4}. Αν θέλουμε να υπολογίσουμε την συμμετρική διαφορά παραπάνω των δυο συνόλων τότε θα πρέπει να την υπολογίσουμε για τα πρώτα δυο και το αποτέλεσμα με το τρίτο κ.ο.κ. Δηλ. (A △ B △ C) == ((A △ B) △ C)). Π.χ. για τα σύνολα A και B που είδαμε παραπάνω και Γ = {2, 3}, A △ B △ Γ = (A △ B) △ Γ = {1, 4} △ {2, 3} = {1, 2, 3, 4}. Δημιουργήστε μια μέθοδο που θα δέχεται δυο ή περισσότερα σύνολα και θα επιστρέφει ένα σύνολο με την συμμετρική διαφορά τους.](https://codecheck.io/files/24070421103plfd9m4533vu71slpxbknnfq)\n",
    "\n",
    "---\n",
    "\n",
    "[<](../5.3-Generics/5.3-Generics.ipynb) | [Δ](../../TOC.ipynb) |  [>](../5.5-Queues/5.5-Queues.ipynb)\n",
    "\n",
    "---"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "17+35-LTS-2724"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}