def test_LabelledPointUndirectedGraph_remove_label():
    lgroup = LabelledPointUndirectedGraph(points, adjacency_matrix, mask_dict_3)

    new_lgroup = lgroup.remove_label('lower')

    assert 'all' in new_lgroup.labels
    assert 'lower' not in new_lgroup.labels
    assert 'all' in lgroup.labels

def test_LabelledPointUndirectedGraph_add_label():
    lgroup = LabelledPointUndirectedGraph(points, adjacency_matrix, mask_dict_2)

    new_lgroup = lgroup.add_label('lower2', [0, 1])
    assert not is_same_array(new_lgroup.points, lgroup.points)

    lower_pcloud = new_lgroup.get_label('lower2')
    assert lower_pcloud.n_points == 2
    assert_allclose(lower_pcloud.points[0, :], [1., 1., 1.])
    assert_allclose(lower_pcloud.points[1, :], [1., 1., 1.])

def test_LabelledPointUndirectedGraph_copy_method():
    lgroup = LabelledPointUndirectedGraph(points, adjacency_matrix, mask_dict)
    lgroup_copy = lgroup.copy()

    assert not is_same_array(lgroup_copy.points, lgroup.points)
    # Check the mask dictionary is deepcopied properly
    assert lgroup._labels_to_masks is not lgroup_copy._labels_to_masks
    masks = zip(lgroup_copy._labels_to_masks.values(),
                lgroup._labels_to_masks.values())
    for ms in masks:
        assert ms[0] is not ms[1]

def test_LabelledPointUndirectedGraph_add_ordered_labels():
    lgroup = LabelledPointUndirectedGraph(points, adjacency_matrix, mask_dict_2)

    labels = lgroup.labels
    assert labels[0] == 'lower'
    assert labels[1] == 'upper'

    new_lgroup = lgroup.add_label('A', [0, 1])
    new_labels = new_lgroup.labels

    assert new_labels[2] == 'A'

def test_LabelledPointUndirectedGraph_with_labels():
    lgroup = LabelledPointUndirectedGraph(points, adjacency_matrix, mask_dict_2)

    new_lgroup = lgroup.with_labels('lower')

    assert new_lgroup.n_labels == 1
    assert new_lgroup.n_points == 6
    assert 'lower' in new_lgroup.labels

    new_lgroup = lgroup.with_labels(['lower'])

    assert new_lgroup.n_labels == 1
    assert new_lgroup.n_points == 6
    assert 'lower' in new_lgroup.labels

def eye_ibug_close_17_to_eye_ibug_close_17(pcloud):
    r"""
    Apply the IBUG 17-point close eye semantic labels.

    The semantic labels applied are as follows:

      - upper_eyelid
      - lower_eyelid
    """
    from menpo.shape import LabelledPointUndirectedGraph

    n_expected_points = 17
    validate_input(pcloud, n_expected_points)

    upper_indices, upper_connectivity = _build_upper_eyelid()

    middle_indices = np.arange(12, 17)
    bottom_indices = np.arange(6, 12)
    lower_indices = np.hstack((bottom_indices, 0, middle_indices))
    lower_connectivity = list(zip(bottom_indices, bottom_indices[1:]))
    lower_connectivity += [(0, 12)]
    lower_connectivity += list(zip(middle_indices, middle_indices[1:]))
    lower_connectivity += [(11, 0)]

    all_connectivity = np.asarray(upper_connectivity + lower_connectivity)

    mapping = OrderedDict()
    mapping['upper_eyelid'] = upper_indices
    mapping['lower_eyelid'] = lower_indices

    new_pcloud = LabelledPointUndirectedGraph.init_from_indices_mapping(
        pcloud.points, all_connectivity, mapping)

    return new_pcloud, mapping

