Software Libraries: Design and Reuse

Franck.Barbier@FranckBarbier.com)

Creative Commons License
Software Libraries: Design and Reuse is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License

Preamble

This tutorial is an overview of Software Libraries. It is mostly illustrated by means of the Java technology. The purpose of this tutorial is to show that "good programming" is not enough. Reuse is the key action in software development, supposing a broad knowledge on existing libraries, how to put them into practice in a safe and rapid way. Design for reuse is the other facet. Designing software to be reused is a complicated task requiring specific skill.

Software libraries, the case of Java

Software libraries organize pre-implemented software in reusable, composable pieces. To that extent, the power of Java mostly resides in its core libraries, for instance, the Java SE 6 platform/technology is as follows:

Java SE 6

Libraries depend upon each other, the case of AWT, Swing and Beans

«class» java.util.EventObject
⇧ «class» java.awt.AWTEvent
⇧ «class» java.awt.ActionEvent
⇧ «class» java.beans.PropertyChangeEvent

«interface» java.util.EventListener
⇧ «interface» java.beans.PropertyChangeListener
⇧ «interface» java.awt.event.ActionListener
⇪ «class» javax.swing.JLayer<V extends Component>

Software libraries, the case of C++

C++ Standard Template Library (STL)

STL is fully part of C++ while it first was an external library. STL is mainly constituted of container classes, i.e., collections, but it also includes generic algorithms that may be found in <algorithm> and in <numeric>, for instance:

Example

Specification

E ⊂ F ⇔ E ⊆ F ∧ E ≠ F
-> strict_subset? (i.e., ⊂): Set x Set -> Boolean with s1, s2: Set, strict_subset?(s1,s2) = subset?(s1,s2) ∧ ∼equals?(s1,s2)
E - F = {t ∈ E ∧ t ∉ F}
-> difference: Set x Set -> Set with s1, s2: Set, ti: T, difference(s1,s2) = [remove(union(s1,s2),ti)]belongs?(ti,s2)

Implementation

template <typename T> class Set : public std::set<T> {
public:
bool strict_subset(const Set<T>&);
Set<T> operator -(const Set<T>&);
};

template<typename T> bool Set<T>::strict_subset(const Set<T>& s) {
Set<T> intersection;
std::set_intersection(this->begin(),this->end(),s.begin(),s.end(),std::inserter(intersection,intersection.end()));
return intersection == *this && intersection != s;
}
template<typename T> Set<T> Set<T>::operator -(const Set<T> & s) {
Set<T> difference;
std::set_difference(this->begin(),this->end(),s.begin(),s.end(),std::inserter(difference,difference.end()));
return difference;
}

Yet another famous C++ library: boost

The most reused libraries: collections in C++ and Java

C++ and Java collections: overview

Advantages of class-based arrays over native arrays (reminder)

Java iteration style

java.util.Collection<Boolean> collection = new java.util.LinkedList<Boolean>();
java.util.Random random = new java.util.Random();
for(int i = 0;i < 5;i++) {
boolean b = random.nextBoolean();
collection.add(b);
}
for(Boolean b : collection) System.out.print("\t" + b);

java.util.Collections utility class

This class is not a common collection! It is mainly used for collection creation, conversion (from native arrays especially), sorting and other generic algorithms as C++ generic algorithms. Example:

short native_tab[] = {3, 4, 6, 7, 8, 11, 12, 13};

java.util.List<Short> advanced_tab = new java.util.Vector<Short>();
for (int i = 0; i < native_tab.length; i++) advanced_tab.add(native_tab[i]);

java.util.Collections.shuffle(advanced_tab); // Random permutation of elements to loose the initial order
for (short s : advanced_tab) System.out.print("\t" + s);

System.out.print(java.util.Collections.binarySearch(advanced_tab, (short) 0)); // '-1' (insertion point) is returned since '0' is not present in 'advanced_tab'

java.util.Collections.sort(advanced_tab);
for (short s : advanced_tab) System.out.print("\t" + s);

Sequences

Java sequences

