Запретить бесконечную петлю между объектами, ссылающимися друг на друга?

Question

Хорошо, поэтому я не был полностью уверен, что заголовок будет соответствовать моей проблеме, но здесь идет описание:

У меня есть объекты, которые могут ссылаться на другие объекты, для создания выпадающих списков, где содержание/значения зависят от того, что значения выбираются в «родительских» выпадающих списках.

Мои выпадающие объекты содержат id и parentId (и другие вещи, которые здесь не актуальны).

Я хочу, чтобы запретить пользователям делать бесконечные циклы, как это:

• Список 1 (В зависимости от списка 3)

• List 2 (в зависимости от списка 1)

• Список 3 (Зависит от списка 2)

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

Может ли кто-нибудь сказать мне, как бы вы гарантировали, что объект не ссылается на него самостоятельно «вниз по линии»? Или, может быть, привести пример.

Любая помощь очень ценится.

Answer 1

Самый простой способ, который я могу придумать, - создать сплющенный список. Рекурсивно перебирайте объекты и сохраняйте каждую ссылку в списке. Когда вы обнаружите, что новые объекты проверяют каждый из них.

Вы либо столкнетесь с объектом, который ссылается на себя, либо закончите поиск объектов.

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

Поскольку все объект содержит идентификатор список может хранить/проверить, что вместо того, чтобы, если вам нужно проверить равенство значений вместо ссылочного равенства

Answer 2

Если вы написали рекурсивную функцию для управления этими списками, одним из решений может быть создайте список элементов и передайте его как параметр в рекурсивную функцию, и каждая каждая итерация добавит текущий элемент в список. Чтобы остановить рекурсивную функцию, проверьте только, был ли текущий элемент добавлен ранее в список.

Answer 3

Если вы перебираете фактические элементы каждого списка, полагаясь на конкретные счетчики для каждого списка, вы не должны найти никаких проблем. Самый вероятный способ спровоцировать бесконечный цикл - это изменение значения счетчика от внешнего источника. Пример:

for(int i = 0; i < max_i; i++) 
    { 
     if(val1[i] != null) 
     { 
     for(int j = 0; j < max_j; j++) 
     { 
      if(val2[j] != null) 
      { 
       //Delete or anything 

       //YOU CANNOT AFFECT NEITHER i NOR j DIRECTLY. 
      } 
     } 
     } 

Если вы хотите, чтобы учесть изменения значения j во внутренней части, вы должны полагаться на другой переменной. Пример:

if(val2[j] != null) 
{    
    int j2 = j; 

    //Do whatever with j2, never with j 
} 

Делая это (связывая разные счетчики с разными контурами), не будет бесконечного цикла. Бесконечная петля возникает, когда: i = 1, 2, 3, 4 и внезапно i заменен на 2 «внешним источником»; таким образом, решение: НИКОГДА не изменяйте i, кроме как через цикл for.

Answer 4

Спасибо всем за ваш вклад в это. Я пошел с Джеймсом предложением, используя список и в конечном итоге с помощью следующего кода (который может или не может иметь смысл для кого-то еще, кроме меня)

public static bool BadParent(int fieldId, int childId, List<int> list) 
    { 
     if (list == null) 
      list = new List<int>(); 

     bool returnValue = true; 

     var field = EkstraFelterBLL.getEkstraFeltUdfraEkstraFeltId(fieldId); 

     if (field != null) 
     { 
      if (field.ParentEkstraFeltId == childId) 
       returnValue = false; //loop reference, fail 
      else if (list.Contains(field.EkstraFeltId)) 
       returnValue = false; //already been in the cycle, fail 
      else 
      { 
       list.Add(field.EkstraFeltId); 
       returnValue = BadParent(field.ParentEkstraFeltId, childId, list); 
      } 
     } 

     return returnValue; 
    }