Sachverhalt:
A.
A._ stammt eigenen Angaben zufolge aus Algerien. Im März 2013 stellte er in der Schweiz ein Asylgesuch. Darauf trat das Bundesamt für Migration (BFM; heute: Staatssekretariat für Migration [SEM]) mit Verfügung vom 18. Juli 2013 nicht ein. Der daraufhin ergangenen Wegweisungsanordnung leistete A._ keine Folge; stattdessen wurde er in der Schweiz straffällig und erwirkte unter anderem wegen gewerbs- und bandenmässigen Diebstahls, Hausfriedensbruchs, rechtswidriger Einreise und rechtswidrigen Aufenthalts mehrere Haftstrafen. Kurz vor Beendigung des Strafvollzugs verfügte das Migrationsamt des Kantons Basel-Stadt (nachfolgend: Migrationsamt) am 7. Dezember 2018 eine dreimonatige Ausschaffungshaft. Die Einzelrichterin des Appellationsgerichts Basel-Stadt für Zwangsmassnahmen im Ausländerrecht (nachfolgend: die Einzelrichterin) bestätigte die angeordnete Ausschaffungshaft mit Urteil vom 10. Dezember 2018, beschränkte die Haftdauer indes auf einen Monat.
B.
B.a. Mit Verfügung vom 3. Januar 2019 hob das Migrationsamt die Ausschaffungshaft auf und verfügte stattdessen eine Durchsetzungshaft von einem Monat. Mit Urteil vom 7. Januar 2019 bestätigte die Einzelrichterin diese Durchsetzungshaft. Mit Verfügung vom 30. Januar 2019 stimmte die Einzelrichterin auch der vom Migrationsamt verfügten Verlängerung der Durchsetzungshaft bis zum 2. April 2019 zu; ihre Zustimmung hielt sie auch nach einer im Beisein des amtlichen Rechtsbeistands durchgeführten Gerichtsverhandlung aufrecht. Ein weiteres Mal verlängerte das Migrationsamt mit Verfügung vom 21. März 2019 die Durchsetzungshaft um zwei Monate. Auch diese Verlängerung wurde von der Einzelrichterin mit Verfügung vom 29. März 2019 beziehungsweise mit dem nach mündlicher Verhandlung ergangenen Urteil vom 8. April 2019 geschützt.
B.b. Zuletzt verlängerte das Migrationsamt die Ausschaffungshaft mit Verfügung vom 23. Mai 2019 um weitere zwei Monate. Mit Verfügung vom 29. Mai 2019 schützte die Einzelrichterin auch diesen Entscheid. A._ verlangte in der Folge eine mündliche Verhandlung unter Beigabe eines unentgeltlichen Rechtsbeistands in der Person eines namentlich benannten Rechtsanwalts. Mit Verfügung vom 3. Juni 2019 setzte die Einzelrichterin auf den 5. Juni 2019 eine Verhandlung an, wies das Gesuch um Beiordnung eines unentgeltlichen Rechtsbeistands hingegen ab. Nach Durchführung der Verhandlung am 5. Juni 2019 stellte die Einzelrichterin mit gleichentags ergangenem Urteil fest, die Verlängerung der Durchsetzungshaft über A._ sei bis zum 2. August 2019 rechtmässig und angemessen.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 1. Juli 2019 gelangt A._ an das Bundesgericht und beantragt die Aufhebung des Urteils der Einzelrichterin des Appellationsgerichts Basel-Stadt vom 5. Juni 2019 und die Anweisung an das Migrationsamt, ihn aus der Durchsetzungshaft zu entlassen und umgehend auf freien Fuss zu setzen; weiter sei festzustellen, dass er in seinen Rechten aus Art. 6 Abs. 2 lit. c EMRK sowie <ref-law> verletzt sei.
Mit Präsidialverfügung vom 3. Juli 2019 verzichtet das Bundesgericht antragsgemäss auf die Erhebung eines Kostenvorschusses.
Das Migrationsamt und die Einzelrichterin des Appellationsgerichts beantragen die Abweisung der Beschwerde. Das SEM verzichtet auf Vernehmlassung. A._ repliziert.

Erwägungen:
1.
1.1. Gegen letztinstanzliche kantonale Entscheide betreffend Zwangsmassnahmen im Ausländerrecht steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen (Art. 82 lit. a, Art. 83 lit. c e contrario, Art. 86 Abs. 1 lit. d und Abs. 2 sowie Art. 90 BGG). Der Beschwerdeführer ist gemäss <ref-law> zur Beschwerde in öffentlich-rechtlichen Angelegenheiten legitimiert, weshalb auf das frist- und formgerecht eingereichte Rechtsmittel grundsätzlich einzutreten ist (Art. 100 Abs. 1 und Art. 42 Abs. 1 und 2 BGG).
1.2. Der Beschwerdeführer beantragt die Feststellung einer Verletzung von Art. 6 Abs. 2 lit. c EMRK und <ref-law>. Feststellungsbegehren sind im bundesgerichtlichen Verfahren indes nur dann zulässig, wenn an der Feststellung ein schutzwürdiges Interesse besteht und dieses Interesse nicht ebenso gut mit einem Leistungsbegehren gewahrt werden kan (vgl. <ref-ruling> E. 2c S. 303; Urteile 2C_364+425/2015 vom 3. Februar 2017 E. 2.4, nicht publ. in: <ref-ruling>; 2C_497/2017 vom 5. März 2018 E. 1). Der Beschwerdeführer macht nicht geltend, dass er an der beantragten Feststellung ein Interesse hätte, das über die ebenfalls beantragte Entlassung aus der Durchsetzungshaft hinausginge; ein solches Interesse ist auch nicht erkennbar. Aufgrund der Subsidiarität von Feststellungsbegehren ist auf den genannten Feststellungsantrag nicht einzutreten.
2.
Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), prüft jedoch unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG) nur die geltend gemachten Rechtsverletzungen, sofern rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.5 S. 144). In Bezug auf die Verletzung von Grundrechten gilt eine qualifizierte Rüge- und Substanziierungspflicht (<ref-law>; <ref-ruling> E. 2.2 S. 232; <ref-ruling> E. 2.5 S. 314).
Seinem Urteil legt das Bundesgericht den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Eine Berichtigung oder Ergänzung der vorinstanzlichen Sachverhaltsfeststellungen ist von Amtes wegen (<ref-law>) oder auf Rüge hin (<ref-law>) möglich. Von den tatsächlichen Grundlagen des vorinstanzlichen Urteils weicht das Bundesgericht jedoch nur ab, wenn diese offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen und die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (<ref-law>; <ref-ruling> E. 1.6 S. 144 f.).
3.
Der Beschwerdeführer macht geltend, die Verlängerung der Durchsetzungshaft sei unrechtmässig erfolgt.
3.1. Die Durchsetzungshaft bildet das letzte Mittel, wenn und soweit keine andere Massnahme (mehr) zum Ziel führt, einen illegal anwesenden Ausländer auch gegen seinen Willen in seine Heimat verbringen zu können. Sie setzt voraus, dass ein rechtskräftiger Weg- oder Ausweisungsentscheid vorliegt, der Betroffene diesem nicht rechtzeitig freiwillig nachgekommen ist und der zwangsweise Vollzug der Weg- oder Ausweisung bzw. der Landesverweisung an einem ihm vorwerfbaren Verhalten scheitert. Zudem darf die Ausschaffungshaft nicht mehr zulässig sein und kein milderes Mittel zur Verfügung stehen, um den Haftzweck zu erreichen (Festhaltung zur Sicherung der Ausschaffung bzw. Durchsetzung der Ausreisepflicht, soweit diese von der Mitwirkung des Betroffenen abhängt; vgl. <ref-law> [SR 142.20]). Der mit der Durchsetzungshaft verbundene Freiheitsentzug steht im Einklang mit Art. 5 Ziff. 1 lit. f EMRK (Haft zur Sicherung eines schwebenden Ausweisungsverfahrens) und dient in diesem Rahmen der Durchsetzung einer durch das Gesetz vorgeschriebenen Verpflichtung des Betroffenen (Art. 5 Ziff. 1 lit. b EMRK; vgl. <ref-ruling> E. 2.3.1).
3.2. Wie jedes staatliche Handeln muss die Durchsetzungshaft verhältnismässig sein. Innerhalb der Höchstdauer von 18 Monaten (vgl. <ref-law>) ist jeweils aufgrund der Umstände des Einzelfalles zu prüfen, ob die ausländerrechtliche Festhaltung insgesamt noch geeignet bzw. erforderlich erscheint und nicht gegen das Übermassverbot verstösst (<ref-ruling> E. 2.1 S. 411; <ref-ruling> E. 2.2.1 S. 107; <ref-ruling> E. 2.3.1 und 2.3.2 S. 96 f.; <ref-ruling> E. 2.2 S. 99 f.). Neben dem Verhalten der betroffenen Person bildet ihr erklärtes, konsequent unkooperatives Verhalten diesbezüglich nur einen - allenfalls aber gewichtigen - Gesichtspunkt unter anderen (vgl. Urteil 2C_1038/2018 vom 7. Dezember 2018 E. 2.3).
3.3. Der Beschwerdeführer macht sinngemäss geltend, die Verlängerung der Durchsetzungshaft sei unverhältnismässig, weil feststehe, dass er zur Feststellung seiner Identität auch weiterhin nicht mit den Behörden zusammenarbeiten werde.
Sein Einwand verfängt nicht. Die unter dem Gesichtspunkt der Verhältnismässigkeit erforderliche Eignung der Durchsetzungshaft ist nach der Rechtsprechung schon dann gegeben, wenn eine minimale Wahrscheinlichkeit dafür besteht, dass der renitente Ausländer dadurch sein Verhalten überdenkt und zur Durchführung der Wegweisung mit den Behörden kooperiert (vgl. Urteil 2C_441/2011 vom 15. Juni 2011 E. 2.2). Die Vorinstanz hat diesbezüglich festgestellt, die vom Gesetz vorgesehene maximale Haftdauer sei noch längstens nicht ausgeschöpft, und es sei deshalb nicht auszuschliessen, dass die Fortdauer der Inhaftierung den Beschwerdeführer noch zu einem Umdenken bewegen könne. Inwiefern diese Feststellung offensichtlich unrichtig sein soll, legt der Beschwerdeführer nicht dar; der abstrakte Hinweis auf allgemeine Erfahrungswerte genügt nicht, um entgegen der Vorinstanz im Falle des Beschwerdeführers davon auszugehen, die erforderliche minimale Wahrscheinlichkeit einer Verhaltensänderung sei ausgeschlossen.
3.4. Der Beschwerdeführer bestreitet nicht, dass die Voraussetzungen für die Anordnung der Durchsetzungshaft (vgl. E. 3.2 hiervor) im Übrigen erfüllt sind. Die von der Vorinstanz bestätigte Verlängerung der Durchsetzungshaft erweist sich als rechtmässig.
4.
Der Beschwerdeführer beanstandet, ihm sei im vorinstanzlichen Verfahren verweigert worden, einen Rechtsvertreter beizuziehen.
4.1. Der Anspruch auf rechtliches Gehör vermittelt einer Person das Recht, sich in Verwaltungs- und Gerichtsverfahren durch einen Rechtsvertreter ihrer Wahl vertreten zu lassen (<ref-ruling> E. 3.3 S. 445). Mit seinen Vorbringen verkennt der Beschwerdeführer jedoch, dass die Vorinstanz ihm nie den Beizug eines Rechtsvertreters verweigert hat; die Verfügung der Vorinstanz vom 3. Juni 2019 bezieht sich vielmehr auf die Frage, ob ein allfällig beigezogener Rechtsvertreter vom Staat als unentgeltlicher Rechtsbeistand eingesetzt und entsprechend entschädigt würde.
4.2. Eine allfällige Übernahme der Vertretungskosten durch den Staat bestimmt sich nach Massgabe von <ref-law> (vgl. KIENER/ RÜTSCHE/KUHN, Öffentliches Verfahrensrecht, 2. Aufl. 2015, Rz. 246). Diese Bestimmung setzt voraus, dass die Beiordnung des unentgeltlichen Rechtsbeistands zur Wahrung der Rechte der betroffenen Person notwendig ist. In Bezug auf die Durchsetzungshaft geht das Bundesgericht davon aus, dass die Notwendigkeit der Verbeiständung insbesondere für die erste haftrichterliche Verhandlung zu bejahen ist, bei Haftverlängerungen alsdann (nur) noch bei besonderen Schwierigkeiten rechtlicher oder tatsächlicher Natur (<ref-ruling> E. 4.1 S. 101 f.).
Was den vorliegenden Fall betrifft, hat die Vorinstanz unter Zugrundelegung dieser Massstäbe nachvollziehbar festgestellt, der Sachverhalt sei nicht komplex und habe sich - soweit aus den Akten ersichtlich - seit der letzten Beurteilung der Angelegenheit nicht verändert; entsprechend sei die Beiordnung eines unentgeltlichen Rechtsbeistands (anders als noch bei der Verhandlung vom 7. Februar 2019) nicht notwendig. Der Beschwerdeführer bringt nichts vor, was diese Feststellung in Frage stellen könnte; seine Ausführungen, wonach es im Zusammenhang mit der Durchsetzungshaft "[k]eine einzige gut verständliche Bestimmung" gebe, zielen an der Sache vorbei, nachdem aus den verschiedenen Entscheiden zur Anordnung bzw. Verlängerung der Durchsetzungshaft klar hervorgeht, was diesbezüglich vorausgesetzt wird, und sich der Sachverhalt seit der erstmaligen Anordnung der Durchsetzungshaft nicht massgeblich geändert hat (vgl. auch Urteil 2C_724/2016 vom 21. Dezember 2016 E. 2.2 und 2.3). Auch bezüglich des Anspruchs auf Beziehung eines Rechtsbeistands verletzt der angefochtene Entscheid deshalb Bundesrecht nicht.
5.
Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf einzutreten ist.
Bei diesem Verfahrensausgang wären die Gerichtskosten dem unterliegenden Beschwerdeführer aufzuerlegen (<ref-law>). Umständehalber ist auf die Erhebung von Gerichtskosten jedoch zu verzichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2.
Es werden keine Kosten erhoben.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht, Einzelrichterin für Zwangsmassnahmen im Ausländerrecht, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 19. Juli 2019
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Brunner