Usage:
Adding at the end (_all_criminal_cases is typed with java.util.List<Criminal_case>):
public void involve(Criminal_case cc) {
boolean result = _all_criminal_cases.add(cc);
assert result;
}
Adding at the beginning (_all_criminal_cases is typed with java.util.List<Criminal_case>):
public void involve(Criminal_case cc) {
_all_criminal_cases.add(0,cc);
}
Adding at the end (_all_criminal_cases is typed with java.util.LinkedList<Criminal_case>): _all_criminal_cases.addLast(cc);
Adding at the beginning (_all_criminal_cases is typed with java.util.LinkedList<Criminal_case>): _all_criminal_cases.addFirst(cc);
Getting the last one:
public Criminal_case last() { // 'java.util.LinkedList<E>'
return _all_criminal_cases.isEmpty() ? null : _all_criminal_cases.getLast();
}
public Criminal_case last() { // 'java.util.List<E>'
Criminal_case last = null;
java.util.ListIterator<Criminal_case> iterator = _all_criminal_cases.listIterator();
while(iterator.hasNext()) last = iterator.next();
return last;
}

C++ sequences

class Prisoner {
protected: std::list<const Criminal_case*> _all_criminal_cases;
void Prisoner::involve(const Criminal_case& cc) {
_all_criminal_cases.push_back(&cc);
}
void Prisoner::involve(const Criminal_case& cc) {
_all_criminal_cases.push_front(&cc);
}
const Criminal_case* Prisoner::last() const {
return _all_criminal_cases.empty() ? NULL : _all_criminal_cases.back();
}

Other C++ sequences

std::queue<char,std::list<char> > q;
q.push('a');
q.push('b');
q.pop();
std::cout << "front: " << q.front() << std::endl; // 'b' is displayed

Sets

C++ sets

std::set<char> alphabet;
alphabet.insert('a');
alphabet.insert('a'); // without effect because 'a' < 'a' is false

assert(alphabet.size() == 1);
std::set<Task,std::greater<Task> > scheduler;
short tab[] = {3,4,6,7,8,11,12,13};
std::set<short> set(tab,tab + 8);
assert(std::binary_search(set.begin(),set.end(),13)); // '#include <algorithm>'
assert(! std::binary_search(set.begin(),set.end(),14)); // '#include <algorithm>'

Java sets

Insertion requires an appropriate equality function in Prisoner class:
public boolean equals(Object object) {
return this == object ? true : object instanceof Prisoner ? _prison_file_number.equals(((Prisoner)object)._prison_file_number) : false;
}

enum Decision_type {Conviction, Shortened_sentence, Final_discharge}
protected final Enum<Decision_type> _decision_type; // <=> 'Decision_type _decision_type;'
public enum Temperature_unit {
Celsius("°C"), Fahrenheit("°F"), Kelvin("°K");
protected final String _literal;
private Temperature_unit(String literal) { _literal = literal; }
public String toString() { return _literal; }
}

Maps

C++ maps

double polynomial[] = {8.,-3.,5.}
std::list<std::pair<double,double> > polynomial;
std::map<double,double> polynomial;
polynomial[1.] = -12.;
polynomial[39.] = 8.;
std::map<std::string,std::string> given_names__dictionary; // This is equivalent to: 'std::map<std::string,std::string,std::less<std::string> > given_names__dictionary;'
std::string s1 = "Franck";
std::string s2 = "Franck";
given_names__dictionary[s1] = "English origin given name";
given_names__dictionary[s2] = "German origin given name");
assert(given_names__dictionary.size() == 1);

Principle: if(! (s1 < s2) && ! (s2 < s1)) must lead to true, i.e., s1 and s2 are "the same key".

Java maps

java.util.Map<Double,Double> polynomial = new java.util.Hashtable<Double,Double>();
polynomial.put(1.,-12.);
polynomial.put(39.,8.);

java.util.Map<Object,String> my_map = new java.util.Hashtable<Object,String>();
Object o1 = new Object();
my_map.put(o1,"inserted string at the ‘o1’ index (key)");
String s = my_map.get(o1);
assert(s.equals("inserted string at the ‘o1’ index (key)") == true);
Objective: o1 ≠ o2 ⇒ hashCode(o1) ≠ hashCode(o2)
Memory management: H(o) = └((hashCode(o) * Θ) modulo 1.) * max┘ with 0 < Θ < 1
Example:
int max = 100;
float theta = 0.5F;
java.util.Map<String,String> given_names__dictionary = new java.util.Hashtable<String,String>(max,theta);
Root interface: java.util.Map<K,V>
Classes: java.util.Hashtable<K,V> (no nullvalues), java.util.HashMap<K,V> (no synchronization), java.util.LinkedHashMap<K,V> (order preservation) and java.util.TreeMap<K,V> (order preservation with red-black tree as backbone)
Concurrent programming:java.util.concurrent.ConcurrentMap<K,V>

Maps with duplicated keys (a.k.a. multimaps) only exist in C++

