Бесконечный вызов цикла при обходе?

Question

[Константин]

Есть такой цикл:

let children = [];
		do {
			console.log(tag.create());
			children = tag.getChildren();
		} while (children.length);

Он на вход получает корневой элемент XMLtag и дальше должен вывести всех его чилдов:

class XMLtag {
private children: XMLtag[] = [];
}

Создание элементов такое:

const tagsTree = new TagsTree();
	const orderTag = new XMLtag("order");

	orderTag.addAttribute({ name: "id", value: "1" });
	const priceTag = new XMLtag("price");
	orderTag.addChildren(priceTag);

Почему зацикливается цикл do/while?

Класс целиком:

class XMLtag {
	private tagname: string;
	private _attributes = new Map<string, string>();
	private parent: XMLtag[] = [];

	constructor(tagname: string) {
		if (!tagname) throw Error("No tag passed!");
		this.tagname = tagname;
	}

	public addAttribute(attribute: { name: string; value: string }) {
		if (!attribute) throw Error("No attribute!");
		if (!attribute.name) throw "No attribute name!";
		if (this._attributes.has(attribute.name)) throw Error("Attribute alread exist!");

		this._attributes.set(attribute.name, attribute.value);
	}

	public create() {
		return `<${this.tagname} ${this.attributes}></${this.tagname}>`;
	}

	public getChildren() {
		return this.parent;
	}

	public addChildren(tag: XMLtag) {
		this.parent.push(tag);
	}

	private get attributes(): string {
		let arr: any[] = [];
		this._attributes.forEach((value, name) => {
			arr.push({ name, value });
		});

		return arr.map((attribute) => `${attribute.name}="${attribute.value}"`).join(" ");
	}
}

Comments

[Владимир]

Почему цикл работает в цикле? хмм....

while(true) === while(children.length)

[Константин]

Владимир, так если children пустой массив то lenght вернет true - и цикл прекретится - нет разве?

[Владимир]

Константин, запустите while(true) в консоли, откроете Америку для себя

[WbICHA]

Владимир, ты какую-то фигню сморозил, проблема совершенно в другом. И написанное тобой равенство равенством не является.

Константин, у тебя каждую итерацию обращение к одному и тому же тегу, поэтому children = tag.getChildren(); всегда будет выдавать один и тот же результат.
Хотя реализацию методов create и getChildren я не вижу, но я сильно сомневаюсь, что там используются итераторы.

[Владимир]

WbICHA, чел, посмотри код и потом повтори этот калл вторым комментарием. Цикл при существовании длины массива работает бесконечно, если есть хоть 1 элемент в массиве children, то children.length === true.

[Константин]

Владимир, разве[].length !== true?. Я привел класс целиком

[WbICHA]

Владимир, ещё раз, цикл будет работать бесконечно не потому, что while(children.length), а потому, что children всегда будет равен одному и тому же массиву.
И именно поэтому вот это: while(true) === while(children.length) полная ахинея.

[WbICHA]

Константин,

