text:
// ==========================================================================
//                 SeqAn - The Library for Sequence Analysis
// ==========================================================================
// Copyright (c) 2006-2013, Knut Reinert, FU Berlin
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above copyright
//       notice, this list of conditions and the following disclaimer in the
//       documentation and/or other materials provided with the distribution.
//     * Neither the name of Knut Reinert or the FU Berlin nor the names of
//       its contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
// DAMAGE.
//
// ==========================================================================
// Author: Anne-Katrin Emde <emde@fu-berlin.de>
// ==========================================================================

// TODO(holtgrew): Bring back random center computation using new random module?

// (weese:) This header needs improvement
//
// documentation lacks:
//   - is createIntervalTree clearing the tree first (what happens after a second call of createIntervalTree?)
//   - where is clear(itree)?
//   - some flags are missing in the dddoc entries, e.g. ..cat:, class:, or ..type: of arguments
//
// interface flaws:
//   - there are 2 interfaces for createIntervalTree
//      - based on IntervalTree
//      - based on Graph and PropertyMap (should be removed)
//   - addInterval

#ifndef SEQAN_HEADER_MISC_INTERVAL_TREE_H
#define SEQAN_HEADER_MISC_INTERVAL_TREE_H

#include <seqan/graph_types.h>

namespace SEQAN_NAMESPACE_MAIN
{
//////////////////////////////////////////////////////////////////////////////
// Graph - Interval Tree Types
//////////////////////////////////////////////////////////////////////////////

///---------------------------------------------------------------///

//////////////////// Interval and ID type ///////////////////
/**
.Class.IntervalAndCargo:
..cat:Miscellaneous
..summary:A simple record type that stores an interval and a cargo value.
..signature:IntervalAndCargo<TValue, TCargo>
..param.TValue:The value type, that is the type of the interval borders.
...default:int.
...metafunction:Metafunction.Value
..param.TCargo:The cargo type.
...default:int.
...metafunction:Metafunction.Cargo
..include:seqan/misc/misc_interval_tree.h
*/
template<typename TValue = int, typename TCargo = int>
class IntervalAndCargo
{
public:
    /**
.Memvar.IntervalAndCargo#i1:
..class:Class.PointAndCargo
..summary:The first element in the interval of type i1.
     */
	TValue i1;

    /**
.Memvar.IntervalAndCargo#i2:
..class:Class.PointAndCargo
..summary:The last element in the interval of type i2.
     */
	TValue i2;

    /**
.Memvar.IntervalAndCargo#cargo:
..class:Class.PointAndCargo
..summary:The stored cargo of type TCargo.
     */
	TCargo cargo;

    /**
.Memfunc.IntervalAndCargo#IntervalAndCargo:
..signature:IntervalAndCargo()
     */
    IntervalAndCargo()
    {
SEQAN_CHECKPOINT
    }

    /**
.Memfunc.IntervalAndCargo#IntervalAndCargo:
..class:Class.IntervalAndCargo
..summary:Constructor.
..signature:IntervalAndCargo(i1, i2, cargo)
..param.i1:The first element in the interval, of type TValue.
..param.i2:The last element in the interval of type TValue.
..param.cargo:The cargo value of type TCargo.
     */
	IntervalAndCargo(TValue i1, TValue i2, TCargo cargo):
		i1(i1), i2(i2), cargo(cargo)
	{
SEQAN_CHECKPOINT
	}
};

/////////////////////// Point and ID type ////////////////
/**
.Class.PointAndCargo:
..cat:Miscellaneous
..summary:Simple record class storing a point (one-value interval) and a cargo.
..signature:PointAndCargo<TValue, TCargo>
..param.TValue:
...default:int.
...metafunction:Metafunction.Value
..param.TCargo:
...default:int.
...metafunction:Metafunction.Value
..include:seqan/misc/misc_interval_tree.h
*/
template<typename TValue=int, typename TCargo=int>
class PointAndCargo {
public:
    /**
.Memvar.PointAndCargo#point:
..class:Class.PointAndCargo
..summary:The stored point of type TValue.
     */
	TValue point;

    /**
.Memvar.PointAndCargo#cargo:
..class:Class.PointAndCargo
..summary:The stored cargo of type TCargo.
     */
	TCargo cargo;

    /**
.Memfunc.PointAndCargo#PointAndCargo
..class:Class.PointAndCargo
..signature:PointAndCargo(point, cargo)
    */
	PointAndCargo() {
SEQAN_CHECKPOINT
	}

    /**
.Memfunc.PointAndCargo#PointAndCargo
..class:Class.PointAndCargo
..summary:Constructor.
..signature:PointAndCargo(point, cargo)
..param.point:
...summary:The point to store of type TValue.
..param.cargo:
...summary:The cargo to store of type TCargo.
    */
	PointAndCargo(TValue point, TCargo cargo):
		point(point), cargo(cargo)
	{
SEQAN_CHECKPOINT
	}
};

///////////////////////////////////////////////////////////////////////////
/////////////////////////// IntervalTreeNode	///////////////////////////

/**
.Tag.IntervalTree Node Types
..summary:Tags to select the node type for @Class.IntervalTree@.
..cat:Miscellaneous
..see:Class.IntervalTree

..tag.StorePointsOnly:The tree nodes store points.
..include:seqan/misc/misc_interval_tree.h
*/
struct StorePointsOnly {};

///..tag.StoreIntervals:The tree nodes store intervals.
struct StoreIntervals {};

/**
.Class.IntervalTreeNode:
..cat:Miscellaneous
..summary:Element of @Class.IntervalTree@.
..signature:IntervalTreeNode<TInterval, TSpec>
..param.TInterval:The type of interval to store.
..param.TSpec:The type of interval to store.
...default:StorePointsOnly.
...metafunction:Metafunction.Spec
..include: seqan/misc/misc_interval_tree.h

.Memvar.IntervalTreeNode#center:
..class:Class.IntervalTreeNode
..summary:The center of the interval of type TValue.

.Memvar.IntervalTreeNode#list1
..class:Class.IntervalTreeNode
..summary:Sorted list of pointers to intervals, sorted in ascending according to their left boundary points.

.Memvar.IntervalTreeNode#list2
..class:Class.IntervalTreeNode
..summary:Sorted list of pointers to intervals, sorted in descending according to their right boundary points.
 */
template<typename TInterval, typename TSpec=StorePointsOnly>
class IntervalTreeNode;

/**
.Spec.Interval Tree Node
..cat:Miscellaneous
..general:Class.IntervalTreeNode
..summary:An Interval Tree Node that stores intervals explicitely in each node.
..signature:IntervalTreeNode<TInterval, StoreIntervals>
..param.TInterval:The interval type to store in the node.
..include:seqan/misc/misc_interval_tree.h
 */
template<typename TInterval>
class IntervalTreeNode<TInterval, StoreIntervals> {
public:
	typedef typename Value<TInterval>::Type TValue;

	TValue center;
	String<TInterval> list1;
	String<TInterval> list2;

    IntervalTreeNode() : center()
    {}
};

/**
.Spec.Points Only Tree Node
..cat:Miscellaneous
..general:Class.IntervalTreeNode
..summary:Spec for IntervalTreeNode that stores only the relevant point in each node meaning the endpoint of the interval in the list sorted by endpoints (list2) and only the beginpoint of the interval in the list sorted by beginpoints (list1).
..signature:IntervalTreeNode<TInterval, StorePointsOnly>
..param.TInterval:The interval type to store in the node.
..include:seqan/misc/misc_interval_tree.h
 */
template<typename TInterval>
class IntervalTreeNode<TInterval, StorePointsOnly> {
public:
	typedef typename Cargo<TInterval>::Type TCargo;
	typedef typename Value<TInterval>::Type TValue;

	TValue center;
	String<PointAndCargo<TValue,TCargo> > list1;
	String<PointAndCargo<TValue,TCargo> > list2;

    /**
.Memfunc.IntervalTreeNode#IntervalTreeNode:
..class:Class.IntervalTreeNode
..summary:Default constructor.
..signature:IntervalTreeNode()
     */
    IntervalTreeNode() : center()
    {
SEQAN_CHECKPOINT
    }

	IntervalTreeNode(IntervalTreeNode const & other):
		center(other.center),
		list1(other.list1),
		list2(other.list2)
	{
SEQAN_CHECKPOINT
	}
};

//////////////////////////////////////////////////////////////////////////////
// Graph - Interval Tree
//////////////////////////////////////////////////////////////////////////////

/**
.Class.IntervalTree:
..cat:Miscellaneous
..summary:A datastructure that efficiently stores intervals.
..signature:IntervalTree<TValue, TCargo>
..param.TValue:The value type.
...default:int
..param.TCargo:The cargo/id type.
...default:int
...remarks:If the intervals are not associated with cargos/IDs, they will be numbered consecutively.
..include:seqan/misc/misc_interval_tree.h
*/
template<typename TValue=int, typename TCargo=unsigned int>
class IntervalTree
{
public:
	typedef Graph<Directed<void,WithoutEdgeId> > TGraph;
	typedef IntervalAndCargo<TValue,TCargo> TInterval;
	typedef IntervalTreeNode<TInterval> TNode;
	typedef String<TNode> TPropertyMap;

	TGraph g;
	TPropertyMap pm;
	size_t interval_counter;

/**
.Memfunc.IntervalTree#IntervalTree:
..class:Class.IntervalTree
..summary:Constructor
..signature:IntervalTree()
..signature:IntervalTree(String<TInterval> intervals)
..signature:IntervalTree(String<TInterval> intervals, TValue center)
..signature:IntervalTree(String<TInterval> intervals, Tag<TTagSpec> const tag)
..signature:IntervalTree(intervalBegins, intervalEnds, len)
..signature:IntervalTree(intervalBegins, intervalEnds, intervalCargos, len)
..param.intervals:Container of intervals.
...type:Spec.Alloc String
...remarks:A string of $IntervalAndCargo<TValue, TCargo>$ objects, see @Class.IntervalAndCargo@.
..param.intervalBegins:Iterator pointing to begin position of first interval.
..param.intervalEnds:Iterator pointing to end position of first interval.
..param.intervalCargos:Iterator pointing to cargos/ids for intervals.
..param.len:Number of intervals to store in tree.
..param.tag:Tag for tree construction method; @Tag.IntervalTree Centers.tag.ComputeCenter@
...default:@Tag.IntervalTree Centers.tag.ComputeCenter@
..remarks:center of root node is computed by _calcIntervalTreeRootCenter
*/

	IntervalTree()
	{
SEQAN_CHECKPOINT
		interval_counter = 0;
	}

	template<typename TIterator,typename TCargoIterator>
	IntervalTree(TIterator interval_begins,
				 TIterator interval_ends,
				 TCargoIterator interval_cargos,
				 size_t len)
	{
SEQAN_CHECKPOINT
		String<TInterval> intervals;
		resize(intervals,len);
		size_t i = 0;
		while(i<len)
		{
			intervals[i].i1 = value(interval_begins);
			++interval_begins;
			intervals[i].i2 = value(interval_ends);
			++interval_ends;
			intervals[i].cargo = value(interval_cargos);
			++interval_cargos;
			++i;
		}
		createIntervalTree(*this, intervals);
	}

	template<typename TIterator>
	IntervalTree(TIterator interval_begins,
				 TIterator interval_ends,
				 size_t len)
	{
SEQAN_CHECKPOINT
		String<TInterval> intervals;
		resize(intervals,len);
		size_t i = 0;
		while(i<len)
		{
			intervals[i].i1 = value(interval_begins);
			++interval_begins;
			intervals[i].i2 = value(interval_ends);
			++interval_ends;
			intervals[i].cargo = i;
			++i;
		}
		createIntervalTree(*this, intervals);
	}

	IntervalTree(String<TInterval> intervals)
	{
SEQAN_CHECKPOINT
		createIntervalTree(*this, intervals);
	}

	template <typename TTagSpec>
	IntervalTree(String<TInterval> intervals, Tag<TTagSpec> const tag)
	{
SEQAN_CHECKPOINT
		interval_counter = length(intervals);
		createIntervalTree(g,pm,intervals,tag);
	}

	IntervalTree(String<TInterval> intervals, TValue center)
	{
SEQAN_CHECKPOINT
		interval_counter = length(intervals);
		createIntervalTree(g,pm,intervals,center);
	}
};

///////Specs for the way interval centers are determined
/**
.Tag.IntervalTree Centers
..cat:Miscellaneous
..summary:Tag to select a specific way to compute the center of an interval tree node.
..see:Class.IntervalTree
..include:seqan/misc/misc_interval_tree.h
 */

/**
..tag.ComputeCenter
...summary:For intervals that are more or less uniformly distributed in the value range, using the ComputeCenter tag may result in a more balanced tree compared to using a random approach.
...signature:ComputeCenter
...remarks:center = minbegin + (maxend-minbegin)/2
 */
//template <typename TSpec = SpecPointAndCargo>
struct TagComputeCenter_;
typedef Tag<TagComputeCenter_> const ComputeCenter;

///////////////////////////////////////////////////////////////////////////
///////////////////// IntervalAndCargo functions //////////////////////////
///////////////////////////////////////////////////////////////////////////

/**
.Function.leftBoundary
..cat:Miscellaneous
..summary:Access to the left boundary.
..signature:leftBoundary(interval)
..class:Class.IntervalAndCargo
..param.interval:The interval to return the left boundary for.
...type:Class.IntervalAndCargo
..returns:The reference to the left boundary of the interval of type TValue&.
..see:Function.getLeftBoundary
..see:Function.rightBoundary
..see:Function.getRightBoundary
*/

template<typename TValue, typename TCargo>
TValue &
leftBoundary(IntervalAndCargo<TValue, TCargo> & interval)
{
	return interval.i1;
}

template<typename TValue, typename TCargo>
TValue const &
leftBoundary(IntervalAndCargo<TValue, TCargo> const & interval)
{
	return interval.i1;
}

/**
.Function.rightBoundary
..cat:Miscellaneous
..summary:Access to the right boundary.
..signature:leftBoundary(interval)
..class:Class.IntervalAndCargo
..param.interval:The interval to return the left boundary for.
...type:Class.IntervalAndCargo
..returns:The reference to the right boundary of the interval of type TValue&.
..see:Function.getRightBoundary
..see:Function.leftBoundary
..see:Function.getLeftBoundary
*/

template<typename TValue, typename TCargo>
TValue &
rightBoundary(IntervalAndCargo<TValue, TCargo> & interval)
{
	return interval.i2;
}

template<typename TValue, typename TCargo>
TValue const &
rightBoundary(IntervalAndCargo<TValue, TCargo> const & interval)
{
	return interval.i2;
}

/**
.Function.getLeftBoundary
..cat:Miscellaneous
..summary:Get method for the left boundary.
..signature:leftBoundary(interval)
..class:Class.IntervalAndCargo
..param.interval:The interval to return the left boundary for.
...type:Class.IntervalAndCargo
..returns:The copy of the left boundary of the interval of type TValue.
..see:Function.leftBoundary
..see:Function.getRightBoundary
..see:Function.rightBoundary
*/

template<typename TValue, typename TCargo>
TValue
getLeftBoundary(IntervalAndCargo<TValue, TCargo> const & interval)
{
	return interval.i1;
}

/**
.Function.getRightBoundary
..cat:Miscellaneous
..summary:Get method for the right boundary.
..signature:leftBoundary(interval)
..class:Class.IntervalAndCargo
..param.interval:The interval to return the right boundary for.
...type:Class.IntervalAndCargo
..returns:The copy of the right boundary of the interval of type TValue.
..see:Function.rightBoundary
..see:Function.getLeftBoundary
..see:Function.leftBoundary
*/

template<typename TValue, typename TCargo>
TValue
getRightBoundary(IntervalAndCargo<TValue, TCargo> const & interval)
{
	return interval.i2;
}

/**
.Function.cargo
..signature:cargo(me)
..class:Class.IntervalAndCargo
..param.me:
...type:Class.IntervalAndCargo
..see:Function.getCargo
*/

template<typename TValue, typename TCargo>
TCargo const &
cargo(IntervalAndCargo<TValue, TCargo> const & interval)
{
	return interval.cargo;
}

template<typename TValue, typename TCargo>
TCargo &
cargo(IntervalAndCargo<TValue, TCargo> & interval)
{
	return interval.cargo;
}

/**
.Function.getCargo
..signature:getCargo(me)
..class:Class.IntervalAndCargo
..param.me:
...type:Class.IntervalAndCargo
..see:Function.cargo
*/

template<typename TValue, typename TCargo>
TCargo
getCargo(IntervalAndCargo<TValue,TCargo> const & interval)
{
	return interval.cargo;
}

/////////////////// Metafunctions //////////////////////

///.Metafunction.Value.param.T.type:Class.IntervalAndCargo
///.Metafunction.Value.class:Class.IntervalAndCargo
template<typename TValue,typename TCargo>
struct Value<IntervalAndCargo<TValue,TCargo> >
{
	typedef TValue Type;
};

///.Metafunction.Cargo.param.T.type:Class.IntervalAndCargo
///.Metafunction.Cargo.class:Class.IntervalAndCargo
template<typename TValue,typename TCargo>
struct Cargo<IntervalAndCargo<TValue, TCargo> >
{
	typedef TCargo Type;
};

///////////////////////////////////////////////////////////////////////////
///////////////////// PointAndCargo functions /////////////////////////////
///////////////////////////////////////////////////////////////////////////

/**
.Function.leftBoundary
..signature:leftBoundary(point)
..class:Class.PointAndCargo
..param.point.type:Class.PointAndCargo
 */

template<typename TValue, typename TCargo>
TValue const &
leftBoundary(PointAndCargo<TValue, TCargo> const & point)
{
	return point.point;
}

template<typename TValue, typename TCargo>
TValue &
leftBoundary(PointAndCargo<TValue, TCargo> & point)
{
	return point.point;
}

/**
.Function.rightBoundary
..signature:rightBoundary(point)
..class:Class.PointAndCargo
..param.point.type:Class.PointAndCargo
 */

template<typename TValue, typename TCargo>
TValue const &
rightBoundary(PointAndCargo<TValue, TCargo> const & point)
{
	return point.point;
}

template<typename TValue, typename TCargo>
TValue &
rightBoundary(PointAndCargo<TValue, TCargo> & point)
{
	return point.point;
}

/**
.Function.getLeftBoundary
..signature:getLeftBoundary(point)
..class:Class.PointAndCargo
..param.point.type:Class.PointAndCargo
 */

template<typename TValue, typename TCargo>
TValue
getLeftBoundary(PointAndCargo<TValue, TCargo> const & point)
{
    return point.point;
}

/**
.Function.getRightBoundary
..signature:getRightBoundary(point)
..class:Class.PointAndCargo
..param.point.type:Class.PointAndCargo
 */

template<typename TValue, typename TCargo>
TValue
getRightBoundary(PointAndCargo<TValue,TCargo> const & point)
{
	return point.point;
}

/**
.Function.cargo
..signature:cargo(point)
..class:Class.PointAndCargo
..param.point.type:Class.PointAndCargo
 */

template<typename TValue, typename TCargo>
TCargo const &
cargo(PointAndCargo<TValue,TCargo> const & point)
{
	return point.cargo;
}

template<typename TValue, typename TCargo>
TCargo &
cargo(PointAndCargo<TValue,TCargo> & point)
{
	return point.cargo;
}

/**
.Function.cargo
..signature:getCargo(point)
..class:Class.IntervalAndCargo
..param.point:
...type:Class.IntervalAndCargo
..see:Function.getCargo
*/

template<typename TValue, typename TCargo>
TCargo
getCargo(PointAndCargo<TValue,TCargo> const & point)
{
	return point.cargo;
}

////////////////// Metafunctions //////////////////
///.Metafunction.Value.param.T.type:Class.PointAndCargo
///.Metafunction.Value.class:Class.PointAndCargo
template<typename TValue,typename TCargo>
struct Value<PointAndCargo<TValue,TCargo> >
{
	typedef TValue Type;
};

///.Metafunction.Cargo.param.T.type:Class.PointAndCargo
///.Metafunction.Cargo.class:Class.PointAndCargo
template<typename TValue,typename TCargo>
struct Cargo<PointAndCargo<TValue,TCargo> >
{
	typedef TCargo Type;
};

//// Comparators
template <typename TPair>
bool _less_compI1_ITree(TPair const & p1, TPair const & p2)
{
    return (leftBoundary(p1) < leftBoundary(p2));
}

template <typename TPair>
bool _greater_compI2_ITree(TPair const & p1, TPair const & p2)
{
    return (rightBoundary(p1) > rightBoundary(p2));
}

///////////////////////////////////////////////////////////////////////////
///////////////////// IntervalTreeNode functions //////////////////////////
///////////////////////////////////////////////////////////////////////////

// internal set node functions
template<typename TValue, typename TInterval>
void
_setIntervalTreeNode(IntervalTreeNode<TInterval, StoreIntervals> & knot, TValue center, TInterval const & interval)
{
	knot.center = center;
	appendValue(knot.list1, interval);
	appendValue(knot.list2, interval);
}

// append intervals to lists in node knot
template<typename TInterval>
void
_appendIntervalTreeNodeLists(IntervalTreeNode<TInterval, StoreIntervals> & knot,TInterval const & interval)
{
	appendValue(knot.list1, interval);
	appendValue(knot.list2, interval);
}

//internal set node functions
template<typename TValue, typename TInterval>
void
_setIntervalTreeNode(IntervalTreeNode<TInterval, StorePointsOnly> & knot, TValue center, TInterval const & interval)
{
	knot.center = center;
	appendValue(knot.list1,PointAndCargo<TValue,typename Cargo<TInterval>::Type>(leftBoundary(interval),cargo(interval)));
	appendValue(knot.list2,PointAndCargo<TValue,typename Cargo<TInterval>::Type>(rightBoundary(interval),cargo(interval)));
}

template<typename TInterval>
void
_appendIntervalTreeNodeLists(IntervalTreeNode<TInterval, StorePointsOnly> & knot, TInterval const & interval)
{
	appendValue(knot.list1,PointAndCargo<typename Value<TInterval>::Type,typename Cargo<TInterval>::Type>(leftBoundary(interval),cargo(interval)));
	appendValue(knot.list2,PointAndCargo<typename Value<TInterval>::Type,typename Cargo<TInterval>::Type>(rightBoundary(interval),cargo(interval)));

}

/////////////////// Metafunctions ///////////////////////
///.Metafunction.Value.param.T.type:Class.IntervalTreeNode
///.Metafunction.Value.class:Class.IntervalTreeNode
template<typename TInterval, typename TSpec>
struct Value<IntervalTreeNode<TInterval,TSpec> >
{
	typedef typename Value<TInterval>::Type Type;
};

///.Metafunction.Cargo.param.T.type:Class.IntervalTreeNode
///.Metafunction.Cargo.class:Class.IntervalTreeNode
template<typename TInterval, typename TSpec>
struct Cargo<IntervalTreeNode<TInterval,TSpec> >
{
	typedef typename Cargo<TInterval>::Type Type;
};

/**
.Metafunction.ListType:
..cat:Miscellaneous
..signature:ListType<T>::ListType
..class.Class.IntervalTreeNode
..summary:Type of lists in tree nodes.
..param.T:The type to retrieve the list type for.
..returns:Returns the type of the lists in @Class.IntervalTreeNode@ objects.
..include:seqan/misc/misc_interval_tree.h
 */
template<typename T>
struct ListType;

///.Metafunction.ListType.param.T.type:Class.IntervalTreeNode
///.Metafunction.ListType.class:Class.IntervalTreeNode
template<typename TInterval>
struct ListType<IntervalTreeNode<TInterval,StorePointsOnly> >
{
	typedef String<PointAndCargo<typename Value<TInterval>::Type,typename Cargo<TInterval>::Type> > Type;

};

///.Metafunction.ListType.param.T.type:Class.IntervalTreeNode
///.Metafunction.ListType.class:Class.IntervalTreeNode
template<typename TInterval>
struct ListType<IntervalTreeNode<TInterval,StoreIntervals> >
{
	typedef String<IntervalAndCargo<typename Value<TInterval>::Type,typename Cargo<TInterval>::Type> > Type;

};

///////////////////////////////////////////////////////////////////////////
/////////////////////// IntervalTree functions ////////////////////////////
///////////////////////////////////////////////////////////////////////////

/**
.Function.createIntervalTree
..summary:Create an interval tree.
..cat:Miscellaneous
..class:Class.IntervalTree
..signature:createIntervalTree(intervalTree, intervals [, tag])
..signature:createIntervalTree(g, pm, intervals [, tag])
..signature:createIntervalTree(g, pm, intervals, center [, tag]])
..param.intervalTree:An interval tree
...type:Class.IntervalTree
..param.g:DirectedGraph to create interval tree in.
...type:Class.Graph
..param.pm:Property map to use for the created interval tree.
..param.intervals:Container of intervals.
...type:Spec.Alloc String
...remarks:A string of $IntervalAndCargo<TValue, TCargo>$ objects, see @Class.IntervalAndCargo@.
..param.tag:Tag for tree construction method; @Tag.IntervalTree Centers.tag.ComputeCenter@
...default:@Tag.IntervalTree Centers.tag.ComputeCenter@
..remarks:center of root node is computed by _calcIntervalTreeRootCenter
..include:seqan/misc/misc_interval_tree.h
 */

template <typename TGraph, typename TPropertyMap, typename TIntervals, typename TSpec>
inline void
createIntervalTree(TGraph & g,
				   TPropertyMap & pm,
				   TIntervals & intervals,
				   Tag<TSpec> const tag)
{
	typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
	typedef typename Value<TIntervals>::Type TInterval;
	typedef typename Value<TInterval>::Type TValue;

	reserve(g.data_vertex,length(intervals));
	reserve(pm,length(intervals));

	TVertexDescriptor root = addVertex(g);
	resizeVertexMap(g,pm);

    if (length(intervals) > 0u) {
        TValue center =	_calcIntervalTreeRootCenter(intervals);

        std::sort(begin(intervals, Standard()),end(intervals, Standard()),_less_compI1_ITree<TInterval>);

        String<TInterval *> interval_pointers;
        // interval tree stores pointers to intervals, not original intervals
        _makePointerInterval(intervals, interval_pointers);

        _createIntervalTree(g,pm,interval_pointers,root,(TValue)0.0,center,length(intervals),tag);
        reserve(pm, length(pm), Exact());
        reserve(g.data_vertex, length(g.data_vertex), Exact());
    }
}

template <typename TGraph, typename TPropertyMap, typename TIntervals>
inline void
createIntervalTree(TGraph & g,
				   TPropertyMap & pm,
				   TIntervals & intervals)
{
	createIntervalTree(g, pm, intervals, ComputeCenter());
}

template <typename TGraph, typename TPropertyMap, typename TIntervals, typename TSpec>
inline void
createIntervalTree(TGraph & g,
                   TPropertyMap & pm,
				   TIntervals & intervals,
				   typename Value<typename Value<TIntervals>::Type>::Type center,
				   Tag<TSpec> const tag)
{
	typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
	typedef typename Value<TIntervals>::Type TInterval;
	typedef typename Value<typename Value<TIntervals>::Type>::Type TValue;

	reserve(g.data_vertex,length(intervals));
	reserve(pm,length(intervals));

	TVertexDescriptor root = addVertex(g);
	resizeVertexMap(g,pm);

    if (length(intervals) > 0u) {
	    TInterval a;
	    typename Iterator<TIntervals, Standard>::Type begin_ = begin(intervals, Standard());
	    typename Iterator<TIntervals, Standard>::Type end_ = end(intervals, Standard());
	    std::sort(begin_, end_ ,_less_compI1_ITree<TInterval>);

	    String<TInterval const*> interval_pointers;
	    _makePointerInterval(intervals,interval_pointers);

	    if(length(intervals)==1) // if there is just one interval ->  center = center of this interval
		    center = (rightBoundary(intervals[0])-leftBoundary(intervals[0]))/(TValue)2.0;

	    _createIntervalTree(g, pm, interval_pointers, root, (TValue)0.0, center, length(intervals), tag);

	    reserve(pm, length(pm), Exact());
	    reserve(g.data_vertex, length(g.data_vertex), Exact());
    }
}

// ComputeCenter tag as default construction method
template <typename TGraph, typename TPropertyMap, typename TIntervals>
inline void
createIntervalTree(TGraph & g, TPropertyMap & pm,
				   TIntervals & intervals,
				   typename Value<typename Value<TIntervals>::Type>::Type center)
{
	createIntervalTree(g, pm, intervals, center, ComputeCenter());
}

template <typename TValue,typename TCargo, typename TIntervals, typename TSpec>
inline void
createIntervalTree(IntervalTree<TValue,TCargo> & it,
				   TIntervals & intervals,
				   Tag<TSpec> const tag)
{
	it.interval_counter = length(intervals);
	createIntervalTree(it.g, it.pm, intervals, tag);
}

template <typename TValue,typename TCargo, typename TIntervals>
inline void
createIntervalTree(IntervalTree<TValue, TCargo> & it,
				   TIntervals & intervals)
{
	createIntervalTree(it, intervals, ComputeCenter());
}

//////////////////////////////////////////////////////////////////////////////
//remembers minimum and maximum of point values in intervals and sets the center
//of each node to min+(max-min)/2
template<typename TGraph, typename TPropertyMap, typename TIntervalPointer, typename TValue>
inline void
_createIntervalTree(TGraph & g, TPropertyMap & pm,
				   String<TIntervalPointer*> & intervals,
				   typename VertexDescriptor<TGraph>::Type & knot,
				   TValue,
				   TValue center,
				   typename VertexDescriptor<TGraph>::Type len,
				   Tag<TagComputeCenter_> const tag)
{
	//  Rekursionsanker
	if (len == 1)
    {
		_setIntervalTreeNode(value(pm, knot), center, *intervals[0]);
		return;
	}

	typedef typename Value<TPropertyMap>::Type TNode;
	typedef typename ListType<TNode>::Type TList;
	typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
	typedef String<TIntervalPointer*> TIntervalPointers;

	// one list of interval pointers for the intervals to the left of center
	TIntervalPointers S_left;
	// one list of interval pointers for the intervals to the right of center
	TIntervalPointers S_right;

	TValue min1 = maxValue<TValue>();
	TValue min2 = maxValue<TValue>();
	TValue max1 = minValue<TValue>();
	TValue max2 = minValue<TValue>();

	value(pm,knot).center = center;

	typedef typename Iterator<TIntervalPointers,Standard>::Type TIntervalIterator;
	TIntervalIterator it = begin(intervals,Standard());
	TIntervalIterator it_end = end(intervals,Standard());

	// walk through intervals
	while(it != it_end)
	{
		// interval belongs to the left list
		if((**it).i2<=center)
		{
			appendValue(S_left,*it, Generous());
			 //remember right most and left most point in left list
			if((**it).i2 > max1)
				max1 = (**it).i2;
			if((**it).i1 < min1)
				min1 = (**it).i1;
		}
		else
		{
			// interval belongs to the right list
			if((**it).i1>center)
			{
				appendValue(S_right,(*it), Generous());
				 //remember right most and left most point in right list
				if((**it).i2 > max2)
					max2 = (**it).i2;
				if ((**it).i1 < min2)
					min2 = (**it).i1;
			}
			else // interval belongs to this node
			{
				_appendIntervalTreeNodeLists(value(pm,knot), **it);
			}
		}
        ++it;
	}

//	std::sort(begin(value(pm,knot).list1),end(value(pm,knot).list1),_less_compI1_ITree<typename Value<TList>::Type>);
	std::sort(begin(value(pm,knot).list2),end(value(pm,knot).list2),_greater_compI2_ITree<typename Value<TList>::Type>);

	// build subtree to the left
	if(!empty(S_left))
	{
		TVertexDescriptor vd = addVertex(g);
		resize(pm, vd+1);
		addEdge(g,knot,vd);
		_createIntervalTree(g,pm,S_left,vd,center,min1+(max1-min1)/2,length(S_left),tag);
	}
	// build subtree to the right
	if(!empty(S_right))
	{
		TVertexDescriptor vd = addVertex(g);
		resize(pm, vd+1);
		addEdge(g,knot,vd);
		_createIntervalTree(g,pm,S_right,vd,center,min2+(max2-min2)/2,length(S_right),tag);
	}
}

//////////////////////////////////////////////////////////////////////////////
//createIntervalTree for all specs except CompCenter, the center value of each
//node is determined by functions _calcIntervalTreeNodeCenterLeft and
//_calcIntervalTreeNodeCenterRight
template<typename TGraph, typename TPropertyMap, typename TSpec, typename TInterval, typename TValue>
inline void
_createIntervalTree(TGraph & g, TPropertyMap & pm,
				   String<TInterval*> & intervals,
				   typename VertexDescriptor<TGraph>::Type & knot,
				   TValue last_center, TValue center,
				   typename VertexDescriptor<TGraph>::Type len,
				   Tag<TSpec> const tag)
{
SEQAN_CHECKPOINT
	// Rekursionsanker
	if(len==1){
		_setIntervalTreeNode(value(pm,knot),center,*value(intervals,0));
		return;
	}

	typedef typename Value<TPropertyMap>::Type TNode;
	typedef typename ListType<TNode>::Type TList;
	typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
	typedef String<TInterval*> TIntervalPointers;

	// one list of interval pointers for the intervals to the left of center
	TIntervalPointers S_left;
	// one list of interval pointers for the intervals to the right of center
	TIntervalPointers S_right;

	value(pm,knot).center = center;

	typedef typename Iterator<TIntervalPointers,Standard>::Type TIntervalIterator;
	TIntervalIterator it = begin(intervals,Standard());
	TIntervalIterator it_end = end(intervals,Standard());

	// walk through intervals
	while(it != it_end)
	{
		// interval belongs to the left list
		if((**it).i2<=center)
		{
			appendValue(S_left,*it, Generous());
		}
		else
		{	// interval belongs to the right list
			if((**it).i1>center)
			{
				appendValue(S_right,(*it), Generous());
			}
			else
			{
				// interval belongs to the current node
				_appendIntervalTreeNodeLists(value(pm,knot),**it);
			}
		}
        ++it;
	}

//	std::sort(begin(value(pm,knot).list1),end(value(pm,knot).list1),_less_compI1_ITree<typename Value<TList>::Type>);
	std::sort(begin(value(pm,knot).list2),end(value(pm,knot).list2),_greater_compI2_ITree<typename Value<TList>::Type>);

	// build subtree to the left
	if(!empty(S_left))
	{
		TVertexDescriptor vd = addVertex(g);
		resizeVertexMap(g,pm);
		addEdge(g,knot,vd);
		TValue next_center = _calcIntervalTreeNodeCenterLeft(S_left,last_center,center,tag);
		_createIntervalTree(g,pm,S_left,vd,center,next_center,length(S_left),tag);
	}
	// build subtree to the right
	if(!empty(S_right))
	{
		TVertexDescriptor vd = addVertex(g);
		resizeVertexMap(g,pm);
		addEdge(g,knot,vd);
		TValue next_center = _calcIntervalTreeNodeCenterRight(S_right,last_center,center,tag);
		_createIntervalTree(g,pm,S_right,vd,center,next_center,length(S_right),tag);
	}
}

// fill the container interval_pointers with pointers to the corresponding objects in intervals.
// this is done to avoid copying and passing the whole IntervalAndCargo objects during interval tree construction
template<typename TIntervals, typename TIntervalPointers>
void
_makePointerInterval(TIntervals & intervals, TIntervalPointers & interval_pointers)
{
	typedef typename Iterator<TIntervals, Standard>::Type TIntervalIterator;
	typedef typename Iterator<TIntervalPointers, Standard>::Type TIntervalPointerIterator;

    resize(interval_pointers, length(intervals));
	if (empty(intervals))
        return;

	TIntervalIterator it = begin(intervals, Standard());
	TIntervalIterator itEnd = end(intervals, Standard());
	TIntervalPointerIterator iit = begin(interval_pointers, Standard());

    for (; it != itEnd; ++it, ++iit)
        *iit = it;
}

// if the center of the root is not given, it is placed in the "ComputeCenter way": in the middle of minValue and maxValue
// where minValue is the minimum left boundary and maxValue is the maximum right boundary of all intervals
template<typename TIntervals>
typename Value<typename Value<TIntervals>::Type>::Type
_calcIntervalTreeRootCenter(TIntervals & intervals)
{
    SEQAN_CHECKPOINT;

    SEQAN_ASSERT_GT(length(intervals), 0u);

	typedef typename Value<typename Value<TIntervals>::Type>::Type TValue;
	typedef typename Iterator<TIntervals,Standard>::Type TIntervalIterator;

	TIntervalIterator it = begin(intervals);
	TIntervalIterator it_end = end(intervals);

	TValue min = maxValue<TValue>();
	TValue max = minValue<TValue>();

    // get min and max
	while(it != it_end)
	{
		if(leftBoundary(*it)<min) min = leftBoundary(*it);
		if(rightBoundary(*it)>max) max = rightBoundary(*it);
	  SEQAN_ASSERT_LEQ(min, max);
		++it;
	}

	SEQAN_ASSERT_LEQ(min, max);

    // return middle between max and min
	return (min+(max-min)/(TValue)2.0);

}

/**
.Function.addInterval
..summary:Adds an interval to an interval tree.
..cat:Miscellaneous
..class:Class.IntervalTree
..signature:addInterval(intervalTree, interval)
..signature:addInterval(intervalTree, begin, end)
..signature:addInterval(intervalTree, begin, end, cargo)
..signature:addInterval(graph, propertyMap, interval)
..param.intervalTree:The interval tree to add the interval to.
...type:Class.IntervalTree
..param.interval:The interval to be added to the interval tree.
..param.begin:Begin position of interval of type TValue.
..param.end:End position of interval of type TValue.
..param.cargo:Cargo to attach to the interval.
...type:Class.IntervalAndCargo
..param.graph:The directed graph that contains the topography of the interval tree.
..param.propertyMap:The property map containing the node properties of the interval tree.
..include:seqan/misc/misc_interval_tree.h
*/

template<typename TGraph, typename TPropertyMap, typename TInterval>
void
addInterval(TGraph & g, TPropertyMap & pm, TInterval interval)
{
SEQAN_CHECKPOINT

	typedef typename Iterator<TGraph, OutEdgeIterator>::Type TOutEdgeIterator;
	typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
	typedef typename Value<TPropertyMap>::Type TProperty;
	typedef typename Value<TInterval>::Type TValue;
	typedef typename ListType<TProperty>::Type TList;

	if(empty(pm))
	{
		TVertexDescriptor vd = addVertex(g);
		resizeVertexMap(g,pm);
		_setIntervalTreeNode(property(pm,vd),(rightBoundary(interval)+leftBoundary(interval))/2,interval);
		return;

	}
	// start at root
	TVertexDescriptor act_knot = 0;
	TProperty act_prop = property(pm,act_knot);
	TProperty next_prop;

    // look for the right node to add interval to
	while(true)
	{
		TOutEdgeIterator it(g, act_knot);
		act_prop = property(pm,act_knot);
		if(act_prop.center < leftBoundary(interval)) // interval to the left of current node?
		{
			if(atEnd(it)){
				TVertexDescriptor vd = addVertex(g);
				resizeVertexMap(g,pm);
				addEdge(g,act_knot,vd);
				_setIntervalTreeNode(property(pm,vd),(rightBoundary(interval)+leftBoundary(interval))/(TValue)2.0,interval);
				break;
			}
			else{
				next_prop = property(pm,targetVertex(it));
				if(next_prop.center <= act_prop.center)
				{
					goNext(it);
					if(atEnd(it)){
						TVertexDescriptor vd = addVertex(g);
						resizeVertexMap(g,pm);
						addEdge(g,act_knot,vd);
						_setIntervalTreeNode(property(pm,vd),(rightBoundary(interval)+leftBoundary(interval))/(TValue)2.0,interval);
						break;
					}
				}
			}
			act_knot = targetVertex(it);
		}
		else{
			if(rightBoundary(interval) <= act_prop.center) // interval to the right of current node?
			{
				if(atEnd(it)){
					TVertexDescriptor vd = addVertex(g);
					resizeVertexMap(g,pm);
					addEdge(g,act_knot,vd);
					_setIntervalTreeNode(property(pm,vd),(rightBoundary(interval)+leftBoundary(interval))/2,interval);
					break;
				}
				else
				{
					next_prop = property(pm,targetVertex(it));
					if(next_prop.center >= act_prop.center)
					{
						goNext(it);
						if(atEnd(it)){
							TVertexDescriptor vd = addVertex(g);
							resizeVertexMap(g,pm);
							addEdge(g,act_knot,vd);
							_setIntervalTreeNode(property(pm,vd),(rightBoundary(interval)+leftBoundary(interval))/2,interval);
							break;
						}
					}
				}
				act_knot = targetVertex(it);
			}
			else{ // need to create new node for interval
				_appendIntervalTreeNodeLists(property(pm, act_knot),interval);
				std::sort(begin(property(pm,act_knot).list1),end(property(pm,act_knot).list1),_less_compI1_ITree<typename Value<TList>::Type>);
				std::sort(begin(property(pm,act_knot).list2),end(property(pm,act_knot).list2),_greater_compI2_ITree<typename Value<TList>::Type>);
				break;
			}
		}
	}

}

template<typename TValue, typename TCargo, typename TInterval>
void
addInterval(IntervalTree<TValue,TCargo> & itree, TInterval interval)
{
SEQAN_CHECKPOINT

	++itree.interval_counter;
	addInterval(itree.g,itree.pm,interval);

}

template<typename TValue, typename TCargo>
void
addInterval(IntervalTree<TValue,TCargo> & itree, TValue begin, TValue end, TCargo cargo)
{
SEQAN_CHECKPOINT

	IntervalAndCargo<TValue,TCargo> interval;
	interval.i1 = begin;
	interval.i2 = end;
	interval.cargo = cargo;
	++itree.interval_counter;
	addInterval(itree.g,itree.pm,interval);

}

template<typename TValue, typename TCargo>
void
addInterval(IntervalTree<TValue,TCargo> & itree, TValue begin, TValue end)
{
SEQAN_CHECKPOINT

	IntervalAndCargo<TValue,TCargo> interval;
	interval.i1 = begin;
	interval.i2 = end;
	interval.cargo = itree.interval_counter;
	++itree.interval_counter;
	addInterval(itree.g,itree.pm,interval);

}

/**
.Function.findIntervals
..summary:Find all intervals that contain the query point or overlap with the query interval.
..cat:Miscellaneous
..class:Class.IntervalTree
..signature:findIntervals(intervalTree, query, result)
..signature:findIntervals(intervalTree, query_begin, query_end, result)
..signature:findIntervals(graph, propertyMap, query, result)
..param.intervalTree:An interval tree
...type:Class.IntervalTree
..param.query:A query point.
..param.query_begin:The begin position of the query interval.
..param.query_end:The end position of the query interval.
..param.result:A reference to the result string of $TCargo$ objects
...type:Class.String
..include:seqan/misc/misc_interval_tree.h
*/
template <typename TSpec, typename TPropertyMap, typename TValue, typename TCargo>
inline void
findIntervals(
    Graph<TSpec> const & g,
    TPropertyMap const & pm,
    TValue query,
    String<TCargo> & result)
{
SEQAN_CHECKPOINT

    typedef Graph<TSpec> const TGraph;
	typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
	typedef typename Value<TPropertyMap>::Type TProperty;
	typedef typename Value<TProperty>::Type TPropertyValue;
	typedef typename Iterator<TGraph, OutEdgeIterator>::Type TOutEdgeIterator;

    resize(result,0);
    if (empty(g)) return;

	// start at root
	TVertexDescriptor act_knot = 0;
	TProperty act_prop = property(pm,act_knot);
	TProperty next_prop;

	while(true)
	{
        typename Iterator<Graph<TSpec> , OutEdgeIterator>::Type it7;
        Iter<Graph<TSpec>, GraphIterator<InternalOutEdgeIterator<OutEdgeIterator> > > it5(g,act_knot);
        TOutEdgeIterator it4;
		TOutEdgeIterator it(g, act_knot);
		act_prop = property(pm,act_knot);
		if(act_prop.center < (TPropertyValue)query) // look in current node and right subtree
		{
			unsigned int i = 0;
			while(i < length(act_prop.list2) && rightBoundary(value(act_prop.list2,i)) > (TPropertyValue)query)
			{
				appendValue(result,cargo(value(act_prop.list2,i)), Generous());
				++i;
			}
			if(atEnd(it)) break;
			else{
				next_prop = property(pm,targetVertex(it));
				if(next_prop.center <= act_prop.center)
				{
					goNext(it);
					if(atEnd(it)) break;
				}
			}
			act_knot = targetVertex(it);
		}
		else{
			if((TPropertyValue)query < act_prop.center) // look in current node and left subtree
			{
				unsigned int i = 0;
				while(i < length(act_prop.list1) && leftBoundary(value(act_prop.list1,i)) <= (TPropertyValue)query)
				{
					appendValue(result,cargo(value(act_prop.list1,i)), Generous());
					++i;
				}
				if(atEnd(it)) break;
				else
				{
					next_prop = property(pm,targetVertex(it));
					if(next_prop.center >= act_prop.center)
					{
						goNext(it);
						if(atEnd(it)) break;
					}
				}
				act_knot = targetVertex(it);
			}
			else{ // look in current node only, as query is center
				for(unsigned int i = 0; i < length(act_prop.list1); ++i)
                    appendValue(result, cargo(value(act_prop.list1,i)), Generous());
				break;
			}
		}
	}

}

template <typename TValue, typename TCargo>
inline void
findIntervals(
    IntervalTree<TValue,TCargo> const & it,
    TValue query,
    String<TCargo> & result)
{
SEQAN_CHECKPOINT
	findIntervals(it.g,it.pm,query,result);
}

template <typename TValue, typename TCargo>
inline void
findIntervals(
    IntervalTree<TValue,TCargo> const & tree,
    TValue query_begin,
    TValue query_end,
    String<TCargo> & result)
{
SEQAN_CHECKPOINT
	findIntervals(tree.g,tree.pm,query_begin,query_end,result);
}

template <typename TSpec, typename TPropertyMap, typename TValue, typename TCargo>
inline void
findIntervals(
    Graph<TSpec> const & g,
    TPropertyMap const & pm,
    TValue query_begin,
    TValue query_end,
    String<TCargo> & result)
{
    typedef Graph<TSpec> const TGraph;
	typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;

    resize(result,0);

	// start at root
	TVertexDescriptor act_knot = 0;
	findIntervals(g, pm, act_knot, query_begin, query_end, result);
}

template <
    typename TSpec,
    typename TPropertyMap,
    typename TVertexDescriptor,
    typename TValue,
    typename TCargo >
inline void
findIntervals(
    Graph<TSpec> const & g,
    TPropertyMap const & pm,
    TVertexDescriptor & act_knot,
    TValue query_begin,
    TValue query_end,
    String<TCargo> & result)
{
SEQAN_CHECKPOINT

	typedef typename Value<TPropertyMap>::Type TProperty;
	typedef typename Iterator<Graph<TSpec>, OutEdgeIterator>::Type TOutEdgeIterator;

    if (empty(g)) return;

    TProperty act_prop = property(pm,act_knot);
	TProperty next_prop;

	while(true)
	{
		TOutEdgeIterator it(g, act_knot);
		act_prop = property(pm,act_knot);
		//
		if(act_prop.center < query_begin) // query interval is to the right of node center
		{
			unsigned int i = 0;
			while(i < length(act_prop.list2) && rightBoundary(value(act_prop.list2,i)) > query_begin)
			{
				appendValue(result,cargo(value(act_prop.list2,i)), Generous());
				++i;
			}
			if(atEnd(it)) break;
			else{
				next_prop = property(pm,targetVertex(it));
				if(next_prop.center <= act_prop.center)
				{
					goNext(it);
					if(atEnd(it)) break;
				}
			}
			act_knot = targetVertex(it);
		}
		else{
			if(query_end < act_prop.center) // query interval is to the left of node center
			{
				unsigned int i = 0;
				while(i < length(act_prop.list1) && leftBoundary(value(act_prop.list1,i)) < query_end)
				{
					appendValue(result,cargo(value(act_prop.list1,i)), Generous());
					++i;
				}
				if(atEnd(it)) break;
				else
				{
					next_prop = property(pm,targetVertex(it));
					if(next_prop.center >= act_prop.center)
					{
						goNext(it);
						if(atEnd(it)) break;
					}
				}
				act_knot = targetVertex(it);
			}
			else{//node center is contained in query interval
				for(unsigned int i = 0; i < length(act_prop.list1); ++i)
                    appendValue(result, cargo(value(act_prop.list1,i)), Generous());

				while(!atEnd(it))
				{
					TVertexDescriptor next_knot = targetVertex(it);
					findIntervals(g,pm, next_knot, query_begin, query_end, result);
					goNext(it);
				}
				break;

				//break; //dont break! continue in both subtrees!!
			}
		}
	}
}

/**
.Function.findIntervalsExcludeTouching
..summary:Find all intervals that contain the query point, exclude intervals that touch the query, i.e. where the query point equals the start or end point.
..signature:findIntervalsExcludeTouching(intervalTree, query, result)
..signature:findIntervalsExcludeTouching(graph, propertyMap, query, result)
..cat:Miscellaneous
..class:Class.IntervalTree
..param.intervalTree:An interval tree
...type:Class.IntervalTree
..param.graph:The directed graph that contains the topography of the interval tree.
..param.propertyMap:The property map containing the node properties of the interval tree
..param.query:The TValue to query here.
..param.result:The resulting string of cargos/ids of the intervals that contain the query point.
...type:Class.String
...remarks:Should be a string of TCargo.
..include:seqan/misc/misc_interval_tree.h
*/
template <typename TSpec, typename TPropertyMap, typename TValue, typename TCargo>
inline void
findIntervalsExcludeTouching(
    Graph<TSpec> const & g,
    TPropertyMap const & pm,
    TValue query,
    String<TCargo> & result)
{
SEQAN_CHECKPOINT

    typedef Graph<TSpec> const TGraph;
	typedef typename Iterator<TGraph, OutEdgeIterator >::Type TOutEdgeIterator;
	typedef typename VertexDescriptor<TGraph>::Type TVertexDescriptor;
	typedef typename Value<TPropertyMap>::Type TProperty;

	resize(result,0);
    if (empty(g)) return;

	// start at root
	TVertexDescriptor act_knot = 0;
	TProperty act_prop = property(pm,act_knot);
	TProperty next_prop;

	while(true)
	{
		TOutEdgeIterator it(g, act_knot);
		act_prop = property(pm,act_knot);
		if( (TValue) act_prop.center < query) // look in current node and right subtree
		{
			int i = 0;
			while(i < (int) length(act_prop.list2) && (TValue) rightBoundary(value(act_prop.list2,i)) > query)
			{
				appendValue(result,cargo(value(act_prop.list2,i)), Generous());
				++i;
			}
			if(atEnd(it)) break;
			else{
				next_prop = property(pm,targetVertex(it));
				if(next_prop.center <= act_prop.center)
				{
					goNext(it);
					if(atEnd(it)) break;
				}
			}
			act_knot = targetVertex(it);
		}
		else{
			if(query < (TValue) act_prop.center) // look in current node and left subtree
			{
				int i = 0;
				while(i < (int) length(act_prop.list1) && (TValue) leftBoundary(value(act_prop.list1,i)) < query)
				{
					appendValue(result,cargo(value(act_prop.list1,i)), Generous());
					++i;
				}
				if(atEnd(it)) break;
				else
				{
					next_prop = property(pm,targetVertex(it));
					if(next_prop.center >= act_prop.center)
					{
						goNext(it);
						if(atEnd(it)) break;
					}
				}
				act_knot = targetVertex(it);
			}
			else{ // look in current node only
				int i = 0;
				while(i < (int) length(act_prop.list1) && (TValue) leftBoundary(value(act_prop.list1,i)) < query)
				{
					appendValue(result,cargo(value(act_prop.list1,i)), Generous());
					++i;
				}
				break;
			}
		}
	}

}

template <typename TValue, typename TCargo>
inline void
findIntervalsExcludeTouching(
    IntervalTree<TValue,TCargo> const & tree,
    TValue query,
    String<TCargo> & result)
{
SEQAN_CHECKPOINT
	findIntervalsExcludeTouching(tree.g,tree.pm,query,result);
}

/**
.Function.removeInterval
..summary:Removes an interval from the interval tree.
..signature:removeInterval(intervalTree, i_begin, i_end, i_id)
..cat:Miscellaneous
..class:Class.IntervalTree
..param.intervalTree:An interval tree
...type:Class.IntervalTree
..param.i_begin:The begin position of the interval to be removed.
..param.i_end:The end position of the interval to be removed.
..param.i_id:The ID of the interval to be removed.
*/

template <
    typename TSpec,
    typename TPropertyMap,
    typename TVertexDescriptor,
    typename TValue,
    typename TCargo >
inline bool
removeInterval(
    Graph<TSpec> & g,
    TPropertyMap & pm,
    TVertexDescriptor & act_knot,
    TValue i_begin,
    TValue i_end,
    TCargo i_id)
{
SEQAN_CHECKPOINT

	typedef typename Value<TPropertyMap>::Type TProperty;
	typedef typename ListType<TProperty>::Type TList;
	typedef typename Iterator<TList, Standard>::Type TListIterator;
	typedef typename Iterator<Graph<TSpec>, OutEdgeIterator>::Type TOutEdgeIterator;

    if (empty(g)) return false;

    TProperty act_prop = property(pm,act_knot);
	TProperty next_prop;

	while(true)
	{
		TOutEdgeIterator it(g, act_knot);
		act_prop = property(pm,act_knot);
		//
		if(act_prop.center < i_begin) // interval is to the right of node center
		{
			if(atEnd(it)) break;
			else{
				next_prop = property(pm,targetVertex(it));
				if(next_prop.center <= act_prop.center)
				{
					goNext(it);
					if(atEnd(it)) break;
				}
			}
			act_knot = targetVertex(it);
		}
		else{
			if(i_end < act_prop.center) // interval is to the left of node center
			{
				if(atEnd(it)) break;
				else
				{
					next_prop = property(pm,targetVertex(it));
					if(next_prop.center >= act_prop.center)
					{
						goNext(it);
						if(atEnd(it)) break;
					}
				}
				act_knot = targetVertex(it);
			}
			else{//node center is contained in interval, this is where we should find the interval to be removed
                // remove from list1
                TProperty& change_prop = property(pm,act_knot);
                bool foundInLeft = false;
                TListIterator list_it_keep = begin(change_prop.list1,Standard());
                TListIterator list_it = begin(change_prop.list1,Standard());
				while(list_it != end(change_prop.list1,Standard()))
                {
                    //std::cout << "Element: " << getLeftBoundary(*list_it) << ".." << getRightBoundary(*list_it) << " " << cargo(*list_it) << std::endl;
                    if (getLeftBoundary(*list_it) == i_begin && cargo(*list_it) == i_id)
                    {
                        foundInLeft = true;
                        ++list_it;
                        continue;
                    }
                    *list_it_keep = *list_it;
                    //std::cout << "Element keep: " << getLeftBoundary(*list_it_keep) << ".." << getRightBoundary(*list_it_keep) << " " << cargo(*list_it_keep) << std::endl;
                    ++list_it; ++list_it_keep;
                }

	            bool foundInRight = false;
                list_it_keep = begin(change_prop.list2,Standard());
                list_it = begin(change_prop.list2,Standard());
				while(list_it != end(change_prop.list2,Standard()))
                {
                    //std::cout << "Element: " << getLeftBoundary(*list_it) << ".." << getRightBoundary(*list_it) << " " << cargo(*list_it) << std::endl;
                    if (getRightBoundary(*list_it) == i_end && cargo(*list_it) == i_id)
                    {
                        foundInRight = true;
                        ++list_it;
                        continue;
                    }
                    *list_it_keep = *list_it;
                    //std::cout << "Element keep: " << getLeftBoundary(*list_it_keep) << ".." << getRightBoundary(*list_it_keep) << " " << cargo(*list_it_keep) << std::endl;
                    ++list_it; ++list_it_keep;

                }

                // TODO: if node is empty and does not have child nodes --> remove node.
                // keeping these empty leaf nodes just takes space unnecessarily
				if(foundInRight && foundInLeft)
                {
                    resize(change_prop.list2, length(change_prop.list2)-1);
                    resize(change_prop.list1, length(change_prop.list1)-1);
                    return true;
                }

			}
		}
	}
    return false;
}

template <
    typename TSpec,
    typename TPropertyMap,
    typename TValue,
    typename TCargo >
inline bool
removeInterval(
    Graph<TSpec> & g,
    TPropertyMap & pm,
    TValue i_begin,
    TValue i_end,
    TCargo i_id)
{
SEQAN_CHECKPOINT

	typedef typename VertexDescriptor<Graph<TSpec> >::Type TVertexDescriptor;

	// start looking at root
	TVertexDescriptor act_knot = 0;
	return removeInterval(g, pm, act_knot, i_begin, i_end, i_id);
}

template <typename TValue, typename TCargo>
inline bool
removeInterval(
    IntervalTree<TValue,TCargo> & tree,
    TValue i_begin,
    TValue i_end,
    TCargo i_id)
{
SEQAN_CHECKPOINT

	return removeInterval(tree.g, tree.pm, i_begin, i_end, i_id);
    // we do not decrease the interval_counter of tree, as it would mix up interval IDs
}

/////////////////// Metafunctions ///////////////////////

///.Metafunction.Value.param.T.type:Class.IntervalTree
template<typename TValue, typename TCargo>
struct Value<IntervalTree<TValue,TCargo> >
{
	typedef TValue Type;
};

///.Metafunction.Cargo.param.T.type:Class.IntervalTree
template<typename TValue, typename TCargo>
struct Cargo<IntervalTree<TValue,TCargo> >
{
	typedef TCargo Type;
};

}  // namespace SEQAN_NAMESPACE_MAIN