def car_streetscene_20_to_car_streetscene_view_5_10(pcloud):
    r"""
    Apply the 10-point semantic labels of "view 5" from the MIT Street Scene
    Car dataset (originally a 20-point markup).

    The semantic labels applied are as follows:

      - right_side

    References
    ----------
    .. [1] http://www.cs.cmu.edu/~vboddeti/alignment.html
    """
    from menpo.shape import LabelledPointUndirectedGraph

    n_expected_points = 20
    validate_input(pcloud, n_expected_points)

    right_side_indices = np.array([0, 1, 2, 3, 4, 5, 6, 7, 9, 8])

    right_side_connectivity = connectivity_from_array(right_side_indices,
                                                      close_loop=True)

    all_connectivity = right_side_connectivity

    mapping = OrderedDict()
    mapping['right_side'] = right_side_indices

    ind = np.array([1, 3, 5, 7, 9, 11, 13, 15, 17, 19])
    new_pcloud = LabelledPointUndirectedGraph.init_from_indices_mapping(
        pcloud.points[ind], all_connectivity, mapping)

    return new_pcloud, mapping

def _parse_ljson_v1(lms_dict):
    all_points = []
    labels = []  # label per group
    labels_slices = []  # slices into the full pointcloud per label
    offset = 0
    connectivity = []
    for group in lms_dict['groups']:
        lms = group['landmarks']
        labels.append(group['label'])
        labels_slices.append(slice(offset, len(lms) + offset))
        # Create the connectivity if it exists
        conn = group.get('connectivity', [])
        if conn:
            # Offset relative connectivity according to the current index
            conn = offset + np.asarray(conn)
            connectivity += conn.tolist()
        for p in lms:
            all_points.append(p['point'])
        offset += len(lms)

    # Don't create a PointUndirectedGraph with no connectivity
    points = _ljson_parse_null_values(all_points)
    n_points = points.shape[0]

    labels_to_masks = OrderedDict()
    # go through each label and build the appropriate boolean array
    for label, l_slice in zip(labels, labels_slices):
        mask = np.zeros(n_points, dtype=np.bool)
        mask[l_slice] = True
        labels_to_masks[label] = mask

    lmarks = LabelledPointUndirectedGraph.init_from_edges(points, connectivity,
                                                          labels_to_masks)
    return {'LJSON': lmarks}

def eye_ibug_open_38_to_eye_ibug_open_38(pcloud):
    r"""
    Apply the IBUG 38-point open eye semantic labels.

    The semantic labels applied are as follows:

      - upper_eyelid
      - lower_eyelid
      - iris
      - pupil
      - sclera
    """
    from menpo.shape import LabelledPointUndirectedGraph

    n_expected_points = 38
    validate_input(pcloud, n_expected_points)

    upper_el_indices, upper_el_connectivity = _build_upper_eyelid()

    iris_range = (22, 30)
    pupil_range = (30, 38)
    sclera_top = np.arange(12, 17)
    sclera_bottom = np.arange(17, 22)
    sclera_indices = np.hstack((0, sclera_top, 6, sclera_bottom))
    lower_el_top = np.arange(17, 22)
    lower_el_bottom = np.arange(7, 12)
    lower_el_indices = np.hstack((6, lower_el_top, 0, lower_el_bottom))

    iris_connectivity = connectivity_from_range(iris_range, close_loop=True)
    pupil_connectivity = connectivity_from_range(pupil_range, close_loop=True)

    sclera_connectivity = list(zip(sclera_top, sclera_top[1:]))
    sclera_connectivity += [(0, 21)]
    sclera_connectivity += list(zip(sclera_bottom, sclera_bottom[1:]))
    sclera_connectivity += [(6, 17)]

    lower_el_connectivity = list(zip(lower_el_top, lower_el_top[1:]))
    lower_el_connectivity += [(6, 7)]
    lower_el_connectivity += list(zip(lower_el_bottom, lower_el_bottom[1:]))
    lower_el_connectivity += [(11, 0)]

    all_connectivity = np.asarray(upper_el_connectivity +
                                  lower_el_connectivity +
                                  iris_connectivity.tolist() +
                                  pupil_connectivity.tolist() +
                                  sclera_connectivity)

    mapping = OrderedDict()
    mapping['upper_eyelid'] = upper_el_indices
    mapping['lower_eyelid'] = lower_el_indices
    mapping['pupil'] = np.arange(*pupil_range)
    mapping['iris'] = np.arange(*iris_range)
    mapping['sclera'] = sclera_indices

    new_pcloud = LabelledPointUndirectedGraph.init_from_indices_mapping(
        pcloud.points, all_connectivity, mapping)

    return new_pcloud, mapping

