/*
 Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
 in the Software without restriction, including without limitation the rights
 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 copies of the Software, and to permit persons to whom the Software is
 furnished to do so, subject to the following conditions:
 
 The above copyright notice and this permission notice shall be included in
 all copies or substantial portions of the Software.
 
 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 SOFTWARE.
*/

// C5 example: ViewPatterns 2005-07-22

// Compile with 
//   csc /r:C5.dll ViewPatterns.cs 

using System;
using C5;
using SCG = System.Collections.Generic;

namespace ViewPatterns {
  class Views {
    public static void Main(String[] args) {
      IList<char> lst = new ArrayList<char>();
      lst.AddAll<char>(new char[] { 'a', 'b', 'c', 'd' });
      IList<char> v1 = lst.View(1, 1);
      Console.WriteLine("v1 = {0}", v1);
      InsertBeforeFirst(v1, '<', 'b');
      InsertAfterFirst(v1, '>', 'b');
      Console.WriteLine("v1 = {0}", v1);
      char x; 
      if (SequencePredecessor(v1, 'b', out x)) 
        Console.WriteLine("Predecessor of b is " + x);
      if (SequenceSuccessor(v1, 'b', out x)) 
        Console.WriteLine("Successor of b is " + x);
      if (!SequencePredecessor(v1, 'c', out x)) 
        Console.WriteLine("c has no predecessor");
      if (!SequenceSuccessor(v1, 'a', out x)) 
        Console.WriteLine("a has no successor");
      IList<char> lst2 = new ArrayList<char>();
      lst2.AddAll<char>(new char[] { 'a', 'b', 'c', 'A', 'a', 'd', 'a' });
      foreach (int i in IndexesOf(lst2, 'a')) 
        Console.Write("{0} ", i);
      Console.WriteLine();
      foreach (int i in ReverseIndexesOf(lst2, 'a')) 
        Console.Write("{0} ", i);
      Console.WriteLine();
      Console.WriteLine(lst2);
      IList<char> view = lst2.View(2,0);
      InsertAtView(lst2, view, 'y');
      Console.WriteLine(lst2);
      InsertIntoView(view, 'x');
      Console.WriteLine(lst2);
    }

    // --- Patterns for zero-item views -----------------------------

    // Number of items before zero-item view
   
    public static int ItemsBefore<T>(IList<T> view) {
      return view.Offset;
    }

    // Number of items after zero-item view
   
    public static int ItemsAfter<T>(IList<T> view) {
      return view.Underlying.Count - view.Offset;
    }

    // Move (zero-item) view one item to the left
   
    public static void MoveLeft<T>(IList<T> view) {
      // One of these:
      view.Slide(-1);
      view.TrySlide(-1);
    }

    // Move (zero-item) view one item to the right
   
    public static void MoveRight<T>(IList<T> view) {
      // One of these:
      view.Slide(+1);
      view.TrySlide(+1);
    }

    // Test whether (zero-item) view is at beginning of list
   
    public static bool AtBeginning<T>(IList<T> view) {
      return view.Offset == 0;
    }

    // Test whether (zero-item) view is at end of list
   
    public static bool AtEnd<T>(IList<T> view) {
      return view.Offset == view.Underlying.Count;
    }

    // Insert x into zero-item view and into underlying list
   
    public static void InsertIntoView<T>(IList<T> view, T x) {
      view.Add(x);
    }

    // Insert x into list at zero-item view 
   
    public static void InsertAtView<T>(IList<T> list, IList<T> view, T x) {
      list.Insert(view, x);
    }

    // Delete the item before zero-item view 
   
    public static void DeleteBefore<T>(IList<T> view) {
      view.Slide(-1,1).RemoveFirst();
    }

    // Delete the item after zero-item view 
   
    public static void DeleteAfter<T>(IList<T> view) {
      view.Slide(0,1).RemoveFirst();
    }

    // Get the zero-item view at left endpoint.  Succeeds on all lists
    // and valid views.

    public static IList<T> LeftEndView<T>(IList<T> list) {
      return list.View(0,0);
    }

    // Get the zero-item view at right endpoint.  Succeeds on all
    // lists and valid views.

    public static IList<T> RightEndView<T>(IList<T> list) {
      return list.View(list.Count,0);
    }


    // --- Patterns for one-item views ------------------------------

    // Find the sequence predecessor x of y; or throw exception

    public static T SequencePredecessor<T>(IList<T> list, T y) {
      return list.ViewOf(y).Slide(-1)[0];
    }  
    
    // Find the sequence predecessor x of y; or return false 

    public static bool SequencePredecessor<T>(IList<T> list, T y, out T x) {
      IList<T> view = list.ViewOf(y);
      bool ok = view != null && view.TrySlide(-1);
      x = ok ? view[0] : default(T);
      return ok;
    }  

    // Find the sequence successor x of y; or throw exception

    public static T SequenceSuccessor<T>(IList<T> list, T y) {
      return list.ViewOf(y).Slide(+1)[0];
    }  

    // Find the sequence successor x of y; or return false

    public static bool SequenceSuccessor<T>(IList<T> list, T y, out T x) {
      IList<T> view = list.ViewOf(y);
      bool ok = view != null && view.TrySlide(+1);
      x = ok ? view[0] : default(T);
      return ok;
    }  