#endif  //#ifndef SEQAN_MISC_INTERVAL_TREE_H


text:
// clang-format off
// Keep it on top of all other includes to fix double include WinSock.h header file
// which is windows specific boost build problem
#include <osquery/remote/transports/tls.h>
// clang-format on

#include "tls_enroll.h"

#include <osquery/remote/enroll/enroll.h>
#include <osquery/core/flags.h>
#include <osquery/logger/logger.h>
#include <osquery/registry/registry_factory.h>
#include <osquery/sql/sql.h>
#include <osquery/core/system.h>

#include <osquery/process/process.h>
#include <osquery/remote/requests.h>
#include <osquery/remote/serializers/json.h>
#include <osquery/utils/info/platform_type.h>

namespace osquery {

DECLARE_string(enroll_secret_path);
DECLARE_bool(disable_enrollment);

CLI_FLAG(uint64,
         tls_enroll_max_attempts,
         3,
         "Number of attempts to retry a TLS enroll request, it used to be the "
         "same as [config_tls_max_attempts]");

/// Enrollment TLS endpoint (path) using TLS hostname.
CLI_FLAG(string,
         enroll_tls_endpoint,
         "",
         "TLS/HTTPS endpoint for client enrollment");

/// Undocumented feature for TLS access token passing.
HIDDEN_FLAG(bool,
            tls_secret_always,
            false,
            "Include TLS enroll secret in every request");

/// Undocumented feature to override TLS enrollment key name.
HIDDEN_FLAG(string,
            tls_enroll_override,
            "enroll_secret",
            "Override the TLS enroll secret key name");

REGISTER_INTERNAL(TLSEnrollPlugin, "enroll", "tls");

std::string TLSEnrollPlugin::enroll() {
  // If no node secret has been negotiated, try a TLS request.
  auto uri = "https://" + FLAGS_tls_hostname + FLAGS_enroll_tls_endpoint;
  if (FLAGS_tls_secret_always) {
    uri += ((uri.find('?') != std::string::npos) ? '&' : '?') +
           FLAGS_tls_enroll_override + "=" + getEnrollSecret();
  }

  std::string node_key;
  VLOG(1) << "TLSEnrollPlugin requesting a node enroll key from: " << uri;
  for (size_t i = 1; i <= FLAGS_tls_enroll_max_attempts; i++) {
    auto status = requestKey(uri, node_key);
    if (status.ok() || i == FLAGS_tls_enroll_max_attempts) {
      break;
    }

    LOG(WARNING) << "Failed enrollment request to " << uri << " ("
                 << status.what() << ") retrying...";
    sleepFor(i * i * 1000);
  }

  return node_key;
}

Status TLSEnrollPlugin::requestKey(const std::string& uri,
                                   std::string& node_key) {
  // Read the optional enrollment secret data (sent with an enrollment request).
  JSON params;
  params.add(FLAGS_tls_enroll_override, getEnrollSecret());
  params.add("host_identifier", getHostIdentifier());
  params.add("platform_type",
             std::to_string(static_cast<uint64_t>(kPlatformType)));

  // Select from each table describing host details.
  JSON host_details;
  genHostDetails(host_details);
  params.add("host_details", host_details.doc());

  Request<TLSTransport, JSONSerializer> request(uri);
  request.setOption("hostname", FLAGS_tls_hostname);
  auto status = request.call(params);
  if (!status.ok()) {
    return status;
  }

  // The call succeeded, store the node secret key (the enrollment response).
  JSON recv;
  status = request.getResponse(recv);
  if (!status.ok()) {
    return status;
  }

  // Support multiple response keys as a node key (identifier).
  auto it = recv.doc().FindMember("node_key");
  if (it == recv.doc().MemberEnd()) {
    it = recv.doc().FindMember("id");
  }

  if (it != recv.doc().MemberEnd()) {
    node_key = it->value.IsString() ? it->value.GetString() : "";
  }

  if (node_key.empty()) {
    return Status(1, "No node key returned from TLS enroll plugin");
  }
  return Status::success();
}
} // namespace osquery

