// look wikipedia's article for description
		T getPoint(size_t _segment_num,float _t)
		{
			// pivot points
			T P[3];
			//truncated
			float t;

			std::tie(P[0],P[1],P[2],t) = getSegment(_segment_num,_t);

			// Bernstain's polynomials
			float b[] = {
				std::pow(1-t,2.0f),
				2*t*(1-t),
				std::pow(t,2.0f)
			};

			T sum;
			memset(&sum,0,sizeof(T));

			size_t cnt = 3;

			for(size_t i=0;i<cnt;++i)
				sum = sum + P[i]*b[i];

			return sum;
		}

void HeightMap::blitHeights(int xMin, int xMax, int yMin, int yMax, std::vector<float>& heights) const
{

	int xSize = xMax - xMin;

	int segmentXMin = I_ROUND(floor(xMin / (double)mSegmentResolution));
	int segmentXMax = I_ROUND(floor(xMax / (double)mSegmentResolution));
	int segmentYMin = I_ROUND(floor(yMin / (double)mSegmentResolution));
	int segmentYMax = I_ROUND(floor(yMax / (double)mSegmentResolution));

	for (int segmentX = segmentXMin; segmentX <= segmentXMax; ++segmentX) {
		for (int segmentY = segmentYMin; segmentY <= segmentYMax; ++segmentY) {

			auto segmentPtr = getSegment(segmentX, segmentY);
			auto segment = segmentPtr.get();

			int segmentXStart = segmentX * mSegmentResolution;
			int segmentYStart = segmentY * mSegmentResolution;
			int dataXOffset = segmentXStart - xMin;
			int dataYOffset = segmentYStart - yMin;

			int xStart = std::max(xMin - segmentXStart, 0);
			int yStart = std::max(yMin - segmentYStart, 0);
			int xEnd = std::min<int>(xMax - segmentXStart, mSegmentResolution);
			int yEnd = std::min<int>(yMax - segmentYStart, mSegmentResolution);

			for (int x = xStart; x < xEnd; ++x) {
				for (int y = yStart; y < yEnd; ++y) {
					heights[((dataYOffset + y) * xSize) + (dataXOffset + x)] = segment->getHeight(x, y);
				}
			}
		}
	}
}

int MapFile::findEntry(long addr) const
{
	for(int j = 0 ; j < segments() ; ++j)
	{
		const MapFileEntry & segment = getSegment(j);
		long section = segment.section();
		long segmentBegin = loadAddress() + (segment.section() << 12) + segment.offset();
		long segmentEnd = segmentBegin + segment.length();

		if(addr >= segmentBegin && addr < segmentEnd)
		{
			for(int i = entries() - 1 ; i >= 0  ; --i)
			{
				const MapFileEntry entry = getEntry(i);
				if(entry.section() == section)
				{
					long entryAddr = loadAddress() + (entry.section() << 12) + entry.offset();
					if(entryAddr <= addr)
						return i;
				}
			}
		}
	}
	return -1;
}

LLBufferArray::segment_iterator_t LLBufferArray::splitAfter(U8* address)
{
	LLMemType m1(LLMemType::MTYPE_IO_BUFFER);
	segment_iterator_t end = mSegments.end();
	segment_iterator_t it = getSegment(address);
	if(it == end)
	{
		return end;
	}

	// We have the location and the segment.
	U8* base = (*it).data();
	S32 size = (*it).size();
	if(address == (base + size))
	{
		// No need to split, since this is the last byte of the
		// segment. We do not want to have zero length segments, since
		// that will only incur processing overhead with no advantage.
		return it;
	}
	S32 channel = (*it).getChannel();
	LLSegment segment1(channel, base, (address - base) + 1);
	*it = segment1;
	segment_iterator_t rv = it;
	++it;
	LLSegment segment2(channel, address + 1, size - (address - base) - 1);
	mSegments.insert(it, segment2);
	return rv;
}

void
EraseCommand::modifySegment()
{
    bool needRelayOut = eraseInSegment(m_selection);
    if (needRelayOut)
        { m_relayoutEndTime = getSegment().getEndTime(); }
}