constructor(tagname: string) {
    if (!tagname) throw Error("No tag passed!");
    this.tagname = tagname;
  }

  public addAttribute(attribute: { name: string; value: string }) {
    if (!attribute) throw Error("No attribute!");
    if (!attribute.name) throw "No attribute name!";

Зачем эти проверки при использовании тайпскрипта?

private get attributes(): string {
    let arr: any[] = [];
    this._attributes.forEach((value, name) => {
      arr.push({ name, value });
    });

    return arr.map((attribute) => `${attribute.name}="${attribute.value}"`).join(" ");
  }

Что мешает сразу пушить строку?

public getChildren() {
    return this.parent;
  }

Что и требовалось доказать.
Каким образом данная конструкция проходится по детям?

let children = tag.getChildren();
while (children.length) {
  children = tag.getChildren();
}
// =
let children = [1, 2, 3];
while (children.length) {
  children = [1, 2, 3];
}

[Константин]

WbICHA, какое решение?

let i = 0;

		while (i <= parents.length) {
			console.log(tag.create());
			parents = tag.getChildren();
			i++;
		}

Пытаюсь решить это не используя рекурсию

[WbICHA]

Константин, во-первых, что не так с рекурсиями?
Во-вторых, ты вообще не понимаешь что ты делаешь?

tag.getChildren().forEach((child) => console.log(child));

[Константин]

WbICHA, что можете порекомендовать к прочтению? Обход графа?

[Константин]

WbICHA, ваш пример пройдет только по чилдам одного элемента - дальше одной вложенности не пойдет

[WbICHA]

Константин, основы программирования. Тут полное непонимание что такое массив, как он работает и его обойти циклом. А учитывая, что класс явно не ты писал, то и непонимание классов.

[Владимир]

WbICHA, да понятное дело что массив будет один и тот-же, но услышь меня, хватит тупить, массив пуст но его длина существует и равна 0, 0 - true из-за этого рекурсия.

[WbICHA]

Константин, конечно нет, тут уже великая и могучая рекурсия нужна.
Можно, конечно, и вайлом это решить, но выглядеть будет убого и бессмысленно.

[WbICHA]

Владимир, ты шутишь? 0 => false
Верни children = tag.getChildren(); пустой массив и цикл сразу завершился бы.

[Константин]

WbICHA, класс мой. с массивами знаком, вы перегнули палку. Вопрос в реализации через цикл. Я понимаю что у первого элемнта есть массив чилдов у каждого элемента массива мождет быть так же свой чилд и так в грубину. Поэтому сначала нужно обойти верхние элементы массив [1,2,3] вы вести их затем зайти в каждый 1 2 3 и в них найти чилдов

[Константин]

Константин, т-е я не понимаю как заставить цикл переключиться на вывод чилдов первого элемента кода завершен обход всех элементов массива корневого уровня

[Константин]

Константин, по идеи должен быть дополнительный массив из элементов которы йнужно дополнять если еслть чилды и удалять верхний элемент после обхода.

Answer 1

[WbICHA]

Адекватно без рекурсии и только через циклы не сделать никак, а неадекватно можно использовать 2 цикла.

console.log(tag.create());
  const allChildren = [tag.getChildren()];

  for(const children of allChildren) {
    children.forEach((child) => {
      console.log(child.create());
      allChildren.push(child.getChildren());
    })
  }

Comments

[Константин]

можете порекомендовать статью по обходу - алгоритму?

[Константин]

Если через рекурсию - то так?

build(tag: XMLtag) {
		console.log(tag.create());

		if (tag.getChildren().length == 0) {
			return;
		}

		tag.getChildren().forEach((c) => {
			this.build(c);
		});
	}

[WbICHA]

можете порекомендовать статью по обходу - алгоритму?

Скорее нет, чем да, потому что я давно не задавался этим вопросом.
Нагугли, статей должно быть полно, любая будет полезна. В идеале если там ещё и комментарии под ней будут, там могут указать на ошибки и неточности статьи.

Если через рекурсию - то так?

Почти. Иф вообще лишний. И обход по другому будет идти (в глубину).

[WbICHA]

И да, Константин, подправил ответ, теперь он даже смотрится неплохо.
Если что, форыч там не пройдёт, он запоминает стартовый размер массива.

[Aetae]

WbICHA, чёт ты намудрил:

function list(tag) {
  const stack = [tag];
  while(tag = stack.shift()) {
    console.log(tag.create());
    stack.push(...tag.getChildren());
  }
}

[WbICHA]

Aetae, вообще-то изначально через шифт я и написал, но я нелюблю его использовать, потому что медленно. Деструктурирование тоже не использовал по этой же причине.
А за вот это: while(tag = stack.shift()) вообще расстреливать надо.)

[Aetae]

Я считаю, что расстреливать надо за неиспользования подобной выразительности языка в явно идеально подходящих доля того случаях. И похрен что по этому поводу думает дефалтно настроенный линтер.

[WbICHA]

Aetae, а причём здесь линтер? Это слабочитабельно. Слишком легко с проверкой на равенство перепутать.

[Aetae]

WbICHA, да отлично это читабельно. В каких-то более замороченых случаях я мог бы и согласиться, но конструкция while(foo = bar()) слишком очевидна, чтоб её можно было с чем-то спутать. Линтер тут как раз при том, что тонкостей не различает и кладёт всё на прокрустово ложе формальности, заодно форматируя мозги пользователей.

[WbICHA]

Aetae,

while(foo = bar())
while(foo == bar())
while(foo === bar())

Если быстро просматривать код, перепутать легче лёгкого.

[WbICHA]

Aetae, и да, в чём смысл, если можно без проблем написать так:

function list(tag) {
  const stack = [];
  while(tag) {
    console.log(tag.create());
    stack.push(...tag.getChildren());
    tag = stack.shift()
  }
}

Чётко и ясно.

[Aetae]

WbICHA,

Если быстро просматривать код, перепутать легче лёгкого.

Фигня абстрактная. Не вижу ни одной ситуации в которой я мог бы тут что-то перепутать.

в чём смысл, если можно без проблем написать так:

Так действительно няшнее для данного случая, но вот как раз чтобы понять, что тут происходит, придётся задуматься, ибо конструкция нестандартная.)

В итоге на самом деле всё упирается в привычки конкретного человека и набор выражений, которые "внутренний парсер" схватывает слёту.)

[WbICHA]

Aetae, верно, такое написание тоже шлак, потому что тут всё сделано для фор..офа.

function list(parentTag) {
  const tags = [parentTag];
  for(const tag of tags) {
    console.log(tag.create());
    tags.push(...tag.getChildren());
  }
}

Собственно, практически пришли к тому, что у меня выше.)

[Aetae]

WbICHA, я сам обычно for of юзаю в таком виде, но стоит это делать с оглядкой, т.к. массив растёт постоянно, и если тут это не на что особо не влияет(всё равно ссылки есть в других местах), то если бы те же getChildren() генерили результат динамически, то это съедало бы лишнюю память.

[WbICHA]

Aetae, это безусловно, именно поэтому я бы использовал рекурсию.)