def hand_ibug_39_to_hand_ibug_39(pcloud):
    r"""
    Apply the IBUG 39-point semantic labels.

    The semantic labels applied are as follows:

      - thumb
      - index
      - middle
      - ring
      - pinky
      - palm
    """
    from menpo.shape import LabelledPointUndirectedGraph

    n_expected_points = 39
    validate_input(pcloud, n_expected_points)

    thumb_indices = np.arange(0, 5)
    index_indices = np.arange(5, 12)
    middle_indices = np.arange(12, 19)
    ring_indices = np.arange(19, 26)
    pinky_indices = np.arange(26, 33)
    palm_indices = np.hstack((np.array([32, 25, 18, 11, 33, 34, 4]),
                              np.arange(35, 39)))

    thumb_connectivity = connectivity_from_array(thumb_indices,
                                                 close_loop=False)
    index_connectivity = connectivity_from_array(index_indices,
                                                 close_loop=False)
    middle_connectivity = connectivity_from_array(middle_indices,
                                                  close_loop=False)
    ring_connectivity = connectivity_from_array(ring_indices,
                                                close_loop=False)
    pinky_connectivity = connectivity_from_array(pinky_indices,
                                                 close_loop=False)
    palm_connectivity = connectivity_from_array(palm_indices,
                                                close_loop=True)

    all_connectivity = np.vstack([thumb_connectivity, index_connectivity,
                                  middle_connectivity, ring_connectivity,
                                  pinky_connectivity, palm_connectivity])

    mapping = OrderedDict()
    mapping['thumb'] = thumb_indices
    mapping['index'] = index_indices
    mapping['middle'] = middle_indices
    mapping['ring'] = ring_indices
    mapping['pinky'] = pinky_indices
    mapping['palm'] = palm_indices

    new_pcloud = LabelledPointUndirectedGraph.init_from_indices_mapping(
        pcloud.points, all_connectivity, mapping)

    return new_pcloud, mapping

def car_streetscene_20_to_car_streetscene_view_1_14(pcloud):
    """
    Apply the 14-point semantic labels of "view 1" from the MIT Street Scene
    Car dataset (originally a 20-point markup).

    The semantic labels applied are as follows:

      - front
      - bonnet
      - windshield
      - left_side

    References
    ----------
    .. [1] http://www.cs.cmu.edu/~vboddeti/alignment.html
    """
    from menpo.shape import LabelledPointUndirectedGraph

    n_expected_points = 20
    validate_input(pcloud, n_expected_points)

    front_indices = np.array([0, 1, 3, 2])
    bonnet_indices = np.array([2, 3, 5, 4])
    windshield_indices = np.array([4, 5, 7, 6])
    left_side_indices = np.array([0, 2, 4, 6, 8, 9, 10, 11, 13, 12])

    front_connectivity = connectivity_from_array(front_indices,
                                                 close_loop=True)
    bonnet_connectivity = connectivity_from_array(bonnet_indices,
                                                  close_loop=True)
    windshield_connectivity = connectivity_from_array(windshield_indices,
                                                      close_loop=True)
    left_side_connectivity = connectivity_from_array(left_side_indices,
                                                     close_loop=True)

    all_connectivity = np.vstack([
        front_connectivity, bonnet_connectivity, windshield_connectivity,
        left_side_connectivity
    ])

    mapping = OrderedDict()
    mapping['front'] = front_indices
    mapping['bonnet'] = bonnet_indices
    mapping['windshield'] = windshield_indices
    mapping['left_side'] = left_side_indices

    ind = np.hstack((np.arange(9), np.array([10, 12, 14, 16, 18])))
    new_pcloud = LabelledPointUndirectedGraph.init_from_indices_mapping(
        pcloud.points[ind], all_connectivity, mapping)

    return new_pcloud, mapping

