Heap.ts 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156
  1. import { JavaObject, cast_java_lang_Object } from '../../../java/lang/JavaObject';
  2. import { Variable, cast_de_nrw_schule_svws_core_kursblockung_satsolver_Variable } from '../../../core/kursblockung/satsolver/Variable';
  3. import { JavaString, cast_java_lang_String } from '../../../java/lang/JavaString';
  4. import { Arrays, cast_java_util_Arrays } from '../../../java/util/Arrays';
  5. import { System, cast_java_lang_System } from '../../../java/lang/System';
  6. export class Heap extends JavaObject {
  7. private _data : Array<Variable>;
  8. private _size : number = 0;
  9. /**
  10. * Konstruktor.
  11. */
  12. constructor() {
  13. super();
  14. this._data = Array(1).fill(null);
  15. this._size = 0;
  16. }
  17. public toString() : String {
  18. return "Heap: " + Arrays.toString(Arrays.copyOf(this._data, this._size)).valueOf();
  19. }
  20. /**
  21. * Überprüft, ob der Heap leer ist.
  22. *
  23. * @return TRUE, wenn der Heap leer ist.
  24. */
  25. isEmpty() : boolean {
  26. return this._size === 0;
  27. }
  28. /**
  29. * Liefert das oberste (beste) Element des Heaps mit hoher Wahrscheinlichkeit.
  30. *
  31. * @return Liefert das oberste (beste) Element des Heaps mit hoher Wahrscheinlichkeit.
  32. */
  33. top() : Variable {
  34. let index : number = 0;
  35. while ((Math.random() < 0.1) && (index + 1 < this._size)) {
  36. index++;
  37. }
  38. return this._data[index];
  39. }
  40. /**
  41. * Liefert die Anzahl an Elementen im Heap.
  42. *
  43. * @return Die Anzahl an Elementen im Heap.
  44. */
  45. size() : number {
  46. return this._size;
  47. }
  48. /**
  49. * Fügt die Variable "var" dem Heap hinzu. Nach dem Einfügen kennt die Variable
  50. * mit {@link Variable#index} ihre eigene Position in diesem Heap.
  51. *
  52. * @param pVar Die einzufügende Variable.
  53. */
  54. insert(pVar : Variable) : void {
  55. if (this._size === this._data.length) {
  56. this._data = Arrays.copyOf(this._data, 2 * this._size);
  57. }
  58. let insertI : number = this._size;
  59. while (insertI > 0) {
  60. let parentI : number = Math.trunc((insertI - 1) / 2);
  61. let parentV : Variable = this._data[parentI];
  62. if (pVar.isBetterThan(parentV)) {
  63. this._data[insertI] = parentV;
  64. parentV.index = insertI;
  65. insertI = parentI;
  66. } else {
  67. break;
  68. }
  69. }
  70. this._data[insertI] = pVar;
  71. pVar.index = insertI;
  72. this._size++;
  73. }
  74. /**
  75. * Entfernt die Variable pVar vom Heap. Dabei wird zunächst mit Hilfe von
  76. * {@link Variable#index} die Position bestimmt. Anschließend wird der Heap so
  77. * transformiert, dass die Variable entfernt werden kann.
  78. *
  79. * @param pVar Die zu entfernende Variable.
  80. */
  81. remove(pVar : Variable) : void {
  82. this._size--;
  83. let lastV : Variable = this._data[this._size];
  84. if (lastV as unknown === pVar as unknown) {
  85. return;
  86. }
  87. let currentI : number = pVar.index;
  88. if (this._data[pVar.index] as unknown !== pVar as unknown) {
  89. console.log(JSON.stringify("FEHLER: Die Variable " + pVar + " ist nicht beim Index " + pVar.index + "!"));
  90. }
  91. while (currentI > 0) {
  92. let parentI : number = Math.trunc((currentI - 1) / 2);
  93. this._data[currentI] = this._data[parentI];
  94. this._data[currentI].index = currentI;
  95. currentI = parentI;
  96. }
  97. let parentI : number = 0;
  98. let childI : number = 1;
  99. while (childI < this._size) {
  100. if (childI + 1 < this._size) {
  101. if (this._data[childI + 1].isBetterThan(this._data[childI])) {
  102. childI = childI + 1;
  103. }
  104. }
  105. let child : Variable = this._data[childI];
  106. if (child.isBetterThan(lastV)) {
  107. this._data[parentI] = child;
  108. child.index = parentI;
  109. parentI = childI;
  110. childI = parentI * 2 + 1;
  111. } else {
  112. break;
  113. }
  114. }
  115. this._data[parentI] = lastV;
  116. lastV.index = parentI;
  117. }
  118. /**
  119. * Falls sich die Variable pVar im Heap befindet, wird sie entfernt und direkt
  120. * wieder hinzugefügt. Diese Methode muss aufgerufen werden, sobald die Variable
  121. * eine neue Bewertung erhalten hat.
  122. *
  123. * @param pVar Die Variable, deren Bewertung sich geändert hat.
  124. */
  125. public update(pVar : Variable) : void {
  126. if (pVar.index >= 0) {
  127. this.remove(pVar);
  128. if (pVar.negation !== null)
  129. this.remove(pVar.negation);
  130. this.insert(pVar);
  131. if (pVar.negation !== null)
  132. this.insert(pVar.negation);
  133. }
  134. }
  135. isTranspiledInstanceOf(name : string): boolean {
  136. return ['de.nrw.schule.svws.core.kursblockung.satsolver.Heap'].includes(name);
  137. }
  138. }
  139. export function cast_de_nrw_schule_svws_core_kursblockung_satsolver_Heap(obj : unknown) : Heap {
  140. return obj as Heap;
  141. }