Created
February 6, 2010 20:35
-
-
Save jwachter/296945 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package de.johanneswachter.education.scala.listprocessing { | |
| /** | |
| * <p>The <code>ListProcessing</code> object contains a number of methods to demonstrate | |
| * functional list handling with <i>Scala</i>. Each method performs operations | |
| * on <code>List</code>s to fit a specific scenario.<p> | |
| * | |
| * <p>This functions have been implemented as part of the exercises during the <i>FPUS</i> course | |
| * at the <i>University of Applied Sciences Mannheim</i> in the <i>winter semester 2009</i></p> | |
| */ | |
| object ListProcessing { | |
| /** | |
| * Creates a list containing all suffixes of the given <code>List</code>. | |
| * | |
| * @param l the list the suffixes are created for. | |
| * @return a <code>List</code> containing all suffixes valid for the given list. | |
| */ | |
| def suffixes[T](l:List[T]):List[List[T]] = l match { | |
| case(Nil) => Nil | |
| case(list) => list :: suffixes(list.tail) | |
| } | |
| /** | |
| * Returns if the given second list is contained as a sublist inside the | |
| * first list. | |
| * @param l1 the base list. | |
| * @param l2 the sublist to check the base list for. | |
| * @return if <code>l2</code> is (completely) contained as a sublist inside <code>l1</code>. | |
| */ | |
| def contains[T](l1:List[T], l2:List[T]):Boolean= (l1,l2) match { | |
| case (Nil,Nil) => true // Return true if both lists are empty | |
| case (Nil,_) => false // return false if only the base list is empty | |
| case (l, l2) => findStart(l,l2) // go through list until element matches head of list to compare | |
| } | |
| def contains2[T](l1:List[T], l2:List[T]):Boolean= { | |
| (l1.intersect(l2) == l2) | |
| } | |
| /** | |
| * <p>Get through the first list until a starting point to compare it with the second list is found.</p> | |
| * | |
| * <p>Returns the result of checking from a found start with the second list. If no start is found false | |
| * is returned.</p> | |
| * | |
| * @param l the base list. | |
| * @param l2 the list that is supposed to be a sublist of <code>l</code>. | |
| * @return <code>true</code> if <code>l2</code> is a sublist of <code>l</code>, <code>false</code> otherwise. | |
| */ | |
| private def findStart[T](l:List[T], l2:List[T]):Boolean = (l,l2) match { | |
| case (Nil,Nil) => true // emtpy lists are equal | |
| case (Nil, _) => false // return false if we have not found a start | |
| case (list,list2) => ((list.head == list2.head) && compareLists(list.tail, list2.tail))|| findStart(list.tail,list2) // heads match & compare || look for another startpoint | |
| } | |
| /** | |
| * <p>Compares the given lists and returns the result.</p> | |
| * | |
| * @param l the base list. | |
| * @param tc the sublist. | |
| * @return returns if <code>tc</code> is contained inside <code>l</code>. | |
| */ | |
| private def compareLists[T](l:List[T], tc:List[T]):Boolean= (l,tc) match { | |
| case (Nil, Nil) => true // both lists empty => match | |
| case (Nil, _) => false // list empty but we have elements to compare leftover | |
| case (list, remains) => (l.head == remains.head) && compareLists(l.tail, remains.tail) // concatenate checks until heads of remaining lists aren't equal | |
| } | |
| /** | |
| * <p>Splits a list into groups containing the given number of elements.</p> | |
| * | |
| * @param cs the group size. | |
| * @param l the list to extract the groups from. | |
| * @return a list containing the groups. | |
| */ | |
| def groups[T](cs:Int, l:List[T]):List[List[T]] = { | |
| def group(l:List[T], cs:Int):List[List[T]]=l match { | |
| case (Nil) => Nil // no elements => no group | |
| case l => l.take(cs) :: group(l.drop(cs), cs) // extract chop size elements and group the rest of the list | |
| } | |
| (l,cs) match { | |
| case (Nil,_) => Nil // No list, nothing to do | |
| case (_,0) => List(l) // Any list but no chopping | |
| case (l,cs) => group(l,cs) // normal case, group the elements | |
| } | |
| } | |
| /** | |
| * Returns a <code>Boolean</code> indicating if the list contain exactly the same elements. The ordering within | |
| * the list doesn't matter. | |
| * | |
| * @param l1 the first list. | |
| * @param l2 the second list. | |
| * @return true when elements are identical, false otherwise. | |
| */ | |
| def sameElems[T](l1:List[T], l2:List[T]):Boolean={ | |
| (l1.length == l2.length) && (l1 -- l2).isEmpty | |
| } | |
| /** | |
| * Returns a list of pairs containing a selected element and the remaining list without | |
| * this element. | |
| * | |
| * @param l the list to pick the selections from. | |
| * @return a list containing pairs of one element and the remaining list. | |
| */ | |
| def selections[T](l:List[T]):List[(T,List[T])]={ | |
| def select(selections:List[T], list:List[T]):List[(T,List[T])]= selections match{ | |
| case (Nil) => Nil | |
| case (_) => (selections.head, extract(list, selections.head)) :: select(selections.tail, list) | |
| } | |
| def extract(l:List[T], e:T):List[T]={ | |
| l match { | |
| case Nil => Nil | |
| case list if(list.head == e) => extract(list.tail, e) | |
| case _ => l.head :: extract(l.tail, e) | |
| } | |
| } | |
| select(l,l) | |
| } | |
| def selections2[T](l:List[T]):List[(T, List[T])]={ | |
| def select(e:List[T], l:List[T]):List[(T,List[T])]={ | |
| l match { | |
| case Nil => Nil | |
| case head::Nil => List((head, e)) | |
| case head::tail => (l.head, e ::: l.tail) :: select(e ::: List(l.head), l.tail) | |
| } | |
| } | |
| l match { | |
| case Nil => Nil | |
| case head::tail => (head, tail) :: select(List(head), tail) | |
| } | |
| } | |
| /** | |
| * [1, 2, 3, 4] | |
| * (2, [3,4]) (2, [1,3,4]) | |
| * (3, [2,4]) => (3, [1,2,4]) | |
| * (4, [2,3]) (4, [1,2,3]) | |
| * (1, [2,3,4]) | |
| * @param l The list with the | |
| */ | |
| def selections3[T](l:List[T]):List[(T,List[T])] = l match { | |
| case Nil => Nil | |
| case hd::tl => (hd, tl) :: selections3(tl).map((x)=>(x._1, (hd :: x._2))) | |
| } | |
| /** | |
| * Calculates all the amounts you can pay with the given set of coins. | |
| * @param l he coins you have | |
| * @return a list of the possible amounts | |
| */ | |
| def amounts(l:List[Int]):List[Int] = { | |
| /** | |
| * Calculates the sum for a list of possible selections for a first coin. | |
| * @param sl selections for start values and remainders. | |
| * @return the amounts payable. | |
| */ | |
| def sum(sl:List[(Int, List[Int])]):List[Int]={ | |
| sl match { | |
| case Nil => Nil | |
| // Take the heads selection, add up the suffixes and sum the selections on the suffixes. Also concat the sum of the remaining selections. | |
| case s => s.head._1 :: sumSuffixes(s.head._1, ListProcessing.suffixes(s.head._2)) ::: sum(ListProcessing.selections(s.head._2)) ::: sum(s.tail) | |
| } | |
| } | |
| /** | |
| * Calculates the amounts available through all suffixes in the list together | |
| * with the base. | |
| * | |
| * @param base the base value. | |
| * @param lists the suffixes. | |
| * @return a list of possible amounts. | |
| */ | |
| def sumSuffixes(base:Int, lists:List[List[Int]]):List[Int]={ | |
| lists match { | |
| case (Nil) => Nil | |
| case (l) => (base + sumList(l.head)) :: sumSuffixes(base, l.tail) | |
| } | |
| } | |
| /** | |
| * Sums up the values in a list in a recursive way. | |
| * @param l the list of <code>Int</code> values. | |
| * @return the sum. | |
| */ | |
| def sumList(l:List[Int]):Int={ | |
| l match { | |
| case (Nil) => 0 // 0 when list is empty | |
| case (hd::Nil) => hd // head when only head remains | |
| case (l) => l.head + sumList(l.tail) // head + sum of tail | |
| } | |
| } | |
| // Start with initial set of selections | |
| val sums = sum(ListProcessing.selections(l)) | |
| // Remove duplicates and sort | |
| sums.removeDuplicates.sort((e1,e2)=>(e1 < e2)) | |
| } | |
| /** | |
| * Computes which amounts two persons can change each other based on the sets of coins | |
| * both of them posses. | |
| * | |
| * @param p1 coins in pocket of person 1. | |
| * @param p2 coins in pocket of person 2. | |
| * @return the amounts both can exchange each other. | |
| */ | |
| def withChange(p1:List[Int],p2:List[Int]):List[Int]={ | |
| ListProcessing.amounts(p1).intersect(ListProcessing.amounts(p2)) | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment