template < class A> class stack : public stack_or_queue< A > { public: void push(A x) { first = new element(x,first); } }
template < class A > class queue : public stack_or_queue< A > { private: element *last; public: queue(){last = first = NULL; }//not necessary: it's enough to init. first void insert(A x) { if (is_empty()) { first = last = new element(x,NULL); } else { last = last->next = new element(x,NULL); } } /* If we use the pop of stack_or_queue, popping the last element will cause last to become a dangling reference. In this particular case this dangling reference would not be harmful, since the next insert will redefine last correctly, and we don't use last otherwise. However, for the sake of a "clean programming style", we redefine (override) pop so to delete last when the queue is emptied. */ A pop(){ A inf = stack_or_queue< A >::pop(); if (first==NULL) { last = NULL; } return inf; } }
~element() { if (next != NULL) delete next; } ~stack_or_queue() { if (first != NULL) delete first; }
class Buffer2 { private int content1, content2; private boolean is_empty1, is_empty2; public Buffer2() { is_empty1 = is_empty2 = true; } public synchronized void put(int k) throws InterruptedException { while (!is_empty1) wait(); if (is_empty2) { // buffer empty content2 = k; is_empty2 = false; notifyAll(); } else { content1 = k; is_empty1 = false; } } public synchronized int get() throws InterruptedException { while (is_empty2) wait(); int k = content2; if (!is_empty1) { // buffer full content2 = content1; is_empty1 = true; notifyAll(); } else { is_empty2 = true; } return k; } }
A more elegant solution consists in defining Buffer2 as an object containing two objects of type Buffer1 (buffers with only one position) fisrt and second, and a little thread "demon". A put() on Buffer2 will cause a put() on first, and a get() on Buffer2 will cause a get() on second. The demon will take care of moving data from first to second.
class Buffer2 { private Buffer1 first, second; private class Demon extends Thread { private Buffer1 from, to; public Demon(Buffer1 f, Buffer1 t){ from = f; to = t; } public void run() { try { while (!isInterrupted()) { synchronized (from) { int k = from.get(); to.put(k); } } } catch (InterruptedException e) { return; } } } public Buffer2(){ first = new Buffer1(); second = new Buffer1(); new Demon(first,second).start(); } public void put(int k) throws InterruptedException { first.put(k); } public int get() throws InterruptedException { return second.get(); } }
fun count(x,[]) = 0 | count(x,y::l) = (if x=y then 1 else 0) + count(x,l);
datatype 'a tree = emptyt | const of 'a * 'a tree list;
fun height t = let fun max(x,y) = if x>y then x else y; fun max_heights [] = 0 | max_heights (emptyt::l) = max_heights l | max_heights (const(n,k)::l) = max(1 + max_heights k, max_heights l) in max_heights [t] end;Another, more elegant solution for height is:
fun height emptyt = 0 | height (const(n,[])) = 1 | height (const(n,t::l)) = let fun max(x,y) = if x>y then x else y in max(1 + height t, height(const(n,l))) end;Finally, we give also a more interesting solution using the map function
fun map f [] = [] | map f (x::l) = (f x) :: (map f l); fun height emptyt = 0 | height (const(n,l)) = let fun max(x,y) = if x>y then x else y; fun maxlist [] = 0 | maxlist (a::k) = max(a, maxlist k) in 1 + maxlist(map height l) end;