redpajama_set_name: RedPajamaGithub


text:
<!DOCTYPE html>

	<link href="js/bootstrap.min.css" rel="stylesheet"type="text/css">
	<link href="css/moncss.css" rel="stylesheet"type="text/css">

	<title>Comparison of movie cameras - Shutter</title>
	<meta charset="utf-8">

Comparison of movie cameras - Shutter

			<fieldset>

					<form action="" method="post">
						<legend style="color:red;font-weight: bold;font-style:italic;text-align: center;" >Formulaire</legend>

								Angles :

											<input type="checkbox" name="Feature" >stops every 15° between 30° and 135°

											<input type="checkbox" name="Feature" >also stops at 11.2°

											<input type="checkbox" name="Feature" >22.5°

											<input type="checkbox" name="Feature" >144°

											<input type="checkbox" name="Feature" >172.8°

											<input type="checkbox" name="Feature" >and 180°

											<input type="checkbox" name="Feature" >between 50° and 200°

											<input type="checkbox" name="Feature" >continuously adjustable

											<input type="checkbox" name="Feature" >stops at 45°

											<input type="checkbox" name="Feature" >90°

											<input type="checkbox" name="Feature" >120°

											<input type="checkbox" name="Feature" >and 180°.

											<input type="checkbox" name="Feature" >between 11.2° and 180°

											<input type="checkbox" name="Feature" >in 0.1° stops

											<input type="checkbox" name="Feature" >and 180°. 22.5° available on newer models.

											<input type="checkbox" name="Feature" >stops at 144°

											<input type="checkbox" name="Feature" >150°

											<input type="checkbox" name="Feature" >between 11.2° to 180°

											<input type="checkbox" name="Feature" >between 45° and 180°

											<input type="checkbox" name="Feature" >stops every 15° between 15° and 180°

											<input type="checkbox" name="Feature" >also stops at 144° and 172.8°

											<input type="checkbox" name="Feature" >between 0° and 180°

											<input type="checkbox" name="Feature" >180°

											<input type="checkbox" name="Feature" >although the V

											<input type="checkbox" name="Feature" >B variant is adjustable from 0° to 165°

											<input type="checkbox" name="Feature" >stops at 22.5°

											<input type="checkbox" name="Feature" >45°

											<input type="checkbox" name="Feature" >between 11° to 180°

											<input type="checkbox" name="Feature" >in 0.01° stops

											<input type="checkbox" name="Feature" >stops every 15° between 45° and 150°

											<input type="checkbox" name="Feature" >also stops at 144°

											<input type="checkbox" name="Feature" >160°; many conversions for different angles

										<input type='checkbox'>autre:
<input type="text"/>

								Adjustment :
 <input id="0" type="text" name="Feature">

								Reflex? :

 <input type="radio" name="FeatureReflex?" value="oui">Yes <input type="radio" name="FeatureReflex?" value = "non">No <input type="radio" name="FeatureReflex?" value = "non">Partial

											<input  style="display:none;" id ="id2Reflex?"type="text"/>
										    <button class="btn btn-primary btn-xs" type="button" onClick="switchFunction('id1Reflex?','id2Reflex?');">Changer type</button>

								Camera model :
 <input id="1" type="text" name="Feature">

								Design :
 <input id="2" type="text" name="Feature">

								Location :
 <input id="3" type="text" name="Feature">

<input type="submit" class="btn btn-info" value="Ajouter un produit" />
					</form>

			</fieldset>


text:
var Checker = require('../lib/checker');
var assert = require('assert');

describe('modules/string-checker', function() {
    var checker;
    beforeEach(function() {
        checker = new Checker();
        checker.registerDefaultRules();
    });

    describe('line starting with hash, temporary, until we will have inline rules', function() {
        it('should ignore lines starting with #!', function() {
            assert(checker.checkString(
                '#! random stuff\n' +
                '#! 1234\n' +
                'var a = 5;\n'
            ).isEmpty());
        });

        it('should ignore ios instruments style import', function() {
            assert(checker.checkString(
                '#import "abc.js"\n' +
                '#import abc.js\n' +
                'var a = 5;\n'
            ).isEmpty());
        });

        it('should not replace when not beginning of line', function() {
            checker.configure({ disallowMultipleLineStrings: true });
            assert(checker.checkString(
                '#import "abc.js"\n' +
                'var b="#import \\\n abc.js";\n' +
                'var a = 5;\n'
            ).getErrorCount() === 1);
        });
    });

    it('should report parse issues as errors', function() {
        var errors = checker.checkString('this is not javascript');
        assert(errors.getErrorCount() === 1);

        var error = errors.getErrorList()[0];
        assert(error.rule === 'parseError');
        assert(error.message === 'Unexpected identifier');
        assert(error.line === 1);
        assert(error.column === 6);
    });

    it('should not process the rule if it is equals to null (#203)', function() {
        try {
            checker.configure({
                preset: 'jquery',
                requireCurlyBraces: null
            });
            assert(true);
        } catch (_) {
            assert(false);
        }
    });

    it('should throw if preset does not exist', function() {
        try {
            checker.configure({
                preset: 'not-exist'
            });

            assert(false);
        } catch (e) {
            assert(e.toString() === 'Error: Preset "not-exist" does not exist');
        }
    });

    describe('rules registration', function() {
        it('should report rules in config which don\'t match any registered rules', function() {
            var error;
            try {
                checker.configure({ disallowMulipleLineBreaks: true, disallowMultipleVarDelc: true });
            } catch (e) {
                error = e;
            }
            assert.equal(
                error.message,
                'Unsupported rules: disallowMulipleLineBreaks, disallowMultipleVarDelc'
            );
        });

        it('should not report rules in config which match registered rules', function() {
            var error;
            try {
                checker.configure({ disallowMultipleLineBreaks: true, disallowMultipleVarDecl: true });
            } catch (e) {
                error = e;
            }
            assert(error === undefined);
        });

        it('should not report "excludeFiles" rule as unregistered', function() {
            var error;
            try {
                checker.configure({ excludeFiles: [] });
            } catch (e) {
                error = e;
            }
            assert(error === undefined);
        });
    });
});


