Сортируем?
Сортируем?
Что-то у меня не получается отсортировать список проектов.
Дано: TSore : SortedSet<TProject>, который должен содержать упорядоченный список проектов.
using System;using System.Collections.ObjectModel;using System.Collections.Generic;namespace Data.CCScript.Comparer{internal class TProjectOrderComparer : IComparer<TProject>{const int EARLY = 1;const int EQUAL = 0;const int LATE = -1;// Projects should be ordered as following:// in order in which it should be build.// if a list of project references contain reference to the project// project in the reference list sould be build earlierint IComparer<TProject>.Compare(TProject a, TProject b){if (b.Guid == a.Guid){return EQUAL; // The same project}if (b.ProjectReferences.Contains(a)){return LATE; // 'b' going down}return EARLY;}}public class TStore : SortedSet<TProject>{public TStore() : base(new TProjectOrderComparer()){}}public class TProject{public TProject(){ProjectReferences = new Collection<TProject>();}public Guid Guid { get; set; }public ICollection<TProject> ProjectReferences { get; internal set; }}}
Может Я снова чего-то не понимаю, но конечный результат у меня не соответствует заданным критериям.
В аттаче - результат "сортировки".
Да, для исключения разночтений - проекты добавляются с полным списком референсов на другие проекты.
Есть отдельный несортированный список где все строится, потом он помещается в то что приведено выше.
Эээ... "годных" результатов сортировки может быть много. Проблема в том что получается "не годный" результат.
с очень беглого взгляда: 0 на выходе сравнилова должен быть не только когда "тот же самый", а когда "по барабану", т.е. "в списках взаимно не числятся". может еще что. я бы это исправил и еще раз тестанул.
да, редактирую пост: почему не проверяется, не содержит ли а ссылки на б?
псевдокод должен быть таков:
если а и б одно и то же - 0
иначе если а сслыается на б, то (если б ссылается на а - throw exception) -1
иначе если б ссылается на а, то 1, иначе 0
не соответствует, например, вот это:
<Project name="CareyGlass.DefaultsStorage" guid="97c05e9b-0b5f-4bb0-952d-c90e4ddee9c3" priority="6">
<DependOn guid="a0a574f4-33dc-4312-8ba7-0abd09cd7323" priority="2">CareyGlass.Interfaces</DependOn>
<DependOn guid="f3cd6b63-0312-4708-9c99-18232a20d21e" priority="3">GPS.Order.Factory</DependOn>
<DependOn guid="f0b39b3d-ebc0-46cb-b4b5-d60fbcaafcc0" priority="4">GPS.Order.Invariant</DependOn>
<DependOn guid="f162b1c8-5455-42bd-8170-754aaa625aa7" priority="12">GPS.Order.Serializer</DependOn>
, т.е. проект с приоритетом 6 зависит от другого с 12, который, следовательно, к моменту былда еще не будет готов.
не знаю, как другим, мне сравнялово - очевидно грубо-неправильно построено. но это, как говорил, на беглый взгляд. время пусть тс на проверки тратит, ему нужнее : )
Так все есть - коммент прямо в тексте - список проектов в порядке построения... или обратном.
А получается - неправильно... в файлике лежит.
Что интересно - сделал "голую" схему - получил правильно отсортированные данные.
То же самое, но в живой версии дает билиберду...
При этом разницы - в "голой" схеме делается однократная вставка, а в живой - Проекты вставляются. потом - модифицируются (понятно - порядок нарушается), затем перекидываются в массив, после чего хранилище зачищается и все вставляется обратно... но получается - не в том порядке.
Завтра, может быть, скину тесты...
псевдокод должен быть таков:
-----
Там не обязательно делать так сложно - приведенный код вполне должен делать что надо.
почему не проверяется, не содержит ли а ссылки на б?
-----
Потому что проверять не надо - Студия не допустит рекурсивную ссылку в солюшене.
Так все есть - коммент прямо в тексте - список проектов в порядке построения... или обратном.
Имеешь в виду комментарий в исходном тексте?
Так неотформатированные исходники я просто игнорирую. Когда наконец уже научишься вставлять форматированный текст? Ломит кнопу нажать?
вы что - действительно не видите, что ваш compare() - полная чушь?
-----
Чушь - не компаре - оно нормальное.
А вот - данные - это реальная "чушь" - они не полные.
А при неполных данных нет возможности однозначно определить -1, 0, +1.
Для полноты данных надо добавлять в ProjectReferences ссылки на ВСЕ (включая косвенно затрагиваемые) проекты от которых зависит данный. Мне это делать не хочется и потому Я сортирую то что есть и так как могу. Двойной прогон "стандартной" сортировки дает желаемый результат... хотя пузырьком прошло бы и за раз...
Вот тесты - погоняй:
using System;
using System.IO;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Data.CCScript.Comparer;
namespace Data.CCScript.Comparer.Tests
{
[TestClass]
public class Comparer_tests
{
[TestMethod]
public void Comparer_ProjectList()
{
ProjectList = new Dictionary<string, TProject>();
Assert.IsNotNull(ProjectList);
Assert.IsTrue(ProjectList.Count == 0);
FillProjectList();
Assert.IsTrue(ProjectList.Count > 0);
int dependant = 0;
foreach (var kvp in ProjectList)
{
dependant += kvp.Value.ProjectReferences.Count;
}
Assert.IsTrue(dependant == 0);
SetDependentProject();
dependant = 0;
foreach (var kvp in ProjectList)
{
dependant += kvp.Value.ProjectReferences.Count;
}
Assert.IsTrue(dependant != 0);
}
[TestMethod]
public void Comparer_ValidateComparisson()
{
ProjectList = new Dictionary<string, TProject>();
FillProjectList();
SetDependentProject();
IComparer<TProject> comparer = new TProjectOrderComparer();
TProject p1;
TProject p2;
p1 = ProjectList["GPS.Order.ColumnsDefs"];
p2 = ProjectList["GPS.Order.ColumnsDefs"];
Assert.AreEqual(0, comparer.Compare(p1, p2));
p1 = ProjectList["CareyGlass.Interfaces"];
p2 = ProjectList["GPS.Order.ColumnsDefs"];
Assert.AreEqual(1, comparer.Compare(p1, p2));
p1 = ProjectList["CareyGlass.Interfaces"];
p2 = ProjectList["GPS.Order.ColumnsDefs.Tests"];
Assert.AreEqual(1, comparer.Compare(p1, p2));
p1 = ProjectList["CareyGlass.Interfaces"];
p2 = ProjectList["GPS.Order.Factory"];
Assert.AreEqual(-1, comparer.Compare(p1, p2));
}
[TestMethod]
public void Comparer_TStore()
{
TStore store = new TStore();
ProjectList = new Dictionary<string, TProject>();
FillProjectList();
SetDependentProject();
foreach (var kvp in ProjectList)
{
store.Add(kvp.Value);
}
int n = 1;
foreach(TProject p in store)
{
p.Priority = n++;
}
if (File.Exists("Data.txt"))
File.Delete("Data.txt");
using (StreamWriter sw = new StreamWriter("Data.txt"))
{
foreach (TProject p in store)
{
sw.WriteLine("Project {0} {1} {2}", p.Priority, p.Guid, p.Name);
}
sw.Flush();
}
}
#region Support
static Dictionary<String, TProject> ProjectList = new Dictionary<string, TProject>();
static TProject GetProject(string pProjectName)
{
TProject project = ProjectList[pProjectName];
return project;
}
void SetDependentProject()
{
foreach (var kvp in ProjectList)
{
TProject project = kvp.Value;
switch (project.Name)
{
case "GPS.Order.ColumnsDefs":
break;
case "CareyGlass.Interfaces":
break;
case "GPS.Order.Factory":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
break;
case "GPS.Order.Invariant":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
project.ProjectReferences.Add(GetProject("GPS.Order.ColumnsDefs"));
project.ProjectReferences.Add(GetProject("GPS.Order.Factory"));
break;
case "GPS.Order.v06":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
project.ProjectReferences.Add(GetProject("GPS.Order.ColumnsDefs"));
project.ProjectReferences.Add(GetProject("GPS.Order.Factory"));
project.ProjectReferences.Add(GetProject("GPS.Order.Invariant"));
break;
case "CareyGlass.DefaultsStorage":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
project.ProjectReferences.Add(GetProject("GPS.Order.Factory"));
project.ProjectReferences.Add(GetProject("GPS.Order.Invariant"));
project.ProjectReferences.Add(GetProject("GPS.Order.Serializer"));
project.ProjectReferences.Add(GetProject("GPS.Order.v06"));
project.ProjectReferences.Add(GetProject("GPS.Order.v07"));
project.ProjectReferences.Add(GetProject("GPS.Order.v11"));
project.ProjectReferences.Add(GetProject("GPS.Order.ColumnsDefs"));
break;
case "GPS.Order.v06.Tests":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
project.ProjectReferences.Add(GetProject("CareyGlass.DefaultsStorage"));
project.ProjectReferences.Add(GetProject("GPS.Order.ColumnsDefs"));
project.ProjectReferences.Add(GetProject("GPS.Order.Invariant"));
project.ProjectReferences.Add(GetProject("GPS.Order.v06"));
break;
case "GPS.Order.v11.Tests":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
project.ProjectReferences.Add(GetProject("CareyGlass.DefaultsStorage"));
project.ProjectReferences.Add(GetProject("GPS.Order.ColumnsDefs"));
project.ProjectReferences.Add(GetProject("GPS.Order.Invariant"));
project.ProjectReferences.Add(GetProject("GPS.Order.v11"));
break;
case "Gps.Order.SW":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
project.ProjectReferences.Add(GetProject("GPS.Order.ColumnsDefs"));
project.ProjectReferences.Add(GetProject("GPS.Order.Factory"));
project.ProjectReferences.Add(GetProject("GPS.Order.Invariant"));
break;
case "Gps.Order.SW.Tests":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
project.ProjectReferences.Add(GetProject("CareyGlass.DefaultsStorage"));
project.ProjectReferences.Add(GetProject("GPS.Order.ColumnsDefs"));
project.ProjectReferences.Add(GetProject("GPS.Order.Invariant"));
project.ProjectReferences.Add(GetProject("Gps.Order.SW"));
break;
case "GPS.Order.v07":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
project.ProjectReferences.Add(GetProject("GPS.Order.ColumnsDefs"));
project.ProjectReferences.Add(GetProject("GPS.Order.Factory"));
project.ProjectReferences.Add(GetProject("GPS.Order.Invariant"));
break;
case "GPS.Order.Serializer":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
project.ProjectReferences.Add(GetProject("GPS.Order.ColumnsDefs"));
project.ProjectReferences.Add(GetProject("GPS.Order.Factory"));
project.ProjectReferences.Add(GetProject("GPS.Order.Invariant"));
break;
case "GPS.Order.v11":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
project.ProjectReferences.Add(GetProject("GPS.Order.ColumnsDefs"));
project.ProjectReferences.Add(GetProject("GPS.Order.Factory"));
project.ProjectReferences.Add(GetProject("GPS.Order.Invariant"));
break;
case "GPS.Order.Serializer.Tests":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
project.ProjectReferences.Add(GetProject("GPS.Order.Factory"));
project.ProjectReferences.Add(GetProject("GPS.Order.Serializer"));
project.ProjectReferences.Add(GetProject("GPS.Order.Invariant"));
project.ProjectReferences.Add(GetProject("Gps.Order.SW"));
project.ProjectReferences.Add(GetProject("GPS.Order.v06"));
project.ProjectReferences.Add(GetProject("GPS.Order.v07"));
project.ProjectReferences.Add(GetProject("GPS.Order.v11"));
break;
case "GPS.Order.ColumnsDefs.Tests":
project.ProjectReferences.Add(GetProject("GPS.Order.ColumnsDefs"));
project.ProjectReferences.Add(GetProject("GPS.Order.Invariant"));
break;
case "GPS.Order.Invariant.Tests":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
project.ProjectReferences.Add(GetProject("GPS.Order.Invariant"));
project.ProjectReferences.Add(GetProject("GPS.Order.v07"));
break;
case "GPS.Order.v07.Tests":
project.ProjectReferences.Add(GetProject("CareyGlass.Interfaces"));
project.ProjectReferences.Add(GetProject("CareyGlass.DefaultsStorage"));
project.ProjectReferences.Add(GetProject("GPS.Order.ColumnsDefs"));
project.ProjectReferences.Add(GetProject("GPS.Order.Invariant"));
project.ProjectReferences.Add(GetProject("GPS.Order.v07"));
project.ProjectReferences.Add(GetProject("GPS.Order.Factory"));
break;
}
}
}
static void FillProjectList()
{
ProjectList.Add("GPS.Order.ColumnsDefs", new TProject("GPS.Order.ColumnsDefs", "462d0d6a-6d3a-42cc-8e5f-4cadb5380f6f"));
ProjectList.Add("CareyGlass.Interfaces", new TProject("CareyGlass.Interfaces", "a0a574f4-33dc-4312-8ba7-0abd09cd7323"));
ProjectList.Add("GPS.Order.Factory", new TProject("GPS.Order.Factory", "f3cd6b63-0312-4708-9c99-18232a20d21e"));
ProjectList.Add("GPS.Order.Invariant", new TProject("GPS.Order.Invariant", "f0b39b3d-ebc0-46cb-b4b5-d60fbcaafcc0"));
ProjectList.Add("GPS.Order.v06", new TProject("GPS.Order.v06", "a11d5c1b-6bc5-4392-87d3-2596a7a780f8"));
ProjectList.Add("CareyGlass.DefaultsStorage", new TProject("CareyGlass.DefaultsStorage", "97c05e9b-0b5f-4bb0-952d-c90e4ddee9c3"));
ProjectList.Add("GPS.Order.v06.Tests", new TProject("GPS.Order.v06.Tests", "72c4aab0-c484-439b-b622-9ffac1a0f817"));
ProjectList.Add("GPS.Order.v11.Tests", new TProject("GPS.Order.v11.Tests", "2fe5d102-8f68-46f2-a435-365e9758bd9d"));
ProjectList.Add("Gps.Order.SW", new TProject("Gps.Order.SW", "146b475b-a666-4d4e-ab6e-740704978793"));
ProjectList.Add("Gps.Order.SW.Tests", new TProject("Gps.Order.SW.Tests", "5c529deb-fde0-4d0b-ad4e-db8d3cae5045"));
ProjectList.Add("GPS.Order.v07", new TProject("GPS.Order.v07", "ad138182-ff46-4a3c-9420-81a57c04fc67"));
ProjectList.Add("GPS.Order.Serializer", new TProject("GPS.Order.Serializer", "f162b1c8-5455-42bd-8170-754aaa625aa7"));
ProjectList.Add("GPS.Order.v11", new TProject("GPS.Order.v11", "4545a189-d0b4-4930-9a1e-f49819b3e0d8"));
ProjectList.Add("GPS.Order.Serializer.Tests", new TProject("GPS.Order.Serializer.Tests", "337f9247-cdc4-43a1-963d-75bd259dc12e"));
ProjectList.Add("GPS.Order.ColumnsDefs.Tests", new TProject("GPS.Order.ColumnsDefs.Tests", "2c7be719-5b63-4281-93d9-e7aec1d4a167"));
ProjectList.Add("GPS.Order.Invariant.Tests", new TProject("GPS.Order.Invariant.Tests", "2630aa24-ec74-45a3-8d6b-23b63a78a371"));
ProjectList.Add("GPS.Order.v07.Tests", new TProject("GPS.Order.v07.Tests", "3d41e3b7-8ab3-4143-b12f-6efef8663aec"));
}
#endregion
}
}
Чушь - не компаре - оно нормальное. А вот - данные - это реальная "чушь" - они не полные. А при неполных данных нет возможности однозначно определить -1, 0, +1.Для полноты данных надо добавлять в ProjectReferences ссылки на ВСЕ (включая косвенно затрагиваемые)
логично. но компаре ваше - все равно чушь. в моем пвевдокоде "а сслыается на б" не означает содержит непосредственно ссылку. давайте перепишем это как "а зависит от б" (прямо или косвенно). напишете метод bool dependsOn (Projtct proj), в котором выследите, существует ли цепочка от а к б. если найдете loop, бросите прерывание.
давайте перепишем это как "а зависит от б" (прямо или косвенно).
-----
Написать то напишем, а как считать будем?
Полной выкладки все одно нет - часть рекурсивных ссылок может быть в уже скомпилированных дллках... парсить все дллки на предмет ссылок?
Или... просто не включены в солюшен т.к. он строит только какую-то часть проектов в которых какие-то локальные проблемы.
напишете метод bool dependsOn (Projtct proj), в котором выследите, существует ли цепочка от а к б.
-----
Не надо писать метод - он будет очень сложным.
В общем случае, т.е. в случае когда решение находится только перебором вариантов, метод называется альфа-поиск. Олимпиадная задачка 85/86 годов...
В частном случае, типа имеющегося, можно построить матрицу смежности - там тоже простенько выяснится что есть зависимость... при неполных данных она довольно пуста и бесполезна.
НО! Мне не надо выяснять все эти моменты - за меня большую часть работы сделала Студия - циклических ссылок в проектах нет, остальное меня мало беспокоит.
Так что все что мне нужно - просто УПОРЯДОЧИТЬ список имеющихся проектов.
Двойная сортировка дает нужный результат без всяких сложностей.
но компаре ваше - все равно чушь.
-----
Но оно - примитивно простое, понятное и работает.
Чтобы понять проблему - посмотри на два проекта:'GPS.Order.ColumnsDefs' и 'CareyGlass.Interfaces'
Каким у тебя будет результат их сравнения? -1, 0, +1?
Если все еще не понятно - возьми другую пару: 'GPS.Order.ColumnsDefs' и 'GPS.Order.Factory'
И что будет? -1, 0, +1?
если найдете loop, бросите прерывание
-----
Да нет там циклов - не позволяет Студия добавить в солюшен проект вызывающий циклическую зависимость.
Сторить частичное - мало толку, строить полное - почти алфа-поиск - там дерево с разрывамi.
Что ты называешь альфа-поиском? И что такое дерево с разрывами? И в чем тут может быть проблема? Единственное, что тебе нужно сделать - добавить "родителей" к проекту. Т.е. ты должен знать какие проекты зависят от текущего проекта.
Что ты называешь альфа-поиском?
------
То, что всегда им называлось - перебор вариантов с возвратом.
И что такое дерево с разрывами? И в чем тут может быть проблема?
-----
Множественные предки. Обычное дерево имеет один корень и кучу бетвей. Ну а в этом случае - много мелких кустиков.
Можно, конечно, ввести общего фиктивного предка и обплясать всю ситуацию, но по трудозатратам это будет явно хуже имеющегося решения.
Т.е. ты должен знать какие проекты зависят от текущего проекта.
------
Должен, но по факту - знаю не всех, а только тех, которые непосредственно прописаны в проекте.
Нужно же мне знать еще и тех, что лежат в соседнем солюшнике, а тут - добавлены референсами на дллки.