def pose_lsp_14_to_pose_lsp_14(pcloud):
    r"""
    Apply the lsp 14-point semantic labels.

    The semantic labels applied are as follows:

      - left_leg
      - right_leg
      - left_arm
      - right_arm
      - head

    References
    ----------
    .. [1] http://www.comp.leeds.ac.uk/mat4saj/lsp.html
    """
    from menpo.shape import LabelledPointUndirectedGraph

    n_expected_points = 14
    validate_input(pcloud, n_expected_points)

    left_leg_indices = np.arange(0, 3)
    right_leg_indices = np.arange(3, 6)
    left_arm_indices = np.arange(6, 9)
    right_arm_indices = np.arange(9, 12)
    head_indices = np.arange(12, 14)

    left_leg_connectivity = connectivity_from_array(left_leg_indices)
    right_leg_connectivity = connectivity_from_array(right_leg_indices)
    left_arm_connectivity = connectivity_from_array(left_arm_indices)
    right_arm_connectivity = connectivity_from_array(right_arm_indices)
    head_connectivity = connectivity_from_array(head_indices)

    all_connectivity = np.vstack([
        left_leg_connectivity, right_leg_connectivity,
        left_arm_connectivity, right_arm_connectivity,
        head_connectivity
    ])

    mapping = OrderedDict()
    mapping['left_leg'] = left_leg_indices
    mapping['right_leg'] = right_leg_indices
    mapping['left_arm'] = left_arm_indices
    mapping['right_arm'] = right_arm_indices
    mapping['head'] = head_indices

    new_pcloud = LabelledPointUndirectedGraph.init_from_indices_mapping(
        pcloud.points, all_connectivity, mapping)

    return new_pcloud, mapping

def car_streetscene_20_to_car_streetscene_view_6_14(pcloud):
    r"""
    Apply the 14-point semantic labels of "view 6" from the MIT Street Scene
    Car dataset (originally a 20-point markup).

    The semantic labels applied are as follows:

      - right_side
      - rear_windshield
      - trunk
      - rear

    References
    ----------
    .. [1] http://www.cs.cmu.edu/~vboddeti/alignment.html
    """
    from menpo.shape import LabelledPointUndirectedGraph

    n_expected_points = 20
    validate_input(pcloud, n_expected_points)

    right_side_indices = np.array([0, 1, 2, 3, 5, 7, 9, 11, 13, 12])
    rear_windshield_indices = np.array([4, 5, 7, 6])
    trunk_indices = np.array([6, 7, 9, 8])
    rear_indices = np.array([8, 9, 11, 10])

    right_side_connectivity = connectivity_from_array(right_side_indices,
                                                      close_loop=True)
    rear_windshield_connectivity = connectivity_from_array(
        rear_windshield_indices, close_loop=True)
    trunk_connectivity = connectivity_from_array(trunk_indices, close_loop=True)
    rear_connectivity = connectivity_from_array(rear_indices, close_loop=True)

    all_connectivity = np.vstack([
        right_side_connectivity, rear_windshield_connectivity,
        trunk_connectivity, rear_connectivity
    ])

    mapping = OrderedDict()
    mapping['right_side'] = right_side_indices
    mapping['rear_windshield'] = rear_windshield_indices
    mapping['trunk'] = trunk_indices
    mapping['rear'] = rear_indices

    ind = np.array([1, 3, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 19])
    new_pcloud = LabelledPointUndirectedGraph.init_from_indices_mapping(
        pcloud.points[ind], all_connectivity, mapping)

    return new_pcloud, mapping

def _parse_ljson_v2(lms_dict):
    points = _ljson_parse_null_values(lms_dict['landmarks']['points'])
    connectivity = lms_dict['landmarks'].get('connectivity')

    if connectivity is None and len(lms_dict['labels']) == 0:
        return PointCloud(points)
    else:
        labels_to_mask = OrderedDict() # masks into the pointcloud per label
        n_points = points.shape[0]
        for label in lms_dict['labels']:
            mask = np.zeros(n_points, dtype=np.bool)
            mask[label['mask']] = True
            labels_to_mask[label['label']] = mask
        # Note that we can pass connectivity as None here and the edges will be
        # empty.
        return LabelledPointUndirectedGraph.init_from_edges(
            points, connectivity, labels_to_mask)

