Infinity/-infinity pour l'insertion de liste de choix avec un type inconnu?

Question

Je suis la mise en œuvre d'une liste de saut comme:

template<typename Key, typename Value> class SkipList {...} 

En explications que j'ai vu en ligne, la tête et la queue des listes de saut ont des clés à l'infini infini/négatif, mais ils sont tous utilisés avec les touches numériques .

je peux supposer que < et == opérateurs sont disponibles pour les clés, donc je n'ai pas à vous soucier string < string

Mais, comment puis-je trouver une valeur pour le plus petit/grand genre à avoir la tête/pointeurs de queue? Y at-il quelque chose comme INT_MAX ou INT_MIN mais pour tout type?

Answer 1

Vous pouvez utiliser deux propriétés et private SkipListItem<K, E> posInfinity; et comparer ultérieurement les objets SkipListItems.

Voici comment je suis allé à ce sujet:

private SkipListItem<K, E> negInfinity; 
private SkipListItem<K, E> posInfinity; 

public SkipListDictionary(K[] keys, E[] elements) { 

    this.randomGenerator = new Random(); 
    this.negInfinity = new SkipListItem<K, E>(); 
    this.posInfinity = new SkipListItem<K, E>(); 

    this.constructSkipList(keys, elements); 
} 

Et puis plus tard ...:

private SkipListItem<K, E> searchKey(K key) { 

    SkipListItem<K, E> currentElement = this.lastListStart; 

    while(currentElement.lower != null) { 

     currentElement = currentElement.lower; 

     while(currentElement.next != null && currentElement.next.getItem() != posInfinity && 
       currentElement.next.getKey().compareTo(key) < 1) { 

      currentElement = currentElement.next; 
     } 
    } 

    return currentElement; 
} 

PS: J'ai utilisé une propriété referenceItem pour les listes supérieures pour faire référence à un bas SkipListItem pour une construction plus facile, c'est pourquoi il y a ce getItem qui renvoie un SkipListItem. Je ne pense pas que ce soit la meilleure façon de le résoudre, c'est juste ce que je suis allé chercher.