diff options
author | jsdelfino <jsdelfino@13f79535-47bb-0310-9956-ffa450edef68> | 2009-09-27 20:04:28 +0000 |
---|---|---|
committer | jsdelfino <jsdelfino@13f79535-47bb-0310-9956-ffa450edef68> | 2009-09-27 20:04:28 +0000 |
commit | 215c005bde88752999978adce56b09d2a90a13b7 (patch) | |
tree | d4371936d0c26e24b610cf5f17145a7425ca37d7 /cpp/sca/kernel/list.hpp | |
parent | 49ba52239afa0e6ab295add695a7443633748cfc (diff) |
Moved some sources up in the directory tree to attempt to simplify the directory structure a bit, and some minor refactoring.
git-svn-id: http://svn.us.apache.org/repos/asf/tuscany@819394 13f79535-47bb-0310-9956-ffa450edef68
Diffstat (limited to 'cpp/sca/kernel/list.hpp')
-rw-r--r-- | cpp/sca/kernel/list.hpp | 379 |
1 files changed, 379 insertions, 0 deletions
diff --git a/cpp/sca/kernel/list.hpp b/cpp/sca/kernel/list.hpp new file mode 100644 index 0000000000..ef493b19ca --- /dev/null +++ b/cpp/sca/kernel/list.hpp @@ -0,0 +1,379 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +/* $Rev$ $Date$ */ + +#ifndef tuscany_list_hpp +#define tuscany_list_hpp + +/** + * Simple list functions. + */ + +#include <iostream> +#include "function.hpp" + +namespace tuscany { + +long countlists = 0; +long countIlists = 0; +long countClists = 0; +long countElists = 0; + +bool resetlistCounters() { + countlists = countIlists = countClists = countElists = 0; + return true; +} + +bool printlistCounters() { + std::cout << "countlists " << countlists << std::endl; + std::cout << "countElists " << countElists << std::endl; + std::cout << "countIlists " << countIlists << std::endl; + std::cout << "countClists " << countClists << std::endl; + return true; +} + +/** + * A car/cdr lisp-like pair, base structure to construct lists. + */ + +template<typename T> class list { +public: + + list(const T car, const lambda<list<T> ()>& cdr) : + nil(false), car(car), cdr(cdr) { + countlists++; + countIlists++; + } + + list() : + nil(true) { + countlists++; + countElists++; + } + + list(const list& p) : + nil(p.nil), car(p.car), cdr(p.cdr) { + countlists++; + countClists++; + } + + const list& operator=(const list<T>& p) { + if(this == &p) + return *this; + nil = p.nil; + car = p.car; + cdr = p.cdr; + return *this; + } + + ~list() { + countlists--; + } + + const bool operator==(const list<T>& p) const { + if(this == &p) + return true; + if(nil) + return p.nil; + if(p.nil) + return false; + if(!(car == p.car)) + return false; + if(cdr == p.cdr) + return true; + return cdr() == p.cdr(); + } + + const bool operator!=(const list<T>& p) const { + return !this->operator==(p); + } + + template<typename X> friend std::ostream& operator<<(std::ostream&, const list<X>&); + + bool nil; + T car; + lambda<list<T> ()> cdr; +}; + +/** + * Returns true if the given list is nil. + */ +template<typename T> const bool isNil(const list<T>& p) { + return p.nil; +} + +/** + * Write a list to an output stream. + */ +template<typename X> std::ostream& operator<<(std::ostream& out, const list<X>& l) { + if(l == list<X> ()) + return out << "()"; + return out << "(" << car(l) << ", " << cdr(l) << ")"; +} + +/** + * Construct a (lazy) list from a value and a lambda function that returns the cdr. + */ +template<typename T> const list<T> cons(const T& car, const lambda<list<T> ()>& cdr) { + return list<T> (car, cdr); +} + +/** + * Construct a list from a value and a cdr list. + */ +template<typename T> const list<T> cons(const T& car, const list<T>& cdr) { + return list<T> (car, unit(cdr)); +} + +/** + * Construct a list of one value. + */ +template<typename T> const list<T> makeList(const T& car) { + return list<T> (car, unit(list<T> ())); +} + +/** + * Construct a list of two values. + */ +template<typename T> const list<T> makeList(const T& a, const T& b) { + return cons(a, makeList(b)); +} + +/** + * Construct a list of three values. + */ +template<typename T> const list<T> makeList(const T& a, const T& b, const T& c) { + return cons(a, cons(b, makeList(c))); +} + +/** + * Construct a list of four values. + */ +template<typename T> const list<T> makeList(const T& a, const T& b, const T& c, const T& d) { + return cons(a, cons(b, cons(c, makeList(d)))); +} + +/** + * Returns the car of a list. + */ +template<typename T> const T car(const list<T>& p) { + return p.car; +} + +/** + * Returns the cdr of a list. + */ +template<typename T> list<T> const cdr(const list<T>& p) { + return p.cdr(); +} + +/** + * Returns the car of the cdr of a list. + */ +template<typename T> const T cadr(const list<T>& p) { + return car(cdr(p)); +} + +/** + * Returns the car of the cdr of the cdr of a list. + */ +template<typename T> const T caddr(const list<T>& p) { + return car(cdr(cdr(p))); +} + +/** + * Returns the cdr of a cdr of a list. + */ +template<typename T> const list<T> cddr(const list<T>& p) { + return cdr(cdr(p)); +} + +/** + * Returns the cdr of a cdr of the cdr of a list. + */ +template<typename T> const list<T> cdddr(const list<T>& p) { + return cdr(cdr(cdr(p))); +} + +/** + * Returns the length of a list. + */ +template<typename T> struct lengthRef { + const int operator()(const int c, const list<T>& p) { + if(isNil(p)) + return c; + return (*this)(c + 1, cdr(p)); + } +}; + +template<typename T> const int length(const list<T>& p) { + return lengthRef<T> ()(0, p); +} + +/** + * Appends a list and a lambda function returning a list. + */ +template<typename T> struct appendCdr { + const list<T> a; + const lambda<list<T> ()> fb; + appendCdr(const list<T>& a, const lambda<list<T> ()>& fb) : + a(a), fb(fb) { + } + const list<T> operator()() const { + return append(a, fb); + } +}; + +template<typename T> const list<T> append(const list<T>&a, const lambda<list<T> ()>& fb) { + if(isNil(a)) + return fb(); + + return cons(car(a), lambda<list<T> ()> (appendCdr<T> (cdr(a), fb))); +} + +/** + * Appends two lists. + */ +template<typename T> const list<T> append(const list<T>&a, const list<T>& b) { + return append(a, unit(b)); +} + +/** + * Map a lambda function on a list. + */ +template<typename T, typename R> const list<R> map(const lambda<R(T)>& f, const list<T>& p) { + if(isNil(p)) + return list<R> (); + return cons(f(car(p)), map(f, cdr(p))); +} + +/** + * Run a reduce lambda function on a list. + */ +template<typename T, typename R> struct reduceAccumulate { + const lambda<R(R, T)> f; + explicit reduceAccumulate(const lambda<R(R, T)>& f) : + f(f) { + } + R operator()(const R& acc, const list<T>& p) const { + if(isNil(p)) + return acc; + return (*this)(f(acc, car(p)), cdr(p)); + } +}; + +template<typename T, typename R> const R reduce(const lambda<R(R, T)>& f, const R& initial, const list<T>& p) { + return reduceAccumulate<T, R> (f)(initial, p); +} + +/** + * Run a filter lambda function on a list. + */ +template<typename T> const list<T> filter(const lambda<bool(T)>& f, const list<T>& p) { + if(isNil(p)) + return list<T> (); + if(f(car(p))) { + const lambda<list<T> (lambda<bool(T)> , list<T> )> ff(filter<T> ); + return cons(car(p), curry(ff, f, cdr(p))); + } + return filter(f, cdr(p)); +} + +/** + * Returns a list pointing to a member of a list. + */ +template<typename T> const list<T> member(const T& t, const list<T>& p) { + if(isNil(p)) + return list<T> (); + if(t == car(p)) + return p; + return member(t, cdr(p)); +} + +/** + * Reverse a list. + */ +template<typename T> const list<T> reverseIter(const list<T>& acc, const list<T>& p) { + if(isNil(p)) + return acc; + return reverseIter(cons(car(p), acc), cdr(p)); +} + +template<typename T> const list<T> reverse(const list<T>& p) { + return reverseIter(list<T> (), p); +} + +template<typename T> const list<T> seq(const T& start, const T& end); + +template<typename T> struct seqGenerate { + const T start; + const T end; + seqGenerate(const T& start, const T&end) : + start(start), end(end) { + } + const list<T> operator()() const { + return seq<T> (start, end); + } +}; + +/** + * Returns a sequence of values between the given bounds. + */ +template<typename T> const list<T> seq(const T& start, const T& end) { + if(start == end) + return makeList(start); + if(start < end) + return cons(start, lambda<list<T> ()> (seqGenerate<T> (start + 1, end))); + return cons(start, lambda<list<T> ()> (seqGenerate<T> (start - 1, end))); +} + +/** + * Equivalent of the list assoc function. + */ +template<typename T> const list<T> assoc(const T& k, const list<list<T> >& p) { + if(isNil(p)) + return list<T> (); + if(k == car(car(p))) + return car(p); + return assoc(k, cdr(p)); +} + +/** + * Pretty print a list. + */ +template<typename T> std::ostream& print(const list<T>& l, std::ostream& os) { + os << "("; + if (!isNil(l)) { + list<T> ml = l; + while(true) { + os << car(ml); + ml = cdr(ml); + if (isNil(ml)) + break; + os << ", "; + } + } + os << ")"; + return os; +} + +} + +#endif /* tuscany_list_hpp */ |