def pcloud_and_lgroup_from_ranges(pointcloud, labels_to_ranges):
    """
    Label the given pointcloud according to the given ordered dictionary
    of labels to ranges. This assumes that you can semantically label the group
    by using ranges in to the existing points e.g ::

        labels_to_ranges = {'jaw': (0, 17, False)}

    The third element of the range tuple is whether the range is a closed loop
    or not. For example, for an eye landmark this would be ``True``, as you
    do want to create a closed loop for an eye.

    Parameters
    ----------
    pointcloud : :map:`PointCloud`
        The pointcloud to apply semantic labels to.
    labels_to_ranges : `ordereddict` {`str` -> (`int`, `int`, `bool`)}
        Ordered dictionary of string labels to range tuples.

    Returns
    -------
    new_pcloud : :map:`PointCloud`
        New pointcloud with specific connectivity information applied.
    mapping : `ordereddict` {`str` -> `int ndarray`}
        For each label, the indices in to the pointcloud that belong to the
        label.
    """
    from menpo.shape import LabelledPointUndirectedGraph

    mapping = OrderedDict()
    all_connectivity = []
    for label, tup in labels_to_ranges.items():
        range_tuple = tup[:-1]
        close_loop = tup[-1]

        connectivity = connectivity_from_range(range_tuple,
                                               close_loop=close_loop)
        all_connectivity.append(connectivity)
        mapping[label] = np.arange(*range_tuple)
    all_connectivity = np.vstack(all_connectivity)

    new_pcloud = LabelledPointUndirectedGraph.init_from_indices_mapping(
        pointcloud.points, all_connectivity, mapping)

    return new_pcloud, mapping

def face_ibug_68_to_face_ibug_65(pcloud):
    r"""
    Apply the IBUG 68 point semantic labels, but ignore the 3 points that are
    coincident for a closed mouth (bottom of the inner mouth).

    The semantic labels applied are as follows:

      - jaw
      - left_eyebrow
      - right_eyebrow
      - nose
      - left_eye
      - right_eye
      - mouth

    References
    ----------
    .. [1] http://www.multipie.org/
    .. [2] http://ibug.doc.ic.ac.uk/resources/300-W/
    """
    from menpo.shape import LabelledPointUndirectedGraph

    # Apply face_ibug_68_to_face_ibug_68
    new_pcloud, mapping = face_ibug_68_to_face_ibug_68(pcloud,
                                                       return_mapping=True)

    # The coincident points are considered the final 3 landmarks (bottom of
    # the inner mouth points). We remove all the edges for the inner mouth
    # which are the last 8.
    edges = new_pcloud.edges[:-8]
    # Re-add the inner mouth without the bottom 3 points
    edges = np.vstack([edges,
                       connectivity_from_range((60, 65), close_loop=True)])

    # Luckily, OrderedDict maintains the original ordering despite updates
    outer_mouth_indices = np.arange(48, 60)
    inner_mouth_indices = np.arange(60, 65)
    mapping['mouth'] = np.hstack([outer_mouth_indices, inner_mouth_indices])

    new_pcloud = LabelledPointUndirectedGraph.init_from_indices_mapping(
        new_pcloud.points[:-3], edges, mapping)

    return new_pcloud, mapping

def _parse_ljson_v3(lms_dict):
    all_lms = {}
    for key, lms_dict_group in lms_dict['groups'].items():
        points = _ljson_parse_null_values(lms_dict_group['landmarks']['points'])
        connectivity = lms_dict_group['landmarks'].get('connectivity')
        # TODO: create the metadata label!

        if connectivity is None and len(lms_dict_group['labels']) == 0:
            all_lms[key] = PointCloud(points)
        else:
            # masks into the pointcloud per label
            labels_to_mask = OrderedDict()
            n_points = points.shape[0]
            for label in lms_dict_group['labels']:
                mask = np.zeros(n_points, dtype=np.bool)
                mask[label['mask']] = True
                labels_to_mask[label['label']] = mask

            # Note that we can pass connectivity as None here and the edges
            # will be empty.
            all_lms[key] = LabelledPointUndirectedGraph.init_from_edges(
                    points, connectivity, labels_to_mask)
    return all_lms

