Sachverhalt:
Sachverhalt:
A. X._ wurde am 15. Oktober 2004 von der Kantonspolizei Appenzell A.Rh. festgenommen und dem Verhörrichter des Kantons Appenzell A.Rh. zugeführt; dieser eröffnete gegen ihn ein Strafverfahren und nahm ihn am gleichen Tag in Untersuchungshaft. Vorgeworfen wurden ihm - wenn auch nicht ausdrücklich - Drohung (Art. 180 Abs. 1 StGB) und Vorbereitungshandlungen zu vorsätzlicher Tötung bzw. Mord (Art. 260bis Abs. 1 StGB).
Die Anzeige war vom Sozialpsychiatrischen Dienst des Psychiatrischen Zentrums in Herisau erstattet worden. Danach soll der Beschuldigte in zwei Therapiegesprächen konkrete Gewaltdrohungen gegen eine Drittperson geäussert haben, die er für den Tod seines Vaters im Jahre 1989 verantwortlich machte; gefährdet sei nach der Anzeige allenfalls auch die Therapeutin selbst, die den angeblichen Gesprächsinhalt weitergab. Der Verhörrichter erachtete die Bedrohungslage insbesondere vor dem Hintergrund der geplanten Ausschaffung des Verhafteten nach der rechtskräftigen Abweisung seines Asylgesuchs als ernsthaft. Der Beschuldigte bestritt die ihm zur Last gelegten Äusserungen wie auch das Bestehen von Racheplänen.
Im Haftprüfungsverfahren bestätigte der Präsident des Kantonsgerichts von Appenzell A.Rh. die Untersuchungshaft mit Entscheid vom 19. Oktober 2004. Er nahm einen dringenden Tatverdacht im Hinblick auf Art. 260bis StGB an. Ausserdem bejahte er den im kantonalen Verfahrensrecht vorgesehenen besonderen Haftgrund der Ausführungsgefahr. Er verfügte, die Haft falle dahin, wenn nicht innert 20 Tagen um Verlängerung nachgesucht werde.
Im Haftprüfungsverfahren bestätigte der Präsident des Kantonsgerichts von Appenzell A.Rh. die Untersuchungshaft mit Entscheid vom 19. Oktober 2004. Er nahm einen dringenden Tatverdacht im Hinblick auf Art. 260bis StGB an. Ausserdem bejahte er den im kantonalen Verfahrensrecht vorgesehenen besonderen Haftgrund der Ausführungsgefahr. Er verfügte, die Haft falle dahin, wenn nicht innert 20 Tagen um Verlängerung nachgesucht werde.
B. Gegen den Haftprüfungsentscheid erhob X._ am 26. Oktober 2004 staatsrechtliche Beschwerde (Verfahren 1P.618/2004). In der Folge wurde der Vollzug der Ausschaffung aufgeschoben. Ausserdem sah die Drittperson, auf die sich die Drohungen bezogen haben sollen, einstweilen davon ab, einen Strafantrag zu stellen. Der Verhörrichter ging daher vom Wegfall der Voraussetzungen der Untersuchungshaft aus und liess den Beschuldigten am 5. November 2004 frei. X._ zog am 12. November 2004 die staatsrechtliche Beschwerde zurück; das bundesgerichtliche Verfahren wurde am 16. November 2004 als erledigt abgeschrieben.
B. Gegen den Haftprüfungsentscheid erhob X._ am 26. Oktober 2004 staatsrechtliche Beschwerde (Verfahren 1P.618/2004). In der Folge wurde der Vollzug der Ausschaffung aufgeschoben. Ausserdem sah die Drittperson, auf die sich die Drohungen bezogen haben sollen, einstweilen davon ab, einen Strafantrag zu stellen. Der Verhörrichter ging daher vom Wegfall der Voraussetzungen der Untersuchungshaft aus und liess den Beschuldigten am 5. November 2004 frei. X._ zog am 12. November 2004 die staatsrechtliche Beschwerde zurück; das bundesgerichtliche Verfahren wurde am 16. November 2004 als erledigt abgeschrieben.
C. Am 20. Dezember 2004 stellte der Verhörrichter das Strafverfahren ein, auferlegte dem Beschuldigten aber die Untersuchungskosten. Bereits am 22. November 2004 hatte dieser um eine Entschädigung von insgesamt Fr. 10'000.-- "für seine Anwaltskosten und als Genugtuungssumme für nicht nur ungerechtfertigte, sondern illegale Haft von 20 Tagen" ersucht. Der Verhörrichter nahm im Dispositiv der Verfügung keinen Bezug auf diesen Antrag. Er führte jedoch in den Erwägungen aus, die gesetzlichen Voraussetzungen für eine Entschädigung bzw. Genugtuung seien nicht erfüllt.
Die Staatsanwaltschaft des Kantons Appenzell-Ausserrhoden wies den Rekurs von X._ gegen diese Verfügung am 10. Februar 2005 vollumfänglich ab. In der Rekursschrift war unter anderem beantragt worden, vom Verhöramt sei eine angemessene Parteientschädigung sowie eine Genugtuung im Sinne seiner Begehren zuzusprechen. Die Staatsanwaltschaft behandelte diesen Rekursantrag in den Erwägungen; sie erachtete die Verweigerung einer Parteientschädigung und einer Genugtuung für die Untersuchungshaft als rechtmässig.
Die Staatsanwaltschaft des Kantons Appenzell-Ausserrhoden wies den Rekurs von X._ gegen diese Verfügung am 10. Februar 2005 vollumfänglich ab. In der Rekursschrift war unter anderem beantragt worden, vom Verhöramt sei eine angemessene Parteientschädigung sowie eine Genugtuung im Sinne seiner Begehren zuzusprechen. Die Staatsanwaltschaft behandelte diesen Rekursantrag in den Erwägungen; sie erachtete die Verweigerung einer Parteientschädigung und einer Genugtuung für die Untersuchungshaft als rechtmässig.
D. X._ führt staatsrechtliche Beschwerde mit dem Antrag, den Rekursentscheid der Staatsanwaltschaft aufzuheben. Er rügt eine Verletzung seines Anspruchs auf einen verfassungsmässigen Richter (Art. 30 BV) sowie eine willkürliche Tatsachenfeststellung und Anwendung des kantonalen Rechts (Art. 9 BV); gleichzeitig sei gegen Art. 29 und Art. 31 Abs. 1 BV bzw. Art. 5 Ziff. 5 EMRK verstossen worden. Ausserdem stellt er ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung im bundesgerichtlichen Verfahren.
Die Staatsanwaltschaft ersucht um Abweisung der Beschwerde. In der Replik hat der Beschwerdeführer an seinen Anträgen festgehalten.
Die Staatsanwaltschaft ersucht um Abweisung der Beschwerde. In der Replik hat der Beschwerdeführer an seinen Anträgen festgehalten.
E. Mit Formularverfügung vom 23. Mai 2005 hat der Präsident der I. öffentlichrechtlichen Abteilung bis zum Entscheid über das im Nachgang zur Replik gestellte Gesuch um aufschiebende Wirkung superprovisorisch alle Vollziehungsvorkehrungen untersagt.
Das Bundesgericht zieht in Erwägung:
Das Bundesgericht zieht in Erwägung:
1. Angefochten ist ein kantonal letztinstanzlicher Entscheid (Art. 86 Abs. 1 OG). Damit wurde die Verfügung des Verhörrichters bestätigt, dem Beschwerdeführer trotz Einstellung der Strafuntersuchung die Verfahrenskosten aufzuerlegen. Gleichzeitig wurden die Anträge des Beschwerdeführers um Parteientschädigung und Genugtuung für die erlittene Untersuchungshaft beurteilt, auch wenn dies weder im Dispositiv der erstinstanzlichen Verfügung noch des Rekursentscheids in Erscheinung tritt. Der Beschwerdeführer wird durch den angefochtenen Entscheid in rechtlich geschützten Interessen berührt (Art. 84 Abs. 1 lit. a und Art. 88 OG). Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde - unter dem Vorbehalt gehörig begründeter Rügen (Art. 90 Abs. 1 lit. b OG; BGE 130 I 258 E. 1.3 S. 262) - grundsätzlich einzutreten.
1. Angefochten ist ein kantonal letztinstanzlicher Entscheid (Art. 86 Abs. 1 OG). Damit wurde die Verfügung des Verhörrichters bestätigt, dem Beschwerdeführer trotz Einstellung der Strafuntersuchung die Verfahrenskosten aufzuerlegen. Gleichzeitig wurden die Anträge des Beschwerdeführers um Parteientschädigung und Genugtuung für die erlittene Untersuchungshaft beurteilt, auch wenn dies weder im Dispositiv der erstinstanzlichen Verfügung noch des Rekursentscheids in Erscheinung tritt. Der Beschwerdeführer wird durch den angefochtenen Entscheid in rechtlich geschützten Interessen berührt (Art. 84 Abs. 1 lit. a und Art. 88 OG). Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde - unter dem Vorbehalt gehörig begründeter Rügen (Art. 90 Abs. 1 lit. b OG; BGE 130 I 258 E. 1.3 S. 262) - grundsätzlich einzutreten.
2. 2.1 Nach der materiell unverändert von Art. 58 aBV in Art. 30 Abs. 1 BV überführten, ebenfalls in Art. 6 Ziff. 1 EMRK enthaltenen Garantie des verfassungsmässigen Richters hat jede Person, deren Sache in einem gerichtlichen Verfahren beurteilt werden muss, Anspruch auf ein durch Gesetz geschaffenes, zuständiges, unabhängiges und unparteiisches Gericht (BGE 127 I 196 I E. 2b S. 198). Das Bundesgericht hat festgehalten, dass diese Garantie insbesondere auf den Staatsanwalt im Kanton Appenzell A.Rh. anzuwenden ist, wenn dieser über einen Rekurs gegen eine Einstellungsverfügung des Verhöramtes entscheidet (BGE 112 Ia 142 E. 2a S. 143). Weiter gilt nach der Rechtsprechung Art. 6 Ziff. 1 EMRK mit seinen formellen Anforderungen im Verfahren über die Zusprechung einer Entschädigung bzw. Genugtuung für erlittene Untersuchungshaft (BGE 125 I 394 E. 5d S. 402; 119 Ia 221 E. 2b S. 225 f.).
Art. 30 Abs. 1 BV und Art. 6 Ziff. 1 EMRK sollen garantieren, dass keine Umstände, die ausserhalb des Prozesses liegen, in sachwidriger Weise zu Gunsten oder zu Lasten einer Partei auf das Urteil einwirken (BGE 128 V 82 E. 2a S. 84; 124 I 121 E. 3a S. 123; 114 Ia 50 E. 3b S. 54).
2.2 Gemäss Art. 153 i.V.m. Art. 242 und Art. 246 der Strafprozessordnung des Kantons Appenzell A.Rh. vom 30. April 1978 (StPO/AR; bGS 321.1) befindet das Verhöramt im Rahmen der Einstellung des Strafverfahrens über die Auferlegung der Untersuchungskosten an den Beschuldigten und über die Zusprechung bzw. Verweigerung einer Entschädigung. Unter Art. 246 StPO/AR fällt auch die Entschädigung für rechtswidrige bzw. ungerechtfertigte Untersuchungshaft. Der gegen eine derartige Verfügung gerichtete Rekurs des Beschuldigten wird vom Staatsanwalt beurteilt (Art. 204 Ziff. 1 StPO/AR); sein Entscheid ist gegenüber dem Beschuldigten endgültig (Art. 211 StPO/AR). Die Einstellungsverfügung des Verhöramtes muss vor der Eröffnung an den Beschuldigten durch die Staatsanwaltschaft genehmigt werden (Art. 155 und Art. 156 Abs. 2 StPO/AR).
2.3 Der Beschwerdeführer wirft dem angefochtenen Entscheid der Staatsanwaltschaft in doppelter Weise eine Verletzung seines Anspruchs auf einen verfassungsmässigen Richter (Art. 30 Abs. 1 BV) vor: Einerseits fehle eine Überprüfung durch ein Gericht; anderseits sei die Staatsanwaltschaft funktionell bzw. organisatorisch vorbefasst, weil ein stellvertretender Staatsanwalt die Einstellungsverfügung bereits genehmigt habe. Diese Einwände hat der Beschwerdeführer im kantonalen Verfahren noch nicht geäussert.
2.4 Die Rüge, dass der Anspruch auf gerichtliche Beurteilung verletzt sei, muss grundsätzlich bereits im kantonalen Verfahren vorgebracht werden. Andernfalls wird ein Verzicht auf diesen Vorwurf angenommen (BGE 131 I 31 E. 2.1.1 S. 33 f.) Nach der Rechtsprechung gilt dies auch in Fällen, in denen über die Anwendbarkeit von Art. 6 Ziff. 1 EMRK - wie hier - eine gefestigte Praxis besteht, und zwar selbst dann, wenn als letzte kantonale Instanz eine nichtrichterliche Behörde entscheidet und geltend gemacht wird, gegen deren Entscheid sollte eine richterliche Beurteilung möglich sein, die freilich nach der massgeblichen kantonalen Gesetzgebung noch nicht besteht (BGE 123 I 87 E. 2d S. 89; 120 Ia 19 E. 2c/bb S. 25 f.).
Ebenso sind Ablehnungsgründe gegen einen Richter nach Treu und Glauben ohne Verzug geltend zu machen. Wer von einem Ablehnungsgrund Kenntnis erhält und nicht unverzüglich ein Begehren um Ablehnung stellt, sondern sich auf den Prozess einlässt, verwirkt den Anspruch auf die spätere Anrufung der Garantie des unabhängigen Richters (BGE 128 V 82 E. 2b S. 85; 124 I 121 E. 2 S. 123; 119 Ia 221 E. 5a S. 228 f.). Nicht anders verhält es sich, wenn die Namen der an einem Rechtsmittelverfahren Mitwirkenden dem Betroffenen nicht im Voraus persönlich mitgeteilt werden, sondern die dafür in Frage kommenden Personen einer allgemein zugänglichen Quelle, wie etwa dem Staatskalender oder heute dem Internet, entnommen werden können (BGE 117 Ia 322 E. 1c S. 323; Urteil 2P.332/2001 vom 30. April 2002 E. 2).
Es war dem anwaltschaftlich vertretenen Beschwerdeführer ohne weiteres zumutbar, im kantonalen Verfahren eine mangelnde Unabhängigkeit und Unparteilichkeit der Staatsanwaltschaft zu rügen. Unter diesen Umständen ist zu schliessen, dass der Beschwerdeführer nach Treu und Glauben dort auf die Rüge des verfassungsmässigen Richters verzichtet hat.
Es war dem anwaltschaftlich vertretenen Beschwerdeführer ohne weiteres zumutbar, im kantonalen Verfahren eine mangelnde Unabhängigkeit und Unparteilichkeit der Staatsanwaltschaft zu rügen. Unter diesen Umständen ist zu schliessen, dass der Beschwerdeführer nach Treu und Glauben dort auf die Rüge des verfassungsmässigen Richters verzichtet hat.
2.5 2.5.1 Allerdings fragt sich, ob der entsprechende Verzicht des Beschwerdeführers allenfalls unerheblich ist, weil ein besonders schwerer und zentraler Bereich des Anspruchs auf einen unbefangenen und unparteiischen Richter betroffen ist. Die Rechtsprechung schliesst nicht aus, dass ein Verzicht auf die Geltendmachung der aus Art. 30 Abs. 1 BV fliessenden Rechte in Ausnahmefällen in Anlehnung an die Lehre von den unverjährbaren und unverzichtbaren Grundrechten unbeachtlich sein könnte (BGE 118 Ia 209 E. 2 S. 212 ff. und 282 E. 6 S. 292 ff.). Eine derartige Konstellation liegt hier jedoch nicht vor.
2.5.2 Gemäss Art. 211 Abs. 1 StPO/AR amtet der Staatsanwalt im Rekursverfahren in richterlicher Funktion. In dieser Bestimmung wird zwar das rechtlich uneingeschränkte Aufsichts- und Weisungsrecht der Justizdirektion gegenüber der Staatsanwaltschaft (Art. 9 StPO/AR; Art. 1 Abs. 2 und Art. 4 Abs. 1 der Verordnung über die Rechtspflege des Kantons Appenzell A.Rh. vom 15. Juni 1981 [bGS 145.32]) im Rahmen des Rekursverfahrens nicht ausdrücklich ausgeschlossen. Deshalb ist fraglich, ob die Staatsanwaltschaft in dieser richterlichen Funktion über eine hinreichende Weisungsungebundenheit gegenüber der Exekutive verfügt. Die Frage kann aber offen bleiben. Der Anspruch auf Justizgewährleistung wird nicht als unverzichtbar erachtet, wenn die Anwendbarkeit dieser Garantie für den betroffenen Sachbereich nach der Rechtsprechung feststeht (BGE 120 Ia 19 E. 2c/bb S. 25 f.; 118 Ia 209 E. 2d S. 215). Dies ist hier der Fall (E. 2.1, 2.4). Es handelt sich in diesem Sinne nicht um einen besonders schweren oder zentralen Bereich des Grundrechts auf einen verfassungsmässigen Richter.
2.5.3 Ausserdem wird weder geltend gemacht noch ist ersichtlich, dass der mit dem Rekursverfahren betraute leitende Staatsanwalt einen Anschein von Vorbefassung gegenüber der Strafuntersuchung des Verhörrichters bzw. dem Genehmigungsentscheid des stellvertretenden Staatsanwalts erweckt. Im Übrigen genügt Art. 14 Ziff. 3 StPO/AR für die Sicherstellung des Ausstands desjenigen Staatsanwalts, der die Einstellungsverfügung genehmigt hat; der Gehalt dieser Bestimmung ist im Lichte des von den Parteien erwähnten, unveröffentlichten Urteils 1P.431/1995 vom 2. Oktober 1996 zu verstehen. Das Bundesgericht hat damals ausgeschlossen, dass derselbe Staatsanwalt sowohl die Einstellungsverfügung genehmigen als auch für das Rekursverfahren zuständig sein könne (a.a.O., E. 4d und 6). Um einen derartigen Fall geht es hier nicht. Es erübrigt sich deshalb, näher auf die Weisung des Regierungsrats vom 13. Januar 1997 einzugehen, die nach Angaben der Staatsanwaltschaft der Umsetzung der Vorgaben im genannten Urteil dient.
2.6 Aus diesen Gründen ist davon auszugehen, dass der Beschwerdeführer sein Recht auf die Anrufung von Art. 30 Abs. 1 BV mangels entsprechender Rügen im kantonalen Verfahren verwirkt hat. Der vom Beschwerdeführer in diesem Zusammenhang angerufene Art. 31 Abs. 1 BV führt zu keiner andere Betrachtungsweise. Auf diese Vorwürfe ist daher nicht einzutreten.
2.6 Aus diesen Gründen ist davon auszugehen, dass der Beschwerdeführer sein Recht auf die Anrufung von Art. 30 Abs. 1 BV mangels entsprechender Rügen im kantonalen Verfahren verwirkt hat. Der vom Beschwerdeführer in diesem Zusammenhang angerufene Art. 31 Abs. 1 BV führt zu keiner andere Betrachtungsweise. Auf diese Vorwürfe ist daher nicht einzutreten.
3. 3.1 Nach der Rechtsprechung des Bundesgerichts dürfen einem Angeschuldigten bei Freispruch oder Einstellung einer Strafuntersuchung nur dann Kosten auferlegt werden, wenn er durch ein unter rechtlichen Gesichtspunkten vorwerfbares Verhalten die Einleitung eines Strafverfahrens veranlasst oder dessen Durchführung erschwert hat. Bei der Kostenpflicht des freigesprochenen oder aus dem Verfahren entlassenen Angeschuldigten handelt es sich nicht um eine Haftung für ein strafrechtliches Verschulden, sondern um eine zivilrechtlichen Grundsätzen angenäherte Haftung für ein fehlerhaftes Verhalten, durch das die Einleitung oder Erschwerung eines Strafverfahrens verursacht wurde (BGE 119 Ia 332 E. 1b S. 334). Wie das Bundesgericht festgehalten hat, ist es mit Art. 32 Abs. 1 BV und Art. 6 Ziff. 2 EMRK vereinbar, einem nicht verurteilten Angeschuldigten die Kosten aufzuerlegen, wenn er in zivilrechtlich vorwerfbarer Weise (d.h. im Sinne einer analogen Anwendung der sich aus Art. 41 OR ergebenden Grundsätze) gegen eine geschriebene oder ungeschriebene Verhaltensnorm, die aus der gesamten schweizerischen Rechtsordnung stammen kann, klar verstossen und dadurch das Strafverfahren veranlasst oder dessen Durchführung erschwert hat (BGE 119 Ia 332 E. 1b S. 334; 116 Ia 162 E. 2a S. 166, je mit Hinweisen). Hingegen verstösst eine Kostenauflage bei Freispruch oder Einstellung des Strafverfahrens gegen den Grundsatz der Unschuldsvermutung, wenn dem Angeschuldigten in der Begründung des Kostenentscheids direkt oder indirekt vorgeworfen wird, er habe sich strafbar gemacht bzw. es treffe ihn ein strafrechtliches Verschulden (BGE 120 Ia 147 E. 3b S. 155).
Diese Grundsätze gelten nicht nur für die Auferlegung von Kosten, sondern auch für die Verweigerung einer Entschädigung (vgl. BGE 120 Ia 147 E. 3b S. 155; 116 Ia 162 E. 2g S. 176 f.).
3.2 Die vorliegende Beschwerde kreist zwar sinngemäss um die Frage, ob dem Beschwerdeführer in der Einstellungsverfügung ein strafrechtlich relevantes Verhalten zur Last gelegt wird. Der Beschwerdeführer beruft sich aber vor dem Bundesgericht - im Unterschied zu seinen Äusserungen im kantonalen Verfahren - nicht auf die Unschuldsvermutung gemäss Art. 32 Abs. 1 BV bzw. Art. 6 Ziff. 2 EMRK. Er macht auch nicht geltend, der angefochtene Entscheid lasse in der Begründung durchblicken, dass ihn trotz der Einstellung des Strafverfahrens ein strafrechtliches Verschulden treffe. Mit Blick auf diese Frage kann daher eine Prüfung des angefochtenen Entscheids unterbleiben (Art. 90 Abs. 1 lit. b OG; vgl. E. 1 hiervor).
3.3 Geht es nicht um den Schutzbereich von Art. 32 Abs. 1 BV und Art. 6 Ziff. 2 EMRK, womit der gute Ruf des Angeschuldigten gegen den direkten oder indirekten Vorwurf einer strafrechtlichen Missbilligung geschützt werden soll (BGE 114 Ia 299 E. 2b S. 302), so werden die Voraussetzungen für die Verlegung von Kosten und Entschädigungen durch das kantonale Recht umschrieben. Insofern gilt Art. 9 BV; danach dürfen die Anwendung der kantonalen Gesetzesbestimmungen und die Beweiswürdigung nicht willkürlich erfolgen (BGE 116 Ia 162 E. 2f S. 175 f.).
3.3 Geht es nicht um den Schutzbereich von Art. 32 Abs. 1 BV und Art. 6 Ziff. 2 EMRK, womit der gute Ruf des Angeschuldigten gegen den direkten oder indirekten Vorwurf einer strafrechtlichen Missbilligung geschützt werden soll (BGE 114 Ia 299 E. 2b S. 302), so werden die Voraussetzungen für die Verlegung von Kosten und Entschädigungen durch das kantonale Recht umschrieben. Insofern gilt Art. 9 BV; danach dürfen die Anwendung der kantonalen Gesetzesbestimmungen und die Beweiswürdigung nicht willkürlich erfolgen (BGE 116 Ia 162 E. 2f S. 175 f.).
4. 4.1 Die Staatsanwaltschaft erachtete es im angefochtenen Entscheid als erwiesen, dass der Beschwerdeführer im Rahmen von zwei Therapiegesprächen im Psychiatrischen Zentrum Herisau ganz konkrete und massivste Drohungen gegen eine erkennbare Drittperson ausgesprochen habe, untermauert mit dem Vorzeigen einer Waffe bzw. Waffenbestandteilen und entsprechenden Gesten. Die Drohungen seien von den damit konfrontierten Therapeuten als ernstzunehmend beurteilt worden. Auch wenn der Beschwerdeführer seine Gewaltbereitschaft bestritten habe, seien die Feststellungen der Therapeuten als realistisch zu beurteilen. In jener Situation habe er zu erkennen gegeben, dass er das potentielle Opfer töten wollte. Dabei sei unerheblich, dass die Drohungen im Rahmen einer Therapie und nicht direkt gegenüber dem Betroffenen ausgesprochen worden seien. Dadurch habe der Beschwerdeführer die Einleitung der Strafuntersuchung veranlasst.
4.2 Der Beschwerdeführer beklagt sich über eine willkürliche Feststellung des Sachverhalts. Eine Beweiswürdigung ist praxisgemäss nicht schon dann willkürlich, wenn die vom Sachrichter gezogenen Schlüsse nicht mit der Darstellung des Beschwerdeführers übereinstimmen (BGE 116 Ia 85 E. 2b S. 88). Rügt ein Beschwerdeführer die Verletzung des Willkürverbots (Art. 9 BV), so reicht es nach der Rechtsprechung zu Art. 90 Abs. 1 lit. b OG nicht aus, wenn er mit pauschalen Vorbringen behauptet, der angefochtene Entscheid sei willkürlich. Er hat vielmehr im Einzelnen aufzuzeigen, inwiefern die Beweiswürdigung offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (BGE 125 I 492 E. 1b S. 495 mit Hinweisen).
4.3 Der Beschwerdeführer bestreitet, dass ihm irgendeine vorwerfbare Handlung anzulasten sei. Er habe sich gegenüber seiner Therapeutin allenfalls ungeschickt ausgedrückt, weil er die deutsche Sprache nicht gut beherrsche. Zudem sei zu berücksichtigen, dass er die ihm vorgeworfenen Äusserungen in einem therapeutischen Rahmen gemacht habe; es sei um einen Hilferuf gegangen, mit dem er auf seine Probleme habe aufmerksam machen wollen. Diese pauschalen Vorbringen genügen in keiner Weise den Anforderungen der Rechtsprechung, um eine willkürliche Beweiswürdigung darzutun. Insoweit ist an sich auf die Beschwerde nicht einzutreten. Unabhängig davon erweisen sich die Vorbringen gegen die angefochtene Beweiswürdigung als unbegründet.
4.4 Einerseits steht das behauptete sprachliche Missverständnis zwischen der Therapeutin und dem Beschwerdeführer in offensichtlichem Gegensatz zur aktenkundigen Tatsache, dass der Beschwerdeführer gut deutsch spricht. Anderseits hält es ohne weiteres vor dem Willkürverbot stand, dass die Staatsanwaltschaft für den Sachverhalt auf die schlüssigen Aussagen der behandelnden Therapeutin abgestellt hat, die dem Inhalt der Anzeige des Psychiatrischen Zentrums entsprechen. Danach äusserte der Beschwerdeführer zuerst oberflächlich und später - als der geplante Ausschaffungstermin vom 5. November 2005 näher rückte - konkret und ernsthaft Rachepläne gegen den Mann, den er für den Tod seines Vaters verantwortlich machte. Dabei habe er der Therapeutin ein Klappmesser gezeigt, das er geöffnet habe; damit habe er vorgeführt, wie er den Mörder seines Vaters enthaupten werde. Weiter habe er vor ihr zwei Patronen auf den Tisch gelegt und erklärt, dass er mit einer Patrone jenen Mann und mit der anderen sich selbst töten werde.
Dass das potentielle Opfer dieser Drohungen im fraglichen Zeitpunkt vorübergehend im Ausland weilte, kann keine Rolle spielen, zumal es vor dem geplanten Ausschaffungstermin in die Schweiz zurückgekehrt ist. Überdies hat der Beschwerdeführer in der letzten Sitzung vor der Anzeige gegenüber der Therapeutin selbst eine feindliche Haltung zum Ausdruck gebracht, die sie nachhaltig erschrecken und um ihre eigene Person fürchten liess. Der Beschwerdeführer geht fehl, wenn er sein Gebaren nachträglich als Hilferuf an die Therapeutin zu verharmlosen sucht. Vor diesem Hintergrund ist es entgegen der Meinung des Beschwerdeführers auch unerheblich, dass er gegen sie nicht ausdrücklich Gewaltdrohungen ausgestossen hat.
4.5 Ebenso unbehelflich sind die weiteren Vorwürfe des Beschwerdeführers zur Sachverhaltsfeststellung im angefochtenen Entscheid. Die Staatsanwaltschaft durfte die ausführlichen Schilderungen in der Anzeige des Psychiatrischen Zentrums ohne weiteres mit dem gleichwertigen Ausdruck "massivste Drohungen" zusammenfassen. Dass diese Wendung sachlich überzeugt, bedarf keiner weiteren Erörterung (vgl. E. 4.4). Zu beanstanden ist auch nicht, dass die Staatsanwaltschaft von "zahlreichen Abklärungen" in der Strafuntersuchung nach der Verhaftung des Beschwerdeführers spricht. Im angefochtenen Entscheid wird in nachvollziehbarer Weise erläutert, worin diese Abklärungen bestanden haben. Haltlos ist schliesslich der Einwand, bei der Anzeige des Psychiatrischen Zentrums habe es sich lediglich um eine Information und nicht um eine Strafanzeige gehandelt.
4.6 Insgesamt dringt die Beschwerde in diesem Punkt nicht durch, soweit darauf einzutreten ist.
4.6 Insgesamt dringt die Beschwerde in diesem Punkt nicht durch, soweit darauf einzutreten ist.
5. 5.1 Nach Art. 242 Abs. 1 StPO/AR hat der Beschuldigte die Verfahrenskosten zu tragen, wenn er verurteilt wird oder wenn er durch verwerfliches Verhalten Anlass zum Strafverfahren gegeben oder dessen Durchführung erschwert hat. Gemäss Abs. 2 dieser Bestimmung kann er von der Kostenpflicht ganz oder teilweise befreit werden, wenn er nur teilweise im Sinne der Anschuldigung verantwortlich erklärt wird (Ziff. 1) oder die Kosten nicht veranlasst hat (Ziff. 2). Ebenso kann die Entschädigung ganz oder teilweise verweigert werden, wenn der Beschuldigte verwerflich oder unkorrekt gehandelt oder durch sein Verhalten die Untersuchung erschwert hat (Art. 246 Abs. 3 StPO/AR).
5.2 Nach Auffassung des Beschwerdeführers liegt Willkür vor, weil es die Staatsanwaltschaft unterlassen habe, eine konkrete zivilrechtliche Grundlage bzw. Verhaltensnorm zu nennen, die er verletzt haben solle. Dieser Vorwurf trifft zu. Nach der erwähnten Rechtsprechung des Bundesgerichts (E. 3.1) setzt die Kostenauflage bei der Einstellung des Strafverfahrens voraus, dass dieser in zivilrechtlich vorwerfbarer Weise gegen eine geschriebene oder ungeschriebene Verhaltensnorm klar verstossen hat. Hingegen ist es unzulässig, einem nicht verurteilten Angeschuldigten wegen eines allein unter ethischen oder moralischen Gesichtspunkten vorwerfbaren Verhaltens Kosten aufzuerlegen (BGE 116 Ia 162 E. 2b S. 167 f.). Im angefochtenen Entscheid wird bloss ausgeführt, der Beschwerdeführer habe mit seinen Drohungen gegen Normen unserer Rechtsordnung verstossen und sich damit in vorwerfbarer Weise verhalten. Inwiefern er mit den betreffenden Handlungen in zivilrechtlich vorwerfbarer Weise eine Verhaltensnorm nicht eingehalten habe, wird nicht gesagt. Eine derartige rechtliche Begründung hält vor Art. 9 BV nicht stand.
Der angefochtene Entscheid ist freilich erst aufzuheben, wenn er im Ergebnis gegen die Verfassung verstösst; es genügt nicht, dass sich die Begründung als verfassungswidrig erweist (BGE 129 I 8 E. 2.1 S. 9; 127 I 54 E. 2b S. 56). Das Bundesgericht hat somit die Möglichkeit, die Motive des umstrittenen Entscheids zu ersetzen (BGE 124 I 208 E. 4a S. 211; 122 I 257 E. 5 S. 262; vgl. auch BGE 130 I 241 E. 4.4 S. 248). Von dieser Möglichkeit ist indessen nur dann Gebrauch zu machen, wenn der massgebliche Sachverhalt aus den Akten hinreichend ersichtlich ist und die rechtliche Situation als klar erscheint (BGE 112 Ia 129 E. 3c S. 135 f.; Urteil 1P.164/2002 vom 25. Juni 2002 E. 1.3, in: Pra 91/2002 Nr. 203 S. 1069). Diese Voraussetzungen sind hier gegeben.
5.3 Die Rechtsprechung anerkennt als zivilrechtliche Haftungsgrundlage den Grundsatz "neminem laedere" (Urteil 1P.484/2002 vom 24. Januar 2003 E. 2.2.1, in: Pra 92/2003 Nr. 135 S. 727). Es handelt sich um ein allgemeines Rechtsprinzip, das insbesondere in Art. 28 Abs. 1 ZGB konkretisiert wird. Danach kann, wer in seiner Persönlichkeit widerrechtlich verletzt wird, zu seinem Schutz gegen jeden, der an der Verletzung mitwirkt, das Gericht anrufen.
Das Persönlichkeitsrecht wird verletzt durch Angriffe auf die physische und die psychische Integrität; darunter fällt auch ein Verhalten, das andere in Angst und Schrecken versetzt und diese in ihrem seelischen Wohlbefinden gefährdet bzw. erheblich stört (Hans Michael Riemer, Personenrecht des ZGB, 2. Aufl., Bern 2002, Rz. 338 f.; Henri Deschenaux/Paul-Henri Steinauer, Personnes physiques et tutelle, 4. Aufl., Bern 2001, Rz. 543 f.). Für die Beurteilung der Schwere des Eingriffs ist ein objektivierter Massstab anzulegen (BGE 127 III 481 E. 1b/aa S. 483; Andreas Meili, Basler Kommentar zum ZGB, Band I, 2. Auf., Basel 2002, Rz. 42 zu Art. 28).
5.4 Der Beschwerdeführer hat das Persönlichkeitsrecht der behandelnden Therapeutin verletzt, indem er sie in Angst und Schrecken versetzte (E. 4.4). Sein Verhalten überschritt bei weitem den zulässigen Rahmen einer therapeutischen Beziehung. Der Beschwerdeführer greift folglich zu kurz, wenn er die bei ihr ausgelösten Ängste einzig auf Schuldgefühle wegen der Weitergabe des Gesprächsinhalts zurückführt. Sie hat aus Furcht vor ihm auf eine Strafanzeige in eigenem Namen verzichtet. Ihr Verzicht ändert demnach nichts an der Widerrechtlichkeit der Persönlichkeitsverletzung. Das genannte Verhalten des Beschwerdeführers war denn auch adäquat kausal für die Einleitung des Strafverfahrens. Bei diesem Ergebnis kann offen bleiben, ob der Beschwerdeführer ebenfalls das Persönlichkeitsrecht jener Person missachtete, gegen die er in der Therapie Todesdrohungen ausgesprochen hat.
5.5 Aus diesen Gründen ist zu erkennen, dass der Beschwerdeführer vorliegend gegen den Grundsatz "neminem laedere" verstossen hat. Die Strafverfolgungsbehörden konnten auf die ihnen zur Anzeige gebrachte Gewaltbereitschaft des Beschwerdeführers vernünftigerweise nicht anders als mit der Einleitung eines Strafverfahrens reagieren (vgl. Niklaus Schmid, Strafprozessrecht, 4. Aufl., Zürich 2004, Rz. 1207). Demzufolge hält der angefochtene Entscheid mit dieser substituierten Begründung im Hinblick auf die Kostenauflage und die Verweigerung einer Parteientschädigung vor der Verfassung stand.
5.5 Aus diesen Gründen ist zu erkennen, dass der Beschwerdeführer vorliegend gegen den Grundsatz "neminem laedere" verstossen hat. Die Strafverfolgungsbehörden konnten auf die ihnen zur Anzeige gebrachte Gewaltbereitschaft des Beschwerdeführers vernünftigerweise nicht anders als mit der Einleitung eines Strafverfahrens reagieren (vgl. Niklaus Schmid, Strafprozessrecht, 4. Aufl., Zürich 2004, Rz. 1207). Demzufolge hält der angefochtene Entscheid mit dieser substituierten Begründung im Hinblick auf die Kostenauflage und die Verweigerung einer Parteientschädigung vor der Verfassung stand.
6. 6.1 Nach Art. 5 Ziff. 5 EMRK hat jeder, der entgegen den Bestimmungen dieses Artikels von Festnahme oder Haft betroffen ist, Anspruch auf Schadenersatz. Dieser Anspruch umfasst auch einen solchen auf Genugtuung (BGE 124 I 274 E. 3d S. 280; 119 Ia 221 E. 6a S. 230; 118 II 254 E. 2a S. 258). Die Bestimmung bezieht sich ausschliesslich auf den Fall rechtswidriger Haft. Anspruch auf Entschädigung besteht danach nur, wenn eine der Bestimmungen von Ziff. 1-4 des Art. 5 EMRK oder eine entsprechende Norm des nationalen Rechts missachtet worden ist (BGE 129 I 139 E. 2 S. 141; 125 I 394 E. 5b S. 400); nach allgemeinen haftpflichtrechtlichen Grundsätzen muss der geltend gemachte Schaden dabei durch die rechtswidrige Handlung verursacht worden sein.
6.2 Das Bundesgericht tritt nach Beendigung der Untersuchungshaft auf eine staatsrechtliche Beschwerde gegen die Haftanordnung nicht mehr ein und verweist den Beschwerdeführer für die Rüge der Verletzung von Art. 5 Ziff. 5 EMRK auf das Entschädigungsverfahren (BGE 125 I 394 E. 5g S. 404 f.). Das Entschädigungsverfahren ist nicht von der vorherigen Anfechtung der Haft oder der Feststellung von deren Rechtswidrigkeit abhängig (BGE 129 I 139 E. 3.1 S. 143; 125 I 394 E. 5d S. 402).
6.3 Art. 5 Ziff. 5 EMRK gewährt keinen Entschädigungsanspruch für Haft, die zwar rechtmässig angeordnet worden ist, sich nachträglich aber als ungerechtfertigt erweist; ein solcher kann vom anwendbaren kantonalen Recht verliehen werden (Urteil 1P.263/1997 vom 12. November 1997 E. 4a/b, in: Pra 87/1998 Nr. 78 S. 482 ff.; Urteil 1P.457/1996 vom 26. November 1996 E. 2, in: ZBl 99/1998 S. 34 f.). Der Beschwerdeführer ruft neben Art. 5 Ziff. 5 EMRK auch Art. 246 Abs. 1 StPO/AR als Haftungsnorm an; diese Bestimmung sei willkürlich angewendet worden. Aus diesen Normen beansprucht er Genugtuung für rechtswidrige Haft. Dagegen wird in der Beschwerde ein entsprechender Anspruch aus ungerechtfertigter Haft nicht hinreichend begründet (Art. 90 Abs. 1 lit. b OG; vgl. E. 1); darauf muss nicht eingegangen werden.
7. Der Beschwerdeführer begründet die geforderte Genugtuung mit dem Fehlen der materiellen Haftvoraussetzungen; es habe weder ein hinreichender Tatverdacht vorgelegen noch Ausführungsgefahr bestanden.
7.1 Nach Art. 98 Abs. 1 StPO/AR darf gegen einen Beschuldigten ein Haftbefehl erlassen werden, wenn er eines Verbrechens oder Vergehens dringend verdächtig ist und zudem bestimmte Anhaltspunkte für einen der vorgesehenen besonderen Haftgründe gegeben sind. Ziff. 3 sieht als derartigen Haftgrund die Gefährdung anderer durch Begehung einer neuen Straftat oder Ausführung einer angedrohten schweren Straftat vor. Demgegenüber lässt Art. 5 Ziff. 1 lit. c EMRK die Untersuchungshaft in weitergehender Weise zu, wenn hinreichender Verdacht besteht, dass die betreffende Person eine Straftat begangen hat, oder wenn begründeter Anlass zu der Annahme besteht, dass es notwendig ist, sie an der Begehung einer Straftat zu hindern. Der ebenfalls angerufene Art. 31 Abs. 1 BV hält fest, dass einer Person die Freiheit nur in den vom Gesetz selbst vorgesehenen Fällen entzogen werden darf.
Bei staatsrechtlichen Beschwerden, die sich gegen die Rechtmässigkeit der Anordnung einer Untersuchungshaft richten, prüft das Bundesgericht angesichts von Art. 31 Abs. 1 BV und im Hinblick auf die Schwere des Eingriffes die Auslegung und Anwendung des kantonalen Rechts frei. Soweit jedoch reine Sachverhaltsfragen und damit Fragen der Beweiswürdigung zu beurteilen sind, greift das Bundesgericht nur ein, wenn die tatsächlichen Feststellungen der kantonalen Instanz willkürlich sind (BGE 128 I 184 E. 2.1 S. 186; 123 I 31 E. 3a S. 35, 268 E. 2d S. 271).
Bei staatsrechtlichen Beschwerden, die sich gegen die Rechtmässigkeit der Anordnung einer Untersuchungshaft richten, prüft das Bundesgericht angesichts von Art. 31 Abs. 1 BV und im Hinblick auf die Schwere des Eingriffes die Auslegung und Anwendung des kantonalen Rechts frei. Soweit jedoch reine Sachverhaltsfragen und damit Fragen der Beweiswürdigung zu beurteilen sind, greift das Bundesgericht nur ein, wenn die tatsächlichen Feststellungen der kantonalen Instanz willkürlich sind (BGE 128 I 184 E. 2.1 S. 186; 123 I 31 E. 3a S. 35, 268 E. 2d S. 271).
7.2 7.2.1 Bei der Überprüfung des allgemeinen Haftgrundes des dringenden Tatverdachtes ist keine erschöpfende Abwägung sämtlicher belastender und entlastender Beweisergebnisse erforderlich. Wird das Fehlen eines ausreichenden Tatverdachts geltend gemacht, ist vielmehr zu prüfen, ob aufgrund der damals vorliegenden Untersuchungsergebnisse genügend konkrete Anhaltspunkte für eine Straftat und eine Täterschaft des Beschwerdeführers gegeben waren, die kantonalen Behörden somit das Bestehen eines dringenden Tatverdachts mit vertretbaren Gründen bejahen durften. Im Haftprüfungsverfahren genügt dabei der Nachweis von konkreten Verdachtsmomenten, wonach das inkriminierte Verhalten mit erheblicher Wahrscheinlichkeit die fraglichen Tatbestandsmerkmale erfüllen könnte (BGE 116 Ia 143 E. 3c S. 146). Das Beschleunigungsgebot in Haftsachen lässt dabei nur wenig Raum für ausgedehnte Beweismassnahmen. Zur Frage des dringenden Tatverdachtes bzw. zur Schuldfrage hat der Haftrichter weder ein eigentliches Beweisverfahren durchzuführen, noch dem erkennenden Strafrichter vorzugreifen. Vorbehalten bleibt allenfalls die Abnahme eines liquiden Alibibeweises (BGE 124 I 208 E. 3 S. 210 mit Hinweisen).
7.2.2 Im Haftprüfungsentscheid wurde zum dringenden Tatverdacht gegenüber dem Beschwerdeführer ausgeführt, er habe Vorbereitungshandlungen zu einer vorsätzlichen Tötung oder Mord im Sinne von Art. 260bis StGB begangen. Nach Abs. 1 dieser Bestimmung kann mit Zuchthaus bis zu fünf Jahren oder mit Gefängnis bestraft werden, wer planmässig konkrete technische oder organisatorische Vorkehrungen trifft, deren Art und Umfang zeigen, dass er sich anschickt, unter anderem die genannten Verbrechen auszuführen.
Der Haftprüfungsrichter stützte sich für diesen Vorwurf einerseits auf die Ausführungen in der Anzeige des Psychiatrischen Zentrums (vgl. E. 4.4) und anderseits auf die Aussagen des Beschwerdeführers. Dieser habe zugegeben, mit dem Anwalt, der die Opferfamilie beim Tod seines Vaters vertreten hatte, mehrfach Kontakt gehabt und einen Ordner mit Fakten zum Tod seines Vaters angelegt zu haben. Weiter habe er eingeräumt, vor der behandelnden Therapeutin zwei Patronenhülsen auf den Tisch gelegt zu haben sowie ein schweizerisches Armeesackmesser zu besitzen.
7.2.3 Diese Darstellung des damaligen Beweisergebnisses ist vertretbar. Es ergeben sich daraus ausreichende Anhaltspunkte für eine mögliche Täterschaft des Beschwerdeführers am untersuchten Verbrechen im Sinne eines dringenden Tatverdachts. Daran ändern auch die pauschalen Vorbringen des Beschwerdeführers nichts, er habe sich gegenüber der Therapeutin aus sprachlichen Gründen ungeschickt ausgedrückt und es sei um einen Hilferuf in einer Therapie gegangen. Diesen sachverhaltlichen Rügen wurde im Übrigen bereits vorstehend nachgegangen (E. 4.4). Der allgemeine Haftgrund des dringenden Tatverdachts war somit im Zeitpunkt der Haftprüfung gegeben.
7.2.3 Diese Darstellung des damaligen Beweisergebnisses ist vertretbar. Es ergeben sich daraus ausreichende Anhaltspunkte für eine mögliche Täterschaft des Beschwerdeführers am untersuchten Verbrechen im Sinne eines dringenden Tatverdachts. Daran ändern auch die pauschalen Vorbringen des Beschwerdeführers nichts, er habe sich gegenüber der Therapeutin aus sprachlichen Gründen ungeschickt ausgedrückt und es sei um einen Hilferuf in einer Therapie gegangen. Diesen sachverhaltlichen Rügen wurde im Übrigen bereits vorstehend nachgegangen (E. 4.4). Der allgemeine Haftgrund des dringenden Tatverdachts war somit im Zeitpunkt der Haftprüfung gegeben.
7.3 7.3.1 Art. 5 Ziff. 1 lit. c EMRK anerkennt ausdrücklich die Notwendigkeit, Angeschuldigte an der Begehung strafbarer Handlungen zu hindern, als Haftgrund (BGE 125 I 361 E. 4c S. 366; 123 I 268 E. 2c S. 270). Die rein hypothetische Möglichkeit der Verübung von Delikten sowie die Wahrscheinlichkeit, dass nur geringfügige Straftaten verübt werden, reichen allerdings nicht aus, um eine Präventivhaft zu begründen (BGE 125 I 60 E. 3a S. 62 mit Hinweis).
Für die Annahme der Ausführungsgefahr ist nicht erforderlich, dass der Verdächtige konkrete Anstalten getroffen hat, um das befürchtete Verbrechen zu vollenden. Vielmehr genügt es, wenn die Wahrscheinlichkeit einer Ausführung aufgrund einer Gesamtwertung der persönlichen Verhältnisse des Verdächtigen sowie der Umstände als sehr hoch erscheint (BGE 125 I 361 E. 5 S. 366 f.). Bei Gewalttaten von der Schwere einer Tötung darf an die Annahme von Ausführungsgefahr kein allzu hoher Massstab gelegt werden. Besonders bei drohenden schweren Gewaltverbrechen ist dabei auch dem psychischen Zustand des Verdächtigen bzw. seiner Unberechenbarkeit oder Aggressivität Rechnung zu tragen. Anders zu entscheiden hiesse, die potentiellen Opfer einem nicht verantwortbaren Risiko auszusetzen (vgl. BGE 123 I 268 E. 2e S. 271 f.).
7.3.2 Der Haftprüfungsrichter erblickte die Ausführungsgefahr vor dem Hintergrund der drohenden Ausweisung des Beschwerdeführers als gegeben; die Beteuerungen des Beschwerdeführers, dass er keine Tötungsabsichten habe, wurden als wenig glaubwürdig angesehen. Der Haftprüfungsrichter ging auch nicht weiter auf die nur mit Vorbehalten geäusserte Absicht des Beschwerdeführers ein, er könne seine Freundin heiraten und dadurch ein Aufenthaltsrecht in der Schweiz erlangen.
Ins Gewicht fällt, dass hinter der Anzeige, die das Strafverfahren ausgelöst hat, die behandelnde Therapeutin und ihr psychiatrisch geschulter Vorgesetzter standen. Diese zwei Fachpersonen kannten den Beschwerdeführer persönlich; sie stuften dessen Gewaltbereitschaft als hoch ein. Die im Haftprüfungsentscheid vorgenommene Einschätzung der vom Beschwerdeführer ausgehenden Gefahren erscheint deshalb für den damaligen Zeitpunkt als haltbar. Dass der Beschwerdeführer und seine Freundin in der Folge tatsächlich heirateten, ändert nichts an der Rechtmässigkeit der damaligen Beurteilung.
7.4 Unter diesen Umständen war es im Lichte der dargestellten Rechtsprechung gerechtfertigt, den Beschwerdeführer in Präventivhaft zu nehmen. Da die materiellen Haftgründe im Zeitpunkt des Haftprüfungsentscheids gegeben waren, fehlen insofern die Voraussetzungen für die geltend gemachte Genugtuung.
8. Ferner rügt der Beschwerdeführer die Dauer der Untersuchungshaft als unverhältnismässig und leitet daraus deren Rechtswidrigkeit ab.
8.1 Nach Art. 107 Abs. 1 StPO/AR darf die Untersuchungshaft nicht länger dauern, als Anlass dazu besteht. Im Haftprüfungsverfahren kann eine Frist von höchstens dreissig Tagen bestimmt werden, innert welcher um weitere Verlängerung der Haft nachgesucht werden kann (Art. 107 Abs. 2 StPO/AR). Vorliegend legte der Haftprüfungsrichter in diesem Sinne eine Frist von 20 Tagen fest.
8.2 Gemäss Art. 31 Abs. 3 BV und Art. 5 Ziff. 3 EMRK hat eine in strafprozessualer Haft gehaltene Person Anspruch darauf, innerhalb einer angemessenen Frist richterlich abgeurteilt oder während des Strafverfahrens aus der Haft entlassen zu werden. Eine übermässige Haftdauer stellt eine unverhältnismässige Beschränkung dieses Grundrechts dar. Sie liegt dann vor, wenn die Haftfrist die mutmassliche Dauer der zu erwartenden freiheitsentziehenden Sanktion übersteigt. Bei der Prüfung der Verhältnismässigkeit der Haftdauer ist namentlich der Schwere der untersuchten (bzw. zu befürchtenden) Straftaten Rechnung zu tragen. Im Weiteren kann eine Haft die zulässige Dauer auch dann überschreiten, wenn das Strafverfahren nicht genügend vorangetrieben wird, wobei sowohl das Verhalten der Justizbehörden als auch dasjenige des Inhaftierten in Betracht gezogen werden müssen. Nach der übereinstimmenden Rechtsprechung des Bundesgerichts und des Europäischen Gerichtshofes für Menschenrechte ist die Frage, ob eine Haftdauer als übermässig bezeichnet werden muss, aufgrund der konkreten Verhältnisse des einzelnen Falles zu beurteilen (BGE 128 I 149 E. 2.2 S. 151; 126 I 172 E. 5a S. 176 f.).
In Anbetracht des hier angerufenen Art. 5 Ziff. 5 EMRK erfolgt die Überprüfung der Angemessenheit der Haftdauer ebenfalls mit freier Kognition (vgl. BGE 119 Ia 221 E. 8a S. 235 f.).
8.3 Der Beschwerdeführer bemängelt, es sei eine verkappte Ausschaffungshaft angeordnet worden, weil die Haftdauer mit Blick auf den geplanten Ausschaffungstermin festgesetzt worden sei. Dieser Einwand geht an der Sache vorbei. Die Frage der Ausweisung aus der Schweiz spielte, wie dargelegt (E. 7.3.2), eine entscheidende Rolle für die Einschätzung der Gewaltbereitschaft. Der Aufenthaltsort der Person, auf die sich die Todesdrohungen bezogen, war im Zeitpunkt des Haftprüfungsentscheids noch unklar; ein wirksamer Schutz ihres Lebens konnte nur mit der Untersuchungshaft gewährleistet werden (BGE 125 I 361 E. 6 S. 367). Das Bundesgericht hat im angeführten Fall eine Dauer von zwei Monaten zum Schutz der dort von Todesdrohungen betroffenen Personen nicht als unverhältnismässig erachtet. Vor diesem Hintergrund durfte der Haftprüfungsrichter innerhalb der Bandbreite von 30 Tagen gemäss Art. 107 Abs. 2 StPO/AR eine Frist wählen, die bis zum geplanten Ausschaffungstermin reichte.
8.4 Die Dauer der tatsächlich erstandenen Untersuchungshaft ist ebenso wenig zu beanstanden. Den Strafverfolgungsbehörden kann entgegen der Auffassung des Beschwerdeführers keine mangelhafte Untersuchungsführung während der Haftdauer vorgeworfen werden; die Einvernahmen der behandelnden Therapeutin und der Person, auf die sich die Drohungen des Beschwerdeführers bezogen, wurden durchgeführt, sobald sie aus dem Ausland zurückgekehrt waren (vgl. auch E. 4.4/4.5). Am 3. November 2004 erhielt der Verhörrichter die Mitteilung, dass die Ausschaffung des Beschwerdeführers einstweilen nicht vollzogen werde. Aufgrund der weiteren Anwesenheitsmöglichkeit des Beschwerdeführers in der Schweiz war es vertretbar, dass das Verhörrichter annahm, der besondere Haftgrund der Ausführungsgefahr sei entfallen. Immerhin wurde die Schutzvorkehr getroffen, das potentielle Opfer und die Anzeigeerstatter am 4. November 2004 vorgängig über die bevorstehende Freilassung zu orientieren. Am Morgen des 5. November 2004 erfolgte die Freilassung. Es ist festzuhalten, dass die Haft des Beschwerdeführers nicht länger als nötig gedauert hat.
8.5 Demzufolge vermag der Beschwerdeführer die Rechtswidrigkeit der Untersuchungshaft nicht mit der angeblichen Unverhältnismässigkeit ihrer Dauer zu begründen. Damit ist seiner Forderung auch in dieser Hinsicht die Grundlage entzogen.
8.5 Demzufolge vermag der Beschwerdeführer die Rechtswidrigkeit der Untersuchungshaft nicht mit der angeblichen Unverhältnismässigkeit ihrer Dauer zu begründen. Damit ist seiner Forderung auch in dieser Hinsicht die Grundlage entzogen.
9. Schliesslich rügt der Beschwerdeführer eine Verletzung von Art. 29 BV; er führt indessen nicht aus, worin dieser Verstoss bestanden haben soll. Insofern genügt die Beschwerde den Anforderungen von Art. 90 Abs. 1 lit. b OG nicht (vgl. E. 1).
9. Schliesslich rügt der Beschwerdeführer eine Verletzung von Art. 29 BV; er führt indessen nicht aus, worin dieser Verstoss bestanden haben soll. Insofern genügt die Beschwerde den Anforderungen von Art. 90 Abs. 1 lit. b OG nicht (vgl. E. 1).
10. Nach dem Gesagten erweist sich die Beschwerde als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Mit dem Entscheid in der Sache wird das Gesuch um Erteilung der aufschiebenden Wirkung gegenstandslos.
Dem Verfahrensausgang entsprechend sind die Gerichtskosten grundsätzlich dem Beschwerdeführer aufzuerlegen (Art. 156 Abs. 1 OG). Er hat indessen ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung im Verfahren vor Bundesgericht gestellt. Gemäss Art. 152 Abs. 1 OG gewährt das Bundesgericht einer bedürftigen Partei, deren Rechtsbegehren nicht aussichtslos erscheint, auf Antrag Befreiung von der Bezahlung der Gerichtskosten; es gibt ihr nötigenfalls einen Rechtsanwalt bei, dessen Honorar im Falle des Unterliegens im festgesetzten Rahmen von der Bundesgerichtskasse ausgerichtet wird (Art. 152 Abs. 2 OG). Bei der Beurteilung der Bedürftigkeit des Beschwerdeführers sind seine eigenen Mittel sowie jene der ihm gegenüber unterstützungspflichtigen Personen (z.B. Ehegatten) zu berücksichtigen (BGE 108 Ia 9 E. 3 S. 10; Jean-François Poudret/Suzette Sandoz-Monod, Commentaire de la loi fédérale d'organisation judiciaire, Band V, Bern 1992, Rz. 4 zu Art. 152).
Der Beschwerdeführer hat am 10. Dezember 2004 geheiratet. Er behauptet nicht, dass seine Prozessarmut unter Berücksichtigung der Mittel der Ehefrau, die nach seinen Angaben für ihn finanziell aufkommt, gegeben sei. Ebenso wenig hat er Unterlagen eingereicht, um seine finanzielle Bedürftigkeit oder jene seiner Ehefrau glaubhaft zu machen. Der anwaltlich vertretene Beschwerdeführer hat somit die Bedürftigkeit nicht einmal ansatzweise dargetan. Bei dieser Sachlage sind die gesetzlichen Voraussetzungen der unentgeltlichen Rechtspflege und Verbeiständung nicht erfüllt.
Demnach erkennt das Bundesgericht:
Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
1. Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtsgebühr von Fr. 1'000.-- wird dem Beschwerdeführer auferlegt.
3. Die Gerichtsgebühr von Fr. 1'000.-- wird dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer und der Staatsanwaltschaft des Kantons Appenzell A.Rh. schriftlich mitgeteilt.
Lausanne, 14. Juli 2005
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: