Conception de la structure de données : ensemble donné de paires semaine/jour, obtenir les jours adjacents dans l'ensemble?

Question

Je besoin d'un moyen de représenter des informations sur les semaines et les jours comme suit :

W1: D1,D2
W2: D1,D5
W3: D3,D2

de sorte que, étant donné ma semaine actuelle et mon jour, je devrais être capable de obtenir le jour précédent et le jour suivant

Par exemple :

si(jourActuel = W2D5)
{
    jourPrécédent = W2D1;
    jourSuivant = W3D3;
}

Voici deux options que j'ai envisagées :

1. Utiliser une treemap

   TreeMap< Integer,TreeMap< Integer>>

Dans la treemap externe, stocker le numéro de semaine comme clé et dans la treemap interne, stocker le

1. Utiliser un tableau [w1d1,w2d2,w2d1...]

Quelle serait une bonne structure de données à utiliser pour un tel problème ?

Answer 1

Pourquoi ne pas simplement utiliser une collection bien ordonnée sur un type WeekDay? (Le type WeekDay inclut une semaine et un jour et fournit un ordre bien défini.)

Si tel était le cas, TreeSet pourrait être utilisé avec higher/lower (ou même headSet/tailSet).

TreeSet days = ...;
WeekDay nextDay = days.higher(currentDay);

Malheureusement TreeSet (ou PriorityQueue) et d'autres types de données standard ne fonctionneront pas car ils manquent d'une méthode pour itérer vers l'avant/vers l'arrière à partir d'un élément donné. Cela n'est pas strictement vrai, au moins TreeMap peut être utilisé, simplement avec une recherche manuelle en O(1) en utilisant l'itérateur : cependant, les opérations requises pour tirer parti de l'accès en O(lg n) ne sont tout simplement pas "standard" dans un TreeSet.

Cet article sur les Listes Triées en Java couvre un tas de choses intéressantes, tout en fournissant une implémentation qui pourrait être adaptée.

Bien sûr, il est également possible d'utiliser simplement un ArrayList et de le garder trié lors d'une mise à jour. Dans ce cas, un Collections.binarySearch peut être utilisé et l'index pour le précédent/suivant est facilement fourni :)

Bon codage.

Answer 2

J'aime les enums:

class Pair {
    enum Day { lun,mar,mer,jeu,ven;
        Day suivant() {
            retourner valeurs()[(ordinal()+1)%jours];
        }
        Day precedent() {
            retourner valeurs()[(jours+ordinal()-1)%jours];
        }
        statique final int jours=valeurs().longueur;
    }
    enum Semaine { s1,s2,s3;
    Semaine suivant() {
        retourner ordinal()0)
            retourner nouvelle Pair(semaine,jour.precedent());
        autrement retourner nouvelle Pair(semaine.precedent(),Day.ven);
    }
    public String toString() {
        si(semaine==null||jour==null)
            retourner "*** ***";
        retourner semaine+" "+jour;
    }
    final Day jour;
    final Semaine semaine;
}
public class Main {
    public static void main(String[] args) {
        pour(Semaine semaine:Semaine.valeurs())
            pour(Jour jour:Jour.valeurs()) {
                Pair paire=new Pair(semaine,jour);
                System.out.println(paire.precedent()+" "+paire+" "+paire.suivant());
            }
    }
}

*** *** s1 lun s1 mar
s1 lun s1 mar s1 mer
s1 mar s1 mer s1 jeu
s1 mer s1 jeu s1 ven
s1 jeu s1 ven s2 lun
s1 ven s2 lun s2 mar
s2 lun s2 mar s2 mer
s2 mar s2 mer s2 jeu
s2 mer s2 jeu s2 ven
s2 jeu s2 ven s3 lun
s2 ven s3 lun s3 mar
s3 lun s3 mar s3 mer
s3 mar s3 mer s3 jeu
s3 mer s3 jeu s3 ven
s3 jeu s3 ven *** ***

Answer 3

Créez une enum comme ceci

public enum WeekAndDay {
    W1D1(1, 1), W1D2(1, 2) // ...

    private int semaine;
    private int jour;

    private WeekAndDay(int semaine, int jour) {
        this.semaine = semaine; this.jour = jour;
    }
    ...
}

Ceci a un ordre naturel et peut être utilisé comme une clé dans un TreeMap; par exemple

    TreeMap map = ...

ou utilisé pour ordonner une liste d'enregistrements (en supposant que les enregistrements ont une clé déclarée de manière appropriée); par exemple

ArrayList enregistrements = ...
Collections.sort(enregistrements, new Comparator{
        public int compare(Info i1, Info i2) {
            return i1.getWeekAndDay().compareTo(i2.getWeekAndDay());
        }});

---

SUIVI

Dans mon cas, le nombre de semaines et de jours n'est pas connu à l'avance, donc la création d'une énumération ne fonctionnerait pas.

(Cela pourrait fonctionner si vous faites certaines hypothèses / placez certaines limites sur le nombre de valeurs WeekAndDay requises ... mais je suppose que vous ne voulez pas le faire.)

Vous pourriez créer une classe qui se comporte comme une sorte d'énumération dynamique.

• Pas de constructeur public.
• Une méthode de fabrique qui utilise une map de sorte qu'il y ait une instance unique pour chaque paire semaine / jour.
• Une méthode de fabrique surchargée qui prend une chaîne comme argument, par exemple "W1D1".
• Une méthode toString() qui se rend en format "W1D1".

Cependant, en général, vous ne pourrez pas écrire du code comme ceci (issu de votre question !):

if (currentDay == W2D5) {
    prevDay = W2D1;
    nextDay = W3D3;
}

Cela nécessiterait que votre code déclare explicitement un tas de constantes comme ceci :

public static final WeekAndDay W2D5 = WeekAndDay.getInstance("W2D5"); 
public static final WeekAndDay W2D1 = WeekAndDay.getInstance("W2D1"); 
public static final WeekAndDay W3D3 = WeekAndDay.getInstance("W3D3"); 

En général, vous ne pouvez pas le faire pour toutes les combinaisons semaine / jour si le nombre de jours et de semaines ne sont pas connus à l'avance.

(D'accord, vous pouvez le faire, mais seulement si l'ensemble de constantes que vous voulez utiliser dans votre code est connu à l'avance. J'exclus la réflexion ici car ce serait une mauvaise solution.)