package list;

// listes simplement chaînées

public class Singly {
  public int element;
  public Singly next;
  
  public Singly(int element, Singly next) {
    this.element = element;
    this.next = next;
  }
  
  public static int length(Singly s) {
    int len = 0;
    for ( ; s != null; s = s.next)
      len++;
    return len;
  }
  
  public static boolean contains(Singly s, int x) {
    while (s != null) {
      if (s.element == x) return true;
      s = s.next;
    }
    return false;
  }
  
  public static int get(Singly s, int i) {
    for (; s != null; s = s.next)
      if (i-- == 0) return s.element;
    throw new IllegalArgumentException();
  }
  
  /* algorithme de détection de cycle de Floyd
   * (dit algorithme du lièvre et de la tortue)
   */
  public static boolean hasCycle(Singly s) {
    if (s == null) return false;
    Singly tortoise = s, hare = s.next;
    while (tortoise != hare) {
      if (hare == null) return false;
      hare = hare.next;
      if (hare == null) return false;
      hare = hare.next;
      tortoise = tortoise.next;
    }
    return true;
  }

  // variante : le lièvre va deux fois plus loin à chaque fois,
  // et la tortue avance à chaque fois jusqu'à la position précédente
  public static boolean hasCycle2(Singly s) {
    Singly t = s, h = s;
    for (int n = 1; true; n *= 2) {
      for (int k = 0; k < n  ; k++) { if (h == null) return false; h = h.next; }
      for (int k = 0; k < n-1; k++) { if (t == h   ) return true;  t = t.next; }
      t = t.next; assert t==h;
    }
  }

  /* tirage aléatoire dans une liste
   * (en un seul parcours)
   */
  public static int randomElement(Singly s) {
    if (s == null) throw new IllegalArgumentException();
    int candidate = 0, index = 1;
    while (s != null) {
      if ((int)(index * Math.random()) == 0) candidate = s.element;
      index++;
      s = s.next;
    }
    return candidate;
  }
    
  public static String listToString(Singly s) {
    StringBuffer sb = new StringBuffer("[");
    while (s != null) {
      sb.append(s.element);
      if (s.next != null) sb.append(" -> ");
      s = s.next;
    }
    return sb.append("]").toString();
  }
  
  public String toString() {
    return listToString(this);
  }
  
  public static void main(String[] args) {
    Singly x = new Singly(1, new Singly(2, new Singly(3, null)));
    System.out.println(listToString(x));
    System.out.println(x);
    assert (Singly.get(x, 0) == 1);
    assert (Singly.get(x, 1) == 2);
    assert (Singly.get(x, 2) == 3);
    assert Singly.length(x) == 3;
    try { Singly.get(x, 3); assert false; } catch (IllegalArgumentException e) {};
    try { Singly.get(x, -1); assert false; } catch (IllegalArgumentException e) {};
    System.out.println("Singly OK");
  }
}