USAGE:

   #import structure

SYNOPSIS:

     RingBuffer
     Directory
     List
     Graph

TEMPLATE CLASS RingBuffer:

Constructor:

class <T> RingBuffer x(int size):

creates ring buffer for objects of class T

Variables:

readonly int numel

nr of elements in ring

Methods:

insert (T a):

insert a new element at pos 0 and shift remaining els back (oldest el falls out)

T get(int i=0):

get reference to i-th element (i%size)

T push(T x):

equivalent to insert

T pop(T x):

get & remove element

void rotate(int steps):

rotate ringbuffer by given nr of steps

void clear(void):

clear ringbuffer to 0 entries

TEMPLATE CLASS Directory:

Constructors:

   class Directory x(void);

Variables:

readonly numel

nr of elements

Methods:

char *firstkey():

char *lastkey():

lowest and highest char key (NULL, if directory empty)

T get(char *key):

return (reference to) first element with given key in table

void set(char *key, T x):

replace object with key key by x

void insert(char *key, T x):

insert new object with key key. If key already exists: ???

int remove(char *key1, int num=1):

int remove(char *key1, char *key2):

remove object(s) with keys between key1 and key2 (inclusive). If the default values of key2 and maxnum are kept, this will be taken as requesting removal of the first el with key=key1.

void merge(class Directory other, char *key1=NULL, char *key2=NULL):

merge range key1..key2 of Directory other into current Directory. The merged elements will become removed from other.

Directory <T> union(Directory other, char *first, char *last=NULL):

create new list consisting of union of (references to) elements both in list other and current list.

for_elements(void(*fun)(char *key, T x), char *first=NULL, char *last=NULL):

iterate function fun over (part of the) table

Directory <T> subset(float (*pred)(T x), char *first=NULL, char *last=NULL):

create new list consisting of (references to) elements in range start..end (exclusive) for which pred() is true.

clear():

remove all elements from the table

TEMPLATE CLASS List:

Usage:

     class <T> List x();

Variables:

readonly int end:

nr of elements currently in list.

readonly int is_sorted:

1 (-1) if list has a comparison function (cf. below) and is sorted in ascending (descending) order. Value 0 indicates that list may have become (but is not guaranteed to be!) unsorted or has no comparison function.

readonly int capacity:

nr of currently allocated memory positions for elements.

Methods:

T get(int i):

return reference to list element at position i, throws badop:index exception, when i is not in legal range i..end-1.

set(int i,T x):

replace list element at position i by x. Throws badop:index exception, when i is not in legal range i..end-1

sort(cmp):

enforce sorting of list, using comparison function

              float cmp(class T a, class T b)

sort():

analogous, but re-use most recently specified cmp function and act only if an intermediate operation (such as set() or insert(pos,x) has destroyed a previously established sorting order. NOTE: sort() assumes that cmp's behavior has not been changed (e.g., through global variables) since the most recent sort.

sort(0):

disable sorting function. Subsequent operations behave as if no sorting function were defined.

void revert():

invert list order

void insert(T x):

if a comparison function has been defined and the list is sorted: insert new element x such that sorting order stays intact. Otherwise simply append x after last list element.

void insert(int pos, T x)

insert x at position pos (0=start), shifting all elements at former positions pos..end-1 one position up (this may destroy sorting order). Throws a badop:index exception, if pos is not in the legal range 0..end.

void insert(int pos,class List src, int start=0,int end=9999999):

insert elements from range start..end of list src into current list. Existing elements will be shifted up so that the first inserted element will occupy position pos. Src must not be identical with the current list.

void merge(class List other, int start=0, int end=99999999):

merge range start..end of list other into current list. The merged elements will become removed from other.

subtract(List other, int start=0,int end=999999):

remove from current list all those elements that occur in the range start..end of list other. List other must be different from the current list.

int remove(int first, int num=1):

starting at position first, remove up to num elements from list. Return nr of removed elements.

remove_if(float (*pred)(T x), int start=0,int end=9999999):

remove all elements from the range start..end (with end not included) for which the predicate pred(x) is nonzero,

for_elements(void (*fun)(T), int first=0, int end=9999999, int stride=1):

call function fun(x) for all list elements in range first..end, using stride as the step increment from position first (if first>end, a non-empty range requires stride<0).

for_elements(void (*fun)(int i, T x), int first=0, int end=9999999, int stride=1):

analogous, but for function fun() that passes for each element x also its list position i.

int closest(T x, float dist(T,T), int first=0, int end=999999, int stride):

find position of list element y in range first..end (with end excluded) for which function dist(x,y) has smallest absolute value, using step increment stride to traverse the range (starting at from). In case of multiple minima of same magnitude, the first one found is returned.

List <T> neighbors(T x, int num, float dist(T,T), int first=0, int end=999999, int stride):

create new list containing (references to) first num closest elements (according to smallest dist() value) in range first..end (with end excluded), using step increment stride to traverse the range (starting at from). The returned list will contain the elements ordered by increasing distance.

List <T> subset(int *pos):

create new list of (references to) elements with positions specified in array pos.

List <T> subset(float (*pred)(T x), int start=0,int end=999999):

create new list consisting of (references to) elements in range start..end (exclusive) for which pred() is true.

List <T> intersection(List other, int start=0,int end=999999):

create new list consisting of (references to) elements both in list other and current list.

List <T> union(List other, int start=0,int end=999999):

create new list consisting of union of (references to) elements both in list other and current list.

List <T> difference(List other, int start=0,int end=999999):

create new list consisting of those elements of the current list that are not in the range start..end of list other.

void reserve(int size):

if capacity<size, raise it to size.

void clear():

remove all elements from current list (elements whose ref count drops to zero will become destroyed).

TEMPLATE CLASS Graph:

CONSTRUCTORS:

graph(int dimn, int dime1, ...,dimek):

create graph whose nodes carry an optional string label and a dimn dimensional node data vector. Created nodes can be connected with edges from k different edge types (identified by an integer index 0,1,..k-1). Edge type i-1 carries an dimei dimensional float vector plus an (optional) string label with each edge. If dimei=0, the edge has the string label (which may remain NULL) as its only data.

<T0> graph(int dimn, int dime1, ...,dimek):

As before, but now each node additionally can carry a node object of type T0.

<T0,T1> graph(int dimn, int dime1, ..,dimek):

As before, but now there is one additional edge type (in addition to the vector-carrying edge types 0..k-1) that (instead of a float vector) carries an object of type T1. Access functions to this additional edge type are identified by the keyword edge1 (instead of just edge).

<T0,T1,T2> graph(int dimn, int dime1, ...,dimek):

As before, but now there are two additional edge types (identified by keywords edge1 and edge2 resp.), carrying object types T1 and T2, resp.

<T0,T1,T2,T3> graph(int dimn, int dime1, ...,dimek):

Analogous, but with three additional object-carrying edge types.

Methods involving nodes only:

int insert_node(float *data)

insert a node and initialize its vector data

int insert_node(T0 obj)

insert a node and initialize its node object - void remove_node(int id) remove node with id id.

void set_node_partition(int id, int partition)

mark node id as belonging to a subset identified by the value of partition. Subsets are disjoint, except for partition=0, which always comprises all nodes.

int get_node_partition(int id)

retrieve to which partition a given node is currently assigned.

for_nodes(float *pcFmt, void (*f)(float*), int partition=0):

iterate function f() over all nodes (if partition!=0, iteration is restricted to the nodes that belong to the indicated partition). At each step, the caller passes to f() node data according to format string pcFmt.

for_nodes(void (*f)(T0), int partition=0):

similar, but with function f() which receives node object on each call

int closest(float *data, float (*Dist)(float*,float*),float *mindist=NULL,int partition):

int closest(T0 obj, float (*Dist)(T0,T0),float *mindist=NULL,int partition):

return index of node of current graph whose node data vector (or node object, resp.) is closest to a given vector data (or object, resp). The min distance is returned when mindist!=NULL. partition permits to restrict the set of admissible nodes on the current graph.

int closest(class Graph graph2,float (*Dist)(T0,T0),int *i2=NULL,float mindist=NULL,int partition):

int closest(class Graph graph2, int partition2, float (*Dist)(T0,T0),int *i2=NULL,float mindist=NULL,int partition):

return index of node of current graph that is closest to a node i2 of graph graph2. i2 and the min distance are returned, when non-NULL parameters have been specified. partition and partition2 permit to restrict the set of admissible nodes on the current graph and on graph2.

int neighbors(T x, int *nb, float dist(T,T), int partition=0):

find ids of first dimof(nb) closest nodes (according to smallest dist() value) in partition partition of the current graph. Fill nb with the ids ordered by increasing distance. Return nr of ids filled into nb.

for_neighbors_of(int id, void fun(T), int radius=1):

for_neighbors_of(int id, void fun(T,int), int radius=1):

iterate function fun() over node objects of node id and its neighbors within a maximal graph distance of radius edges (inclusively). The 2nd version also passes with each function call the id of the currently visited node.

set_node(int id, float *data, char *mask=NULL):

get_node(int id, float *data, char *mask=NULL):

void set_node_label(int id, char *label):

char *get_node_label(int id):

set/get node vector data/label

void set_node_obj(int id, T0 obj):

T0 get_node_obj(int id):

void merge(class Graph other, int partition=0):

merge nodes in partition partition of graph other into current graph. The merge will include all edges connecting nodes from the merged partition. The merged elements will become removed from other. In addition, all edges between the partition and the rest of other will become deleted.

clear()

remove all nodes and edges

compactify_ids(int *list=NULL)

compactify node ids to the contiguous range 0..nodes-1. This is useful after node deletions, which may have left unused holes in the index range. Note that after this the indices of nodes will have changed! To keep track of such changes, one may specify an array list filled with previous node index values, which will then become updated with their new values (entries that did not specify used node index values will become replaced by -1).

Methods involving edges:

    mode = OUT_E : visit all outward directed edges of a node
    mode = INP_E : visit all inward directed edges of a node
    mode = SYM_E : visit all symmetric edges of a node
    mode = SYM1_E : visit all symmetric edges of a node, but
                     with the additional restriction that
                     node-id1 < node-id2 to ensure that each symmetric
                     edge is visited only once when iterating over
                     all nodes.

    mode = 0: (the default) equivalent to
              OUT_E+INP_E+SYM_E or OUT_E+INP_E+SYM1_E when
              iterating over selected or all nodes, resp.

void use_edge_type(int type):

void insert_edge(int from, int to, float *data=NULL):

void insert_symedge(int n1, int n2, float *data=NULL):

insert float vector edge or symmetric edge of current type.

void insert_edge1(int from, int to, T1 obj):

void insert_symedge1(int n1, int n2, T1 obj):

insert object edge or symmetric edge of additional type 1. (analogous calls for additional types 2 and 3).

void remove_edge(int from, int to):

void remove_edge(int *piFrom, int *piTo):

remove edge(s) between two nodes/two node sets

void remove_edge1..3(int from, int to):

remove edge(s) for additional type between two nodes/two node sets

void set_edge_vector(int from, int to, float *data):

float *get_edge_vector(int from, int to):

void set_edge1_obj1(int from, int to, T1 obj):

T1 get_edge1_obj(int from, int to):

int for_edges(void(*fun)(int,int), int mode=0):

int for_edges_of(int node, void (*fun)(int,int), int mode=0):

int for_edges(char *fmt, void(*fun)(float*), int mode=0):

int for_edges_of(int node, char *fmt, void(*fun)(float*), int mode=0):

iterate function fun() over all vector edges of type layer, passing node index pair or edge data according to fmt

int for_edges1(void(*fun)(int,int)), int mode=0):