    // Insert x into list after first occurrence of y (or throw
    // NullReferenceException).
    
    public static void InsertAfterFirst<T>(IList<T> list, T x, T y) {
      list.Insert(list.ViewOf(y), x);
    }

    // Insert x into list before first occurrence of y (or throw
    // NullReferenceException)
    
    public static void InsertBeforeFirst<T>(IList<T> list, T x, T y) {
      list.Insert(list.ViewOf(y).Slide(0, 0), x);
    }

    // Insert x into list after last occurrence of y (or throw
    // NullReferenceException).
    
    public static void InsertAfterLast<T>(IList<T> list, T x, T y) {
      list.Insert(list.LastViewOf(y), x);
    }

    // Insert x into list before last occurrence of y (or throw
    // NullReferenceException)
    
    public static void InsertBeforeLast<T>(IList<T> list, T x, T y) {
      list.Insert(list.LastViewOf(y).Slide(0, 0), x);
    }

    // Same meaning as InsertBeforeFirst on a proper list, but not on
    // a view

    public static void InsertBeforeFirstAlt<T>(IList<T> list, T x, T y) {
      list.ViewOf(y).InsertFirst(x);
    }

    // Delete the sequence predecessor of first y; or throw exception

    public static T RemovePredecessorOfFirst<T>(IList<T> list, T y) {
      return list.ViewOf(y).Slide(-1).Remove();
    }

    // Delete the sequence successor of first y; or throw exception

    public static T RemoveSuccessorOfFirst<T>(IList<T> list, T y) {
      return list.ViewOf(y).Slide(+1).Remove();
    }

    // --- Other view patterns --------------------------------------

    // Replace the first occurrence of each x from xs by y in list:
    
    public static void ReplaceXsByY<T>(HashedLinkedList<T> list, T[] xs, T y) {
      foreach (T x in xs) {
        using (IList<T> view = list.ViewOf(x)) {
          if (view != null) { 
            view.Remove();
            view.Add(y);
          }
        }
      }
    }

    // Get index in underlying list of view's left end
    
    public static int LeftEndIndex<T>(IList<T> view) { 
      return view.Offset;
    }

    // Get index in underlying list of view's right end

    public static int RightEndIndex<T>(IList<T> view) { 
      return view.Offset + view.Count;
    }

    // Test whether views overlap 

    public static bool Overlap<T>(IList<T> u, IList<T> w) { 
      if (u.Underlying == null || u.Underlying != w.Underlying) 
        throw new ArgumentException("views must have same underlying list");
      else
        return u.Offset < w.Offset+w.Count && w.Offset < u.Offset+u.Count;
    }

    // Find the length of the overlap between two views

    public static int OverlapLength<T>(IList<T> u, IList<T> w) { 
      if (Overlap(u, w))
        return Math.Min(u.Offset+u.Count, w.Offset+w.Count) 
             - Math.Max(u.Offset, w.Offset);
      else
        return -1; // No overlap
    }

    // Test whether view u contains view v 

    public static bool ContainsView<T>(IList<T> u, IList<T> w) { 
      if (u.Underlying == null || u.Underlying != w.Underlying) 
        throw new ArgumentException("views must have same underlying list");
      else
        if (w.Count > 0)
          return u.Offset <= w.Offset && w.Offset+w.Count <= u.Offset+u.Count;
        else
          return u.Offset < w.Offset && w.Offset < u.Offset+u.Count;
    }

    // Test whether views u and v have (or are) the same underlying list

    public static bool SameUnderlying<T>(IList<T> u, IList<T> w) { 
      return (u.Underlying ?? u) == (w.Underlying ?? w);
    }

    // Find the index of the first item that satisfies p

    public static int FindFirstIndex<T>(IList<T> list, Fun<T,bool> p) {
      using (IList<T> view = list.View(0, 0)) {
        while (view.TrySlide(0, 1)) {
          if (p(view.First)) 
            return view.Offset;
          view.Slide(+1, 0);
        }
      }
      return -1;
    }

    // Find the index of the last item that satisfies p
    
    public static int FindLastIndex<T>(IList<T> list, Fun<T,bool> p) {
      using (IList<T> view = list.View(list.Count, 0)) {
        while (view.TrySlide(-1, 1)) {
          if (p(view.First)) 
            return view.Offset;
        }
      }
      return -1;
    }

    // Yield indexes of all items equal to x, in list order:

    public static SCG.IEnumerable<int> IndexesOf<T>(IList<T> list, T x) { 
      IList<T> tail = list.View(0, list.Count);
      tail = tail.ViewOf(x);
      while (tail != null) {
        yield return tail.Offset;
        tail = tail.Slide(+1,0).Span(list);
        tail = tail.ViewOf(x); 
      }
    }

    // Yield indexes of items equal to x, in reverse list order.

    public static SCG.IEnumerable<int> ReverseIndexesOf<T>(IList<T> list, T x) {
      IList<T> head = list.View(0, list.Count);
      head = head.LastViewOf(x);
      while (head != null) {
        yield return head.Offset;
        head = list.Span(head.Slide(0,0));
        head = head.LastViewOf(x);
      }
    }

  }
}