text:
ACCEPTED

#### According to
Index Fungorum

#### Published in
Mycologia 9(2): 108 (1917)

#### Original name
Cercospora bliti Tharp

### Remarks
null


text:
package com.google.auto.value.processor;

/**
 * A simplistic Java scanner. This scanner returns a sequence of tokens that can be used to
 * reconstruct the source code. Since the source code is coming from a string, the scanner in fact
 * just returns token boundaries rather than the tokens themselves.
 *
 *
We are not dealing with arbitrary user code so we can assume there are no exotic things like
 * tabs or Unicode escapes that resolve into quotes. The purpose of the scanner here is to return a
 * sequence of offsets that split the string up in a way that allows us to work with spaces without
 * having to worry whether they are inside strings or comments. The particular properties we use are
 * that every string and character literal and every comment is a single token; every newline plus
 * all following indentation is a single token; and every other string of consecutive spaces outside
 * a comment or literal is a single token. That means that we can safely compress a token that
 * starts with a space into a single space, without falsely removing indentation or changing the
 * contents of strings.
 *
 *
In addition to real Java syntax, this scanner recognizes tokens of the form {@code `text`},
 * which are used in the templates to wrap fully-qualified type names, so that they can be extracted
 * and replaced by imported names if possible.
 *
 * @author Éamonn McManus
 */
class JavaScanner {
  private final String s;

  JavaScanner(String s) {
    this.s = s.endsWith("\n") ? s : (s + '\n');
    // This allows us to avoid checking for the end of the string in most cases.
  }

  /**
   * Returns the string being scanned, which is either the original input string or that string plus
   * a newline.
   */
  String string() {
    return s;
  }

  /** Returns the position at which this token ends and the next token begins. */
  int tokenEnd(int start) {
    if (start >= s.length()) {
      return s.length();
    }
    switch (s.charAt(start)) {
      case ' ':
      case '\n':
        return spaceEnd(start);
      case '/':
        if (s.charAt(start + 1) == '*') {
          return blockCommentEnd(start);
        } else if (s.charAt(start + 1) == '/') {
          return lineCommentEnd(start);
        } else {
          return start + 1;
        }
      case '\'':
      case '"':
      case '`':
        return quoteEnd(start);
      default:
        // Every other character is considered to be its own token.
        return start + 1;
    }
  }

  private int spaceEnd(int start) {
    assert s.charAt(start) == ' ' || s.charAt(start) == '\n';
    int i;
    for (i = start + 1; i < s.length() && s.charAt(i) == ' '; i++) {}
    return i;
  }

  private int blockCommentEnd(int start) {
    assert s.charAt(start) == '/' && s.charAt(start + 1) == '*';
    int i;
    for (i = start + 2; s.charAt(i) != '*' || s.charAt(i + 1) != '/'; i++) {}
    return i + 2;
  }

  private int lineCommentEnd(int start) {
    assert s.charAt(start) == '/' && s.charAt(start + 1) == '/';
    int end = s.indexOf('\n', start + 2);
    assert end > 0;
    return end;
  }

  private int quoteEnd(int start) {
    char quote = s.charAt(start);
    assert quote == '\'' || quote == '"' || quote == '`';
    int i;
    for (i = start + 1; s.charAt(i) != quote; i++) {
      if (s.charAt(i) == '\\') {
        i++;
      }
    }
    return i + 1;
  }
}


text:
<title>Using the GNU Compiler Collection (GCC)</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="Using the GNU Compiler Collection (GCC)">
<meta name="generator" content="makeinfo 4.7">
<link title="Top" rel="start" href="#Top">
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">

<meta http-equiv="Content-Style-Type" content="text/css">

This file documents the use of the GNU compilers.

Copyright © 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
2008 Free Software Foundation, Inc.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.2 or
any later version published by the Free Software Foundation; with the
Invariant Sections being “GNU General Public License” and “Funding
Free Software”, the Front-Cover texts being (a) (see below), and with
the Back-Cover Texts being (b) (see below).  A copy of the license is
included in the section entitled “GNU Free Documentation License”.

(a) The FSF's Front-Cover Text is:

A GNU Manual

(b) The FSF's Back-Cover Text is:

You have freedom to copy and modify this GNU Manual, like GNU
     software.  Copies published by the Free Software Foundation raise
     funds for GNU development.

Short Contents

Introduction

1 Programming Languages Supported by GCC

2 Language Standards Supported by GCC

3 GCC Command Options

4 C Implementation-defined behavior

5 Extensions to the C Language Family

6 Extensions to the C++ Language

7 GNU Objective-C runtime features

8 Binary Compatibility

9 gcov—a Test Coverage Program

10 Known Causes of Trouble with GCC

11 Reporting Bugs

12 How To Get Help with GCC

13 Contributing to GCC Development

Funding Free Software

The GNU Project and GNU/Linux

GNU General Public License

GNU Free Documentation License

Contributors to GCC

Option Index

Keyword Index

Table of Contents

Introduction

1 Programming Languages Supported by GCC

2 Language Standards Supported by GCC

2.1 C language

2.2 C++ language

2.3 Objective-C and Objective-C++ languages

2.4 Treelang language

3 GCC Command Options

3.1 Option Summary

3.2 Options Controlling the Kind of Output

3.3 Compiling C++ Programs

3.4 Options Controlling C Dialect

3.5 Options Controlling C++ Dialect

3.6 Options Controlling Objective-C and Objective-C++ Dialects

3.7 Options to Control Diagnostic Messages Formatting

3.8 Options to Request or Suppress Warnings

3.9 Options for Debugging Your Program or GCC

3.10 Options That Control Optimization

3.11 Options Controlling the Preprocessor

3.12 Passing Options to the Assembler

3.13 Options for Linking

3.14 Options for Directory Search

3.15 Specifying subprocesses and the switches to pass to them

3.16 Specifying Target Machine and Compiler Version

3.17 Hardware Models and Configurations

3.17.1 ARC Options

3.17.2 ARM Options

3.17.3 AVR Options

3.17.4 Blackfin Options

3.17.5 CRIS Options

3.17.6 CRX Options

3.17.7 Darwin Options

3.17.8 DEC Alpha Options

3.17.9 DEC Alpha/VMS Options

3.17.10 FRV Options

3.17.11 GNU/Linux Options

3.17.12 H8/300 Options

3.17.13 HPPA Options

3.17.14 Intel 386 and AMD x86-64 Options

3.17.15 IA-64 Options

3.17.16 M32C Options

3.17.17 M32R/D Options

3.17.18 M680x0 Options

3.17.19 M68hc1x Options

3.17.20 MCore Options

3.17.21 MIPS Options

3.17.22 MMIX Options

3.17.23 MN10300 Options

3.17.24 MT Options

3.17.25 PDP-11 Options

3.17.26 PowerPC Options

3.17.27 IBM RS/6000 and PowerPC Options

3.17.28 S/390 and zSeries Options

3.17.29 Score Options

3.17.30 SH Options

3.17.31 SPARC Options

3.17.32 SPU Options

3.17.33 Options for System V

3.17.34 V850 Options

3.17.35 VAX Options

3.17.36 VxWorks Options

3.17.37 x86-64 Options

3.17.38 Xstormy16 Options

3.17.39 Xtensa Options

3.17.40 zSeries Options

3.18 Options for Code Generation Conventions

3.19 Environment Variables Affecting GCC

3.20 Using Precompiled Headers

3.21 Running Protoize

4 C Implementation-defined behavior

4.1 Translation

4.2 Environment

4.3 Identifiers

4.4 Characters

4.5 Integers

4.6 Floating point

4.7 Arrays and pointers

4.8 Hints

4.9 Structures, unions, enumerations, and bit-fields

4.10 Qualifiers

4.11 Declarators

4.12 Statements

4.13 Preprocessing directives

4.14 Library functions

4.15 Architecture

4.16 Locale-specific behavior

5 Extensions to the C Language Family

5.1 Statements and Declarations in Expressions

5.2 Locally Declared Labels

5.3 Labels as Values

5.4 Nested Functions

5.5 Constructing Function Calls

5.6 Referring to a Type with typeof

5.7 Conditionals with Omitted Operands

5.8 Double-Word Integers

5.9 Complex Numbers

5.10 Additional Floating Types

5.11 Decimal Floating Types

5.12 Hex Floats

5.13 Fixed-Point Types

5.14 Arrays of Length Zero

5.15 Structures With No Members

5.16 Arrays of Variable Length

5.17 Macros with a Variable Number of Arguments.

5.18 Slightly Looser Rules for Escaped Newlines

5.19 Non-Lvalue Arrays May Have Subscripts