void Lightcone::generate() {
	Timer generationTimer;
	generationTimer.start();

	printf(
			"Generating Lightcone with [R:%.2f, Theta: %.2f, Phi: %.2f, Opening: %.2f]\n",
			mR, mTheta, mPhi, mOpening);
	mParticles.clear();
	int fileIndex = 0;
	double rMin = 0;
	double rMax = 0;
	for (vector<double>::iterator it = mRedshiftSteps.begin();
			it != mRedshiftSteps.end(); it++, fileIndex++) {
		rMax = getRFromRedshift(*(it + 1) / 2);
		bool last = false;
		if (rMax > mR) {
			rMax = mR;
			last = true;
		}
		// Load the snapshot according to redshift
		Snapshot snap(TAO_STARTING_ID + fileIndex);
		snap.load();
		vector<Particle> segment = getSegment(snap, rMax, rMin);
		// merge
		mParticles.insert(mParticles.end(), segment.begin(), segment.end());
		rMin = rMax;
		if (last) {
			break;
		}
	}
	printf(
			"[COMPLETE] Lightcone generated, %.0f seconds, with %lu particles inside.\n",
			generationTimer.getSec(), mParticles.size());
}

 /***********************************************************
  * DESCRIPTION:
  * RETURN:
  *    success NO_ERROR
  *    fail    
  ***********************************************************/  
  const int IndexList::moveRidsToNewSub(FILE* pFile, const RID& oldRid, 
                                        const RID& newRid,
                                        IdxEmptyListEntry* newIdxListEntryPtr)
  {    
        int rc;  
        //Write everything out in getSegment  
        m_segType = LIST_SUBBLOCK_TYPE;
                       
        rc =getSegment( m_pFile, ENTRY_32, newIdxListEntryPtr );         
        if (rc != NO_ERROR)
            return rc;
        //This is the new segment   
        m_curType = LIST_SUBBLOCK_TYPE;        
        m_lbid   = newIdxListEntryPtr->fbo;
        m_sbid   = newIdxListEntryPtr->sbid;
        m_entry  = newIdxListEntryPtr->entry;
        if  (m_lbid !=m_hdrLbid)
          rc = readCurBlk();
        rc = insertRid(oldRid, m_entry);
        m_entry++;
        rc = insertRid(newRid, m_entry);
        rc = updateCurCount(2);
                            
        return rc;                                              
  }

void BTreeBuilder::buildUnbalanced(
    ByteInputStream &sortedInputStream,
    RecordNum nEntriesTotal,
    double fillFactor)
{
    // TODO:  common fcn
    // calculate amount of space to reserve on each leaf from fillfactor
    uint cbReserved = getSegment()->getUsablePageSize() - sizeof(BTreeNode);
    cbReserved = uint(cbReserved*(1-fillFactor));

    // start with just a leaf level
    growTree();
    BTreeBuildLevel &level = getLevel(0);
    level.cbReserved = cbReserved;
    level.nEntriesTotal = nEntriesTotal;
    level.processInput(sortedInputStream);

    // NOTE:  It's important to realize that growTree() could be called inside
    // this loop, so it's necessary to recompute levels.size() after each
    // iteration.
    for (uint i = 0; i < levels.size(); ++i) {
        BTreeBuildLevel &level = getLevel(i);
        level.indexLastKey(true);
    }

    swapRoot();
}

int Stream::compare(const Stream *stream) const
{
	for (int offset = 0;;)
	{
		const int length1 = getSegmentLength(offset);
		const int length2 = stream->getSegmentLength(offset);
		if (length1 == 0)
		{
			if (length2)
				return -1;

			return 0;
		}
		if (length2 == 0)
			return 1;
		const int length = MIN (length1, length2);
		const char *p1 = (const char*) getSegment (offset);
		const char *p2 = (const char*) stream->getSegment (offset);
		for (const char *end = p1 + length; p1 < end;)
		{
			int n = *p1++ - *p2++;
			if (n)
				return n;
		}
		offset += length;
	}
}

