stackAlgorithm.cpp

// SPDX-License-Identifier: Apache-2.0
// Copyright Contributors to the OpenTimelineIO project

#include "opentimelineio/stackAlgorithm.h"
#include "opentimelineio/gap.h"
#include "opentimelineio/track.h"
#include "opentimelineio/trackAlgorithm.h"
#include "opentimelineio/transition.h"

namespace opentimelineio { namespace OPENTIMELINEIO_VERSION_NS {

typedef std::map<Track*, std::map<Composable*, TimeRange>> RangeTrackMap;
typedef std::vector<SerializableObject::Retainer<Track>>   TrackRetainerVector;

static bool
_is_not_visible(
    SerializableObject::Retainer<Composable> thing)
{
    auto item = dynamic_retainer_cast<Item>(thing);
    if (!item)
        return false;

    return !item->visible();
}

static void
_flatten_next_item(
    RangeTrackMap&             range_track_map,
    Track*                     flat_track,
    std::vector<Track*> const& tracks,
    int                        track_index,
    std::optional<TimeRange>   trim_range,
    ErrorStatus*               error_status)
{
    if (track_index < 0)
    {
        track_index = int(tracks.size()) - 1;
    }

    if (track_index < 0)
    {
        return;
    }

    Track* track = tracks[track_index];

    SerializableObject::Retainer<Track> track_retainer;
    if (trim_range)
    {
        track = track_trimmed_to_range(track, *trim_range, error_status);
        if (track == nullptr || is_error(error_status))
        {
            return;
        }
        track_retainer = SerializableObject::Retainer<Track>(track);
    }

    std::map<Composable*, TimeRange>* track_map;
    auto                              it = range_track_map.find(track);
    if (it != range_track_map.end())
    {
        track_map = &it->second;
    }
    else
    {
        auto result = range_track_map.emplace(
            track,
            track->range_of_all_children(error_status));
        if (is_error(error_status))
        {
            return;
        }
        track_map = &result.first->second;
    }

    auto children = track->children();
    for (size_t i = 0; i < children.size(); i++)
    {
        std::optional<TimeRange> trim = std::nullopt;
        SerializableObject::Retainer<Composable> child = children[i];

        // combine all non visible children into one continuous range
        while(track_index > 0 && _is_not_visible(child))
        {
            TimeRange child_trim = (*track_map)[child];

            // offset ranges so they are in track range before being trimmed
            if (trim_range)
            {
                trim = TimeRange(
                    child_trim.start_time() + trim_range->start_time(),
                    child_trim.duration());
                (*track_map)[child] = child_trim;
            }

            if (trim.has_value())
            {
                trim = trim->duration_extended_by(child_trim.duration());
            }
            else
            {
                trim = child_trim;
            }

            if (i+1 < children.size())
            {
                child = children[i++];
            }
            else
            {
                // last item is not visible
                child = nullptr;
                break;
            }
        }

        if (trim.has_value())
        {
            _flatten_next_item(
                range_track_map,
                flat_track,
                tracks,
                track_index - 1,
                trim,
                error_status);

            if (is_error(error_status))
            {
                return;
            }
        }

        if (child)
        {
            auto item = dynamic_retainer_cast<Item>(child);
            if (!item)
            {
                if (!dynamic_retainer_cast<Transition>(child))
                {
                    if (error_status)
                    {
                        *error_status = ErrorStatus(
                            ErrorStatus::TYPE_MISMATCH,
                            "expected item of type Item* || Transition*",
                            child);
                    }
                    return;
                }
            }

            flat_track->insert_child(
                static_cast<int>(flat_track->children().size()),
                static_cast<Composable*>(child->clone(error_status)),
                error_status);

            if (is_error(error_status))
            {
                return;
            }
        }
    }

    // range_track_map persists over the entire duration of flatten_stack
    // track_retainer.value is about to be deleted; it's entirely possible
    // that a new item will be created at the same pointer location, so we
    // have to clean this value out of the map now.
    if (track_retainer)
    {
        range_track_map.erase(track_retainer);
    }
}

// add a gap to end of a track if it is shorter then the longest track.
// shorter tracks are clones and get added to the tracks_retainer.
// a new track will replace the original pointer in the track vector.
static void
_normalize_tracks_lengths(
    std::vector<Track*>& tracks,
    TrackRetainerVector& tracks_retainer,
    ErrorStatus*         error_status)
{
    RationalTime duration;
    for (auto track: tracks)
    {
        duration = std::max(duration, track->duration(error_status));
        if (is_error(error_status))
        {
            return;
        }
    }

    for (size_t i = 0; i < tracks.size(); i++)
    {
        Track*       old_track      = tracks[i];
        RationalTime track_duration = old_track->duration(error_status);
        if (track_duration < duration)
        {
            Track* new_track =
                static_cast<Track*>(old_track->clone(error_status));
            if (is_error(error_status))
            {
                return;
            }
            // add track to retainer so it can be freed later
            tracks_retainer.push_back(
                SerializableObject::Retainer<Track>(new_track));
            new_track->append_child(
                new Gap(duration - track_duration),
                error_status);
            if (is_error(error_status))
            {
                return;
            }
            tracks[i] = new_track;
        }
    }
}

Track*
flatten_stack(Stack* in_stack, ErrorStatus* error_status)
{
    std::vector<Track*> tracks;
    // tracks are cloned if they need to be normalized
    // they get added to this retainer so they can be
    // freed when the algorithm is complete
    TrackRetainerVector tracks_retainer;
    tracks.reserve(in_stack->children().size());

    for (auto c: in_stack->children())
    {
        if (auto track = dynamic_retainer_cast<Track>(c))
        {
            if (track->enabled())
            {
                tracks.push_back(track);
            }
        }
        else
        {
            if (error_status)
            {
                *error_status = ErrorStatus(
                    ErrorStatus::TYPE_MISMATCH,
                    "expected item of type Track*",
                    c);
            }
            return nullptr;
        }
    }

    _normalize_tracks_lengths(tracks, tracks_retainer, error_status);
    if (is_error(error_status))
    {
        return nullptr;
    }

    Track* flat_track = new Track;
    flat_track->set_name("Flattened");

    RangeTrackMap range_track_map;
    _flatten_next_item(
        range_track_map,
        flat_track,
        tracks,
        -1,
        std::nullopt,
        error_status);
    return flat_track;
}

Track*
flatten_stack(std::vector<Track*> const& tracks, ErrorStatus* error_status)
{
    std::vector<Track*> flat_tracks;
    // tracks are cloned if they need to be normalized
    // they get added to this retainer so they can be
    // freed when the algorithm is complete
    TrackRetainerVector tracks_retainer;
    flat_tracks.reserve(tracks.size());
    for (auto track: tracks)
    {
        flat_tracks.push_back(track);
    }

    _normalize_tracks_lengths(flat_tracks, tracks_retainer, error_status);
    if (is_error(error_status))
    {
        return nullptr;
    }

    Track* flat_track = new Track;
    flat_track->set_name("Flattened");

    RangeTrackMap range_track_map;
    _flatten_next_item(
        range_track_map,
        flat_track,
        flat_tracks,
        -1,
        std::nullopt,
        error_status);
    return flat_track;
}
}} // namespace opentimelineio::OPENTIMELINEIO_VERSION_NS