5.20 Arithmetic on void- and Function-Pointers

5.21 Non-Constant Initializers

5.22 Compound Literals

5.23 Designated Initializers

5.24 Case Ranges

5.25 Cast to a Union Type

5.26 Mixed Declarations and Code

5.27 Declaring Attributes of Functions

5.28 Attribute Syntax

5.29 Prototypes and Old-Style Function Definitions

5.30 C++ Style Comments

5.31 Dollar Signs in Identifier Names

5.32 The Character <ESC> in Constants

5.33 Inquiring on Alignment of Types or Variables

5.34 Specifying Attributes of Variables

5.34.1 Blackfin Variable Attributes

5.34.2 M32R/D Variable Attributes

5.34.3 i386 Variable Attributes

5.34.4 PowerPC Variable Attributes

5.34.5 SPU Variable Attributes

5.34.6 Xstormy16 Variable Attributes

5.34.7 AVR Variable Attributes

5.35 Specifying Attributes of Types

5.35.1 ARM Type Attributes

5.35.2 i386 Type Attributes

5.35.3 PowerPC Type Attributes

5.35.4 SPU Type Attributes

5.36 An Inline Function is As Fast As a Macro

5.37 Assembler Instructions with C Expression Operands

5.37.1 Size of an asm

5.37.2 i386 floating point asm operands

5.38 Constraints for asm Operands

5.38.1 Simple Constraints

5.38.2 Multiple Alternative Constraints

5.38.3 Constraint Modifier Characters

5.38.4 Constraints for Particular Machines

5.39 Controlling Names Used in Assembler Code

5.40 Variables in Specified Registers

5.40.1 Defining Global Register Variables

5.40.2 Specifying Registers for Local Variables

5.41 Alternate Keywords

5.42 Incomplete enum Types

5.43 Function Names as Strings

5.44 Getting the Return or Frame Address of a Function

5.45 Using vector instructions through built-in functions

5.46 Offsetof

5.47 Built-in functions for atomic memory access

5.48 Object Size Checking Builtins

5.49 Other built-in functions provided by GCC

5.50 Built-in Functions Specific to Particular Target Machines

5.50.1 Alpha Built-in Functions

5.50.2 ARM iWMMXt Built-in Functions

5.50.3 ARM NEON Intrinsics

5.50.3.1 Addition

5.50.3.2 Multiplication

5.50.3.3 Multiply-accumulate

5.50.3.4 Multiply-subtract

5.50.3.5 Subtraction

5.50.3.6 Comparison (equal-to)

5.50.3.7 Comparison (greater-than-or-equal-to)

5.50.3.8 Comparison (less-than-or-equal-to)

5.50.3.9 Comparison (greater-than)

5.50.3.10 Comparison (less-than)

5.50.3.11 Comparison (absolute greater-than-or-equal-to)

5.50.3.12 Comparison (absolute less-than-or-equal-to)

5.50.3.13 Comparison (absolute greater-than)

5.50.3.14 Comparison (absolute less-than)

5.50.3.15 Test bits

5.50.3.16 Absolute difference

5.50.3.17 Absolute difference and accumulate

5.50.3.18 Maximum

5.50.3.19 Minimum

5.50.3.20 Pairwise add

5.50.3.21 Pairwise add, single_opcode widen and accumulate

5.50.3.22 Folding maximum

5.50.3.23 Folding minimum

5.50.3.24 Reciprocal step

5.50.3.25 Vector shift left

5.50.3.26 Vector shift left by constant

5.50.3.27 Vector shift right by constant

5.50.3.28 Vector shift right by constant and accumulate

5.50.3.29 Vector shift right and insert

5.50.3.30 Vector shift left and insert

5.50.3.31 Absolute value

5.50.3.32 Negation

5.50.3.33 Bitwise not

5.50.3.34 Count leading sign bits

5.50.3.35 Count leading zeros

5.50.3.36 Count number of set bits

5.50.3.37 Reciprocal estimate

5.50.3.38 Reciprocal square-root estimate

5.50.3.39 Get lanes from a vector

5.50.3.40 Set lanes in a vector

5.50.3.41 Create vector from literal bit pattern

5.50.3.42 Set all lanes to the same value

5.50.3.43 Combining vectors

5.50.3.44 Splitting vectors

5.50.3.45 Conversions

5.50.3.46 Move, single_opcode narrowing

5.50.3.47 Move, single_opcode long

5.50.3.48 Table lookup

5.50.3.49 Extended table lookup

5.50.3.50 Multiply, lane

5.50.3.51 Long multiply, lane

5.50.3.52 Saturating doubling long multiply, lane

5.50.3.53 Saturating doubling multiply high, lane

5.50.3.54 Multiply-accumulate, lane

5.50.3.55 Multiply-subtract, lane

5.50.3.56 Vector multiply by scalar

5.50.3.57 Vector long multiply by scalar

5.50.3.58 Vector saturating doubling long multiply by scalar

5.50.3.59 Vector saturating doubling multiply high by scalar

5.50.3.60 Vector multiply-accumulate by scalar

5.50.3.61 Vector multiply-subtract by scalar

5.50.3.62 Vector extract

5.50.3.63 Reverse elements

5.50.3.64 Bit selection

5.50.3.65 Transpose elements

5.50.3.66 Zip elements

5.50.3.67 Unzip elements

5.50.3.68 Element/structure loads, VLD1 variants

5.50.3.69 Element/structure stores, VST1 variants

5.50.3.70 Element/structure loads, VLD2 variants

5.50.3.71 Element/structure stores, VST2 variants

5.50.3.72 Element/structure loads, VLD3 variants

5.50.3.73 Element/structure stores, VST3 variants

5.50.3.74 Element/structure loads, VLD4 variants

5.50.3.75 Element/structure stores, VST4 variants

5.50.3.76 Logical operations (AND)

5.50.3.77 Logical operations (OR)

5.50.3.78 Logical operations (exclusive OR)

5.50.3.79 Logical operations (AND-NOT)

5.50.3.80 Logical operations (OR-NOT)

5.50.3.81 Reinterpret casts

5.50.4 Blackfin Built-in Functions

5.50.5 FR-V Built-in Functions

5.50.5.1 Argument Types

5.50.5.2 Directly-mapped Integer Functions

5.50.5.3 Directly-mapped Media Functions

5.50.5.4 Raw read/write Functions

5.50.5.5 Other Built-in Functions

5.50.6 X86 Built-in Functions

5.50.7 MIPS DSP Built-in Functions

5.50.8 MIPS Paired-Single Support

5.50.8.1 Paired-Single Arithmetic

5.50.8.2 Paired-Single Built-in Functions

5.50.8.3 MIPS-3D Built-in Functions

5.50.9 PowerPC AltiVec Built-in Functions

5.50.10 SPARC VIS Built-in Functions

5.50.11 SPU Built-in Functions

5.51 Format Checks Specific to Particular Target Machines

5.51.1 Solaris Format Checks

5.52 Pragmas Accepted by GCC

5.52.1 ARM Pragmas

5.52.2 M32C Pragmas

5.52.3 RS/6000 and PowerPC Pragmas

5.52.4 Darwin Pragmas

5.52.5 Solaris Pragmas

5.52.6 Symbol-Renaming Pragmas

5.52.7 Structure-Packing Pragmas

5.52.8 Weak Pragmas

5.52.9 Diagnostic Pragmas

5.52.10 Visibility Pragmas

5.53 Unnamed struct/union fields within structs/unions

5.54 Thread-Local Storage

5.54.1 ISO/IEC 9899:1999 Edits for Thread-Local Storage

5.54.2 ISO/IEC 14882:1998 Edits for Thread-Local Storage

5.55 Binary constants using the 0b prefix

6 Extensions to the C++ Language

6.1 When is a Volatile Object Accessed?

6.2 Restricting Pointer Aliasing

6.3 Vague Linkage

6.4 #pragma interface and implementation

6.5 Where's the Template?

6.6 Extracting the function pointer from a bound pointer to member function

6.7 C++-Specific Variable, Function, and Type Attributes

6.8 Namespace Association

6.9 Type Traits

6.10 Java Exceptions

6.11 Deprecated Features

6.12 Backwards Compatibility

7 GNU Objective-C runtime features

7.1 +load: Executing code before main

7.1.1 What you can and what you cannot do in +load

7.2 Type encoding

7.3 Garbage Collection

7.4 Constant string objects

7.5 compatibility_alias

8 Binary Compatibility

9 gcov—a Test Coverage Program

9.1 Introduction to gcov

9.2 Invoking gcov

9.3 Using gcov with GCC Optimization

9.4 Brief description of gcov data files

9.5 Data file relocation to support cross-profiling

10 Known Causes of Trouble with GCC

10.1 Actual Bugs We Haven't Fixed Yet

10.2 Cross-Compiler Problems

10.3 Interoperation

10.4 Incompatibilities of GCC

10.5 Fixed Header Files

10.6 Standard Libraries

10.7 Disappointments and Misunderstandings

10.8 Common Misunderstandings with GNU C++

10.8.1 Declare and Define Static Members

10.8.2 Name lookup, templates, and accessing members of base classes

10.8.3 Temporaries May Vanish Before You Expect

10.8.4 Implicit Copy-Assignment for Virtual Bases

10.9 Caveats of using protoize

10.10 Certain Changes We Don't Want to Make

10.11 Warning Messages and Error Messages

11 Reporting Bugs

11.1 Have You Found a Bug?

11.2 How and where to Report Bugs

12 How To Get Help with GCC

13 Contributing to GCC Development

Funding Free Software

The GNU Project and GNU/Linux

GNU General Public License

GNU Free Documentation License

ADDENDUM: How to use this License for your documents

Contributors to GCC

Option Index

Keyword Index

Next: G++ and GCC,
Up: (DIR)

Introduction

This manual documents how to use the GNU compilers,
as well as their features and incompatibilities, and how to report
bugs.  It corresponds to the compilers
(WinAVR 20081205)
version 4.3.2.
The internals of the GNU compilers, including how to port them to new
targets and some information about how to write front ends for new
languages, are documented in a separate manual.  See Introduction (GNU Compiler Collection (GCC) Internals).

G++ and GCC:      You can compile C or C++ programs.

Standards:        Language standards supported by GCC.

Invoking GCC:     Command options supported by gcc.

C Implementation:  How GCC implements the ISO C specification.

C Extensions:     GNU extensions to the C language family.

C++ Extensions:   GNU extensions to the C++ language.

Objective-C:      GNU Objective-C runtime features.

Compatibility:    Binary Compatibility

Gcov:             gcov---a test coverage program.

Trouble:          If you have trouble using GCC.

Bugs:             How, why and where to report bugs.

Service:          How to find suppliers of support for GCC.

Contributing:     How to contribute to testing and developing GCC.

Funding:          How to help assure funding for free software.

GNU Project:      The GNU Project and GNU/Linux.

Copying:          GNU General Public License says
                     how you can copy and share GCC.

GNU Free Documentation License:  How you can copy and share this manual.

Contributors:     People who have contributed to GCC.

Option Index:     Index to command line options.

Keyword Index:     Index of concepts and symbol names.