balanced_ternary/
lib.rs

1//! A [balanced ternary](https://en.wikipedia.org/wiki/Balanced_ternary) data structure.
2//!
3//! A `Ternary` object in this module represents a number in the balanced ternary numeral system.
4//! Balanced ternary is a non-standard positional numeral system that uses three digits: {-1, 0, +1}
5//! represented here as `Neg` for -1, `Zero` for 0, and `Pos` for +1. It is useful in some domains
6//! of computer science and mathematics due to its arithmetic properties and representation
7//! symmetry.
8//!
9//! # Data Structures
10//!
11//! - **`Digit` Enum**:
12//!     Represents a single digit for balanced ternary values, with possible values:
13//!     - `Neg` for -1
14//!     - `Zero` for 0
15//!     - `Pos` for +1
16//!
17//! - **`Ternary` Struct**:
18//!     Represents a balanced ternary number as a collection of `Digit`s.
19//!     Provides utility functions for conversion, parsing, and manipulation.
20//!
21//! # Examples
22//!
23//! ## Converting between representations:
24//! ```rust
25//! use balanced_ternary::*;
26//!
27//! let ternary = Ternary::from_dec(5);
28//! assert_eq!(ternary.to_string(), "+--");
29//! assert_eq!(ternary.to_dec(), 5);
30//!
31//! let parsed = Ternary::parse("+--");
32//! assert_eq!(parsed.to_string(), "+--");
33//! assert_eq!(parsed.to_dec(), 5);
34//! ```
35//!
36//! ## Negative numbers:
37//! ```rust
38//! use balanced_ternary::*;
39//!
40//! let neg_five = Ternary::from_dec(-5);
41//! assert_eq!(neg_five.to_string(), "-++");
42//! assert_eq!(neg_five.to_dec(), -5);
43//!
44//! let negated = -&neg_five;
45//! assert_eq!(negated.to_string(), "+--");
46//! assert_eq!(negated.to_dec(), 5);
47//! ```
48//!
49//! ## Larger numbers:
50//! ```rust
51//! use balanced_ternary::*;
52//!
53//! let big = Ternary::from_dec(121);
54//! assert_eq!(big.to_string(), "+++++");
55//! assert_eq!(big.to_dec(), 121);
56//!
57//! let neg_big = Ternary::from_dec(-121);
58//! assert_eq!(neg_big.to_string(), "-----");
59//! assert_eq!(neg_big.to_dec(), -121);
60//! ```
61//!
62//! ## Operations
63//! ```
64//! use balanced_ternary::Ternary;
65//!
66//! let repr9 = Ternary::parse("+00");
67//! let repr4 = Ternary::parse("++");
68//! let repr13 = &repr9 + &repr4;
69//! let repr17 = &repr13 + &repr4;
70//! let repr34 = &repr17 + &repr17;
71//!
72//! assert_eq!(repr13.to_string(), "+++");
73//! assert_eq!(repr17.to_string(), "+-0-");
74//! assert_eq!(repr34.to_string(), "++-+");
75//!
76//! let repr30 = &repr34 - &repr4;
77//! assert_eq!(repr30.to_dec(), 30);
78//! assert_eq!(repr30.to_string(), "+0+0");
79//! ```
80//!
81#![no_std]
82extern crate alloc;
83
84use alloc::string::{String, ToString};
85use alloc::vec::Vec;
86use alloc::{format, vec};
87use core::fmt::{Display, Formatter};
88use core::str::FromStr;
89
90/// Provides helper functions for formatting integers in a given radix.
91///
92/// Used internally to convert decimal numbers into their ternary representation.
93/// - `x`: The number to be formatted.
94/// - `radix`: The base of the numeral system.
95///
96/// Returns a string representation of the number in the specified base.
97fn format_radix(x: i64, radix: u32) -> String {
98    let mut result = vec![];
99    let sign = x.signum();
100    let mut x = x.abs() as u64;
101    loop {
102        let m = (x % radix as u64) as u32;
103        x /= radix as u64;
104        result.push(core::char::from_digit(m, radix).unwrap());
105        if x == 0 {
106            break;
107        }
108    }
109    format!(
110        "{}{}",
111        if sign == -1 { "-" } else { "" },
112        result.into_iter().rev().collect::<String>()
113    )
114}
115
116pub mod digit;
117
118pub use crate::digit::{
119    Digit,
120    Digit::{Neg, Pos, Zero},
121};
122
123/// Represents a balanced ternary number using a sequence of `Digit`s.
124///
125/// Provides functions for creating, parsing, converting, and manipulating balanced ternary numbers.
126#[derive(Debug, Clone, PartialEq, Eq, Hash)]
127pub struct Ternary {
128    digits: Vec<Digit>,
129}
130
131impl Ternary {
132    /// Creates a new balanced ternary number from a vector of `Digit`s.
133    pub fn new(digits: Vec<Digit>) -> Ternary {
134        Ternary { digits }
135    }
136
137    /// Returns the number of digits (length) of the balanced ternary number.
138    pub fn log(&self) -> usize {
139        self.digits.len()
140    }
141
142    /// Retrieves a slice containing the digits of the `Ternary`.
143    ///
144    /// # Returns
145    ///
146    /// A slice referencing the digits vec of the `Ternary`.
147    ///
148    /// This function allows access to the raw representation of the
149    /// balanced ternary number as a slice of `Digit` values.
150    pub fn to_digit_slice(&self) -> &[Digit] {
151        self.digits.as_slice()
152    }
153
154    /// Returns a reference to the [Digit] indexed by `index` if it exists.
155    ///
156    /// Digits are indexed **from the right**:
157    /// ```
158    /// use balanced_ternary::Ternary;
159    ///
160    /// // Indexes :
161    /// //                              32
162    /// //                             4||1
163    /// //                            5||||0
164    /// //                            ||||||
165    /// //                            vvvvvv
166    /// let ternary = Ternary::parse("+++--+");
167    /// assert_eq!(ternary.get_digit(1).unwrap().to_char(), '-')
168    /// ```
169    pub fn get_digit(&self, index: usize) -> Option<&Digit> {
170        self.digits.iter().rev().nth(index)
171    }
172
173    /// Parses a string representation of a balanced ternary number into a `Ternary` object.
174    ///
175    /// Each character in the string must be one of `+`, `0`, or `-`.
176    pub fn parse(str: &str) -> Self {
177        let mut repr = Ternary::new(vec![]);
178        for c in str.chars() {
179            repr.digits.push(Digit::from_char(c));
180        }
181        repr
182    }
183
184    /// Converts the `Ternary` object to its integer (decimal) representation.
185    ///
186    /// Calculates the sum of each digit's value multiplied by the appropriate power of 3.
187    pub fn to_dec(&self) -> i64 {
188        let mut dec = 0;
189        for (rank, digit) in self.digits.iter().rev().enumerate() {
190            dec += digit.to_i8() as i64 * 3_i64.pow(rank as u32);
191        }
192        dec
193    }
194
195    /// Creates a balanced ternary number from a decimal integer.
196    ///
197    /// The input number is converted into its balanced ternary representation,
198    /// with digits represented as `Digit`s.
199    pub fn from_dec(dec: i64) -> Self {
200        let sign = dec.signum();
201        let str = format_radix(dec.abs(), 3);
202        let mut carry = 0u8;
203        let mut repr = Ternary::new(vec![]);
204        for digit in str.chars().rev() {
205            let digit = u8::from_str(&digit.to_string()).unwrap() + carry;
206            if digit < 2 {
207                repr.digits.push(Digit::from_i8(digit as i8));
208                carry = 0;
209            } else if digit == 2 {
210                repr.digits.push(Digit::from_i8(-1));
211                carry = 1;
212            } else if digit == 3 {
213                repr.digits.push(Digit::from_i8(0));
214                carry = 1;
215            } else {
216                panic!("Ternary::from_dec(): Invalid digit: {}", digit);
217            }
218        }
219        if carry == 1 {
220            repr.digits.push(Digit::from_i8(1));
221        }
222        repr.digits.reverse();
223        if sign == -1 {
224            -&repr
225        } else {
226            repr
227        }
228    }
229
230    /// Converts the balanced ternary number to its unbalanced representation as a string.
231    ///
232    /// The unbalanced representation treats the digits as standard ternary (0, 1, 2),
233    /// instead of balanced ternary (-1, 0, +1). Negative digits are handled by
234    /// calculating the decimal value of the balanced ternary number and converting
235    /// it back to an unbalanced ternary string.
236    ///
237    /// Returns:
238    /// * `String` - The unbalanced ternary representation of the number, where each
239    /// digit is one of `0`, `1`, or `2`.
240    ///
241    /// Example:
242    /// ```
243    /// use balanced_ternary::Ternary;
244    ///
245    /// let repr = Ternary::parse("+--");
246    /// assert_eq!(repr.to_unbalanced(), "12");
247    /// assert_eq!(repr.to_dec(), 5);
248    /// let repr = Ternary::parse("-++");
249    /// assert_eq!(repr.to_unbalanced(), "-12");
250    /// assert_eq!(repr.to_dec(), -5);
251    /// ```
252    pub fn to_unbalanced(&self) -> String {
253        format_radix(self.to_dec(), 3)
254    }
255
256    /// Parses a string representation of an unbalanced ternary number into a `Ternary` object.
257    ///
258    /// The string must only contain characters valid in the unbalanced ternary numeral system (`0`, `1`, or `2`).
259    /// Each character is directly converted into its decimal value and then interpreted as a balanced ternary number.
260    ///
261    /// # Arguments
262    ///
263    /// * `unbalanced` - A string slice representing the unbalanced ternary number.
264    ///
265    /// # Returns
266    ///
267    /// A `Ternary` object representing the same value as the input string in balanced ternary form.
268    ///
269    /// # Panics
270    ///
271    /// This function will panic if the string is not a valid unbalanced ternary number.
272    /// For instance, if it contains characters other than `0`, `1`, or `2`.
273    ///
274    /// # Examples
275    ///
276    /// ```
277    /// use balanced_ternary::Ternary;
278    ///
279    /// let ternary = Ternary::from_unbalanced("-12");
280    /// assert_eq!(ternary.to_string(), "-++");
281    /// assert_eq!(ternary.to_dec(), -5);
282    /// ```
283    pub fn from_unbalanced(unbalanced: &str) -> Self {
284        Self::from_dec(i64::from_str_radix(unbalanced, 3).unwrap())
285    }
286}
287
288impl Display for Ternary {
289    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
290        let mut str = String::new();
291        for digit in self.digits.iter() {
292            str.push(digit.to_char());
293        }
294        write!(f, "{}", str)
295    }
296}
297
298pub mod operations;
299
300#[cfg(feature = "tryte")]
301pub mod tryte;
302
303#[cfg(feature = "tryte")]
304pub use crate::tryte::Tryte;
305
306#[cfg(test)]
307#[test]
308fn test_ternary() {
309    use crate::*;
310
311    let repr5 = Ternary::new(vec![Pos, Neg, Neg]);
312    assert_eq!(repr5.to_dec(), 5);
313    let repr5 = Ternary::from_dec(5);
314    assert_eq!(repr5.to_dec(), 5);
315
316    let repr13 = Ternary::new(vec![Pos, Pos, Pos]);
317    assert_eq!(repr13.to_dec(), 13);
318
319    let repr14 = Ternary::parse("+---");
320    let repr15 = Ternary::parse("+--0");
321    assert_eq!(repr14.to_dec(), 14);
322    assert_eq!(repr15.to_dec(), 15);
323    assert_eq!(repr14.to_string(), "+---");
324    assert_eq!(repr15.to_string(), "+--0");
325
326    let repr120 = Ternary::from_dec(120);
327    assert_eq!(repr120.to_dec(), 120);
328    assert_eq!(repr120.to_string(), "++++0");
329    let repr121 = Ternary::from_dec(121);
330    assert_eq!(repr121.to_dec(), 121);
331    assert_eq!(repr121.to_string(), "+++++");
332
333    let repr_neg_5 = Ternary::parse("-++");
334    assert_eq!(repr_neg_5.to_dec(), -5);
335    assert_eq!(repr_neg_5.to_string(), "-++");
336
337    let repr_neg_5 = Ternary::from_dec(-5);
338    assert_eq!(repr_neg_5.to_dec(), -5);
339    assert_eq!(repr_neg_5.to_string(), "-++");
340
341    let repr_neg_121 = Ternary::from_dec(-121);
342    assert_eq!(repr_neg_121.to_dec(), -121);
343    assert_eq!(repr_neg_121.to_string(), "-----");
344
345    let test = Ternary::from_dec(18887455);
346    assert_eq!(test.to_dec(), 18887455);
347    assert_eq!(test.to_string(), "++00--0--+-0++0+");
348
349    let unbalanced = Ternary::from_unbalanced("12");
350    assert_eq!(unbalanced.to_dec(), 5);
351    assert_eq!(unbalanced.to_string(), "+--");
352
353    let unbalanced = Ternary::from_unbalanced("-12");
354    assert_eq!(unbalanced.to_dec(), -5);
355    assert_eq!(unbalanced.to_string(), "-++");
356
357    let unbalanced = Ternary::from_dec(121);
358    assert_eq!(unbalanced.to_unbalanced(), "11111");
359    assert_eq!(unbalanced.to_string(), "+++++");
360}
balanced_ternary/lib.rs

balanced_ternary/
lib.rs
