je

1. conserver une liste non ordonnée de plages "ouvertes"
2. commencez dès le premier jour, et ajoutez la première gamme à la liste des gammes ouvertes.
3. Déplacer jusqu'à la prochaine plage de limites (début ou fin). Créez votre première gamme "output": à partir du jour 1, se terminant ce jour-là. Dans ce sont les articles dans votre liste de gammes ouvertes.
4. si la plage rencontrée est déjà dans la liste des plages ouvertes, supprimez-la. Sinon, l'ajouter.
5. répéter 3 et 4, se déplaçant le long de la ligne.

j'ai vraiment fait un mauvais travail d'expliquer cela. Je vais écrire un peu de code pour ce bientôt. Mais en attendant, voici ce qui se passerait dans votre solution:

a   |------------------------------|
b                    |-------------------|
c          |-----------------|

1.  Start at day 1, add A to open ranges list, which now contains [A]
2.  Move to the start of C.  First RESULT RANGE: A range from Day 1 to C's start,
      with a value A. (what is in your open ranges list)
3.  Add C to the open ranges list, which now contains [A,C]
4.  Move to the start of B.  Second RESULT RANGE: A range from C's start to B's
      start, with a value A,C. (what is in your open ranges list)
5.  Add B to the open ranges list, which now contains [A,C,B]
6.  Move to the end of C.  Third RESULT RANGE: A range from B's start to C's end,
      with a value of A,C,B.
7.  Remove C from the open ranges list, which now contains [A,B]
8.  Move to the end of A.  Fourth RESULT RANGE: A range from C's end to A's end,
      with a value of A,B
9.  Remove A from the open ranges list, which now contains [B]
10. Move to the end of A.  Fourth RESULT RANGE: A range from A's end to B's end,
      with a value of B

RESULT RANGES
1. from Day 1 to C's start: A
2. from C's start to B's start: A,C
3. from B's start to C's end: A,C,B
4. from C's end to A's end: A,B
5. from A's end to B's end: B

Méthode Alternative

Vous pourriez faire ceci:

1. conservez une liste ordonnée des"plages de sortie". Cela rend facile de tester si un point est dans une gamme, et aussi quelles gammes suivent l'autre.
2. prise a gamme à partir de vos gammes d'entrée.
3. vérifier pour voir si elle est complètement avant ou complètement après toutes les plages de sortie, et gérer en conséquence. Ignorer les étapes suivantes et retourner à l'étape 2, si.
4. comparez son point de départ aux plages de sortie
5. Si c'est avant toute autre gamme de sortie, ajouter une nouvelle gamme de sortie de son départ au début de la première plage de sortie.
6. si c'est entre une plage de sortie déjà existante, divisez cette plage de sortie point. La première partie aurait le même "les parents", et la deuxième partie aurait les mêmes parents + la nouvelle gamme d'entrée.
7. maintenant, comparez son point final aux plages de sortie.
8. si elle est après une autre plage de sortie, ajouter une nouvelle plage de sortie de la fin de la dernière plage de sortie à sa fin.
9. s'il s'agit d'une plage de sortie déjà existante, divisez cette plage de sortie à ce point. La deuxième partie contiendrait les mêmes "parents", et la première partie aurait les mêmes parents + la nouvelle gamme d'entrée
10. ajouter la plage d'entrée courante en tant que partie à toutes les plages situées entre les deux plages "traitées" aux étapes 6 et 9, le cas échéant.
11. répéter 2-6 pour toutes les plages d'entrée.

Voici les premières étapes, en utilisant les données de l'échantillon + une gamme D: (les plages "traitées" sont indiquées par **double stars**)

a   |------------------------------|
b                    |-------------------|
c          |-----------------|
d       |------------------------|

1.
   Process A
   Output ranges: |--------------A---------------|
2.
   Process B
     - Start of B is in **A**; split A in two:
                  |-------A-------|------AB------|
     - End of B is after any output range range;
         creating new output range at end
                  |-------A-------|------AB------|---B---|
    - Nothing was/is in between **A** and (nothing)
3.
   Process C
     - Start of C is in **A**; split A in two:
                  |---A----|--AC--|------AB------|---B---|
     - End of C is in **AB**; split AB in two:
                  |---A----|--AC--|--ABC--|--AB--|---B---|
     - There were/are no ranges between **A** and **AB**

4.
   Process D
     - Start of D is in **A**; split A in two:
                  |-A-|-AD-|--AC--|--ABC--|--AB--|---B---|
     - End of D is in **AB**; split AB in two:
                  |-A-|-AD-|--AC--|--ABC--|ABD|AB|---B---|
     - Ranges AC and ABC were/are in between **A** and **AB**
                  |-A-|-AD-|--ACD-|-ABCD--|ABD|AB|---B---|

