From dc15dc32bb3348c760ba3643c083af7e0c8e43fe Mon Sep 17 00:00:00 2001 From: jsdelfino Date: Sat, 25 Dec 2010 01:49:19 +0000 Subject: Create a sandbox branch to experiment with latest APR. git-svn-id: http://svn.us.apache.org/repos/asf/tuscany@1052740 13f79535-47bb-0310-9956-ffa450edef68 --- sandbox/sebastien/cpp/apr-2/kernel/list.hpp | 587 ++++++++++++++++++++++++++++ 1 file changed, 587 insertions(+) create mode 100644 sandbox/sebastien/cpp/apr-2/kernel/list.hpp (limited to 'sandbox/sebastien/cpp/apr-2/kernel/list.hpp') diff --git a/sandbox/sebastien/cpp/apr-2/kernel/list.hpp b/sandbox/sebastien/cpp/apr-2/kernel/list.hpp new file mode 100644 index 0000000000..a8dbcc1b0c --- /dev/null +++ b/sandbox/sebastien/cpp/apr-2/kernel/list.hpp @@ -0,0 +1,587 @@ +/* + * 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 +#include "string.hpp" +#include "fstream.hpp" +#include "function.hpp" + +namespace tuscany { + +#ifdef WANT_MAINTAINER_MODE + +/** + * Debug utilities. Counters used to track instances of lists, and + * macro used to write the contents of a list in a string, easier to + * watch in a debugger than the list itself. + */ +long countLists = 0; +long countILists = 0; +long countCLists = 0; +long countELists = 0; + +bool resetListCounters() { + countLists = countILists = countCLists = countELists = 0; + return true; +} + +bool checkListCounters() { + return countLists == 0; +} + +bool printListCounters() { + cout << "countLists " << countLists << endl; + cout << "countELists " << countELists << endl; + cout << "countILists " << countILists << endl; + cout << "countCLists " << countCLists << endl; + return true; +} + +#else + +#define resetListCounters() +#define checkListCounters() true +#define printListCounters() + +#endif + +#ifdef WANT_MAINTAINER_WATCH + +#define debug_watchList() do { \ + this->watch = watchList(*this); \ + } while (0) + +#else + +#define debug_watchList(); + +#endif + +/** + * A car/cdr lisp-like pair, base structure to construct lists. + */ + +template class list { +public: + + list() { + debug_inc(countLists); + debug_inc(countELists); + debug_watchList(); + } + + list(const T car, const lambda()>& cdr) : car(car), cdr(cdr) { + debug_inc(countLists); + debug_inc(countILists); + debug_watchList(); + } + + list(const list& p) : car(p.car), cdr(p.cdr) { + debug_inc(countLists); + debug_inc(countCLists); +#ifdef WANT_MAINTAINER_WATCH + watch = p.watch; +#endif + } + + const list& operator=(const list& p) { + if(this == &p) + return *this; + car = p.car; + cdr = p.cdr; +#ifdef WANT_MAINTAINER_WATCH + watch = p.watch; +#endif + return *this; + } + + ~list() { + debug_dec(countLists); + } + + const bool operator==(const list& p) const { + if(this == &p) + return true; + if(isNil(cdr)) + return isNil(p.cdr); + if(isNil(p.cdr)) + return false; + if(!(car == p.car)) + return false; + if(cdr == p.cdr) + return true; + return cdr() == p.cdr(); + } + + const bool operator<(const list& p) const { + if(this == &p) + return false; + if (isNil(cdr)) + return !isNil(p.cdr); + if (isNil(p.cdr)) + return false; + if (car < p.car) + return true; + if (car != p.car) + return false; + return cdr() < p.cdr(); + } + + const bool operator>(const list& p) const { + if(this == &p) + return false; + if (isNil(cdr)) + return false; + if (isNil(p.cdr)) + return true; + if (car > p.car) + return true; + if (car != p.car) + return false; + return cdr() > p.cdr(); + } + + const bool operator!=(const list& p) const { + return !this->operator==(p); + } + + operator const list >() const { + return (list >)T(*this); + } + +private: +#ifdef WANT_MAINTAINER_WATCH + template friend const string watchList(const list& p); + string watch; +#endif + + template friend const bool isNil(const list& p); + template friend const X car(const list& p); + template friend const list cdr(const list& p); + + T car; + lambda()> cdr; +}; + +#ifdef WANT_MAINTAINER_WATCH + +/** + * Debug utility used to write the contents of a list to a string, easier + * to watch than the list itself in a debugger. + */ +template const string watchList(const list& p) { + if(isNil(p)) + return "()"; + odebugstream os; + os << "(" << car(p) << " ...)"; + return str(os); +} + +#endif + +/** + * Returns true if the given list is nil. + */ +template const bool isNil(const list& p) { + return isNil(p.cdr); +} + +/** + * Write a list to an output stream. + */ +template ostream& writeHelper(ostream& out, const list& l) { + if (isNil(l)) + return out; + out << " " << car(l); + return writeHelper(out, cdr(l)); +} + +template ostream& operator<<(ostream& out, const list& l) { + if(isNil(l)) + return out << "()"; + out << "(" << car(l); + writeHelper(out, cdr(l)); + return out << ")"; +} + +/** + * Construct a (lazy) list from a value and a lambda function that returns the cdr. + */ +template const list cons(const T& car, const lambda()>& cdr) { + return list (car, cdr); +} + +/** + * Construct a list from a value and a cdr list. + */ +template const list cons(const T& car, const list& cdr) { + return list (car, result(cdr)); +} + +/** + * Cons variations for use with the reduce and reduceRight functions. + */ +template const list lcons(const list& cdr, const T& car) { + return cons(car, cdr); +} + +template const list rcons(const T& car, const list& cdr) { + return cons(car, cdr); +} + +/** + * Construct a list of one value. + */ +template const list mklist(const T& car) { + return list (car, result(list ())); +} + +/** + * Construct a list of two values. + */ +template const list mklist(const T& a, const T& b) { + return cons(a, mklist(b)); +} + +/** + * Construct a list of three values. + */ +template const list mklist(const T& a, const T& b, const T& c) { + return cons(a, cons(b, mklist(c))); +} + +/** + * Construct a list of four values. + */ +template const list mklist(const T& a, const T& b, const T& c, const T& d) { + return cons(a, cons(b, cons(c, mklist(d)))); +} + +/** + * Construct a list of five values. + */ +template const list mklist(const T& a, const T& b, const T& c, const T& d, const T& e) { + return cons(a, cons(b, cons(c, cons(d, mklist(e))))); +} + +/** + * Construct a list of six values. + */ +template const list mklist(const T& a, const T& b, const T& c, const T& d, const T& e, const T& f) { + return cons(a, cons(b, cons(c, cons(d, cons(e, mklist(f)))))); +} + +/** + * Returns the car of a list. + */ +template const T car(const list& p) { + // Abort if trying to access the car of a nil list + assert(!isNil(p.cdr)); + return p.car; +} + +/** + * Returns the cdr of a list. + */ +template const list cdr(const list& p) { + return p.cdr(); +} + +/** + * Returns the car of the cdr (the 2nd element) of a list. + */ +template const T cadr(const list& p) { + return car(cdr(p)); +} + +/** + * Returns the 3rd element of a list. + */ +template const T caddr(const list& p) { + return car(cdr(cdr(p))); +} + +/** + * Returns the 4th element of a list. + */ +template const T cadddr(const list& p) { + return car(cdr(cdr(cdr(p)))); +} + +/** + * Returns the 5th element of a list. + */ +template const T caddddr(const list& p) { + return car(cdr(cdr(cdr(cdr(p))))); +} + +/** + * Returns the 6th element of a list. + */ +template const T cadddddr(const list& p) { + return car(cdr(cdr(cdr(cdr(cdr(p)))))); +} + +/** + * Returns the 7th element of a list. + */ +template const T caddddddr(const list& p) { + return car(cdr(cdr(cdr(cdr(cdr(cdr(p))))))); +} + +/** + * Returns the 8th element of a list. + */ +template const T cadddddddr(const list& p) { + return car(cdr(cdr(cdr(cdr(cdr(cdr(cdr(p)))))))); +} + +/** + * Returns the cdr of a cdr of a list. + */ +template const list cddr(const list& p) { + return cdr(cdr(p)); +} + +/** + * Returns the cdr of a cdr of the cdr of a list. + */ +template const list cdddr(const list& p) { + return cdr(cdr(cdr(p))); +} + +/** + * Returns the length of a list. + */ +template struct lengthRef { + const size_t operator()(const size_t c, const list& p) { + if(isNil(p)) + return c; + return (*this)(c + 1, cdr(p)); + } +}; + +template const size_t length(const list& p) { + return lengthRef ()(0, p); +} + +/** + * Appends a list and a lambda function returning a list. + */ +template struct appendCdr { + const list a; + const lambda()> fb; + appendCdr(const list& a, const lambda()>& fb) : + a(a), fb(fb) { + } + const list operator()() const { + return append(a, fb); + } +}; + +template const list append(const list&a, const lambda()>& fb) { + if(isNil(a)) + return fb(); + + return cons(car(a), appendCdr (cdr(a), fb)); +} + +/** + * Appends two lists. + */ +template const list append(const list&a, const list& b) { + return append(a, result(b)); +} + +/** + * Append a value to a list. + */ +template const list operator+(const list& l, const T& v) { + return append(l, mklist(v)); +} + +template const list operator+(const list& l, const V& v) { + return append(l, mklist(v)); +} + +/** + * Map a lambda function on a list. + */ +template const list map(const lambda& f, const list& p) { + if(isNil(p)) + return list (); + return cons(f(car(p)), map(f, cdr(p))); +} + +/** + * Run a reduce lambda function on a list. + */ +template struct reduceAccumulate { + const lambda f; + reduceAccumulate(const lambda& f) : + f(f) { + } + R operator()(const R& acc, const list& p) const { + if(isNil(p)) + return acc; + return (*this)(f(acc, car(p)), cdr(p)); + } +}; + +template const R reduce(const lambda& f, const R& initial, const list& p) { + return reduceAccumulate (f)(initial, p); +} + +template struct reduceRightAccumulate { + const lambda f; + reduceRightAccumulate(const lambda& f) : + f(f) { + } + R operator()(const list& p, const R& acc) const { + if(isNil(p)) + return acc; + return (*this)(cdr(p), f(car(p), acc)); + } +}; + +template const R reduceRight(const lambda& f, const R& initial, const list& p) { + return reduceRightAccumulate (f)(p, initial); +} + +/** + * Run a filter lambda function on a list. + */ +template const list filter(const lambda& f, const list& p) { + if(isNil(p)) + return list (); + if(f(car(p))) { + const lambda(const lambda, const list)> ff(filter); + 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 const list member(const T& t, const list& p) { + if(isNil(p)) + return list (); + if(t == car(p)) + return p; + return member(t, cdr(p)); +} + +/** + * Reverse a list. + */ +template const list reverseIter(const list& acc, const list& p) { + if(isNil(p)) + return acc; + return reverseIter(cons(car(p), acc), cdr(p)); +} + +template const list reverse(const list& p) { + return reverseIter(list (), p); +} + +template const list seq(const T& start, const T& end); + +template struct seqGenerate { + const T start; + const T end; + seqGenerate(const T& start, const T&end) : + start(start), end(end) { + } + const list operator()() const { + return seq (start, end); + } +}; + +/** + * Returns a sequence of values between the given bounds. + */ +template const list seq(const T& start, const T& end) { + if(start == end) + return mklist(start); + if(start < end) + return cons(start, seqGenerate (start + 1, end)); + return cons(start, seqGenerate (start - 1, end)); +} + +/** + * Returns the i-th element of a list. + */ +template const T listRef(const list& l, const size_t i) { + if (i == 0) + return car(l); + return listRef(cdr(l), i - 1); +} + +/** + * Returns the first pair matching a key from a list of key value pairs. + */ +template const list assoc(const T& k, const list >& p) { + if(isNil(p)) + return list (); + if(k == car(car(p))) + return car(p); + return assoc(k, cdr(p)); +} + +/** + * Returns a list of lists containing elements from two input lists. + */ +template const list > zip(const list& a, const list& b) { + if (isNil(a) || isNil(b)) + return list >(); + return cons >(mklist(car(a), car(b)), zip(cdr(a), cdr(b))); +} + +/** + * Converts a list of key value pairs to a list containing the list of keys and the list of values. + */ +template const list unzipKeys(const list >& l) { + if (isNil(l)) + return list(); + return cons(car(car(l)), unzipKeys(cdr(l))); +} + +template const list unzipValues(const list >& l) { + if (isNil(l)) + return list(); + return cons(cadr(car(l)), unzipValues(cdr(l))); +} + +template const list > unzip(const list >& l) { + return mklist >(unzipKeys(l), unzipValues(l)); +} + +} + +#endif /* tuscany_list_hpp */ -- cgit v1.2.3