def _parse_ljson_v1(lms_dict):
    from menpo.base import MenpoDeprecationWarning
    warnings.warn('LJSON v1 is deprecated. export_landmark_file{s}() will '
                  'only save out LJSON v2 files. Please convert all LJSON '
                  'files to v2 by importing into Menpo and re-exporting to '
                  'overwrite the files.', MenpoDeprecationWarning)
    all_points = []
    labels = []  # label per group
    labels_slices = []  # slices into the full pointcloud per label
    offset = 0
    connectivity = []
    for group in lms_dict['groups']:
        lms = group['landmarks']
        labels.append(group['label'])
        labels_slices.append(slice(offset, len(lms) + offset))
        # Create the connectivity if it exists
        conn = group.get('connectivity', [])
        if conn:
            # Offset relative connectivity according to the current index
            conn = offset + np.asarray(conn)
            connectivity += conn.tolist()
        for p in lms:
            all_points.append(p['point'])
        offset += len(lms)

    # Don't create a PointUndirectedGraph with no connectivity
    points = _ljson_parse_null_values(all_points)
    n_points = points.shape[0]

    labels_to_masks = OrderedDict()
    # go through each label and build the appropriate boolean array
    for label, l_slice in zip(labels, labels_slices):
        mask = np.zeros(n_points, dtype=np.bool)
        mask[l_slice] = True
        labels_to_masks[label] = mask

    return LabelledPointUndirectedGraph.init_from_edges(points, connectivity, labels_to_masks)

def test_LabelledPointUndirectedGraph_get_label():
    pcloud = LabelledPointUndirectedGraph(points, adjacency_matrix, mask_dict_2)

    assert isinstance(pcloud, PointUndirectedGraph)
    assert pcloud.get_label('lower').n_points == 6
    assert pcloud.get_label('upper').n_points == 4

def asf_importer(filepath, asset=None, **kwargs):
    r"""
    Importer for the ASF file format.

    For images, the `x` and `y` axes are flipped such that the first axis is
    `y` (height in the image domain).

    Currently only open and closed path types are supported.

    Landmark labels:

    +---------+
    | label   |
    +=========+
    | all     |
    +---------+

    Parameters
    ----------
    filepath : `Path`
        Absolute filepath of the file.
    asset : `object`, optional
        An optional asset that may help with loading. This is unused for this
        implementation.
    \**kwargs : `dict`, optional
        Any other keyword arguments.

    Returns
    -------
    landmarks : :map:`LabelledPointUndirectedGraph`
        The landmarks including appropriate labels if available.

    References
    ----------
    .. [1] http://www2.imm.dtu.dk/~aam/datasets/datasets.html
    """
    with open(str(filepath), 'r') as f:
        landmarks = f.read()

    # Remove comments and blank lines
    landmarks = [l for l in landmarks.splitlines()
                 if (l.rstrip() and not '#' in l)]

    # Pop the front of the list for the number of landmarks
    count = int(landmarks.pop(0))
    # Pop the last element of the list for the image_name
    image_name = landmarks.pop()

    xs = np.empty([count, 1])
    ys = np.empty([count, 1])
    connectivity = []

    # Only unpack the first 7 (the last 3 are always 0)
    split_landmarks = [ASFPath(*landmarks[i].split()[:7])
                       for i in range(count)]
    paths = [list(g)
             for k, g in itertools.groupby(split_landmarks, lambda x: x[0])]
    vert_index = 0
    for path in paths:
        if path:
            path_type = path[0].path_type
        for vertex in path:
            # Relative coordinates, will be scaled by the image size
            xs[vert_index, ...] = float(vertex.xpos)
            ys[vert_index, ...] = float(vertex.ypos)
            vert_index += 1
            # If True, isolated point
            if not (vertex.connects_from == vertex.connects_to and
                    vertex.connects_to == vertex.point_num):
                # Connectivity is defined by connects_from and connects_to
                # as well as the path_type:
                #   Bit 1: Outer edge point/Inside point
                #   Bit 2: Original annotated point/Artificial point
                #   Bit 3: Closed path point/Open path point
                #   Bit 4: Non-hole/Hole point
                # For now we only parse cases 0 and 4 (closed or open)
                connectivity.append((int(vertex.point_num),
                                     int(vertex.connects_to)))
        if path_type == '0':
            connectivity.append((int(path[-1].point_num),
                                 int(path[0].point_num)))

    connectivity = np.vstack(connectivity)
    points = np.hstack([ys, xs])
    if asset is not None:
        # we've been given an asset. As ASF files are normalized,
        # fix that here
        points = Scale(np.array(asset.shape)).apply(points)

    labels_to_masks = OrderedDict(
        [('all', np.ones(points.shape[0], dtype=np.bool))])
    return LabelledPointUndirectedGraph.init_from_edges(points, connectivity,
                                                        labels_to_masks)