path: root/diplomacy/engine/map.py

# ==============================================================================
# Copyright (C) 2019 - Philip Paquette
#
#  This program is free software: you can redistribute it and/or modify it under
#  the terms of the GNU Affero General Public License as published by the Free
#  Software Foundation, either version 3 of the License, or (at your option) any
#  later version.
#
#  This program is distributed in the hope that it will be useful, but WITHOUT
#  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
#  FOR A PARTICULAR PURPOSE.  See the GNU Affero General Public License for more
#  details.
#
#  You should have received a copy of the GNU Affero General Public License along
#  with this program.  If not, see <https://www.gnu.org/licenses/>.
# ==============================================================================
# -*- coding: utf-8 -*-
# pylint: disable=too-many-lines
""" Map
    - Contains the map object which represents a map where the game can be played
"""
from copy import deepcopy
import os
from diplomacy import settings
from diplomacy.utils import KEYWORDS, ALIASES
import diplomacy.utils.errors as err

# Constants
UNDETERMINED, POWER, UNIT, LOCATION, COAST, ORDER, MOVE_SEP, OTHER = 0, 1, 2, 3, 4, 5, 6, 7
MAP_CACHE = {}


class Map():
    """ MAP Class

    Properties:
        - abbrev: Contains the power abbreviation, otherwise defaults to first letter of PowerName
                e.g. {'ENGLISH': 'E'}
        - abuts_cache: Contains a cache of abuts for ['A,'F'] between all locations for orders ['S', 'C', '-']
                e.g. {(A, PAR, -, MAR): 1, ...}
        - aliases: Contains a dict of all the aliases (e.g. full province name to 3 char)
                e.g. {'EAST': 'EAS', 'STP ( /SC )': 'STP/SC', 'FRENCH': 'FRANCE', 'BUDAPEST': 'BUD', 'NOR': 'NWY', ... }
        - centers: Contains a dict of currently owned supply centers for each player
                e.g. {'RUSSIA': ['MOS', 'SEV', 'STP', 'WAR'], 'FRANCE': ['BRE', 'MAR', 'PAR'], ... }
        - convoy_paths: Contains a list of all possible convoys paths bucketed by number of fleets
                format: {nb of fleets: [(START_LOC, {FLEET LOC}, {DEST LOCS})]}
        - dummies: Indicates the list of powers that are dummies
                e.g. ['FRANCE', 'ITALY']
        - error: Contains a list of errors that the map generated
                e.g. [''DUPLICATE MAP ALIAS OR POWER: JAPAN']
        - files: Contains a list of files that were loaded (e.g. USES keyword)
                e.g. ['standard.map', 'standard.politics', 'standard.geography', 'standard.military']
        - first_year: Indicates the year where the game is starting.
                e.g. 1901
        - flow: List that contains the seasons with the phases
                e.g. ['SPRING:MOVEMENT,RETREATS', 'FALL:MOVEMENT,RETREATS', 'WINTER:ADJUSTMENTS']
        - flow_sign: Indicate the direction of flow (1 is positive, -1 is negative)
                e.g. 1
        - homes: Contains the list of supply centers where units can be built (i.e. assigned at the beginning)
                e.g. {'RUSSIA': ['MOS', 'SEV', 'STP', 'WAR'], 'FRANCE': ['BRE', 'MAR', 'PAR'], ... }
        - inhabits: List that indicates which power have a INHABITS, HOME, or HOMES line
                e.g. ['FRANCE']
        - keywords: Contains a dict of keywords to parse status files and orders
                e.g. {'BUILDS': 'B', '>': '', 'SC': '/SC', 'REMOVING': 'D', 'WAIVED': 'V', 'ATTACK': '', ... }
        - loc_abut: Contains a adjacency list for each province
                e.g. {'LVP': ['CLY', 'edi', 'IRI', 'NAO', 'WAL', 'yor'], ...}
        - loc_coasts: Contains a mapping of all coasts for every location
                e.g. {'PAR': ['PAR'], 'BUL': ['BUL', 'BUL/EC', 'BUL/SC'], ... }
        - loc_name: Dict that indicates the 3 letter name of each location
                e.g. {'GULF OF LYON': 'LYO', 'BREST': 'BRE', 'BUDAPEST': 'BUD', 'RUHR': 'RUH', ... }
        - loc_type: Dict that indicates if each location is 'WATER', 'COAST', 'LAND', or 'PORT'
                e.g. {'MAO': 'WATER', 'SER': 'LAND', 'SYR': 'COAST', 'MOS': 'LAND', 'VEN': 'COAST', ... }
        - locs: List of 3 letter locations (With coasts)
                e.g. ['ADR', 'AEG', 'ALB', 'ANK', 'APU', 'ARM', 'BAL', 'BAR', 'BEL', 'BER', ... ]
        - name: Name of the map
                e.g. 'standard'
        - own_word: Dict to indicate the word used to refer to people living in each power's country
                e.g. {'RUSSIA': 'RUSSIAN', 'FRANCE': 'FRENCH', 'UNOWNED': 'UNOWNED', 'TURKEY': 'TURKISH', ... }
        - owns: List that indicates which power have a OWNS or CENTERS line
                e.g. ['FRANCE']
        - phase: String to indicate the beginning phase of the map
                e.g. 'SPRING 1901 MOVEMENT'
        - phase_abbrev: Dict to indicate the 1 letter abbreviation for each phase
                e.g. {'A': 'ADJUSTMENTS', 'M': 'MOVEMENT', 'R': 'RETREATS'}
        - pow_name: Dict to indicate the power's name
                e.g. {'RUSSIA': 'RUSSIA', 'FRANCE': 'FRANCE', 'TURKEY': 'TURKEY', 'GERMANY': 'GERMANY', ... }
        - powers: Contains the list of powers (players) in the game
                e.g. ['AUSTRIA', 'ENGLAND', 'FRANCE', 'GERMANY', 'ITALY', 'RUSSIA', 'TURKEY']
        - root_map: Contains the name of the original map file loaded (before the USES keyword are applied)
                    A map that is called with MAP is the root_map
                e.g. 'standard'
        - rules: Contains a list of rules used by all variants (for display only)
                e.g. ['RULE_1']
        - scs: Contains a list of all the supply centers in the game
                e.g. ['MOS', 'SEV', 'STP', 'WAR', 'BRE', 'MAR', 'PAR', 'BEL', 'BUL', 'DEN', 'GRE', 'HOL', 'NWY', ... ]
        - seq: [] Contains the sequence of seasons in format 'SEASON_NAME SEASON_TYPE'
                e.g. ['NEWYEAR', 'SPRING MOVEMENT', 'SPRING RETREATS', 'FALL MOVEMENT', 'FALL RETREATS',
                      'WINTER ADJUSTMENTS']
        - unclear: Contains the alias for ambiguous places
                e.g. {'EAST': 'EAS'}
        - unit_names: {} Contains a dict of the unit names
                e.g. {'F': 'FLEET', 'A': 'ARMY'}
        - units: Dict that contains the current position of each unit by power
                e.g. {'FRANCE': ['F BRE', 'A MAR', 'A PAR'], 'RUSSIA': ['A WAR', 'A MOS', 'F SEV', 'F STP/SC'], ... }
        - validated: Boolean to indicate if the map file has been validated
                e.g. 1
        - victory: Indicates the number of supply centers to win the game (>50% required if None)
                e.g. 18
    """
    # pylint: disable=too-many-instance-attributes

    __slots__ = ['name', 'first_year', 'victory', 'phase', 'validated', 'flow_sign', 'root_map', 'abuts_cache',
                 'homes', 'loc_name', 'loc_type', 'loc_abut', 'loc_coasts', 'own_word', 'abbrev', 'centers', 'units',
                 'pow_name', 'rules', 'files', 'powers', 'scs', 'owns', 'inhabits', 'flow', 'dummies', 'locs', 'error',
                 'seq', 'phase_abbrev', 'unclear', 'unit_names', 'keywords', 'aliases', 'convoy_paths']

    def __new__(cls, name='standard', use_cache=True):
        """ New function - Retrieving object from cache if possible
            :param name: Name of the map to load
            :param use_cache: Boolean flag to indicate we want a blank object that doesn't use cache
        """
        if name in MAP_CACHE and use_cache:
            return MAP_CACHE[name]
        return object.__new__(cls)

    def __init__(self, name='standard', use_cache=True):
        """ Constructor function
            :param name: Name of the map to load
            :param use_cache: Boolean flag to indicate we want a blank object that doesn't use cache
        """
        if name in MAP_CACHE:
            return
        self.name = name
        self.first_year = 1901
        self.victory = self.phase = self.validated = self.flow_sign = None
        self.root_map = None
        self.abuts_cache = {}
        self.homes, self.loc_name, self.loc_type, self.loc_abut, self.loc_coasts = {}, {}, {}, {}, {}
        self.own_word, self.abbrev, self.centers, self.units, self.pow_name = {}, {}, {}, {}, {}
        self.rules, self.files, self.powers, self.scs, self.owns, self.inhabits = [], [], [], [], [], []
        self.flow, self.dummies, self.locs = [], [], []
        self.error, self.seq = [], []
        self.phase_abbrev, self.unclear = {}, {}
        self.unit_names = {'A': 'ARMY', 'F': 'FLEET'}
        self.keywords, self.aliases = KEYWORDS.copy(), ALIASES.copy()
        self.load()
        self.build_cache()
        self.validate()
        if name not in CONVOYS_PATH_CACHE and use_cache:
            CONVOYS_PATH_CACHE[name] = add_to_cache(name)
        self.convoy_paths = CONVOYS_PATH_CACHE.get(name, {})
        if use_cache:
            MAP_CACHE[name] = self

    def __deepcopy__(self, memo):
        """ Fast deep copy implementation """
        actual_init = self.__class__.__init__
        self.__class__.__init__ = lambda *args, **kwargs: None
        instance = self.__class__(name=self.name, use_cache=False)
        self.__class__.__init__ = actual_init
        for key in self.__slots__:
            setattr(instance, key, deepcopy(getattr(self, key)))
        return instance

    def __str__(self):
        return self.name

    def validate(self, force=0):
        """ Validate that the configuration from a map file is correct
            :param force: Indicate that we want to force a validation, even if the map is already validated
            :return: Nothing
        """
        # pylint: disable=too-many-branches
        # Already validated, returning (except if forced or if validating phases)
        if not force and self.validated:
            return
        self.validated = 1

        # Root map
        self.root_map = self.root_map or self.name

        # Validating powers
        self.powers = [power_name for power_name in self.homes if power_name != 'UNOWNED']
        self.powers.sort()
        if len(self.powers) < 2:
            self.error += [err.MAP_LEAST_TWO_POWERS]

        # Validating area type
        for place in self.loc_name.values():
            if place.upper() not in self.powers and not self.area_type(place):
                self.error += [err.MAP_LOC_NOT_FOUND % place]

        # Validating adjacencies
        for place, abuts in self.loc_abut.items():
            up_abuts = [loc.upper() for loc in abuts]
            for abut in abuts:
                up_abut = abut.upper()
                if up_abuts.count(up_abut) > 1:
                    self.error += [err.MAP_SITE_ABUTS_TWICE % (place.upper(), up_abut)]
                    while up_abut in up_abuts:
                        up_abuts.remove(up_abut)

            # Checking full name
            if place.upper() not in self.loc_name.values():
                self.error += [err.MAP_NO_FULL_NAME % place]

            # Checking one-way adjacency
            for loc in abuts:
                if self.area_type(place) != 'SHUT' \
                        and self.area_type(loc) != 'SHUT' \
                        and not self.abuts('A', loc, '-', place) \
                        and not self.abuts('F', loc, '-', place):
                    self.error.append(err.MAP_ONE_WAY_ADJ % (place, loc))

        # Validating home centers
        for power_name, places in self.homes.items():
            for site in places:
                # Adding home as supply center
                if site not in self.scs:
                    self.scs += [site]
                if not self.area_type(site):
                    self.error += [err.MAP_BAD_HOME % (power_name, site)]

                # Remove home centers from unowned list.
                # It's perfectly OK for 2 powers to share a home center, as long
                # as no more than one owns it at the same time.
                if power_name != 'UNOWNED':
                    if site in self.homes['UNOWNED']:
                        self.homes['UNOWNED'].remove(site)

        # Valid supply centers
        for scs in self.centers.values():
            self.scs.extend([center for center in scs if center not in self.scs])

        # Validating initial centers and units
        for power_name, places in self.centers.items():
            for loc in places:
                if not self.area_type(loc):
                    self.error.append(err.MAP_BAD_INITIAL_OWN_CENTER % (power_name, loc))

        # Checking if power has OWN line
        for power_name in self.powers:
            if power_name not in self.owns:
                self.centers[power_name] = self.homes[power_name][:]
            for unit in self.units.get(power_name, []):
                if not self.is_valid_unit(unit):
                    self.error.append(err.MAP_BAD_INITIAL_UNITS % (power_name, unit))

        # Checking for multiple owners
        for power_name, centers in self.centers.items():
            for site in centers:
                for other, locs in self.centers.items():
                    if other == power_name and locs.count(site) != 1:
                        self.error += [err.MAP_CENTER_MULT_OWNED % site]
                    elif other != power_name and locs.count(site) != 0:
                        self.error += [err.MAP_CENTER_MULT_OWNED % site]
        if 'UNOWNED' in self.homes:
            del self.homes['UNOWNED']

        # Ensure a default game-year FLOW
        self.flow = ['SPRING:MOVEMENT,RETREATS', 'FALL:MOVEMENT,RETREATS', 'WINTER:ADJUSTMENTS']
        self.flow_sign = 1
        self.seq = ['NEWYEAR', 'SPRING MOVEMENT', 'SPRING RETREATS', 'FALL MOVEMENT', 'FALL RETREATS',
                    'WINTER ADJUSTMENTS']
        self.phase_abbrev = {'M': 'MOVEMENT', 'R': 'RETREATS', 'A': 'ADJUSTMENTS'}

        # Validating initial game phase
        self.phase = self.phase or 'SPRING 1901 MOVEMENT'
        phase = self.phase.split()
        if len(phase) != 3:
            self.error += [err.MAP_BAD_PHASE % self.phase]
        else:
            self.first_year = int(phase[1])

    def load(self, file_name=None):
        """ Loads a map file from disk
            :param file_name: Optional. A string representing the file to open. Otherwise, defaults to the map name
            :return: Nothing
        """
        # pylint: disable=too-many-nested-blocks,too-many-statements,too-many-branches
        # If file_name is string, opening file from disk
        # Otherwise file_name is the file handler
        power = 0
        if file_name is None:
            file_name = '{}.map'.format(self.name)
        file_path = os.path.join(settings.PACKAGE_DIR, 'maps', file_name)

        # Checking if file exists:
        found_map = 1 if os.path.exists(file_path) else 0
        if not found_map:
            self.error.append(err.MAP_FILE_NOT_FOUND % file_name)
            return

        # Adding to parsed files
        self.files += [file_name]

        # Parsing file
        with open(file_path, encoding='utf-8') as file:
            variant = 0

            for line in file:
                word = line.split()

                # -- # comment...
                if not word or word[0][0] == '#':
                    continue
                upword = word[0].upper()

                # ----------------------------------
                # Centers needed to obtain a VICTORY
                # -- VICTORY centerCount...
                if upword == 'VICTORY':
                    try:
                        self.victory = [int(word) for word in word[1:]]
                    except ValueError:
                        self.error += [err.MAP_BAD_VICTORY_LINE]

                # ---------------------------------
                # Inclusion of other base map files
                # -- USE[S] fileName...
                # -- MAP mapName
                elif upword in ('USE', 'USES', 'MAP'):
                    if upword == 'MAP':
                        if len(word) != 2:
                            self.error += [err.MAP_BAD_ROOT_MAP_LINE]
                        elif self.root_map:
                            self.error += [err.MAP_TWO_ROOT_MAPS]
                        else:
                            self.root_map = word[1].split('.')[0]
                    for new_file in word[1:]:
                        if '.' not in new_file:
                            new_file = '{}.map'.format(new_file)
                        if new_file not in self.files:
                            self.load(new_file)
                        else:
                            self.error += [err.MAP_FILE_MULT_USED % new_file]

                # ------------------------------------
                # Set BEGIN phase
                # -- BEGIN season year phaseType
                elif upword == 'BEGIN':
                    self.phase = ' '.join(word[1:]).upper()

                # ------------------------------------
                # RULEs specific to this map
                elif upword in ('RULE', 'RULES'):
                    if (variant or 'ALL') == 'ALL':
                        self.rules += line.upper().split()[1:]

                # ------------------------------------
                # -- [oldAbbrev ->] placeName = abbreviation alias...
                elif '=' in line:
                    token = line.upper().split('=')
                    if len(token) == 1:
                        self.error += [err.MAP_BAD_ALIASES_IN_FILE % token[0]]
                        token += ['']
                    old_name, name, word = 0, token[0].strip(), token[1].split()
                    parts = [part.strip() for part in name.split('->')]
                    if len(parts) == 2:
                        old_name, name = parts
                    elif len(parts) > 2:
                        self.error += [err.MAP_BAD_RENAME_DIRECTIVE % name]
                    if not (word[0][0] + word[0][-1]).isalnum() or word[0] != self.norm(word[0]).replace(' ', ''):
                        self.error += [err.MAP_INVALID_LOC_ABBREV % word[0]]

                    # Rename no longer supported
                    # Making sure place not already there
                    if old_name:
                        self.error += [err.MAP_RENAME_NOT_SUPPORTED]
                    if name in self.keywords:
                        self.error += [err.MAP_LOC_RESERVED_KEYWORD % name]
                        normed = name
                    else:
                        normed = self.norm(name)
                    if name in self.loc_name or normed in self.aliases:
                        self.error += [err.MAP_DUP_LOC_OR_POWER % name]
                    self.loc_name[name] = self.aliases[normed] = word[0]

                    # Ambiguous place names end with a ?
                    for alias in word[1:]:
                        unclear = alias[-1] == '?'
                        # For ambiguous place names, let's do just a minimal normalization
                        # otherwise they might become unrecognizable (e.g. "THE")
                        normed = alias[:-1].replace('+', ' ').upper() if unclear else self.norm(alias)
                        if unclear:
                            self.unclear[normed] = word[0]
                        elif normed in self.aliases:
                            if self.aliases[normed] != word[0]:
                                self.error += [err.MAP_DUP_ALIAS_OR_POWER % alias]
                        else:
                            self.aliases[normed] = word[0]

                # ------------------------------------
                # Center ownership (!= Home Ownership)
                # -- OWNS center...
                # -- CENTERS [center...]
                elif upword in ('OWNS', 'CENTERS'):
                    if not power:
                        self.error += [err.MAP_OWNS_BEFORE_POWER % (upword, ' '.join(word))]
                    else:
                        if power not in self.owns:
                            self.owns.append(power)
                        # CENTERS resets the list of centers, OWNS only appends
                        if upword[0] == 'C' or power not in self.centers:
                            self.centers[power] = line.upper().split()[1:]
                        else:
                            self.centers[power].extend(
                                [center for center in line.upper().split()[1:] if center not in self.centers[power]])

                # ------------------------------------
                # Home centers, overriding those from the power declaration line
                # -- INHABITS center...
                elif upword == 'INHABITS':
                    if not power:
                        self.error += [err.MAP_INHABITS_BEFORE_POWER % ' '.join(word)]
                    else:
                        reinit = power not in self.inhabits
                        if reinit:
                            self.inhabits.append(power)
                        self.add_homes(power, word[1:], reinit)

                # -- HOME(S) [center...]
                elif upword in ('HOME', 'HOMES'):
                    if not power:
                        self.error += [err.MAP_HOME_BEFORE_POWER % (upword, ' '.join(word))]
                    else:
                        if power not in self.inhabits:
                            self.inhabits.append(power)
                        self.add_homes(power, word[1:], 1)

                # ------------------------------------
                # Clear known units for a power
                # -- UNITS
                elif upword == 'UNITS':
                    if power:
                        self.units[power] = []
                    else:
                        self.error += [err.MAP_UNITS_BEFORE_POWER]

                # ------------------------------------
                # Unit Designation (A or F)
                # -- unit location
                elif upword in ('A', 'F'):
                    unit = ' '.join(word).upper()
                    if not power:
                        self.error += [err.MAP_UNIT_BEFORE_POWER]
                    elif len(word) == 2:
                        for units in self.units.values():
                            for current_unit in units:
                                if current_unit[2:5] == unit[2:5]:
                                    units.remove(current_unit)
                        self.units.setdefault(power, []).append(unit)
                    else:
                        self.error += [err.MAP_INVALID_UNIT % unit]

                # ------------------------------------
                # Dummies
                # -- DUMMY [ALL] -or-
                # -- DUMMY [ALL EXCEPT] powerName... -or-
                # -- DUMMIES ALL -or-
                # -- DUMMIES [ALL EXCEPT] powerName...
                elif upword in ('DUMMY', 'DUMMIES'):
                    if len(word) > 1:
                        power = None
                    # DUMMY
                    if len(word) == 1:
                        if upword == 'DUMMIES':
                            self.error += [err.MAP_DUMMY_REQ_LIST_POWERS]
                        elif not power:
                            self.error += [err.MAP_DUMMY_BEFORE_POWER]
                        elif power not in self.dummies:
                            self.dummies += [power]
                    # DUMMY powerName powerName
                    elif word[1].upper() != 'ALL':
                        self.dummies.extend(
                            [dummy for dummy in [self.norm_power(p_name) for p_name in word[1:]]
                             if dummy not in self.dummies])
                    # DUMMY ALL
                    elif len(word) == 2:
                        self.dummies = [power_name for power_name in self.homes if power_name != 'UNOWNED']
                    # DUMMY ALL powerName
                    elif word[2].upper() != 'EXCEPT':
                        self.error += [err.MAP_NO_EXCEPT_AFTER_DUMMY_ALL % upword]
                    # DUMMY ALL EXCEPT
                    elif len(word) == 3:
                        self.error += [err.MAP_NO_POWER_AFTER_DUMMY_ALL_EXCEPT % upword]
                    # DUMMY ALL EXCEPT powerName powerName
                    else:
                        self.dummies = [power_name for power_name in self.homes if power_name not in
                                        (['UNOWNED'] + [self.norm_power(except_pow) for except_pow in word[3:]])]

                # ------------------------------------
                # -- DROP abbreviation...
                elif upword == 'DROP':
                    for place in [loc.upper() for loc in word[1:]]:
                        self.drop(place)

                # ------------------------------------
                # Terrain type and adjacencies (with special adjacency rules)
                # -- COAST abbreviation [ABUTS [abut...]] -or-
                # -- LAND  abbreviation [ABUTS [abut...]] -or-
                # -- WATER abbreviation [ABUTS [abut...]] -or-
                # -- PORT  abbreviation [ABUTS [abut...]] -or-
                # -- SHUT  abbreviation [ABUTS [abut...]] -or-
                # -- AMEND abbreviation [ABUTS [abut...]]
                # --    - removes an abut
                elif len(word) > 1 and upword in ('AMEND', 'WATER', 'LAND', 'COAST', 'PORT', 'SHUT'):
                    place, other = word[1], word[1].swapcase()

                    # Removing the place and all its coasts
                    if other in self.locs:
                        self.locs.remove(other)
                        if upword == 'AMEND':
                            self.loc_type[place] = self.loc_type[other]
                            self.loc_abut[place] = self.loc_abut[other]
                        del self.loc_type[other]
                        del self.loc_abut[other]
                        if place.isupper():
                            for loc in self.locs:
                                if loc.startswith(place):
                                    self.drop(loc)
                    if place in self.locs:
                        self.locs.remove(place)

                    # Re-adding the place and its type
                    self.locs += [place]
                    if upword != 'AMEND':
                        self.loc_type[place] = word[0]
                        if len(word) > 2:
                            self.loc_abut[place] = []
                    elif place not in self.loc_type:
                        self.error += [err.MAP_NO_DATA_TO_AMEND_FOR % place]
                    if len(word) > 2 and word[2].upper() != 'ABUTS':
                        self.error += [err.MAP_NO_ABUTS_FOR % place]

                    # Processing ABUTS (adjacencies)
                    for dest in word[3:]:

                        # Removing abuts if they start with -
                        if dest[0] == '-':
                            for site in self.loc_abut[place][:]:
                                if site.upper().startswith(dest[1:].upper()):
                                    self.loc_abut[place].remove(site)
                            continue

                        # Now add the adjacency
                        self.loc_abut[place] += [dest]

                # ------------------------------------
                # Removal of an existing power
                # -- UNPLAYED [ALL] -or-
                # -- UNPLAYED [ALL EXCEPT] powerName...
                elif upword == 'UNPLAYED':
                    goners = []
                    # UNPLAYED powerName
                    if len(word) == 1:
                        if not power:
                            self.error += [err.MAP_UNPLAYED_BEFORE_POWER]
                        else:
                            goners = [power]
                    # UNPLAYED powerName powerName
                    elif word[1].upper() != 'ALL':
                        goners = [self.norm_power(power_name) for power_name in word[1:]]
                    # UNPLAYED ALL
                    elif len(word) == 2:
                        goners = [power_name for power_name in self.homes if power_name != 'UNOWNED']
                    # UNPLAYED ALL playerName
                    elif word[2].upper() != 'EXCEPT':
                        self.error += [err.MAP_NO_EXCEPT_AFTER_UNPLAYED_ALL]
                    # UNPLAYED ALL EXCEPT
                    elif len(word) == 3:
                        self.error += [err.MAP_NO_POWER_AFTER_UNPLAYED_ALL_EXCEPT]
                    # UNPLAYED ALL EXCEPT powerName
                    else:
                        goners = [power_name for power_name in self.homes if power_name not in
                                  (['UNOWNED'] + [self.norm_power(pow_except) for pow_except in word[3:]])]

                    # Removing each power
                    for goner in goners:
                        try:
                            del self.pow_name[goner]
                            del self.own_word[goner]
                            del self.homes[goner]
                            self.dummies = [x for x in self.dummies if x != goner]
                            self.inhabits = [x for x in self.inhabits if x != goner]
                            if goner in self.centers:
                                del self.centers[goner]
                            self.owns = [x for x in self.owns if x != goner]
                            if goner in self.abbrev:
                                del self.abbrev[goner]
                            if goner in self.units:
                                del self.units[goner]
                            self.powers = [x for x in self.powers if x != goner]
                        except KeyError:
                            self.error += [err.MAP_NO_SUCH_POWER_TO_REMOVE % goner]
                    power = None

                else:
                    # ------------------------------------
                    # Power name, ownership word, and home centers
                    # -- [oldName ->] powerName [([ownWord][:[abbrev]])] [center...]
                    # -- UNOWNED [center...] -or-
                    # -- NEUTRAL [center...] -or-
                    # -- CENTERS [center...]
                    if upword in ('NEUTRAL', 'CENTERS'):
                        upword = 'UNOWNED'
                    power = self.norm_power(upword) if upword != 'UNOWNED' else 0

                    # Renaming power (Not Supported)
                    if len(word) > 2 and word[1] == '->':
                        old_power = power
                        word = word[2:]
                        upword = word[0].upper()
                        if upword in ('NEUTRAL', 'CENTERS'):
                            upword = 'UNOWNED'
                        power = self.norm_power(upword) if upword != 'UNOWNED' else 0
                        if not old_power or not power:
                            self.error += [err.MAP_RENAMING_UNOWNED_DIR_NOT_ALLOWED]
                        elif not self.pow_name.get(old_power):
                            self.error += [err.MAP_RENAMING_UNDEF_POWER % old_power]
                        else:
                            self.error += [err.MAP_RENAMING_POWER_NOT_SUPPORTED]

                    # Adding power
                    if power and not self.pow_name.get(power):
                        self.pow_name[power] = upword
                        normed = self.norm(power)
                        # Add power to aliases even if the normed form is identical. That way
                        # it becomes part of the vocabulary.
                        if not normed:
                            self.error += [err.MAP_POWER_NAME_EMPTY_KEYWORD % power]
                            normed = power
                        if normed not in self.aliases:
                            if len(normed.split('/')[0]) in (1, 3):
                                self.error += [err.MAP_POWER_NAME_CAN_BE_CONFUSED % normed]
                            self.aliases[normed] = power
                        elif self.aliases[normed] != power:
                            self.error += [err.MAP_DUP_LOC_OR_POWER % normed]

                    # Processing own word and abbreviations
                    upword = power or upword
                    if power and len(word) > 1 and word[1][0] == '(':
                        self.own_word[upword] = word[1][1:-1] or power
                        normed = self.norm(self.own_word[upword])
                        if normed == power:
                            pass
                        elif normed not in self.aliases:
                            self.aliases[normed] = power
                        elif self.aliases[normed] != power:
                            self.error += [err.MAP_DUP_LOC_OR_POWER % normed]
                        if ':' in word[1]:
                            owner, abbrev = self.own_word[upword].split(':')
                            self.own_word[upword] = owner or power
                            self.abbrev[upword] = abbrev[:1].upper()
                            if not abbrev or self.abbrev[upword] in 'M?':
                                self.error += [err.MAP_ILLEGAL_POWER_ABBREV]
                        del word[1]
                    else:
                        self.own_word.setdefault(upword, upword)

                    # Adding homes
                    reinit = upword in self.inhabits
                    if reinit:
                        self.inhabits.remove(upword)
                    self.add_homes(upword, word[1:], reinit)

    def build_cache(self):
        """ Builds a cache to speed up abuts and coasts lookup """
        # Adding all coasts to loc_coasts
        for loc in self.locs:
            self.loc_coasts[loc.upper()] = \
                [map_loc.upper() for map_loc in self.locs if loc.upper()[:3] == map_loc.upper()[:3]]

        # Building abuts cache
        for unit_type in ['A', 'F']:
            for unit_loc in self.locs:
                for other_loc in self.locs:
                    for order_type in ['-', 'S', 'C']:

                        # Calculating and setting in cache
                        unit_loc, other_loc = unit_loc.upper(), other_loc.upper()
                        query_tuple = (unit_type, unit_loc, order_type, other_loc)
                        self.abuts_cache[query_tuple] = self._abuts(*query_tuple)

    def add_homes(self, power, homes, reinit):
        """ Add new homes (and deletes previous homes if reinit)
            :param power: Name of power (e.g. ITALY)
            :param homes: List of homes e.g. ['BUR', '-POR', '*ITA', ... ]
            :param reinit: Indicates that we want to strip the list of homes before adding
            :return: Nothing
        """
        # Reset homes
        if reinit:
            self.homes[power] = []
        else:
            self.homes.setdefault(power, [])
        self.homes.setdefault('UNOWNED', [])

        # For each home:
        # '-' indicates we want to remove home
        for home in ' '.join(homes).upper().split():
            remove = 0
            while home:
                if home[0] == '-':
                    remove = 1
                else:
                    break
                home = home[1:]
            if not home:
                continue

            # Removing the home if already there
            if home in self.homes[power]:
                self.homes[power].remove(home)
            if power != 'UNOWNED':
                self.homes['UNOWNED'].append(home)

            # Re-adding it
            if not remove:
                self.homes[power].append(home)

    def drop(self, place):
        """ Drop a place
            :param place: Name of place to remove
            :return: Nothing
        """
        # Removing from locs
        for loc in list(self.locs):
            if loc.upper().startswith(place):
                self.locs.remove(loc)

        # Loc_name
        for full_name, loc in list(self.loc_name.items()):
            if loc.startswith(place):
                self.loc_name.pop(full_name)

        # Aliases
        for alias, loc in list(self.aliases.items()):
            if loc.startswith(place):
                self.aliases.pop(alias)

        # Homes
        for power_name, power_homes in list(self.homes.items()):
            if place in power_homes:
                self.homes[power_name].remove(place)

        # Units
        for power_name, power_units in list(self.units.items()):
            for unit in power_units:
                if unit[2:5] == place[:3]:
                    self.units[power_name].remove(unit)

        # Supply Centers
        for center in list(self.scs):
            if center.upper().startswith(place):
                self.scs.remove(center)

        # Centers ownerships
        for power_name, power_centers in list(self.centers.items()):
            for center in power_centers:
                if center.startswith(place):
                    self.centers[power_name].remove(center)

        # Removing from adjacencies list
        for site_name, site_abuts in list(self.loc_abut.items()):
            for site in [loc for loc in site_abuts if loc.upper().startswith(place)]:
                self.loc_abut[site_name].remove(site)
            if site_name.startswith(place):
                self.loc_abut.pop(site_name)

        # Removing loc_type
        for loc in list(self.loc_type):
            if loc.startswith(place):
                self.loc_type.pop(loc)

    def norm_power(self, power):
        """ Normalise the name of a power (removes spaces)
            :param power: Name of power to normalise
            :return: Normalised power name
        """
        return self.norm(power).replace(' ', '')

    def norm(self, phrase):
        """ Normalise a sentence (add spaces before /, replace -+, with ' ', remove .:
            :param phrase: Phrase to normalise
            :return: Normalised sentences
        """
        phrase = phrase.upper().replace('/', ' /').replace(' / ', '')
        for token in '.:':
            phrase = phrase.replace(token, '')
        for token in '-+,':
            phrase = phrase.replace(token, ' ')
        for token in '|*?!~()[]=_^':
            phrase = phrase.replace(token, ' {} '.format(token))

        # Replace keywords which, contrary to aliases, all consist of a single word
        return ' '.join([self.keywords.get(keyword, keyword) for keyword in phrase.strip().split()])

    def compact(self, phrase):
        """ Compacts a full sentence into a list of short words
            :param phrase: The full sentence to compact (e.g. 'England: Fleet Western Mediterranean -> Tyrrhenian
                           Sea. (*bounce*)')
            :return: The compacted phrase in an array (e.g. ['ENGLAND', 'F', 'WES', 'TYS', '|'])
        """
        word, result = self.norm(phrase).split(), []
        while word:
            alias, i = self.alias(word)
            if alias:
                result += alias.split()
            word = word[i:]
        return result

    def alias(self, word):
        """ This function is used to replace multi-words with their acronyms
            :param word: The current list of words to try to shorten
            :return: alias, ix - alias is the shorten list of word, ix is the ix of the next non-processed word
        """
        # pylint: disable=too-many-return-statements
        # Assume that word already was subject to norm()
        # Process with content inside square or round brackets
        j = -1
        alias = word[0]
        if alias in '([':
            for j in range(1, len(word)):
                if word[j] == '])'[alias == '(']:
                    break
            else:
                return alias, 1
            if j == 1:
                return '', 2
            if word[1] + word[j - 1] == '**':
                word2 = word[2:j - 1]
            else:
                word2 = word[1:j]
                alias2 = self.aliases.get(' '.join(word2) + ' \\', '')
                if alias2[-2:] == ' \\':
                    return alias2[:-2], j + 1
            result = []
            while word2:
                alias2, i = self.alias(word2)
                if alias2:
                    result += [alias2]
                word2 = word2[i:]
            return ' '.join(result), j + 1
        for i in range(len(word), 0, -1):
            key = ' '.join(word[:i])
            if key in self.aliases:
                alias = self.aliases[key]
                break
        else:
            i = 1

        # Concatenate coasts
        if i == len(word):
            return alias, i
        if alias[:1] != '/' and ' ' not in alias:
            alias2, j = self.alias(word[i:])
            if alias2[:1] != '/' or ' ' in alias2:
                return alias, i
        elif alias[-2:] == ' \\':
            alias2, j = self.alias(word[i:])
            if alias2[:1] == '/' or ' ' in alias2:
                return alias, i
            alias, alias2 = alias2, alias[:-2]
        else:
            return alias, i

        # Check if the location is also an ambiguous power name
        # and replace with its other name if that's the case
        if alias in self.powers and alias in self.unclear:
            alias = self.unclear[alias]

        # Check if the coast is mapped to another coast
        if alias + ' ' + alias2 in self.aliases:
            return self.aliases[alias + ' ' + alias2], i + j
        return alias + alias2, i + j

    def vet(self, word, strict=0):
        """ Determines the type of every word in a compacted order phrase
            0 - Undetermined, 1 - Power, 2 - Unit, 3 - Location, 4 - Coastal location
            5 - Order, 6 - Move Operator (-=_^), 7 - Non-move separator (|?~) or result (*!?~+)
            :param word: The list of words to vet (e.g. ['A', 'POR', 'S', 'SPA/NC'])
            :param strict: Boolean to indicate that we want to verify that the words actually exist.
                           Numbers become negative if they don't exist
            :return: A list of tuple (e.g. [('A', 2), ('POR', 3), ('S', 5), ('SPA/NC', 4)])
        """
        result = []
        for thing in word:
            if ' ' in thing:
                data_type = UNDETERMINED
            elif len(thing) == 1:
                if thing in self.unit_names:
                    data_type = UNIT
                elif thing.isalnum():
                    data_type = ORDER
                elif thing in '-=_':
                    data_type = MOVE_SEP
                else:
                    data_type = OTHER
            elif '/' in thing:
                if thing.find('/') == 3:
                    data_type = COAST
                else:
                    data_type = POWER
            elif thing == 'VIA':
                data_type = ORDER
            elif len(thing) == 3:
                data_type = LOCATION
            else:
                data_type = POWER
            if strict and thing not in list(self.aliases.values()) + list(self.keywords.values()):
                data_type = -data_type
            result += [(thing, data_type)]
        return result

    def rearrange(self, word):
        """ This function is used to parse commands
            :param word: The list of words to vet (e.g. ['ENGLAND', 'F', 'WES', 'TYS', '|'])
            :return: The list of words in the correct order to be processed (e.g. ['ENGLAND', 'F', 'WES', '-', 'TYS'])
        """
        # pylint: disable=too-many-branches
        # Add | to start and end of list (to simplify edge cases) (they will be returned as ('|', 7))
        # e.g. [('|', 7), ('A', 2), ('POR', 3), ('S', 5), ('SPA/NC', 4), ('|', 7)]
        result = self.vet(['|'] + word + ['|'])

        # Remove result tokens (7) at start and end of string (but keep |)
        result[0] = ('|', UNDETERMINED)
        while result[-2][1] == OTHER:
            del result[-2]
        if len(result) == 2:
            return []
        result[0] = ('|', OTHER)
        while result[1][1] == OTHER:
            del result[1]

        # Move "with" unit and location to the start. There should be only one
        # Ignore the rest
        found = 0
        while ('?', OTHER) in result:
            i = result.index(('?', OTHER))
            del result[i]
            if found:
                continue
            j = -1
            for j in range(i, len(result)):
                if result[j][1] in (POWER, UNIT):
                    continue
                if result[j][1] in (LOCATION, COAST):
                    j += 1
                break
            if j != i:
                found = 1
                k = 0
                for k in range(1, i):
                    if result[k][1] not in (POWER, UNIT):
                        break
                if k < i:
                    result[k:k] = result[i:j]
                    result[j:2 * j - i] = []

        # Move "from" location before any preceding locations
        while ('\\', OTHER) in result:
            i = result.index(('\\', OTHER))
            del result[i]
            if result[i][1] not in (LOCATION, COAST):
                continue
            for j in range(i - 1, -1, -1):
                if result[j][1] not in (LOCATION, COAST) and result[j][0] != '~':
                    break
            if j + 1 != i:
                result[j + 1:j + 1] = result[i:i + 1]
                del result[i + 1]

        # Move "via" locations between the two preceding locations.
        while ('~', OTHER) in result:
            i = result.index(('~', OTHER))
            del result[i]
            if (result[i][1] not in (LOCATION, COAST)
                    or result[i - 1][1] not in (LOCATION, COAST)
                    or result[i - 2][1] not in (LOCATION, COAST)):
                continue
            for j in range(i + 1, len(result)):
                if result[j][1] not in (LOCATION, COAST):
                    break
            result[j:j] = result[i - 1:i]
            del result[i - 1]

        # Move order beyond first location
        i = 0
        for j in range(1, len(result)):
            if result[j][1] in (LOCATION, COAST):
                if i:
                    result[j + 1:j + 1] = result[i:i + 1]
                    del result[i]
                break
            elif result[j][1] == ORDER:
                i = j
            elif result[j][0] == '|':
                break

        # Put the power before the unit, or replace it with a location if there's ambiguity
        vet = 0
        for i, result_i in enumerate(result):
            if result_i[1] == POWER:
                if vet > 0 and result_i[0] in self.unclear:
                    result[i] = (self.unclear[result_i[0]], LOCATION)
                elif vet == 1:
                    result[i + 1:i + 1] = result[i - 1:i]
                    del result[i - 1]
                vet = 2
            elif not vet and result_i[1] == UNIT:
                vet = 1
            elif result_i[1] == ORDER:
                vet = 0
            else:
                vet = 2

        # Insert hyphens between subsequent locations
        for i in range(len(result) - 1, 1, -1):
            if result[i][1] in (LOCATION, COAST) and result[i - 1][1] in (LOCATION, COAST):
                result[i:i] = [('-', MOVE_SEP)]

        # Remove vertical bars at start and end
        return [x for x, y in result[1:-1]]

    def area_type(self, loc):
        """ Returns 'WATER', 'COAST', 'PORT', 'LAND', 'SHUT'
            :param loc: The name of the location to query
            :return: Type of the location ('WATER', 'COAST', 'PORT', 'LAND', 'SHUT')
        """
        return self.loc_type.get(loc.upper()) or self.loc_type.get(loc.lower())

    def default_coast(self, word):
        """ Returns the coast for a fleet move order that can only be to a single coast
            (e.g. F GRE-BUL returns F GRE-BUL/SC)
            :param word: A list of tokens (e.g. ['F', 'GRE', '-', 'BUL'])
            :return: The updated list of tokens (e.g. ['F', 'GRE', '-', 'BUL/SC'])
        """
        if len(word) == 4 and word[0] == 'F' and word[2] == '-' and '/' not in word[3]:
            unit_loc, new_loc, single_coast = word[1], word[3], None
            for place in self.abut_list(unit_loc):
                up_place = place.upper()
                if new_loc == up_place:                 # Target location found with no coast, original query is correct
                    return word
                if new_loc == up_place[:3]:
                    if single_coast:                    # Target location has multiple coasts, unable to decide
                        return word
                    single_coast = up_place             # Found a potential candidate, storing it
            word[3] = single_coast or new_loc           # Only one candidate found, modifying the order to include it
        return word

    def find_coasts(self, loc):
        """ Finds all coasts for a given location
            :param loc: The name of a location (e.g. 'BUL')
            :return: Returns the list of all coasts, including the location (e.g. ['BUL', 'BUL/EC', 'BUL/SC']
        """
        return self.loc_coasts.get(loc.upper(), [])

    def abuts(self, unit_type, unit_loc, order_type, other_loc):
        """ Determines if a order for unit_type from unit_loc to other_loc is adjacent
            Note: This method uses the precomputed cache

            :param unit_type: The type of unit ('A' or 'F')
            :param unit_loc: The location of the unit ('BUR', 'BUL/EC')
            :param order_type: The type of order ('S' for Support, 'C' for Convoy', '-' for move)
            :param other_loc: The location of the other unit
            :return: 1 if the locations are adjacent for the move, 0 otherwise
        """
        if unit_type == '?':
            return (self.abuts_cache.get(('A', unit_loc.upper(), order_type, other_loc.upper()), 0) or
                    self.abuts_cache.get(('F', unit_loc.upper(), order_type, other_loc.upper()), 0))

        query_tuple = (unit_type, unit_loc.upper(), order_type, other_loc.upper())
        return self.abuts_cache.get(query_tuple, 0)

    def _abuts(self, unit_type, unit_loc, order_type, other_loc):
        """ Determines if a order for unit_type from unit_loc to other_loc is adjacent
            Note: This method is used to generate the abuts_cache

            :param unit_type: The type of unit ('A' or 'F')
            :param unit_loc: The location of the unit ('BUR', 'BUL/EC')
            :param order_type: The type of order ('S' for Support, 'C' for Convoy', '-' for move)
            :param other_loc: The location of the other unit
            :return: 1 if the locations are adjacent for the move, 0 otherwise
        """
        # pylint: disable=too-many-return-statements
        unit_loc, other_loc = unit_loc.upper(), other_loc.upper()

        # Removing coasts for support
        # Otherwise, if army, not adjacent since army can't move, hold, or convoy on coasts
        if '/' in other_loc:
            if order_type == 'S':
                other_loc = other_loc[:3]
            elif unit_type == 'A':
                return 0

        # Looking for adjacency between unit_loc and other_loc
        # If the break line is not executed, not adjacency were found
        place = ''
        for place in self.abut_list(unit_loc):
            up_place = place.upper()
            up_loc = up_place[:3]
            if other_loc in (up_place, up_loc):
                break
        else:
            return 0

        # If the target location is impassible, returning 0
        other_loc_type = self.area_type(other_loc)
        if other_loc_type == 'SHUT':
            return 0

        # If the unit type is unknown, then assume the adjacency is okay
        if unit_type == '?':
            return 1

        # Fleets cannot affect LAND and fleets are not adjacent to any location listed in lowercase
        # (except when offering support into such an area, as in F BOT S A MOS-STP), or listed in
        # the adjacency list in lower-case (F VEN-TUS)

        # Fleet should be supporting a adjacent 'COAST', 'WATER' or 'PORT', with a name starting with a capital letter
        if unit_type == 'F':
            if (other_loc_type == 'LAND'
                    or place[0] != up_loc[0]
                    or order_type != 'S'
                    and other_loc not in self.loc_type):
                return 0

        # Armies cannot move to water (unless this is a convoy). Note that the caller
        # is responsible for determining if a fleet exists at the adjacent spot to convoy
        # the army. Also, armies can't move to spaces listed in Mixed case.
        elif order_type != 'C' and (other_loc_type == 'WATER' or place == place.title()):
            return 0

        # It's adjacent.
        return 1

    def is_valid_unit(self, unit, no_coast_ok=0, shut_ok=0):
        """ Determines if a unit and location combination is valid (e.g. 'A BUR') is valid
            :param unit: The name of the unit with its location (e.g. F SPA/SC)
            :param no_coast_ok: Indicates if a coastal location with no coast (e.g. SPA vs SPA/SC) is acceptable
            :param shut_ok: Indicates if a impassable country (e.g. Switzerland) is OK
            :return: A boolean to indicate if the unit/location combination is valid
        """
        unit_type, loc = unit.upper().split()
        area_type = self.area_type(loc)
        if area_type == 'SHUT':
            return 1 if shut_ok else 0
        if unit_type == '?':
            return 1 if area_type is not None else 0
        # Army can be anywhere, except in 'WATER'
        if unit_type == 'A':
            return '/' not in loc and area_type in ('LAND', 'COAST', 'PORT')
        # Fleet must be in WATER, COAST, or PORT
        # Coastal locations are stored in CAPS with coasts and non-caps with non-coasts
        # e.g. SPA/NC, SPA/SC, spa
        return (unit_type == 'F'
                and area_type in ('WATER', 'COAST', 'PORT')
                and (no_coast_ok or loc.lower() not in self.loc_abut))

    def abut_list(self, site, incl_no_coast=False):
        """ Returns the adjacency list for the site
            :param site: The province we want the adjacency list for
            :param incl_no_coast: Boolean flag that indicates to also include province without coast if it has coasts
                                 e.g. will return ['BUL/SC', 'BUL/EC'] if False, and ['bul', 'BUL/SC', 'BUL/EC'] if True
            :return: A list of adjacent provinces

            Note: abuts are returned in mixed cases (lowercase for A only, First capital letter for F only)
        """
        if site in self.loc_abut:
            abut_list = self.loc_abut.get(site, [])
        else:
            abut_list = self.loc_abut.get(site.lower(), [])
        if incl_no_coast:
            abut_list = abut_list[:]
            for loc in list(abut_list):
                if '/' in loc and loc[:3] not in abut_list:
                    abut_list += [loc[:3]]
        return abut_list

    def find_next_phase(self, phase, phase_type=None, skip=0):
        """ Returns the long name of the phase coming immediately after the phase
            :param phase: The long name of the current phase (e.g. SPRING 1905 RETREATS)
            :param phase_type: The type of phase we are looking for (e.g. 'M' for Movement, 'R' for Retreats,
                               'A' for Adjust.)
            :param skip: The number of match to skip (e.g. 1 to find not the next phase, but the one after)
            :return: The long name of the next phase (e.g. FALL 1905 MOVEMENT)
        """
        # If len < 3, Phase is FORMING or COMPLETED, unable to find previous phase
        now = phase.split()
        if len(now) < 3:
            return phase

        # Parsing year and season index
        year = int(now[1])
        season_ix = (self.seq.index('%s %s' % (now[0], now[2])) + 1) % len(self.seq)
        seq_len = len(self.seq)

        # Parsing the sequence of seasons
        while seq_len:
            seq_len -= 1
            new = self.seq[season_ix].split()

            # Looking for IFYEARDIV DIV or IFYEARDIV DIV=MOD
            if new[0] == 'IFYEARDIV':
                if '=' in new[1]:
                    div, mod = map(int, new[1].split('='))
                else:
                    div, mod = int(new[1]), 0
                if year % div != mod:
                    season_ix = -1

            # NEWYEAR [X] indicates to increase years by [X] (or 1 by default)
            elif new[0] == 'NEWYEAR':
                year += len(new) == 1 or int(new[1])

            # Found phase
            elif phase_type in (None, new[1][0]):
                if skip == 0:
                    return '%s %s %s' % (new[0], year, new[1])
                skip -= 1
                seq_len = len(self.seq)
            season_ix += 1
            season_ix %= len(self.seq)

        # Could not find next phase
        return ''

    def find_previous_phase(self, phase, phase_type=None, skip=0):
        """ Returns the long name of the phase coming immediately prior the phase
            :param phase: The long name of the current phase (e.g. SPRING 1905 RETREATS)
            :param phase_type: The type of phase we are looking for (e.g. 'M' for Movement, 'R' for Retreats,
                               'A' for Adjust.)
            :param skip: The number of match to skip (e.g. 1 to find not the next phase, but the one after)
            :return: The long name of the previous phase (e.g. SPRING 1905 MOVEMENT)
        """
        # If len < 3, Phase is FORMING or COMPLETED, unable to find previous phase
        now = phase.split()
        if len(now) < 3:
            return phase

        # Parsing year and season index
        year = int(now[1])
        season_ix = self.seq.index('%s %s' % (now[0], now[2]))
        seq_len = len(self.seq)

        # Parsing the sequence of seasons
        while seq_len:
            seq_len -= 1
            season_ix -= 1

            # No more seasons in seq
            if season_ix == -1:
                for new in [x.split() for x in self.seq]:
                    # Looking for IFYEARDIV DIV or IFYEARDIV DIV=MOD
                    if new[0] == 'IFYEARDIV':
                        if '=' in new[1]:
                            div, mod = map(int, new[1].split('='))
                        else:
                            div, mod = int(new[1]), 0
                        if year % div != mod:
                            break
                    season_ix += 1

            # Parsing next seq
            new = self.seq[season_ix].split()
            if new[0] == 'IFYEARDIV':
                pass

            # NEWYEAR [X] indicates to increase years by [X] (or 1 by default)
            elif new[0] == 'NEWYEAR':
                year -= len(new) == 1 or int(new[1])

            # Found phase
            elif phase_type in (None, new[1][0]):
                if skip == 0:
                    return '%s %s %s' % (new[0], year, new[1])
                skip -= 1
                seq_len = len(self.seq)

        # Could not find prev phase
        return ''

    def compare_phases(self, phase1, phase2):
        """ Compare 2 phases (Strings) and return 1, -1, or 0 to indicate which phase is larger
            :param phase1:  The first phase (e.g. S1901M, FORMING, COMPLETED)
            :param phase2:  The second phase (e.g. S1901M, FORMING, COMPLETED)
            :return: 1 if phase1 > phase2, -1 if phase2 > phase1 otherwise 0 if they are equal
        """
        # If the phase ends with '?', we assume it's the last phase type of that season
        # e.g. S1901? -> S1901R  W1901? -> W1901A
        if phase1[-1] == '?':
            phase1 = phase1[:-1] + [season.split()[1][0] for season in self.seq if season[0] == phase1[0]][-1]
        if phase2[-1] == '?':
            phase2 = phase2[:-1] + [season.split()[1][0] for season in self.seq if season[0] == phase2[0]][-1]

        # Converting S1901M (abbrv) to long phase (SPRING 1901 MOVEMENT)
        if len(phase1.split()) == 1:
            phase1 = self.phase_long(phase1, phase1.upper())
        if len(phase2.split()) == 1:
            phase2 = self.phase_long(phase2, phase2.upper())
        if phase1 == phase2:
            return 0
        now1, now2 = phase1.split(), phase2.split()

        # One of the phase is either FORMING, or COMPLETED
        # Syntax is (bool1 and int1 or bool2 and int2) will return int1 if bool1, else int2 if bool2
        # 1 = FORMING, 2 = Normal Phase, 3 = COMPLETED, 0 = UNKNOWN
        if len(now1) < 3 or len(now2) < 3:
            order1 = (len(now1) > 2 and 2 or phase1 == 'FORMING' and 1 or phase1 == 'COMPLETED' and 3 or 0)
            order2 = (len(now2) > 2 and 2 or phase2 == 'FORMING' and 1 or phase2 == 'COMPLETED' and 3 or 0)
            return order1 > order2 and 1 or order1 < order2 and -1 or 0

        # Comparing years
        year1, year2 = int(now1[1]), int(now2[1])
        if year1 != year2:
            return (year1 > year2 and 1 or -1) * (self.flow_sign or 1)

        # Comparing seasons
        # Returning the inverse if NEW_YEAR is between the 2 seasons
        season_ix1 = self.seq.index('%s %s' % (now1[0], now1[2]))
        season_ix2 = self.seq.index('%s %s' % (now2[0], now2[2]))
        if season_ix1 > season_ix2:
            return -1 if 'NEWYEAR' in [x.split()[0] for x in self.seq[(season_ix2) + (1):season_ix1]] else 1
        if season_ix1 < season_ix2:
            return 1 if 'NEWYEAR' in [x.split()[0] for x in self.seq[(season_ix1) + (1):season_ix2]] else -1
        return 0

    @staticmethod
    def phase_abbr(phase, default='?????'):
        """ Constructs a 5 character representation (S1901M) from a phase (SPRING 1901 MOVEMENT)
            :param phase: The full phase (e.g. SPRING 1901 MOVEMENT)
            :param default: The default value to return in case conversion fails
            :return: A 5 character representation of the phase
        """
        if phase in ('FORMING', 'COMPLETED'):
            return phase
        parts = tuple(phase.split())
        return ('%.1s%04d%.1s' % (parts[0], int(parts[1]), parts[2])).upper() if len(parts) == 3 else default

    def phase_long(self, phase_abbr, default='?????'):
        """ Constructs a full sentence of a phase from a 5 character abbreviation
            :param phase_abbr: 5 character abbrev. (e.g. S1901M)
            :param default: The default value to return in case conversion fails
            :return: A full phase description (e.g. SPRING 1901 MOVEMENT)
        """
        try:
            year = int(phase_abbr[1:-1])
            for season in self.seq:
                parts = season.split()
                if parts[0] not in ('NEWYEAR', 'IFYEARDIV') \
                        and parts[0][0].upper() == phase_abbr[0].upper() \
                        and parts[1][0].upper() == phase_abbr[-1].upper():
                    return '{} {} {}'.format(parts[0], year, parts[1]).upper()
        except ValueError:
            pass
        return default

# Loading at the bottom, to avoid load recursion
from diplomacy.utils.convoy_paths import add_to_cache, get_convoy_paths_cache   # pylint: disable=wrong-import-position
CONVOYS_PATH_CACHE = get_convoy_paths_cache()