1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

// This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of
// the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/

//! This module define surface history functionality.

// TODO: Add unit tests.

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

// TODO: Check what is better: VecDeque or LinkedList.
use std::collections::VecDeque as Ordering;

use qualia::SurfaceId;

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

mod magic {
    pub const AVARAGE_NUM_SURFACES: usize = 10;
    pub const PEEK_TO_AVARAGE_RATIO: usize = 3;
    pub const OPTIMAL_TO_AVARAGE_RATIO: usize = 2;
}

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

/// Provides functionality to manage surface history as resizable list.
pub struct SurfaceHistory {
    history: Ordering<SurfaceId>,
}

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

impl SurfaceHistory {
    /// `SurfaceHistory` constructor.
    pub fn new() -> Self {
        SurfaceHistory { history: Ordering::with_capacity(magic::AVARAGE_NUM_SURFACES) }
    }

    /// Add surface as the latest in history.
    pub fn add(&mut self, sid: SurfaceId) {
        self.history.push_front(sid);
    }

    /// Return `n`th element from begin. If `n` is negative, return `n`th element from end.
    pub fn get_nth(&self, n: isize) -> Option<SurfaceId> {
        if n < 0 {
            let m = -n as usize;
            self.history.get(self.history.len() - m).cloned()
        } else {
            self.history.get(n as usize).cloned()
        }
    }

    /// Make given surface the latest in history.
    pub fn pop(&mut self, sid: SurfaceId) {
        self.simple_remove(sid);
        self.add(sid);
    }

    /// Remove surface. Shrink underlying memory pool if needed.
    pub fn remove(&mut self, sid: SurfaceId) {
        self.simple_remove(sid);

        let len = self.history.len();
        let capacity = self.history.capacity();
        if (len > magic::AVARAGE_NUM_SURFACES) &&
           ((magic::PEEK_TO_AVARAGE_RATIO * len) > capacity) {
            self.history.truncate(magic::OPTIMAL_TO_AVARAGE_RATIO * len);
        }
    }

    /// Remove surface without shrinking memory pool.
    fn simple_remove(&mut self, sid: SurfaceId) {
        let len = self.history.len();
        for i in 0..len {
            if *self.history.get(i).unwrap() == sid {
                self.history.remove(i);
                break;
            }
        }
    }

    /// Return iterator for `SurfaceHistory`.
    pub fn iter(&self) -> Iter {
        Iter::new(self)
    }
}

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

pub struct Iter<'a> {
    history: &'a SurfaceHistory,
    pos: isize,
}

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

impl<'a> Iter<'a> {
    /// `Iter` constructor.
    fn new(history: &'a SurfaceHistory) -> Self {
        Iter {
            history: history,
            pos: -1,
        }
    }
}

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

impl<'a> Iterator for Iter<'a> {
    type Item = SurfaceId;

    fn next(&mut self) -> Option<SurfaceId> {
        self.pos += 1;
        self.history.get_nth(self.pos)
    }
}

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