iterate function fun() over all object edges of additional type 1, passing edge object with each call. Analogous calls for additional types 2 and 3.

int for_edges1(void(*fun)(T1)), int mode=0):

int for_edges1_of(int node, void(*fun)(int,int), int mode=0):

int for_edges1_of(int node, void(*fun)(T1), int mode=0):

Analogous calls, but for edges connected to a single node. mode=1 only outgoing, mode=-1 only ingoing, mode=0 both types of edges.

int *shortest_path(int from, int to, float *dist=NULL, int distidx=0, int reuse=0):

find shortest path from node from to node to, using as distance value the edge data element at position distidx. The routine will return a newly allocated array with one element for each node in the path (including start from and end to). If dist!=NULL, deposit also the distance along the shortest path. When reuse=1, a new call will check if from and distidx is unchanged. If so, a recomputation will be based on the (internally stored) result of the most previous call, assuming that the graph topology has not been changed. This allows to retrieve a number of paths to different destination points without excessive recomputations.

float *mindist(int from, int *piPrev, int distidx=0):

compute and return array with one slot per element in the current node index range. Those slots i that correspond to existing nodes contain the min path distance from node from to that node i. An infinite distance is indicated by Infty. Slots that correspond to unused gaps in the index range contain the value NaN. If piPrev is non-null, it is filled for each node slot with the predecessor of the shortest path connecting that node to the starting node from (i.e., piPrev will be of the same dimension as the returned distance array).

FILE