Final output:     |-A-|-AD-|--ACD-|-ABCD--|ABD|AB|---B---|

Vous voudrez peut-être regarder Arbres D'Intervalle.

j'ai un code qui fait ça. Il s'appuie sur l'entrée-ensemble étant commandé par from et to (ie. si c'était SQL, il serait ORDER BY from_value, to_value), mais après qu'il est tout à fait optimale.

Mon application ne fait que @Justin L.réponse décrit, donc si vous voulez une description textuelle, regardez sa réponse pour l'algorithme.

Le code est ici: LVK.Infrastructure de données, et les fichiers que vous voulez regarder sont:

• portée.cs
• RangeExtensions.cs, en particulier la méthode Slice à ligne 206 et au-delà.

utilisation:

List<Range<DateTime>> ranges = ...
var slices = ranges.Slice();

cela vous donnera une nouvelle gamme pour chaque tranche, et pour chacune de ces gammes vous aurez un .Propriété de données contenant des références aux plages de contribution.

ie. pour votre exemple, vous obtiendrez exactement ce que vous voulez, fourchettes individuelles, avec les fourchettes contributives a, b, C, etc. dans l' .Les données de propriété.

Les classes peuvent utiliser d'autres parties de ma bibliothèque de classe, qui est tous là. Si vous décidez de l'utiliser, copiez les portions que vous voulez utiliser.

si vous êtes seulement intéressé par la mise en œuvre, il peut être trouvé dans le RangeExtensions.cs fichier, ligne 447 et plus, Méthode de L'échelle interne.

Vous pouvez:

1. tri de la liste de toutes les dates (en combinant les dates de et à)
2. alors en suivant cette liste, chaque nouvelle plage serait d'une date à la date suivante de début ou de fin qui est différente de la précédente.

pour nommer les nouvelles gammes, il serait logique d'avoir la liste des noms de gammes originales que contient la nouvelle gamme actuelle, et chaque fois que vous frappez une date de fin, supprimez l'ancien nom de gamme de la liste, et chaque tiem vous cliquez sur une date de début, ajoutez son nom à la liste.

Faire ceci:

Créer un Event classe.

class DateEvent : IComparable<DateEvent>
{
    public Date Date;
    public int DateRangeId;
    public bool IsBegin; // is this the start of a range?

    public int CompareTo(DateEvent other)
    {
        if (Date < other.Date) return -1;
        if (Date > other.Date) return +1;
        if (IsBegin && !other.IsBegin) return -1;
        if (!IsBegin && other.IsBegin) return +1;
        return 0;
    }
}

Définir List<DateEvent> events;

ajouter les dates de début et de fin de chaque fourchette dans la liste:

for (int i = 0; i < dateRanges.Length; ++i)
{
    DateRange r = dateRanges[i];
    events.Add(new DateEvent(r.BeginDate, i, true));
    events.Add(new DateEvent(r.EndDate, i, false));
}

triez les événements.

events.Sort();

Maintenant sortie de la classe:

class OutputDateRange
{
    public Date BeginDate;
    public Date EndDate;
    public List<string> Names;
}

enfin, parcourez les événements, en maintenant les plages présentes:

List<int> activeRanges;
List<OutputDateRange> output;
Date current = events[0].Date;
int i = 0;

while (i < events.Length;)
{
    OutputDateRange out = new OutputDateRange();
    out.BeginDate = current;

    // Find ending date for this sub-range.
    while (i < events.Length && events[i].Date == current)
    {
        out.EndDate = events[i].Date;
        if (events[i].IsBegin)
            activeRanges.Add(events[i].DateRangeId);
        else
            activeRanges.Remove(events[i].DateRangeId);
        ++i;
    }

    if (i < events.Length)
        current = events[i].Date;

    foreach (int j in activeRanges)
        out.Names.Add(dateRanges[j].Name);

    output.Add(out);
}

cela devrait faire l'affaire. Notez que je n'ai pas fait les constructeurs, et le code est un peu moche, mais espérons que l'exprime l'idée générale.

1. j'ai une liste d'abord, je ne sais pas sa longueur, mais j'ai eu 3 caractères
2. vérifier pour une fente, si un là? ajouter "A", Si B est là? ajouter le 'B', c là? ajouter "C"
3. aller à un autre emplacement, cycle 2
4. fin quand rien n'est ajouté à une autre nouvelle fente
5. j'ai eu la liste
6. aplatir la liste