// Select exactly the beat-defining events, including any extra notes
// this command inserted.
// @author Tom Breton (Tehom)
EventSelection *
SelectAddEvenNotesCommand::getSubsequentSelection()
{
    RG_DEBUG << "SelectAddEvenNotesCommand::getSubsequentSelection";
    EventSelection *selection = new EventSelection(getSegment());

    RG_DEBUG << (int)m_beatEventVector.size()
             << "elements in m_beatEventVector"
             << endl;
    // Add the beat events we found to the selection
    for (BeatEventVector::iterator i = m_beatEventVector.begin();
         i != m_beatEventVector.end();
         ++i) {
        BeatEvent &beatEvent = *i;
        // Skip ties
        selection->addEvent(beatEvent.m_event, false);
    }

    // Also add any events that we made.
    RG_DEBUG << (int)m_eventsAdded.size()
             << "elements in redoEvents"
             << endl;
    for (EventVector::const_iterator i = m_eventsAdded.begin();
         i != m_eventsAdded.end();
         ++i) {
        Event *e = *i;
        // Skip ties
        selection->addEvent(e, false);
    }
    return selection;
}

// Worker function of SelectAddEvenNotesCommand
// Add any extra note events needed to give evenly spaced beats.
// @author Tom Breton (Tehom)
void
SelectAddEvenNotesCommand::modifySegment()
{
    Segment &s = getSegment();
    BeatEventVector &beatEventVector = m_beatEventVector;
    // The time of the previous beat, which we have to carry to the
    // next interpolator.  Initial value is meaningless, since the
    // first beat can have no preceding interpolated beats.
    timeT prevBeatTime = 0;
    for (BeatEventVector::iterator i = beatEventVector.begin();
         i != beatEventVector.end();
         ++i) {
        BeatEvent &beatEvent = *i;
        Event *modelEvent = beatEvent.m_event;
        BeatInterpolator &beatInterpolator =
            beatEvent.m_beatInterpolator;
        for (int j = 0; j < beatEvent.m_numSkippedBeats; ++j) {
            timeT newTime =
                prevBeatTime + beatInterpolator.getBeatRelativeTime(j + 1);
            Event *e = new Event(*modelEvent, newTime);
            s.insert(e);
            m_eventsAdded.push_back(e);
        }
        prevBeatTime = modelEvent->getAbsoluteTime();
    }
}

/**
    \fn updateRefVideo
    \brief Update start time
*/
bool        ADM_EditorSegment::updateRefVideo(void)
{
    int n=videos.size();
    ADM_assert(n);
    _VIDEOS *ref=getRefVideo(n-1);
    vidHeader *demuxer=ref->_aviheader;
    uint64_t pts,dts;

        demuxer->getPtsDts(0,&pts,&dts);
        if(pts!=ADM_NO_PTS && pts >0)
        {
            ADM_warning("Updating firstFramePTS, The first frame has a PTS >0, adjusting to %" PRIu64" ms\n",pts/1000);
            ref->firstFramePts=pts;
        }else
        {
            ADM_info("First PTS is %s\n",ADM_us2plain(pts));
        }

    //
    n=segments.size();
    if(n)
    {
    _SEGMENT *seg=getSegment(n-1);
    uint64_t dur=ref->_aviheader->getVideoDuration();
#ifdef ADM_ZERO_OFFSET
    seg->_refStartTimeUs=pts;
    seg->_durationUs=dur-pts;
#endif
    printf("Current duration %" PRIu64" ms real one %" PRIu64" ms\n",dur/1000,seg->_durationUs/1000);
    }
    updateStartTime();
    return true;
}

char* Stream::getString()
{
	char* const string = new char [totalLength + 1];
	getSegment (0, totalLength, string);
	string [totalLength] = 0;

	return string;
}

bool RobotModel::toggleHighlight(std::string name)
{
    osg::ref_ptr<OSGSegment> seg = getSegment(name);
    assert(seg);

    seg->toggleSelected();
    return seg->isSelected_;
}

	bool Polygon::isPointInside(const Point& p) const
	{
		for (size_t i = 0; i < size(); i++)
		{
			if (getSegment(i).dist(p) < 0)
				return false;
		}
		return true;
	}

static void printMapCPP(const QList<T> &l, const QString &name)
{
    ldbg << name;
    for(int i = 0; i < l.size(); i++) {
        const LineSegment &s = getSegment(l, i);
        ldbg << endl << "<< " << segmentPrefix(l) << "LineSegment(" << s.x1() << "," << s.y1() << "," << s.x2() << "," << s.y2() << ")";
    }
    ldbg << ";" << endl;
}