std::multimap<std::string,std::string> given_names__dictionary;
std::string s1 = "Franck";
std::string s2 = "Franck";
given_names__dictionary[s1] = "English origin given name";
given_names__dictionary[s2] = "German origin given name");
assert(given_names__dictionary.size() == 2);

Heaps, priority queues

Heap internal representation

Heap internal representation

C++ heaps and priority queues

short tab[] = {3,4,6,7,8,11,12,13};
std::vector<short> my_heap(tab,tab + 8);
std::make_heap(my_heap.begin(),my_heap.end());
for(int i = 0;i < my_heap.size();i++) std::cout << "-" << my_heap[i];
std::sort_heap(my_heap.begin(),my_heap.end());
for(int i = 0;i < my_heap.size();i++) std::cout << "-" << my_heap[i];
Heap sort (1/2)
Heap sort (2/2)
Heap result (1/2)

Java heaps and priority queues

java.util.Comparator<Short> comparator = new java.util.Comparator<Short> () {
public int compare(Short i,Short j) {
if(i < j) return -1;
if(i == j) return 0; // if(i > j) return 1;
return 1; // mandatory when not using 'if'
}
};

java.util.PriorityQueue<Short> my_priority_queue = new java.util.PriorityQueue<Short>(10,comparator);

Red-black trees

Red-black trees are one of the most efficient data structures to be used as the backbone of sets and maps. Insertions, deletions and searches are run in O(log(n)) complexity.

Java

The java.util.TreeSet<E> and java.util.TreeMap<K,V> classes are based on red-black trees.

C++

For example, the std::set<Key,Compare> is based on red-black trees. Please note that rb_tree<> is a native STL generic class, but it is not part of the C++ standard. As such, it does not aim to be directly (re)-used.

Software quality

Economical quality features

Other key quality features

Design with reuse

Design with reuse encompasses the search, the selection and the controlled integration of trusted software pieces with cost-effectiveness and time-effectiveness (productivity...). The reuse process is a suite of three key phases, namely analysis, design and programming as follows:

Analysis model

Analysis

As shown above, white rectangles are "business objects" coming from business analysis.

Design model

Design

At design time, business objects are assigned to library components (gray rectangles) in order to elaborate on how business services may rely on technical functions in these components.

Programming model

Programming

At programming time, glue code allows the effective connection. Often, library components cannot be reused "as is". Dots in gray rectangles image such an adaptation so that library components become fully integrable.

Design patterns

Design for reuse versus design with reuse

Case study (requirements)

Requirements, first part

Requirements, first part

Requirements, second part

Requirements, second part

Case study (analysis)

Analysis model sample

Analysis model sample

Case study (design FOR reuse)

Bad design 1

Bad design (1/2)

Bad design 2

Bad design (2/2)


In fact, the two bad designs above do not favor maintainability at the time a third norm calculation would be introduced in the application. To better manage this potential evolution, the two good designs below are based on the Template design pattern. Namely the Vector class is abstract with two concrete subclasses, Vector quadratic norm and Vector maximum norm that both implement the norm abstract function in Vector.

Good design (inheritance)

Good design (inheritance)

Good design (composition)

Good design (composition)

Case study (design WITH reuse)

Design model sample v. 1

Programming model sample (reuse through composition)

Design model sample v. 2

Programming model sample (reuse through multiple inheritance)

Implementation in C++

template<class T> class Vector {

protected:
std::vector<T> _implementation;
public:
… // constructors and destructors here
virtual double norm() const = 0; // norm computation (abstract function, whose implementation depends upon subtypes)
double norm_addition(const Vector& v) const {return (*this + v).norm();}
double norm_subtraction(const Vector& v) const {return (*this - v).norm();}
double lambda_norm(const double lambda) const {return  ::fabs(lambda) * norm();}
// utility functions (i.e., out of the scope of the initial requirements), for instance, the addition of vectors:
Vector<T>& operator +(const Vector<T>&) const throw(std::logic_error); // implementation is deported

};

Implementation in Java

abstract public class Vector<T extends Number> extends Number {

protected java.util.Vector<Number> _implementation;
… // constructors here
abstract public double norm();
public double norm_addition(final Vector<T> v) { return this.plus(v).norm(); }
public double norm_subtraction(final Vector<T> v) { return this.minus(v).norm(); }
public double lambda_norm(final double lambda) { return Math.abs(lambda) * norm(); }

}

Full Java implementation may be downloaded here.

Refactoring

Illustration by means of the NetBeans IDE

Plugin

Illustration by means of the NetBeans IDE

Code documention

Illustration by means of the NetBeans IDE