reg_t reg_t::operator-(const reg_t right) const {
	if (getSegment() == right.getSegment()) {
		// We can subtract numbers, or pointers with the same segment,
		// an operation which will yield a number like in C
		return make_reg(0, toSint16() - right.toSint16());
	} else {
		return *this + make_reg(right.getSegment(), -right.toSint16());
	}
}

bool
AddIndicationCommand::canExecute()
{
    Segment &s(getSegment());

    for (Segment::iterator i = s.begin(); s.isBeforeEndMarker(i); ++i) {

        if ((*i)->getNotationAbsoluteTime() >=
            m_indicationStart + m_indicationDuration) {
            return true;
        }

        if ((*i)->isa(Indication::EventType)) {

            try {
                Indication indication(**i);

                if ((*i)->getNotationAbsoluteTime() +
                    indication.getIndicationDuration() <= m_indicationStart)
                    continue;

                std::string type = indication.getIndicationType();

                if (type == m_indicationType) {
                    // for all indications (including slur), we reject an
                    // exact overlap
                    if ((*i)->getAbsoluteTime() == m_indicationStart &&
                        indication.getIndicationDuration() == m_indicationDuration) {
                        return false;
                    }
                } else if (m_indicationType == Indication::Slur) {
                    continue;
                }

                // for non-slur indications we reject a partial
                // overlap such as this one, if it's an overlap with
                // an indication of the same "sort"

                if (m_indicationType == Indication::Crescendo ||
                    m_indicationType == Indication::Decrescendo) {
                    if (type == Indication::Crescendo ||
                        type == Indication::Decrescendo) return false;
                }

                if (m_indicationType == Indication::QuindicesimaUp ||
                    m_indicationType == Indication::OttavaUp ||
                    m_indicationType == Indication::OttavaDown ||
                    m_indicationType == Indication::QuindicesimaDown) {
                    if (indication.isOttavaType()) return false;
                }
            } catch (...) {}
        }
    }

    return true;
}

void BTreeBuilder::createEmptyRoot()
{
    assert(getRootPageId() == NULL_PAGE_ID);
    BTreePageLock pageLock;
    pageLock.accessSegment(treeDescriptor.segmentAccessor);
    treeDescriptor.rootPageId = pageLock.allocatePage(getPageOwnerId());
    BTreeNode &node = pageLock.getNodeForWrite();
    pLeafNodeAccessor->clearNode(
        node, getSegment()->getUsablePageSize());
}

void
CollapseNotesCommand::modifySegment()
{
    Segment &s(getSegment());
    SegmentNotationHelper helper(s);
    timeT endTime = getEndTime();

    // Because the selection tracks the segment as a SegmentObserver,
    // anything we do to the segment will also affect the selection.

    // And because collapsing a note may delete events before or after
    // it, we can't really iterate through the selection (or segment)
    // while we do it.

    // We also can't test events to find out whether they're still in
    // the segment or not, because the event comparator will crash if
    // an event has actually been deleted.

    // So, we maintain a set of the events we have already seen
    // (checking in this set by pointer comparison only, for safety)
    // and traverse the selection requesting a collapse for each event
    // that is not already in our seen set.  Each time a collapse is
    // requested, we fly back to the start of the selection -- this is
    // partly so we are sure to see any new events that may appear
    // during collapsing, and partly so that our active iterator is
    // always valid even if an event is deleted from the selection.

    QSet<Event *> seen;

    EventSelection::eventcontainer::iterator i =
        m_selection->getSegmentEvents().begin();

    while (i != m_selection->getSegmentEvents().end()) {

        Event *e = *i;

        if (!seen.contains(e)) {

            seen.insert(e);

            Segment::iterator collapsed =
                helper.collapseNoteAggressively(e, endTime);
            if (collapsed != s.end()) {
                m_selection->addEvent(*collapsed);
            }

            i = m_selection->getSegmentEvents().begin();
            continue;
        }

        ++i;
    }
    helper.makeNotesViable(m_selection->getStartTime(), endTime);
    
}